基于模式元素的文檔聚類方法研究

孫霞，張玉生

（常熟理工學院計算機科學與工程學院，江蘇常熟 215500）

基于模式元素的文檔聚類方法研究

孫霞，張玉生

（常熟理工學院計算機科學與工程學院，江蘇常熟 215500）

聚類問題的關鍵是把相似的事物聚集在一起，因此相似度計算是進行文檔聚類的首要問題.XML模式是XML文檔結構的體現，對XML文檔的聚類可以通過XML模式的聚類來實現.本文提出一種基于XML模式元素的文檔聚類方法，通過計算XML模式元素間的相似度來對文檔進行聚類，綜合考慮了XML模式中元素的結構和語義信息，進一步提高了計算相似度的精度，提高聚類的準確性，并且易于提取聚簇的通用XML模式.

元素；模式；相似度；聚類

1 引言

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

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

2 相似度計算

2.1 模式提取

一般XML文檔會含有大量相似結構的冗余信息.為了有效實現對文檔的聚類，我們所關心的只是與XML文檔結構有密切聯系的信息，而不是文檔中表示事物具體信息的數據本身.XML模式是W 3C的推薦標準，它負責定義和描述XML文檔的結構和內容模式.XML Schema可以定義XML文檔中存在哪些元素和元素之間的關系，并且可以定義元素和屬性的數據類型，同時XML Schema還可以約束文檔的內容.XML模式文檔的規模通常遠遠小于XML文檔，對XML文檔的聚類可以通過XML模式的聚類來實現.

但是現實世界中存在著大量無模式的XML文檔，對于這類XML文檔，如何高效準確地獲得其模式信息是XML技術研究者關注的重要問題.XML模式提取技術正是為了解決這個問題而成為XML技術領域的研究熱點[1-3].許多研究者對自動提取XML模式的工具進行研究并取得了一定的成果.XTRACT，DDbE，DTD-Miner都是自動提取XML文檔DTD的工具；在XML Schema成為標準之后，XStruct[4]用來自動提取XML Schema.這些模式抽取系統所采用的一般方法是對XML文檔進行解析，在內存中創建一棵DOM樹，將XML樹模型轉換為用OEM模型描述的圖模型，通過對圖模型的操作來提取模式信息.這些系統運行的時間和空間代價較大，并且會產生缺邊及環路問題.

本文提出使用SAX解析器對XML文檔進行解析，不需要把整個文檔加載到內存，而是根據已經定義好的事件處理器來決定當前所解析的部分（元素、屬性或時元素內容）是否有必要記錄并存儲，通過對XML文檔進行掃描，高效地提取出模式信息.圖1是進行模式提取的流程圖.

2.2 元素相似度

在XML文檔中，構成模式的主體是元素，元素的信息能夠反映XML模式的內容，XML模式的相似度由元素相似度組成.因此計算文檔的相似度可以通過計算模式元素的相似度來獲得.由于XML文檔是結構信息和語義信息的綜合體，因此相似度計算需要將結構信息和語義信息兩者相結合進行.

一般兩個文檔樹d1和d2所包含的相同元素越多，且元素間的層次關系越相似時兩個XML模式間的結構相似程度越大；反之，則相似度越低.因此計算結構相似度時要綜合考慮相同元素的個數以及元素所在的層次信息，元素的結構相似度公式為

圖1 模式提取流程圖

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

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

語義相似度計算公式為

綜合考慮XML模式中元素的結構和語義相似度后，XML模式的相似度公式為

其中α和β用來控制結構信息和語義信息對相似度的影響程度.通過該公式計算相似度的結果在0到1的區間范圍內，結果為0表示這兩個XML模式完全不相同，結果為1則表示這兩個XML模式完全相同.

3 文檔聚類

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

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

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

具體算法如下：

算法：Cluster

輸入：XML文檔集合D

輸出：模式集合S、聚類集合C

4 實驗分析

在文檔聚類中常用查全率（又稱聚類精度）和查準率（又稱聚類召回率）兩個指標來評價聚類結果.本文采用XML文檔生成工具XMLGenerator按照10個DTD各自生成的50個文檔作為XML測試數據集，選用基于編輯距離的聚類和本文提出的基于模式元素的聚類方法進行聚類分析和比較，聚類結果如圖2、圖3所示.

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

圖2 查全率對比圖

圖3 查準率對比圖

5 小結

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

[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].計算機工程，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文檔聚類研究[J].計算機科學，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—），女，河南周口人，講師，碩士，研究方向：算法分析與設計，計算機網絡.