夏 英，李洪旭

(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065)(*通信作者電子郵箱565268915@qq.com)

基于覆蓋模式的頻繁子樹(shù)挖掘方法

夏 英，李洪旭*

(重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065)(*通信作者電子郵箱565268915@qq.com)

無(wú)序樹(shù)常用于半結(jié)構(gòu)化數(shù)據(jù)建模，對(duì)其進(jìn)行頻繁子樹(shù)挖掘有利于發(fā)現(xiàn)隱藏的知識(shí)。傳統(tǒng)的頻繁子樹(shù)挖掘方法常常輸出大規(guī)模且?guī)в腥哂嘈畔⒌念l繁子樹(shù)，這樣的輸出結(jié)果會(huì)降低后續(xù)操作的效率。針對(duì)傳統(tǒng)方法的不足，提出了一種用于挖掘覆蓋模式(MCRP)算法。首先,采用寬度孩子數(shù)編碼對(duì)樹(shù)進(jìn)行編碼;然后,通過(guò)基于最大前綴編碼序列的邊擴(kuò)展方式生成所有的候選子樹(shù);最后,在頻繁子樹(shù)集和δ′-覆蓋概念的基礎(chǔ)上輸出覆蓋模式集。與傳統(tǒng)的挖掘頻繁閉樹(shù)模式和極大頻繁樹(shù)模式的算法相比，該算法能夠在保留所有頻繁子樹(shù)信息的情況下輸出更少的頻繁子樹(shù)，并且將處理效率提高15%到25%。實(shí)驗(yàn)結(jié)果表明，所提算法能有效減小輸出頻繁子樹(shù)的規(guī)模，減少冗余信息，在實(shí)際操作中具有較高的可行性。

無(wú)序樹(shù)；頻繁子樹(shù)；最大前綴編碼；邊擴(kuò)展；覆蓋模式

隨著互聯(lián)網(wǎng)的發(fā)展，大量的WWW(World Wide Web)頁(yè)面、XML(eXtensible Markup Language)文檔等具有半結(jié)構(gòu)化特征的數(shù)據(jù)不斷涌現(xiàn)，對(duì)這些數(shù)據(jù)用無(wú)序樹(shù)建模，并利用頻繁子樹(shù)挖掘技術(shù)能夠有效挖掘隱藏在其結(jié)構(gòu)中的信息。目前，許多頻繁子樹(shù)挖掘算法已經(jīng)被提出，比如算法FP-Tree(Frequent Pattern Tree)[1]和PFP-Tree(Projection Frequent Pattern Tree)[2]采用基于投影的思想來(lái)挖掘頻繁子樹(shù)，算法EvoMiner[3]、MCFP-Tree(Mining Compressed Frequent Pattern Tree)[4]和FRESTM(Frequent Restrictedly Embedded SubTree Miner)[5]采用基于Apriori的思想進(jìn)行頻繁子樹(shù)挖掘。但這些算法會(huì)輸出大規(guī)模且?guī)в腥哂嘈畔⒌念l繁子樹(shù)集合，大規(guī)模的頻繁子樹(shù)輸出會(huì)影響后續(xù)的操作效率，為了減小頻繁子樹(shù)輸出規(guī)模、提高后續(xù)操作效率，挖掘頻繁閉樹(shù)的FBMiner(Frequent Closed Miner)[6]和極大頻繁子樹(shù)MFTM(Maximal Frequent Tree Mining)[7]兩種算法已經(jīng)被提出，這兩種算法雖然能夠有效減小頻繁子樹(shù)的輸出規(guī)模，但卻丟失了大量頻繁子樹(shù)的信息。

針對(duì)傳統(tǒng)方法的不足，本文提出了一種挖掘覆蓋模式(Mining CoveRage Pattern, MCRP)算法。該算法采用寬度孩子數(shù)編碼，該編碼方式記錄了每個(gè)節(jié)點(diǎn)與其孩子節(jié)點(diǎn)的位置關(guān)系，提高了后續(xù)子樹(shù)支持度計(jì)算的效率。在寬度孩子數(shù)編碼的基礎(chǔ)上，算法采用了一種基于最大前綴編碼序列的邊擴(kuò)展方式生成了所有的候選子樹(shù)，確保能夠找出所有的頻繁子樹(shù)，避免了信息的遺漏。此外，在δ′-覆蓋[8]概念的基礎(chǔ)上提出了一種新的δ′-覆蓋概念，在生成頻繁子樹(shù)的時(shí)候同時(shí)判斷該子樹(shù)是否滿足δ′-覆蓋條件，若滿足，算法將輸出該覆蓋模式。

1 度孩子數(shù)編碼

定義1 樹(shù)的支持度和頻繁子樹(shù)。

D={T1,T2,…,Tn}是樹(shù)數(shù)據(jù)集，T是樹(shù)模式，Dsup(T)=|{Ti|T?Ti,Ti∈D}|/|D|記為樹(shù)T的支持度，其中，|D|表示數(shù)據(jù)集的大小。給定最小支持度閾值min_sup∈[0,1]，如果Dsup(T)≥min_sup，則T是D上的頻繁子樹(shù)。

為了提高子樹(shù)支持度計(jì)算效率，在傳統(tǒng)字符串編碼[9]的基礎(chǔ)上優(yōu)化了一種寬度孩子數(shù)編碼。在寬度孩子數(shù)編碼中，樹(shù)的每個(gè)節(jié)點(diǎn)用(index(v),range(v),tag(v))三元組表示，其中index(v)表示節(jié)點(diǎn)v在樹(shù)的寬度優(yōu)先序列中的位置，range(v)表示節(jié)點(diǎn)v孩子的位置范圍，tag(v)表示節(jié)點(diǎn)v的標(biāo)簽。按照寬度優(yōu)先遍歷得到的三元組序列就是寬度孩子數(shù)編碼。由于無(wú)序樹(shù)中兄弟節(jié)點(diǎn)間是無(wú)序的，為了使寬度孩子數(shù)編碼更加規(guī)范，對(duì)于兄弟關(guān)系的樹(shù)節(jié)點(diǎn)按照其標(biāo)簽tag(v)的字典順序進(jìn)行排序。如圖1，T的寬度孩子數(shù)編碼為：code(T)=(1,(2-4),A)-(2,(5),B)-(3,(),C)-(4,(),D)-(5,(),E)。在計(jì)算子樹(shù)支持度時(shí)首先要統(tǒng)計(jì)子樹(shù)的頻數(shù)，例如，統(tǒng)計(jì)圖2中樹(shù)t的頻數(shù)時(shí)可以先在code(T)中找到節(jié)點(diǎn)A，然后直接在range(A)范圍內(nèi)查找C、D節(jié)點(diǎn)是否存在，避免了從頭到尾逐一查找，節(jié)約了時(shí)間。

圖1 樹(shù)T實(shí)例 圖2 樹(shù)t實(shí)例

2 MCRP算法

定義2 最大前綴編碼。

一棵無(wú)序樹(shù)按寬度孩子數(shù)編碼，去掉最后一個(gè)節(jié)點(diǎn)后剩余節(jié)點(diǎn)的編碼，稱為該樹(shù)的最大前綴編碼。

定義3δ′-覆蓋。

設(shè)T和T′是頻繁樹(shù)模式，若T?T′，T與T′之間的Jaccard距離[10]小于δ′，H(T′)≤H(T)+1且W(T′)≤W(T)+1，則稱T′δ′-覆蓋T。其中，H(T)、W(T)分別表示T的高度和寬度。

該算法主要分為兩大核心步驟：第一步使用基于最大前綴編碼的邊擴(kuò)展方式生成候選子樹(shù)并判斷候選子樹(shù)是否為頻繁子樹(shù)；第二步在頻繁子樹(shù)的基礎(chǔ)上輸出滿足δ′-覆蓋條件的覆蓋樹(shù)模式。

2.1 基于最大前綴編碼的邊擴(kuò)展

生成候選子樹(shù)一般采用邊擴(kuò)展方式，傳統(tǒng)的基于最右路徑擴(kuò)展[11]的方法在每次生成候選子樹(shù)的時(shí)候要事先找到最右路徑，降低了挖掘效率?；谧畲笄熬Y編碼的邊擴(kuò)展規(guī)定只有具有相同的最大前綴編碼的兩棵子樹(shù)才能夠進(jìn)行合并擴(kuò)展生成候選子樹(shù)，該方法彌補(bǔ)了上述方法的不足，在時(shí)間效率上有所提升，同時(shí)能夠生成所有的候選子樹(shù)，減少了信息的遺漏。最大前綴編碼相同的兩棵樹(shù)拓?fù)浣Y(jié)構(gòu)可能相同也可能不同。下面分別討論這兩種情況下候選子樹(shù)的生成方法。

2.1.1 拓?fù)浣Y(jié)構(gòu)相同

拓?fù)浣Y(jié)構(gòu)相同的兩棵待合并樹(shù)的編碼中的最后一個(gè)節(jié)點(diǎn)一定位于同一層且它們的父親節(jié)點(diǎn)的標(biāo)簽一定相同，此時(shí)合并擴(kuò)展生成的候選子樹(shù)的編碼中最后兩個(gè)節(jié)點(diǎn)可能是兄弟關(guān)系節(jié)點(diǎn)，也可能是雙親孩子關(guān)系節(jié)點(diǎn)，如圖3所示。

2.1.2 拓?fù)浣Y(jié)構(gòu)不同

拓?fù)浣Y(jié)構(gòu)不同的兩棵待合并樹(shù)的編碼中的最后一個(gè)節(jié)點(diǎn)可能在同一層也可能不在同一層，此時(shí)直接將兩棵樹(shù)的最大前綴編碼重疊，剩下的節(jié)點(diǎn)位置不變即可，如圖4所示。

圖3 相同拓?fù)浣Y(jié)構(gòu)的兩棵樹(shù)合并操作

圖4 不同拓?fù)浣Y(jié)構(gòu)的兩棵樹(shù)合并操作

生成越多的候選子樹(shù)意味著保留了越多的原始數(shù)據(jù)信息，對(duì)于某些要求精確結(jié)果的子樹(shù)挖掘應(yīng)用來(lái)說(shuō)，生成所有的候選子樹(shù)是很有意義的，基于最大前綴編碼的邊擴(kuò)展能夠生成所有的候選子樹(shù)，下面給出理論證明。

證明 設(shè)兩棵m(m≥2)叉n(n≥2)階頻繁樹(shù)通過(guò)窮舉法能夠生成的候選子樹(shù)數(shù)量為M(n)，基于最大前綴編碼的邊擴(kuò)展方法能夠生成候選子樹(shù)數(shù)量為H(n)，式(1)中h表示兩棵最大前綴編碼相同的m叉n階樹(shù)中每棵樹(shù)的邏輯結(jié)構(gòu)數(shù)。通過(guò)窮舉法發(fā)現(xiàn)M(n)與m、n之間具有如下關(guān)系：(?」表示向下取整運(yùn)算符)。

M(n)=h*(h+3);

(1)

接下來(lái)采用雙層嵌套的數(shù)學(xué)歸納法來(lái)證明上式的正確性。首先固定m的取值，采用數(shù)學(xué)歸納法證明M(n)與n的關(guān)系式成立，接下來(lái)假設(shè)m=g(g>2)時(shí)公式任然成立，最后推理出m=g+1時(shí)公式成立。

1)當(dāng)m=2時(shí)，式(1)化簡(jiǎn)為式(2)。

(2)

①當(dāng)n=2時(shí)，M(n)=4，通過(guò)窮舉法可以驗(yàn)證結(jié)果正確。

②假設(shè)當(dāng)n=k時(shí)，式(2)仍然成立，即式(3)成立：

(3)

③下面證明當(dāng)n=k+1時(shí)，式(3)成立。

a)當(dāng)k為偶數(shù)時(shí)，k+1為奇數(shù)，此時(shí)h=k+1-?(k+1)/2」=k+1-k/2=k/2+1，將h代入式(1)中可得M(k+1)=(k+1)2/4+2(k+1)+7/4。

b)當(dāng)k為奇數(shù)時(shí)，k+1為偶數(shù)，此時(shí)時(shí)h=k+1-?(k+1)/2」=k+1-(k+1)/2=k/2+1/2，將h代入式(1)中可得M(k+1)=(k+1)2/4+3(k+1)/2。

綜上，式(3)成立，進(jìn)而可得m=2時(shí)，式(1)成立。

2)假設(shè)m=g(g>2)時(shí)，式(1)仍然成立。

3)接下來(lái)證明當(dāng)m=g+1時(shí)，式(1)成立。

因?yàn)閚為大于2的任意正整數(shù)，由h=n-?n/g」,n%g=0,1可得h=n+1-?(n+1)/g」,(n+1)%g=0,1成立。又因?yàn)楣?jié)點(diǎn)數(shù)為n的g叉樹(shù)變成節(jié)點(diǎn)數(shù)為n+1的g+1叉樹(shù)時(shí)，h會(huì)相應(yīng)地變成h+1，所以,h=n+1-?(n+1)/(g+1)」,(n+1)%g=0,1。

綜上所述，式(1)得證。

上述已經(jīng)證明兩棵m(m≥2)叉n(n≥2)階頻繁樹(shù)通過(guò)窮舉法能夠生成的候選子樹(shù)數(shù)量為M(n)，接下來(lái)證明基于最大前綴編碼的邊擴(kuò)展方法生成候選子樹(shù)數(shù)量H(n)的公式。

通過(guò)基于最大前綴編碼的邊擴(kuò)展方法不難發(fā)現(xiàn)，拓?fù)浣Y(jié)構(gòu)相同的情況下可以生成4h棵子樹(shù)，拓?fù)浣Y(jié)構(gòu)不同的情況下可生成h(h-1)棵子樹(shù)，進(jìn)而得：

H(n)=4h+h(h-1)；

(4)

將M(n)中h表達(dá)式去下限符號(hào)后進(jìn)一步整理發(fā)現(xiàn)M(n)=H(n)。至此，基于最大前綴編碼的邊擴(kuò)展方法能夠生成所有的候選子樹(shù)得到了證明。

2.2 輸出覆蓋模式

為了減小頻繁子樹(shù)輸出規(guī)模，提高后續(xù)操作效率，用一個(gè)小的覆蓋模式集合來(lái)概括所有的頻繁子樹(shù)模式，領(lǐng)域?qū)＜抑恍枰治鲞@個(gè)小的覆蓋模式集合就可以了解數(shù)據(jù)集中的所有信息。若樹(shù)T被樹(shù)T′δ′-覆蓋，MCRP將只會(huì)輸出T′而不會(huì)輸出T。

覆蓋模式建立在δ′-覆蓋概念的基礎(chǔ)上，為了盡可能使覆蓋模式與其對(duì)應(yīng)的被覆蓋模式的結(jié)構(gòu)相似，規(guī)定覆蓋模式與其對(duì)應(yīng)的被覆蓋模式階數(shù)差的絕對(duì)值不能超過(guò)1。當(dāng)T′比T的高度大1時(shí)，在輸出T′的時(shí)候在其編碼的最前面加上標(biāo)號(hào)H，表示T′覆蓋了一個(gè)高度比自己小1的頻繁樹(shù)，領(lǐng)域?qū)＜彝ㄟ^(guò)去掉T′最后一層的最后一個(gè)節(jié)點(diǎn)就可以還原出未被輸出的頻繁樹(shù)T；當(dāng)T′比T寬度大1時(shí)，在輸出T′的時(shí)候在其編碼的最前面加上標(biāo)號(hào)W，表示T′覆蓋了一個(gè)寬度比自己小1的頻繁樹(shù)，領(lǐng)域?qū)＜彝ㄟ^(guò)去掉T′最右邊的節(jié)點(diǎn)就可以還原出未被輸出的頻繁樹(shù)T；同樣的道理，當(dāng)T′的寬度和高度均比T大1時(shí)，本文在T′編碼的最前邊加上標(biāo)號(hào)HW。理論和實(shí)驗(yàn)證明算法保留了原始頻繁子樹(shù)幾乎所有的信息，并且大大降低了頻繁子樹(shù)的輸出規(guī)模。

2.3 MCRP算法偽代碼

MCRP算法首先采用寬度孩子數(shù)編碼對(duì)樹(shù)進(jìn)行編碼，然后通過(guò)基于最大前綴編碼序列的邊擴(kuò)展方式生成所有的候選子樹(shù)。接下來(lái)計(jì)算候選子樹(shù)的支持度，找出頻繁子樹(shù)。由于本文對(duì)樹(shù)采用了寬度孩子數(shù)編碼，因此在線性時(shí)間復(fù)雜度內(nèi)可以完成候選子樹(shù)支持度的計(jì)算。最后在頻繁子樹(shù)集和δ′-覆蓋概念的基礎(chǔ)上輸出覆蓋模式集。MCRP算法偽代碼如下。

MCRP(D,min_sup,δ′)

輸入：數(shù)據(jù)集D，min_sup，Jaccard距離閾值δ′;

輸出：頻繁子樹(shù)的覆蓋模式集合CS。

//Sk表示k階頻繁子樹(shù)集合

//L(Sk)表示集合Sk的大小

//Sk(i)表示集合Sk中第i棵樹(shù)

//函數(shù)countNum(T)用于統(tǒng)計(jì)T的頻數(shù)

1)

遍歷數(shù)據(jù)集D，統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的頻度，D中樹(shù)的最大階數(shù)M，并將頻繁的節(jié)點(diǎn)存放在S1中

2)

For(inti=0;i

3)

For(intj=i;j

4)

S1(i)與S1(j)合并擴(kuò)展所得候選子樹(shù)T;

5)

If(countNum(T)/|D|≥min_sup)

6)

Sk←T;

7)

End for

8)

End for

9)

For(inti=2;i≤M;i++)

10)

CS← GenerateCorageTree(Si,δ′);

11)

ReturnCS;

函數(shù)GenerateCorageTree(Sk,δ′)

1)

If(L(Sk)≥2)

2)

For(inti=0;i

3)

For(intj=i+1;j

4)

If(Sk(i)與Sk(j)最大前綴編碼相同)

5)

If(Sk(i)與Sk(j)拓?fù)浣Y(jié)構(gòu)相同)

6)

T=合并擴(kuò)展Sk(i)與Sk(j);

7)

Else

8)

T將Sk(i)與Sk(j)最大前綴編碼重疊;

9)

End if

10)

If(countNum(T)/|D|≥min_sup)

11)

Sk+1←T;

12)

If(1-|{Tr|(T?Tr)&(Sk(e)?Tr),

Tr∈D}|/|{Tr|(T?Tr)|(Sk(e)?Tr),

Tr∈D}|≥δ′)

//e=i，j

13)

If(H(T)>H(Sk(e)))

//Tag(“H”,T)表示在code(T)的前面加上標(biāo)號(hào)H

14)

CSK←Tag(“H”,T);

15)

Else if(W(T)>W(Sk(e)))

16)

CSK←Tag(“W”,T);

17)

Else if(H(T)>H(Sk(e)) &&W(T)>W(Sk(e)))

18)

CSK←Tag(“HW”,T);

19)

End if

20)

End for

21)

End for

22)

ReturnCSK;

2.4 算法時(shí)間復(fù)雜度分析

函數(shù)GenerateCorageTree(Si,δ′)在生成k+1階候選子樹(shù)的時(shí)候需要遍歷頻繁k階子樹(shù)集合，以保證頻繁k階子樹(shù)集合中任意兩棵子樹(shù)都有機(jī)會(huì)被判斷是否有生成k+1階候選子樹(shù)的可能，最壞的情況下任意兩棵k階子樹(shù)都能生成k+1階候選子樹(shù)，此時(shí)的時(shí)間復(fù)雜度為O(L(Sk)2)。當(dāng)生成一棵候選子樹(shù)的時(shí)候需要計(jì)算該子樹(shù)的頻數(shù)，這一步需要的時(shí)間近似為O(k)，所以函數(shù)GenerateCorageTree(Si,δ′)的時(shí)間復(fù)雜度為O(k*L(Sk)2)。函數(shù)GenerateCorageTree(Si,δ′)只是輸出某一階頻繁子樹(shù)的覆蓋模式，MCRP算法需要輸出所有覆蓋模式，其時(shí)間復(fù)雜度為O(k*L(Sk)2*|M|)。在實(shí)際情況中MCRP算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于本文得出的時(shí)間復(fù)雜度，因?yàn)椴⒉皇侨我獾膬煽胟階子樹(shù)都能滿足條件生成k+1階候選子樹(shù)，并且實(shí)際生成的頻繁子樹(shù)的最大階數(shù)要遠(yuǎn)小于|M|。

FBMiner算法是頻繁閉樹(shù)模式挖掘中最經(jīng)典且挖掘效率最高的幾個(gè)算法之一。該算法采用基于最右路徑的邊擴(kuò)展的思想生成候選子樹(shù)。在生成k+1階候選子樹(shù)之前，首先需要遍歷k階頻繁子樹(shù)集合找到每一棵k階頻繁子樹(shù)的最右路徑，這一步的時(shí)間復(fù)雜度為O(k*L(Sk))。接著在k階頻繁子樹(shù)的最右路徑上的任意一個(gè)節(jié)點(diǎn)上擴(kuò)展一條邊生成k+1階候選子樹(shù)，這一步的時(shí)間復(fù)雜度為O(m)，其中m為最右路徑上的節(jié)點(diǎn)個(gè)數(shù)。然后計(jì)算候選子樹(shù)的支持度，這一步的時(shí)間復(fù)雜度近似為O((k+1)*L(Sk+1))。綜上，F(xiàn)BMiner算法的時(shí)間復(fù)雜度為O(m*k2*L(Sk)*L(Sk+1)*|M|)。

MFTM算法是極大頻繁樹(shù)模式挖掘中的代表性算法。其挖掘流程大致與FBMiner算法相同，不同的是在計(jì)算候選子樹(shù)支持度的時(shí)候，其時(shí)間復(fù)雜度為O(L(Sk+1)2)，通常情況下L(Sk+1)遠(yuǎn)遠(yuǎn)大于k+1。綜上，MFTM算法的時(shí)間復(fù)雜度近似為O(m*k2*L(Sk+1)2*|M|)。

3 實(shí)驗(yàn)設(shè)置與分析

3.1 實(shí)驗(yàn)設(shè)置

MCRP算法用于減少頻繁子樹(shù)的輸出數(shù)量，降低輸出頻繁子樹(shù)的冗余性，進(jìn)而提高候選領(lǐng)域?qū)＜业姆治鲂?。與MCRP算法類似，為了減小頻繁子樹(shù)的輸出規(guī)模，F(xiàn)BMiner和MFTM算法同樣只輸出部分具有代表性的頻繁子樹(shù)。為了驗(yàn)證MCRP算法可行性，本實(shí)驗(yàn)將MCRP算法與頻繁閉樹(shù)挖掘領(lǐng)域中的經(jīng)典算法FBMiner和極大頻繁子樹(shù)挖掘領(lǐng)域中的代表性算法MFTM在真實(shí)實(shí)驗(yàn)數(shù)據(jù)集NI-AGARA (http://research.cs.wisc.edu/niag-ara/data/)上進(jìn)行實(shí)驗(yàn)對(duì)比。該數(shù)據(jù)包含400多個(gè)XML文檔，每個(gè)文檔表示好萊塢某個(gè)演員的相關(guān)信息，以及其出演電影的相關(guān)信息。實(shí)驗(yàn)采用算法執(zhí)行時(shí)間和輸出頻繁子樹(shù)的數(shù)量作為衡量算法性能的兩個(gè)指標(biāo)。算法執(zhí)行時(shí)間越短表示算法的時(shí)間效率越高，算法輸出頻繁子樹(shù)的數(shù)量越少表示算法的去冗余能力越強(qiáng)。本實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境

3.2 實(shí)驗(yàn)分析

如圖5所示，圖中第一行分別表示Jaccard距離閾值δ′分別為0.2、0.4和0.6時(shí)MCRP、FBMiner和MFTM算法在不同支持度閾值min_sup的情況下輸出的頻繁子樹(shù)的數(shù)量。圖中第二行分別對(duì)應(yīng)不同δ′值時(shí)三個(gè)算法的執(zhí)行時(shí)間。由實(shí)驗(yàn)圖可知，MCRP算法輸出的頻繁子樹(shù)數(shù)量和算法執(zhí)行時(shí)間都要比算法FBMiner和MFTM輸出的頻繁子樹(shù)數(shù)量和執(zhí)行時(shí)間少。實(shí)驗(yàn)表明，MCRP時(shí)間效率優(yōu)于FBMiner和MFTM，并且能在不丟失頻繁子樹(shù)信息的情況下比FBMiner和MFTM輸出更少的頻繁子樹(shù)。

圖5 三種算法在δ′=0.2,0.4,0.6時(shí)頻繁子樹(shù)輸出數(shù)和執(zhí)行時(shí)間與支持度閾值的關(guān)系

4 結(jié)語(yǔ)

本文探討了無(wú)序樹(shù)的頻繁子樹(shù)挖掘問(wèn)題。首先，改進(jìn)了一種寬度孩子數(shù)編碼方式，該編碼方式保留了節(jié)點(diǎn)及其孩子節(jié)點(diǎn)的位置信息，使得在計(jì)算子樹(shù)支持度的時(shí)間效率得到了提升；然后，在寬度孩子數(shù)編碼基礎(chǔ)上，提出了基于最大前綴編碼的邊擴(kuò)展方式用于生成所有的候選子樹(shù)，避免了頻繁子樹(shù)信息的遺漏；最后，在δ′-覆蓋概念的基礎(chǔ)上輸出覆蓋模式，避免輸出大規(guī)模的頻繁子樹(shù)影響后續(xù)操作的效率。實(shí)驗(yàn)結(jié)果表明MCRP算法在頻繁子樹(shù)降低輸出規(guī)模以及時(shí)間開(kāi)銷上是有效的。頻繁子樹(shù)挖掘中生成候選子樹(shù)一直以來(lái)都是效率瓶頸之一，基于投影的思想挖掘頻繁子樹(shù)雖然不用生成候選子樹(shù)，但需要消耗大量?jī)?nèi)存空間，如何彌補(bǔ)該方式的缺陷以及如何應(yīng)對(duì)海量數(shù)據(jù)的挑戰(zhàn)將是后續(xù)研究的主要內(nèi)容。

References)

[1] YAKOP M A M, MUTALIB S, ABDUL-RAHMAN S. Data projection effects in frequent itemsets mining [M]// Soft Computing in Data Science. Berlin: Springer, 2015: 23-32.

[2] MALVIYA J, SINGH A, SINGH D. An FP tree based approach for extracting frequent pattern from large database by applying parallel and partition projection [J]. International Journal of Computer Applications, 2015, 114(18): 1-5.

[3] DEEPAK A, FERNNDEZ-BACA D, TIRTHAPURA S, et al. EvoMiner: frequent subtree mining in phylogenetic databases [J]. Knowledge and Information Systems, 2014, 41(3): 559-590.

[4] 吳倩,羅健旭.壓縮FP-Tree的改進(jìn)搜索算法 [J]. 計(jì)算機(jī)工程與設(shè)計(jì),2015,36(7):1771-1777.(WU Q, LUO J X. Improved search algorithm of compressed FP-Tree [J]. Computer Engineering and Design, 2015, 36(7): 1771-1777.)[5] ZHANG S, DU Z, WANG J T. New techniques for mining frequent patterns in unordered trees [J]. IEEE Transactions on Cybernetics, 2015, 45(6): 1113-1125.

[6] FENG B, XU Y, ZHAO N, et al. A new method of mining frequent closed trees in data streams [C]// Proceedings of the 2010 7th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway, NJ: IEEE, 2010: 2245-2249.

[7] 楊沛,譚琦.極大頻繁子樹(shù)挖掘及其應(yīng)用[J].計(jì)算機(jī)科學(xué),2008,35(2):150-153.(YAN P, TAN Q. Maximal frequent subtree mining and its application [J]. Computer Science, 2008, 35(2):150-153.)

[8] XIN D, HAN J, YAN X, et al. Mining compressed frequent-pattern sets [C]// Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim, Norway: VLDB Endowment, 2005: 709-720.

[9] LIU L, LIU J. Mining frequent embedded subtree from tree-like databases [C]// Proceedings of the 2011 International Conference on Internet Computing and Information Services. Washington, DC: IEEE Computer Society, 2011:3-7.

[10] JAIN A K, DUBES R C. Algorithms for Clustering Data [M]. Upper Saddle River, NJ: Prentice-Hall, Inc., 1988: 67-73.

[11] HAN K, LV W, YIN B, et al. Constrained frequent subtree mining method [C]// Proceedings of the 2014 5th International Conference on Digital Home. Washington, DC: IEEE Computer Society, 2014: 287-292.

Frequentsubtreeminingmethodbasedoncoveragepatterns

XIA Ying, LI Hongxu*

(SchoolofComputerScienceandTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

Unordered tree is widely used for semi-structured data modeling, frequent subtrees mining on it has benefit for finding hidden knowledge. The traditional methods of mining frequent subtrees often output large-scale frequent subtrees with redundant information, such an output will reduce the efficiency of subsequent operations. In view of the shortcomings of traditional methods, the Mining CoveRage Pattern (MCRP) algorithm was proposed for mining coverage patterns. Firstly, a tree coding rule according to the tree width and the number of children was presented. Then, all candidate subtrees were generated by edge extension based on the maximum prefix coding sequence. Finally, a set of coverage patterns was output on the basis of frequent subtrees andδ′-coverage concept. Compared with the traditional algorithms for mining frequent closed tree patterns and maximal frequent tree patterns, the proposed algorithm can output fewer frequent subtrees in the case of preserving all the frequent subtrees, and the processing efficiency is increased by 15% to 25%.The experimental results show that the algorithm can effectively reduce the size and redundant information of the output frequent subtrees, and it has high feasibility in practical operation.

unordered tree; frequent subtree; maximum prefix coding; edge extension; coverage pattern

2017- 03- 27;

2017- 04- 25。

國(guó)家自然科學(xué)基金資助項(xiàng)目(41201378)。

夏英(1972—)，女，四川南充人，教授，博士生導(dǎo)師，博士，主要研究方向：數(shù)據(jù)庫(kù)與數(shù)據(jù)挖掘、云計(jì)算與大數(shù)據(jù)、空間信息處理；李洪旭(1990—)，男，四川資陽(yáng)人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘與大數(shù)據(jù)。

1001- 9081(2017)09- 2439- 04

10.11772/j.issn.1001- 9081.2017.09.2439

TP391.4

A

This work is partially supported by National Natural Science Foundation of China (41201378).

XIAYing, born in 1972, Ph. D., professor. Her research interests include database and data mining, cloud computing and big data, spatial information processing.

LIHongxu, born in 1990, M.S. candidate. His research interests include data mining and big data.