基于迭代算法的新詞識別

趙小寶，張華平

(北京理工大學計算機學院，北京 100081)

1 概述

詞是最小的能夠獨立應用的有意義的語言成分[1]，中文信息處理的特有問題即漢語分詞，漢語分詞是句法分析等深層處理的基礎，也是機器翻譯、信息檢索和信息抽取等應用的重要環節[2]，但隨著語言的不斷發展和進化，新詞開始大量出現。特別是隨著網絡技術的高速發展，新詞的產生變得更快更多，傳播也變得更快更廣，如“拼客”、“山寨”、“蟻族”、“裸婚”、“神馬都是浮云”、“給力”、“屌絲”、“高富帥”等。如果在中文分詞過程中不考慮這些新詞，不實施新詞發現，必然影響中文分詞的質量。

與英語不同，中文詞語與詞語之間沒有特定的分隔標記，任何相鄰中文字符都可能構成一個詞語；且書面語中沒有字符形態變化，這都給中文新詞自動檢測帶來了巨大障礙[3]。國內外大量科研院校和科研單位都相繼開展了新詞識別研究工作，并取得了一定的研究成果。在這些研究中，主要分為有監督和無監督的方法。大量研究實踐表明，在沒有大規模標注語料的情況下，使用無監督的方法獲得候選新詞具有對語料依賴程度小、適應能力強、新詞識別效果好等特點，因此該方法也成為新詞識別領域比較流行的研究方法。本文介紹新詞發現研究的相關工作及衡量詞語內聚性的特征，論述衡量詞語外部靈活性的特征，提出一種左鄰右平均熵和右鄰左平均熵的計算方法。

2 相關工作

眾多研究者從不同角度應用不同的方法進行了研究。利用遞增的N-Gram模型提取重復模式，在此基礎上使用手工編制的提取和過濾規則從互聯網語料中提取新詞[4]的方法，其主要思想是先統計所有二字串的頻次，然后逐步統計三字串，四字串，五字串，……，記CRF錄每一次擴展的字串以及對應頻次，到達句末或者是字串長度達到閾值時停止擴展。該方法的優點是空間復雜度低，但時間復雜度較高。在此方法的基礎上，使用正則表達式來表示過濾規則[5]，可實現任意長度新詞的檢測。另一種新詞檢測方法是采用形式化描述模型在框架下判斷是否是新詞[6]。其訓練和解碼所選用的語言知識特征包括前綴、雙字前綴、后綴、雙字后綴、串長、命名實體后綴、候選模式的出現頻率、互信息、色子系數和左、右熵等11項。結合LDCRF和semi-CRF的基于全局特征的判別模型[7]同樣被用來進行新詞識別和詞性猜測。首先利用LDCRF識別新詞候選，然后利用semi-CRF對新詞候選的Nbest進行剪枝和過濾，得到新詞。該方法加快訓練速度，縮短了計算時間。以上2種方法的優點是無監督方式進行新詞識別，不需要過多的人工干預，缺點是易受訓練數據的影響，訓練特征的選擇導致了人工工作量的增加。在分詞的過程中進行新詞識別的方法[8]提出了一種快速的分詞訓練法——ADF，利用該方法得到的模型即使在多維特征的數據集上依然能夠快速的進行分詞和新詞識別。針對專業領域的新詞識別[9]，第1步是構建專業領域詞典，第2步是利用該詞典尋找該專業的專家用戶，最后從專家用戶的輸入內容中提取該領域的新詞，該方法只能識別某一領域內的新詞，構建專業領域詞典需要人工參與，而且專家用戶的選擇會直接影響到新詞識別的結果。另外還有一些研究者在位置成詞概率的基礎上，結合新詞內部模式的特征，綜合互信息、鄰接類別等統計量對新詞進行識別[10]。

本文針對以上方法的優缺點，考慮到詞語的結構特性，把詞語內部的凝聚程度(內聚度)和外部的靈活程度(靈活度)作為識別新詞的特征，提出一種基于完全無監督的新詞識別算法。該算法提出使用左鄰右平均熵和右鄰左平均熵作為表征詞語外部靈活性的特征，新詞發現的正確率得到一定程度的提升。

3 新詞識別

3.1 基本設計理念

在自然語言處理過程中，詞是最小的可以獨立應用的語言單位。其中無監督的分詞方法——ESA[11]綜合了頻率、長度、左(右)信息熵等特征計算字符串的IV(AB)值和2個子串連接在一起時的CV(AB)值，判定字符(串)AB是獨立成詞還是子串A和B分別成詞，通過反復迭代，最終將一串字符進行粗切分，并利用局部最優化方法進行最優化，選出最優序列作為最終分詞結果。新詞作為詞的有機組成部分，同樣也會擁有詞語的所有特性。在結構上，新詞應該具有較高的內聚性和靈活性，這樣才能滿足獨立應用的要求。

到目前為止，學術界對于新詞的定義仍然沒有達成共識。這里所說的新詞指的是自動分詞工具未能正常切分且可以獨立表達完整意義的詞。這些詞或者是由已經存在的多字詞組成(如：“中國特色社會主義”是由中國、特色、社會主義3個多字詞組成)，或者是由單字詞組成(如：“高富帥”是由高、富、帥3個單字詞組成，“白富美”是由白、富、美3個單字詞組成)。從這些詞的后驗表現上看，這些新詞都有一個共同的特點：出現頻率高，內部結合緊密(內聚性高)，上下文語境靈活(靈活性高)。假設一個字串在語料中反復出現(高于一定的頻率閾值)、內部結合緊密(高于一定的內聚性特征閾值)、上下文語境靈活(高于一定的靈活性特征閾值)，可以認定該字串是一個新詞。即使該字串不是新詞(某一靈活性特征未達到閾值，如：白富、富美)，它仍有可能是某一新詞的一個組成部分，可以反復迭代以解決類似問題。

綜合上述思想，本文算法使用迭代方法，利用內聚性(共現頻率、互信息)和靈活性(左熵、右熵、左鄰接右平均熵、右鄰接左平均熵)2個方面的6個特征對新詞進行識別。

3.1.1 內聚性

新詞作為一個有機的并且能夠獨立應用的有意義的語言成分，新詞內部各元素之間必然存在高耦合度。內聚性作為詞語的內部特征，有多種度量方法：共現頻率，色子矩陣，互信息等，本文利用共現頻率和互信息兩種方法度量詞語的內聚性。

互信息(Mutual Information,MI)是信息論里一種有用的信息度量，它是用來度量2個事件集合之間的相關性，假設S是長度為n的字符串，S=xy，其中，x,y為字符串S的2個子串，x=c1,c2,…,ck，y=ck+1,ck+2,…,cn，則x，y的互信息可由式(1)計算得到互信息：

其中，Pxy表示字符串S在待分析語料中出現的頻率；Px表示子串x在待分析語料中出現的概率；Py表示子串y在待分析語料中出現的概率。

3.1.2 靈活性

作為一個獨立的語言成分，新詞應該比非獨立的語言成分具有更靈活的應用場合。人們用熵來衡量對事物的不確定性，熵越大，表示人們對該事物認知的不確定性越大，對應的，該事物對于人們來說就具有很高的靈活性；反之，說明人們對該事物的認知是確定的，此時該事物對于人們來說是確定的，失去了靈活性。左(右)熵是度量人們對于新詞左(右)鄰接的不確定性，即新詞的左(右)靈活性。左熵和右熵可以分別由式(2)、式(3)計算得到。受對偶原理的啟發，若一個字符串是新詞，其左鄰接應該具有較高的右靈活性，同樣的，其右鄰接應該具有較高的左靈活性。進一步，該算法用左(右)鄰接右(左)平均熵作為左(右)鄰接右(左)靈活性的判定特征，可以分別由式(6)、式(7)計算得到。

3.2 算法流程

基于迭代算法的新詞識別算法流程如圖1所示，具體流程為：用中文自動分詞工具對語料進行中文分詞和詞性標注；對分詞后的結果進行詞頻統計，找出重復模式。統計過程中利用詞性進行停用詞過濾。該過程利用兩遍掃描法進行詞頻統計，有效地提高了程序運行速度。第一遍掃描只統計單個詞語的詞頻，將低于一定閾值的詞加入到過濾詞表(因為如果一個詞的詞頻低于該閾值，則包含該詞的字符串肯定不會大于該閾值)，第二遍掃描時，只統計不以排除詞表(過濾詞表和詞性過濾列表，其中詞性過濾列表由人工添加)中的詞作為子串的字符串；再次，找出重復模式，統計重復模式的左(右)鄰接信息，計算重復模式的互信息、左(右)熵、左(右)鄰接右(左)平均熵，利用這些特征信息進行新詞識別，獲得新詞候選列表；最后，利用中文詞語搭配庫[12]對候選結果進行最后過濾，得到最終的新詞列表。

圖1 基于迭代算法的新詞識別算法流程

3.3 新詞識別過程描述

新詞識別是一個層疊迭代的過程，如圖2所示，其中實線表示算法流程，虛線表示迭代層級。該算法主要包括一個核心過程和2個子過程，首先介紹2個子過程。描述中常用符號說明見表1。

圖2 新詞識別過程示意圖

表1 符號說明

子過程1主要通過2次掃描獲得重復模式列表：第1次掃描進行詞頻統計，根據設置閾值獲得過濾詞表，第2次掃描基于過濾詞表和詞性過濾列表獲得重復模式列表。

假設語料中的用詞個數為n，第1遍掃描的時間復雜度為O(n)，空間復雜度為O(n)。如果重復模式平均由m個詞構成，第2遍掃描的時間復雜度為O(nm)，空間復雜度為O(n)。該子過程的時間復雜度為O(n+mn)，該算法所占用的空間主要為O(n)。

子過程2是整個算法中的核心子過程，計算給定重復模式的內聚性和靈活性特征的值。

該過程是整個算法中時間復雜度和空間復雜度最高的部分。由式(1)、式(2)、式(3)、式(6)、式(7)計算5項特征的值，時間復雜度主要取決于后4項特征值的計算時間，假設平均每一個重復模式包含ml個左鄰接和mr右鄰接，每一個左鄰接的平均右鄰接個數為mlr，每一個右鄰接的平均左鄰接個數為mrl，則該過程的時間復雜度為O(mlmlr+mrmrl)，空間復雜度為5個特征值的空間，即O(1)。

核心過程負責2個子過程的執行和判定重復模式是否為新詞，是從原始語料識別新詞、得到新詞列表的過程。

該過程的時間和空間復雜度主要取決于子過程1和子過程2，假設總共有m個重復模式，時間復雜度為：O(mn+m×(mlmlr+mrmrl))；空間復雜度為：O(n+m)。

4 實驗結果及分析

4.1 實驗環境

實驗在普通的PC單機上進行，采用Windows操作系統，CPU為2.4 GHz×2，內存為3 GB，算法的實現代碼采用C/C++語言實現。

4.2 測試對象的選取

實驗主要分兩部分進行，實驗1取中國共產黨第十八次全國代表大會報告(以下稱十八大報告)；實驗2取北京大學提供的98年1月的《人民日報》手工標注語料(以下簡稱北大語料)，手工標注后進行實驗。表2為語料的詳細說明。

表2 語料的詳細說明

4.3 實驗條件設置

實驗均采用如下設置：MI0表示互信息大于0，作為基準實驗(baseline)，LE0表示左鄰接熵大于0，RE0表示左鄰接熵大于0，LRAE0表示左鄰接右平均熵大于0，RLAE0表示右鄰接左平均熵大于0，Filter表示經過中文詞語搭配庫過濾，NoFilter表示未經過中文詞語搭配庫過濾。

4.4 實驗評測

在不同的條件下，新詞列表按照互信息由高到低進行排序，取P@N作為實驗結果的評測指標。

正確率計算公式：

其中，p表示正確率；Nq表示正確的新詞個數；Nc表示新詞總數。

4.5 實驗結果與性能分析

表3為實驗1中不同參數下的結果比較。實驗結果顯示，正確率均高于72%，利用互信息這一單一特征，N=100的正確率達到了72%，經過詞語固定搭配的過濾，準確率提升到78%。經過全部5項特征的過濾，N=100的正確率達到83%，經過詞語固定搭配詞典的過濾，新詞的正確率能夠達到85%。

表4為實驗2中不同參數下的結果比較。實驗結果顯示，正確率均高于76%，利用互信息這一單一特征，N=100的正確率達到了76%，經過詞語固定搭配的過濾，準確率提升到78%。經過全部5項特征的過濾，N=100的正確率達到88%，經過詞語固定搭配詞典的過濾，新詞的正確率能夠達到90%。

圖3、圖4分別為實驗1和實驗2中的部分新詞列表。

表3 實驗1中不同參數下的結果比較%

表4 實驗2中不同參數下的結果比較%

圖3 實驗1中部分新詞列表

圖4 實驗2中部分新詞列表

以上數據表明：N=10時，均有很高的正確率。隨著N的增加，正確率有一定程度的下降是因為互信息是該算法的主要特征，互信息的變化對新詞識別的準確率有直接的影響。隨著特征的逐一加入，新詞識別的正確數和正確率均呈現不斷上升的趨勢，證明各項特征均起到了提高正確率的效果。在同一實驗條件下，固定詞語搭配詞典的過濾可以不同程度的提高正確率。當語料的規模較小時，新詞發現的正確率略低，而語料規模較大時，新詞發現的正確率會升高，這是因為該算法完全基于統計方法，語料規模的越大，各項統計信息越接近真實情況。另外，左鄰接右平均熵和右鄰接左平均熵可以在一定程度上提高新詞識別的正確率，如果對新詞識別的正確率要求不高，可酌情刪除這2個特征，提高算法的執行效率。

另外從2個實驗的執行時間來看，算法的執行效率不是很高，主要有以下3個方面的原因：

(1)共現頻率閾值設置太小(為保證召回率)，導致重復模式過多，計算量增加；

(2)靈活度的4個特征值，尤其是左(右)鄰接右(左)平均熵計算復雜度過高；

(3)程序設計不盡合理，代碼執行效率偏低。

5 結束語

本文基于迭代算法，提出了運用左(右)鄰右(左)平均熵作為判斷重復模式是否為新詞的外部靈活度特征，采用內聚性和靈活度等6項特征判斷重復模式是否為新詞，通過十八大報告和北大語料的實驗測試，結果表明，該算法能夠有效提取新詞。通過對2組實驗進行對比分析發現，無論語料規模的大小，各項特征均起到提高正確率的效果。此外，語料規模對新詞發現的正確率也有一定的影響。語料規模越大，新詞發現的正確率就越高，這是因為該方法是基于統計的方法，數據量越大，統計數據的可靠性也越高，正確率也就越大，表明使用非監督的統計方法整合有效特征是一種非常有前途的新詞識別研究方法。

下一步工作是充分挖掘有效的新詞檢測特征并將其放入統計框架中，以進一步改進新詞檢測效果與算法的執行效率，利用機器學習的方法學習各個特征的閾值，減少人工干預，以便將該方法整合到中文分詞技術中，提高中文分詞效果。

[1]朱德熙.語法講義[M].北京:商務印書館,2004.

[2]劉 群,張華平,俞鴻魁,等.基于層疊隱馬模型的漢語詞法分析[J].計算機研究與發展,2004,41(8):1421-1429.

[3]李 鈍,屠 衛,石 磊,等.基于上下文感知的中文新詞識別算法[J].計算機工程與設計,2012,33(10):4022-4027.

[4]鄭家恒,李文花.基于構詞法的網絡新詞自動識別初探[J].山西大學學報:自然科學版,2002,25(2):115-119.

[5]鄒 剛,劉 群.面向Internet的中文新詞語檢測[J].中文信息學報,2004,18(6):1-9.

[6]張海軍,欒 靜,李 勇,等.基于統計學習框架的中文新詞檢查方法[J].計算機科學,2012,39(2):232-235.

[7]Sun Xiao,Huang Degen,Song Haiyu.Chinese New Word Identification:A Latent Discriminative Model with Global Features[J].Journal of Computer Science and Technology,2011,26(1):14-24.

[8]Sun Xu,Wang Houfeng,Li Wenjie.Association for Computational Linguistics[C]//Proc.of the 50th Annual Meeting of the Association for Computational Linguistics.[S.1.]:Association for Computational Linguistics,2012:123-128.

[9]Liu Zhiyuan,Zheng Yabin,Xie Lixing,et al.User Behaviors in Related Word Retrieval and New Word Detection:A Collaborative Perspective[J].ACM Transactions on Asian Language Information Processing,2011,10(4):20-27.

[10]林自芳,蔣秀鳳.基于改進位置成詞概率的新詞識別[J].福州大學學報:自然科學版,2011,39(1):43-48.

[11]Wang Hanshi,Zhu Jian,Tang Shiping,et al.A New Unsupervised Approach to Word Segmentation[J].Computational Linguistics,2011,37(3):421-454.

[12]搜狗實驗室.搜狗中文詞語搭配庫[EB/OL].(2009-01-20).http://www.sogou.com/labs/resources.htm.