数据挖掘FP-tree树

数据仓库与数据挖掘课程报告——FP-tree算法的思考与实现指导老师：蒋良孝姓名：赵冠豪班级：086131学号：201310025622015年10月FP——tree算法的思考与实现1FP-Tree算法的思考与实现1.发现问题在学习数据仓库与数据挖掘课程中，有关关联分析的算法，首先是在1994年R.Agrawal和R.Srikant提出的布尔关联规则挖掘频繁项集的原创性算法——Apriori算法，一种使用候选产生发现频繁项集的算法。下面以课本P151页例5-3来进行Apriori算法的演示。AllElectronics某分店的业务数据TID商品ID的列表T100I1，I2，I3T200I2，I4T300I2,I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3假设候选项集和频繁项集的产生，最小支持计数为2那么根据Apriori算法进行演示：项集支持度计数{I1}{I2}{I3}{I4}{I5}67622项集支持度计数{I1}{I2}{I3}{I4}{I5}67622扫描D，对每个候选计数比较候选支持度计数与最小支持度计数C1L1FP——tree算法的思考与实现2通过此演示，我们可以清晰地发现：虽然在许多情况下，Apriori的候选产生-检查方法显著压缩了候选项集的大小，并导致很好的性能。然而，Apriori算法的每次迭代都会扫描事务数据库，并且每次每次都会产生大量候选项集，这是Apriori算法的致命缺陷。例如，如果有10^4个频繁1项集，则Apriori算法需要产生多达10^7个候选二项集。此外为发现长度为100的频繁模式，如{a1,a2,…,a100},必须产生总过多达2^100大约为10^30个候选。再如，Apriori算法需要不断重复扫描数据库，通过模式匹配检查一个很大的候选集合。检查数据库中的每个事务来确定候选项集的支持度的开销非常大。因此我们可以得到一个很清晰的结论，在一般情况下，我们在使用Apriori算法（使用候选产生发现频繁项集的方法）进行关联分析时，想要找到感兴趣的规则，开销是非常大的，而这正是Apriori算法在实际运用中要改善的问题。项集支持度计数{I1，I2}{I1，I3}{I1，I5}{I2，I3}{12，I4}{I2，I5}442422项集支持度计数{I1，I2}{I1，I3}{I1，14}{I1，I5}{I2，I3}{12，I4}{I2，I5}{I3，I4}{I3，I5}{I4，15}4412422010项集支持度计数{I1，I2，I3}{I1，I2,I5}22项集支持度计数{I1，I2，I3}{I1，I2,I5}22由L1产生候选C2，并扫描D对每个候选计数比较候选支持度计数与最小支持度计数由L2产生候选C3，并扫描D对每个候选计数比较候选支持度计数与最小支持度计数C2L2C3L3FP——tree算法的思考与实现32.分析问题经过上面的分析我们可以确定，Apriori算法的两大限制：○1产生大量的候选集；○2重复扫描事务数据库。那么我们分析如何提高Apriori算法的效率时，就有着两大分析方向。一是考虑降低是事务数据库的扫描次数，如能不能先扫描一次事务数据库，然后进行分类划分，找出局部频繁项集，然后在进行下次扫描。二是考虑如何压缩候选集，在产生的时候就进行剔除，或者对未来要产生的候选项集，增加一个规则，压缩未来迭代扫描的事务数。显然无论是降低扫描的事务数据库的次数，还是压缩产生的候选集，都是针对于Apriori算法本身的调整，这就不可能在本质上解决Apriori算法的效率低下问题。在思考这个问题时，我很容易想到，既然是产生大量的候选项集，那么一个很直接的办法就是：能不能不产生候选集，而直接发现频繁项集，从而找出感兴趣的关联规则呢。如果我们不产生大量的候选集，那么扫描事务数据库进行匹配的次数也自然就会大大降低。我在思考过程中，想到老师上课讲到的一句话“把条件进行简单化处理，先找出一个可行解”，这样思维就大大开阔。联系到《数据仓库与数据挖掘》在开始的课程“分类”中的第一个方法：决策树，显然关联分析是进行名词性布尔值的分析，而决策树的应用范围也正是名词性数据的分类。我们来对比下，在决策树算法中，我们根据元组的信息增益的大小来进行生成树的判断依据。类比决策树算法，我们可以利用关联分析中事务发生的支持计数的大小来代替熵减值。根据我在《算法导论》中所学习到的思想——递归算法中的分治策略，再加上决策树这个“先例”的借鉴，我对于提高Apriori算法的效率有了一个较为清晰的方向。首先，对于事务数据库中的所有事务都是由一项集构成的，所以我们可以根据在整个事务数据库中所有的一项集的支持计数来进行排序（类似决策树中对于每个元组的熵减值计算）。接着，参考决策树算法中树的生成方法和分治策略思想，我们在扫描事务数据库的一个事务时，根据第一步的排序顺位，进行调整，将该事务的所有项都有序化，依照顺序建立一棵树，下次的事务按照这个方法继续对前面的树的节点值进行修改、增加节点或者生成另一棵树，这样我们就可以保证越靠近树根的支持计数越高，而叶子节点的支持计数越低，十分有利于降低我们在挖掘有趣规则时的开销。3.解决问题经过上面的分析后，我们对于怎么提高Apriori算法的有了一个有效的解决办法。而且在2000年针对Apriori算法的固有缺陷，J.Han等人提出了不产生候选频繁项集的方法即FP-tree算法。该算法直接将事务数据库压缩成一个频繁模式树，然后通过这棵树生成关联规则。而这个算法和我上面分析时提出的思想大致相同，下面我们仍然根据书上的例子进行FP-tree算法的演示：第一步，进行事务数据库的扫描，得到每个一项集的支持计数，然后进行排序。所有一项集的计数：{I1,6}，{I2,7}{I3,6},{I4,2},{I5,2}；按照支持计数进行排序I2I1I3I4I576622FP——tree算法的思考与实现4第二步，扫描事务数据库的每个事务，生成树。第三步，进行强关联规则的挖掘。挖掘前，先进行一下解释和定义：由每个长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP树与后缀式一起出现的前缀路径集组成），然后，构造它的（条件）FP树，并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。首先考虑I5——L中的最后一项，而不是第一个。I5出现在树最深层的叶子节点上，并且有两个叶子节点，我们把这两条路径列出来{I2，I1，I5：1},{I2，I1，I3，I5：1}，显然I5的前缀路径是{I2，I1：1}，{I2，I1，I3：1}，形成I5的条件模式基，而它的条件FP树显然只包含{I2,I1:2}（I3只出现一次，小于最小支持计数2）。因此次路径产生的频繁模式的所有组合：{I2，I5:2},{I1，I5:2},{I2，I1，I5：2}。那么基于I5的所有条件模式产生的频繁模式都找到了。同样的方法进行I4，I3I1的迭代，得到下表：项条件模式基条件FP树产生的频繁模式I5{{I2I1：1},I2：2，I1：2{I2I5：2},{I1I5：2}{I2I1，I3：1}}{I2I1I5：2}I4{{I2I1：1}I2：2{I2I4：2}{I2：1}}I3{{I2I1：2}I2：4，I1：2{I2I3：4},{I1I3：4}{I2：2},{I1：2}}I1：2{I2I1I3：2}I1{{I2：4}}I2：4{I2I1:4}NullI2:7I1:4I5:1I3:2I4:1I4:1I3:2I5:1I1:2I3:2FP——tree算法的思考与实现54.得出结论根据上面的算法演示，我们接下来进行试验测试。首先根据上机时老师讲到的利用Myeclipse将weka当做一个项目文件，在java平台运行。由于我只是实现了FP-tree算法，所以我直接运用weka平台进行数据测试，测试数据为weka平台自带的数据supermarket.arff。首先我先用Apriori算法进行测试，supermarket.arff(1979KB大小的数据)，从点击Start开始，到运行处结果，大概用了8s。测试结果如下图：FP——tree算法的思考与实现6接着我利用FPGrowth算法进行了测试，耗时不到1s。测试结果如下：我分别选取两个算法生成的频繁项集的最强关联规则的项集如下：Apriori算法：1.biscuits=tfrozenfoods=tfruit=ttotal=high788==breadandcake=t723conf:(0.92)FPGrowth算法：1.[fruit=t,frozenfoods=t,biscuits=t,total=high]:788==[breadandcake=t]:723conf:(0.92)lift:(1.27)lev:(0.03)conv:(3.35)两者对比可见结果是一致的，这保证了FP-tree算法是正确的。同时由测试时时间不同Apriori算法耗时约8s,FPGrowth算法大概1s，便可清晰的看出FP-tree算法对于Apriori算法的优势。同时，由于我学过《算法导论》，根据里面的知识，通过课本上的伪代码可以计算出Apriori算法的时间复杂度为O（n^3）,而FP-tree算法的时间复杂度为O(n)，显而易见两者不在一个数量级上。由于我只会怎么计算时间复杂度，不懂怎么计算空间复杂度，所以不能给出怎么空间复杂度的比较。5.心得体会这次课程报告，我前前后后写了差不多1周，因为自己对算法这部分内容很感兴趣，自己课下学习了《算法导论》，所以看这些思想和代码，感觉收获也是很大，对于关联分析的算法和用途，有了较为深刻和全面的了解。同时也引起了我对数据挖掘课程继续深入学习的兴趣。参考资料：《数据挖掘概念与技术》JiaweiHan、MichelineKanber。《算法导论》ThomasH.Cormen、CharlesE.Leiserson、RonaldL.Rivest、CliffordStein。