【正文】 本文將需要做預(yù)處理的情況作出如下總結(jié)： ● 大小寫轉(zhuǎn)換，將大寫字母統(tǒng)一轉(zhuǎn)換為小寫字母； ● 連拼詞組，比如 “ studentbook” ，進(jìn)行分詞； ● 去掉無意義符號，比如 “ 、 /” 等等； ● 根據(jù)說明文檔將縮略詞恢復(fù)為完整詞匯。 通常 XML 文檔的節(jié)點內(nèi)容都是由單詞和短語構(gòu)成的，這也為我們通過概念語義相似度比較文檔節(jié)點的語義相似度提供了可能。該算法的一個子問題是：需要選擇合適的概念語義相似度算法，在 節(jié)詳細(xì)闡述了兩種算法的優(yōu)缺點，并提供了選擇標(biāo)準(zhǔn)。 因此，當(dāng)我們需要的語義相似性是狹義的相似性是，應(yīng)當(dāng)選擇方法一；而當(dāng)我們的預(yù)期是尋找兩個相關(guān)的 XML 文檔，需要的是廣義的語義相似性，那么方法二就是一個非常 好的選擇。這和一些人的預(yù)期是相左的。雖然方法二的基本思想是通過兩個概念的共有信息量判 斷其相似程度，但我們都知道，無論什么物體，只要是生活在地球上的，其基本組成元素都是相天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 16 同的，都可以歸結(jié)為 “ entity” ，因此即使 “ 文具盒 ” 和 “ 人類 ” 這兩個看起來毫不相關(guān)的單詞，其相似度也不可能是零。相對于方法一，這用方法的一個明顯缺點是計算復(fù)雜度的增高，但顯然，這是計算精度不可避免的犧牲。 為了克服二元性，在第三章，本文提出了一種測量概念語義相似性的新方法，參見 節(jié)。這 種測量方法的優(yōu)點是測量簡單，操作易行。也就是說，因為單詞通常是多意的，同時一個概念可能由多個單詞表達(dá)，所以同一個單詞可能出現(xiàn)在多個同義詞集合中，而一個同義詞結(jié)合可能包含多個單詞。 根據(jù) WordNet 的組織特點，其結(jié)構(gòu)基礎(chǔ)為概念，也即同義詞集合。 兩種概念相似性測量方法的選擇 在上一節(jié)中我們指出，尋找最匹配子根節(jié)點算法是一種基于語義相似性計算XML 文檔相似性的算法，但并沒有給出 ( , )simmn 的具體算法。 通過公式 11 可知，若兩個文檔完全相似，則相似度取值為 1，若兩個文檔完全無關(guān)，則相似度取值為 0，即最終輸出的取值結(jié)果規(guī)約到了 [0,1]。由此，給出計算 XML文檔每一個節(jié)點相似度的計算公式： 1( ) ( , )()nS n s im m nN u m n??? (41) 1(1 )nn? ? ? ??? (42) 其中 為經(jīng)驗參數(shù)， 為目標(biāo)文檔中節(jié)點 n 和參照文檔中節(jié)點 m 的語義相似度，天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 15 節(jié)點 m 為參照文檔中的對應(yīng)節(jié)點。由此可見，上層節(jié)點對相似度的貢獻(xiàn)大于下層節(jié)點對相似度的貢獻(xiàn)。實際情況是，根據(jù) XML 文檔的樹形結(jié)構(gòu)，處于上層的節(jié)點應(yīng)該更具有普遍性、總結(jié)性、概要 性。一個直觀的想法是用匹配的結(jié)點個數(shù)除以總結(jié)點個數(shù)來衡量相似程度。 這一算法被命名為尋找最匹配子根節(jié)點算法。但是，在第二層比較是，我們已經(jīng)發(fā)現(xiàn) B 和 b 相似， B 和 c 不相似，那么有必要將 B 的子節(jié)點和 c 的子節(jié)點作比較嗎？因此，我們改進(jìn)算法得到： ● 計算根節(jié)點的相似度值； ● 將父節(jié)點匹配的子節(jié)點進(jìn)行比較，尋找最匹配子根節(jié)點； ● 重復(fù)上述過程，直至遍歷所有節(jié)點。以下圖為例，我們發(fā)現(xiàn)兩顆樹的第一層對應(yīng)于第一層，第二層對應(yīng)于第二層 ?? 因此只需將第一層的節(jié)點和第一層的節(jié)點作比較，將第二層的節(jié)點和第二層的節(jié)點作比較 ?? ，因此我們總結(jié)出 XML 文檔比較的第一步：尋找文檔 A在文檔 B 中的匹配層。因此，以結(jié)構(gòu)相似性作為評判語義相似性的先決條件是不可取的。以 圖 41 為例，因為子樹 ACF 和子樹 ABD 的結(jié)構(gòu)是相似的， ABDE 和ACFG 的結(jié)構(gòu)是相似的，因此只需分別比較這兩對子樹的相似性。 基于語義相似性計算 XML 文檔的語義相似性 通過上一節(jié)的論述我們知道， XML 文檔的內(nèi)容是以元素節(jié)點為基礎(chǔ)的樹形結(jié)構(gòu)。和普通文本文檔相比， XML 文檔具有 “ 自描述 ” 、 “ 樹形結(jié)構(gòu) ” 、 “ 結(jié)構(gòu)嵌套 ” 等特點。 所謂可擴(kuò)展是針對于 HTML 等結(jié)構(gòu)語言而言的， XML 文檔有自己的結(jié)構(gòu)特點，但對結(jié)構(gòu)的要求并不強(qiáng)，使用者可以定義自己的 XML 文檔結(jié)構(gòu)。 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 13 第四章 基于 WordNet 的 XML 語義相似性算法 XML 文檔簡介 XML（ Extensible Markup Language）的英文原意是可擴(kuò)展的標(biāo)記 語言。并從信息學(xué)的角度重新解釋了深度、邊密度，節(jié)點之間的連接強(qiáng)度這三個概念， 在此基礎(chǔ)上給出了一個新的測量概念相似性的方法。 在 節(jié)中我們提出了一個建議，采用信息理論模型，同時避免訪問語料庫。 本章小結(jié) 本章系統(tǒng)的闡述了目前概念相似性比較的主流方法，主要分為兩種，網(wǎng)絡(luò)距離模型和信息理論模型。 但相對于網(wǎng)絡(luò)距離模型，其復(fù)雜度顯然是略高的，因此，在具體的實現(xiàn)中，可以根據(jù)應(yīng)用的不同，在精度和效率之間進(jìn)行取舍。 表 31 網(wǎng)絡(luò)距離模型與本文設(shè)計算法比較 公式 節(jié)點間距離 邊密度 連接強(qiáng)度 深度 方向性 31 是 否 否 是 否 33 是 是 否 是 是 34 是 否 否 是 否 35 是 否 否 是 否 38 是 是 是 是 是 從表 31 可以看出，本文設(shè)計算法在繼承了現(xiàn)有算法優(yōu)點的基礎(chǔ)上，進(jìn)一步可慮了方向性、連接強(qiáng)度等現(xiàn)有算法沒有可慮的因素，進(jìn)一步提高了算法的精確天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 12 性。 α， β是區(qū)分相似度和非對稱性的權(quán)重而設(shè)置的參數(shù)，需要根據(jù)實驗數(shù)據(jù)不斷修改。其中前半部分中 為節(jié)點 ， 的公共祖先到根 節(jié)點的距離，即兩者的共有信息量， 為兩者之間的連接強(qiáng)度，即差異信息量，因此為通過信息學(xué)理論計算出的相似度；后半部分是為了體現(xiàn)非對稱性而編寫的輔助函數(shù) 。這樣，本文重新定義任意兩個節(jié)點 a， b 的最短路徑為任意兩個節(jié)點 a， b 之間的連接強(qiáng)度 stren（ a， b）。也就是說，父子節(jié)點之間的連接強(qiáng)度越大，取值越小，連接強(qiáng)度越小，取值越大。 算法分析 我們知道，兩個概念之間的語義距離和連接強(qiáng)度的取值是相反的，語義距離越大連接強(qiáng)度越低，為了將連接強(qiáng)度和語義距離結(jié) 合，本文擴(kuò)展了連接強(qiáng)度的概念。 ( 1 , 2) 2 * 3 / ( 1 2 2 * 3 )si m c c N N N N? ? ? (34) 然而，公式 34 它本身的缺點也是不容忽視的，公式本身并沒有 充分 考慮邊密度、連接強(qiáng)度、方向性等因素，因此， 本文給出了一個新的計算概念語義相似度的方法，它以共享信息為基礎(chǔ)，綜合考慮了深度、邊密度、連接強(qiáng)度、方向性、取值范圍等因素 ，同時避免了對語料庫的頻繁訪問 。深度：隨著深度的加深，子節(jié)點相對于父節(jié)點的變異越小，共有信息量越大，因此權(quán)值越小，距離越小，相似度越大；邊密度：隨著區(qū)域密度的增大，概念劃分的粒度越細(xì)，概念間的差異越小，距離越小，相似度越大；連接強(qiáng)度：節(jié)點之間連接強(qiáng)度越大，節(jié)點之間的繼承關(guān)系越明顯，共有信息量越大，距離越小，相似度越大。我們將本體中每一個概念進(jìn)行量化，統(tǒng)一進(jìn)行賦值，下圖就是一個賦值后的樹形結(jié)構(gòu)圖32： 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 10 圖 32 賦值后的樹形結(jié)構(gòu)圖 每個節(jié)點的信息量跟它們的深度成反比，樹的最大深度為 3，因此頂層的信息量為 3，依次向下逐個遞減。那么，如何判定兩個概念的共享信息量呢？首先，我們可以根據(jù)本體找到概念 C1 和 C2 的公共祖先 C3，即它們的共有信息為 C3， C3 占它們所有信息量的比重是多少呢，如何量化它？這里就用到了語料庫，我們通過計算 C3 在語料庫中出現(xiàn)的概率 P(C3)來衡量共有信息 C3 的數(shù)量，這樣給出一種計算相似度的方法： ( 1, 2) log ( 3 )Rsim c c p c?? (36) 這里我們只考慮了共有信息量，有人提出忽略差異信息量是不可取的，因為即使 C1 和 C2 的共有信息量很多，但也許它們的差異信息量更多，下面給出了一種考慮了差異信息量的計算方法，共享信息量越多，越相似，差異信息量越多，越不相似： ( 1 , 2 ) 2 * l o g ( 3 ) / ( l o g ( 1 ) l o g ( 2 ) )Lsim c c p c p c p c?? (37) 當(dāng)前算法存在的問題 在網(wǎng)絡(luò)距離模型中，更多的考慮 了 isa 關(guān)系，而很少考慮其他關(guān)系，這種測量也更容易讓人聯(lián)想到相關(guān)性，而不是相似性；通過信息理論模型，我們可以很好的測量兩個概念的相似性，但其對語料庫的頻繁訪問使得算法的實用性不大；兩個算法共同存在的問題是算法都是對稱性的，即測量 C1 和 C2 的相似度值和測量 C2， C1 的相似度值 所得結(jié)果 是一樣的，而實際情況是我們可以說 “ 獵犬 ”是 “ 狗 ” ，但反過來卻不行 ，兩個結(jié)果完全不同 。 由公式 4 計算出的結(jié)果是無法預(yù)知其取值范圍的，因此，有人提出了一種將取之范圍規(guī)約到 [0,1]的方法，這種方法也同時考慮了最短路徑和公共祖先： 33( , )( , ) ij NNl e n c cij ees im c c e??? ? ? ???? ? ???? ? (35) 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 9 信息理論 模型 信息理論模型是一種本體和語料庫結(jié)合的方法。（由于 WordNet 中的語義關(guān)系有許多種，這在上文中有所描述，這里只計算某種特定的語義關(guān)系，比如 isa 關(guān)系）。 其中一種最簡單的改進(jìn)是找到概念 c1 和 c2 最短路徑，并計算出 c1,c2 所在層級結(jié)構(gòu)的最大深度，并且只考慮上位關(guān)系即 isa 關(guān)系，得到相似度計算公式： 1 , 2( 1 , 2) m a x[ l og ( m in [ ( 1 , 2) ] / 2 * ) ]LC c csim c c le n c c D?? (31) 下面的方法給出了一種計算語義距離的方法，我們知道，語義距離越大，相似度越小，因此，只需要適當(dāng)變形就可以得到一種新的相似度計算方法： m a x m in( ) m a x ()rri r j rriw t c c nc?? ? ? (32) 39。 簡而言之，隨著深度的加深，權(quán)值隨之變小，概念間的距離變小；隨著邊的區(qū)域密度的增大，權(quán)值變小，概念 間距離變??；隨著父子節(jié)點連接強(qiáng)度的增大，權(quán)值變小，概念間距離變小。所謂深度，就是節(jié)點在樹中的深度；從 圖 31 我們可以看到，節(jié)點 B 所在區(qū)域邊的個數(shù)大于節(jié)點 C 所在區(qū) 圖 31 樹形 節(jié)點圖 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 8 域邊的個數(shù)，即區(qū)域密度 B 大于區(qū)域密度 C，則對應(yīng)的 BD 邊的權(quán)值應(yīng)當(dāng)小于CF 邊的權(quán)值。 為了解決這個問題，有人嘗試給不同的邊賦予權(quán)值，然而，手工賦值的辦法顯然是不可取的，應(yīng)為大型本體中的概念實在太多，完成這一工程，無異于再建一座萬里長城。這是因為“ dog”處于樹形結(jié)構(gòu)的更底層，而 tooth 處于樹形結(jié)構(gòu)的更高層，在距離相同的情況下，樹形結(jié)構(gòu)的越高層，概念越抽象，之間的差異越大，反之，樹形結(jié)構(gòu)的越底層，概念越具體，之間的差異越小。 然而，這種測量方法存在一個問題，在計算最短路徑的過程中每一條邊得權(quán)重都是相同，都為 1，這與實際情況是不相符的。 網(wǎng)絡(luò)距離模型 由于 WordNet 本身的樹形結(jié)構(gòu)以及語義距離和語義相似度之間的關(guān)系，使得計算兩個概念之間的相似度有一種非常直觀的方法，即測量表示兩個概念的節(jié)點在樹種的距離 —— 節(jié)點 A 到 B 的最短路徑。 天津大學(xué) 2021屆本科生畢業(yè)設(shè)計（論文） 7 第三章 基于 WordNet 的概念語義相似度算法 基于 WordNet 的語義相似性算法綜述 如上文所述，目前基于 WordNet 的語義相似性算法總體上分為兩類，一種直觀方法是網(wǎng)絡(luò)距離模型，即以本體所在樹形結(jié)構(gòu)中兩個概念的距離為基本指標(biāo)來衡量概念的相似程度；另一種測量方法是信息理論模型，即通過兩個概念的共有信息量來衡量概念的相似程度。當(dāng)然，它也有局限性，即本身是一本英文詞典，并不適用于中文或者其他語言。旨在說明為什么用本體可以測量語義的相似性，如何構(gòu)建本體，如何選擇本體等。上文我們已經(jīng)舉例說明，兩者相關(guān)并不一定說明兩者相似。 通過語義距離測量相似性一種直觀方法是網(wǎng)絡(luò)距離模型，即以本體所在樹形結(jié)構(gòu)中兩個概念的距離為基本指標(biāo)來衡量概念的相似程度；另一種測量方法是信息理論模型，即通過兩個概念的共有信息量來衡量概念的相似程度。 語義距離，簡而言之就是兩個概念的語義相距的距離。因此相似和相關(guān)是不同的。但在這之前，我們還要討論一下什么是