趙明月

(河南大學計算機與信息工程學院，河南 開封 475004)

0 引言

文本相似度的度量就是衡量兩個文本之間語義相似的程度，是自然語言處理中一個非常重要的任務。

早期的文本相似度研究多側(cè)重于長文本，比如文檔或段落等[15]。然而近年來，由于微博平臺上大量短文本的出現(xiàn)，對短文本相似度度量的研究吸引了很多研究者進行了深入而廣泛的關(guān)注。例如pilehvar等[12]通過尋找文本的語義指紋，進而比較兩個語義指紋的差異性來判斷文本的相似度，Yazdani等[13]利用維基百科生成一個概念網(wǎng)絡，通過計算由概念網(wǎng)絡中生成的文本各自的語義概念的相似度，來計算文本間的相似度。其中 Matt等[14]人提出的 Word Mover’s Distance（WMD）算法，為求解兩條微博的相似度開辟了新思路，取得了較好的效果。

WMD是一種新的計算文本文檔距離方法，是將Earth Mover’s Distance(EMD)和詞嵌入結(jié)合起來，用來度量兩個文檔之間的語義相似距離。WMD算法是在EMD算法基礎上改進得來的，這個方法第一次用運輸距離的思想解決了自然語言中如何對文本內(nèi)容進行歸類的問題。

雖然WMD算法使用EMD和詞嵌入在文本內(nèi)容相似度衡量方面取得了較好的效果，但是WMD算法中所有的單詞用相同的權(quán)重，其忽略了關(guān)鍵詞在語義相似度衡量上的重要性,未考慮到詞性不同的單詞對語義相似度衡量的影響。因此本文針對WMD不考慮單詞權(quán)重問題，做出如下改進。

首先，使用TextRank[7]算法將句子中的關(guān)鍵詞提取出來，然后使用Natural Language Toolkit(NLTK)將句子中單詞標注詞性，最后根據(jù)提出權(quán)重分配算法求解不同詞性的單詞和關(guān)鍵詞的最優(yōu)權(quán)重。使用文獻[14]中的數(shù)據(jù)進行實驗表明，本文所提的方法在微博情感傾向應用中，性能優(yōu)于原始的WMD方法。

1 WMD算法的簡介

WMD算法是在對EMD(Earth Mover’s Distance)算法基礎上進行改進得到的新算法。首先簡單介紹EMD算法，EMD是一個找到運輸問題最優(yōu)解的算法，假定有P和Q兩個地方，需要將貨物從P運輸?shù)絈。兩地之間的距離定義為dij且為恒定值；從P運輸?shù)絈的物品重量定義為fij，它是運輸?shù)奈┮蛔兞坎⑾拗苀ij≥0。這樣得到運輸完所有物品的總工作量是：

從公式⑴得到P的總?cè)萘繛閃p和Q的總?cè)萘繛閃Q，則有，所以運輸總量等于P和Q的最小值

其中WMD的度量是依靠Word2Vec模型生成的高質(zhì)量和大規(guī)模的數(shù)據(jù)集中的word embedding工具實現(xiàn)的。因為自然語言是由詞來組成的，所以Word2Vec是將每一個詞表示成一定緯度的向量，如果這個詞在第三個位置出現(xiàn)，那么就將第三個位置的值設為1，其余設為0，這樣的話就可以對所有樣本進行神經(jīng)網(wǎng)絡的訓練直到收斂。收斂之后會得到權(quán)重，然后將這些權(quán)重作為每一個詞的向量，需要注意的是，在Word2Vec中使用了哈夫曼樹，這樣的話就可以根據(jù)上下文來推測這個詞的概率。

WMD的圖解如圖1所示。

圖1 WMD圖解

首先將去除停用詞的這些文字插入到Word2Vec空間里，這些文字會表示在向量空間上，稱之為Word Embeeding。從圖1可以看出，從文檔1到文檔2的距離就是將文檔1所有非停用詞移動到文檔2中詞語的最小距離的累加。

對于文檔1和文檔2，首先用nBOW將文檔P和Q中去除停用詞的單詞用向量表示，并用計算該詞的權(quán)重，其中ci表示詞語ci在文檔中出現(xiàn)的次數(shù)。

在Word2Vec向量空間中，語義相似的詞與詞之間的距離可以用歐式距離來計算，即：

這里的C(i,j)是一個詞運輸?shù)搅硪粋€詞所花費的代價。

在得到每一個單詞到單詞之間的距離之后，就可以得到整個文檔P到文檔Q之間的距離：

將累積cost最小化，有以下公式⑷：

subject to:

圖2 距離計算圖解

從圖2中可以看出，將Illinois轉(zhuǎn)換為Chicago，比Japan轉(zhuǎn)換為Chicago的代價小，因為在向量空間中，向量（Illinois）比向量（Japan）的距離小，因此能計算出哪兩個文檔之間距離較近。

WMD在實際運用中也存在一些缺點，例如在得到詞向量時，WMD算法只是單純的對所有詞隨機賦予一個權(quán)重，并不考慮詞在句子中的重要與否，這樣可能會造成對句子的分類錯誤。在原先的WMD算法中，若是隨機賦予權(quán)重，可能會將這兩句話歸為意思相近的一類，但是實際卻恰恰相反。本文對句子中的所有詞進行重新的梳理，將不同詞性的詞分門別類的賦予權(quán)重，這樣在使用WMD求解語義相似度的過程中可以將意思更為接近的句子歸為一類，提高求解相似度的準確率。

2 基于詞性的WMD算法改進

隨著社交媒體的發(fā)展，每天的新文本內(nèi)容有了爆炸式的增長，但是，這些文本內(nèi)容與傳統(tǒng)的文本內(nèi)容（新聞，小說等）有很大區(qū)別，其主要特點是，風格隨意，單詞簡寫，文法接近于口語化表達。這些特點也大大影響了自然語言處理的效率。近年來，各類自然語言處理工具的準確率下降的事件多次被提及，例如Stanford tagger[3](針對社交文本的詞性標注結(jié)果分析)準確率從97%下降到87%，詞性也稱為詞類，是詞匯在文章中最基本的語法特征，一方面，文章中許多單詞，即便是同一個單詞，在不同的語境中也有不同的意思；另一方面，文章中的關(guān)鍵詞也可以對文章進行高度概括，所以，這些詞性和關(guān)鍵詞成為了語義分類的關(guān)鍵因素。

2.1 詞性的分類及方法

在詞性分類中，現(xiàn)在有以下三種模型比較流行[4]。第一種是布朗語料庫，這種模型純粹是靠手工的方式來獲得大量的語料庫，然后對這些語料庫取樣本，并且還要靠用戶來對存在的錯誤進行勘正。第二種是隱馬爾可夫模型，在二十世紀八十年代，歐洲的研究人員通過計算單詞出現(xiàn)的可能性來得到下一個單詞的詞性。第三種是動態(tài)編程的方法，1987年，Steven DeRose[5]和Ken Church[6]獨立開發(fā)了動態(tài)規(guī)劃算法，在很短的時間內(nèi)解決同樣的問題。他們的方法類似于其他領(lǐng)域已知的Viterbi算法。DeRose使用了一個對的表格，而Church則使用了一個三元組表格和一個估算在Brown語料庫中罕見或不存在的三元值的方法（三重概率的實際測量將需要更大的語料庫）。本文根據(jù)實際情況，使用了第三種模型來處理這些問題，依托Python中現(xiàn)有的NTLK包中POS_TAG功能，對每條用戶所發(fā)的微博內(nèi)容進行單獨提取，例子如表1所示。

表2 對文本內(nèi)容的詞語進行分類

如表1所示，首先對于給定的文本內(nèi)容進行分割，然后使用NTLK工具對其去除停用詞的所有單詞進行詞性標準，從而得到給定文本內(nèi)容中名詞、形容、動詞和副詞的分類。

2.2 TextRank算法簡介和關(guān)鍵詞提取

TextRank[7]算法是在PageRank[8]基礎進行改進，在PageRank最初是用在搜索引擎上，用于搜索網(wǎng)頁的算法其基本思想是投票，在對某一個網(wǎng)頁進行排名時，首先要看有多少網(wǎng)頁鏈接到這個網(wǎng)頁，這個值稱為PR值，計算PR值的公式如下：

其中，S(Vi)是網(wǎng)頁i的中重要性（PR值）。d是阻尼系數(shù)，一般設置為0.85。In(Vi)是存在指向網(wǎng)頁i的鏈接的網(wǎng)頁集合。Out(Vj)是網(wǎng)頁j中的鏈接存在的鏈接指向的網(wǎng)頁的集合。|Out(Vj)|是集合中元素的個數(shù)。由于PageRank算法構(gòu)成的是一個無向圖，所以在PageRank算法中加入每個點的權(quán)重，就可以得到TextRank算法，其公式如下：

相比PageRank算法，TextRank算法中多了一個W作為權(quán)重值，用來表示兩個節(jié)點之間的邊連接有不同的重要程度。這樣將文章中不同重要程度的詞按照大小排列起來，得到備選關(guān)鍵詞。

在本文中，經(jīng)過實驗對比，發(fā)現(xiàn)選取前三個關(guān)鍵詞時效果最好，所以將前三個關(guān)鍵詞存入文檔備用。

2.3 權(quán)重算法的學習

對于2.1和2.2所提取出的關(guān)鍵詞和詞性不同的詞語，將這些詞語賦予新的權(quán)重，為了找到最合適的權(quán)重算法使得準確率最高，在本文中使用梯度下降算法[9]來對權(quán)重進行迭代更新。

在使用梯度算法之前，首先要對梯度進行求解，對于每一個自變量求偏導數(shù)并將其偏導數(shù)作為變量方向的坐標，梯度下降算法的公式如下：

h(θ)是要擬合的函數(shù)，J(θ)損失函數(shù)，θ是參數(shù)，要迭代求解的值。其中m是訓練集的記錄條數(shù)，i是參數(shù)的個數(shù)。

由于本文中數(shù)據(jù)量過多，對比批量梯度下降和隨機梯度下降兩種算法，發(fā)現(xiàn)采取隨機梯度下降方法來對權(quán)重進行求解效果更好。因此，公式可以改寫為：

其中，（xi,yi）是訓練集中的一個樣本。這樣的好處是可以通過隨機選取訓練集中的樣本來對權(quán)重進行求解，從而得到局部最優(yōu)解，由此可得每個樣本的損失函數(shù)，對θ求偏導得到對應梯度，來更新θ。

為了求得局部最優(yōu)解，在對函數(shù)f(x)進行求導的時候必須先選擇一個初始點并計算該點的梯度值，假定梯度的符號為?,所以對任意函數(shù)f(x,y)的梯度為：

由于本文中使用的凸函數(shù)，所以按照梯度的負方向來更新參數(shù)。假設第n次迭代后的值為xn,可得公式：

其中，α為學習率，這個值表示每次迭代變化的幅度。這個值需要人為設定，如果設定的學習率過大或過小，對于求得的局部最優(yōu)解會產(chǎn)生較大的影響。

在隨機梯度下降中，假設有兩個點a(n)和a(n+1)，從a(n)出發(fā)，到a(n+1)截止，學習率為α，可得：

其中，

因此，參數(shù)推導過程如下：

參數(shù)θ的迭代方程可表示為：

算法：權(quán)重最優(yōu)化算法

輸入：變量X，訓練樣本G

輸出：變量Y，變量θ

初始化：隨機設置α

1.For i=1 to N Do:

2.改變θ，更新

3.For i=1 to M Do:

3 實驗及其結(jié)果分析

3.1 實驗過程

為驗證上述改進算法的有效性，本文通過使用文獻[14]中的Twitter數(shù)據(jù)作為原始數(shù)據(jù)集D1。對所得的數(shù)據(jù)進行分類，提取各種所需的單詞。

也許是去年效益好的緣由，今年的園里栽了不少美人嬌花，園林的負責人說，美人蕉花是雞冠花好幾倍，難怪前些年那片土慌著。給人一種園好企業(yè)興的感覺。

為了對比實驗結(jié)果，本文在改進算法和未改進算法中使用了同一測試集，將D1的前百分之八十作為訓練集，后百分之二十作為測試集。

3.2 實驗結(jié)果分析

本章實驗中，為了對實驗結(jié)果進行衡量，選取正確率、精確率、召回率和F1值作為性能評價指標。我們將獲得轉(zhuǎn)發(fā)的目標微博記為正例，反之則記為反例。

正確率(Accuracy)：反應模型對整個樣本數(shù)據(jù)的判定能力。即對于測試集，能將正例判定為正例，將反例判定為反例的能力。

精確率(Precision)：分類器將樣本數(shù)據(jù)正確分類為正例的個數(shù)，占全部分類為正例的個數(shù)的比例。

召回率(Recall)：分類器將樣本數(shù)據(jù)正確分類為正例的個數(shù)，占整個數(shù)據(jù)集中所有正例的個數(shù)的比例。

F1值：對精確率和召回率綜合考慮得到的另一個評價指標即：

對這兩種方法進行比較，結(jié)果如表2所示。

表2 兩種算法的實驗結(jié)果比較

只加詞性不同的詞和只加形容之間的正確率，如圖3所示。

圖3 詞性不同的詞和形容之間存在時正確率

圖4 所有權(quán)重都存在時正確率

表2實驗結(jié)果顯示，在采取相同的數(shù)據(jù)集中，本文改進的WMD算法較原始的WMD算法有較為明顯的提升。

對上述實驗結(jié)果進行總結(jié)，得出以下結(jié)論。

傳統(tǒng)的WMD對于詞語權(quán)重這方面并沒有較大的涉及，只是隨機的分配給詞語權(quán)重，并未考慮到在句子中，不同詞性的詞語會對句子的意思產(chǎn)生較大的影響。

在傳統(tǒng)的WMD算法中并未考慮到否定詞對于整體句子情感走向的影響，只是單純的將否定詞與其他詞語簡單的賦予權(quán)重。

綜上所述，本文提出的改進WMD的算法可以較好地提高對于相似文本的分類，這對于自然語言處理和輿情控制等方面有較好的幫助。

4 結(jié)束語

自然語言處理中的語言分類是一個較為熱門的領(lǐng)域，在當今社會，這個領(lǐng)域可以較好地幫助人們節(jié)省大量時間，例如處理垃圾郵件，對流行程度進行預測等。本文對于傳統(tǒng)的WMD算法進行分析和整理，對其中不足之處提出改進，但本文所改進的算法仍有一些不足之處，例如在進行賦予詞權(quán)重時并未對算法進行優(yōu)化，所需要的時間太長。下一步工作將繼續(xù)優(yōu)化賦值操作，進一步減小算法耗時，提升算法運行的效率。

參考文獻(References):

[1]Yang C,Wen J.Text Categorization Based on a Similarity Approach[J].InternationalJournalofComputational Intelligence Systems,2007.29(6):1-1

[2]Kusner M J,Sun Y,Kolkin N I,et al.From word embeddings to document distances[C]//International ConferenceonInternationalConferenceonMachine Learning.JMLR.org,2015:957-966

[3]Gupta V,Joshi N,Mathur I.POS tagger for Urdu using Stochastic approaches[C]//International Conference on Information and Communication Technology for Competitive Strategies.ACM,2016:56

[4]張一哲.漢語詞類劃分與詞性標注方法的研究[D].南京師范大學碩士學位論文,2011.

[5]Aly,G.(n.d.).Tagging text with Stanford POS Tagger in Java Applications|Galal Aly.Retrieved from http://www.galalaly.me/index.php/2011/05/tagging-text-withstanford-pos-tagger-in-java-applications/

[6]Surhone L M,Tennoe M T,Henssonow S F.Steven DeRose[J].2010.

[7]Dredze M,Jansen A,Coppersmith G,et al.NLP on Spoken Documents without ASR[C]//Conference on EmpiricalMethodsin NaturalLanguage Processing,EMNLP 2010,9-11 October 2010,Mit Stata Center,Massachusetts,Usa,A MeetingofSigdat,A Special Interest Group of the ACL.DBLP,2010:460-470

[8]Haveliwala T H.Topic-sensitive PageRank:a contextsensitiverankingalgorithm forWebsearch[M].IEEE Educational Activities Department,2003.

[9]Mihalcea R,Tarau P.TextRank:Bringing Order into Texts[C]// Conference on EmpiricalMethods in Natural LanguageProcessing,EMNLP 2004,A Meetingof Sigdat,A Special Interest Group of the Acl,Held in Conjunction with ACL 2004,25-26 July 2004,Barcelona,Spain.DBLP,2004:404-411

[10]Burges C,Shaked T,Renshaw E,et al.Learning to rank using gradientdescent[C]//InternationalConference on Machine Learning.ACM,2005:89-96

[11]Mohler M,Mihalcea R.Text-to-text semantic similarity for automatic short answer grading[C]//Conference ofthe European Chapterofthe Association for Computational Linguistics.Association for Computational Linguistics,2009:567-575

[12]Pilehvar M T,Jurgens D,Navigli R.Align,Disambiguate and Walk: A Unified Approach for Measuring Semantic Similarity[C]//Meeting of the Association for Computational Linguistics,2013.

[13]Yazdani M,Popescu-Belis A.Computing text semantic relatedness using the contents and links of a hypertext encyclopedia:extended abstract[J].Artificial Intelligence,2013.194(194):176-202

[14]Kusner M J,Sun Y,Kolkin N I,et al.From word embeddings to document distances[C]//International Conference on International Conference on Machine Learning.JMLR.org,2015:957-966

[15]Chua T S,Leong M K,Myaeng S H,et al.Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval[J].1992,105(4):1227-1230