基于詞性和關(guān)鍵詞的短文本相似度計(jì)算方法

趙明月

(河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475004)

0 引言

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

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

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

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

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

1 WMD算法的簡介

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

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

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

WMD的圖解如圖1所示。

圖1 WMD圖解

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

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

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

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

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

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

subject to:

圖2 距離計(jì)算圖解

從圖2中可以看出，將Illinois轉(zhuǎn)換為Chicago，比Japan轉(zhuǎn)換為Chicago的代價(jià)小，因?yàn)樵谙蛄靠臻g中，向量（Illinois）比向量（Japan）的距離小，因此能計(jì)算出哪兩個(gè)文檔之間距離較近。

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

2 基于詞性的WMD算法改進(jìn)

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

2.1 詞性的分類及方法

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

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

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

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

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

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

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

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

2.3 權(quán)重算法的學(xué)習(xí)

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

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

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

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

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

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

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

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

在隨機(jī)梯度下降中，假設(shè)有兩個(gè)點(diǎn)a(n)和a(n+1)，從a(n)出發(fā)，到a(n+1)截止，學(xué)習(xí)率為α，可得：

其中，

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

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

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

輸入：變量X，訓(xùn)練樣本G

輸出：變量Y，變量θ

初始化：隨機(jī)設(shè)置α

1.For i=1 to N Do:

2.改變?chǔ)?，更?/p>

3.For i=1 to M Do:

3 實(shí)驗(yàn)及其結(jié)果分析

3.1 實(shí)驗(yàn)過程

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

F1值：對精確率和召回率綜合考慮得到的另一個(gè)評價(jià)指標(biāo)即：

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

表2 兩種算法的實(shí)驗(yàn)結(jié)果比較

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

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

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

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

對上述實(shí)驗(yàn)結(jié)果進(jìn)行總結(jié)，得出以下結(jié)論。

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)(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]張一哲.漢語詞類劃分與詞性標(biāo)注方法的研究[D].南京師范大學(xué)碩士學(xué)位論文,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