何晴　陸黎明

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

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

中圖分類號： TP 311 文獻(xiàn)標(biāo)志碼： 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算法在每次生成新的頻繁項(xiàng)集時(shí)，都要遍歷一次事務(wù)數(shù)據(jù)集，其執(zhí)行的I/O操作過于頻繁，導(dǎo)致算法效率不高，頻繁模式增長（FP-Growth）算法[2]對此作了改進(jìn).FP-Growth算法僅對事務(wù)數(shù)據(jù)集掃描2次：第一次掃描建立頻繁1階項(xiàng)集，第二次掃描建立頻繁模式樹（FP-Tree），通過構(gòu)建條件模式基遞歸地生成頻繁項(xiàng)集，在頻繁項(xiàng)集的基礎(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)狀進(jìn)行了分析，對以上所列算法的優(yōu)缺點(diǎn)進(jìn)行了比較，為增量關(guān)聯(lián)規(guī)則挖掘相關(guān)領(lǐng)域的研究提供了參考.Rashid等[9]通過改進(jìn)CAN樹挖掘無線傳感網(wǎng)絡(luò)的關(guān)聯(lián)模式，記錄事務(wù)數(shù)據(jù)集中所有頻繁項(xiàng)集的支持度.Jamsheela等[10]通過使用頭樹代替FP-Growth算法中的頭表提高查找效率.

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

1 改進(jìn)的FP-Growth算法

1.1 哈希頭表

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

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

1.2 合并FP-Tree相同支持?jǐn)?shù)的結(jié)點(diǎn)

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

1） 有多于一個(gè)孩子的樹結(jié)點(diǎn)不能再往上進(jìn)行合并；

2） 合并的結(jié)點(diǎn)具有相同的支持?jǐn)?shù)；

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

1.3 算法實(shí)現(xiàn)

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

2 實(shí)驗(yàn)結(jié)果及分析

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

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

3 總 結(jié)

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

參考文獻(xiàn)：

[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].小型微型計(jì)算機(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ù)格式頻繁項(xiàng)集挖掘改進(jìn)算法 [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].計(jì)算機(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ī)則的動(dòng)態(tài)維護(hù)及其在財(cái)務(wù)數(shù)據(jù)中的應(yīng)用 [J].清華大學(xué)學(xué)報(bào)（自然科學(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é)任編輯：包震宇）