一種基于多字互信息與鄰接熵的改進新詞合成算法

王欣

（重慶師范大學(xué)計算機與信息科學(xué)學(xué)院，重慶 401331）

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)不斷改變著人類的交流方式和表達方式，因此，產(chǎn)生了大量的新詞。作為大數(shù)據(jù)時代最熱門的社交網(wǎng)絡(luò)媒體，微博成為了互聯(lián)網(wǎng)上新詞誕生和高速流傳的重要平臺。因為對新詞的識別不夠充分，很大程度上影響了中文分詞的準確性。所以，基于微博短文本的新詞發(fā)現(xiàn)具有十分重要的研究意義與價值。

雖然現(xiàn)在對于新詞的研究已經(jīng)逐漸深入，但是關(guān)于新詞的界定還沒有一個準確的定義。目前，主流的新詞概念有兩種，未登錄詞和新詞。未登錄詞（Unknown Word）是指沒有收錄在詞典中的詞語[1]；新詞（New Word）是指隨著時代的發(fā)展而出現(xiàn)的具有新的構(gòu)詞規(guī)則、新的使用方法或新的意義的詞語[2]。

新詞發(fā)現(xiàn)的方法按處理的候選字符可以分為：基于重復(fù)字符串的方法和基于分詞的方法。基于重復(fù)字符串的方法是先從語料中按不同長度依次切割得到候選字符串，然后再判斷候選字符串是不是新詞?；诜衷~的方法則是在對預(yù)料進行分詞的基礎(chǔ)上，在切分成多個詞的字符串中發(fā)現(xiàn)新詞。

基于重復(fù)字符串的方法簡單易懂，且容易實現(xiàn)，但是由于逐字滑動切割固定長度的字符串，會產(chǎn)生大量的重復(fù)串，效率比較低。孫立遠等人[3]采用N元遞增算法（N-gram）獲取所有2-5字組成的漢字符串作為候選字符串，用詞頻和詞語靈活度對候選詞進行過濾得到新詞。Du Y等人[4]提出了一種結(jié)合傳統(tǒng)N-gram算法和基于詞向量的相似度剪枝方法進行新詞識別。唐波等人[5]采用廣義后綴樹的數(shù)據(jù)結(jié)構(gòu)存儲字符串及其前后綴，通過構(gòu)詞能力提取候選詞。鄭家桓等人[6]用新詞的構(gòu)規(guī)則總結(jié)歸納了適用于網(wǎng)絡(luò)新詞發(fā)現(xiàn)的構(gòu)詞規(guī)則庫，取得很好的效果，但構(gòu)詞規(guī)則的制定需要大量人工標注，且可移植性比較差。Su Q L等人[7]針對微博文本特點和統(tǒng)計手段的缺陷，分析了5種經(jīng)典統(tǒng)計量，在此基礎(chǔ)上改進了鄰接熵，通過計算加權(quán)相對臨界熵，新詞抽取能力提升且對詞頻不敏感。夭榮明等人[8]提出了一種MBN-gram算法，用多個統(tǒng)計量過濾重復(fù)字符串得到候選項，基于改進互信息和鄰接熵對候選項進行擴展和過濾，從中篩選出新詞，并在不同語料規(guī)模上進行實驗，均有效可行。梁韜等人[9]根據(jù)詞語信息量特征和條件隨機場進行新詞發(fā)現(xiàn)，取得了一定的效果。邢恩軍等人[10]提出了一種基于上下文詞頻詞匯量的統(tǒng)計指標，基于改進信息熵公式和鄰接關(guān)系的字符串連接方法發(fā)現(xiàn)新詞，改善了左右信息熵在識別新詞時特征不明顯和N-gram固定滑窗缺陷。

基于分詞的方法是雖然效率有所提高，不會產(chǎn)生過多的重復(fù)串，但對分詞器的效果有較強的依賴。張華平等人[11]針對社會媒體的特征，提出一種基于條件隨機場實現(xiàn)的字符標注分詞算法，結(jié)合基于全局特征的過濾方法進行新詞識別，算法所有步驟均為線性時間復(fù)雜度，速度有所提升，實驗效果也較好。周霜霜等人[12]融合構(gòu)詞規(guī)則、改進的C/NC-value算法和條件隨機場模型進行微博新詞抽取，提高新詞識別準確率以及對低頻微博新詞的識別率。Chen F等人[13]利用條件隨機場和多個詞邊界統(tǒng)計特征進行開放領(lǐng)域的新詞發(fā)現(xiàn)。雷一鳴等人[14]采用互信息統(tǒng)計模型對最小搭配單元的候選詞進行向右擴展統(tǒng)計并去除低頻詞以獲得新詞，規(guī)避了N元重疊問題。周超等人[15]根據(jù)字符串頻率、成詞規(guī)則和鄰接域變化特性篩選新詞，在COAE2014評測任務(wù)上取得了較好的成績，但對低頻詞不友好，且垃圾串并未完全過濾。李文坤等人[16]針對分詞后的散串，結(jié)合詞內(nèi)部結(jié)合度和邊界自由度進行新詞發(fā)現(xiàn)，該方法在大規(guī)模語料上有效，但對低頻詞的識別并不是很有效。

本文在進行了相關(guān)理論研究的條件下，對新詞發(fā)現(xiàn)方法進行分析和討論。針對現(xiàn)有方法中對低頻新詞不敏感、新詞合成算法發(fā)現(xiàn)的新詞內(nèi)凝聚度不夠穩(wěn)固等問題，改進了一種結(jié)合統(tǒng)計、規(guī)則和改進的新詞合成算法發(fā)現(xiàn)新詞的方法。通過設(shè)計對比的實驗證明，這種方法能夠提高新詞發(fā)現(xiàn)的效率。

1 新詞特征選擇

判斷兩個漢字是否能構(gòu)成一個詞語，需要判斷兩個漢字之間結(jié)合的緊密程度，詞內(nèi)凝聚度可以用來衡量兩個漢字構(gòu)成詞語的可能性。詞內(nèi)凝聚度越大，表明漢字之間的結(jié)合程度越緊密，構(gòu)成詞語的可能性越大。當(dāng)詞內(nèi)凝聚度大于一定的閾值時，就可以認為它們能構(gòu)成一個詞語。

互信息是常用的表示詞內(nèi)凝聚度的統(tǒng)計量，可以用來推斷多個特征關(guān)聯(lián)程度的大小，通常用來衡量兩個信號之間的依賴程度[16]。在做文本分類時，可能會判斷一個詞和某類的相關(guān)程度，但是在計算時未必會考慮詞頻的影響。所以，在計算兩個詞語共同出現(xiàn)的概率時，更多的是使用點互信息（Pointwise Mutual Information，PMI）來度量兩個詞內(nèi)部結(jié)合的緊密程度。點互信息越大，說明詞的詞內(nèi)凝聚度越大，成為新詞或者新詞的一部分的可能性就越大。計算公式見式（1）。

其中，p(x,y)是字符x和y在語料里同時出現(xiàn)的概率；p(x)是字符x單獨出現(xiàn)的概率；p(y)是字符y單獨出現(xiàn)的概率。當(dāng)MI(x,y)?0時，表明x和y是高度相關(guān)的，他們經(jīng)常同時出現(xiàn)，字符串xy就很有可能構(gòu)成新詞；當(dāng)MI(x,y)=0時，表明x和y是相互獨立分布的；當(dāng)MI(x,y)?0時，表明x和y是互不相關(guān)分布的。

點互信息對于二元詞組的計算有很好的效果，但是對大于兩個字的多字詞如何劃分成兩部分是比較困難的，針對這個問題，本文采用多字點互信息計算公式[17]，見式（2）、式（3）和式（4）。

其中，w1…wn為多字字符串，p(w1…wn)是字符串w1…wn在語料中出現(xiàn)的概率；f(w1…wn)表示字符串w1…wn在語料里出現(xiàn)的次數(shù)；num表示語料里的總字數(shù)；avg(w1…wn)表示多字字符串不同組合的平均概率。改進后的計算公式能夠計算多字詞語之間的點互信息，本文算法所使用的是多字點互信息。

兩個漢字是否能夠構(gòu)成一個詞語，除了推斷漢字之間的結(jié)合程度外，詞語相鄰字的多樣性也是一個衡量標準。邊界自由度是指與一個字符串相鄰的所有字符種類的數(shù)量。邊界自由度越大，表示字符串的相鄰字符集合中的字符類別就越多，與該字符串相鄰的字符就越豐富多樣，那么該字符串的邊界就越明確，這個字符串成為詞語的可能性就越大。目前常用的外部統(tǒng)計量包括鄰接熵[18]和鄰接類別[19]（Accessor Variety，AV）。通過已有的對比方法發(fā)現(xiàn)鄰接熵比鄰接類別的準確率要高，所以大多數(shù)研究都是以信息熵作為衡量字符串成詞概率的外部統(tǒng)計量。

在新詞發(fā)現(xiàn)任務(wù)中，確定詞語的左邊界和右邊界的統(tǒng)計量通常是左右信息熵。一個候選詞組的左信息熵是指該候選詞組和與它左邊所有相鄰的字結(jié)合的信息熵之和，用來判斷該候選詞組的左鄰接字的多樣性。左信息熵越大，說明該候選詞組左邊相鄰的字的種類越多，那么該候選詞組成為某個詞語的左邊界的可能性越大；反之，左信息熵越小，該候選詞組左邊相鄰的字的種類越少，它不是某個詞語的左邊界的情況就越肯定，那么就應(yīng)該對該候選詞組向左擴展直到左邊界確定為止。式（5）為候選詞左信息熵的計算公式。

其中，Hleft(W)是候選詞語w的左信息熵，Cleft是候選詞w的左鄰接字集合，p(wleft|w)是候選詞w出現(xiàn)的情況下它左邊的鄰接字是wleft的條件概率。如果N(wleft)是左鄰接字wleft和候選詞w共同出現(xiàn)的概率，N(w)是候選詞w單獨出現(xiàn)的概率，p(wleft|w) 的計算公式如式（6）所示。

同理，右信息熵用來推斷詞語的右邊界，候選詞的右信息熵計算公式見式（7）。

其中,Hright(W) 是候選詞w的右信息熵，Cright是候選詞的w的右鄰接字集合，p(wright|w)是候選的詞w出現(xiàn)的情況下其右鄰接字是wright的條件概率。如果N(wright)是wright和w同時出現(xiàn)的概率，N(w)是w單獨出現(xiàn)的概率，那么p(wright|w)的計算公式見式（8）。

因此，若Hleft(W)大于指定的閾值，則左邊界確定；若Hright(W)大于制定的閾值，則右邊界確定[20]。

2 新詞合成算法

基于規(guī)則和統(tǒng)計的新詞發(fā)現(xiàn)是一種有效的新詞抽取方法，目前己經(jīng)提出了很多融合的方法，基于詞內(nèi)部凝結(jié)度和邊界自由度的新詞發(fā)現(xiàn)算法是目前比較常用的信息發(fā)掘方法，本文對該類算法進行了全面的分析，并基于此改進了適合微博新詞發(fā)現(xiàn)的方法。

現(xiàn)有的多種基于詞內(nèi)部凝結(jié)度和邊界自由度的新詞發(fā)現(xiàn)算法之間的不同之處通常體現(xiàn)在候選詞串的選擇上。一種是通過N-gram算法對文本語料進行切分，選擇頻率達到閾值并滿足條件的詞作為候選詞。N-gram算法最大的優(yōu)勢是具有語言無關(guān)性，不需要對文本語料進行語法規(guī)則和專業(yè)詞典等語言學(xué)方面的處理，對于書寫錯誤也有很強的容錯性。雖然N-gram算法簡單易實現(xiàn)，但是效率并不高，不適合針對規(guī)模較大的文本進行新詞挖掘。另一種是利用分詞工具對文本語料進行分詞，統(tǒng)計分詞后的文本中散串，針對散串進行新詞發(fā)現(xiàn)。所謂散串，是指經(jīng)過分詞軟件分詞以后，連續(xù)多個單字（不包括標點符號）組成的字符串[16]。雖然大多數(shù)新詞都以散串的形式出現(xiàn)，但是個別詞會被分詞工具切分成雙字或多字的形式，影響新詞識別的召回率。常用的新詞發(fā)現(xiàn)算法流程如圖1所示。

圖1 新詞合成算法流程

考慮到現(xiàn)有的基于詞內(nèi)部凝結(jié)度和邊界自由度的新詞發(fā)現(xiàn)算法存在的不足之處，為了改善更多新詞存在的情況以及對結(jié)合后的新詞內(nèi)凝聚度不充足的問題，本文在NLPIR分詞工具[21]對已經(jīng)預(yù)處理好的語料進行分詞后，采用改進的新詞合成算法對全文進行新詞發(fā)現(xiàn)，改進的新詞合成算法的算法流程如圖2所示。

圖2 改進新詞合成算法流程

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

①實驗數(shù)據(jù)

語料：本實驗選用的是NLPCC2014任務(wù)1提供的評測數(shù)據(jù)，其中情緒表達抽取子任務(wù)的訓(xùn)練集包含1000條微博，共3454個句子；測試集包含10000條微博，共36005句。

符號過濾表：利用正則表達式從語料中挑選的標點符號和特殊符號。

標準新詞集：從訓(xùn)練語料中人工抽取新詞，作為標準新詞集。在本研究任務(wù)中，新詞是指有一定使用頻率、被分詞工具切分錯誤且不在常用詞典中的未登錄詞。本文人工標注了該數(shù)據(jù)集中情緒表達抽取子任務(wù)訓(xùn)練集的新詞共150個。

工具：NLPIR分詞工具、Python3.6。

②評價指標

對于新詞發(fā)現(xiàn)任務(wù)的訓(xùn)練集，采用PRF值即正確率（Precision）、召回率（Recall）和 F 值（F-measure）來評價各個新詞發(fā)現(xiàn)的性能，PRF計算公式如下：

其中，GN表示新詞發(fā)現(xiàn)方法正確識別出來的新詞個數(shù)，N表示新詞發(fā)現(xiàn)方法識別出的詞語總數(shù)，M表示在語料中人工標注的新詞總數(shù)。

③新詞合成算法對比實驗

根據(jù)上一部分實驗的分析，在語料庫上進行實驗，將點互信息與鄰接熵結(jié)合的新詞發(fā)現(xiàn)作為基線（PMI+BE）實驗，對比多字點互信息與鄰接熵結(jié)合的新詞發(fā)現(xiàn)（nPMI+BE，即本文方法）進行對比實驗，實驗結(jié)果如表所示。

表1 新詞合成算法對比實驗

實驗結(jié)果分析：通過改變點互信息可以提高微博新詞的識別精度。本文在進行左信息熵和右信息熵計算之后，對擴展的候選詞進行二次互信息計算，可以得到詞內(nèi)凝聚度更高的候選新詞，減少因成詞概率低導(dǎo)致的錯誤結(jié)合，一定程度上提高了新詞識別的準確率。

4 結(jié)語

本文就微博新詞發(fā)現(xiàn)和新詞的情感極性判斷問題進行了研究，首先分析了現(xiàn)有新詞發(fā)現(xiàn)方法仍存在的問題，針對被分詞工具錯分成多個詞的新詞，結(jié)合多字點互信息和左右鄰接熵以及本文改進的新詞合成算法對相鄰詞進行合并，得到候選新詞；再對候選新詞集合進行低頻詞、首尾停用詞、構(gòu)詞規(guī)則、常用詞典等規(guī)則與統(tǒng)計相結(jié)合的過濾方法，去除不符合要求的字符串，最后得到新詞集合。并通過在NLPCC2014會議任務(wù)提供的評測數(shù)據(jù)上的新詞發(fā)現(xiàn)對比實驗驗證了該方法的可行性和有效性。但同時，本文方法還有一些需要改進的地方，可以深入分析新詞識別中的結(jié)果錯誤，多角度分析與總結(jié)結(jié)合錯誤的字符串的特點與規(guī)律，找到更通用的過濾方法。發(fā)掘更多的統(tǒng)計量特征，提出新的統(tǒng)計算法，找到有效的方法實現(xiàn)對新詞快速準確的抽取，以及探尋新的新詞發(fā)現(xiàn)方法，提高新詞發(fā)現(xiàn)的效率。

參考文獻：

[1]Ling G C,Asahara M,Matsumoto Y.Chinese Unknown Word Identification Using Character-Based Tagging and Chunking[J].Proceedings of Annual Meeting on Association for Computational Linguistics,2003：197-200.

[2]鄒綱,劉洋,劉群,等.面向 Internet的中文新詞語檢測[J].中文信息學(xué)報,2004,18（6）：1-9.

[3]孫立遠,周亞東,管曉宏.利用信息傳播特性的中文網(wǎng)絡(luò)新詞發(fā)現(xiàn)方法[J].西安交通大學(xué)學(xué)報,2015,49（12）：59-64.

[4]Du Y,Yuan H,Qian Y.A Word Vector Representation Based Method for New Words Discovery in Massive Text[J].Springer International Publishing,2016,10102：76-88.

[5]唐波,陳光,王星雅,王非,陳小慧.微博新詞發(fā)現(xiàn)及情感極性判斷分析[J].山東大學(xué)學(xué)報（理學(xué)版）,2015,50（01）：20-25.

[6]鄭家恒,李文花.基于構(gòu)詞法的網(wǎng)絡(luò)新詞自動識別初探[J].山西大學(xué)學(xué)報（自然科學(xué)版）,2002（02）：115-119.

[7]Su Q L,Liu B Q.Chinese New Word Extraction from MicroBlog Data[C].International Conference on Machine Learning and Cybernetics.IEEE,2014：1874-1879.

[8]夭榮朋,許國艷,宋健.基于改進互信息和鄰接熵的微博新詞發(fā)現(xiàn)方法[J].計算機應(yīng)用,2016,36（10）：2772-2776.

[9]梁韜,張瑞.基于詞語條件信息量的新詞發(fā)現(xiàn)[J].電子技術(shù)與軟件工程,2014,（11）：181-182.

[10]邢恩軍,趙富強.基于上下文詞頻詞匯量指標的新詞發(fā)現(xiàn)方法[J].計算機應(yīng)用與軟件,2016,33（6）：64-67.

[11]張華平,商建云.面向社會媒體的開放領(lǐng)域新詞發(fā)現(xiàn)[J].中文信息學(xué)報,2017,31（03）：55-61.

[12]周霜霜,徐金安,陳鈺楓,張玉潔.融合規(guī)則與統(tǒng)計的微博新詞發(fā)現(xiàn)方法[J].計算機應(yīng)用,2017,37（04）：1044-1050.

[13]Chen F,Liu YQ,Wei C,Zhang YL,Zhang M,Ma SP.Open Domain New Word Detection Using Condition Random Field Method.Journal of Software,2013,24（5）：1051-1060（in Chinese）.

[14]雷一鳴,劉勇,霍華.面向網(wǎng)絡(luò)語言基于微博語料的新詞發(fā)現(xiàn)方法[J].計算機工程與設(shè)計,2017,38（03）：789-794.

[15]周超,嚴馨,余正濤,洪旭東,線巖團.融合詞頻特性及鄰接變化數(shù)的微博新詞識別[J].山東大學(xué)學(xué)報（理學(xué)版）,2015,50（03）：6-10.[16]李文坤,張仰森,陳若愚.基于詞內(nèi)部結(jié)合度和邊界自由度的新詞發(fā)現(xiàn)[J].計算機應(yīng)用研究,2015,32（8）：2302-2304.

[17]Ye Y.M,Wu Q.Y,Li Y,et al.Unknown Chinese Word Extraction Based on variety of Overlapping Strings[J].Information Processing&Management,2013,49（2）：497-512.

[18]Huang J H,Powers D.Chinese Word Segmentation Based on Contextual Entropy[C].Proceedings of the 17th Asian Pacific Conference on Language Information and Computation,2003：152-158.

[19]Feng H,Chen K,Deng X,et al.Accessor Variety Criteria for Chinese Word Extraction[J].Computational Linguistics,2004,30（1）：75-93.

[20]Thomas M.Cover,Joy A.Thomas著.信息論基礎(chǔ)（原書第2版）[M].阮吉壽,張華譯.北京：機械工業(yè)出版社,2007：9-16.

[21]張華平.漢語分詞系統(tǒng)[EB/OL].http：//www.nlpir.org/.