李 巍，廖雪花，楊 軍

(四川師范大學 計算機科學學院，四川 成都 610101)

0 引 言

大數據時代，基于海量數據的科學研究領域受到廣泛關注并成為研究熱點，例如大數據分析、深度學習和數據挖掘等[1]。大數據呈現出明顯的半結構化特征，半結構化數據是使用樹形Tree數據結構模型的各類數據總稱，例如互聯網HTML文檔。半結構化數據具有自述性、標記性和動態(tài)性等特征而被廣泛應用，Internet使用半結構化數據格式的HTML文檔描述網頁內容，并使用半結構化數據格式XML文檔和JSON文檔進行Web信息存儲和信息交換，Microsoft公司使用半結構化數據格式Open XML存儲Office辦公軟件docx、xlsx、pptx等文檔，Redis和MongoDB等NoSQL數據庫也使用半結構化數據格式存儲Key-Value數據。

目前，半結構化數據聚類分析方法已經用于解決人們生產生活實際問題，例如，清華大學彭宗超等[2]在2020年新冠肺炎疫情期間基于網絡大數據分析技術進行新冠肺炎疫情應急防控工作，Chitra等[3]使用XML聚類為Smarty Web搜索引擎建模等。

本文使用樹形結構數據模型表示半結構化數據，提出一種以樹形結構數據集頻繁子樹模式為特征的半結構化數據集聚類方法。首先，介紹樹形結構數據集頻繁子樹模式挖掘方法和基于頻繁子樹為特征的聚類分析方法的理論背景。然后，本文提出一種基于模式增長策略的半結構化數據集頻繁子樹模式發(fā)現方法FSTPMiner，該方法使用編碼樹模型對樹形模型數據進行線性編碼，將樹結構數據集頻繁子模式挖掘轉化為線性表頻繁子模式挖掘，提高了樹形結構數據集頻繁模式挖掘效率。之后，使用頻繁子樹作為半結構化樹形數據特征，基于余弦相似度Cosine Similarity計算方法和凝聚型層次文檔聚類Hierarchical Clustering方法對半結構化文檔數據集進行聚類。在ACM SIGMOD數據集、NASA數據集和人工生成數據集上進行對照實驗，實驗結果驗證了本文半結構化文檔數據集聚類方法在保證正確率的前提下，其聚類效率具有一定優(yōu)勢。

1 相關理論基礎

1.1 含根有序標簽樹

半結構化數據文件由格式標記部分和文本內容部分共兩個主要部分組成，可使用如文檔對象模型DOM的含根有序標簽樹形模型表示，HTML文件的含根有序標簽樹DOM模型如圖1所示。

樹是一種非線性結構，是n個節(jié)點的有限集合，樹的一般性定義如下：

定義1 樹(Tree)：樹結構是無環(huán)連通圖結構T={V,E,r}， 其中：V是有限非空節(jié)點集合，E是有限非空邊集合，r是樹的根節(jié)點。

根據樹的不同特點和約束，可將樹分為含根樹和無根樹、有序樹和無序樹、標簽樹和無標簽樹等：

(1)含根樹與無根樹：若樹根節(jié)點r不為空，r∈V，即樹含有一個可作為所有其它節(jié)點的祖先的根節(jié)點，稱為“含根樹”；若樹根節(jié)點r為空，即無明確指定一個節(jié)點作為根節(jié)點，則稱為“無根樹”；

(2)有序樹與無序樹：若樹中任意節(jié)點的孩子節(jié)點之間有順序關系，這種樹稱為“有序樹”。若樹中任意節(jié)點的孩子節(jié)點之間沒有順序關系，則稱為“無序樹”；

(3)標簽樹和無標簽樹：若樹中任意節(jié)點都帶有一個標簽Tag，標簽Tag可用于區(qū)分不同的樹節(jié)點，則稱為“標簽樹”。若樹中任意節(jié)點都沒有標簽，即不區(qū)分樹中所有節(jié)點，則稱為“無標簽樹”。

1.2 半結構化數據聚類方法

針對海量半結構化數據進行數據分析的基礎工作是半結構化數據集聚類算法研究。由于數據集的半結構化特點，基于傳統(tǒng)結構化數據集的聚類分析方法并不適用于半結構化數據集[3]，所以很多研究集中在半結構化數據集高效聚類分析方法研究，這是很多領域需要解決的基礎性研究問題。

半結構化數據集的聚類分析研究工作主要集中在兩個問題的研究：第一是研究半結構化數據特征提取和半結構化數據間基于不同特征的相似性度量方法；第二是研究基于某種特征模式的半結構化數據集聚類分簇方法。國內外學者在半結構化數據集特征提取、相似性度量和聚類算法方面已經取得一些成果[4-6]。

在半結構化數據集頻繁模式和特征挖掘方面，現有算法可分類兩大類：

第一類是基于生成測試策略的方法，這種方法將半結構化數據頻繁模式挖掘過程分為兩個子過程，分別是候選子樹集產生階段和支持度產生階段。例如Chen Y等[7]提出使用生成測試策略的基于Cuts檢查樹間包含關系的方法。

第二類是基于模式增長策略的方法，這種方法采用結果集增長策略并反復迭代直至結果集是頻繁子樹完備的。國內外學者在半結構化數據集聚類算法方面取得一些成果[8-12]。

2 半結構化數據集頻繁子樹模式挖掘

2.1 頻繁子樹模式挖掘策略

在半結構化數據集頻繁子樹模式挖掘過程中，關鍵內容和主要計算開銷是半結構化樹形結構數據之間的差異比較和相似性度量。半結構化數據的差異比較和相似性度量本質是圖形結構數據Graph Structure Data的節(jié)點匹配問題。一般來講，這類圖形結構數據匹配問題涉及節(jié)點數量較大，圖中路徑較多，計算成本較大。以半結構化XML文檔數據為例，根據X-diff算法[13]，兩個XML文檔的差異比較算法的復雜度為式(1)

(1)

根據X-diff算法，兩個半結構化數據之間的差異計算復雜度與樹形結構的節(jié)點規(guī)模正相關。

因此，本文創(chuàng)新點在于提出并采用以下3個策略提高頻繁子樹模式的挖掘效率：

策略1：采用線性編碼重建樹結構數據。本策略的實現過程稱為編碼樹構建過程，該過程采用線性編碼樹模型描述半結構化數據，通過增加額外編碼信息，降低樹形結構數據集的遍歷計算開銷，將復雜度較高的樹形結構數據節(jié)點匹配和差異比較過程轉換成線性表結構的差異比較過程，這樣提高頻繁模式挖掘效率。

策略2：降低半結構化數據集規(guī)模。本策略的實現過程稱為數據集剪邊過程，該過程在遍歷已編碼的樹形結構數據集時，刪除不可能在頻繁子樹集中出現的頻度小于閾值的所有邊。由于不頻繁出現的邊被刪除，將會把一棵規(guī)模較大的樹形結構數據拆分成多棵規(guī)模較小的樹形結構數據。在該剪邊過程結束中，如果出現單節(jié)點樹結構，則將所有單節(jié)點樹刪除。

策略3：采用模式增長策略。本策略的實現過程稱為數據集壓縮過程，該過程基本思想是反復迭代遍歷半結構化樹形結構數據集，在每次遍歷過程中，合并具有最大頻繁度的相鄰節(jié)點，直至滿足停止條件。該策略優(yōu)點是每次遍歷都減小數據集規(guī)模，提高挖掘效率。

3棵示例半結構化數據建模的樹形結構數據T1、T2和T3如圖2所示，闡述在樹形結構數據集中挖掘頻繁子樹模式的過程(FSTPMiner)。在頻繁子樹發(fā)現過程中，假設用戶設定的最小頻繁度閾值為2，也就是挖掘發(fā)現在數據集中出現次數大于等于2次的所有子樹。

2.2 構建編碼樹

頻繁子樹挖掘FSTPMiner方法首先構建編碼樹，編碼樹是節(jié)點帶有編碼鏈信息的樹形結構數據，編碼鏈是一種鏈表結構，可以表示一顆含根有序標簽樹。

例如，圖2中樹T1的所有節(jié)點采用編碼鏈結構表示后，如圖3所示。

編碼鏈本質是保存含根有序標簽樹頻繁性質的鏈表結構，通過記錄每個樹節(jié)點在鏈表結構中的位置，以及其到父節(jié)點的距離，可與一棵含根有序標簽樹相互轉換。通過編碼鏈方法，可將含根有序標簽樹形結構數據集的頻繁子樹模式挖掘轉化成線性表結構數據集的頻繁子模式挖掘。

定義3 編碼樹(coding tree，CT)：編碼樹定義為無環(huán)連通圖CT={V,E,CL,L,F,r}， 其中V是樹結構的節(jié)點Vertex非空集合、E是樹結構的邊Edge非空集合、r是樹結構的根節(jié)點Root、CL是樹結構的編碼鏈非空集合、L是樹結構的各個節(jié)點v到編碼鏈cl映射的集合v→cl(其中，v∈V,cl∈CL)、F是遍歷樹時存儲邊頻繁度的集合。

編碼樹是每個節(jié)點都帶有編碼鏈的樹形結構，因為每個編碼鏈都可表示一顆無序樹，所以編碼樹可以被壓縮，即將所有孩子節(jié)點壓縮進編碼鏈中。

根據定義2和定義3，將圖2中樹T1、T2、T3構建編碼樹后如圖3所示。

2.3 剪邊與壓縮

構建編碼樹后，進行數據集剪邊操作和迭代壓縮操作。

定理1 在頻繁模式集中，所有子模式樹枝的頻繁度都大于等于頻繁度閾值。

證明：根據頻繁模式定義，所有子模式出現的次數均大于等于預定義的最小頻繁度閾值，所以所有子模式樹枝的頻繁度也大于等于預定義的最小頻繁度閾值。證畢。

根據定理1，進行剪邊操作。具體操作方法是將編碼樹中小于最小頻繁度閾值的樹枝刪除，然后刪除只有單節(jié)點的結構。

剪邊操作后進行壓縮操作。壓縮操作具體方法是反復迭代數據集，在每輪迭代過程中，將當前數據集中出現次數最多的樹枝進行壓縮操作，壓縮操作將樹的兩個節(jié)點合并成為一個點，同時，在這個合并后的節(jié)點的編碼鏈上更新壓縮后的內容。

圖2中樹形結構數據集T1、T2和T3經過構建編碼樹后，其2輪剪邊與壓縮迭代變換過程如圖4所示。

經過第1輪迭代，剪邊壓縮后的數據集如圖4(a)所示。此時，所有頻繁度為3的邊都已經被壓縮，即 (3,4)(3,5)(3,6)和(3,7) 這4條邊壓縮成節(jié)點3141526374。經過第2輪迭代，剪邊壓縮后數據集如圖4(b)所示，此時，所有頻繁度為2的邊也已經被壓縮。每輪壓縮后，都會將具有一定頻繁度(即一定的出現次數)的邊壓縮進節(jié)點的壓縮鏈中，例如，第1輪迭代壓縮所有出現3次的邊到編碼鏈中，第2輪迭代壓縮所有出現兩次的邊到編碼鏈中。

因為用戶設定的最小頻繁度為2，所以經過兩輪迭代剪邊與壓縮，最后得到的編碼樹就是頻繁子樹模式集，如圖4(b)所示。之后，根據編碼樹定義，將圖4(b)所示的所有編碼樹轉換為含根有序標簽樹結構數據，最終得到的樹形結構數據集就是出現次數大于等于閾值兩次的所有頻繁子樹模式。

2.4 頻繁子樹模式挖掘方法

結合構建編碼樹過程和剪邊壓縮過程，半結構化數據集頻繁子樹模式挖掘過程方法FSTPMiner的偽代碼描述如下：

頻繁子樹挖掘FSTPMiner算法

輸入：半結構化樹形結構數據集D={T1,T2,…,Tn}， 頻繁度閾值e。

輸出：頻繁子樹模式集F

(1) 為樹集D構建壓縮樹集CD={CT1,…,CTn};

(2)MaxFrq=MaxE(CD); //將最大的邊頻繁度MaxE(CD)賦值給變量MaxFrq

(3) FOR 每個編碼樹CT=(V,E,CL,L,F,r)∈CD//步驟(3)為剪邊操作

(4) FOR 每條邊(x,y)∈E//E是樹邊集合

(5) IF EFrq(x,y)

(6) IF 節(jié)點y是單節(jié)點 THEN 刪除y;

(7) ELSECD=CD∩以y為根的樹;

(8) IF |V|=1 THEN 在CD中刪除CT; //V是樹節(jié)點集合

(9) WHILEMaxFrq≥e; //壓縮操作

(10) FOR 每個CT=(V,E,CL,L,F,r)∈CD

(11) FOR 每條邊(x,y)∈E

(12) IF EFrq(x,y)=MaxFrqTHEN 壓縮邊(x,y);

(13)MaxFrq=MaxFrq-1;

(14)F←頻繁FK項集對應的子樹; //將頻繁子樹放入結果集F;

3 相似度計算和聚類

本文聚類過程將每個半結構化數據使用其包含的頻繁子樹作為特征，并組成相應的特征向量。然后使用余弦定理計算特征向量間的相似程度。最后的半結構化數據集聚類過程采用經典凝聚型層次聚類方法。

之后，使用余弦定理計算特征向量間的相似程度，設兩個半結構化文檔的特征向量分別為Fi和Fj，則Fi和Fj的相似度Sim(i,j) 計算方法如式(2)所示

(2)

最后，使用凝聚性層次聚類方法并根據半結構化文檔數據集的特征向量進行聚類，過程如下：

基于頻繁子樹模式的半結構化數據聚類算法

輸入：半結構化文檔數據集D，最小頻繁度e，層次聚類停止簇數閾值k

輸出：聚類結果

(1) 計算半結構化文檔數據集D的頻繁子樹模式集FP=FSTPMiner(D);

(2) 對數據集D中每個半結構化文檔構建特征向量

(3) 計算特征向量兩兩間的相似度并組成相似度矩陣Mm×m， 其中， 矩陣第i行第j列元素Mij值計算如下

其中，i=1,2,…,m-1，j=i+1,i+2,…,m;

(4) 在Mm×m中查找具有最大值的元素Mij， 找到具有最大相似度兩個簇i和簇j， 將這兩個簇合并成新簇Cnew;

(5) 計算新簇Cnew與其它簇的相似度， 更新相似度矩陣Mm×m;

(6) IF 簇數量>kTHEN 執(zhí)行步驟(4)

ELSE return 簇信息;

4 實驗結果與分析

4.1 實驗環(huán)境

本文相關實驗均在主頻為2.83 GHz 4 Core CPU、8 GB DDR4 2666MHz RAM的計算機上運行，操作系統(tǒng)為Fedora Core 6。

本文算法和其它相關對照算法均使用C++語言編寫實現，在代碼中使用C++ STL標準庫容器和函數。解析XML文檔DOM數據并處理樹形結構數據使用TinyXML第三方開源庫。

實驗使用半結構化XML文檔數據集，包括真實半結構化文檔數據集和人工半結構化文檔數據集。真實半結構化數據集來自ACM提供的SIGMOD標準XML文檔聚類數據集和美國航空航天局NASA提供的航天飛機組播數據抽樣半結構化數據集。人工數據集使用IBM XMLGenerator工具生成，共使用10個DTD文件，然后根據每個DTD文件隨機生成100篇XML文檔，因此人工數據集中共包含XML文檔1000(10×100) 篇。

4.2 實驗過程

在上述軟硬件實驗環(huán)境中，實驗過程分為兩階段：

第一階段，基于人工生成的半結構化數據集，使用本文提出的半結構化數據聚類算法與劉昕等提出的基于局部密度的快速文本聚類算法[14]進行對照分析。該階段實驗目的是驗證普通文本聚類方法在半結構化文檔數據集環(huán)境中的適用程度；

第二階段使用本文算法與其它已公開發(fā)表的半結構化文檔數據聚類算法進行對照分析，對照算法包括Costa等提出的基于貝葉斯概率主題模型的XML文檔聚類算法[9]、LIU等提出的ICQB算法[12]和Damalagas提出的經典半結構化文檔聚類算法[10]，這些算法是不同時期和不同應用環(huán)境下的半結構化文檔數據集的代表性聚類分析算法。

在聚類實驗過程中，頻繁子樹出現次數設定為3次(即頻繁度閾值為3)，所有凝聚型層次聚類過程停止條件閾值為k=10。

4.3 文本聚類算法對照實驗

為測試普通文本聚類方法在半結構化文檔數據集聚類環(huán)境中的適用程度，并驗證普通本文聚類方法與針對樹結構的聚類方法在半結構化數據集中的聚類效果，使用本文基于FSTPMiner的半結構化數據聚類算法與基于局部密度的快速文本聚類算法，基于人工生成的半結構化文檔數據集，進行文本聚類對照分析。

聚類結果主要指標數據見表1。

表1 本文方法與文本聚類方法對照結果

4.4 人工半結構化數據集實驗結果

分別使用基于FSTPMiner算法、Costa算法、ICQB算法和Damalagas算法對人工生成的半結構化XML數據集進行聚類，聚類結果正確率、召回率和聚類過程時間值見表2。

表2 人工數據集聚類結果

4.5 真實半結構化數據集實驗結果

對于ACM SIGMOD真實數據集和NASA真實數據集，分別使用本文基于FSTPMiner算法、Costa算法、ICQB算法和Damalagas算法進行半結構化XML文檔數據集進行聚類，聚類結果正確率和召回率見表3。

表3 真實數據集聚類結果

對于相同數據規(guī)模的半結構化數據集，使用聚類過程消耗的時間來衡量各個算法的聚類效率。在真實數據集對照實驗中，本文基于FSTPMiner的算法、Costa提出的算法、ICQB算法和Damalagas提出的算法的運行時間見表4。

表4 真實數據集聚類時間

4.6 實驗結果分析

基于人工生成的半結構化數據集，經過本文針對半結構化樹形結構數據聚類算法和普通文本聚類算法對照實驗結果，可以得到以下結論：

(1)本文針對半結構化數據樹形結構特點設計的聚類算法，其聚類效果要優(yōu)于普通文本聚類算法，在實驗中，聚類結果的正確率提高25.3%，召回率提高20.5%；

(2)半結構化數據聚類算法的聚類過程時間占用和內存空間占用要大于普通文本聚類算法，原因在于樹形結構模型的解析和存儲均大于文本線性模型。

對于各種半結構化數據集聚類算法，經過在真實半結構化數據集和人工生成半結構化數據集的各聚類算法對照實驗運行結果，可得出以下基本結論：

(1)本文基于FSTPMiner算法保證聚類結果正確率前提下，在半結構化數據集聚類效率方面具有優(yōu)勢。由于FSTPMiner算法使用半結構化數據集頻繁子樹模式作為數據特征進行聚類，這樣①減少了數據集樹節(jié)點總數，②避免了高時間消耗的樹形結構數據差異比較過程，節(jié)省聚類時間，提高聚類效率，實驗中相比于Costa算法，聚類效率提高39.97%；

(2)根據各算法對照實驗，基于FSTPMiner算法聚類結果的正確率和召回率略略低于Costa提出的算法，根據實驗，在NASA數據集中，聚類結果正確率和召回率比Costa方法分別低0.2%和0.2%。原因是FSTPMiner算法僅使用半結構化數據集頻繁子樹模式作為特征進行相似度計算，雖然提高聚類效率，但忽略了非頻繁模式的相似度信息。

綜上所述，①一個含根有序標簽樹結構數據可以采用某種標簽線性表結構表示，并且采用線性表結構的計算效率更優(yōu)，該思想可以推廣到其它樹形結構數據的應用領域；②對于其它類型的樹形結構數據，其線性化方法有待研究；③經典數據挖掘的剪邊思想在半結構化數據挖掘領域依然有效。

5 結束語

為有效挖掘半結構化數據集頻繁子樹，本文提出頻繁子樹挖掘FSTPMiner算法，FSTPMiner算法基于編碼樹結構，采用剪邊壓縮動態(tài)策略在半結構化數據集中高效地挖掘頻繁子樹模式，進一步提出使用頻繁子樹為特征的、基于凝聚型層次聚類過程的半結構化數據集聚類方法，最后經過在真實半結構化數據集和人工生成半結構化數據集的對照驗證實驗結果表明：①與文本聚類方法相比，本文基于FSTPMiner方法聚類正確率等指標提高幅度較大；②與其它半結構化數據聚類方法相比，本文基于FSTPMiner方法在聚類結果基本不變的前提下能有效提高聚類效率。

下一步可以研究結合半結構化數據子結構和子內容的頻繁子模式挖掘和聚類工作，也可以研究基于頻繁子樹模式的半結構化數據分類問題。