基于模式增長的嵌入式頻繁子樹挖掘算法研究

衛(wèi)朝霞，鄒倩影

(1.四川大學(xué)錦城學(xué)院，四川 成都 611731；2.電子科技大學(xué)成都學(xué)院，四川 成都 611731)

1 引言

頻繁子樹挖掘是數(shù)據(jù)挖掘的主要研究內(nèi)容，在生物信息、Web結(jié)構(gòu)分析等方面具有較高的應(yīng)用價(jià)值。作為如此有價(jià)值的任務(wù)，同樣也充滿挑戰(zhàn)，例如，即便使頂點(diǎn)集合縮小到最小范圍內(nèi)，仍然能形成很多結(jié)構(gòu)不一致的樹，并且每一棵樹的不同節(jié)點(diǎn)能夠取相同的權(quán)，這會(huì)導(dǎo)致對樹的同構(gòu)判斷非常復(fù)雜。

針對上述問題，一些學(xué)者給出如下方法。文獻(xiàn)[1]提出基于B-list的頻繁子樹挖掘算法。采用B-list數(shù)據(jù)結(jié)構(gòu)挖掘頻繁項(xiàng)集，將全序搜索樹當(dāng)作搜索空間，通過父等價(jià)剪枝方法限制搜索范圍，并結(jié)合MFI-tree投影技術(shù)完成挖掘。實(shí)驗(yàn)結(jié)果表明，該算法無論在稠密數(shù)據(jù)集還是稀疏數(shù)據(jù)集中都有較好挖掘效果。文獻(xiàn)[2]提出基于FP-Tree的頻繁子樹挖掘方法。將數(shù)據(jù)集合分為大小相同的模塊進(jìn)行挖掘，任意一個(gè)模塊都運(yùn)用三角矩陣的方式進(jìn)行儲(chǔ)存，并設(shè)計(jì)一個(gè)NCFP-Tree儲(chǔ)存每個(gè)滑動(dòng)窗口中的頻繁項(xiàng)集，使用優(yōu)化挖掘算法將每個(gè)窗口中頻繁子樹全部挖掘出來。該方法挖掘過程簡便，挖掘準(zhǔn)確率較高。

上述方法雖然簡化了挖掘過程，但是不能描述數(shù)據(jù)對象之間的內(nèi)在聯(lián)系，在挖掘中會(huì)產(chǎn)生大量的冗余信息，影響挖掘效率。由于數(shù)據(jù)目標(biāo)不僅是集合關(guān)系，更多時(shí)候是具有結(jié)構(gòu)層次的，因此，在模式增長[3]的基礎(chǔ)上對嵌入式頻繁子樹進(jìn)行挖掘，并在挖掘過程中提出如下要求：數(shù)據(jù)庫必須是大量且真實(shí)的；挖掘目標(biāo)與知識(shí)需要滿足用戶要求，是可理解、可運(yùn)用的，能夠通過自然語言對其表達(dá)，并且?guī)в刑囟s束條件。按照上述要求運(yùn)用融合思想對數(shù)據(jù)進(jìn)行清洗，獲取融合后的壓縮樹，使挖掘結(jié)果中冗余信息量減少，進(jìn)一步提高挖掘效率。

2 基于模式增長的嵌入式頻繁子樹挖掘算法

2.1 挖掘任務(wù)分析

在進(jìn)行頻繁子樹挖掘之前，首先需要確定挖掘任務(wù)。指定樹中全部節(jié)點(diǎn)的順序，便得出有序樹[4]。已知樹T(v1)、標(biāo)簽集合L、頂點(diǎn)與邊集合分別為N、B，標(biāo)簽樹T(v1)存在映射f:N→L，則任意v∈N，f(v)=l∈L記為T(v1)=(L(N)，B)。

標(biāo)簽數(shù)據(jù)庫屬于標(biāo)簽樹集合，其中，任意一顆樹都是基于標(biāo)簽L的，若運(yùn)用TDB代表標(biāo)簽數(shù)據(jù)庫，則每個(gè)元組可以表示為(TID，Ti)。已知標(biāo)簽數(shù)據(jù)庫TDB與模式樹T，T的支持度表達(dá)式為

sup(T)=T(v1)|p(T)/X|

(1)

其中，p(T)為TDB所含T的實(shí)例數(shù)量，X為TDB中樹的總量。若T的支持度sup(T)≥minsup(0≤minsup ≤1)，則T代表TDB中頻繁子樹，minsup 是用戶規(guī)定的支持度閾值[5]。

2.2 模式增長性質(zhì)與增長過程研究

2.2.1 模式增長性質(zhì)分析

基于上述挖掘任務(wù)，通過模式增長方法對嵌入式頻繁子樹挖掘時(shí)會(huì)利用如下兩個(gè)重要性質(zhì)：

性質(zhì)2：假設(shè)SD表示一個(gè)序列數(shù)據(jù)庫，α為此數(shù)據(jù)庫中某個(gè)ξ-模式，針對項(xiàng)目e而言，序列αe為SD中某個(gè)ξ-模式，則在α的候選后綴中，項(xiàng)目e屬于頻繁項(xiàng)。

可利用上述性質(zhì)停止對頻繁子樹一條軌跡的搜索進(jìn)程。假設(shè)β不是SD中一個(gè)75%-模式，則任意一個(gè)包含β的序列都不能成為75%-模式，同樣不需要對以β開頭的空間子樹進(jìn)行搜索。圖1為所搜空間的裁剪示意圖。

圖1 所搜空間裁剪示意圖

2.2.2 模式增長過程

在考慮模式增長性質(zhì)的前提下將子樹模式增長過程分為下述兩步：

步驟一：對森林?jǐn)?shù)據(jù)庫D進(jìn)行掃描，尋找全部頻繁標(biāo)識(shí)，每個(gè)標(biāo)識(shí)均與一個(gè)長度為1的頻繁子樹相對。

步驟二：根據(jù)不同頻繁1項(xiàng)子樹，劃分搜索空間。并針對任意一個(gè)頻繁1項(xiàng)子樹，建立與其對應(yīng)的投影庫，利用頻繁增長點(diǎn)開拓已有子樹模式，獲得新模式。

假設(shè)U′表示一顆頻繁k子樹(k>1)，此時(shí)必然存在唯一一顆頻繁k-1子樹U，則U′是根據(jù)U的一個(gè)增長點(diǎn)獲得的。

2.3 模式增長框架建立

采用最右路徑拓展法[6]建立完整的模式增長空間，其本質(zhì)為任意一棵頻繁(k-1)-子樹只能在最右路徑的節(jié)點(diǎn)上進(jìn)行增長，在此條件下構(gòu)建一個(gè)新的頻繁k-子樹。

假設(shè)S(rs)表示頻繁(k-1)-子樹，w為樹S(rs)的最后節(jié)點(diǎn)，則最右路徑表示為

p=〈rs，u，…，w〉，u∈N

(2)

令函數(shù)pi代表返回路徑中的第i個(gè)節(jié)點(diǎn)(i=0，…，|p|-1)，若T(r)為在p(i)中加入子節(jié)點(diǎn)后，根據(jù)S(rs)增長獲得的頻繁k-子樹，當(dāng)i=|p|-1時(shí)，稱其為向下增長點(diǎn)；當(dāng)0≤i<|p|-1時(shí)，p(i)屬于向右增長點(diǎn)，增長數(shù)量表示為g=|p|。

針對某個(gè)待增長的頻繁(k-1)-子樹模式S(rs)，結(jié)合S(rs)拓?fù)浣Y(jié)構(gòu)，選取最右路徑p，確定所有節(jié)點(diǎn)pi在數(shù)據(jù)庫D中的投影，則全體投影組成S(rs)在pi處的投影庫。此時(shí)，頻繁子樹挖掘轉(zhuǎn)換為在S(rs)的增長點(diǎn)p(i)的投影庫中挑選頻繁節(jié)點(diǎn)的問題。若投影庫中節(jié)點(diǎn)總數(shù)量為m，將所有節(jié)點(diǎn)加在p(i)上，組成p(i)的子節(jié)點(diǎn)。此過程能夠通過遞歸進(jìn)行[7]。模式增長框架示意圖如圖2所示。

圖2 模式增長框架圖

圖2中，粗線表示最右路徑，陰影代表投影庫。在增長模式下于數(shù)據(jù)庫D中搜索由全部頻繁節(jié)點(diǎn)組成的1-子樹，將投影庫中頻繁節(jié)點(diǎn)添加到(k-1)-子樹增長點(diǎn)中，即可生成多棵頻繁k-子樹。

2.4 基于融合壓縮的數(shù)據(jù)清理

在實(shí)際應(yīng)用中，造成數(shù)據(jù)不統(tǒng)一、丟失等現(xiàn)象的原因較多。例如收集設(shè)備出現(xiàn)故障、網(wǎng)絡(luò)運(yùn)行不平穩(wěn)造成傳輸中斷和輸入錯(cuò)誤等，由這些操作產(chǎn)生的數(shù)據(jù)通常會(huì)導(dǎo)致挖掘結(jié)果不可靠。因此，在做挖掘準(zhǔn)備工作時(shí)，必須經(jīng)過數(shù)據(jù)清洗去除數(shù)據(jù)不一致、丟失等現(xiàn)象，此外還要識(shí)別存在較大差異的數(shù)據(jù)，使其更加光滑，為挖掘工作提供質(zhì)量更優(yōu)的數(shù)據(jù)。數(shù)據(jù)量劇增會(huì)對挖掘工作造成影響，實(shí)際上并不需要對全部數(shù)據(jù)進(jìn)行挖掘，通常只需要分析感興趣的信息。因此，有必要對數(shù)據(jù)進(jìn)行選擇，篩選有相關(guān)特征要求的數(shù)據(jù)，避免在分析所有數(shù)據(jù)時(shí)占用大量挖掘時(shí)間，降低挖掘效率。

采用融合壓縮樹原理進(jìn)行數(shù)據(jù)清理，融合壓縮[8，9]的主要思想為：將森林?jǐn)?shù)據(jù)庫D做數(shù)據(jù)預(yù)處理工作，去除非頻繁節(jié)點(diǎn)，獲得處理后的數(shù)據(jù)庫D′；遍歷僅包括頻繁節(jié)點(diǎn)數(shù)據(jù)庫中所有嵌入式頻繁子樹Ti=〈Ni，Bi，Ri〉，找出與頻繁子樹Ti具有同樣根節(jié)點(diǎn)的其它頻繁子樹Tj=〈Nj，Bj，Rj〉。假如根節(jié)點(diǎn)Ri的子節(jié)點(diǎn)不包括Rj的某子節(jié)點(diǎn)Ncj，此時(shí)需要建立一個(gè)包含Ncj信息的新節(jié)點(diǎn)，并將其加入到Ri的子節(jié)點(diǎn)Ncj中。進(jìn)行嵌入式逐層遍歷處理，將Ri每個(gè)子節(jié)點(diǎn)均進(jìn)行清理。根據(jù)上述融合壓縮思想，構(gòu)建如下融合壓縮樹。

圖3 融合壓縮樹示意圖

2.5 樹與森林的拓?fù)渚幋a

基于數(shù)據(jù)清理結(jié)果，對樹與森林進(jìn)行拓?fù)渚幋a，拓?fù)渚幋a的方式有兩類，一類是對投影庫重新分配動(dòng)態(tài)空間，該方法能夠確保數(shù)據(jù)庫中不會(huì)再有無用節(jié)點(diǎn)；另一種是使投影庫和初始庫共同享用同一個(gè)空間，采用過濾處理方法消除冗余節(jié)點(diǎn)。后者消耗內(nèi)存較低，能夠提升挖掘效率，本研究采用第二種方法參考數(shù)組結(jié)構(gòu)的隨機(jī)存取性質(zhì)，確定樹與森林的拓?fù)渚幋a方式。

已知樹T(r)，按照節(jié)點(diǎn)順序排列可以組成一個(gè)標(biāo)識(shí)符序列，并把描述節(jié)點(diǎn)層次的數(shù)據(jù)記錄到序列中，使其包括樹的拓?fù)湫畔ⅲQ其為樹T(r)的拓?fù)湫蛄?。假如T(r)的最右節(jié)點(diǎn)是ω，則T(r)的拓?fù)湫蛄斜硎緸?/p>

top(T)=〈rlr，…ulu，…ωlω〉

(3)

其中，ulu為拓?fù)湫蛄兄械哪硞€(gè)元組。

已知樹T1(r1，N1，B1)與T2(r2，N2，B2)，若它們屬于同質(zhì)結(jié)構(gòu)，則只存在唯一一個(gè)保序映射函數(shù)f:N1→N2，對于任意一個(gè)節(jié)點(diǎn)u∈N1，均有u=f(u)且lu=lI(u)

綜上所述，樹與森林的拓?fù)渚幋a如下：

1)樹的任意一節(jié)點(diǎn)分為三個(gè)域，分別是：lable(標(biāo)識(shí)符)、level(層次)以及scope(等于)。

2)樹是由節(jié)點(diǎn)構(gòu)成的數(shù)組，節(jié)點(diǎn)在其中的位置和節(jié)點(diǎn)順序需要始終一致。

3)森林是樹組成的數(shù)組。

2.6 挖掘算法實(shí)現(xiàn)

結(jié)合數(shù)據(jù)清理結(jié)果與頻繁子樹拓?fù)渚幋a結(jié)果，對嵌入式頻繁子樹實(shí)施挖掘，具體過程如下：

輸入：森林?jǐn)?shù)據(jù)庫D與最小支持度閾值minsup 。

輸出：頻繁子樹集Ω。

步驟一：掃描初始數(shù)據(jù)庫中全部樹的根節(jié)點(diǎn)，獲取頻繁1-子樹集合L1，并將此集合中全部頻繁1-子樹加入到頻繁子樹隊(duì)列freqtree-vec中。

步驟二：若隊(duì)列freqtree-vec為空，返回到頻繁子樹集合Ω，反之進(jìn)行下一步。

步驟三：根據(jù)覆蓋定理對子樹隊(duì)列freqtree-vec做裁剪，去除被覆蓋的頻繁子樹。

步驟四：從隊(duì)列freqtree-vec中挑選一個(gè)元素，記為Fk，如果Fk不能拓展，則進(jìn)行下一步操作；反之對Fk進(jìn)行拓展，獲得一個(gè)(k+1)-子樹，并將其加入到隊(duì)列freqtree-vec中，轉(zhuǎn)至步驟二。

步驟五：把Fk加入到頻繁子樹集合Ω中，實(shí)現(xiàn)嵌入式頻繁子樹挖掘。

在實(shí)現(xiàn)頻繁子樹的挖掘后必須對時(shí)間復(fù)雜度進(jìn)行分析。假設(shè)某個(gè)節(jié)點(diǎn)經(jīng)過擴(kuò)展后獲得b個(gè)頻繁子節(jié)點(diǎn)。此時(shí)，利用挖掘算法獲取的最終頻繁子樹為一棵完全b叉樹T。若此完全b叉樹T的深度表示為d，節(jié)點(diǎn)總數(shù)是f，下述使用分治法分析時(shí)間復(fù)雜度。

圖4 時(shí)間復(fù)雜度分析圖

因此，結(jié)合組合原理，可獲得下述遞推公式：

(4)

假設(shè)T(1)=1，則又存在如下遞推方程：

(5)

由上述分析結(jié)果可知挖掘過程中產(chǎn)生的頻繁子樹數(shù)量是非常大的，屬于指數(shù)級(jí)別。若在挖掘過程中對其進(jìn)行裁剪，這樣就可以降低算法的復(fù)雜度，若b等于2的機(jī)率是ρ，b為1的概率是1-ρ，此時(shí)時(shí)間復(fù)雜度計(jì)算公式為：

T(f)=ρ(2bd)=ρ(22dp×d(1-ρ))=ρ(22dp)

(6)

綜上所述，通過數(shù)據(jù)清理與頻繁子樹隊(duì)列裁剪，降低了挖掘過程的復(fù)雜度，實(shí)現(xiàn)對嵌入式頻繁子樹的高效挖掘。

3 仿真研究

為了驗(yàn)證基于模式增長的嵌入式頻繁子樹挖掘算法的有效性，通過仿真對比所提方法、文獻(xiàn)[1]方法、文獻(xiàn)[2]方法，給出不同方法的性能對比結(jié)果。實(shí)驗(yàn)數(shù)據(jù)集包括真實(shí)數(shù)據(jù)集CSLOGS和模擬數(shù)據(jù)集TreeGen，其中，真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集中均包含兩個(gè)分區(qū)，在上述兩個(gè)數(shù)據(jù)集中挖掘頻繁子樹。實(shí)驗(yàn)均在一臺(tái)ADM Athlon 3000+PC上進(jìn)行，內(nèi)存為1T，操作系統(tǒng)為RedHat Linuc 9.0，采用MATLAB軟件進(jìn)行數(shù)據(jù)處理。利用數(shù)據(jù)生成程序產(chǎn)生數(shù)據(jù)集合，其相關(guān)參數(shù)設(shè)置如下：樹最大深度E=10，樹最大扇初度F=6，在確保實(shí)驗(yàn)參數(shù)相同的情況下分別進(jìn)行如下實(shí)驗(yàn)。

3.1 最小支持度相同

檢測在最小支持度Smin=1%的情況下，數(shù)據(jù)集從10K～90K遞增過程中不同方法挖掘頻繁子樹的總數(shù)量，實(shí)驗(yàn)結(jié)果如下圖所示：

圖5 最小支持度相同情況下頻繁子樹挖掘數(shù)量

分析圖5可知，文獻(xiàn)[1]方法與文獻(xiàn)[2]方法挖掘的頻繁子樹總數(shù)量基本一致，但是所提方法的挖掘總數(shù)明顯高于其它兩種方法，主要因?yàn)樵摲椒ǔ浞掷媚Ｊ皆鲩L性質(zhì)，逐層進(jìn)行挖掘，從而得到更加全面的頻繁子樹。

3.2 數(shù)據(jù)規(guī)模相同

確定人工數(shù)據(jù)集為75K，最小支持度Smin從0.2%～1.8%逐漸遞增，在此情況下，比較不同方法的挖掘總數(shù)。

圖6 數(shù)據(jù)規(guī)模相同下頻繁子樹挖掘數(shù)量

如上圖6所示，在最小支持度逐漸遞增的過程中，不同方法挖掘總數(shù)隨最小支持度增加而減少。在相同支持度情況下，所提方法的頻繁子樹挖掘數(shù)量高于其它方法，特別是在支持度較小時(shí)，優(yōu)勢更加明顯。這是因?yàn)槠渌鼉煞N方法都不包含隱含子樹，而所提方法隱含子樹出現(xiàn)概率較大，而隱含子樹對挖掘總數(shù)量會(huì)產(chǎn)生較大影響。隨最小支持度的增加，使頻繁度提高，此時(shí)隱含子樹出現(xiàn)概率降低，使頻繁子樹挖掘總量呈現(xiàn)下降趨勢。

3.3 挖掘效率對比

使人工數(shù)據(jù)集從10K～90K遞增，將最小支持度設(shè)置為Smin=1%，對比不同方法的執(zhí)行時(shí)間。

圖7 不同方法挖掘效率對比圖

圖7中顯示，當(dāng)數(shù)據(jù)規(guī)模逐漸增大時(shí)，不同方法執(zhí)行時(shí)間逐漸增加，但是所提方法執(zhí)行時(shí)間總體上低于其它方法，其最高耗時(shí)約1.2s，主要因?yàn)樗岱椒▽?shù)據(jù)進(jìn)行了清洗，并進(jìn)行融合壓縮處理，數(shù)據(jù)預(yù)處理不但能提升數(shù)據(jù)質(zhì)量，還能獲得更好的挖掘結(jié)果。減少冗余數(shù)據(jù)，提高了挖掘效率。

4 結(jié)論

為方便從海量數(shù)據(jù)中提取所需信息，利用模式增長方式對嵌入式頻繁子樹進(jìn)行挖掘。仿真結(jié)果證明，所提方法在挖掘頻繁子樹較多的情況下，能夠提高執(zhí)行效率，并且與傳統(tǒng)方法相比蘊(yùn)含更多的結(jié)構(gòu)信息。但挖掘模式還需進(jìn)一步精簡，在今后研究中，在一定的允許誤差范圍內(nèi)，通過較為簡便的挖掘模式即可滿足用戶挖掘需要，進(jìn)一步提高信息分析工作的效率。