基于哈希和合并技術(shù)的FP—Growth新算法

何晴　陸黎明

摘 要： 對頻繁模式增長（FP-Growth）算法進行了改進，用哈希頭表代替頭表.通過合并頻繁模式樹（FP-Tree）中支持數(shù)相同的結(jié)點，壓縮了樹的規(guī)模，有效地節(jié)省了空間.實驗結(jié)果表明，改進后的算法在查找效率上有了大幅度的提高，可以更好地適用于大規(guī)模數(shù)據(jù)集的關(guān)聯(lián)規(guī)則挖掘.

關(guān)鍵詞： 頻繁模式增長（FP-Growth）； 關(guān)聯(lián)規(guī)則； 頻繁項集； 哈希頭表； 合并結(jié)點

中圖分類號： 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算法在每次生成新的頻繁項集時，都要遍歷一次事務(wù)數(shù)據(jù)集，其執(zhí)行的I/O操作過于頻繁，導(dǎo)致算法效率不高，頻繁模式增長（FP-Growth）算法[2]對此作了改進.FP-Growth算法僅對事務(wù)數(shù)據(jù)集掃描2次：第一次掃描建立頻繁1階項集，第二次掃描建立頻繁模式樹（FP-Tree），通過構(gòu)建條件模式基遞歸地生成頻繁項集，在頻繁項集的基礎(chǔ)上生成關(guān)聯(lián)規(guī)則.

張步忠等[3]概括了Apriori、Ecalt[4]、字典樹挖掘等關(guān)聯(lián)規(guī)則挖掘算法及FUP[5]、IUA[6]、CAT樹[7]、CAN樹[8]等增量關(guān)聯(lián)規(guī)則挖掘算法，并對該領(lǐng)域目前的研究現(xiàn)狀進行了分析，對以上所列算法的優(yōu)缺點進行了比較，為增量關(guān)聯(lián)規(guī)則挖掘相關(guān)領(lǐng)域的研究提供了參考.Rashid等[9]通過改進CAN樹挖掘無線傳感網(wǎng)絡(luò)的關(guān)聯(lián)模式，記錄事務(wù)數(shù)據(jù)集中所有頻繁項集的支持度.Jamsheela等[10]通過使用頭樹代替FP-Growth算法中的頭表提高查找效率.

本文作者在FP-Growth算法的基礎(chǔ)上通過將哈希頭表代替頭表來提高查找效率，并且合并相同支持數(shù)的結(jié)點來減少建樹所需的內(nèi)存，縮短了程序執(zhí)行時間.

1 改進的FP-Growth算法

1.1 哈希頭表

FP-Growth算法2次掃描事務(wù)數(shù)據(jù)集，都需要在列表中查找事務(wù)中的當前項.在第一次掃描事務(wù)數(shù)據(jù)集時，建立候選1階項集C1，掃描到當前項時，需要在C1中查找是否存在當前項，如果存在，其計數(shù)增加1；否則，添加該當前項，設(shè)置其計數(shù)為1.在第二次掃描事務(wù)數(shù)據(jù)集時，需要在頭表中查找該當前項是否是頻繁項，如果不是，將其刪除；如果是，將其保留，然后將該事務(wù)數(shù)據(jù)集按照頭表中的順序進行排序.

哈希查找的性能優(yōu)于順序查找.假設(shè)包含有n個項里的項集中查找某一個項，順序查找的時間復(fù)雜度是O（n），而哈希查找的時間復(fù)雜度是O（1）.在Python軟件上進行實驗，通過使用內(nèi)置對象Dictionary，實現(xiàn)哈希查找.當將頭表替換為Dictionary時，事務(wù)中的項依據(jù)哈希函數(shù)排列存儲，當調(diào)用Dictionary的get（）方法時，執(zhí)行哈希查找，找到項的存儲地址，并獲取到項的值.

1.2 合并FP-Tree相同支持數(shù)的結(jié)點

對構(gòu)建FP-Tree進行合并，原則如下：

1） 有多于一個孩子的樹結(jié)點不能再往上進行合并；

2） 合并的結(jié)點具有相同的支持數(shù)；

3） 合并后的結(jié)點名字是合并的所有結(jié)點的一個組合.

1.3 算法實現(xiàn)

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

2 實驗結(jié)果及分析

對T10I4D100K.dat和T10I4D100K.dat[11]兩個IBM模擬數(shù)據(jù)集進行實驗，實驗結(jié)果如表1～4所示，其中最小支持度均為5%，HFP表示改進后的FP-Growth算法，F(xiàn)P表示原FP-Growth算法.表1、2是在T10I4D100K.dat上，分別取100 000條和50 000條記錄的實驗結(jié)果，項的種類數(shù)分別是870和869.在HFP與FP上進行5次實驗，并對執(zhí)行時間進行比較.表3、4是在kosarak.dat上，分別取100 000條和50 000條記錄的實驗結(jié)果，項的種類數(shù)分別是23 496和18 936.

由表1可見，HFP與FP平均耗時分別為0.58863與14.14969，F(xiàn)P的執(zhí)行時間大約是HFP的24倍.由表2可知，HFP與FP平均耗時分別為0.27471與7.05064，F(xiàn)P的執(zhí)行時間大約是HFP的25倍.由表3可知，HFP與FP平均耗時分別為0.72488與93.81055，F(xiàn)P的執(zhí)行時間大約是HFP的129倍.由表4可知，HFP與FP平均耗時分別為0.3978與43.42339，F(xiàn)P的執(zhí)行時間大約是HFP的109倍.綜上所述，事務(wù)數(shù)據(jù)集中項的種類數(shù)越多，HFP執(zhí)行效率越高.

3 總 結(jié)

用改進的哈希頭表替換FP-Growth算法的頭表，通過合并最小支持度相同的結(jié)點壓縮FP-Tree，從而減少建樹所占用的內(nèi)存.通過理論分析和實驗結(jié)果可知，改進算法能提高原算法的執(zhí)行效率.

參考文獻：

[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] 張步忠，江克勤，張玉州.增量關(guān)聯(lián)規(guī)則挖掘研究綜述 [J].小型微型計算機系統(tǒng)，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] 李彤陽，王紅梅，牟曉偉.一種基于垂直數(shù)據(jù)格式頻繁項集挖掘改進算法 [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].計算機技術(shù)與發(fā)展，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] 朱群雄，趙春，馮磊，等.關(guān)聯(lián)規(guī)則的動態(tài)維護及其在財務(wù)數(shù)據(jù)中的應(yīng)用 [J].清華大學(xué)學(xué)報（自然科學(xué)版），2012（5）：694-698.

Zhu Q X，Zhao C，F(xiàn)eng 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/.

（責(zé)任編輯：包震宇）