apriori algorithm is a association rule mining technique also known as market basket analysis aims to discover interesting relationships or associations among a set of items in a transactional or relational database for example apriori algorithm states if a customer buys item a and item b then they are likely to buy item c this rule suggests a relationship between items a b and c indicating that customers who purchased a and b are more likely to also purchase item c wiki https en wikipedia orgwikiapriorialgorithm examples https www kaggle comcodeearthianaprioriassociationrulesmining returns a sample transaction dataset loaddata milk milk butter milk bread milk bread chips prune candidate itemsets that are not frequent the goal of pruning is to filter out candidate itemsets that are not frequent this is done by checking if all the k1 subsets of a candidate itemset are present in the frequent itemsets of the previous iteration valid subsequences of the frequent itemsets from the previous iteration prunes candidate itemsets that are not frequent itemset x y z candidates x y x z y z pruneitemset candidates 2 x y x z y z itemset 1 2 3 4 candidates 1 2 4 pruneitemset candidates 3 returns a list of frequent itemsets and their support counts data a b c a b a c a d b c aprioridata 2 a b 1 a c 2 b c 2 data 1 2 3 1 2 1 3 1 4 2 3 aprioridata 3 count itemset support prune infrequent itemsets append frequent itemsets as a list to maintain order apriori algorithm for finding frequent itemsets args data a list of transactions where each transaction is a list of items minsupport the minimum support threshold for frequent itemsets returns a list of frequent itemsets along with their support counts userdefined threshold or minimum support level returns a sample transaction dataset load_data milk milk butter milk bread milk bread chips prune candidate itemsets that are not frequent the goal of pruning is to filter out candidate itemsets that are not frequent this is done by checking if all the k 1 subsets of a candidate itemset are present in the frequent itemsets of the previous iteration valid subsequences of the frequent itemsets from the previous iteration prunes candidate itemsets that are not frequent itemset x y z candidates x y x z y z prune itemset candidates 2 x y x z y z itemset 1 2 3 4 candidates 1 2 4 prune itemset candidates 3 returns a list of frequent itemsets and their support counts data a b c a b a c a d b c apriori data 2 a b 1 a c 2 b c 2 data 1 2 3 1 2 1 3 1 4 2 3 apriori data 3 count itemset support prune infrequent itemsets append frequent itemsets as a list to maintain order apriori algorithm for finding frequent itemsets args data a list of transactions where each transaction is a list of items min_support the minimum support threshold for frequent itemsets returns a list of frequent itemsets along with their support counts user defined threshold or minimum support level
from itertools import combinations


def load_data() -> list[list[str]]:
    
    return [["milk"], ["milk", "butter"], ["milk", "bread"], ["milk", "bread", "chips"]]


def prune(itemset: list, candidates: list, length: int) -> list:
    
    pruned = []
    for candidate in candidates:
        is_subsequence = True
        for item in candidate:
            if item not in itemset or itemset.count(item) < length - 1:
                is_subsequence = False
                break
        if is_subsequence:
            pruned.append(candidate)
    return pruned


def apriori(data: list[list[str]], min_support: int) -> list[tuple[list[str], int]]:
    
    itemset = [list(transaction) for transaction in data]
    frequent_itemsets = []
    length = 1

    while itemset:
        
        counts = [0] * len(itemset)
        for transaction in data:
            for j, candidate in enumerate(itemset):
                if all(item in transaction for item in candidate):
                    counts[j] += 1

        
        itemset = [item for i, item in enumerate(itemset) if counts[i] >= min_support]

        
        for i, item in enumerate(itemset):
            frequent_itemsets.append((sorted(item), counts[i]))

        length += 1
        itemset = prune(itemset, list(combinations(itemset, length)), length)

    return frequent_itemsets


if __name__ == "__main__":
    
    import doctest

    doctest.testmod()

    
    frequent_itemsets = apriori(data=load_data(), min_support=2)
    print("\n".join(f"{itemset}: {support}" for itemset, support in frequent_itemsets))