计算机应用论文　摘要：频繁模式树的提出，提高了挖掘效率，是关联规则挖掘史上的一个历程碑。频繁模式增长算法在创建频繁模式树时，重复比较新结点与已经插入结点，以便确定新插入点的位置，造成了性能上的浪费。针对此问题，本文提出一种解决方法，即在创建FP-tree之前，将每一事务转换成相应的实数，以便在通过项头表寻找结点链时可以快速定位。然后再对这些由实数组成的对应数据库进行排序，得到一个新的数据库。在新的数据库基础上快速生成频繁模式树，这样就避免了大量的重复的工作，提高了创建FP-tree的效率。理论分析表明，修改后的算法的性能明显优于原算法。
　　关键词：数据挖掘；频繁项集挖掘；频繁模式增长算法；有序频繁模式增长算法；
　　中图分类号：TP311.1
　　1引言
　　频繁模式的挖掘[1]在关联规则[2]、相关分析、序列模式、因果律、显露模式等许多重要数据挖掘任务中承担着重要的角色。长期以来，挖掘频繁模式主要采用Apriori[3,4]算法及其改进形式。然而Apriori及其改进算法仍然会产生大量候选项集，并需要反复频繁的扫描数据库，这严重影响了算法的效率。J.Han等人提出了新的结构FP-tree和相应的模式增长算法FP-growth[5]，该算法采用分治的策略，无须产生候选项集，FP-growth算法是一种本质上不同于Apriori的挖掘频繁项集的有效算法。但它的大部分时间都花费在FP-tree及条件FP-tree的构造与遍历上，如果能提高这方面的效率将对提高算法的效率有较大的帮助。基于这样的分析，我们提出了对FP-growth算法的改进措施。在原数据库D的基础上建立新的数据库D*。以便创建有序FP-tree，使得树中的每一个结点的子结点按照项的序号从小到大排列。这样，加入新结点时需要比较的结点数大大降低了，从而缩短构造一棵树的时间。此外，还采取了其它的优化措施，如将item-no按照item-name的次序排成一个列表，在将item-name转换为item-no时，通过列表可直接找到对应的项。
　　2问题描述
　　2．1频繁项集[6]
　　设I={i1,i2,…,in}是n个不同项目（Item）的集合，如果对一个集合，且k=|X|,则X称为K项集，或者简单地称为一个项集（Itemset）。记D为事务T的集合，。对于给定事务数据库D，定义X的支持度为D中包含X的事务个数，记为sup(X)。用户可自定义一个小于|D|的最小支持度记为s.
　　定义1频繁项集：给定事务数据库D和支持度s，对于项集，若sup(X)≥s,则称X为D中的频繁项集。 论文网

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。