一種快速挖掘生成器算法

許普樂　紀　允

(1.蕪湖職業(yè)技術學院　教務處，安徽　蕪湖241006；2.中國移動通信集團安徽有限公司　銅陵分公司，安徽　銅陵244000)

?

一種快速挖掘生成器算法

許普樂1紀允2

(1.蕪湖職業(yè)技術學院教務處，安徽蕪湖241006；2.中國移動通信集團安徽有限公司銅陵分公司，安徽銅陵244000)

摘要：生成器是頻繁項集精簡表示中的一個經(jīng)典模型，但其傳統(tǒng)挖掘算法存在重復生成候選項集，反復掃描數(shù)據(jù)庫得到支持度，需要遍歷所有直接子集等缺點，導致生成效率低下.基于此，一種快速挖掘生成器算法FMG，該算法采用Rymon枚舉樹作為搜索空間，提出的判斷生成器定理對候選項集進行快速判斷，以及特定的剪枝策略.通過這些方法快速的挖掘生成器.實驗結(jié)果證明，該算法不僅比傳統(tǒng)的算法要快，而且比最新提出的快速挖掘算法還要快.

關鍵詞：數(shù)據(jù)挖掘；頻繁項集；精簡表示；Rymon枚舉樹；生成器

引言

在數(shù)據(jù)挖掘領域中，頻繁項集研究一直是一個熱點問題.頻繁項集在解決分類，聚類，關聯(lián)規(guī)則等諸多理論研究問題中有著非常重要的作用[1-2].特別隨著推薦系統(tǒng)的興起，抽取關聯(lián)規(guī)則使得頻繁項集的研究進一步得到發(fā)展.但是在實際的數(shù)據(jù)庫中抽取頻繁項集的數(shù)量過多，直接導致占用大量的數(shù)據(jù)空間，同時在傳輸和使用過程中也會增加網(wǎng)絡帶寬代價和CPU代價以及IO代價[3].這些缺點在數(shù)據(jù)密集型數(shù)據(jù)集上表現(xiàn)尤為明顯并且限制了頻繁項集的使用范圍和能力.相關學者對這些海量的頻繁項集進行研究后，發(fā)現(xiàn)可以通過某些方法例如格結(jié)構中的等價類，壓縮頻繁項集的數(shù)量，使得一部分的項集的支持度是可以從保留的項集中通過推算得到.為了壓縮頻繁項集的數(shù)量，學者們提出了頻繁項集的精簡表示，并且從各個方面提出多種精簡方法和模型.目前頻繁項集精簡表示模型主要有最大頻繁項集[4-5]、頻繁閉合項集[6-8]、生成器模型[9]等.

由于在生成器精簡表示模型中恢復頻繁項集的支持度比最大頻繁項集、閉合項集更加有效率[9]，因此頻繁生成器成為頻繁項集研究中一個熱點.但是傳統(tǒng)的抽取頻繁生成器算法存在重復生成、反復遍歷直接子集、反復掃描數(shù)據(jù)庫等缺點，這些缺點導致生成器的生成效率底下.針對于挖掘效率低下情況，也有學者針對其進行研究，許普樂等人在文獻[3]中提出基于FP樹快速生成生成器算法FPASCAL.雖然在文中提出的算法比原有算法效率有所提高，但是該算法依然存在判斷一個項集是否為生成器需要遍歷所有直接子集的支持度的問題.

本文在分析生成器的相關的特點后，提出一種快速挖掘生成器嶄新算法，該算法采用深度遞歸的思想，采用特定的剪枝思想和遍歷策略，避免重復生成同一個候選項集.同時針對于一個生成器的支持度，可以根據(jù)先前生成器項集存儲的信息計算而得到.在算法的具體運行過程中，從一個生成器直接跳到另外一個生成器，對于生成器的判斷，也避免和所有直接子集的支持度進行比較.

1相關概念

1.1頻繁項集和生成器

設項集IIS={k1，k2,……,kn}為n個不同的項所組成的集合.集合R?IIS為項集，項集中含有d個元素稱該項集為d項集.在集合IIS基礎上建立的交易記錄數(shù)據(jù)庫D,數(shù)據(jù)庫D中每條記錄o均有一個唯一的標識符TID.一個數(shù)據(jù)庫D由三項O,I,R所組成,即D=(O,I,R)，其中R?O×I，(o,i)∈R表示在o這條交易記錄中，包含i這個項.

設X?IIS，項集X的支持度supp(X)為數(shù)據(jù)庫中包含X中所有項的交易記錄個數(shù)或者比例.如果項集的支持度supp(X)大于或者等于設置的最小支持度minsupp，即supp(X)≥minsupp，則稱該項集為頻繁項集.

如果項集X和自己的所有直接子集的支持度均不相等，即supp(X)≠supp(Xi)其中i∈X，則稱該項集為生成器.需要注意是，空集φ在交易數(shù)據(jù)庫中也是一個生成器.如果生成器X的支持度大于或者等于最小支持度minsup，即supp(X)≥minsupp，則稱該生成器為頻繁生成器.可以很容易地發(fā)現(xiàn)，頻繁生成器和頻繁項集一樣具有反單調(diào)性質(zhì).

1.2生成器精簡表示模型

生成閉合項集的第一步是挖掘生成器，但是相關學者經(jīng)過研究后發(fā)現(xiàn)生成器本身也可以作為頻繁項集的一種精簡表示方法，進而壓縮頻繁項集規(guī)模.在文獻[9]中，Bastide Y等人提出了一種以頻繁生成器為基礎的一種頻繁項集精簡表示模型—生成器模型.頻繁生成器FG (Frequent Generator)是生成器精簡表示模型的基礎.設項集X為頻繁生成器，說明項集X不僅是頻繁的，而且也是生成器，F(xiàn)G={X|X∈F,X∈G}.但是僅有頻繁生成器FG是不能足以判斷一個項集X是否為頻繁項集.

因此需要加入另外一個輔助判斷的集合，生成器邊界.生成器邊界包含最小不頻繁生成器，若項集X為生成器邊界，則X為生成器，且X不頻繁，X的任意子集均為頻繁生成器，即

GBd={X∈G|X?F∧(?Y?X,Y∈FG)}.

生成器精簡表示模型由三個集合所構成，分別為：在數(shù)據(jù)庫D交易記錄中出現(xiàn)的不同項的集合I，頻繁生成器集合FG，生成器邊界集合GBd.需要注意的是，集合I和集合GBd只存儲集合，不存儲其他信息.而在集合FG中，存儲的是頻繁生成器集合，以及每個生成器的支持度.

生成器精簡表示模型對于任意一個項集X，首先判斷項集X是否是頻繁項集，如果是頻繁項集，再尋找其支持度.過程如下：

在文獻[9]中，學者Bastide Y等人也提出一種算法PASCAL挖掘出生成器精簡表示所需要的頻繁生成器集合和邊界集合.算法PASCAL主要步驟如下[3,9]：

1)Ck←PASCAL_GEN(Pk-1);

2)if?(c∈Ckwhere c.key=true) then

3)forall o∈D do begin

4)Co←subset(Ck,o);

5)forall c∈Cowhere c.key=true do

6)c.sup++;

7)end

8)forall c∈Ckdo

9)if c.sup≥minsup then begin

10)if c.key and c.sup=c.pred_sup then

11)c.key←false;

12)Pk←Pk∪{c};

從該算法中，可以看出，Ck存在多次生成同一個候選項集的問題，同時針對于每一個候選項集c，需要掃描數(shù)據(jù)庫得到其支持度，為了判斷一個候選項集是否為生成器，需要和其所有直接子集進行比較.這些缺點使得算法的執(zhí)行效率比較低下.

1.3枚舉樹

Rymon枚舉樹[10-11]的思想是在一個給定的集合元素中設定一個偏序.這種偏序可以是人為設定的也是可以任意指定的.這種偏序保證了在枚舉樹上的節(jié)點之間的父母/孩子關系.枚舉樹能夠?qū)⒁粋€集合中所有元素的各種組合很完整地沒有重復的枚舉出來，這點非常適合解決搜索問題.

枚舉樹的高效使用特點體現(xiàn)在搜索的過程中，如果某一個節(jié)點不滿足要求，可以將該分支完整的進行剪枝.在文獻[9]中,頻繁生成器也具有典型的反單調(diào)性質(zhì),非常適合在Rymon枚舉樹上進行搜索.如果一個節(jié)點不是頻繁生成器,則該分支下面所有節(jié)點都不是頻繁生成器.

2算法

在本節(jié)中,提出了一種快速挖掘頻繁核心項集算法FMG(Fast Mining Generators).傳統(tǒng)的生成器算法中存在的掃描數(shù)據(jù)庫得到支持度，候選項集重復生成，遍歷候選項集所有的直接子集等三個嚴重缺點，這三個缺點會嚴重影響挖掘生成器的效率.算法FMG針對于這些問題進行解決.

2.1生成器判斷定理

在閉合項集算法，提出了一個函數(shù)g，該函數(shù)能夠返回在數(shù)據(jù)庫中出現(xiàn)所有該項集的元素的行.該函數(shù)定義如下：

g(X)={o∈O|?i∈X,(o,i)∈R}從函數(shù)g中可以看出，項集X的支持度等于|g(X)|.

設i為單個項，i?X，則項集X∪i的支持度為|g(X)∩g(i)|.

生成器判斷定理：設X項集為頻繁生成器，i為某單個項，i?X.如果不存在某個項y，y∈X，g(y)?g(i),或者g(i)?g(y)，則項集X∪i是生成器.如果|g(X)∩g(i)|大于等于最小支持度，則為頻繁生成器.

證明：設g(y)?g(i)，則g(y) ∩g(i)=g(i),即g(X∪i)=g(X).因此|g(X∪i)|=|g(X)|，則項集X∪i和項集X的支持度是相等的.根據(jù)2.1節(jié)中的定義，項集X∪i不是生成器.同理，當g(y)?g(i)時，項集X∪i也不是生成器.

因此當不存在這樣y的時候，項集X∪i是生成器，并且其支持度為|g(X)∩g(i)|，如果支持度最小支持度，則為頻繁生成器.

2.2FMG算法

根據(jù)以上思想，本文提出了新的算法FMG，該算法采用2.1，將數(shù)據(jù)集中的每個項的g函數(shù)得到的結(jié)果進行存儲.在集合中POST為所有項的集合，并且集合中的元素之間存在一種偏序關系.

算法FMG

輸入：數(shù)據(jù)庫D，最小支持度minsup

輸出：生成器FG

1)FG=NULL

2)C1={1項集}

3)POST=C1

4)generator=null

5)FMG(generator,POST,FG)

6)return FG

procedureFMG(generator,POST,FG)

1)while POST≠NULL do

2)i=min(POST)

3)newgenerator= generator∪i

4)POST=POSTi

5)if(!contain(generator,i))

6)newgenerator.sup=|g(generator) ∩g(i) |

7)FG=FG∪newgenerator

8)if(newgenerator.sup) ≥minsup

9)NEWPOST=POST

10)FMG(newgenerator,NEWPOST,FG)

11)endif

12)endif

13)endwhile

procedurecontain(generator,i)

1)for all item j∈generator

2)if gen(j) ?gen(i) or gen(i) ?gen(j)

3)return true

4)endif

5)endfor

6)return false

2.3算法介紹

算法FMG的輸入是數(shù)據(jù)庫D和最小支持度minsup，輸出是生成器集合FG.在算法的第1步到第4步都是初始化，分別將所得到的FG集合設定為空，POST集合設定為數(shù)據(jù)庫D中的所有項，并且將最先的generator設定為空.在第5步正式調(diào)用算法，算法中的參數(shù)有三個，分別是上一輪生成的生成器generator，POST集合，需要返回的集合FG.需要注意的是POST集合中的元素已經(jīng)設定成一種偏序關系.

算法首先在POST集合中找到偏序最小的元素i，i和上一輪生成器generator集合形成新的候選項集newgenerator，并且在POST集合中除去元素i.通過這樣的步驟，形成Rymon枚舉樹的搜索空間.再調(diào)用contain函數(shù)判斷在generator的元素和i是否有包含關系.如果沒有在候選項集newgenerator是生成器，并且生成器的支持度為|g(generator)∩g(i)|，并且將newgenerator加入到FG集合中.如果newgenerator是頻繁的，則此時使用一個新的NEWPOST集合保持POST集合，并且繼續(xù)調(diào)用FMG算法直至POST集合為空為止.最后算法返回生成器集合FG.

contain函數(shù)主要有兩個參數(shù)，生成器generator和單個項i.對于生成器generator中的所有項j，如果存在gen(j) ?gen(i) 或者 gen(i) ?gen(j)，則根據(jù)3.1節(jié)生成器判斷定理，生成器generator和單個項i形成的候選項集不是生成器.

2.4算法實例

設數(shù)據(jù)庫D如下圖所示.

TID1abcd2abc3c4cd5ad

圖1數(shù)據(jù)庫D

設最小支持度為1，則g(a)={1,2,5}，g(b)={1,2},g(c)={1,2,3,4}, g(d)={1,4,5}.設枚舉樹的排序按照字母的順序進行排序.FG為空，POST={a,b,c,d}.

算法從a開始,POSTa={b,c,d}.則a是生成器.a和b組合，形成ab，POSTab={c,d}.由于g(a)和g(b)存在gen(b)?gen(a)，不滿足3.1節(jié)中定理的要求，所以ab不是生成器.a和c結(jié)合形成ac，POSTac=j5i0abt0b.ac滿足定理的要求，ac是生成器.ac和d組合，形成acd，POSTacd={}.acd滿足定理的要求，因此acd是生成器.

b，POSTb={c,d}.b是生成器，b和c組合，形成bc，POSTbc=j5i0abt0b.但是bc不滿足條件，存在gen(b) ?gen(c).因此bc不是生成器.b和d組合，形成bd，POSTbd={}.bd滿足要求，因此bd是生成器.

c，POSTc=j5i0abt0b.c是生成器，c和d組合，形成cd，POSTcd={}.cd滿足要求，是生成器.

d，POSTd={}.d是生成器.

3.實驗結(jié)果和分析

在本文中，提出了一種快速挖掘生成算法FMG，為了比較算法的性能，包括時間復雜度和空間復雜度，本文使用C++分別實現(xiàn)算法FMG和PASCAL以及在文獻[3]中提出的算法FPASCAL.但是在文獻[3]的實驗結(jié)果中，F(xiàn)PASCAL的時間效率優(yōu)于PASCAL，因此在本文和算法FPASCAL進行比較.

實驗平臺是win7環(huán)境下的PC機，i5處理器，4G內(nèi)存.實驗所采用的數(shù)據(jù)集均從http://fimi.cs.helsinki.fi/data/中下載的.為了全面衡量實驗效果，實驗中使用的數(shù)據(jù)集既包括密集型數(shù)據(jù)集：connect、chess、pumsb、pumbs_star，也包括稀疏型數(shù)據(jù)集T10I4D100K、T40I10D100K.FMG算法挖掘出來的生成器精簡表示結(jié)果和文獻[9]一致.實驗結(jié)果如表1、表2、圖1、圖2、圖3、圖4、圖5、圖6、圖7所示.

在表1和表2中可以看出，F(xiàn)MG算法得到的生成器精簡表示結(jié)果和PASCAL算法所挖掘出來的結(jié)果是一樣的.

在圖2和圖3、圖4以及圖5中，可以得知在數(shù)據(jù)密集型數(shù)據(jù)集上，算法FMG比FPASCAL要快3倍左右，并且隨著支持度的降低，這種優(yōu)勢會更加明顯.在圖6和圖7中，可以得知在數(shù)據(jù)稀疏性數(shù)據(jù)集上，算法FMG比FPASCAL要快30%，這是因為在稀疏型數(shù)據(jù)集上，需要存儲的項的g函數(shù)的值比較多，從而增加檢索時間，但是隨著支持度的降低，這種效率優(yōu)勢會繼續(xù)增加.

表1在connect數(shù)據(jù)集上運行結(jié)果

15%25%35%45%55%生成器負邊界生成器負邊界生成器負邊界生成器負邊界生成器負邊界FMG663992064215479543060582412258512931122640PASCAL663992064215479543060582412258512931122640

表2在pumsb數(shù)據(jù)集上運行結(jié)果

70%75%80%85%90%生成器負邊界生成器負邊界生成器負邊界生成器負邊界生成器負邊界FMG351848355451342672210237336106067755456111702622PASCAL351848355451342672210237336106067755456111702622

圖2　connect時間效率對比圖

圖3　chess時間效率對比圖

圖4　pumsb時間效率對比圖

圖5　pumsb_star時間效率對比圖

圖6　T10I4D100K時間效率對比圖

圖7　T40I10D100K時間效率對比圖

4結(jié)束語

本文在分析傳統(tǒng)生成器挖掘算法后，得出導致該算法效率低下的幾點原因.針對于這些問題，提出了一種快速挖掘生成器算法FMG，該算法使用Rymon枚舉樹作為搜索空間，采用Rymon枚舉樹的特定剪枝策略，利用生成器的特有性質(zhì)快速判斷候選項集是否為生成器，這些方法都很好地解決傳統(tǒng)算法中的三個重大缺點，從而快速地挖掘所有的生成器.實驗結(jié)果也很好地證明了FMG算法比傳統(tǒng)的算法PASCAL和后來改進的算法FPASCAL都快很多.隨著大數(shù)據(jù)時代和云計算時代的到來，如何將FMG算法應用到海量數(shù)據(jù)集中快速挖掘，如何在分布式環(huán)境下應用該算法，這些問題今后值得探討和研究.

參考文獻:

[1]Jiawei Han，Micheline Kamber．Data Mining Concepts and Techniques.數(shù)據(jù)挖掘概念與技術[M]．范明，孟小峰,譯．北京：機械工業(yè)出版社，2004：1-261.

[2]紀允.析取閉合項集的快速生成和恢復算法研究[D].安徽：合肥工業(yè)大學,2013.

[3]許普樂,張勤,紀允.基于FP樹的一種快速挖掘生成器算法[J].安慶師范學院學報(自然科學版),2013,19(1)：48-53.

[4]陳凱,馮全源.最大頻繁項集的高效挖掘[J].微電子學與計算機,2005,22(8):22-25.

[5]Bayardo R J. Efficiently mining long patterns from databases[C]//Proc of the ACM SIGMOD Int Conf on Management of Data. New York: ACM Press, 1998: 85- 93.

[6]陳俊杰,崔曉紅.基于FP-Tree的頻繁閉合項目集挖掘算法的研究[J].計算機工程與應用,2006,42(34):169-171.

[7]譚軍,卜英勇,楊勃.一種高效的閉頻繁模式挖掘算法[J].計算機工程與應用,2010,46(6):130-132.

[8] Pasquier N, Bastide Y, Taouil R, et al. Discovering frequent closed itemsets for association rules[C]//7th Intl. Conf. on Database Theory, January：1999: 398-416.

[9] Bastide Y, Taouil R. Pasquire N. Mining frequent patterns with counting inference [J]. SIGKDD Explorations,2000, 2(2): 66-75.

[10] Rymon R. Search through Systematic Set Enumeration[C]//Proc of Third Int’l Conf. on Principles of Knowledge Representation and Reasoning, 1992:539-550.

[11]田衛(wèi)東，紀允.一種頻繁核心項集的快速挖掘算法[J].計算機工程,2014,40(6):120-124.

(責任編輯魯越青)

A Fast Mining Generator Algorithm

Xu PuleJi Yun

(1.Office of Educational Administration, Wuhu Vocational and Technical College, Wuhu, Anhui 241006;2.Tongling Branch, China Mobile Communication Group Anhui Co., Ltd., Tongling, Anhui 244000)

Abstract：Generators are a classical model concisely represented in frequent itemsets, whose traditional mining algorithm has such deficiencies as repeated generations of candidate itemsets and whose support obtained by repeatedly scanning database needs traversing all direct subsets. All those drawbacks result in lower generation efficiency. Motivated by this, a fast mining generator algorithm FMG is proposed. This algorithm uses the Rymon setenumeration tree as its searching space; a generator determiner lemma proposed in this paper is used to quickly determine a candidate itemset and to select particular paths for pruning. All the methods are helpful for mining generators. Experimental results show that this algorithm not only has better performance than traditional ones, but also is faster than a fast mining generator algorithm proposed recently.

Key words：data mining; frequent itemset; concise representation; Rymon setenumeration tree; generator

收稿日期：2016-01-12基金項目：安徽省高等教育振興計劃重大教學改革研究項目“職業(yè)院校信息化教學改革的研究與實踐”(項目編號2014zdjy198); 安徽省高校優(yōu)秀青年人才支持計劃重點項目 “職業(yè)院校教育信息化發(fā)展路徑研究-以安徽省為例”(項目編號：gxyqZD2016591)

作者簡介：許普樂 (1980- )，男，安徽蕪湖人，副教授，研究方向：數(shù)據(jù)挖掘、智能計算.

doi：10.16169/j.issn.1008-293x.k.2016.07.13

中圖分類號：TP311

文獻標志碼：A

文章編號：1008-293X(2016)07-0063-06