数据挖掘FP-tree树

数据仓库与数据挖掘课程报告

——FP-tree算法的思考与实现

指导老师：蒋良孝 姓名：赵冠豪 班级：086131 学号：20131002562 2015年10月

FP——tree算法的思考与实现

FP-Tree算法的思考与实现

1.发现问题

在学习数据仓库与数据挖掘课程中，有关关联分析的算法，首先是在1994年R.Agrawal和R.Srikant提出的布尔关联规则挖掘频繁项集的原创性算法——Apriori算法，一种使用候选产生发现频繁项集的算法。下面以课本P151页例5-3来进行Apriori算法的演示。

AllElectronics某分店的业务数据

TID 商品ID的列表 I1，I2，I3 I2，I4 I2,I3 I1，I2，I4 I1，I3 I2，I3 I1，I3 I1，I2，I3，I5 I1，I2，I3 T100 T200 T300 T400 T500 T600 T700 T800 T900 假设候选项集和频繁项集的产生，最小支持计数为2 那么根据Apriori算法进行演示： C1 项集 比较候选支持度计数与最小支持度计数 L1 支持度计数 6 7 6 2 2 项集 支持度计数 扫描D，对每个候选计数 {I1} {I2} {I3} {I4} {I5} 6 7 6 2 2 {I1} {I2} {I3} {I4} {I5} 1

FP——tree算法的思考与实现

项集 {I1，I2} 由L1产生候选C2，并扫描D对每个候选计数 {I1，I3} {I1，14} {I1，I5} {I2，I3} 由L2产生候选C3，并扫描D对每个候选计数

通过此演示，我们可以清晰地发现：虽然在许多情况下，Apriori的候选产生-检查方法显著压缩了候选项集的大小，并导致很好的性能。然而，Apriori算法的每次迭代都会扫描事务数据库，并且每次每次都会产生大量候选项集，这是Apriori算法的致命缺陷。

例如，如果有10^4个频繁1项集，则Apriori算法需要产生多达10^7个候选二项集。此外为发现长度为100的频繁模式，如{a1,a2,?,a100},必须产生总过多达2^100大约为10^30个候选。再如，Apriori算法需要不断重复扫描数据库，通过模式匹配检查一个很大的候选集合。检查数据库中的每个事务来确定候选项集的支持度的开销非常大。

因此我们可以得到一个很清晰的结论，在一般情况下，我们在使用Apriori算法（使用候选产生发现频繁项集的方法）进行关联分析时，想要找到感兴趣的规则，开销是非常大的，而这正是Apriori算法在实际运用中要改善的问题。

{12，I4} {I2，I5} {I3，I4} {I3，I5} {I4，15} 4 4 1 2 4 2 2 0 1 0 比较候选支持度计数与最小支持度计数 项集 {I1，I2} {I1，I3} {I1，I5} {I2，I3} {12，I4} {I2，I5} 支持度计数 4 4 2 4 2 2 支持度计数 C2 L2 C3 项集 {I1，I2，I3} {I1，I2,I5} 支持度计数 2 2 比较候选支持度计数与最小支持度计数 L3 项集 {I1，I2，I3} {I1，I2,I5} 支持度计数 2 2 2