基于哈希和合并技术的FP—Growth新算法

何晴　陆黎明

摘 要： 对频繁模式增长（FP-Growth）算法进行了改进，用哈希头表代替头表.通过合并频繁模式树（FP-Tree）中支持数相同的结点，压缩了树的规模，有效地节省了空间.实验结果表明，改进后的算法在查找效率上有了大幅度的提高，可以更好地适用于大规模数据集的关联规则挖掘.

关键词： 频繁模式增长（FP-Growth）； 关联规则； 频繁项集； 哈希头表； 合并结点

中图分类号： TP 311 文献标志码： A 文章编号： 1000-5137（2018）04-0469-05

Abstract： In this paper，we improve frequent pattern growth（FP-Growth） algorithm，we replace the header table with Hash-header table.By merging the same frequency nodes in frequent pattern tree（FP-Tree），we compress the scale of the tree.The experimental results show that the proposed algorithm has improved the efficiency of query，and it can be applied in mining large data sets with association rules.

Key words： frequent pattern growth（FP-Growth）； association rules； frequent item sets； Hash-header table； merging nodes

0 引 言

Agrawal等[1]于1993年提出Apriori算法在每次生成新的頻繁项集时，都要遍历一次事务数据集，其执行的I/O操作过于频繁，导致算法效率不高，频繁模式增长（FP-Growth）算法[2]对此作了改进.FP-Growth算法仅对事务数据集扫描2次：第一次扫描建立频繁1阶项集，第二次扫描建立频繁模式树（FP-Tree），通过构建条件模式基递归地生成频繁项集，在频繁项集的基础上生成关联规则.

张步忠等[3]概括了Apriori、Ecalt[4]、字典树挖掘等关联规则挖掘算法及FUP[5]、IUA[6]、CAT树[7]、CAN树[8]等增量关联规则挖掘算法，并对该领域目前的研究现状进行了分析，对以上所列算法的优缺点进行了比较，为增量关联规则挖掘相关领域的研究提供了参考.Rashid等[9]通过改进CAN树挖掘无线传感网络的关联模式，记录事务数据集中所有频繁项集的支持度.Jamsheela等[10]通过使用头树代替FP-Growth算法中的头表提高查找效率.

本文作者在FP-Growth算法的基础上通过将哈希头表代替头表来提高查找效率，并且合并相同支持数的结点来减少建树所需的内存，缩短了程序执行时间.

1 改进的FP-Growth算法

1.1 哈希头表

FP-Growth算法2次扫描事务数据集，都需要在列表中查找事务中的当前项.在第一次扫描事务数据集时，建立候选1阶项集C1，扫描到当前项时，需要在C1中查找是否存在当前项，如果存在，其计数增加1；否则，添加该当前项，设置其计数为1.在第二次扫描事务数据集时，需要在头表中查找该当前项是否是频繁项，如果不是，将其删除；如果是，将其保留，然后将该事务数据集按照头表中的顺序进行排序.

哈希查找的性能优于顺序查找.假设包含有n个项里的项集中查找某一个项，顺序查找的时间复杂度是O（n），而哈希查找的时间复杂度是O（1）.在Python软件上进行实验，通过使用内置对象Dictionary，实现哈希查找.当将头表替换为Dictionary时，事务中的项依据哈希函数排列存储，当调用Dictionary的get（）方法时，执行哈希查找，找到项的存储地址，并获取到项的值.

1.2 合并FP-Tree相同支持数的结点

对构建FP-Tree进行合并，原则如下：

1） 有多于一个孩子的树结点不能再往上进行合并；

2） 合并的结点具有相同的支持数；

3） 合并后的结点名字是合并的所有结点的一个组合.

1.3 算法实现

部分算法思想如图1～4所示.

2 实验结果及分析

对T10I4D100K.dat和T10I4D100K.dat[11]两个IBM模拟数据集进行实验，实验结果如表1～4所示，其中最小支持度均为5%，HFP表示改进后的FP-Growth算法，FP表示原FP-Growth算法.表1、2是在T10I4D100K.dat上，分别取100 000条和50 000条记录的实验结果，项的种类数分别是870和869.在HFP与FP上进行5次实验，并对执行时间进行比较.表3、4是在kosarak.dat上，分别取100 000条和50 000条记录的实验结果，项的种类数分别是23 496和18 936.

由表1可见，HFP与FP平均耗时分别为0.58863与14.14969，FP的执行时间大约是HFP的24倍.由表2可知，HFP与FP平均耗时分别为0.27471与7.05064，FP的执行时间大约是HFP的25倍.由表3可知，HFP与FP平均耗时分别为0.72488与93.81055，FP的执行时间大约是HFP的129倍.由表4可知，HFP与FP平均耗时分别为0.3978与43.42339，FP的执行时间大约是HFP的109倍.综上所述，事务数据集中项的种类数越多，HFP执行效率越高.

3 总 结

用改进的哈希头表替换FP-Growth算法的头表，通过合并最小支持度相同的结点压缩FP-Tree，从而减少建树所占用的内存.通过理论分析和实验结果可知，改进算法能提高原算法的执行效率.

参考文献：

[1] Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases [C].Proceedings of the 1993 ACM SIGMOD international conference on Management of data.New York：ACM，1993.

[2] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation [J].Acm Sigmod Record，2000，29（2）：1-12.

[3] 张步忠，江克勤，张玉州.增量关联规则挖掘研究综述 [J].小型微型计算机系统，2016，37（1）：18-23.

Zhang B Z，Jiang K Q，Zhang Y Z.Survey on incremental association rule mining research [J].Journal of Chinese Computer Systems，2016，37（1）：18-23.

[4] 李彤阳，王红梅，牟晓伟.一种基于垂直数据格式频繁项集挖掘改进算法 [J].信息通信，2015（1）：27-28.

Li T Y，Wang H M，Mou X W.An improved algorithm for mining frequent item sets based on vertical data format [J].Information & Communications，2015（1）：27-28.

[5] 周爱武，王琰，陈宝楼.一种基于FUP的TD-FP-Tree并行快速更新算法 [J].计算机技术与发展，2013（4）：91-95.

Zhou A W，Wang Y，Chen B L.A parallel fast update TD-FP-Tree algorithm based on FUP [J].Computer Technology and Development，2013（4）：91-95.

[6] 朱群雄，趙春，冯磊，等.关联规则的动态维护及其在财务数据中的应用 [J].清华大学学报（自然科学版），2012（5）：694-698.

Zhu Q X，Zhao C，Feng L，et al.Dynamic maintenance of association rules and its application in the enterprise financial data [J].Journal of Tsinghua University （Science & Technology），2012（5）：694-698.

[7] Cheung W，Zaiane O R.Incremental mining of frequent patterns without candidate generation or support constraint [C].Database Engineering and Applications Symposium.Hong Kong：IEEE，2003：111-116.

[8] Leung C K，Khan Q I，Li Z.CanTree：A canonical-order tree for incremental frequent-pattern mining [J].Knowledge and Information Systems，2007，11（3）：287-311.

[9] Rashid M M，Gondal I，Kamruzzaman J.Mining associated patterns from wireless sensor networks [J].IEEE Transactions on Computers，2015，64（7）：1998-2011.

[10] Jamsheela O，Raju G.An adaptive method for mining frequent itemsets efficiently：An improved header tree method [C].International Conference on Advances in Computing，Communications and Informatics.Kochi：IEEE，2015.

[11] IBM.Frequent itemset mining dataset repository [EB/OL].[2016-06-18].http：//fimi.ua.ac.be/data/.

（责任编辑：包震宇）