(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,中國(guó) 長(zhǎng)沙　410081)

?

XML文檔的聚類研究尹路修

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,中國(guó) 長(zhǎng)沙410081)

摘要隨著互聯(lián)網(wǎng)的迅速發(fā)展，XML已經(jīng)成為互聯(lián)網(wǎng)中最常用的數(shù)據(jù)交換與存儲(chǔ)語(yǔ)言，如何從大量的XML文檔中提取有價(jià)值的信息是目前的研究熱點(diǎn)之一．本文提出了一種基于SET/BAG模型的改進(jìn)的相似度計(jì)算方法．該方法將XML文檔的每個(gè)節(jié)點(diǎn)轉(zhuǎn)換成一個(gè)對(duì)象(由對(duì)象名、父對(duì)象、屬性集合以及該對(duì)象相對(duì)于其父對(duì)象的權(quán)重組成)，能較完整地表達(dá)XML文檔的結(jié)構(gòu)信息，并且通過(guò)調(diào)整重復(fù)節(jié)點(diǎn)的權(quán)重來(lái)降低其在相似度計(jì)算中的影響．在真實(shí)數(shù)據(jù)集與人工數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)，仿真實(shí)驗(yàn)結(jié)果表明，本文提出的基于SET/BAG模型下改進(jìn)的相似度計(jì)算方法能得到很好的聚類結(jié)果．

關(guān)鍵詞XML；文檔聚類；相似度計(jì)算

在研究如何從大量的XML文檔中提取有價(jià)值的信息時(shí)，關(guān)于XML文檔的聚類[1]研究顯得非常重要．通過(guò)XML文檔的聚類，可以將大量的XML文檔在未知類別的情況下進(jìn)行分類整理，使用戶可以用更短的時(shí)間獲得更為完整和有用的信息．XML文檔聚類研究主要有兩大研究方向．一種是對(duì)聚類算法進(jìn)行改進(jìn)，使之能更好地結(jié)合XML文檔的特點(diǎn)以及更好的聚類結(jié)果．目前主要的聚類算法[2-3]有基于劃分的，基于層次的和基于密度的．另一種是對(duì)XML文檔的表示模型進(jìn)行改進(jìn)，以便得到更有效率的相似度計(jì)算方法．目前主要的XML文檔的表示模型[4-7]有3種，分別是SET/BAG模型，向量空間模型和樹(shù)模型．本文著重對(duì)SET/BAG模型的相似度計(jì)算方法進(jìn)行改進(jìn)，提出一種基于SET/BAG模型改進(jìn)的相似度計(jì)算方法．

1SET/BAG模型相似度計(jì)算

SET/BAG模型[8]是將XML文檔用集合的形式來(lái)表示，通過(guò)Jaccard相似系數(shù)計(jì)算公式得到兩個(gè)文檔的相似度．設(shè)有2個(gè)XML文檔集合，x1,x2，Jaccard相似系數(shù)計(jì)算公式：

(1)

基于SET/BAG模型的相似系數(shù)計(jì)算公式，再結(jié)合XML文檔的自身特點(diǎn)，有以下幾種相似度計(jì)算方法:

(1)節(jié)點(diǎn)比較法.節(jié)點(diǎn)比較法是將一個(gè)XML文檔中的所有節(jié)點(diǎn)組合成一個(gè)集合，這個(gè)集合代表這個(gè)XML文檔．相似度計(jì)算是使用Jaccard相似系數(shù)計(jì)算公式得到相似度．節(jié)點(diǎn)比較法只是簡(jiǎn)單地提取了XML文檔中的節(jié)點(diǎn)，忽略了XML文檔的結(jié)構(gòu)信息，如XML文檔結(jié)構(gòu)中的父子關(guān)系，同時(shí)嵌套節(jié)點(diǎn)與重復(fù)節(jié)點(diǎn)帶來(lái)的相似度計(jì)算的影響也并未得到解決．并且XML文檔中層級(jí)越高的節(jié)點(diǎn)概括的信息量越大，層級(jí)越低的節(jié)點(diǎn)概括的信息量越小，但是在節(jié)點(diǎn)比較法中并未得到表現(xiàn)．

(2)邊集比較法.邊集比較法與節(jié)點(diǎn)比較法類似，只是集合中的節(jié)點(diǎn)不是XML文檔里的元素，而是用表示父子關(guān)系的有向邊．相似度計(jì)算方式與節(jié)點(diǎn)比較法一樣，也是計(jì)算兩個(gè)集合之間的交集除以兩個(gè)集合之間的并集．邊集比較法在一定程度上保存了XML文檔中的父子關(guān)系，但和節(jié)點(diǎn)比較法一樣也未能解決嵌套元素與重復(fù)元素的影響．

2基于SET/BAG模型改進(jìn)的相似度計(jì)算

2.1基于SET/BAG模型改進(jìn)的相似度計(jì)算

2.1.1XML文檔的數(shù)據(jù)預(yù)處理XML文檔中的一個(gè)對(duì)象由一個(gè)四元組表達(dá)，即，O={Name，Parent，AttributeList，Weight}，其中Name:該對(duì)象的名字，Parent:該對(duì)象的父對(duì)象，AttrubuteList:該對(duì)象的屬性集合，Weight:權(quán)重，是該對(duì)象相對(duì)于其父對(duì)象的重要度，如圖1所示．在進(jìn)行對(duì)象集合相似度計(jì)算之前，需要遍歷XML文檔中的每個(gè)節(jié)點(diǎn)并將其轉(zhuǎn)換成一個(gè)對(duì)象．于是，計(jì)算兩個(gè)XML文檔的相似度時(shí)，即對(duì)這個(gè)XML文檔的對(duì)象集合進(jìn)行比較．

圖1　XML文檔示例Fig.1　XML document sample

名稱父對(duì)象屬性權(quán)重booknulltitle;publisher;year;author;price1titlebooknull0.2publisherbooknull0.2yearbooknull0.2authorbookfirstname;lastname0.2pricebooknull0.2firstnameauthornull0.5lastnameauthornull0.5

2.1.2節(jié)點(diǎn)對(duì)象的相似度計(jì)算在將數(shù)據(jù)處理成對(duì)象集合之后，需要進(jìn)行對(duì)象的相似度計(jì)算．對(duì)象的相似度取決于對(duì)象名和對(duì)象的屬性集合．兩個(gè)XML文檔的相似度等于兩個(gè)XML文檔的頂層對(duì)象的相似度．

設(shè)有對(duì)象P1和P2，P1的屬性集合為{a11,a12，…，a1m}，P2的屬性集合為{a21,a22,…,a2n}，對(duì)象的相似度計(jì)算公式：

(2)

基于SET/BAG模型改進(jìn)的相似度計(jì)算算法采用遞歸的方式從頂層對(duì)象(樹(shù)模型里的根節(jié)點(diǎn))開(kāi)始計(jì)算，通過(guò)動(dòng)態(tài)規(guī)劃算法的思想，分別求解出兩個(gè)頂層對(duì)象下屬性集合的相似度，然后將每個(gè)屬性與各自對(duì)于頂層對(duì)象的權(quán)重相乘再累加除以2得到兩個(gè)頂層對(duì)象的相似度，也就是XML文檔的相似度，有兩種情況：

(1)如果對(duì)象的屬性集合為空，則比較對(duì)象名是否一樣.當(dāng)屬性名一樣時(shí)，判定兩個(gè)屬性的語(yǔ)義是否相同，若相同，則similaryValue=1，否則similaryValue=0．

(2)如果對(duì)象屬性集合不為空，先比較對(duì)象名，如果相同，則比較其屬性集合．先將兩個(gè)對(duì)象的所有屬性進(jìn)行兩兩比較，然后分別查找出相似度最大的值作為這兩個(gè)屬性的相似度，若沒(méi)有匹配上的屬性， similaryValue=0．

基于SET/BAG模型改進(jìn)的相似度計(jì)算算法描述如下：

函數(shù)：compareObject

輸入：O1，O2;// 頂層對(duì)象O1，頂層對(duì)象O2

輸出：similaryValue；//兩個(gè)對(duì)象集合的相似度值

方法:

(1)比較頂層對(duì)象名是否相同，如果相同，則跳入(2)；

(2)比較兩個(gè)對(duì)象的屬性集合，

If(其中一個(gè)對(duì)象的屬性集合為空，而另一個(gè)對(duì)象的屬性集合不為空){

similaryValue = 0;

返回 similaryValue;

}else if (兩個(gè)對(duì)象的屬性集合都為空){

If(o1.name == o2.name){

similaryValue = 1;

}else{

similaryValue = 0;

}

返回similaryValue;

}else{

Repeat

//將兩個(gè)對(duì)象的屬性集合進(jìn)行兩兩對(duì)比，跳入(1);

//將相似度最大的兩個(gè)屬性劃分為一組，得到的相似度結(jié)果為這兩個(gè)屬性的相似度;

Until

//所有屬性比較完畢

//跳入(3)

}

(3)分別乘以這個(gè)屬性在該對(duì)象的權(quán)重，得到最終帶權(quán)重的相似度，代入公式(1)中，得到兩個(gè)頂層對(duì)象的相似度．

基于SET/BAG模型改進(jìn)后的相似度計(jì)算方法結(jié)合了語(yǔ)義相似度的比較，并未通過(guò)語(yǔ)義詞典來(lái)得到兩個(gè)屬性的語(yǔ)義相似度．由于目前的語(yǔ)義詞典如WordNet存在一些不足的地方如合并詞匯與縮寫(xiě)詞匯不能計(jì)算相似度，例如圖3.1中firstname是由first和name合并的，但是在語(yǔ)義詞典里面不能被識(shí)別．還有語(yǔ)義詞典中的詞匯不完善，簡(jiǎn)寫(xiě)詞匯和專業(yè)術(shù)語(yǔ)的單詞如VSM是Vector Space Model的簡(jiǎn)寫(xiě)，但是在語(yǔ)義詞典中也不能被識(shí)別．因此，改進(jìn)后的相似度計(jì)算方法并未采用語(yǔ)義詞典進(jìn)行相似度的計(jì)算．

在嵌套節(jié)點(diǎn)與重復(fù)節(jié)點(diǎn)的處理方面，由于基于SET/BAG模型改進(jìn)后的相似度計(jì)算方法將節(jié)點(diǎn)轉(zhuǎn)換成對(duì)象處理，而對(duì)象包含了名稱與屬性，所以對(duì)于嵌套節(jié)點(diǎn)不會(huì)影響相似度的計(jì)算．而在重復(fù)節(jié)點(diǎn)的處理上，通過(guò)在XML文檔的預(yù)處理中，降低重復(fù)節(jié)點(diǎn)的權(quán)重，減少重復(fù)節(jié)點(diǎn)在相似度計(jì)算中的影響．

2.2實(shí)驗(yàn)結(jié)果

為了驗(yàn)證基于SET/BAG模型改進(jìn)的相似度計(jì)算方法的有效性，使用NIGARA數(shù)據(jù)集(actor, movies, department, club, bib)，分別從actor類中抽取117個(gè)文檔，moives類中抽取282個(gè)文檔，department類中抽取19個(gè)XML文檔，club類中抽取12個(gè)文檔，bib類中抽取16個(gè)文檔，總計(jì)446個(gè)文檔進(jìn)行混合．分別使用SET/BAG模型下的節(jié)點(diǎn)比較法、樹(shù)模型下的樹(shù)編輯距離和基于SET/BAG模型下改進(jìn)的相似度計(jì)算方法與DBSCAN聚類算法結(jié)合對(duì)XML文檔進(jìn)行聚類．節(jié)點(diǎn)比較法與樹(shù)編輯距離法是XML文檔相似度計(jì)算中有代表性的計(jì)算方法．并且通過(guò)與節(jié)點(diǎn)比較法和樹(shù)編輯距離法進(jìn)行對(duì)比，能很好地表現(xiàn)出基于SET/BAG模型改進(jìn)的相似度計(jì)算方法在XML文檔結(jié)構(gòu)特征的存儲(chǔ)與對(duì)重復(fù)節(jié)點(diǎn)和嵌套節(jié)點(diǎn)的處理上有很大的提升．實(shí)驗(yàn)結(jié)果如表2所示.

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

由于NIGARA數(shù)據(jù)集中的部分類別重復(fù)節(jié)點(diǎn)較多，對(duì)樹(shù)編輯距離的影響較為嚴(yán)重，節(jié)點(diǎn)比較法其次．并且因?yàn)閏lub,department和bib類別的XML文檔較少而重復(fù)節(jié)點(diǎn)在這些類別中有些文檔出現(xiàn)次數(shù)較多，有些文檔次數(shù)較少，導(dǎo)致基于樹(shù)編輯距離的DBSCAN算法將這些類別中的XML文檔計(jì)算成孤立點(diǎn)并排除在外，所以樹(shù)編輯距離的聚類結(jié)果不理想．而改進(jìn)后的SET/BAG模型相似度計(jì)算方法由于將重復(fù)節(jié)點(diǎn)的權(quán)重進(jìn)行調(diào)整，能很好地消除重復(fù)節(jié)點(diǎn)的影響．

為了防止單一數(shù)據(jù)集帶來(lái)的偶然性，本文使用XML Generator人工生成XML文檔數(shù)據(jù)集，此人工數(shù)據(jù)集分為3類，分別通過(guò)play.dtd，dblp.dtd和SigmodRecord.dtd生成150個(gè)XML文檔，其中play.dtd有45個(gè)文檔， dblp.dtd有65個(gè)文檔， SigmodRecord.dtd有40個(gè)文檔．實(shí)驗(yàn)結(jié)果如表3所示.

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

人工生成的數(shù)據(jù)集由于重復(fù)節(jié)點(diǎn)較少，因此，節(jié)點(diǎn)比較法和樹(shù)編輯距離的表現(xiàn)比在NIGARA數(shù)據(jù)集要好，但是仍然不能將所有數(shù)據(jù)集放入正確的簇集中．而基于SET/BAG改進(jìn)的相似度計(jì)算方法始終能夠得到很好的聚類結(jié)果．

參考文獻(xiàn)：

[1]ALSAYED A, MARCO M, RICHI N,etal. XML data clustering:an overview[J]. ACM Comput Surv, 2011,43(4):25.

[2]ANAND R, JEFFREY D U. Mining of Massive Datasets[M].Cambridge: Cambridge University Press， 2011.

[3]周水庚，周傲英.一種基于密度的快速聚類算法[J].計(jì)算機(jī)研究與發(fā)展， 2000，37(11)：1287-1292.

[4]BERTINO E, GUERRINI G, MESITI M. Measuring the structural similarity among XML documents and DTDS[EB/CD].Technical Report DISI-TR-02-02,Department of Computer Science, University of Genova, 2002.

[5]FLESCA S, MANEO G, MASCIARI E,etal. Detecting structural similarities between XML documents[C]// Proceedings of the 5th International Workshop on the Web and Databases, Madison, Wisconsin, 2002:55-60.

[6]SALTON G, WONG A, YANG C S. A vector space model for automatic indexing[J]. Comm ACM, 1975，18(11):613-620.

[7]LEE J W, LEE K, KIM W. Preparations for semantics-based XML mining[C]//Proceedings of the 2001 IEEE International Conference on Data Mining, San Jose, 2001:345-352.

[8]ANDREA T, SERGIO G. Semantic clustering of XML documents[J]. ACM Trans Inform Syst, 2010，28(1):1-56.

(編輯胡文杰)

Clustering Research on XML Document

YINLu-xiu*

(College of Mathematics and Computer Science, Hunan Normal University, Changsha 410081, China)

AbstractWith the rapid development of Internet, XML has become the most commonly used language for the Internet data exchange and storage. How to extract valuable information from a large number of XML document is one of the hottest research topics currently. This paper proposes a model based on the SET/BAG improved similarity calculation method, which converts each node of the XML document to an object (the object name, object, attribute set, and the weight of the object relative to the parent object) and can fully express the structure of an XML document information, by adjusting the repeated node weights to reduce its influence in similarity calculation. Based on real data sets and artificial datasets experiments respectively, the simulation experimental results show that the proposed method in this paper based on the SET/BAG model improved similarity calculation can get good clustering results.

Key wordsXML; document clustering; similarity computation

中圖分類號(hào)TP391.1

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1000-2537(2015)05-0091-04

通訊作者*,E-mail：55749691@qq.com

收稿日期：2015-02-17

DOI:10.7612/j.issn.1000-2537.2015.05.015