关联规则挖掘中的FP-tree算法及效果

2025-09-30 理论教育版权反馈

【摘要】：设数据集D被分割成分块D1，D2，...，Dn，全局最小支持数为minsup_count。因此，探索新的理论和算法来减少数据库的扫描次数和候选集空间占用，已经成为近年来关联规则挖掘研究的热点之一，典型的方法是FP-tree算法。

1.Apriori算法的性能瓶颈

Apriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。

Apriori算法有两个致命的性能瓶颈：第一，多次扫描事务数据库，需要很大的I/O负载，对每次k循环，侯选集Ck中的每个元素都必须通过扫描一次数据库来验证其是否加入Lk。假如有一个频繁项目集包含10个项的话，那么就至少需要扫描事务数据库10遍。第二，可能产生庞大的侯选集，由Lk-1产生k-侯选集Ck是指数增长的，例如104个1-频繁项目集就有可能产生接近107个元素的2-侯选集。如此大的候选集对时间和主存空间都是一种挑战。

2.提高Apriori算法效率的技术(https://www.chuimin.cn)

一些算法虽然仍然遵循Apriori属性，但是由于引入了相关技术，在一定程度上改善了Apriori算法的适应性和效率。主要的改进方法：基于数据分割（Partition）的方法，基本原理是在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的。基于散列（Hash）的方法，基本原理是，在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的。基于采样（Sampling）的方法，基本原理是通过采样技术，评估被采样的子集中，并依次来估计k-项集的全局频度。其他，如动态删除没有用的事务：不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除。

基于数据分割的方法。设数据集D被分割成分块D1，D2，...，Dn，全局最小支持数为minsup_count。如果一个数据分块Di的局部最小支持数minsup_counti（i=1，2，…，n），按着如下方法生成：minsup_counti=minsup_count||Di||/||D||，则所有的局部频繁项目集涵盖全局频繁项目集。作用：（1）合理利用主存空间。数据分割将大数据集分成小的块，为块内数据一次性导入主存提供机会。（2）支持并行挖掘算法。每个分块的局部频繁项目集是独立生成的，因此提供了开发并行数据挖掘算法的良好机制。

探索新的理论。随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和候选集空间占用，已经成为近年来关联规则挖掘研究的热点之一，典型的方法是FP-tree算法。

关联规则挖掘中的FP-tree算法及效果

相关推荐