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