基于覆蓋模式的頻繁子樹挖掘方法

夏 英，李洪旭

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

基于覆蓋模式的頻繁子樹挖掘方法

夏 英，李洪旭*

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

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

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

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

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

1 度孩子數(shù)編碼

定義1 樹的支持度和頻繁子樹。

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

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

圖1 樹T實例 圖2 樹t實例

2 MCRP算法

定義2 最大前綴編碼。

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

定義3δ′-覆蓋。

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

1)當(dāng)m=2時，式(1)化簡為式(2)。

(2)

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

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

(3)

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

a)當(dāng)k為偶數(shù)時，k+1為奇數(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ù)時，k+1為偶數(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時，式(1)成立。

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

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

因為n為大于2的任意正整數(shù)，由h=n-?n/g」,n%g=0,1可得h=n+1-?(n+1)/g」,(n+1)%g=0,1成立。又因為節(jié)點數(shù)為n的g叉樹變成節(jié)點數(shù)為n+1的g+1叉樹時，h會相應(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ù)量為M(n)，接下來證明基于最大前綴編碼的邊擴(kuò)展方法生成候選子樹數(shù)量H(n)的公式。

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

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

(4)

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

2.2 輸出覆蓋模式

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

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

2.3 MCRP算法偽代碼

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

MCRP(D,min_sup,δ′)

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

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

//Sk表示k階頻繁子樹集合

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

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

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

1)

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

2)

For(inti=0;i

3)

For(intj=i;j

4)

S1(i)與S1(j)合并擴(kuò)展所得候選子樹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

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 算法時間復(fù)雜度分析

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

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

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

3 實驗設(shè)置與分析

3.1 實驗設(shè)置

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

表1 實驗環(huán)境

3.2 實驗分析

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

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

4 結(jié)語

本文探討了無序樹的頻繁子樹挖掘問題。首先，改進(jìn)了一種寬度孩子數(shù)編碼方式，該編碼方式保留了節(jié)點及其孩子節(jié)點的位置信息，使得在計算子樹支持度的時間效率得到了提升；然后，在寬度孩子數(shù)編碼基礎(chǔ)上，提出了基于最大前綴編碼的邊擴(kuò)展方式用于生成所有的候選子樹，避免了頻繁子樹信息的遺漏；最后，在δ′-覆蓋概念的基礎(chǔ)上輸出覆蓋模式，避免輸出大規(guī)模的頻繁子樹影響后續(xù)操作的效率。實驗結(jié)果表明MCRP算法在頻繁子樹降低輸出規(guī)模以及時間開銷上是有效的。頻繁子樹挖掘中生成候選子樹一直以來都是效率瓶頸之一，基于投影的思想挖掘頻繁子樹雖然不用生成候選子樹，但需要消耗大量內(nèi)存空間，如何彌補(bǔ)該方式的缺陷以及如何應(yīng)對海量數(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ī)工程與設(shè)計,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] 楊沛,譚琦.極大頻繁子樹挖掘及其應(yīng)用[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。

國家自然科學(xué)基金資助項目(41201378)。

夏英(1972—)，女，四川南充人，教授，博士生導(dǎo)師，博士，主要研究方向：數(shù)據(jù)庫與數(shù)據(jù)挖掘、云計算與大數(shù)據(jù)、空間信息處理；李洪旭(1990—)，男，四川資陽人，碩士研究生，主要研究方向：數(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.