用於xml文檔分類的語義相似度度量方法
2023-07-05 17:44:46 1
專利名稱：用於xml文檔分類的語義相似度度量方法
用於XML文檔分類的語義相似度度量方法技術領域
本發明屬於數據識別技術領域，尤其是一種用於文檔分類的相似度度量方法。
技術背景
XML作為網際網路上數據表示和數據交換的標準，已得到廣泛的應用。隨著XML文檔 數量的不斷增長，如何對XML數據進行有效的管理在資料庫和信息檢索領域變得越來越重 要。在很多XML數據應用，例如版本控制、半結構化數據集成、XML文檔分類/聚類、XML檢 索等領域，如何度量XML文檔之間的相似度成為一個重要的問題，尤其在XML文檔分類/聚 類應用中，需要根據文檔之間的相似度把XML文檔歸到不同的類別中。
Ifligi^"Tekli J, Chbeir R, Yetongnon K. An overview on XML similarity Background, current trends and future directions. Computer ScienceReview,2009, 3(3) :151-173. 」，度量XML文檔之間相似度的方法大體可分成基於編輯距離(ED，Edit Distance)的方法、基於信息檢索(IR，Information Retrieval)的方法以及其它一些方 法。
基於編輯距離的方法一般都忽略了包含在文檔中的內容信息，利用結構信息計算 文檔距離並進行分類，這種方法的缺點在於編輯距離的計算開銷很大。文獻「DalamagasT， Cheng Τ, Winel KJ, Sellis Τ. A methodology for clustering XML documents by structure. Information Systems, 2006, 31 (3) :187-228. 」首先對 XML 文檔進行簡化，得到 文檔的Summary Tree，然後計算Summary Tree之間的編輯距離來進行分類。雖然這種方 法降低了計算樹編輯距離的時間複雜性，但是Summary Tree並不能很好地保持原有文檔的 結構° 文獻"Xing G, Guo J, Xia ZH. Classifying XML Documents Based onStructure/ Content Similarity. Comparative Evaluation of XML Information RetrievalSystems, 2007,4518 :444-457. 」通過計算XML文檔與khema之間的編輯距離對XML文檔進行分類， 這種方法假設屬於同一個類別的所有XML文檔具有共同的khema，並且該khema可以得 到。事實上屬於同一類別的XML文檔很多情況下並不具有共同的khema，而且XML文檔的 Schema並非總是可以輕易獲得，雖然文中提出了一種從XML文檔中抽取khema的方法，但 這需要額外的開銷。由於基於編輯距離的方法忽略了文檔的內容，因而並沒有利用關鍵字 的語義信息。
傳統的基於信息檢索的方法將文檔表示為一個向量，向量的每個分量為該文檔中 所包含的關鍵字在該文檔中的權重，然後任意兩個文檔之間的相似度可以轉換為計算兩個 向量的距離。關鍵為如何計算關鍵字的權重，使用最多的方法是tf-idf公式，這種方法僅 僅利用文檔中的內容信息，並未考慮到XML文檔中的結構信息，因此不完全適用於XML文檔 的相似度計算。針對XML文檔，也有方法對tf-idf方法進行擴展，同時利用XML文檔中的 結構和內容信息，例如文獻「袁家政，須德，鮑泓.基於結構與文本關鍵詞相關度的xml網頁 分類研究.計算機研究與發展，2006，43 (8) :1361-1367. 」在計算關鍵字的權重時考慮了關 鍵字出現在不同樹節點的位置以及位置的權重，但僅僅考慮關鍵字在不同樹節點的位置和位置權重還未能完全利用包含在其中的語義信息，比如還可以考慮包含關鍵字的路徑的層 次，包含路徑的文檔數以及同時包含路徑和關鍵字的文檔數等信息。
文獻"Zaki MJ, Aggarwal CC. XRules :an effective structural classifier for XML data. In :Getoor L，Senator TE, domingos P，Faloutsos C，eds. Proc. of the ninth ACM SIGKDDinternational conference on Knowledge discovery and data mining. Washington, D. C. :ACM，2003. 316-325. 」提出 了一種基於規則的分類方法，首先 從XML文檔中挖掘頻繁子樹，然後利用這些頻繁子樹生成規則進行分類。這種方法假設 屬於同一類別的文檔具有相同的子結構，事實上在很多情況下這個假設並不成立。文獻 「Theobald M，Schenkel R，Weikum Gerhard. Exploiting Structure，Annotation，and OntologicalKnowledge for Automatic Classification of XML Data. In Christophides V，Freire J，eds. Proc. ofthe WebDB Workshop. San Diego, California :ACM，2003.1-6. 」 除了使用關鍵字作為特徵外，還使用小枝(Twigs)和標籤路徑(Tag Paths)作為結構特 徵來構造特徵空間，然後利用本體論和互信息來確定與某一個類別最相關的m個特徵， 然後根據這些類相關的特徵來構造分類器。由於這種方法預先限制結構特徵中只包含 兩層結構，在一定程度上破壞了 XML的多層結構。文獻「mi Jff, Tang J. A bottom-up approach for XMLdocuments classification. In :Desai BC, ed.Proc. of the 12th International DatabaseEngineering and Applications Symposium. Coimbra,Portugal ACM, 2008. 131-137. 」利用支持度和互信息的概念從文檔中抽取與某一個特定類別相關的 關鍵字，稱為KeyTerm，然後找到包含這些Key Term的路徑，稱為Key Path，該類別的所有 Key Path就構成了該類別的一個分類Model，然後通過計算XML文檔與各個類別的Model 之間的距離來對文檔進行分類。作者同樣利用了一個假設，即屬於同一類別的XML文檔的 Schema是相似的，雖然並不要求khema —定能夠得到，但這個假設仍然在一定程度上限制 了其應用的靈活性。發明內容
為了克服現有技術未充分考慮XML文檔中關鍵字語義信息或者依賴於文檔 khema的不足，本發明提供一種基於關鍵字語義信息的XML文檔相似度度量方法，將XML文 檔表示為由關鍵字權重組成的向量，XML文檔之間的相似度計算就可以轉換為計算兩個向 量之間的距離問題，計算過程中不需要得到XML文檔的khema。本發明同時利用了 XML文 檔中包含的結構信息和內容信息，較為充分地考慮包含在文檔中的關鍵字的語義信息，比 如關鍵字在不同路徑中出現的次數，路徑的深度，路徑本身的分類能力，包含路徑的文檔個 數，同時包含某一路徑和關鍵字的文檔個數等計算關鍵字的權重，並據此度量文檔之間的 相似度。如果將利用這種方法度量的文檔之間相似度用於XML文檔的分類時，可以提高分 類的準確率。
對於給定的XML文檔集D，其中的第i個文檔表示為屯，設D中的文檔分屬於|C| 個類別，C表示所有類別的集合，Ci表示文檔集D中所有屬於第i個類別的文檔組成的集合。 則為了計算文檔之間的相似度，本發明解決其技術問題所採用的技術方案包括以下步驟
1.解析文檔集中所有的XML文檔，將每一個XML文檔分解為結構信息和內容信息。
2.從內容信息中抽取關鍵字特徵，構造關鍵字特徵空間。
3.從結構信息中抽取所有的路徑，構造路徑字典。
4.統計關鍵字特徵空間中每個關鍵字特徵tk在每個文檔的任意路徑pat、中出 現的頻率tfi (tk,pathj)，同時包含該關鍵字特徵和路徑的文檔個數(Ifai^pathj)以及包含 該關鍵字特徵的文檔個數df(tk)，並根據df(tk)進行關鍵字特徵篩選。
5.計算路徑字典中每條路徑Pathj的深度pi (Pathj)，數據集中包含該路徑的文檔 數Clf(Pathj)及其權重wpathj，其中權重利用資訊理論中信息增益的概念進行計算。
6.根據第4，5步得到的信息，利用下式計算關鍵字特徵空間中每個關鍵字特徵tk 在文檔Cli中的權重wik，然後將文檔表示為由關鍵字特徵權重組成的向量。
權利要求
1. 一種用於XML文檔分類的語義相似度度量方法，其特徵在於對於給定的XML文檔 集D，其中的第i個文檔表示為d」設D中的文檔分屬於|C|個類別，C表示所有類別的集 合，Ci表示文檔集D中所有屬於第i個類別的文檔組成的集合，則為了計算文檔之間的相似 度，包括以下步驟a.解析文檔集中所有的XML文檔，將每一個XML文檔分解為結構信息和內容信息；b.從內容信息中抽取關鍵字特徵，構造關鍵字特徵空間；c.從結構信息中抽取所有的路徑，構造路徑字典；d.統計關鍵字特徵空間中每個關鍵字特徵tk在每個文檔的任意路徑中出現的 頻率tfi (tk,pathj)，同時包含該關鍵字特徵和路徑的文檔個數df(tk，path」)以及包含該關 鍵字特徵的文檔個數df(tk)，並根據df(tk)進行關鍵字特徵篩選；e.計算路徑字典中每條路徑Pathj的深度Pl(Pathj),數據集中包含該路徑的文檔數 df(pathj)及其權重wpathj，其中權重利用資訊理論中信息增益的概念進行計算；f.根據第d，e步得到的信息，利用下式計算關鍵字特徵空間中每個關鍵字特徵tk在文 檔Cli中的權重wik，然後將文檔表示為由關鍵字特徵權重組成的向量；
全文摘要
本發明公開了一種用於XML文檔分類的語義相似度度量方法，依次將每個文檔分解為結構信息和內容信息；從內容信息中抽取關鍵字特徵，構造關鍵字特徵空間；從結構信息中抽取所有的路徑，構造路徑字典；統計關鍵字特徵空間中每個關鍵字特徵在每個文檔的任意路徑中出現的頻率，同時包含該關鍵字特徵和路徑的文檔個數以及包含該關鍵字特徵的文檔個數等信息，計算關鍵字特徵空間中每個關鍵字特徵在文檔中的權重；根據餘弦度量計算任意兩個文檔之間的相似度。本發明應用於XML文檔的分類，可以提高準確率。
文檔編號G06F17/27GK102033867SQ201010590689
公開日2011年4月27日 申請日期2010年12月14日 優先權日2010年12月14日
發明者婁穎, 崔海文, 張利軍, 李戰懷, 李霞, 陳群 申請人:西北工業大學