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

衛朝霞，鄒倩影

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

1 引言

頻繁子樹挖掘是數據挖掘的主要研究內容，在生物信息、Web結構分析等方面具有較高的應用價值。作為如此有價值的任務，同樣也充滿挑戰，例如，即便使頂點集合縮小到最小范圍內，仍然能形成很多結構不一致的樹，并且每一棵樹的不同節點能夠取相同的權，這會導致對樹的同構判斷非常復雜。

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

上述方法雖然簡化了挖掘過程，但是不能描述數據對象之間的內在聯系，在挖掘中會產生大量的冗余信息，影響挖掘效率。由于數據目標不僅是集合關系，更多時候是具有結構層次的，因此，在模式增長[3]的基礎上對嵌入式頻繁子樹進行挖掘，并在挖掘過程中提出如下要求：數據庫必須是大量且真實的；挖掘目標與知識需要滿足用戶要求，是可理解、可運用的，能夠通過自然語言對其表達，并且帶有特定約束條件。按照上述要求運用融合思想對數據進行清洗，獲取融合后的壓縮樹，使挖掘結果中冗余信息量減少，進一步提高挖掘效率。

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

2.1 挖掘任務分析

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

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

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

(1)

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

2.2 模式增長性質與增長過程研究

2.2.1 模式增長性質分析

基于上述挖掘任務，通過模式增長方法對嵌入式頻繁子樹挖掘時會利用如下兩個重要性質：

性質2：假設SD表示一個序列數據庫，α為此數據庫中某個ξ-模式，針對項目e而言，序列αe為SD中某個ξ-模式，則在α的候選后綴中，項目e屬于頻繁項。

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

圖1 所搜空間裁剪示意圖

2.2.2 模式增長過程

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

步驟一：對森林數據庫D進行掃描，尋找全部頻繁標識，每個標識均與一個長度為1的頻繁子樹相對。

步驟二：根據不同頻繁1項子樹，劃分搜索空間。并針對任意一個頻繁1項子樹，建立與其對應的投影庫，利用頻繁增長點開拓已有子樹模式，獲得新模式。

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

2.3 模式增長框架建立

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

假設S(rs)表示頻繁(k-1)-子樹，w為樹S(rs)的最后節點，則最右路徑表示為

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

(2)

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

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

圖2 模式增長框架圖

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

2.4 基于融合壓縮的數據清理

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

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

圖3 融合壓縮樹示意圖

2.5 樹與森林的拓撲編碼

基于數據清理結果，對樹與森林進行拓撲編碼，拓撲編碼的方式有兩類，一類是對投影庫重新分配動態空間，該方法能夠確保數據庫中不會再有無用節點；另一種是使投影庫和初始庫共同享用同一個空間，采用過濾處理方法消除冗余節點。后者消耗內存較低，能夠提升挖掘效率，本研究采用第二種方法參考數組結構的隨機存取性質，確定樹與森林的拓撲編碼方式。

已知樹T(r)，按照節點順序排列可以組成一個標識符序列，并把描述節點層次的數據記錄到序列中，使其包括樹的拓撲信息，稱其為樹T(r)的拓撲序列。假如T(r)的最右節點是ω，則T(r)的拓撲序列表示為

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

(3)

其中，ulu為拓撲序列中的某個元組。

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

綜上所述，樹與森林的拓撲編碼如下：

1)樹的任意一節點分為三個域，分別是：lable(標識符)、level(層次)以及scope(等于)。

2)樹是由節點構成的數組，節點在其中的位置和節點順序需要始終一致。

3)森林是樹組成的數組。

2.6 挖掘算法實現

結合數據清理結果與頻繁子樹拓撲編碼結果，對嵌入式頻繁子樹實施挖掘，具體過程如下：

輸入：森林數據庫D與最小支持度閾值minsup 。

輸出：頻繁子樹集Ω。

步驟一：掃描初始數據庫中全部樹的根節點，獲取頻繁1-子樹集合L1，并將此集合中全部頻繁1-子樹加入到頻繁子樹隊列freqtree-vec中。

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

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

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

步驟五：把Fk加入到頻繁子樹集合Ω中，實現嵌入式頻繁子樹挖掘。

在實現頻繁子樹的挖掘后必須對時間復雜度進行分析。假設某個節點經過擴展后獲得b個頻繁子節點。此時，利用挖掘算法獲取的最終頻繁子樹為一棵完全b叉樹T。若此完全b叉樹T的深度表示為d，節點總數是f，下述使用分治法分析時間復雜度。

圖4 時間復雜度分析圖

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

(4)

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

(5)

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

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

(6)

綜上所述，通過數據清理與頻繁子樹隊列裁剪，降低了挖掘過程的復雜度，實現對嵌入式頻繁子樹的高效挖掘。

3 仿真研究

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

3.1 最小支持度相同

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

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

分析圖5可知，文獻[1]方法與文獻[2]方法挖掘的頻繁子樹總數量基本一致，但是所提方法的挖掘總數明顯高于其它兩種方法，主要因為該方法充分利用模式增長性質，逐層進行挖掘，從而得到更加全面的頻繁子樹。

3.2 數據規模相同

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

圖6 數據規模相同下頻繁子樹挖掘數量

如上圖6所示，在最小支持度逐漸遞增的過程中，不同方法挖掘總數隨最小支持度增加而減少。在相同支持度情況下，所提方法的頻繁子樹挖掘數量高于其它方法，特別是在支持度較小時，優勢更加明顯。這是因為其它兩種方法都不包含隱含子樹，而所提方法隱含子樹出現概率較大，而隱含子樹對挖掘總數量會產生較大影響。隨最小支持度的增加，使頻繁度提高，此時隱含子樹出現概率降低，使頻繁子樹挖掘總量呈現下降趨勢。

3.3 挖掘效率對比

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

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

圖7中顯示，當數據規模逐漸增大時，不同方法執行時間逐漸增加，但是所提方法執行時間總體上低于其它方法，其最高耗時約1.2s，主要因為所提方法對數據進行了清洗，并進行融合壓縮處理，數據預處理不但能提升數據質量，還能獲得更好的挖掘結果。減少冗余數據，提高了挖掘效率。

4 結論

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