基于ＴｒｅｅＭｉｎｅｒ算法的ＸＭＬ文檔結構相似度量方法
2009-01-01 00:00:00閻紅燦王淑芬朱曉亮李敏強劉保相
計算機應用研究 2009年5期
（1.天津大學 管理學院 天津 300072； 2.河北理工大學 a.理學院; b.計算中心 河北 唐山 063009）
摘 要：提出了一種基于TreeMiner算法挖掘頻繁子樹的文檔結構相似度量方法，解決了傳統的距離編輯法計算代價高而路徑匹配法無法處理重復標簽的問題。該方法架構了一個新的檢索模型—頻繁結構向量模型，給出了文檔的結構向量表示和權重函數，構造了XML文檔結構相似度量計算公式；同時從數據結構和挖掘程序上對TreeMiner 算法進行了改進，使其更適合大文檔數據集的結構挖掘。實驗結果表明，該方法具有很高的計算精度和準確率。
關鍵詞：頻繁結構向量模型； 嵌入子樹； 頻繁子樹； 結構挖掘
中圖分類號：TP311文獻標志碼：A
文章編號：1001-3695(2009)05-1706-04
Method of similarity measures for XML documents structure
based on TreeMiner algorithm
YAN Hongcan1，2a WANG Shufen2b ZHU Xiaoliang2b LI Minqiang1 LIU Baoxiang2a
（1.School of Management Tianjin University Tianjin 300072 China； 2. a.College of Sciences b.Computing Center Hebei Polytechnic University Tangshan Hebei 063009 China）
Abstract:This paper proposed a novel way of similarity measures for XML documents structure based on TreeMiner algorithm and resolved the high costs in distance editing and the problems of repetiition of labels in path matching designed. In this way a new research model:frequent structure vector model (FSVM) derived the expression of document structure vector and weight function and constructed the calculate formula to measure similarity of the two documents. In order to improve the efficiency of mining frequency subtrees in a forest reformed the algorithm TreeMiner from data structure and miner procedure to fit to minning structure in large documents.The testing results show that this method acquires very high precision and veracity.
Key words：frequent structure vector model; embedded subtree; frequency subtree; structure miner
0 引言
由于具有結構化、可擴展性、跨平臺性等特點，越來越多的數據標準采用XML，如MathML、NewsML、OWL、LOGML、ebXML、cnXML等。XML成為信息存儲與交換的主要形式，繼而從XML文檔結構中獲取所需的模式成為XML應用領域的研究熱點，如對XML文檔結構挖掘可以為生物信息學、網絡日志分析、Web結構分析和分類等提供重要知識。其中XML文檔的結構相似度量是XML結構分析的基礎核心問題。已有的XML文檔結構相似性度量主要包括距離編輯法[1~3]、路徑匹配法[4]和時序分析法[5]，基本上都將XML文檔視為一棵標記樹，編輯距離的思想是將一個文檔轉換為另一個文檔所需操作（更名、刪除、插入）的最小代價作為度量標準，通過圖匹配算法計算相似性。當文檔很大時，計算代價太高；而路徑匹配法基于邊匹配，采用Jaccard系數來度量，但度量相似性的精度不高；時序分析法將XML文檔結構表示為一個時間序列，每個標簽的出現相應于一個脈沖，通過相應傅里葉變換來計算文檔間的相似性，但是這種方法無法排除標簽的多次重復出現對計算結構相似度的影響。
文獻[6，7]提出了一種高效挖掘頻繁子樹的迭代算法TreeMiner，能夠在用戶給定的最小支持度閾值內找出所有的頻繁子樹；文獻[8]給出了一種挖掘無序頻繁子樹的高效算法。本文在此算法基礎上結合文本分類的向量空間模型（vector space model）提出了XML文檔頻繁結構向量模型，通過頻繁結構單元在文檔中出現的頻度和權重定義了文檔結構相似度，同時對TreeMiner算法在兩個方面進行了改進：a)頻繁節點的數據結構增加了層次信息編碼，有利于范圍列表連接時快速判斷其祖先—后代關系，只有(y)中節點是(x)節點的后代節點時才有可能進行內聯和外聯的測試，這樣排除了大量冗余運算，提高了算法性能；b)本著“先預算支持度，后進行類擴展”的思想，將類擴展的節點連接和頻繁子樹支持度的范圍列表連接運算順序重新作了調整，這樣對不存在的子樹或者不頻繁的子樹不再進行類擴展運算，大大提高了挖掘效率。
實驗表明，TreeMiner+算法在時間復雜性上優于TreeMiner算法，特別是隨著支持度的增加性能優勢明顯提高，更適用于大文檔數據集。頻繁結構向量模型在度量XML文檔結構相似性方面具有很高的精確性，并且計算代價更小。
1 頻繁結構向量模型
文獻[9，10]均采用了向量空間模型來表示XML文檔，特別是文獻[9]提出結構鏈接向量模型，將XML文檔中的每個結構單元看做是一個向量，類似于VSM模型的一個文檔，但沒有就如何選擇結構單元給出具體方法，只簡單將每個節點作為基本結構單元，不能完備表示XML文檔結構信息。本文將給出頻繁結構向量模型FSVM的表示及XML文檔結構相似性度量方法，并對結構向量空間中的結構單元—頻繁子樹的挖掘給出高效算法。
1.1 頻繁子樹的相關概念
將每個XML文檔看做一棵帶有標簽的有序樹T=(r，V，B，L)。其中：r表示根節點；V表示樹中節點集合；B表示邊的集合；L表示所有節點標簽的集合。那么XML文檔集合D（又稱數據庫）視為有序樹的集合，D={t0，t1，t2，…}，稱為文檔森林，每棵樹有惟一的標志tid tid∈{0，1，2，…}，分別表示樹t0，t1，t2，…。
定義1 有序樹(ordered tree)。XML文檔有序樹T=(r，V，B，L)中 V＝{n0，n1，n2，…，n｜T｜-1}，nid∈{0，1，2，…}，按照深度優先根序列編號，｜T｜表示樹T的大小，即節點個數。節點不區分元素和屬性，均采用圓圈表示，每個節點的標簽用集合L={1，2，3，…，m}表示，不同的節點可以有相同的標簽。每個邊b=〈x，y〉∈B，是一個有序節點對。其中x是y的父節點。圖1即為一棵有序樹。圖中r=n0，V={n0，n1，n2，n3，n4，n5，n6}，B={〈n0，n1〉，〈n1，n2〉，〈n2，n3〉，〈n2，n4〉，〈n1，n5〉，〈n0，n6〉}，L={1，2，3，4}。
定義2 樹的拓撲編碼表示（topology encoding）。按照先根深度優先遍歷樹中所有節點的標簽序列稱為樹的拓撲編碼表示，用-1表示從一個節點回溯到父節點的序列，圖1所示有序樹的拓撲編碼為“1131121141121”。
定義3 三元組編碼（triple encoding）。有序樹中每個節點采用三元組（tid，scope，high）編碼。其中：tid∈D；scope為節點的轄區范圍，定義為[l，u]區間形式 l為拓撲編碼中本節點編號，u為右子樹最后節點的nid；high表示每個節點在樹中的層次。圖1是樹T中節點編碼的實例，如根節點n0的nid值為0，右子樹最后節點的nid值為6，所以scope為s=[0，6]，根節點的high=0，其三元組編碼為(tid，[0，6]，0)。
定義4 嵌入子樹（embedded subtree）。樹S=(rs，Vs，Bs，Ls)和T=（rt，Vt，St，Lt），如果同時滿足以下條件：a)LsLt；b)對于任意邊b=(x，y)∈Bs，在T中當且僅當x是y的祖先，即存在從x到y的路徑，稱為分支。稱S為T的嵌入子樹，用S≤T表示。圖2中，S1、S2均為樹T的嵌入子樹。這里需要強調的是在樹T中x不一定是y的父節點，只要是祖先節點即可，這是與傳統子樹定義的區別，正是這一點，保證了在大型文檔樹中挖掘頻繁子樹的完備性。
定義5 子樹的支持度（support of subtree）。嵌入子樹S在樹T中出現的次數，稱為樹T對子樹S的支持度，以δT(S1)表示，如δT(S1)＝4，δT(S2)＝1。
數據庫D對子樹S的支持度定義為
定義6 頻繁子樹（frequent subtree）。如果數據庫D對嵌入子樹S的支持度π(D，S)大于或等于用戶給定的最小閾值minsup，則稱子樹S為頻繁子樹。
π(D，S)=∑T∈DdT(S)/｜D｜
dT(S)=1 當δT(S)＞00 當δT(S)=0
其中：｜D｜表示數據庫中有序樹的總數。
定義7 匹配標簽（match labels）。頻繁子樹S中所有節點對應樹T相應節點的標簽序列稱為S的匹配標簽。更一般的定義：設D為文檔集合對應的森林，{n1，n2，…，nn}是T中的節點，T∈D，{s1，s2，…，sm}是T的頻繁子樹S的節點集合，則S的匹配標簽為（ni1，ni2，…，nim）。其中：
L(Sk)=L(nik)，k=1，2，…，m；對于S中每個邊(Sj，Sk)，對應樹T中的分支（nij，nik）。如圖2中S1和S2的match labels。
1.2 XML文檔的結構向量表示
向量空間模型以特征詞構造一個高維空間，每個詞語為該空間的一個維，文檔被看做是這個空間的一個向量，dx=(dw1，dw2，…，dwn)T。其中n是文檔集合中不同詞語的個數。TFIDF（term frequency inverse document frequency）是向量空間模型中一種常用的文檔向量化方法，它綜合考慮了詞語在單個文檔中出現的頻度和該詞語在文檔集合中出現的頻度。 dwi=TF(wi，dx)×IDF(wi)。其中：TF(wi，dx)是詞wi在文檔dx中出現的次數；IDF(wi)=log(｜D｜/｜DF(wi))，｜D｜是文檔集合中文檔總數，DF(wi)是包含詞語wi的文檔個數；IDF(wi)是詞語wi的全局特性，用來體現詞語wi區分文檔的能力。
向量空間模型能夠有效描述文檔內容，但不能體現文檔的結構信息，而XML文檔中含有豐富的結構信息，這些信息就蘊藏在文檔樹的頻繁子集中。基于此，筆者對傳統向量空間模型進行了演變，以文檔集的所有頻繁子樹構造一個結構特征空間，每個頻繁子樹為該空間的一個維，文檔（樹）dt被看做是這個結構空間的一個向量，dt=(ds1，ds2，…，dsn)T。其中：si是文檔集合中不同的頻繁子樹；dsi表示頻繁結構si在文檔樹dt中的權重，dsi=TF(si，dt)×IDF(si)。其中：TF(si，dt)=δt(si)×B(si)，B(si)為頻繁子樹si的邊數；IDF(si)是結構si的全局特性，數值越小，說明該結構在文檔樹集合中的區分能力越強，定義為log(｜D｜/｜DF(si)) DF(si)是含有子樹si結構的樹的個數，為了使每個頻繁結構有作用，修訂為log(｜D｜/｜DF(si)+0.5)。這樣得到每個頻繁子樹的權重函數為
dsi=δt(si)×B(si)×log(｜D｜/｜DF(si)+0.5)（1）
1.3 文檔相似性度量
與VSM模型類似，在FSVM模型中，同樣采用頻繁結構向量夾角的余弦來度量文檔結構的相似性：
sim(Tx，Ty)=cos(TX，Ty)=
∑ni=1(dx(si)×dy(si)）/∑ni=1dx2(si)×∑ni=1dy2(si)(2)
其中：Tx、Ty表示兩個文檔樹；dx(si)和dy(si)分別表示頻繁結構si在文檔樹Tx、Ty中的權重。從式（2）可以看出，計算未知文檔與已知文檔集合中某個文檔的相似度問題可歸結為以下步驟：
a)在文檔集合中挖掘所有頻繁子樹；
b)對拓撲編碼表示的頻繁子樹排序，應用式（1）計算權重，構造結構特征空間；
c)計算未知文檔在結構特征空間的向量表示；
d)應用式（2）計算文檔結構相似性。
未知文檔與某個文檔的相似度越大，按結構分類分在同一類的可能性越大；反之可能性越小。這里的關鍵是a)b)。下面解決如何挖掘頻繁子樹問題。
2 頻繁子樹的挖掘算法TreeMiner+
挖掘頻繁子樹的算法是基于最右擴展遞增模式的，基本思路是：首先獲得1subtrees，即含有一個節點的子樹，通過計算每個標簽的支持度，選出候選頻繁節點；然后通過共享前綴的類節點右擴展生成2subtrees，通過類節點的范圍列表連接計算子樹支持度從而選擇候選類，為下一層的類擴展作數據輸入。依次遞歸由k頻繁子樹生成（k+1）頻繁子樹，直至產生所有頻繁子樹。
2.1 頻繁子樹擴展的相關技術及算法
由k頻繁子樹生成(k+1)頻繁子樹時，首先需要確定擴展類，即候選擴展節點集合。假定P指向k頻繁子樹前k-1個節點的前綴編碼(prefix)，以[P]k表示其類節點集合。其中每個元素形如（x，i）形式，x表示擴展節點的標簽，i表示擴展節點的擴展位置。
性質1 類擴展（class extension）。（x，i）和（y，j）為[P]k類集合中的任意兩個節點元素，Px表示（x，i）的擴展類，兩個節點的連接運算定義為xy，運算具有以下性質：
a)當i=j時，如果前綴P不為空，在[Px]中添加節點(y，j)和(y，j+1)，如果為空，只添加(y，j+1)；
b）當i＞j時，在[Px]中添加節點(y，j)；
c）當i＜j時，不作任何操作。
性質2 范圍列表連接(scopelist join)。[Px]類集合中每個元素都有自己的范圍列表，以(x)表示，集合中每個元素以三元組編碼，范圍列表的連接運算定義為(x)∩ (y)，具有以下性質：
a）如果ty=tx=tid，則兩個節點x、y是在同一文檔樹T中；
b）如果high(x)≥high(y)，則在樹T中x不是y的祖先節點；
c）如果lx≤ly且ux≥uy，即scope(y)，scope(x)，說明在樹T中y是x的后代節點，此時進行內部連接（inscope link）。在[Px]類擴展節點的范圍列表中添加節點（ty，{matchlabels lx}，scope(y)）（此時范圍列表與頻繁節點的范圍列表有些區別，沒有了層次信息，添加了匹配標簽）。
d）如果ux≤ly 即scope(y)＜scope(x)，說明在樹T中y是x的兄弟節點，此時進行外部連接(outscope link)。在[Px]類擴展節點的范圍列表中添加節點（ty，{match labels lx} ，scope(y)）。
改進的TreeMiner算法
TreeMiner+(D minsup)
Input: triple code set D of document trees minimum support of frequent subtree
Output: prefix encoding of all frequent subtrees S and δT(S)
compute support of each label choose frequent labeled nodes F1;
built candidate class extension set P0={(F1，-1)};
prefix[P0]={};encoding[P0，k]= (F1，-1);
for each element of [P0] do Enumerate-subtrees([P0]);
Enumerate-subtrees([P])
{ For each element (x，i)∈[P] do
{ [Px]=;
for each element (y，j)∈P do
if high(x)>high(y) then
{(S)=(x)∩ (y);
if S is frequent then
{ R=（x，i）(y，j)
[Px]= [Px]∪ {R};
k+=1;
build prefix[Px] and encoding[Px，k];
}
}
enumerate-subtrees([Px]);
}
}
2.2 TreeMiner+算法處理實例
圖3所示數據庫D有三個文檔，minsup=70%，挖掘頻繁子樹過程如下：
a)通過掃描數據庫（遍歷文檔樹）得到每個節點的三元編碼，具有相同標簽的節點構成鄰接表，稱為范圍列表（scopelist），采用圖3(b)的數據結構進行存儲，L={1，2，3，4，5}。通過范圍列表很容易計算出節點標簽1、2、3、4 的支持度均為100％，為頻繁節點，標簽5節點的支持度只有1/3，不是頻繁節點（對應算法的1~3行）。
b)遞歸調用enumeratesubtrees()過程，由ksubtrees構造(k+1)subtrees。以2subtrees為例，P0中四個節點任意兩個節點都有可能進行連接，構成含有兩個節點的子樹，所以算法中（第6、8行）對任意兩對元素都要枚舉，包括自身之間。但并不是任意兩個元素都能構成子樹，如（1，-1）和（4，-1）可以構成2subtrees；反之則不能構成2subtrees，因為標簽1是4的祖先節點。為了減少范圍列表的連接次數，算法通過節點的層次關系直接判斷出子樹的可能性（第9行），只有可能構成子樹的節點才進行連接，排除了冗余計算；同時對構成的子樹只有頻繁子樹才是所需結構，所以當11行條件滿足時才進行類擴展，通過這兩個條件的限制，大大減少了算法的時間開銷。見圖4中的2subtrees構造過程。
c)對每個頻繁子樹處理并存儲其前綴編碼prefix和拓撲編碼 encoding（第14、15行）。圖4給出了數據庫D的全部頻繁子樹的挖掘過程。按照節點數和支持度大小順序依次為
S1:12-134-1-1，S2:12-14-1，S3:12-13-1，S4:134-1-1，S5:12-1，S6:14-1，S7:13-1，S8:34-1
3 文檔結構的相似度計算處理實例
假定圖3數據庫D為已知文檔集合，圖1為未知文檔樹，頻繁子樹的頻度δt(si)如表1所示。
根據式(1)計算每個頻繁結構的權重如表2所示。
根據式(2)計算任意兩個文檔之間的相似度為
sim(t0，t1)= 0.322 521sim(t0，t2)= 0.985 432，
sim(t1，t2)= 0.328 011 sim(t，t0)= 0.549 918
sim(t，t1)= 0.446 359，sim(t，t2)= 0.574 932
數據結果表明，基于頻繁結構向量模型的XML文檔相似度量方法有很高的計算精度。下面的實驗通過大量數據集也證明了這一點。
表2 頻繁子樹在FSVM中的向量表示
權重S1S2S3S4S5S6S7S8
t00.903 10.352 20.602 10.602 10.176 10.176 10.176 10.176 1
t10.000 00.352 20.000 00.000 00.176 10.176 10.000 00.000 0
t22.709 31.056 51.806 21.204 10.528 30.352 20.528 30.176 1
t0.000 00.352 21.204 10.000 00.528 30.352 20.352 20.000 0
4 實驗
4.1 數據集與實驗設計
實驗使用AMD雙核Athlon 4000+ 2.10 GHz CPU，1 GM內存的個人計算機，所用操作系統為Windows 2000 server，所有算法均使用Java語言實現，所用JDK為Java 2 Platform Standard Edition 5.0標準版。
實驗數據采用ACMSIGMOD[11]數據集中的OrdinaryIssuePage 和IndexTermsPageXML文件，數據子集使用情況見表3。1999年的OrdinaryIssuePage和2002年的OrdinaryIssuePage文檔結構十分相近，文檔數量中的第一個數字作為頻繁子樹挖掘訓練使用，后一個數字作為相似度量測試使用。同一類中測試文檔與訓練文檔的相似度大于99％，認為結構相同。對三個數據集內部和相互之間分別作測試，ACMSIGMOD1和ACMSIGMOD2的結構相似度人工標定為0.85以上，IndexTermsPage和OrdinaryIssuePage文檔相似度人工標注為0.3，如果測試結果在此范圍內，說明測試準確，實驗結果的準確率（precision）采用式(3)進行評價。
P=(相似度準確的文檔數)/(測試文檔總數) （3）
表3 實驗中使用的數據子集
datasetssourcestotal num of
ACMSIGMOD1OrdinaryIssuePage(1999)40+10
ACMSIGMOD2OrdinaryIssuePage(2002)20+10
ACMSIGMOD3IndexTermsPage(1999)40+20
實驗訓練階段，每個子數據集內部頻繁子樹挖掘時最小支持度minsup取值范圍1~0.5，結果如圖5所示；三個數據子集合并為一個數據庫進行挖掘時，minsup取0.7~0.1，并與TreeMiner算法進行了性能比較，結果如圖6所示。
4.2 實驗結果分析
圖5顯示了不同的數據集在不同支持度下文檔相似度計算的準確度。實驗表明，基于頻繁結構向量模型的XML文檔結構相似度量方法準確性很高，基本可以達到96%以上，而且頻繁子樹的最小支持度越低，頻繁結構越多，計算精度越準確。一般情況下，minsup閾值為0.7即可達到要求。圖5中三個數據集分別測試準確率較高，三個數據集混合測試準確率偏低的原因是數據結構偏差較大，此時需降低最小支持度minsup，以求得高準確率。
圖6顯示了改進的TreeMiner+算法和TreeMiner算法在挖掘頻繁子樹的時間開銷。圖示表明，支持度越高，優勢越明顯，在minsup閾值為0.7以上時，性能可以提高近三倍；特別是訓練文檔越多，優勢更為明顯.
