【導讀】近年來，隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)上的信息資源呈不斷的擴張趨勢，無論在數(shù)量還是領(lǐng)域范圍上，都爆炸式增長。為數(shù)據(jù)挖掘、機器學習等領(lǐng)域中的研究熱點之一。題之一，也是Web數(shù)據(jù)挖掘系統(tǒng)所要解決的關(guān)鍵問題之一。在面向內(nèi)容的智能信息處理中，基于結(jié)構(gòu)表示模式，除網(wǎng)絡(luò)環(huán)境下的信息孤島和實現(xiàn)信息資源的互聯(lián)互通和資源共享。普遍的關(guān)注和研究。但目前對基于XML半結(jié)構(gòu)語言計算語義相似性的研究沒有。重影響了對互聯(lián)網(wǎng)信息的應(yīng)用效率。挖掘方法等進行了深入研究，在此基礎(chǔ)上，展開了XML的語義相似性研究。究平臺和應(yīng)用環(huán)境為Windows7，軟件開發(fā)工具為VisualStudio2021。配，結(jié)合南開大學的已有項目，研究成果將應(yīng)用于Web數(shù)據(jù)挖掘方法與系統(tǒng)；自然語言處理、數(shù)據(jù)集成及語義Web等許多方面。并以本課題為基礎(chǔ)，為將來在更。[8]邱明.語義相似性度量及其在設(shè)計管理系統(tǒng)中的應(yīng)用[D].博士，浙江大學，[10]宋玲.語義相似度計算及其應(yīng)用研究.博士，山東大學，2021.

　　

【正文】 n C Cs im C C es tr e n C C s tr e n C C??? ??? ? (38) 0 0 1 1 2 1( , ) ( , ) ( , ) .. . ( , )n n nstre n a a stre n a a stre n a a stre n a a?? ? ? ? (39) 12 11( , )stren a a C? (310) 其中α、β為經(jīng)驗參數(shù)， len(C)為節(jié)點 C 到根節(jié)點的距離， dist(a0,an)為節(jié)點 a0天津大學 2021屆本科生畢業(yè)設(shè)計（論文） 11 到 an 的語義距離， stren(a1,a2)為父子節(jié)點之間的連接強度， C1 為節(jié)點 1 的出度。 算法分析 我們知道，兩個概念之間的語義距離和連接強度的取值是相反的，語義距離越大連接強度越低，為了將連接強度和語義距離結(jié) 合，本文擴展了連接強度的概念。 10 式定義了連接強度的計算方法，即節(jié)點出度的倒數(shù)。也就是說，父子節(jié)點之間的連接強度越大，取值越小，連接強度越小，取值越大。這樣，就解決了為最短路徑上每一條邊賦權(quán)值的問題：任意兩個節(jié)點 a， b，找到它們的最短路徑后，其路徑長度為每條邊的連接長度 stren(a1,a2)，即 9 式給出的計算方法。這樣，本文重新定義任意兩個節(jié)點 a， b 的最短路徑為任意兩個節(jié)點 a， b 之間的連接強度 stren（ a， b）。 利用連接強度，本文給出了計算相似度的方法 8 式。其中前半部分中 為節(jié)點 ， 的公共祖先到根 節(jié)點的距離，即兩者的共有信息量， 為兩者之間的連接強度，即差異信息量，因此為通過信息學理論計算出的相似度；后半部分是為了體現(xiàn)非對稱性而編寫的輔助函數(shù) 。求 ， 和求 ， 的相似性時，的取值是不一樣的。 α， β是區(qū)分相似度和非對稱性的權(quán)重而設(shè)置的參數(shù)，需要根據(jù)實驗數(shù)據(jù)不斷修改。 表 31 將本算法與上文提到的網(wǎng)絡(luò)距離模型算法進行了比較。 表 31 網(wǎng)絡(luò)距離模型與本文設(shè)計算法比較 公式 節(jié)點間距離 邊密度 連接強度 深度 方向性 31 是 否 否 是 否 33 是 是 否 是 是 34 是 否 否 是 否 35 是 否 否 是 否 38 是 是 是 是 是 從表 31 可以看出，本文設(shè)計算法在繼承了現(xiàn)有算法優(yōu)點的基礎(chǔ)上，進一步可慮了方向性、連接強度等現(xiàn)有算法沒有可慮的因素，進一步提高了算法的精確天津大學 2021屆本科生畢業(yè)設(shè)計（論文） 12 性。 表 32 將本算法與上文提到的信息理論模型進行了比較 表 32 信息理論模型與本文設(shè)計算法比較 公式 共有信息量 差異信息量 訪問語料庫 36 是 否 是 37 是 是 是 38 是 是 否 從表 33 中可以看出，本算法避免了對語料庫的頻繁訪問，降低了算法的實現(xiàn)難度。 但相對于網(wǎng)絡(luò)距離模型，其復雜度顯然是略高的，因此，在具體的實現(xiàn)中，可以根據(jù)應(yīng)用的不同，在精度和效率之間進行取舍。 比如，可以使公式 38中的 β 參數(shù)為零，這樣就變成一個純粹的信息理論模型，而不考慮方向性、連接強度等因素；而如果對 α、β 進行更精確的取值，計算精度提高的同時算法復雜度也將提高。 本章小結(jié) 本章系統(tǒng)的闡述了目前概念相似性比較的主流方法，主要分為兩種，網(wǎng)絡(luò)距離模型和信息理論模型。并分析了這些方法的不足。 在 節(jié)中我們提出了一個建議，采用信息理論模型，同時避免訪問語料庫。由此，我們提出了使用本 體擔當語料庫的方式，并自動為語料庫中的每一個信息賦值（自動生成它們應(yīng)該出現(xiàn)的頻率）。并從信息學的角度重新解釋了深度、邊密度，節(jié)點之間的連接強度這三個概念， 在此基礎(chǔ)上給出了一個新的測量概念相似性的方法。它吸取了兩種不同模型的優(yōu)點，以信息理論模型為基礎(chǔ)，綜合考慮了深度、邊密度，節(jié)點之間的連接強、非對稱性等因素，給出了一種可行的相似度計算方法。 天津大學 2021屆本科生畢業(yè)設(shè)計（論文） 13 第四章 基于 WordNet 的 XML 語義相似性算法 XML 文檔簡介 XML（ Extensible Markup Language）的英文原意是可擴展的標記 語言。也就是說，它有兩方面重要的特性，一是可擴展，二是標記性。 所謂可擴展是針對于 HTML 等結(jié)構(gòu)語言而言的， XML 文檔有自己的結(jié)構(gòu)特點，但對結(jié)構(gòu)的要求并不強，使用者可以定義自己的 XML 文檔結(jié)構(gòu)。總體而言，XML 文檔是樹形結(jié)構(gòu)的，但樹的深度、節(jié)點的出度、入讀、節(jié)點的內(nèi)容是使用者自己定義的；另一方面， XML 文檔的基本組成單位是元素，元素又包括元素本身和元素屬性，元素名稱、元素內(nèi)容對應(yīng)于元素本身，屬性名稱、屬性內(nèi)容對應(yīng)于屬性。和普通文本文檔相比， XML 文檔具有 “ 自描述 ” 、 “ 樹形結(jié)構(gòu) ” 、 “ 結(jié)構(gòu)嵌套 ” 等特點。隨著 XML 在數(shù)據(jù)挖掘、分類聚類、數(shù)據(jù)交換、內(nèi)容管理、 Web服務(wù)等方面的廣泛應(yīng)用，如何高效的解決 XML 語義相似度的測量方法，成為人們普遍關(guān)注的一個焦點。 基于語義相似性計算 XML 文檔的語義相似性 通過上一節(jié)的論述我們知道， XML 文檔的內(nèi)容是以元素節(jié)點為基礎(chǔ)的樹形結(jié)構(gòu)。那么，我們很容易產(chǎn)生下面一種假設(shè)：語義相似的 XML 文檔首先結(jié)構(gòu)是相似的。以 圖 41 為例，因為子樹 ACF 和子樹 ABD 的結(jié)構(gòu)是相似的， ABDE 和ACFG 的結(jié)構(gòu)是相似的，因此只需分別比較這兩對子樹的相似性。然而，通過比較我們發(fā)現(xiàn)，子樹 ACF 和 ACFG 的語義更相似，子樹 ABDE 和 ABD 的語義更相似。因此，以結(jié)構(gòu)相似性作為評判語義相似性的先決條件是不可取的。 圖 41 相似度比較 范例圖 那么， XML 文檔的結(jié)構(gòu)對語義的比較有幫助嗎？答案是肯定的，我們以對天津大學 2021屆本科生畢業(yè)設(shè)計（論文） 14 應(yīng)層之間的節(jié)點作比較，而不是將文檔 A 中的一個節(jié)點和文檔 B 中的所有節(jié)點作比較。以下圖為例，我們發(fā)現(xiàn)兩顆樹的第一層對應(yīng)于第一層，第二層對應(yīng)于第二層 ?? 因此只需將第一層的節(jié)點和第一層的節(jié)點作比較，將第二層的節(jié)點和第二層的節(jié)點作比較 ?? ，因此我們總結(jié)出 XML 文檔比較的第一步：尋找文檔 A在文檔 B 中的匹配層。 當 比較到第三層時我們發(fā)現(xiàn)，需要將 D 分別和 d， f， g 做比較；再將 E 分別和 d， f， g 做比較 ?? 這仍然是一個浩大的工程。但是，在第二層比較是，我們已經(jīng)發(fā)現(xiàn) B 和 b 相似， B 和 c 不相似，那么有必要將 B 的子節(jié)點和 c 的子節(jié)點作比較嗎？因此，我們改進算法得到： ● 計算根節(jié)點的相似度值； ● 將父節(jié)點匹配的子節(jié)點進行比較，尋找最匹配子根節(jié)點； ● 重復上述過程，直至遍歷所有節(jié)點。 仍然以上圖為例， 第一步，找到最匹配根節(jié)點 A 和 a； 第二步，比較 A 和 a 的子節(jié)點，找到最匹配子根節(jié)點 B 和 b， C 和 c； 第三步，比較 B 和 b 的子節(jié)點，找到 最匹配子根節(jié)點 D 和 d， D 和 d 均為葉節(jié)點，遍歷結(jié)束； 第四步，比較 C 和 c 的子節(jié)點，找到最匹配子根節(jié)點 F 和 f， F 和 f 均為葉節(jié)點，遍歷結(jié)束。 這一算法被命名為尋找最匹配子根節(jié)點算法。 然而，計算兩個 XML 文檔的語義相似性需要輸出一個數(shù)值來評價文檔的相似程度，但尋找最匹配子根節(jié)點算法并沒有給出這一結(jié)果。一個直觀的想法是用匹配的結(jié)點個數(shù)除以總結(jié)點個數(shù)來衡量相似程度。這里默認每一個節(jié)點對相似度的貢獻是相同的。實際情況是，根據(jù) XML 文檔的樹形結(jié)構(gòu)，處于上層的節(jié)點應(yīng)該更具有普遍性、總結(jié)性、概要 性。以上圖為例，圖 1 和圖 2 的根節(jié)點相同，葉節(jié)點完全不同；圖 1 和圖 3 的根節(jié)點不同，葉節(jié)點卻完全相同；哪兩棵樹更相似呢？顯然是圖 1 和圖 3，因為它們描述的都是動物學的知識。由此可見，上層節(jié)點對相似度的貢獻大于下層節(jié)點對相似度的貢獻。合理的計算 XML 文檔相似度的方法是，用相似節(jié)點的權(quán)值和除以所有節(jié)點的權(quán)值和。由此，給出計算 XML文檔每一個節(jié)點相似度的計算公式： 1( ) ( , )()nS n s im m nN u m n??? (41) 1(1 )nn? ? ? ??? (42) 其中 為經(jīng)驗參數(shù)， 為目標文檔中節(jié)點 n 和參照文檔中節(jié)點 m 的語義相似度，天津大學 2021屆本科生畢業(yè)設(shè)計（論文） 15 節(jié)點 m 為參照文檔中的對應(yīng)節(jié)點。 重新整理尋找最匹配子根節(jié)點算法的： 第一步，計算根節(jié)點的相似度值 ； 第二步，將父節(jié)點匹配的子節(jié)點進行比較，計算每一個節(jié)點的相似度值 S(n)并記錄； 第三步，尋找最匹配子根節(jié)點，即 MAX[S(n)]； 第四步，重復上述過程，直至遍歷所有節(jié)點； 第五步，累加所有節(jié)點的相似度值 即為文檔的相似度值。 通過公式 11 可知，若兩個文檔完全相似，則相似度取值為 1，若兩個文檔完全無關(guān)，則相似度取值為 0，即最終輸出的取值結(jié)果規(guī)約到了 [0,1]。這里，我們以 為基礎(chǔ)計算兩個節(jié)點相似度，而 是一種計算兩個概念語義相似性的算法，因此尋找最匹配子根節(jié)點算法是一種基于語義相似性計算 XML文檔的語義相似性的算法。 兩種概念相似性測量方法的選擇 在上一節(jié)中我們指出，尋找最匹配子根節(jié)點算法是一種基于語義相似性計算XML 文檔相似性的算法，但并沒有給出 ( , )simmn 的具體算法。結(jié)合本體 WordNet下文給出了兩種 ( , )simmn 算法。 根據(jù) WordNet 的組織特點，其結(jié)構(gòu)基礎(chǔ)為概念，也即同義詞集合。表示相同概念的同義詞構(gòu)成一個集合，成為樹形結(jié)構(gòu)中的一個節(jié)點。也就是說，因為單詞通常是多意的，同時一個概念可能由多個單詞表達，所以同一個單詞可能出現(xiàn)在多個同義詞集合中，而一個同義詞結(jié)合可能包含多個單詞。 這樣，有一種直接測量兩個概念語義相似性的方法：判斷兩個單詞是否出現(xiàn)在同一個同義詞集合中，若是，則兩個單詞相似，反之，兩個單詞不相似。這 種測量方法的優(yōu)點是測量簡單，操作易行。但缺點也是明顯的，兩個單詞的相似度值是二元的，不是零就是一。 為了克服二元性，在第三章，本文提出了一種測量概念語義相似性的新方法，參見 節(jié)。根據(jù)這種方法，我們將兩個單詞的相似度值規(guī)約到了區(qū)間 [0,1]。相對于方法一，這用方法的一個明顯缺點是計算復雜度的增高，但顯然，這是計算精度不可避免的犧牲。那么，這兩種方法的本質(zhì)區(qū)別是，方法一測量的是單詞的語義相似性，這是無異議的，而方法二在某種程度上可以說測量的是單詞的語義相關(guān)性。雖然方法二的基本思想是通過兩個概念的共有信息量判 斷其相似程度，但我們都知道，無論什么物體，只要是生活在地球上的，其基本組成元素都是相天津大學 2021屆本科生畢業(yè)設(shè)計（論文） 16 同的，都可以歸結(jié)為 “ entity” ，因此即使 “ 文具盒 ” 和 “ 人類 ” 這兩個看起來毫不相關(guān)的單詞，其相似度也不可能是零。任何有關(guān)系的兩個單詞，它們的相似度都不可能為零，即使這中關(guān)聯(lián)是微乎其微的。這和一些人的預(yù)期是相左的。這種方法在某種程度上也可以說是基于概念相關(guān)性的語義測量方法。 因此，當我們需要的語義相似性是狹義的相似性是，應(yīng)當選擇方法一；而當我們的預(yù)期是尋找兩個相關(guān)的 XML 文檔，需要的是廣義的語義相似性，那么方法二就是一個非常 好的選擇。 XML 文檔語義相似性測量的其他問題 目前為止，本文提供了一種測量 XML 文檔的方法：尋找最匹配子根節(jié)點算法。該算法的一個子問題是：需要選擇合適的概念語義相似度算法，在 節(jié)詳細闡述了兩種算法的優(yōu)缺點，并提供了選擇標準。但在執(zhí)行算法之前，還有一些小問題需要處理。 通常 XML 文檔的節(jié)點內(nèi)容都是由單詞和短語構(gòu)成的，這也為我們通過概念語義相似度比較文檔節(jié)點的語義相似度提供了可能。然而，許多文檔節(jié)點的內(nèi)容都是有 “ 本地特色 ” 的，比如 “ stu_book” ，可能是 “ student book” 的意思，也可能是 “ book of study” 的意思，這需要結(jié)合說明文檔進行預(yù)處理。本文將需要做預(yù)處理的情況作出如下總結(jié)： ● 大小寫轉(zhuǎn)換，將大寫字母統(tǒng)一轉(zhuǎn)換為小寫字母； ● 連拼詞組，比如 “ studentbook” ，進行分詞； ● 去掉無意義符號，比如 “ 、 /” 等等； ● 根據(jù)說明文檔將縮略詞恢復為完整詞匯。 將這些工作統(tǒng)稱為預(yù)處理，則尋找最匹配子根節(jié)點算法可進一步完善為： 第一步，對 XML 文檔中的每一個元素進行預(yù)處理； 第二步，將 XML 文檔轉(zhuǎn)化為樹形結(jié)構(gòu)； 第三步， 使用 ( , )simmn 算法， 計算根節(jié)點的相似度； 第四步，將父節(jié)點匹配的子節(jié)點進行比較，計算每一個節(jié)點的相似度值 S(n)并記錄； 第五步，從子節(jié)點中尋找最匹配子根節(jié)點，即 MAX[S(n)]，作為新的根節(jié)點； 第六步，重復三、四步過程，直至遍歷所有節(jié)點；