基于回溯的最大頻繁項(xiàng)集挖掘算法

張心靜，于嘉威，王紅梅

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長春 130012)

?

基于回溯的最大頻繁項(xiàng)集挖掘算法

張心靜，于嘉威，王紅梅

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，吉林 長春 130012)

針對Apriori類算法多次掃描數(shù)據(jù)庫和FP-tree類算法需要構(gòu)建大量條件模式樹的問題，文中提出了挖掘最大頻繁項(xiàng)集的GBMFI算法。采用垂直格式存儲事務(wù)數(shù)據(jù)庫，以枚舉樹為基礎(chǔ)，利用子集非頻繁性質(zhì)和父子節(jié)點(diǎn)支持度信息在搜索過程中對枚舉樹進(jìn)行剪枝，最終得到最大頻繁項(xiàng)集。通過實(shí)驗(yàn)對比，結(jié)果證明了算法的有效性，尤其適用于稀疏數(shù)據(jù)集。

數(shù)據(jù)挖掘；最大頻繁項(xiàng)集；關(guān)聯(lián)規(guī)則；回溯法；剪枝

隨著大數(shù)據(jù)時(shí)代的發(fā)展，數(shù)據(jù)挖掘技術(shù)在這個(gè)領(lǐng)域發(fā)揮的作用變得不可小覷[1]。發(fā)現(xiàn)關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘工作的重點(diǎn)。而挖掘頻繁項(xiàng)集又是尋找關(guān)聯(lián)規(guī)則的重要步驟之一。但在通常情況下得到的頻繁項(xiàng)集數(shù)量龐大，且彼此之間存在項(xiàng)重復(fù)的現(xiàn)象，這就導(dǎo)致了信息冗余的問題。由于最大頻繁項(xiàng)集隱含了所有頻繁項(xiàng)集的信息，大幅縮減了頻繁項(xiàng)集的數(shù)量，因此挖掘最大頻繁項(xiàng)集的任務(wù)應(yīng)運(yùn)而生。挖掘最大頻繁項(xiàng)集的算法通?；贏priori[2]和FP-tree[3]思想。一方面，基于Apriori改進(jìn)的算法自底向上逐漸產(chǎn)生所有頻繁項(xiàng)集，但在這一過程中也會因連接操作生成大量的候選項(xiàng)集，同時(shí)為了削減候選項(xiàng)集，導(dǎo)致算法多次掃描整個(gè)事務(wù)數(shù)據(jù)庫，耗費(fèi)了時(shí)間與資源。尤其是針對大數(shù)據(jù)進(jìn)行處理時(shí)，產(chǎn)生的項(xiàng)集規(guī)模過大使得計(jì)算機(jī)難以對其進(jìn)行存儲與計(jì)算，高效得到價(jià)值密度高的數(shù)據(jù)更加困難。另一方面，研究者們基于FP-tree提出一些挖掘最大頻繁項(xiàng)集的算法，如MaxSP[4]，DMFIF[5]，MMFI[6]，IMMFIA[7]，F(xiàn)P-MFIA[8]等算法。然而多數(shù)基于FP-tree的算法，利用遞歸調(diào)用不斷產(chǎn)生條件模式樹的方法得到最大頻繁項(xiàng)集，因此需要構(gòu)建大量的條件模式樹，消耗了巨大的時(shí)空資源。此外，研究發(fā)現(xiàn)，學(xué)者大多是對最小支持度與算法運(yùn)行時(shí)間的關(guān)系進(jìn)行實(shí)驗(yàn)，對結(jié)果的數(shù)量及其分布情況缺少較為詳盡的記錄。

基于上述理論研究，本文提出了GBMFI算法。通過在標(biāo)準(zhǔn)數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)，分別記錄了算法的運(yùn)行時(shí)間，最大頻繁項(xiàng)集的個(gè)數(shù)以及不同長度下最大頻繁項(xiàng)集的分布情況，尤其是對最小支持度和最大頻繁項(xiàng)集個(gè)數(shù)的關(guān)系進(jìn)行了研究。另外，GBMFI與DepthProject進(jìn)行了實(shí)驗(yàn)對比。DepthProject作為挖掘最大頻繁項(xiàng)集的經(jīng)典算法，采用深度優(yōu)先搜索策略，雖然使用了壓縮效率較高的水平二進(jìn)制表示事務(wù)數(shù)據(jù)庫，但本文采用的垂直位圖表示形式可更快速的計(jì)算支持度。結(jié)果證明了GBMFI的有效性，尤其適用于稀疏數(shù)據(jù)集。

1　理論基礎(chǔ)

定義1 設(shè)I={I1,I2,I2,…,Im}是所有項(xiàng)的集合，其中Ii(1≤i≤m)稱為項(xiàng)。若集合X?I，則稱X為項(xiàng)集。設(shè)TDB={T1,T2,T3,…,Tn}是所有事務(wù)的集合，稱為事務(wù)數(shù)據(jù)庫。其中，Ti(1≤i≤n)稱為事務(wù)，且每個(gè)事務(wù)Ti是項(xiàng)的集合，滿足Ti?I。對應(yīng)每一個(gè)事務(wù)都有唯一標(biāo)識符事務(wù)號，記作TID。通常項(xiàng)在事務(wù)中有序;

定義2 項(xiàng)集長度k是指項(xiàng)集中包含的項(xiàng)的個(gè)數(shù)。長度為k的項(xiàng)集稱為k項(xiàng)集;

定義3 已知項(xiàng)集X?I，將X在TDB中出現(xiàn)的次數(shù)作為項(xiàng)集X的支持度，記作Sup(X)，即包含X的事務(wù)數(shù);

定義4 設(shè)最小支持度閾值為min_sup。Sup(X)≥min_sup, 則稱X是頻繁項(xiàng)集。若項(xiàng)集X在數(shù)據(jù)庫中是頻繁的，對任意滿足X?y的項(xiàng)集Y而言，Y是X的超集且是不頻繁的，則X為最大頻繁項(xiàng)集。假設(shè)數(shù)據(jù)庫中的事務(wù)數(shù)為M，則min_sup也可用百分比表示，則最小支持度閾值可用最小支持度百分比乘以事務(wù)數(shù)M求得;

定義5[9]將數(shù)據(jù)庫中出現(xiàn)的所有項(xiàng)按詞典序排列，邏輯上組織成枚舉樹的形式。第0層是根，為空。第k層包含了所有的k項(xiàng)集。樹中每個(gè)節(jié)點(diǎn)由兩部分組成，分別是節(jié)點(diǎn)的頭部Head和節(jié)點(diǎn)的尾部Tail。Head其實(shí)就是節(jié)點(diǎn)本身所代表的項(xiàng)集。Tail為節(jié)點(diǎn)可擴(kuò)展的項(xiàng)的集合。注意，Tail包含了所有按照字典序大于Head的項(xiàng)元素。如圖1所示，假設(shè)所有項(xiàng)的集合為{a,b,c}，圖中“()”內(nèi)表示Head，“{}”內(nèi)表示Tail。

圖1　枚舉樹

性質(zhì)1 (子集非頻繁剪枝[10])若X是非頻繁項(xiàng)集，則任何X的超集Y均是非頻繁項(xiàng)集。在深度搜索過程中，利用此性質(zhì)可對枚舉樹進(jìn)行剪枝;

性質(zhì)2 (父等價(jià)剪枝[11])設(shè)當(dāng)前節(jié)點(diǎn)為X，i∈Tail(C)。若Sup(C∪{i})=Sup(C)且Sup(C∪{i})≥min_sup，可直接從節(jié)點(diǎn)指向C∪{i}遍歷。

證明：反證法。假設(shè)存在Z=C∪{j}(j∈TailC),j≠i，Z?M但iM且m頻繁。由于Sup(C∪{i})=Sup(C)，且Sup(C∪{i})≥min_sup，存在C的頻繁項(xiàng)集中一定存在i。這與iM矛盾。因此包含C而不包含i的項(xiàng)集中不會出現(xiàn)最大頻繁項(xiàng)集。證畢。

2　GBMFI算法

準(zhǔn)備工作：掃描事務(wù)數(shù)據(jù)庫TDB，將水平表示[13]的數(shù)據(jù)庫(如表1所示)轉(zhuǎn)換為垂直表示[12]形式(如表2所示)。若項(xiàng)x在事務(wù)y中存在，則在相應(yīng)位置標(biāo)1，否則標(biāo)0。通過計(jì)數(shù)得到各1項(xiàng)集的支持度，再利用min_sup約束得到頻繁1項(xiàng)集F1，并將F1按支持度升序排列。

表1　水平表示的事務(wù)數(shù)據(jù)庫

表2　垂直表示的事務(wù)數(shù)據(jù)庫

初始條件：節(jié)點(diǎn)R為根節(jié)點(diǎn)。Head(R)=?。Tail(R)=F1。結(jié)果集MFI=?。令當(dāng)前節(jié)點(diǎn)C=R∪{i}(i為Tail(R)中第一個(gè)項(xiàng))，即選擇節(jié)點(diǎn)R的第一個(gè)孩子節(jié)點(diǎn)作為起始節(jié)點(diǎn)。

算法過程：GBMFI(C,MFI)

(1)計(jì)算當(dāng)前節(jié)點(diǎn)C的頭尾并集Un=Head(C)∪Tail(C)；

(2)檢測Un是否已被MFI包含。若是，則終止擴(kuò)展，并將當(dāng)前節(jié)點(diǎn)指向C的第一個(gè)右兄弟RB，然后執(zhí)行GBMFI(RB,MFI)。否則，執(zhí)行(3)；

(3)依次計(jì)算C∪{i}(i∈Tail(C))的支持度。若Sup(C∪{i})≥min_sup且Sup(C∪{i})=Sup(C)，則執(zhí)行步驟(4)。若Sup(C∪{i})

(4)將當(dāng)前節(jié)點(diǎn)指向Cn=C∪{i}(i為ReducedTail(C)中第一個(gè)項(xiàng))。更新當(dāng)前節(jié)點(diǎn)Cn的Tail，繼續(xù)執(zhí)行GBMFI(Cn,MFI);

(5)若該節(jié)點(diǎn)是葉子節(jié)點(diǎn)(Tail(C)=?)，且通過檢測發(fā)現(xiàn)MFI中不存在其超集，則將其加入到結(jié)果集MFI中。否則回溯到根節(jié)點(diǎn)R，在Tail(R)中選擇未被擴(kuò)展的第一個(gè)孩子作為當(dāng)前節(jié)點(diǎn)FC，執(zhí)行GBMFI(FC,MFI)；

(6)直到Tail(R)均被處理完，算法結(jié)束。

3　實(shí)驗(yàn)與結(jié)論

實(shí)驗(yàn)環(huán)境為Windows7 64位s操作系統(tǒng)。Intel(R)Core(TM)i5-3230M CPU@2.60 GHz。內(nèi)存6.00 GB，使用C++語言進(jìn)行編程。為測試該算法的有效性，本文選取了數(shù)據(jù)挖掘?qū)嶒?yàn)中2個(gè)典型的標(biāo)準(zhǔn)數(shù)據(jù)集，如表3所示。分別記錄了不同數(shù)據(jù)集下的算法運(yùn)行時(shí)間，并與DepthProject的運(yùn)行時(shí)間做了對比。同時(shí)還記錄了最大頻繁項(xiàng)集結(jié)果數(shù)以及不同長度的最大頻繁項(xiàng)集的分布情況。

表3　測試數(shù)據(jù)集特征

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

T10I4D100K是由1 000個(gè)項(xiàng)組成，較為稀疏，頻繁項(xiàng)集長度較短。表4記錄了不同min_sup下最大頻繁項(xiàng)集的結(jié)果數(shù)以及GBMFI和DepthProject的執(zhí)行時(shí)間。min_sup用百分比的形式，單位是%，結(jié)果的單位是個(gè)，時(shí)間單位s，T(G)代表GBMFI的執(zhí)行時(shí)間，T(D)代表DepthProject的執(zhí)行時(shí)間。圖2給出了最大頻繁項(xiàng)集的詳細(xì)分布圖，橫坐標(biāo)為項(xiàng)集長度，縱坐標(biāo)為個(gè)數(shù)。根據(jù)表4可知，隨著min_sup的增大，挖掘出的最大頻繁項(xiàng)集數(shù)量也越來越少，則運(yùn)行時(shí)間越來越小。同時(shí)可看出，GBMFI的運(yùn)行速度高于DepthProject。當(dāng)最小支持度較大，例如min_sup為0.05%時(shí)，兩者運(yùn)行時(shí)間相差很小。GBMFI的運(yùn)行時(shí)間為27.9 s，而DepthProject的運(yùn)行時(shí)間為34.1 s。隨著最小支持度減小，兩者的運(yùn)行時(shí)間相差逐漸變大。例如當(dāng)min_sup為0.01%時(shí)，GBMFI的運(yùn)行時(shí)間為44.2 s，而Depth Project的運(yùn)行時(shí)間為56.5 s。圖2顯示出min_sup為0.02%時(shí)，最大頻繁項(xiàng)集的分布詳情。由圖可知，最大頻繁項(xiàng)集的結(jié)果主要集中長度為2和長度為3的地方，最長的最大頻繁項(xiàng)集長度為10。在長度為10的情況下，結(jié)果數(shù)為個(gè)位數(shù)，得到的最大頻繁項(xiàng)集較少。因此，在這一數(shù)據(jù)集中得到的最大頻繁項(xiàng)集較短。

表4　T10I4D100K下的min_sup與結(jié)果數(shù)、算法時(shí)間的關(guān)系

圖2　min_sup為0.02%時(shí)，T10I4D100K下的結(jié)果分布圖

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

Chess是從國際象棋比賽中獲取的數(shù)據(jù)，屬于稠密型數(shù)據(jù)集。從表5可知，隨著min_sup增大，最大頻繁項(xiàng)集的結(jié)果數(shù)也越來越少，而運(yùn)行時(shí)間越來越小，且GBMFI的運(yùn)行速度優(yōu)與DepthProject，例如當(dāng)min_sup為14%時(shí)，GBMFI的運(yùn)行時(shí)間為45.2 s，而DepthProject的運(yùn)行時(shí)間為58.7 s。但對比T10I4D100K可知，相對與Chess本身的大小而言，從Chess中得到結(jié)果的數(shù)量非常多。這是由于Chess中事務(wù)之間較為相似，數(shù)據(jù)的密集性導(dǎo)致了頻繁項(xiàng)集的數(shù)量巨大以及復(fù)雜的計(jì)算性。這也使得Chess被作為具有權(quán)威性的頻繁項(xiàng)集挖掘算法的測試數(shù)據(jù)集。圖3顯示出最大頻繁項(xiàng)集的長度多集中為10、11、12，且結(jié)果長度可達(dá)25。

表5　Chess下的min_sup與結(jié)果數(shù)、算法時(shí)間的關(guān)系

圖3　min_sup為5%時(shí)，Chess下的結(jié)果分布圖

綜合以上對數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可知，隨著min_sup增加，GBMFI運(yùn)行時(shí)間越來越小，得到的最大頻繁項(xiàng)集也越來越少。對比DepthProject可知，GBMFI時(shí)間性能較好。而對稀疏數(shù)據(jù)集而言，結(jié)果多集中在長度較短的地方，得到的最大頻繁項(xiàng)集數(shù)量相對較少，因此運(yùn)行時(shí)間更少。相反，從稠密數(shù)據(jù)集中得到的結(jié)果相對較長。若數(shù)據(jù)集中的事務(wù)較短，那么得到的結(jié)果也較短。否則，得到的最大頻繁項(xiàng)集也較長。另外，由于數(shù)據(jù)集之間存在差異性，因此針對不同的數(shù)據(jù)集文中要選取適合該數(shù)據(jù)集的最小支持度做測試，而不能使用相同的最小支持度閾值。

4　結(jié)束語

挖掘最大頻繁項(xiàng)集可作為壓縮頻繁項(xiàng)集的一種方法，也可是大數(shù)據(jù)環(huán)境下節(jié)省存儲空間的一種手段。針對數(shù)據(jù)挖掘中最大頻繁項(xiàng)集的挖掘問題，本文提出了一種基于回溯法的最大頻繁項(xiàng)集挖掘算法GBMFI，并在兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上對其進(jìn)行測試，對最小支持度與最大頻繁集的個(gè)數(shù)關(guān)系進(jìn)行了研究。分別記錄了算法的運(yùn)行時(shí)間，最大頻繁項(xiàng)集的個(gè)數(shù)以及不同長度下最大頻繁項(xiàng)集的分布情況。與DepthProject進(jìn)行了對比實(shí)驗(yàn)，結(jié)果表明該算法運(yùn)行速度良好，尤其適用于稀疏數(shù)據(jù)集。下一步工作計(jì)劃是針對大數(shù)據(jù)環(huán)境下的分布式存儲機(jī)制，研究分布式并行的最大頻繁項(xiàng)集挖掘算法。

[1]Wu X,Zhu X, Wu G Q,et al. Data mining with big data[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(1):97-107.

[2]Agrawal R,Srikant R.Fast algorithms for mining association rules[C].Santiago: Proceedings of the 20th International Conference on Very Large Data Bases,2000.

[3]Han J, Pei J,Yin Y.Mining frequent patterns without candidate generation[C].Dallas:Proceeding of SIGMOD Conference,2000.

[4]Fournier-Viger P,Wu C W,Tseng V S.Mining maximal sequential patterns without candidate maintenance[M].Heidelberg: Advanced Data Mining and Applications Springer Berlin Heidelberg, 2013.

[5]蔣翠清,胡俊妍.基于FP-tree的最大頻繁項(xiàng)集挖掘算法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2010,33(9):1387-1391.

[6]Huiling P,Yunxing S.A new FP-tree-based algorithm MMFI for mining the maximal frequent itemset[C].Ottawa: Computer Science and Automation Engineering (CSAE),2012.

[7]馬麗生,姚光順,楊傳健.基于改進(jìn)FP-tree的最大頻繁項(xiàng)目集挖掘算法[J].計(jì)算機(jī)應(yīng)用,2012,32(2):326-329.

[2]楊鵬坤,彭慧,周曉峰,等.改進(jìn)的基于頻繁模式樹的最大頻繁項(xiàng)集挖掘算法—FP-MFIA[J].計(jì)算機(jī)應(yīng)用,2015,35(3):775-778.

[3]馬志新,陳曉云,王雪,等.最大頻繁項(xiàng)集挖掘中搜索空間的剪枝策略[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2005,45(S1):1748-1752.

[4]Agrawal R, Imielinski T, Swami A N. Mining association rules between sets of items in large databases[C].Washington,D.C:Proceeding of SIGMOD Conference,1993.

[5]Burdick D,Calimlim M,Gehrke J.MAFIA:A maximal frequent item set algorithm for transactional database[C].Heidelberg: Proceedings of the 17th Conference on Data Engineering,2001.

[6]Zaki M J. Scalable algorithms for association mining[J].IEEE Transactions on Knowledge and Data Engineering,2000,12(3):372-390.

[7]Jiawei Han, Micheling Kamber, Jian Pei .數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2012.

[8]Agarwal R C,Aggarwal C C,Prasad V V V. Depth first generation of long patterns[C].Boston:Proceeding of Sixth ACM SIGKDD International Conference, Knowledge Discovery and Data Ming,2000.

Mining Maximal Frequent Itemsets Based on Back Track

ZHANG Xinjing, YU Jiawei, WANG Hongmei

(School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China)

In view of the fact that Apriori algorithms scans the database multiple times and the FP-tree algorithms requires build a large number of conditional trees, the GBMFI algorithm is proposed for mining maximal frequent itemsets. The transaction database is stored in vertical format. Based on the enumeration tree, the GBMFI algorithm performs the pruning operation to narrow the search space with the properties of non-frequent subsets and the support information of the node to get maximal frequent item sets. Experiments demonstrate the effectiveness of the GBMFI, especially for spares data sets.

data mining; maximal frequent item set; association rule; back track method; pruning

10.16180/j.cnki.issn1007-7820.2016.08.023

2015-11-24

國家自然科學(xué)基金資助項(xiàng)目(61133011)；吉林省教育廳“十二五”科學(xué)技術(shù)研究基金資助項(xiàng)目(2013431)

張心靜(1990-)，女，碩士研究生。究方向：數(shù)據(jù)挖掘。于嘉威(1993-)，男，本科。研究方向：ACM程序設(shè)計(jì)競賽。王紅梅(1968-)，女，教授，碩士生導(dǎo)師。研究方向：數(shù)據(jù)挖掘等。

TP311

A

1007-7820(2016)08-078-04