孫霞，張玉生

（常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇常熟 215500）

基于模式元素的文檔聚類(lèi)方法研究

孫霞，張玉生

（常熟理工學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇常熟 215500）

聚類(lèi)問(wèn)題的關(guān)鍵是把相似的事物聚集在一起，因此相似度計(jì)算是進(jìn)行文檔聚類(lèi)的首要問(wèn)題.XML模式是XML文檔結(jié)構(gòu)的體現(xiàn)，對(duì)XML文檔的聚類(lèi)可以通過(guò)XML模式的聚類(lèi)來(lái)實(shí)現(xiàn).本文提出一種基于XML模式元素的文檔聚類(lèi)方法，通過(guò)計(jì)算XML模式元素間的相似度來(lái)對(duì)文檔進(jìn)行聚類(lèi)，綜合考慮了XML模式中元素的結(jié)構(gòu)和語(yǔ)義信息，進(jìn)一步提高了計(jì)算相似度的精度，提高聚類(lèi)的準(zhǔn)確性，并且易于提取聚簇的通用XML模式.

元素；模式；相似度；聚類(lèi)

1 引言

XML（Extensible Markup Language）作為一種新興的自描述語(yǔ)言，以其良好的可擴(kuò)展性受到業(yè)界的普遍歡迎和支持，逐漸成為Web上的通用語(yǔ)言，越來(lái)越多的應(yīng)用領(lǐng)域已經(jīng)將其作為主要的存儲(chǔ)格式和傳輸媒體.隨著XML信息量的劇增，怎樣對(duì)這些數(shù)據(jù)進(jìn)行復(fù)雜的應(yīng)用成了現(xiàn)今數(shù)據(jù)庫(kù)技術(shù)的研究熱點(diǎn)，特別是從海量數(shù)據(jù)中提取出有用的信息變得越來(lái)越重要.在半結(jié)構(gòu)化數(shù)據(jù)中進(jìn)行數(shù)據(jù)查詢、知識(shí)發(fā)現(xiàn)以及對(duì)Internet上巨大數(shù)量的數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，能夠滿足網(wǎng)絡(luò)這種復(fù)雜分布環(huán)境的需要，但同時(shí)也給數(shù)據(jù)處理帶來(lái)了很大的困難.目前半結(jié)構(gòu)化數(shù)據(jù)相關(guān)的研究方向有很多，如新的數(shù)據(jù)模型、相關(guān)的查詢語(yǔ)言、存儲(chǔ)技術(shù)以及查詢優(yōu)化技術(shù)等.在眾多的研究課題中，對(duì)文檔進(jìn)行聚類(lèi)，從而更好地組織和管理信息，快速、準(zhǔn)確、全面地搜索到用戶所需要的信息成為研究的熱點(diǎn).

聚類(lèi)是研究數(shù)據(jù)間邏輯上或物理上的相互關(guān)系的技術(shù)，其分析結(jié)果不僅可以揭示數(shù)據(jù)間的內(nèi)在聯(lián)系與區(qū)別，還可以為進(jìn)一步的數(shù)據(jù)分析與知識(shí)發(fā)現(xiàn)提供重要依據(jù).聚類(lèi)是一個(gè)將數(shù)據(jù)集劃分為若干組或簇的過(guò)程，使得同一類(lèi)的數(shù)據(jù)對(duì)象之間的相似度較高，而不同類(lèi)的數(shù)據(jù)對(duì)象之間的相似度較低.聚類(lèi)問(wèn)題的關(guān)鍵是把相似的事物聚集在一起，因此相似度計(jì)算是進(jìn)行文檔聚類(lèi)的關(guān)鍵問(wèn)題.本文提出了一種基于XML模式元素相似度的文檔聚類(lèi)方法，通過(guò)計(jì)算XML模式元素的相似度，綜合考慮了元素的結(jié)構(gòu)和語(yǔ)義信息，相似度計(jì)算結(jié)果更加準(zhǔn)確，該方法復(fù)雜度較小，并且易于提取通用的XML模式.

2 相似度計(jì)算

2.1 模式提取

一般XML文檔會(huì)含有大量相似結(jié)構(gòu)的冗余信息.為了有效實(shí)現(xiàn)對(duì)文檔的聚類(lèi)，我們所關(guān)心的只是與XML文檔結(jié)構(gòu)有密切聯(lián)系的信息，而不是文檔中表示事物具體信息的數(shù)據(jù)本身.XML模式是W 3C的推薦標(biāo)準(zhǔn)，它負(fù)責(zé)定義和描述XML文檔的結(jié)構(gòu)和內(nèi)容模式.XML Schema可以定義XML文檔中存在哪些元素和元素之間的關(guān)系，并且可以定義元素和屬性的數(shù)據(jù)類(lèi)型，同時(shí)XML Schema還可以約束文檔的內(nèi)容.XML模式文檔的規(guī)模通常遠(yuǎn)遠(yuǎn)小于XML文檔，對(duì)XML文檔的聚類(lèi)可以通過(guò)XML模式的聚類(lèi)來(lái)實(shí)現(xiàn).

但是現(xiàn)實(shí)世界中存在著大量無(wú)模式的XML文檔，對(duì)于這類(lèi)XML文檔，如何高效準(zhǔn)確地獲得其模式信息是XML技術(shù)研究者關(guān)注的重要問(wèn)題.XML模式提取技術(shù)正是為了解決這個(gè)問(wèn)題而成為XML技術(shù)領(lǐng)域的研究熱點(diǎn)[1-3].許多研究者對(duì)自動(dòng)提取XML模式的工具進(jìn)行研究并取得了一定的成果.XTRACT，DDbE，DTD-Miner都是自動(dòng)提取XML文檔DTD的工具；在XML Schema成為標(biāo)準(zhǔn)之后，XStruct[4]用來(lái)自動(dòng)提取XML Schema.這些模式抽取系統(tǒng)所采用的一般方法是對(duì)XML文檔進(jìn)行解析，在內(nèi)存中創(chuàng)建一棵DOM樹(shù)，將XML樹(shù)模型轉(zhuǎn)換為用OEM模型描述的圖模型，通過(guò)對(duì)圖模型的操作來(lái)提取模式信息.這些系統(tǒng)運(yùn)行的時(shí)間和空間代價(jià)較大，并且會(huì)產(chǎn)生缺邊及環(huán)路問(wèn)題.

本文提出使用SAX解析器對(duì)XML文檔進(jìn)行解析，不需要把整個(gè)文檔加載到內(nèi)存，而是根據(jù)已經(jīng)定義好的事件處理器來(lái)決定當(dāng)前所解析的部分（元素、屬性或時(shí)元素內(nèi)容）是否有必要記錄并存儲(chǔ)，通過(guò)對(duì)XML文檔進(jìn)行掃描，高效地提取出模式信息.圖1是進(jìn)行模式提取的流程圖.

2.2 元素相似度

在XML文檔中，構(gòu)成模式的主體是元素，元素的信息能夠反映XML模式的內(nèi)容，XML模式的相似度由元素相似度組成.因此計(jì)算文檔的相似度可以通過(guò)計(jì)算模式元素的相似度來(lái)獲得.由于XML文檔是結(jié)構(gòu)信息和語(yǔ)義信息的綜合體，因此相似度計(jì)算需要將結(jié)構(gòu)信息和語(yǔ)義信息兩者相結(jié)合進(jìn)行.

一般兩個(gè)文檔樹(shù)d1和d2所包含的相同元素越多，且元素間的層次關(guān)系越相似時(shí)兩個(gè)XML模式間的結(jié)構(gòu)相似程度越大；反之，則相似度越低.因此計(jì)算結(jié)構(gòu)相似度時(shí)要綜合考慮相同元素的個(gè)數(shù)以及元素所在的層次信息，元素的結(jié)構(gòu)相似度公式為

圖1 模式提取流程圖

其中k是相同元素的個(gè)數(shù)，ei是文檔樹(shù)d1和d2中的相同元素，ej是文檔樹(shù)d1和d2中的不同元素，Level（ei）和Level（ej）是指元素ei和ej在文檔樹(shù)中所處的層次.

在XML文檔中，由于用戶可以自定義XML文檔的元素名稱(chēng)，這將會(huì)造成采用不同的元素名稱(chēng)但描述的是相同內(nèi)容的問(wèn)題.如果在比較它們的文檔結(jié)構(gòu)時(shí)要求元素名稱(chēng)完全匹配，那么這兩個(gè)文檔的相似度就很低，這顯然是不合理的.因此，計(jì)算XML模式的相似度時(shí)，還要考慮元素的語(yǔ)義相似度.我們分別為兩個(gè)文檔樹(shù)建立一個(gè)包括所有元素標(biāo)簽的集合T1和T2，通過(guò)計(jì)算這兩個(gè)集合中的單詞的相似度來(lái)計(jì)算兩個(gè)文檔樹(shù)的語(yǔ)義相似度.由于元素的名字是由用戶指定的，XML元素命名可使用英文大小寫(xiě)字符、數(shù)字、下劃線字符、句點(diǎn)字符以及橫短線字符，因此首先需要將元素名稱(chēng)進(jìn)行預(yù)處理，將合成詞分解成單詞序列并去除其中的停止詞，然后再使用WordNet[5]來(lái)計(jì)算元素的語(yǔ)義相似度.

語(yǔ)義相似度計(jì)算公式為

綜合考慮XML模式中元素的結(jié)構(gòu)和語(yǔ)義相似度后，XML模式的相似度公式為

其中α和β用來(lái)控制結(jié)構(gòu)信息和語(yǔ)義信息對(duì)相似度的影響程度.通過(guò)該公式計(jì)算相似度的結(jié)果在0到1的區(qū)間范圍內(nèi)，結(jié)果為0表示這兩個(gè)XML模式完全不相同，結(jié)果為1則表示這兩個(gè)XML模式完全相同.

3 文檔聚類(lèi)

目前國(guó)內(nèi)XML聚類(lèi)大多數(shù)仍然停留在結(jié)構(gòu)相似性聚類(lèi)上，應(yīng)用最多的主要為劃分聚類(lèi)法和層次聚類(lèi)法兩種[6].層次聚類(lèi)法是將文本集合進(jìn)行層次分解，組成一顆凝聚樹(shù)，根據(jù)層次的形成方式可以分為自底向上的方法和自頂向下的方法兩類(lèi).其弱點(diǎn)是每次都必須比較所有類(lèi)簇的相似度，這使得層次聚類(lèi)不易處理大規(guī)模數(shù)據(jù)集.劃分聚類(lèi)法是將包含n個(gè)文檔的文本集合，劃分成k個(gè)分組，k＜=n，每一個(gè)分組代表一個(gè)聚類(lèi)，使用劃分聚類(lèi)算法需要事先指定聚類(lèi)的個(gè)數(shù)，然而現(xiàn)實(shí)中的數(shù)據(jù)往往無(wú)法得知其結(jié)構(gòu)，因此聚類(lèi)的個(gè)數(shù)很難事先確定.XML目前作為一種通用的數(shù)據(jù)交換載體，在海量數(shù)據(jù)的存儲(chǔ)中，其文件本身的結(jié)構(gòu)具有一定的多樣性.因此，傳統(tǒng)的聚類(lèi)方法無(wú)法應(yīng)對(duì)XML文件結(jié)構(gòu)本身的多樣性.本文提出一種基于模式元素的XML文檔聚類(lèi)方法，利用該方法相比傳統(tǒng)的文檔聚類(lèi)技術(shù)可以更加有效地對(duì)文檔進(jìn)行聚類(lèi).

根據(jù)前面的模式提取方法，首先對(duì)于文檔集中的文檔進(jìn)行模式抽取，提取出對(duì)應(yīng)的模式文檔集合S，計(jì)算Si（Si∈S）與聚類(lèi)C1…Cm的相似度simi1…simim，找出其中相似度值最大的simik，如果simik大于相似度閾值，則將Si歸入聚類(lèi)Ck中，否則生成一個(gè)包含該文檔Si的新的聚類(lèi).

但是根據(jù)輸入文檔的順序不同，此方法可能存在生成的聚類(lèi)結(jié)果不準(zhǔn)確的現(xiàn)象，因此還要對(duì)聚類(lèi)集合進(jìn)行改進(jìn)調(diào)整，具體做法是：從模式集中隨機(jī)選擇一個(gè)文檔Si，計(jì)算其與聚類(lèi)C1…Cm的相似度simi1…simim，找出其中相似度值最大的simik，如果simik大于相似度閾值，則將Si歸入聚類(lèi)Ck中，否則生成一個(gè)包含該模式文檔Si的新的聚類(lèi).

具體算法如下：

算法：Cluster

輸入：XML文檔集合D

輸出：模式集合S、聚類(lèi)集合C

4 實(shí)驗(yàn)分析

在文檔聚類(lèi)中常用查全率（又稱(chēng)聚類(lèi)精度）和查準(zhǔn)率（又稱(chēng)聚類(lèi)召回率）兩個(gè)指標(biāo)來(lái)評(píng)價(jià)聚類(lèi)結(jié)果.本文采用XML文檔生成工具XMLGenerator按照10個(gè)DTD各自生成的50個(gè)文檔作為XML測(cè)試數(shù)據(jù)集，選用基于編輯距離的聚類(lèi)和本文提出的基于模式元素的聚類(lèi)方法進(jìn)行聚類(lèi)分析和比較，聚類(lèi)結(jié)果如圖2、圖3所示.

聚類(lèi)查全率反映了將相似文本單元和不相似文本單元合并到同一類(lèi)的程度，反映了對(duì)不同主題的區(qū)分能力，聚類(lèi)精度越高，每個(gè)類(lèi)中的內(nèi)容越集中.聚類(lèi)查準(zhǔn)率反映了將同一主題相似文本單元集合合并到一個(gè)類(lèi)中的程度，反映了對(duì)相同主題的識(shí)別能力，聚類(lèi)召回率越高，相似的文本單元越集中，即被拆分到不同類(lèi)中的情況就越少.從圖2和圖3的實(shí)驗(yàn)結(jié)果可以看出，使用基于模式元素的聚類(lèi)方法進(jìn)行文檔聚類(lèi)，在計(jì)算相似度時(shí)綜合考慮了文檔的結(jié)構(gòu)和語(yǔ)義因素，并且在得到初始聚類(lèi)集合后，為了避免聚類(lèi)不準(zhǔn)確的現(xiàn)象，對(duì)文檔集合進(jìn)行了再次調(diào)整得到最終的聚類(lèi)集合，其查全率和查準(zhǔn)率較高.在使用基于編輯距離方法進(jìn)行相似度計(jì)算時(shí)，由于僅考慮了文檔的結(jié)構(gòu)相似度忽略了語(yǔ)義相似度，因而得到的文檔的相似度精度不高，從而影響文檔的聚類(lèi)結(jié)果.

圖2 查全率對(duì)比圖

圖3 查準(zhǔn)率對(duì)比圖

5 小結(jié)

XML文檔聚類(lèi)有著比較廣泛的應(yīng)用，由于聚類(lèi)可以作為Web挖掘的預(yù)處理過(guò)程，提高信息檢索的效率，因此聚類(lèi)在信息檢索、文本挖掘、Web數(shù)據(jù)分析、客戶關(guān)系管理等方面也起著重要作用.由于XML數(shù)據(jù)的異構(gòu)性，利用本文提出的方法在進(jìn)行文檔聚類(lèi)時(shí)通過(guò)提取出XML模式，可以大大減小比較的文檔的規(guī)模，避免重復(fù)元素對(duì)相似度計(jì)算的干擾，同時(shí)該方法結(jié)合XML模式元素的結(jié)構(gòu)和語(yǔ)義兩方面來(lái)進(jìn)行相似度計(jì)算，可以使相似度計(jì)算結(jié)果更加準(zhǔn)確，從而提高聚類(lèi)的準(zhǔn)確性.但本文進(jìn)行實(shí)驗(yàn)的文檔集規(guī)模較小，并且XML文檔的結(jié)構(gòu)也比較簡(jiǎn)單，對(duì)于大文檔集和復(fù)雜的文檔結(jié)構(gòu)，該方法有待于進(jìn)一步的驗(yàn)證與改進(jìn).

[1]Chang C H,Lui SC,Wu Y C.Applying patternmining toWeb information extraction[A].In Proceedings of the Fifth Pacific Asia Conference on Knowledge Discovery and DataMining[C].Hong Kong,2001:3.

[2]Min JK,Ahn JY,Chung CW.EfficientExtraction ofSchemas for XMLDocuments[J].Information Processing Letters,2003,85(1):7.

[3]張海威，袁曉潔，楊娜，等.元素路徑模型：高效的XML Schema提取方法[J].計(jì)算機(jī)工程，2008，34（3）：32-35.

[4]Hegewald J,Naumann F,Weis M.XStruct:Efficient Schema Extraction from Multiple and Large XML Documents[C].Proceedings of the 22nd International Conference on Data EngineeringWorkshops.Atlanta,GA,USA:[s.n.],2006:81.

[5]George M,richard B.Introduction to wordNet:an online lexical database[J].International Journal of Lexicography,1993,3(4): 235-312.

[6]楊厚群，何中市，雷景生.基于劃分的XML文檔聚類(lèi)研究[J].計(jì)算機(jī)科學(xué)，2008，35（3）：183-185.

A Research on Clustering Method Based on Element of XML Schema

SUN Xia,ZHANG Yu-sheng
(School of Computer Science and Engineering,Changshu Institute of Technology,Changshu 215500,China)

A clustering method based on element of XML schema is brought forward in this paper.The key of clustering is to aggregate the similar things together.Therefore,the similarity is the important foundation for XML clustering.Schema is the representation of document structure,and clustering of XML documents can be achieved through clustering of XML schemas.The authors of this paper cluster documents by calculating the sim?ilarity of elements,because elements are the main body in XML.The approach takes full account of the struc?ture and semantics of elements,and makes a more accurate calculation of sim ilarity.In the meanwhile,it im?proves the accuracy of clustering and makes it easy to extract the common XML schema.

element;schema;similarity;clustering

TP391

A

1008-2794（2012）08-0094-05

2012-06-13

孫霞（1978—），女，河南周口人，講師，碩士，研究方向：算法分析與設(shè)計(jì)，計(jì)算機(jī)網(wǎng)絡(luò).