基于頻繁子樹(shù)模式的半結(jié)構(gòu)化數(shù)據(jù)集聚類

李 巍，廖雪花，楊 軍

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

0 引 言

大數(shù)據(jù)時(shí)代，基于海量數(shù)據(jù)的科學(xué)研究領(lǐng)域受到廣泛關(guān)注并成為研究熱點(diǎn)，例如大數(shù)據(jù)分析、深度學(xué)習(xí)和數(shù)據(jù)挖掘等[1]。大數(shù)據(jù)呈現(xiàn)出明顯的半結(jié)構(gòu)化特征，半結(jié)構(gòu)化數(shù)據(jù)是使用樹(shù)形Tree數(shù)據(jù)結(jié)構(gòu)模型的各類數(shù)據(jù)總稱，例如互聯(lián)網(wǎng)HTML文檔。半結(jié)構(gòu)化數(shù)據(jù)具有自述性、標(biāo)記性和動(dòng)態(tài)性等特征而被廣泛應(yīng)用，Internet使用半結(jié)構(gòu)化數(shù)據(jù)格式的HTML文檔描述網(wǎng)頁(yè)內(nèi)容，并使用半結(jié)構(gòu)化數(shù)據(jù)格式XML文檔和JSON文檔進(jìn)行Web信息存儲(chǔ)和信息交換，Microsoft公司使用半結(jié)構(gòu)化數(shù)據(jù)格式Open XML存儲(chǔ)Office辦公軟件docx、xlsx、pptx等文檔，Redis和MongoDB等NoSQL數(shù)據(jù)庫(kù)也使用半結(jié)構(gòu)化數(shù)據(jù)格式存儲(chǔ)Key-Value數(shù)據(jù)。

目前，半結(jié)構(gòu)化數(shù)據(jù)聚類分析方法已經(jīng)用于解決人們生產(chǎn)生活實(shí)際問(wèn)題，例如，清華大學(xué)彭宗超等[2]在2020年新冠肺炎疫情期間基于網(wǎng)絡(luò)大數(shù)據(jù)分析技術(shù)進(jìn)行新冠肺炎疫情應(yīng)急防控工作，Chitra等[3]使用XML聚類為Smarty Web搜索引擎建模等。

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

1 相關(guān)理論基礎(chǔ)

1.1 含根有序標(biāo)簽樹(shù)

半結(jié)構(gòu)化數(shù)據(jù)文件由格式標(biāo)記部分和文本內(nèi)容部分共兩個(gè)主要部分組成，可使用如文檔對(duì)象模型DOM的含根有序標(biāo)簽樹(shù)形模型表示，HTML文件的含根有序標(biāo)簽樹(shù)DOM模型如圖1所示。

樹(shù)是一種非線性結(jié)構(gòu)，是n個(gè)節(jié)點(diǎn)的有限集合，樹(shù)的一般性定義如下：

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

根據(jù)樹(shù)的不同特點(diǎn)和約束，可將樹(shù)分為含根樹(shù)和無(wú)根樹(shù)、有序樹(shù)和無(wú)序樹(shù)、標(biāo)簽樹(shù)和無(wú)標(biāo)簽樹(shù)等：

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

(2)有序樹(shù)與無(wú)序樹(shù)：若樹(shù)中任意節(jié)點(diǎn)的孩子節(jié)點(diǎn)之間有順序關(guān)系，這種樹(shù)稱為“有序樹(shù)”。若樹(shù)中任意節(jié)點(diǎn)的孩子節(jié)點(diǎn)之間沒(méi)有順序關(guān)系，則稱為“無(wú)序樹(shù)”；

(3)標(biāo)簽樹(shù)和無(wú)標(biāo)簽樹(shù)：若樹(shù)中任意節(jié)點(diǎn)都帶有一個(gè)標(biāo)簽Tag，標(biāo)簽Tag可用于區(qū)分不同的樹(shù)節(jié)點(diǎn)，則稱為“標(biāo)簽樹(shù)”。若樹(shù)中任意節(jié)點(diǎn)都沒(méi)有標(biāo)簽，即不區(qū)分樹(shù)中所有節(jié)點(diǎn)，則稱為“無(wú)標(biāo)簽樹(shù)”。

1.2 半結(jié)構(gòu)化數(shù)據(jù)聚類方法

針對(duì)海量半結(jié)構(gòu)化數(shù)據(jù)進(jìn)行數(shù)據(jù)分析的基礎(chǔ)工作是半結(jié)構(gòu)化數(shù)據(jù)集聚類算法研究。由于數(shù)據(jù)集的半結(jié)構(gòu)化特點(diǎn)，基于傳統(tǒng)結(jié)構(gòu)化數(shù)據(jù)集的聚類分析方法并不適用于半結(jié)構(gòu)化數(shù)據(jù)集[3]，所以很多研究集中在半結(jié)構(gòu)化數(shù)據(jù)集高效聚類分析方法研究，這是很多領(lǐng)域需要解決的基礎(chǔ)性研究問(wèn)題。

半結(jié)構(gòu)化數(shù)據(jù)集的聚類分析研究工作主要集中在兩個(gè)問(wèn)題的研究：第一是研究半結(jié)構(gòu)化數(shù)據(jù)特征提取和半結(jié)構(gòu)化數(shù)據(jù)間基于不同特征的相似性度量方法；第二是研究基于某種特征模式的半結(jié)構(gòu)化數(shù)據(jù)集聚類分簇方法。國(guó)內(nèi)外學(xué)者在半結(jié)構(gòu)化數(shù)據(jù)集特征提取、相似性度量和聚類算法方面已經(jīng)取得一些成果[4-6]。

在半結(jié)構(gòu)化數(shù)據(jù)集頻繁模式和特征挖掘方面，現(xiàn)有算法可分類兩大類：

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

第二類是基于模式增長(zhǎng)策略的方法，這種方法采用結(jié)果集增長(zhǎng)策略并反復(fù)迭代直至結(jié)果集是頻繁子樹(shù)完備的。國(guó)內(nèi)外學(xué)者在半結(jié)構(gòu)化數(shù)據(jù)集聚類算法方面取得一些成果[8-12]。

2 半結(jié)構(gòu)化數(shù)據(jù)集頻繁子樹(shù)模式挖掘

2.1 頻繁子樹(shù)模式挖掘策略

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

(1)

根據(jù)X-diff算法，兩個(gè)半結(jié)構(gòu)化數(shù)據(jù)之間的差異計(jì)算復(fù)雜度與樹(shù)形結(jié)構(gòu)的節(jié)點(diǎn)規(guī)模正相關(guān)。

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

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

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

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

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

2.2 構(gòu)建編碼樹(shù)

頻繁子樹(shù)挖掘FSTPMiner方法首先構(gòu)建編碼樹(shù)，編碼樹(shù)是節(jié)點(diǎn)帶有編碼鏈信息的樹(shù)形結(jié)構(gòu)數(shù)據(jù)，編碼鏈?zhǔn)且环N鏈表結(jié)構(gòu)，可以表示一顆含根有序標(biāo)簽樹(shù)。

例如，圖2中樹(shù)T1的所有節(jié)點(diǎn)采用編碼鏈結(jié)構(gòu)表示后，如圖3所示。

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

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

編碼樹(shù)是每個(gè)節(jié)點(diǎn)都帶有編碼鏈的樹(shù)形結(jié)構(gòu)，因?yàn)槊總€(gè)編碼鏈都可表示一顆無(wú)序樹(shù)，所以編碼樹(shù)可以被壓縮，即將所有孩子節(jié)點(diǎn)壓縮進(jìn)編碼鏈中。

根據(jù)定義2和定義3，將圖2中樹(shù)T1、T2、T3構(gòu)建編碼樹(shù)后如圖3所示。

2.3 剪邊與壓縮

構(gòu)建編碼樹(shù)后，進(jìn)行數(shù)據(jù)集剪邊操作和迭代壓縮操作。

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

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

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

剪邊操作后進(jìn)行壓縮操作。壓縮操作具體方法是反復(fù)迭代數(shù)據(jù)集，在每輪迭代過(guò)程中，將當(dāng)前數(shù)據(jù)集中出現(xiàn)次數(shù)最多的樹(shù)枝進(jìn)行壓縮操作，壓縮操作將樹(shù)的兩個(gè)節(jié)點(diǎn)合并成為一個(gè)點(diǎn)，同時(shí)，在這個(gè)合并后的節(jié)點(diǎn)的編碼鏈上更新壓縮后的內(nèi)容。

圖2中樹(shù)形結(jié)構(gòu)數(shù)據(jù)集T1、T2和T3經(jīng)過(guò)構(gòu)建編碼樹(shù)后，其2輪剪邊與壓縮迭代變換過(guò)程如圖4所示。

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

因?yàn)橛脩粼O(shè)定的最小頻繁度為2，所以經(jīng)過(guò)兩輪迭代剪邊與壓縮，最后得到的編碼樹(shù)就是頻繁子樹(shù)模式集，如圖4(b)所示。之后，根據(jù)編碼樹(shù)定義，將圖4(b)所示的所有編碼樹(shù)轉(zhuǎn)換為含根有序標(biāo)簽樹(shù)結(jié)構(gòu)數(shù)據(jù)，最終得到的樹(shù)形結(jié)構(gòu)數(shù)據(jù)集就是出現(xiàn)次數(shù)大于等于閾值兩次的所有頻繁子樹(shù)模式。

2.4 頻繁子樹(shù)模式挖掘方法

結(jié)合構(gòu)建編碼樹(shù)過(guò)程和剪邊壓縮過(guò)程，半結(jié)構(gòu)化數(shù)據(jù)集頻繁子樹(shù)模式挖掘過(guò)程方法FSTPMiner的偽代碼描述如下：

頻繁子樹(shù)挖掘FSTPMiner算法

輸入：半結(jié)構(gòu)化樹(shù)形結(jié)構(gòu)數(shù)據(jù)集D={T1,T2,…,Tn}， 頻繁度閾值e。

輸出：頻繁子樹(shù)模式集F

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

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

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

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

(5) IF EFrq(x,y)

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

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

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

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

(10) FOR 每個(gè)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項(xiàng)集對(duì)應(yīng)的子樹(shù); //將頻繁子樹(shù)放入結(jié)果集F;

3 相似度計(jì)算和聚類

本文聚類過(guò)程將每個(gè)半結(jié)構(gòu)化數(shù)據(jù)使用其包含的頻繁子樹(shù)作為特征，并組成相應(yīng)的特征向量。然后使用余弦定理計(jì)算特征向量間的相似程度。最后的半結(jié)構(gòu)化數(shù)據(jù)集聚類過(guò)程采用經(jīng)典凝聚型層次聚類方法。

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

(2)

最后，使用凝聚性層次聚類方法并根據(jù)半結(jié)構(gòu)化文檔數(shù)據(jù)集的特征向量進(jìn)行聚類，過(guò)程如下：

基于頻繁子樹(shù)模式的半結(jié)構(gòu)化數(shù)據(jù)聚類算法

輸入：半結(jié)構(gòu)化文檔數(shù)據(jù)集D，最小頻繁度e，層次聚類停止簇?cái)?shù)閾值k

輸出：聚類結(jié)果

(1) 計(jì)算半結(jié)構(gòu)化文檔數(shù)據(jù)集D的頻繁子樹(shù)模式集FP=FSTPMiner(D);

(2) 對(duì)數(shù)據(jù)集D中每個(gè)半結(jié)構(gòu)化文檔構(gòu)建特征向量

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

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

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

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

(6) IF 簇?cái)?shù)量>kTHEN 執(zhí)行步驟(4)

ELSE return 簇信息;

4 實(shí)驗(yàn)結(jié)果與分析

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

本文相關(guān)實(shí)驗(yàn)均在主頻為2.83 GHz 4 Core CPU、8 GB DDR4 2666MHz RAM的計(jì)算機(jī)上運(yùn)行，操作系統(tǒng)為Fedora Core 6。

本文算法和其它相關(guān)對(duì)照算法均使用C++語(yǔ)言編寫(xiě)實(shí)現(xiàn)，在代碼中使用C++ STL標(biāo)準(zhǔn)庫(kù)容器和函數(shù)。解析XML文檔DOM數(shù)據(jù)并處理樹(shù)形結(jié)構(gòu)數(shù)據(jù)使用TinyXML第三方開(kāi)源庫(kù)。

實(shí)驗(yàn)使用半結(jié)構(gòu)化XML文檔數(shù)據(jù)集，包括真實(shí)半結(jié)構(gòu)化文檔數(shù)據(jù)集和人工半結(jié)構(gòu)化文檔數(shù)據(jù)集。真實(shí)半結(jié)構(gòu)化數(shù)據(jù)集來(lái)自ACM提供的SIGMOD標(biāo)準(zhǔn)XML文檔聚類數(shù)據(jù)集和美國(guó)航空航天局NASA提供的航天飛機(jī)組播數(shù)據(jù)抽樣半結(jié)構(gòu)化數(shù)據(jù)集。人工數(shù)據(jù)集使用IBM XMLGenerator工具生成，共使用10個(gè)DTD文件，然后根據(jù)每個(gè)DTD文件隨機(jī)生成100篇XML文檔，因此人工數(shù)據(jù)集中共包含XML文檔1000(10×100) 篇。

4.2 實(shí)驗(yàn)過(guò)程

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

第一階段，基于人工生成的半結(jié)構(gòu)化數(shù)據(jù)集，使用本文提出的半結(jié)構(gòu)化數(shù)據(jù)聚類算法與劉昕等提出的基于局部密度的快速文本聚類算法[14]進(jìn)行對(duì)照分析。該階段實(shí)驗(yàn)?zāi)康氖球?yàn)證普通文本聚類方法在半結(jié)構(gòu)化文檔數(shù)據(jù)集環(huán)境中的適用程度；

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

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

4.3 文本聚類算法對(duì)照實(shí)驗(yàn)

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

聚類結(jié)果主要指標(biāo)數(shù)據(jù)見(jiàn)表1。

表1 本文方法與文本聚類方法對(duì)照結(jié)果

4.4 人工半結(jié)構(gòu)化數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

分別使用基于FSTPMiner算法、Costa算法、ICQB算法和Damalagas算法對(duì)人工生成的半結(jié)構(gòu)化XML數(shù)據(jù)集進(jìn)行聚類，聚類結(jié)果正確率、召回率和聚類過(guò)程時(shí)間值見(jiàn)表2。

表2 人工數(shù)據(jù)集聚類結(jié)果

4.5 真實(shí)半結(jié)構(gòu)化數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

對(duì)于ACM SIGMOD真實(shí)數(shù)據(jù)集和NASA真實(shí)數(shù)據(jù)集，分別使用本文基于FSTPMiner算法、Costa算法、ICQB算法和Damalagas算法進(jìn)行半結(jié)構(gòu)化XML文檔數(shù)據(jù)集進(jìn)行聚類，聚類結(jié)果正確率和召回率見(jiàn)表3。

表3 真實(shí)數(shù)據(jù)集聚類結(jié)果

對(duì)于相同數(shù)據(jù)規(guī)模的半結(jié)構(gòu)化數(shù)據(jù)集，使用聚類過(guò)程消耗的時(shí)間來(lái)衡量各個(gè)算法的聚類效率。在真實(shí)數(shù)據(jù)集對(duì)照實(shí)驗(yàn)中，本文基于FSTPMiner的算法、Costa提出的算法、ICQB算法和Damalagas提出的算法的運(yùn)行時(shí)間見(jiàn)表4。

表4 真實(shí)數(shù)據(jù)集聚類時(shí)間

4.6 實(shí)驗(yàn)結(jié)果分析

基于人工生成的半結(jié)構(gòu)化數(shù)據(jù)集，經(jīng)過(guò)本文針對(duì)半結(jié)構(gòu)化樹(shù)形結(jié)構(gòu)數(shù)據(jù)聚類算法和普通文本聚類算法對(duì)照實(shí)驗(yàn)結(jié)果，可以得到以下結(jié)論：

(1)本文針對(duì)半結(jié)構(gòu)化數(shù)據(jù)樹(shù)形結(jié)構(gòu)特點(diǎn)設(shè)計(jì)的聚類算法，其聚類效果要優(yōu)于普通文本聚類算法，在實(shí)驗(yàn)中，聚類結(jié)果的正確率提高25.3%，召回率提高20.5%；

(2)半結(jié)構(gòu)化數(shù)據(jù)聚類算法的聚類過(guò)程時(shí)間占用和內(nèi)存空間占用要大于普通文本聚類算法，原因在于樹(shù)形結(jié)構(gòu)模型的解析和存儲(chǔ)均大于文本線性模型。

對(duì)于各種半結(jié)構(gòu)化數(shù)據(jù)集聚類算法，經(jīng)過(guò)在真實(shí)半結(jié)構(gòu)化數(shù)據(jù)集和人工生成半結(jié)構(gòu)化數(shù)據(jù)集的各聚類算法對(duì)照實(shí)驗(yàn)運(yùn)行結(jié)果，可得出以下基本結(jié)論：

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

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

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

5 結(jié)束語(yǔ)

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

下一步可以研究結(jié)合半結(jié)構(gòu)化數(shù)據(jù)子結(jié)構(gòu)和子內(nèi)容的頻繁子模式挖掘和聚類工作，也可以研究基于頻繁子樹(shù)模式的半結(jié)構(gòu)化數(shù)據(jù)分類問(wèn)題。