李杰 孫仁誠(chéng)

摘要：??針對(duì)冪律判斷方式存在的問題，本文基于早期對(duì)冪律分布的研究，結(jié)合最大擬然擬合方法及詞頻統(tǒng)計(jì)算法，對(duì)中英文詞頻分布進(jìn)行研究。給出了雙對(duì)數(shù)坐標(biāo)系下冪律分布的判斷，并對(duì)詞頻統(tǒng)計(jì)與冪律分布進(jìn)行擬合。研究結(jié)果表明，在雙對(duì)數(shù)坐標(biāo)系下，分布圖像為近似直線是判斷冪律分布的必要條件，而非充分條件;在自然語言的詞頻統(tǒng)計(jì)分布模型上，對(duì)觀測(cè)數(shù)據(jù)進(jìn)行冪律分布的擬合，得出的pvalue分別為0.14和0.19，均大于0.1，且泊松分布、指數(shù)分布、廣延指數(shù)分布的pvalue值都為0，即可排除滿足其他分布的假設(shè)，因此對(duì)觀測(cè)數(shù)據(jù)擬合效果最好的是冪律分布。說明自然語言的詞頻分布滿足冪律，且中英文同樣適用。該研究對(duì)人們認(rèn)識(shí)語言的發(fā)展過程具有重要意義。

關(guān)鍵詞：??詞頻統(tǒng)計(jì);?冪律分布;?最大似然估計(jì);?KS統(tǒng)計(jì)量

中圖分類號(hào)：?TP312;?C81?文獻(xiàn)標(biāo)識(shí)碼：?A

收稿日期：?2019-06-20;?修回日期：?2019-10-28

基金項(xiàng)目：??國(guó)家自然科學(xué)青年基金資助項(xiàng)目（41706198）

作者簡(jiǎn)介：??李杰（1994-），男，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘與分析。

通信作者：??孫仁誠(chéng)（1977-），男，副教授，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘及人工智能。Email：?qdsunstar@163.com

冪律分布[1]廣泛存在于計(jì)算機(jī)科學(xué)、人口統(tǒng)計(jì)學(xué)與社會(huì)科學(xué)、物理學(xué)、經(jīng)濟(jì)學(xué)與金融學(xué)等眾多領(lǐng)域中，且形式多樣。實(shí)驗(yàn)證明，在自然界與日常生活中，包括地震規(guī)模大小的分布、月球表面上月坑直徑的分布、行星間碎片大小的分布、太陽(yáng)耀斑強(qiáng)度的分布、計(jì)算機(jī)文件大小的分布、戰(zhàn)爭(zhēng)規(guī)模的分布、人類語言中單詞頻率的分布、大多數(shù)國(guó)家姓氏的分布、科學(xué)家撰寫的論文數(shù)的分布、論文被引用的次數(shù)的分布、網(wǎng)頁(yè)被點(diǎn)擊次數(shù)的分布[2]、書籍及唱片的銷售冊(cè)數(shù)或張數(shù)的分布、電力數(shù)據(jù)的分布[3]、甚至電影所獲得的奧斯卡獎(jiǎng)項(xiàng)數(shù)的分布等都是典型的冪律分布。但這一結(jié)果存在巨大缺陷，曾經(jīng)被認(rèn)為滿足冪律分布的某些數(shù)據(jù)，只有在一定的條件范圍內(nèi)才是冪律，而在整體大量的數(shù)據(jù)集上是不純的[4]。20世紀(jì)中期，對(duì)于冪律分布的研究，一些研究者[5-6]分別在語言學(xué)和經(jīng)濟(jì)學(xué)的領(lǐng)域提出了著名的80/20定律。這一定律的基本形式即為簡(jiǎn)單的冪函數(shù)，是冪律分布的4種形式之一，其他形式的冪律分布有名次-規(guī)模分布、規(guī)模-概率分布等。直到21世紀(jì)初，A.L.Barabasi等人[7-8]提出了無標(biāo)度理論，從復(fù)雜網(wǎng)絡(luò)的角度探究了冪律分布的性質(zhì)，即無標(biāo)度網(wǎng)絡(luò)的度分布就是冪律分布，為復(fù)雜網(wǎng)絡(luò)的發(fā)展奠定了理論基礎(chǔ);C.?Aaron等人[4]對(duì)冪律分布的判斷標(biāo)準(zhǔn)進(jìn)行了詳盡的理論證明，推翻了前人通過雙對(duì)數(shù)坐標(biāo)系下是否構(gòu)成一條近似直線判斷冪律分布的方法，并證明了雙對(duì)數(shù)坐標(biāo)系下近似直線是冪律分布的必要條件。關(guān)于中英文詞頻分布的研究[9-11]一直是自然語言處理的重點(diǎn)。國(guó)內(nèi)中文分詞的算法主要集中在詞典與統(tǒng)計(jì)相結(jié)合[12]的方式，但精度有待提升。2017年，麻省理工學(xué)院的Sun?Junyi團(tuán)隊(duì)歷時(shí)4年，完善了新的詞頻統(tǒng)計(jì)算法，與傳統(tǒng)的基于統(tǒng)計(jì)的詞頻算法＼[13＼]不同，新的算法是基于前綴詞典來實(shí)現(xiàn)詞圖掃描，構(gòu)造有向無環(huán)圖（directed?acyclic?graph，DAG），利用動(dòng)態(tài)規(guī)劃算法查找詞頻最大切合組，同時(shí)結(jié)合隱馬爾可夫模型（hidden?markov?model，HMM）模型操作未登錄詞，大大提高了分詞精度和分詞效率。基于此，本文在最新詞頻統(tǒng)計(jì)算法基礎(chǔ)上，構(gòu)造私有的前綴詞典及DAG，同時(shí)采用最新的冪律分布研究方式，對(duì)中英文兩種語言進(jìn)行研究，完善了之前研究者們[14-16]在詞頻統(tǒng)計(jì)精度及冪律分布判斷方式上的不足之處，并進(jìn)行了可視化的冪律擬合。該研究推動(dòng)了人們對(duì)自然語言發(fā)展的認(rèn)識(shí)。

1?冪律分布的研究

1.1?雙對(duì)數(shù)坐標(biāo)系下冪律分布的判斷

20世紀(jì)末，人們對(duì)冪律分布的研究是基于雙對(duì)數(shù)坐標(biāo)系下，數(shù)據(jù)分布的圖像是否為一條近似的直線來判斷。冪律分布特征及其在雙對(duì)數(shù)坐標(biāo)系下的擬合如圖1所示。

其形式化的表達(dá)為：y=cx-r，其中x，y表示正的隨機(jī)變量;c，r為常數(shù)且均大于零。這種分布特征只有少數(shù)事件的規(guī)模比較大，而絕大多數(shù)事件的規(guī)模較小。對(duì)y-cx-r兩邊取對(duì)數(shù)，可知lny與lnx滿足lny=lnc-rlnx，這是一種線性關(guān)系，即在雙對(duì)數(shù)坐標(biāo)系下，冪律分布可以通過一條斜率為負(fù)的冪指數(shù)的直線進(jìn)行擬合，這一線性關(guān)系是判斷給定的實(shí)例中隨機(jī)變量是否滿足冪律的依據(jù)。

判斷兩個(gè)隨機(jī)變量是否滿足線性關(guān)系，可以求解兩者之間的相關(guān)系數(shù);利用一元線性回歸模型和最小二乘法，可得lny對(duì)lnx的線性回歸方程，從而得到y(tǒng)與x之間的冪律關(guān)系式[1，4]。

對(duì)于在雙對(duì)數(shù)坐標(biāo)系下，線性關(guān)系判斷數(shù)據(jù)是否滿足冪律分布的說法不正確，因?yàn)殡p對(duì)數(shù)坐標(biāo)系下的線性關(guān)系是數(shù)據(jù)滿足冪律分布的必要條件，而不是充分條件。

1.2?冪律分布的判斷

2007年，Aaron?chauset等人[4]提出了判斷冪律分布的一系列方法，其思想是將最大似然擬合方法與基于KolmogorovSmirnov（KS）統(tǒng)計(jì)以及似然比的擬合優(yōu)度檢驗(yàn)相結(jié)合，判斷觀測(cè)數(shù)據(jù)是否滿足冪律分布，過程主要分為以下幾部分：

1）?估計(jì)冪律模型的參數(shù)xmin和α。

2）?計(jì)算數(shù)據(jù)與冪律之間的擬合優(yōu)度，如果得到的p-value值大于0.1，則冪律分布是觀測(cè)數(shù)據(jù)的似然假設(shè)，否則拒絕該假設(shè)。

3）?通過似然比檢驗(yàn)，將冪律與其他假設(shè)進(jìn)行比較。對(duì)于每個(gè)備選方案，如果計(jì)算的似然比與零顯著不同，則其符號(hào)表示該備選方案是否優(yōu)于冪律模型。

2?詞頻統(tǒng)計(jì)與冪律分布擬合

關(guān)于自然語言中詞匯的分布特征，早在20世紀(jì)中葉就有研究者進(jìn)行過大量研究，直至20世紀(jì)末，有學(xué)者（冪律分布研究簡(jiǎn)史）通過雙對(duì)數(shù)坐標(biāo)系下圖像近似一條直線的擬合方式，說明數(shù)據(jù)滿足冪律分布，這種方式顯然缺乏說服力。本文基于文獻(xiàn)＼[4＼]提出的方法，首先基于詞頻統(tǒng)計(jì)算法對(duì)文本進(jìn)行統(tǒng)計(jì)，然后結(jié)合最大似然擬合方法[17]與基于KolmogorovSmirnov（KS）統(tǒng)計(jì)[18]以及似然比[19]的擬合優(yōu)度檢驗(yàn)方式，對(duì)自然語言進(jìn)行冪律分布的擬合。

關(guān)于數(shù)據(jù)的選擇，本文選取了經(jīng)典文學(xué)作品《飄》的中英文對(duì)照版本，分別對(duì)英文和中文進(jìn)行詞頻統(tǒng)計(jì)，并擬合冪律分布。

2.1?詞頻統(tǒng)計(jì)算法

詞頻統(tǒng)計(jì)算法流程圖如圖2所示，詞頻統(tǒng)計(jì)算法整體分為3個(gè)部分，每個(gè)部分又可分為多個(gè)步驟，其描述如下：

1）?基于Trie樹結(jié)構(gòu)實(shí)現(xiàn)高效的詞圖掃描，構(gòu)造出有向無環(huán)圖（DAG），圖中包括生成句子中漢字所有可能的成詞情況。根據(jù)dict.txt生成trie樹，字典在生成trie樹的同時(shí)，也把每個(gè)詞的出現(xiàn)次數(shù)轉(zhuǎn)換為頻率;對(duì)需要進(jìn)行分詞的句子，根據(jù)已經(jīng)生成的trie樹，生成有向無環(huán)圖（DAG），簡(jiǎn)言之，就是將句子根據(jù)給定的詞典進(jìn)行查尋操作，生成多種可能的句子切分。

2）?用動(dòng)態(tài)規(guī)劃算法查找最大概率路徑，找到基于詞頻的最大切分組合。查找待分詞句子中已經(jīng)切分好的詞語，即查找該詞語出現(xiàn)的頻率，如果查不到該詞，就把該詞的頻率賦值為詞典中出現(xiàn)頻率最小的那個(gè)詞語的頻率;根據(jù)動(dòng)態(tài)規(guī)劃算法查找最大概率路徑，即對(duì)句子從后往前反向計(jì)算最大概率，P（NodeN）=1.0，P（NodeN-1）=P（NodeN）*Max（P（最后一個(gè)詞））…依次類推，得到最大概率路徑，從而得到最大概率的切分組合。

3）?對(duì)于詞典中未錄入的詞，采用基于漢字成詞能力的HMM模型，同時(shí)使用viterbi算法。中文詞匯按照BEMS四個(gè)狀態(tài)標(biāo)記，B代表begin，即開始位置，E代表end，即結(jié)束位置，M代表middle，表示中間位置，S代表singgle，是單獨(dú)成詞的位置，如山東可表示為BE，即山/B，是開始位置，東/E，是結(jié)束位置;對(duì)語料庫(kù)進(jìn)行初步訓(xùn)練，得到3個(gè)概率表，并結(jié)合viterbi算法，可以得到一個(gè)概率最大的BEMS序列，按照B開始，E結(jié)尾的方式，對(duì)分詞的句子重新組合，就能得到最終的分詞結(jié)果[14]。對(duì)《飄》的中英文對(duì)照版詞頻進(jìn)行統(tǒng)計(jì)，《飄》的前5個(gè)高頻詞匯如表1所示。

由表1可以看出，中英文在表達(dá)同義內(nèi)容時(shí)，所使用詞匯差別巨大，并未出現(xiàn)高頻詞匯一致性的現(xiàn)象，這與語言的特點(diǎn)有關(guān)。同時(shí)，英文的代詞和介詞在使用率上遠(yuǎn)高于其他詞匯，而中文則不同，除代詞外，量詞在文章中也高頻出現(xiàn)。雖然有諸多的差別，但在分布情況上仍需進(jìn)一步驗(yàn)證。

2.2?冪律分布擬合

本文通過將最大似然擬合方法與基于KolmogorovSmirnov（KS）統(tǒng)計(jì)以及似然比的擬合優(yōu)度檢驗(yàn)相結(jié)合的方式，對(duì)自然語言進(jìn)行了冪律分布擬合。中英文詞頻在雙對(duì)數(shù)坐標(biāo)系下的冪律擬合如圖3所示。圖3中，英文詞頻xmin=40，α=1.89;中文詞頻xmin=38，α=2.1。

由圖3可以看出，在雙對(duì)數(shù)坐標(biāo)系下，中英文的詞頻分布均呈現(xiàn)一條近似的直線，說明存在冪律分布的可能性，但需要驗(yàn)證pvalue是否大于0.1，如果大于0.1，就要進(jìn)一步排除其他分布是否比冪律分布擬合效果更好，否則，可以直接判斷不滿足冪律分布。似然比的擬合優(yōu)度LR值和pvalue（p）值如表2所示。

由表2可以看出，對(duì)觀測(cè)數(shù)據(jù)進(jìn)行冪律分布的擬合，得出的pvalue分別為0.14和0.19，均大于0.1，且泊松分布，指數(shù)分布，廣延指數(shù)分布的pvalue值都為0，即滿足其他分布的假設(shè)可直接排除，因此對(duì)觀測(cè)數(shù)據(jù)擬合效果最好的是冪律分布。

3?結(jié)束語

本文通過對(duì)中英文詞頻的統(tǒng)計(jì)分析，證明了自然語言中的詞匯在日常生活中的使用頻率是服從冪律分布的，即部分詞匯會(huì)被大量使用，大部分詞匯的使用頻率較低，符合動(dòng)力學(xué)中的省力原則，人們更傾向于用更少詞匯的不同組合來表達(dá)不同的意思，對(duì)認(rèn)識(shí)語言的發(fā)展過程具有重要意義。這一結(jié)論不僅僅出現(xiàn)在本文所研究的文獻(xiàn)中，對(duì)于其他文獻(xiàn)同樣適用。文中詞頻統(tǒng)計(jì)算法和“最大似然擬合方法”、“KS統(tǒng)計(jì)以及似然比的擬合優(yōu)度檢驗(yàn)方法”的結(jié)合，使本結(jié)論的精確度更高，進(jìn)一步補(bǔ)充了前人對(duì)于詞頻分布的研究與應(yīng)用。在接下來的工作中，可以將重點(diǎn)放在對(duì)其他語言的研究上，在冪律分布的基礎(chǔ)之上，探究是否有更加精確的擬合方式，進(jìn)一步推動(dòng)人們對(duì)于自然語言發(fā)展的認(rèn)識(shí)。

參考文獻(xiàn)：

[1]?胡海波，?王林.?冪律分布研究簡(jiǎn)史[J].?物理，?2005，?34（12）：?889-896.

[2]?Adamic?L?A，?Huberman?B?A，?Barabási?A?L，?et?al.?Powerlaw?distribution?of?the?world?wide?web[J].?Science，?2000，?287?（5461）：?2115a.

[3]?王冠男，?鄧春宇，?趙悅，?等.?電力數(shù)據(jù)中的冪律分布特性[J].?電信科學(xué)，?2013，?29（11）：?109-114，?121.

[4]?Aaron?C，?Cosma?R?S，?Newman?M?E?J.?Powerlaw?distributions?in?empirical?data[J].?Siam?Review，?2009，?0706（1062）：?661-703.

[5]?嚴(yán)怡民.?情報(bào)學(xué)概論[M].?武漢：?武漢大學(xué)出版社，?1994.

[6]?Arnold?B?C.?Pareto?Distribution[M]∥Encyclopedia?of?Statistical?Sciences.?United?States：?John?Wiley?&?Sons，?Inc.，?2006.

[7]?Barabasi?A?L，?Albert?R.?Emergence?of?scaling?in?random?networks[J].?Science，?1999，?286（5439）：?509-514.

[8]?Barabasi?A?L，?Bonabeau?E.?Scalefree?networks[J].?Scientific?American，?2003，?288（5）：?60.

[9]?張丹.?中文分詞算法綜述[J].?黑龍江科技信息，?2012（8）：?206.

[10]?張華平，?劉群.?基于N-最短路徑方法的中文詞語粗分模型[J].?中文信息學(xué)報(bào)，?2002，?16（5）：?1-7.

[11]?費(fèi)洪曉，?康松林，?朱小娟，?等.?基于詞頻統(tǒng)計(jì)的中文分詞的研究[J].?計(jì)算機(jī)工程與應(yīng)用，?2005，?41（7）：?67-68，?100.

[12]?秦贊.?中文分詞算法的研究與實(shí)現(xiàn)[D].?長(zhǎng)春：?吉林大學(xué)，?2016.

[13]?祝永志，?荊靜.?基于Python語言的中文分詞技術(shù)的研究[J].?通信技術(shù)，?2019，?52（7）：?1612-1619.

[14]?Goldstein?M?L，?Morris?S?A，?Yen?G?G.?Fitting?to?the?powerlaw?distribution[J].?The?European?Physical?Journal?BCondensed?Matter?and?Complex?Systems，?2004，?41（2）：?2004.

[15]?Fernholz?R?T.?Nonparametric?methods?and?locatimebased?estimation?for?dynamic?power?law?distributions[J].?Journal?of?Applied?Econometrics，?2016，?32（7）：?1244-1260.

[16]?Montebruno?P，?Bennett?R?J，?van?Lieshout?C，?et?al.?A?tale?of?two?tails：?Do?power?law?and?lognormal?models?fit?firmsize?distributions?in?the?midvictorian?era[J].?Physica?A：?Statistical?Mechanics?and?its?Applications，?2019，?523：?858-875.

[17]?胡德，?郭剛正.?最小二乘法、矩法和最大似然法的應(yīng)用比較[J].?統(tǒng)計(jì)與決策，?2015（9）：?20-24.

[18]?Lilliefors?H?W.?On?the?kolmogorovsmirnov?test?for?normality?with?mean?and?variance?unknown[J].?Journal?of?the?American?Statistical?Association，?1967，?62（318）：?399-402.

[19]?成平.?極大似然估計(jì)與似然比檢驗(yàn)的幾點(diǎn)注記[J].?應(yīng)用概率統(tǒng)計(jì)，?2003，?19（1）：?55-59.

Research?on?Chinese?and?English?Word?Frequency?Distribution?Based?on?Word?Frequency?Statistics?Algorithm

LI?Jie，?SUN?Rencheng

（College?of?Computer?Science?&?Technology，?Qingdao?University，?Qingdao?266071，?China）

Abstract：??Aiming?at?the?problems?existing?in?the?power?law?judgment?method，?this?paper?studies?the?frequency?distribution?of?Chinese?and?English?words?based?on?the?previous?research?on?power?law?distribution，?combined?with?the?maximum?likelihood?fitting?method?and?word?frequency?statistics?algorithm.?The?judgment?of?power?law?distribution?in?double?logarithmic?coordinate?system?is?given，?and?the?word?frequency?statistics?and?power?law?distribution?are?fitted.?The?results?show?that?in?the?double?logarithmic?coordinate?system，?the?distribution?image?being?an?approximate?straight?line?is?a?necessary?condition?for?judging?the?power?law?distribution，?but?not?a?sufficient?condition.?On?the?word?frequency?statistical?distribution?model?of?natural?language，?the?power?law?distribution?of?the?observation?data?is?proposed.?The?pvalues?obtained?are?0.14?and?0.19，?respectively，?both?greater?than?0.1，?and?the?pvalues?of?the?Poisson?distribution，?the?exponential?distribution，?and?the?extensive?exponential?distribution?are?all?0，?that?is，?the?assumptions?satisfying?other?distributions?can?be?directly?excluded.?The?best?fit?for?the?observation?data?is?the?power?law?distribution.?It?shows?that?the?word?frequency?distribution?of?natural?language?satisfies?the?power?law，?and?both?Chinese?and?English?are?applicable.?This?research?is?of?great?significance?for?people?to?understand?the?development?process?of?language.

Key?words：??word?frequency?statistics;?power?law?distribution;?maximum?likelihood?estimation;?KS?statistics