手写Apriori算法及其在关联规则挖掘中的应用

题目描述

Apriori算法是数据挖掘中经典的关联规则挖掘算法，用于发现事务数据库中的频繁项集（经常一起出现的物品集合）和关联规则。题目要求你理解Apriori算法的原理，并能够手写实现其核心步骤，包括生成候选项集、计算支持度、剪枝等过程。

知识讲解

1. 基本概念

首先明确几个核心术语：

• 事务（Transaction）：一次购买行为或一次记录，如购物篮中的商品集合。
• 项集（Itemset）：一个或多个商品的集合。
• 支持度（Support）：项集在总事务中出现的频率。例如，项集{A, B}的支持度 = 包含A和B的事务数 / 总事务数。
• 置信度（Confidence）：规则A→B的置信度 = 支持度({A, B}) / 支持度({A})，表示在包含A的事务中，有多大比例也包含B。
• 频繁项集：支持度不低于设定最小支持度阈值的项集。

2. 算法核心思想

Apriori算法基于一个关键性质：如果一个项集是频繁的，那么它的所有子集也一定是频繁的。反之，如果一个项集是非频繁的，那么它的所有超集也一定是非频繁的。这可以大幅减少候选项集的数量。

解题步骤（手写实现）

假设我们有一个事务数据库D：

T1: {A, B, C}
T2: {A, C}
T3: {A, B}
T4: {B, C}
T5: {A, B, C, D}

最小支持度 min_support = 0.4（即支持数 >= 0.4 * 5 = 2）。

步骤1：生成候选1-项集并计算支持度

首先扫描所有事务，统计每个单项的支持数。

• C1: {A}:4, {B}:4, {C}:4, {D}:1
  比较支持数（>=2）：{A}, {B}, {C}是频繁的，{D}被剪枝。
  得到频繁1-项集 L1 = [{A}, {B}, {C}]。

步骤2：生成候选2-项集

由L1生成候选2-项集C2，通过连接L1中的项集（自连接）并确保前k-1项相同，这里k=2：

• C2 = [{A, B}, {A, C}, {B, C}]。
  然后扫描数据库计算支持数：
• {A, B}: 出现在T1, T3, T5 → 支持数=3
• {A, C}: 出现在T1, T2, T5 → 支持数=3
• {B, C}: 出现在T1, T4, T5 → 支持数=3
  比较支持数（>=2）：全部通过。
  得到频繁2-项集 L2 = [{A, B}, {A, C}, {B, C}]。

步骤3：生成候选3-项集

由L2生成候选3-项集C3。连接L2中的项集（自连接）：

• 取{A, B}和{A, C}，它们的前k-2=1项相同（都是A），连接得到{A, B, C}。
  剪枝：{A, B, C}的所有2-项子集为{A, B}, {A, C}, {B, C}，它们都在L2中，所以保留。
  C3 = [{A, B, C}]。
  扫描数据库计算支持数：
• {A, B, C}: 出现在T1, T5 → 支持数=2
  比较支持数（>=2）：通过。
  得到频繁3-项集 L3 = [{A, B, C}]。

步骤4：生成更高阶项集

尝试生成候选4-项集C4。由于L3只有一个项集，无法连接，算法终止。

步骤5：从频繁项集生成关联规则

以频繁项集{A, B, C}为例，可以生成规则如A→BC, B→AC, C→AB, AB→C, AC→B, BC→A。
对每条规则计算置信度。例如规则AB→C：

• 支持度({A, B, C}) = 2/5 = 0.4
• 支持度({A, B}) = 3/5 = 0.6
• 置信度 = 0.4 / 0.6 ≈ 0.667
  如果置信度高于设定的最小置信度（例如0.5），则该规则成立。

代码实现（Python）

from itertools import combinations

def get_frequent_itemsets(transactions, min_support):
    """返回所有频繁项集及其支持数"""
    items = set()
    for transaction in transactions:
        items.update(transaction)
    
    # 生成候选1-项集
    C1 = [frozenset([item]) for item in items]
    L, supports = generate_frequent(C1, transactions, min_support)
    
    frequent_itemsets = L.copy()
    k = 2
    while L:  # 当还能生成频繁项集时继续
        # 生成候选k-项集
        Ck = apriori_gen(L, k)
        L, new_supports = generate_frequent(Ck, transactions, min_support)
        supports.update(new_supports)
        frequent_itemsets.extend(L)
        k += 1
    
    return frequent_itemsets, supports

def generate_frequent(candidates, transactions, min_support):
    """计算候选项集的支持数，并返回频繁项集"""
    counts = {}
    for transaction in transactions:
        for candidate in candidates:
            if candidate.issubset(transaction):
                counts[candidate] = counts.get(candidate, 0) + 1
    
    n_trans = len(transactions)
    L = []
    supports = {}
    for itemset, count in counts.items():
        support = count / n_trans
        if support >= min_support:
            L.append(itemset)
            supports[itemset] = count
    
    return L, supports

def apriori_gen(L, k):
    """由频繁(k-1)-项集L生成候选k-项集"""
    candidates = set()
    n = len(L)
    itemsets = list(L)
    
    for i in range(n):
        for j in range(i+1, n):
            # 连接条件：前k-2项相同
            itemset1 = list(itemsets[i])
            itemset2 = list(itemsets[j])
            itemset1.sort()
            itemset2.sort()
            if itemset1[:k-2] == itemset2[:k-2]:
                candidate = itemsets[i] | itemsets[j]
                # 剪枝：检查所有(k-1)-子集是否频繁
                if all(frozenset(comb) in L for comb in combinations(candidate, k-1)):
                    candidates.add(candidate)
    
    return list(candidates)

def generate_rules(frequent_itemsets, supports, min_confidence):
    """生成关联规则"""
    rules = []
    for itemset in frequent_itemsets:
        if len(itemset) < 2:
            continue
        
        # 生成所有可能的规则
        for i in range(1, len(itemset)):
            for antecedent in combinations(itemset, i):
                antecedent = frozenset(antecedent)
                consequent = itemset - antecedent
                
                # 计算置信度
                conf = supports[itemset] / supports[antecedent]
                if conf >= min_confidence:
                    rules.append((antecedent, consequent, conf))
    
    return rules

# 示例使用
transactions = [
    {'A', 'B', 'C'},
    {'A', 'C'},
    {'A', 'B'},
    {'B', 'C'},
    {'A', 'B', 'C', 'D'}
]

min_support = 0.4
min_confidence = 0.5

# 转换为frozenset列表便于计算
transactions = [frozenset(t) for t in transactions]

frequent_itemsets, supports = get_frequent_itemsets(transactions, min_support)
print("频繁项集及支持数:")
for itemset in frequent_itemsets:
    print(f"{set(itemset)}: {supports[itemset]}")

rules = generate_rules(frequent_itemsets, supports, min_confidence)
print("\n关联规则:")
for ante, cons, conf in rules:
    print(f"{set(ante)} -> {set(cons)}: {conf:.3f}")

算法优化与变种

1. FP-Growth算法：通过构建频繁模式树（FP-tree）来避免生成候选项集，效率更高。
2. 垂直数据格式：将事务数据库转为项-事务ID列表的形式，可以加速支持度计算。
3. 分区和抽样：对大数据集进行分区处理或抽样，减少内存消耗。

应用场景

• 购物篮分析：发现商品之间的购买关系，如“买啤酒的人常买尿布”。
• 推荐系统：基于用户行为模式推荐相关商品。
• 医疗诊断：发现症状与疾病之间的关联。
• 网络入侵检测：识别异常行为模式。

通过这个详细的讲解，你应该能够理解Apriori算法的每一步原理，并能够自己实现关联规则挖掘。