题解|关联规则发现（Apriori算法）

Apriori算法是关联规则挖掘中的一种经典算法，用于发现数据集中频繁项集和关联规则。

频繁项集：在数据集中频繁出现的项集。 关联规则：在数据集中，若A则B的规则形式。 支持度：项集A在数据集中出现的次数除以数据集的总数。通俗点说，就是项集A在数据集中出现的概率。 置信度：项集A和项集B同时出现的次数除以项集A出现的次数。通俗点说，就是项集A出现时，项集B出现的概率。

频繁项集的生成：

1. 扫描数据集，生成1-频繁项集。
2. 对当前频繁项集，生成候选频繁项集,并计算其支持度。
3. 根据支持度阈值，筛选出频繁项集，并更新当前频繁项集。
4. 重复2-3，直到无法生成新的频繁项集。

关联规则的生成：

1. 对一个频繁项集，枚举其所有非空子集作为规则前件，剩余部分作为规则后件。
2. 对每个规则，计算其置信度。
3. 根据置信度阈值，筛选出关联规则。
4. 重复2-3，直到无法生成新的关联规则。

在本题中，频繁项集的生成和关联规则的生成是分开的，需要先生成频繁项集，再生成关联规则。

此外，在频繁项集的生成和关联规则的生成中，本题预先给出使用位运算来枚举子集的代码，但实际运用上，有其他高效的方法。这里不做赘述。

代码实现

def apriori(transactions, min_sup, min_conf):
    itemCount = defaultdict(int)
    
    # 计算每个单项的支持度
    for transaction in transactions:
        for item in transaction:
            itemCount[item] += 1
            
    # 筛选频繁1项集
    frequent_itemsets = {frozenset([item]) for item in itemCount if itemCount[item] / len(transactions) >= min_sup}
    
    k = 2
    all_frequent_itemsets = frequent_itemsets.copy()  # 存储所有频繁项集
    
    while frequent_itemsets:
        itemset_count = defaultdict(int)
        
        # 生成候选k项集
        candidate_itemsets = [frozenset(x) for x in combinations(list(set().union(*frequent_itemsets)), k)]
        
        # 计算候选项集的支持度
        for transaction in transactions:
            for candidate in candidate_itemsets:
                if candidate.issubset(transaction):
                    itemset_count[candidate] += 1
        
        # 筛选频繁k项集
        frequent_itemsets = {itemset for itemset, count in itemset_count.items() if count / len(transactions) >= min_sup}
        
        # 更新所有频繁项集
        all_frequent_itemsets.update(frequent_itemsets)
        
        k += 1
    
    # 生成关联规则
    rules = []
    # 遍历所有频繁项集
    for itemset in all_frequent_itemsets:
        itemlist = list(itemset)
        # 遍历频繁项集的子集大小
        for i in range(1, len(itemlist)):
            # 枚举子集作为规则前件
            for subset in combinations(itemlist, i):
                antecedent = subset
                consequent = itemset - antecedent
                conf = confidence(antecedent, consequent, transactions)
                if conf >= min_conf:
                    rules.append((antecedent, consequent, conf))
    
    return rules