趙小寶，張華平

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

1 概述

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

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

2 相關(guān)工作

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

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

3 新詞識別

3.1 基本設(shè)計理念

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

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

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

3.1.1 內(nèi)聚性

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

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

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

3.1.2 靈活性

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

3.2 算法流程

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

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

3.3 新詞識別過程描述

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

圖2 新詞識別過程示意圖

表1 符號說明

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

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

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

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

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

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

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

4.1 實驗環(huán)境

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

4.2 測試對象的選取

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

表2 語料的詳細說明

4.3 實驗條件設(shè)置

實驗均采用如下設(shè)置：MI0表示互信息大于0，作為基準(zhǔn)實驗(baseline)，LE0表示左鄰接熵大于0，RE0表示左鄰接熵大于0，LRAE0表示左鄰接右平均熵大于0，RLAE0表示右鄰接左平均熵大于0，F(xiàn)ilter表示經(jīng)過中文詞語搭配庫過濾，NoFilter表示未經(jīng)過中文詞語搭配庫過濾。

4.4 實驗評測

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

正確率計算公式：

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

4.5 實驗結(jié)果與性能分析

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

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

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

表3 實驗1中不同參數(shù)下的結(jié)果比較%

表4 實驗2中不同參數(shù)下的結(jié)果比較%

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

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

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

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

(1)共現(xiàn)頻率閾值設(shè)置太小(為保證召回率)，導(dǎo)致重復(fù)模式過多，計算量增加；

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

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

5 結(jié)束語

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

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

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

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

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

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

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

[6]張海軍,欒 靜,李 勇,等.基于統(tǒng)計學(xué)習(xí)框架的中文新詞檢查方法[J].計算機科學(xué),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].福州大學(xué)學(xué)報:自然科學(xué)版,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.