基于加權語義網的改進文本相似度計算方法

張弛，張貫虹，周艷玲

(合肥學院 計算機科學與技術系，安徽 合肥，230601)

隨著互聯網的普及和使用，互聯網中文本數據的產生正在以指數級的速度在增長，如何有效的管理和維護好這些文本數據，能夠實時、高效的從這些海量文本數據中挖掘對社會生產、生活有價值的信息，已經成為文本聚類、信息檢索、問答系統(tǒng)等諸多研究領域知識管理者和研究者所要亟待解決的問題。

文本相似度計算是文本數據挖掘中需要解決的關鍵問題之一。傳統(tǒng)的文本相似度計算方法是基于統(tǒng)計特征的TF-IDF算法[1-3]，該方法是將文本表示為一個空間向量的形式，向量中每個元素值為特征詞頻(term frequency,TF)和逆文本頻率(inverse document frequency,IDF)的乘積，這樣就可以通過計算向量之間的差異來衡量文本之間的相似性。這種方法的優(yōu)點簡單，并且可以排除文本中低區(qū)分度詞和高頻詞的干擾。但是這種方法也忽略了特征詞本身一般都具備豐富的語義，而且詞之間的語義關系、詞的頻率和詞的上下文結構信息等都將影響著對文本相似度計算結果的準確性[4-6]。

近年來，隨著復雜網絡科學研究的發(fā)展，在自然語言處理研究領域中也發(fā)現了小世界特性[7]，為國內外學者研究文本的相似度計算提供了新的思路。文獻[8-10]等基于語義知識庫的方法，將特征詞映射成概念或義項，通過概念或義項的語義相似性、相關度和語義距離等來間接計算特征詞之間的相似度，并通構建加權文本復雜網絡，使用復雜網絡的物理結構特征如節(jié)點度、介數、聚集系數等，進行關鍵詞的提取研究。文獻[11-12]根據特征詞之間的語義關系構建文本復雜網絡，然后利用復雜網絡社區(qū)的結構特性，使用社區(qū)挖掘算法來進行特征選擇。文獻[13-14]引入相似性和相關性對詞語語義關系進行復雜網絡構建，通過調節(jié)各個參數的分配權重進行特征項選擇。雖然這些研究已經取得較好的成果，但它們都未考慮節(jié)點對全局網絡的影響，忽略了在文本復雜網絡中特征詞的位置、共現頻率、全局統(tǒng)計信息等因素的重要性，導致文本網絡構建中邊權重計算方法不科學，結果不準確，使得最終計算結果存在較大偏差。

鑒于特征詞本身具備的豐富語義特征，文章在綜合考慮了特征詞間的語義相似性、統(tǒng)計TF-IDF值以及共現頻率等因素的基礎上，提出了一種基于《知網(HowNet)》語義知識詞典的改進文本加權語義網絡構建和相似度計算方法。該方法首先對文本進行分詞、去停用詞操作，以特征詞為節(jié)點，以特征詞的TF-IDF值作為節(jié)點的初始權重，以特征詞窗口共現與窗口滑動原理建立邊，基于《知網(HowNet)》語義詞典將特征詞映射為詞典中的概念，考慮到特征詞在文本中的共現系數，融合共現系數和概念間語義距離計算特征詞之間邊的權重，充分利用了文本的結構信息和全局統(tǒng)計信息。最后使用EMD距離公式計算向量化文本之間的相似度，在標準數據集上對文本進行分類實驗，驗證了文中所構建的算法相較于傳統(tǒng)算法，在聚類結果上得到了進一步的提升。

1 相關理論

1.1 復雜網絡特性

復雜網絡是指在結構、節(jié)點類型和連接形式等方面復雜的網絡，該類網絡具有明顯小世界、無標度等特征[15]。在復雜網絡中不同的統(tǒng)計量能夠反映不同的物理含義，對復雜網絡結構拓撲的分析，能夠剖析系統(tǒng)演化的過程和內部存在的機制，文中主要使用如下的復雜網絡物理統(tǒng)計特征量對節(jié)點的重要性進行評估。

1)節(jié)點加權度

根據邊權值是否存復雜網絡在可分為無權網絡和加權網絡，節(jié)點的度是在無權網絡的基礎上定義的，是指與節(jié)點相連邊的數量，反應了節(jié)點與其他鄰接節(jié)點的連接情況。在加權網絡中節(jié)點的加權度需是指與節(jié)點相連的節(jié)點之間邊權值之和，節(jié)點的加權度可定量的表示為

(1)

其中:ωij表示加權復雜網絡中節(jié)點i和j之間邊的權值，節(jié)點加權度綜合考慮了在加權復雜網絡中節(jié)點與相鄰節(jié)點之間邊的數量和權重，體現了節(jié)點在網絡中的局部重要性信息。

2)節(jié)點加權聚集系數

聚集系數是定義在節(jié)點三點組基礎上，對于任意一個節(jié)點，聚集系數反映了在復雜網絡中節(jié)點聚集情況，即節(jié)點的鄰接節(jié)點之間有邊的數量與它們可能存在邊的數量的比值，可定量的表示為

(2)

其中：ki表示節(jié)點i的加權度；WKi為節(jié)點i的加權聚集系數，值為節(jié)點i的相鄰節(jié)點之間邊的權值之和，體現了復雜網絡中節(jié)點間的連接強度和密度，體現了節(jié)點在加權復雜網絡中的局部重要性信息。

3)節(jié)點介數

節(jié)點介數定義為在加權復雜網絡中，任意兩個節(jié)點之間經過特定節(jié)點的最短路徑數量占所有最短路徑數量的比例。節(jié)點介數反映了節(jié)點在網絡連通中起到的作用，節(jié)點介數可定量表示為

(3)

其中：njk表示節(jié)點j和k之間的最短路徑數量；njk(i)表示在節(jié)點j和k之間存在的最短路徑中經過節(jié)點 i的路徑數量。從公式(3)的定義可以看出，節(jié)點介數體現了節(jié)點在加權復雜網絡中的全局重要性信息，

1.2 加權語義網

語義網是一個語義網絡系統(tǒng)，它系統(tǒng)的描述了現實中詞匯與詞匯之間的各種語義關系[16]。因為詞匯之間一般都具有豐富的語義關系，傳統(tǒng)的直接計算文本特征詞之間的語義關系是很困難的。目前，常用兩種方法對特征詞進行語義關系的計算，一種是基于大規(guī)模語料庫的方法[17]，一種是基于世界知識的方法[18]，考慮到前者需要大量的語料作為訓練集，使用中經常受到語料庫規(guī)模的影響。文中選擇了使用基于世界知識的《知網(HowNet)》語義詞典進行語義復雜網絡的構建，這種方法相對前者更加簡單、有效。借助《知網(HowNet)》語義知識詞典，將特征詞轉化為知識詞典中的概念，這樣每個特征詞都將對應于《知網(HowNet)》知識庫中的特定的概念。這樣就可以使用概念之間的距離來間接度量特征詞之間的語義聯系，能夠區(qū)別出不同文本特征詞之間的語義相似性和差異性。借鑒文獻[14]在概念層面上對距離的計算，文中對概念間距離的計算也使用語義距離、語義重合度、層次關系三個因素，利用概念間語義距離作為對應特征詞之間關系強弱的衡量標準。如圖1所示為基于《知網(HowNet)》語義詞典的概念距離計算案例。

圖1 語義詞典中概念的距離計算案例Fig.1 A case of concept distance computation in semantic dictionary

語義距離：表示為在《知網(HowNet)》語義詞典中兩個概念之間的最短路徑長度，文中用D(Si，Sj)表示兩個概念Si和Sj之間的語義距離，值越小表示兩個概念所對應特征詞的間關系就越相近，以圖1中節(jié)點S8和S4為例，D(S8，S4)=3。

語義重合度：表示為兩個概念所擁有的共同父節(jié)點與祖先節(jié)點的數量，擁有的共同父節(jié)點數量越多，說明概念間關系越相近。使用C(Si，Sj)表示概念Si和Sj之間的語義重合度。以圖1中節(jié)點S7和S4、S7和S8為例，C(S4，S8)=2，C(S7，S8)=3。

層次深度：用Hi和Hj表示兩個概念Si和Sj的所在語義樹中的層次深度，隨著兩個概念間的層次深度差增加，所對應詞匯之間的的相似性就越小。

2 基于改進加權語義網絡的文本相似度計算

2.1 文本特征詞之間語義相似度計算

文中綜合考慮詞匯的共現頻率權重、語義距離、語義重合度和層次深度這四個方面的因素作為語義復雜網絡中邊的權重。

共現頻率是指兩個特征詞在同一個窗口中共現的次數，共現次數越多，說明在該文本中這兩個詞匯之間的聯系也就越緊密，共現系數的計算如公式(4)所示。

(4)

其中：fij表示在文本中窗口跨度為2時特征詞i和j在同一個窗口中共現的次數；fij(k)表示特征詞i和j在第k篇文檔中共現的次數。綜上所述，文中對文獻[12]提出的特征詞相似度計算方法進行了改進，融合特征詞共現系數，提出了在語義文本網絡中特征詞間的語義相似度計算如公式(5)所示。

(5)

2.2 文本特征項的加權語義復雜網絡構建

加權語義復雜網絡可以表示為G=(N，E，W，M)。其中N表示特征詞節(jié)點的集合，N={n1，n2，…，nk}，ni表示文本復雜網絡中標號為i的特征詞節(jié)點，k表示節(jié)點集合N中元素的個數，Si表示第i個特征詞在語義詞典中對應的概念。E表示文本復雜網絡中邊的集合，E={eij=(ni，nj)|ni，nj∈N}，根據語言復雜網絡的小世界特征，定義兩個原始特征詞若共現在一個長度大小為2的窗口中，則這兩個特征詞之間就存在一條邊[5]。W表示邊的權重集合，W={w11，w12，…，wij，…}，wij表示特征詞節(jié)點i和j之間邊的權重，表示為特征詞間聯系的緊密程度。M為特征詞節(jié)點的權重，Mi表示第i個特征詞節(jié)點的權重。加權語義網的具體構建步驟如下：

1)對文本進行分詞和去停用詞后，統(tǒng)計特征詞的TF-IDF值，作為特征詞節(jié)點的初始權重。

2)按照標點符號對文本進行句子識別，在句子中定義窗口大小為2，構建特征詞節(jié)點間的邊。

3)使用語義詞典對特征詞進行概念映射，以特征詞的TF-IDF值作為特征詞節(jié)點的權重，以文中3.1節(jié)介紹的文本特征詞間語義相似度計算方法作為邊權值。

2.3 文本特征項權值計算

在文本復雜網絡中，特征節(jié)點的重要性評估往往需要綜合考慮各種指標，鑒于此，文中改進了文獻[9]提出的特征節(jié)點重要性評估函數，在復雜網絡特征基礎上，又考慮了特征詞的統(tǒng)計量，對特征節(jié)點的權重評估函數進行了改進，改進后的文本特征詞權重計算如公式(6)所示。

CFi=(β1WDi+β2WCi+β3PCi)·TIFi

(6)

其中：CFi為文本中第i個特征詞的綜合特征權重指數，對WDi、WCi、PCi進行歸一化處理；TIFi表示特征詞的TF×IDF值；βi(1≤i≤3)為可調節(jié)參數，代表各個部分的權重，且β1+β2+β3=1。

2.4 文本相似度計算

傳統(tǒng)文本相似度計算方法通常經過分詞、去停用詞后，將特征詞以向量形式進行表征，然后以余弦相似度或者歐式距離公式進行衡量相似度。但是這種衡量的方法會帶來一定的語義損失，造成計算的結果存在偏差。文中引入搬土距離(earth mover’s distance，EMD)[19]來對文本的相似度進行衡量，以減少計算中存在的語義信息缺失。

該方法是為了解決貨物運輸問題而提出的，該方法假設某種物資有m個產地分別為{A1，A2，…，Am}，產量分別為{a1，a2，…,am}，n個目的地分別為{B1，B2，…，Bm}，需求量為{b1，b2，…,bn}。假設從產地i生產的物資運輸到目的地j的運輸成本為cij，運輸量為xij。目標是最小化Cost(A，B)，使最終的運輸成本最小化。

(7)

借鑒該模型思想，可以把測試集中的文本特征詞當做物資產地，詞的權重作為運輸量，訓練集中文本特征詞作為目的地，詞的權重作為需求量，特征詞間的相似度作為運輸成本，那么將測試集中一個文本全部特征詞映射到訓練集中任意一個文本，所經距離總和的最小值作為文本之間的語義相似度。

(8)

相應的約束條件為

(9)

(10)

其中：Tij≥0表示文本D中的特征詞wi流向文本D′中特征詞wj的數值。其中c(wi，wj)為兩個特征詞wi和wj的語義相似度，dwi=CFi，dwj=CFj為特征詞wi和wj在各自文本中的權重評估函數值。

2.5 算法流程

使用文中所提出的文本復雜網絡構建和特征詞權重計算方法，對文本的特征詞進行特征權重計算，提高文本相似度計算結果的精度，算法描述如下：

輸入：帶有類標簽的訓練文本集 D1 和測試文本集 D2。

輸出：帶有類標簽的測試文本集 D2。

1)對訓練集D1和測試集D2分別進行分詞和去停用詞操作，得到初始訓練集和測試集特征詞集合。

2)按照3.2節(jié)介紹的方法分別對訓練集D1中和D2進行加權語義網絡構建。

3)對訓練集D1中每篇文檔的特征詞，基于構建的加權語義網絡計算綜合特征指數CFi，并選取CFi排名靠前的m個特征詞作為該文檔的特征集，形成訓練集數據詞典。

4)對測試集中的每篇文檔，按照步驟3的方法計算待分類的測試集數據字典。

5)根據步驟(4)得到的待分類測試集數據字典的每個文檔特征集，使用公式(8)計算其與訓練數據字典中的每一個文檔的相似度，選取訓練集中相似度最大的標簽作為該文本的標簽。

6)對測試集 D2中的每個文檔特征向量，循環(huán)重復步驟(5)，直到測試集中的每篇文檔都確定一個類別標簽為止。

3 實驗驗證分析

3.1 實驗數據及方法

文中實驗環(huán)境使用的是64位win7操作系統(tǒng)，CPU是Intel(R)Core(TM)i5-7200U@2.50GHz 2.60GHz，內存為8G，開發(fā)工具為jupyter notebook下的Python3.7，分詞軟件使用北大最新開源分詞工具pkuseg-python，實驗數據選取復旦大學李榮陸課題組提供的中文新聞語料作為測試數據集，從中選取農業(yè)、政治、經濟、體育和環(huán)境五個類別，每個類別中各隨機選取800篇。選取哈爾濱工業(yè)大學的中文停用詞表，包含767個停用詞，并使用《知網(HowNet)》計算中文特征詞之間的相似度。

文中設置了兩組實驗，第一組為三種算法在同一個數據集上的對比實驗，驗證不同文本表示對相似度計算結果的影響；第二組實驗使用三種不同的距離度量方法，分析不同距離度量對聚類結果的影響。

3.2 實驗評價方法

F1值是對分類結果的綜合評價指標，F1值綜合考慮了查全率(precision,P)和查準率(recall,R)，是兩者的加權平均，其值越大表明分類的效果就越好，定義如公式(11)、(12)所示。

(11)

(12)

其中：a表示被正確分類的文檔數量；b表示被判定為屬于某個類別實際卻不屬于該類別的文檔數量；c表示被判定不屬于某個類別實際卻屬于該類別的文檔數量。

3.3 實驗結果與分析

3.3.1 不同文本表示的相似度計算結果

為了驗證本算法的可行性，第一組實驗使用三種算法進行對比實驗，分別是文中所提出的基于加權語義的方法、文獻[12]提出的基于復雜網絡特性的方法和文獻[1]提出的基于向量空間模型的方法，三種方法分別標記為：N-EMD-1、N-NET-2、N-VSM-3。實驗中公式βi采用文獻[8]的取值，即β1為0.4、β2為0.3、β3為0.3，特征維數取值為1 200，實驗時采用 5 折交叉驗證法，取這五次的F1平均值作為最終的分類結果。三種實驗的文本聚類結果在各類別中的F1值和平均值如表1所示。

表1 三種算法的實驗F1值結果對比

Table 1 The experimental result comparison of F1 values in three algorithms

類別實驗F1值/%N-EMD-1N-NET-2N-VSM-3農業(yè) 88.8387.6585.66政治 84.7783.4281.78經濟 86.5484.1082.12體育 86.8985.7082.23環(huán)境 87.6383.7283.64平均值86.9284.9283.09

將實驗結果的F1平均值繪制成柱狀圖，如圖2所示。

圖2 三種算法的結果對比Fig.2 The experimental result comparison of F1 values in three algorithms

從表1和圖2可以看出，三種實驗的結果呈現遞減趨勢，原因是實驗N-VSM-3是基于傳統(tǒng)統(tǒng)計的方法，該方法只考慮了詞語出現頻率信息，未考慮到詞語之間的語義信息和結構信息；實驗N-NET-2雖然是基于加權語義復雜網絡的方法，但是該算法未充分考慮詞語之間的語義信息，以及特征詞的共現因素，并且需要調節(jié)的參數較多，增加了算法的時間復雜度。文中提出的N-EMD-1算法，綜合考慮了詞頻、詞共現頻率特征，并且使用了EMD距離計算方法，保證了文本之間詞語的是映射到語義最相近的詞語，避免了實驗N-NET-2綜合權值相加取均值造成的結果偏差，最大程度保證了語義的集中，實驗結果表明文中所提方法相較傳統(tǒng)方法得到了一定的改進。

3.3.2 不同距離度量對文本相似度計算的影響

文章設置了第二組實驗，以驗證不同相似度度量公式對文本聚類最終結果的影響，分別是EMD距離公式、余弦相似度和歐式距離三種距離度量方法進行實驗對比，觀察它們對文本聚類結果的影響，三種距離度量分別記為N-EMD、N-Cos和N-ED。特征詞向量采用全部特征詞，向量元素值為對應特征詞在文本中的綜合特征指數，數據使用第一組實驗選擇的五個類別的文本，評價指標為公式(11)和公式(12)中的查全率、查準率和F1值三個指標，實驗結果見表2。

表2 不同距離度量的F1值結果對比

Table 2 The result comparison of F1 values of different distance metric

方法P/%R/%F1/%N-EMD84.3889.0286.64N-ED78.6576.2677.44N-Cos72.8164.6968.51

從表2的測評結果可以看出，文中使用的EMD距離方法比其他兩種相似度度量方法要好，這是因為EMD距離方法在計算相似度時充分考慮了詞語之間的相似性，而不是特征詞語之間相似度的簡單疊加，在一定程度上保留了文本的結構信息，縮小了文本間的語義差異性，提高了聚類結果。

4 結語

文章提出了一種改進的加權語義復雜網絡文本相似度計算方法，首先利用文本的統(tǒng)計信息，融合特征詞的共現頻率和語義距離特性，構建加權語義復雜網絡；其次基于該語義網絡，結合復雜網絡的相關特性計算文本的特征詞綜合指數；再次根據綜合特征指數值的大小，對特征項向量進行選降維處理，使用EMD距離公式對文本進行相似度計算；最后通過對不同算法和不同距離度量公式的實驗結果對比分析，驗證了文中所提出的方法能夠充分利用文本網絡中特征詞節(jié)點間的語義信息、結構信息和統(tǒng)計信息，提高相似度計算結果的準確性。但是鑒于文本相似度計算的復雜性，本研究還有一定的局限性，例如特征詞詞性、詞語以及詞語與句子的關系等因素，還都有待于進一步的研究。