Apriori算法在数据挖掘中的实战优化：从频繁项集到高效实现

1次阅读

没有评论

共计 1845 个字符，预计需要花费 5 分钟才能阅读完成。

频繁项集挖掘是数据挖掘中的核心问题之一，广泛应用于购物篮分析、推荐系统、异常检测等领域。传统 Apriori 算法通过逐层搜索和剪枝策略来发现频繁项集，但其面临两大主要问题：

时间复杂度高 ：需要多次扫描数据库，候选集生成和剪枝过程耗时
内存消耗大 ：随着项集长度增加，候选集数量呈指数级增长

在解决频繁项集挖掘问题时，FP-Growth 算法通常被视为 Apriori 的替代方案。但 Apriori 仍有其优势：

算法原理简单易懂，适合教学和原型开发
某些特定场景下（如项集长度较短时）性能表现良好
优化空间大，通过改进可以显著提升性能

传统 Apriori 使用水平数据格式（事务 - 项），我们可以转换为垂直格式（项 - 事务 ID 列表）：

# 转换为垂直数据格式示例
def create_vertical_data(transactions):
    vertical_data = {}
    for tid, items in enumerate(transactions):
        for item in items:
            if item not in vertical_data:
                vertical_data[item] = set()
            vertical_data[item].add(tid)
    return vertical_data

将事务 ID 列表转换为位图可以加速支持度计算：

确定事务总数 N
为每个项创建长度为 N 的位图
通过位运算快速计算项集支持度

利用多线程或分布式计算来并行化候选生成过程：

将项集划分为多个子集
在不同线程 / 节点上并行生成候选
合并结果并进行剪枝

以下是优化后的 Apriori 算法 Python 实现核心部分：

from itertools import combinations
from collections import defaultdict

def apriori_optimized(transactions, min_support):
    # 转换数据格式
    vertical_data = create_vertical_data(transactions)
    total_trans = len(transactions)

    # 生成频繁 1 - 项集
    freq_items = {frozenset([item]): len(tids)/total_trans
                 for item, tids in vertical_data.items()
                 if len(tids)/total_trans >= min_support}

    # 迭代生成更大项集
    k = 2
    while freq_items:
        yield freq_items

        # 生成候选
        candidates = set()
        items = [set(item) for item in freq_items.keys()]
        for i in range(len(items)):
            for j in range(i+1, len(items)):
                candidate = items[i] | items[j]
                if len(candidate) == k:
                    candidates.add(frozenset(candidate))

        # 计算支持度
        freq_items = {}
        for candidate in candidates:
            # 使用垂直数据快速计算支持度
            tids = set.intersection(*[vertical_data[item] for item in candidate])
            support = len(tids)/total_trans
            if support >= min_support:
                freq_items[candidate] = support

        k += 1

我们在 Groceries 数据集上对比优化前后的性能：