频繁项集(Frequent Itemset)挖掘算法笔记

"这篇笔记主要介绍了频繁项集(Frequent Itemset)的概念以及关联规则(Association Rules)，并探讨了寻找频繁项集的算法，包括朴素算法和Apriori算法，同时还涉及了内存优化策略和多阶段算法。" 在数据挖掘领域，市场购物篮模型是一个常见的例子，用于分析消费者购买行为。在这个模型中，每个篮子代表一个客户的购买记录，而项集（itemset）则是一组被同时购买的商品。频繁项集是指在数据集中出现频率超过一定阈值的项集，通常这个阈值设定为总交易量的1%。 基本定义中，项集是一组商品，而购物篮（basket）是包含这些项的交易记录集合。支持度是衡量项集频繁程度的指标，即项集在所有篮子中出现的比例。例如，如果一个项集在1%的篮子中出现，那么它的支持度就是1%。 寻找频繁项集的算法可以扩展到不同大小的项集，比如从频繁对到频繁三元组等。在处理非连续的item_id时，可以使用哈希函数将其映射到连续空间以节省存储空间。计数方法通常有两种：三角矩阵和哈希表。前者在空间占用上随着项数量的增加呈线性增长，后者则更高效，尤其在查找和更新计数时。 朴素算法是最直观的方法，它逐块读取数据，对每个块中的项集计数。然而，这种方法效率较低，因为它需要扫描数据多次，计算所有可能的项集。为了解决这个问题，Apriori算法应运而生，它利用了“频繁项集的任何子集也必须是频繁的”这一特性，显著减少了候选项集的生成，提高了效率。 Apriori算法包括两个主要步骤：生成频繁项集和构建关联规则。在实现时，可以采取优化策略，如利用主内存（PCY算法）来减少磁盘I/O，或者采用多阶段算法，逐步找出频繁项集。 关联规则是描述项集间关系的表达式，形式为：“如果X发生，那么Y也倾向于发生”，其中X和Y是项集，且Y是X的子集。规则的可信度（confidence）是规则发生的概率，计算为支持度(X U Y) / 支持度(X)。 总结来说，这篇笔记涵盖了频繁项集挖掘的基本概念、算法和优化策略，对于理解数据挖掘中的关联规则分析具有重要价值。