题解|生成频繁项集

频繁项集就是在交易数据中出现频率超过指定阈值的项集，常用于关联规则挖掘。 通俗点说，频繁项集就是交易数据中出现得“够多”的项集。

生成频繁项集可以归结为如下的递归过程

1. 从频繁k项集中组合出候选k+1项集
2. 统计候选k+1项集在交易数据中出现的次数
3. 过滤出频繁k+1项集（出现次数大于等于min_support）
4. 重复上述过程，直到无法生成更高阶的频繁项集 在实际实现上，组合出候选集的方式有很多种，但本题通过直接枚举合并出所有可能的k+1项集来简化代码实现，然后统计出现次数，最后过滤出频繁k+1项集，这种方式在数据量较大时，效率较低。实际运用中不建议大家使用。

代码实现

from itertools import combinations
from collections import defaultdict

def generate_frequent_itemsets(transactions, min_support):
    item_count = defaultdict(int)
    for transaction in transactions:
        items = transaction.split(',')
        for item in items:
            item_count[item.strip()] += 1

    # 过滤出1项频繁项集
    frequent_itemsets = {item: count for item, count in item_count.items() if count >= min_support}
    
    # 生成更高阶的频繁项集
    k = 2
    while True:
        # 组合k个项
        new_combinations = combinations(frequent_itemsets.keys(), k)
        # 统计k个项在交易数据中出现的次数
        new_item_count = defaultdict(int)
        # 遍历交易数据，统计k个项在交易数据中出现的次数
        for transaction in transactions:
            items = set(transaction.split(','))
            for combo in new_combinations:
                if all(item in items for item in combo):
                    new_item_count[combo] += 1
        
        # 过滤出频繁项集
        frequent_itemsets_k = {combo: count for combo, count in new_item_count.items() if count >= min_support}
        # 如果k个项在交易数据中出现的次数小于min_support，则停止生成更高阶的频繁项集
        if not frequent_itemsets_k:
            break
        
        frequent_itemsets.update(frequent_itemsets_k)
        k += 1

    return frequent_itemsets

# 主程序
T = int(input())
transactions = [input().strip() for _ in range(T)]

min_support = int(input())

frequent_itemsets = generate_frequent_itemsets(transactions, min_support)

# 输出结果
for itemset, count in sorted(frequent_itemsets.items(), key=lambda x: -x[1]):
    if isinstance(itemset, str):
        print(f'{{{itemset}}}\n')
    else:
        print(f'{{{", ".join(itemset)}}}\n')