基于高維聚類技術(shù)的中文關(guān)鍵詞提取算法

[摘要]關(guān)鍵詞提取是中文信息處理技術(shù)的熱點(diǎn)和難點(diǎn)，基于統(tǒng)計(jì)信息的方法是其中一個(gè)重要分支。本文針對(duì)基于統(tǒng)計(jì)信息關(guān)鍵詞提取方法準(zhǔn)確率低的問題，提出基于高維聚類技術(shù)的中文關(guān)鍵詞提取算法。算法通過依據(jù)小詞典的快速分詞、二次分詞、高維聚類及關(guān)鍵詞甄選四個(gè)步驟實(shí)現(xiàn)關(guān)鍵詞的提取。理論分析和實(shí)驗(yàn)顯示，基于高維聚類技術(shù)的中文關(guān)鍵詞提取方法具備更好的穩(wěn)定性、更高的效率及更準(zhǔn)確的結(jié)果。

[關(guān)鍵詞]關(guān)鍵詞提取；小詞典分詞；高維聚類；CABOSFV

Chinese Keywords Extraction Algorithm Based on the High-dimensional Clustering Technique

Wu Lingyu， Chen Yuan(與漢語不符)

(School of Economics and Management， University of Science and Technology Beijing， Beijing 100083， P. R. China)

Abstract: Keywords extraction methods are hot and difficult spots in Chinese information processing technology， one of which is the method based on statistical information. In order to improve the inaccuracy of it， Chinese keywords extraction algorithm based on the high-dimensional clustering technique is proposed. After word segmenting with small volume dictionary， secondary word segmenting， high-dimensional clustering and word selecting， the algorithm finds the keywords from article. Theoretical analysis and test show that the Chinese keywords extraction algorithm based on the high-dimensional clustering technique has better stability， efficiency and accuracy.

Keywords: keywords extraction， word segmentation with small volume dictionary， high-dimensional clustering， CABOSFV

1引言

關(guān)鍵詞提取是通過對(duì)一篇輸入文章做內(nèi)容分析，按一定比例或字?jǐn)?shù)要求提取出重要且語義相似性凝聚的關(guān)鍵詞的過程。關(guān)鍵詞自動(dòng)提取是文本挖掘領(lǐng)域的一個(gè)重要分支，在自動(dòng)摘要、文本分類、文本聚類、文本過濾、話題跟蹤、信息檢索、自動(dòng)問答等很多領(lǐng)域有重要作用。

迄今為止，關(guān)鍵詞自動(dòng)提取吸引了不少國內(nèi)外學(xué)者的關(guān)注和研究，其理論成果主要包括基于統(tǒng)計(jì)信息的方法、機(jī)器學(xué)習(xí)方法和淺層式語義分析方法三大類。其中應(yīng)用最為廣泛的是基于統(tǒng)計(jì)信息的關(guān)鍵詞提取方法，具備簡潔易懂、通用性強(qiáng)等優(yōu)勢(shì)。

本文針對(duì)基于統(tǒng)計(jì)信息關(guān)鍵詞提取方法準(zhǔn)確率不高的問題，引入高維聚類思想進(jìn)行改進(jìn)，提出基于高維聚類技術(shù)的中文關(guān)鍵詞自動(dòng)提取算法。經(jīng)過基于小詞典的快速分詞、二次分詞、高維聚類、關(guān)鍵詞甄選四個(gè)步驟，算法抽取出的關(guān)鍵詞更加準(zhǔn)確，并且具有更好的穩(wěn)定性和更高的效率。

2關(guān)鍵詞提取方法

關(guān)鍵詞自動(dòng)提取方法分為基于統(tǒng)計(jì)信息的方法、機(jī)器學(xué)習(xí)方法和淺層式語義分析方法三大類。

基于統(tǒng)計(jì)信息的方法主要包括基于詞頻的關(guān)鍵詞抽取方法[ ]、基于TFIDF指標(biāo)的關(guān)鍵詞抽取方法[ ]、利用字同現(xiàn)信息的關(guān)鍵詞抽取方法、利用詞共現(xiàn)信息的關(guān)鍵詞抽取方法、基于N-Gram信息統(tǒng)計(jì)的關(guān)鍵詞獲取方法、構(gòu)建復(fù)雜網(wǎng)絡(luò)提取關(guān)鍵詞的方法[ ]等。盡管具有簡單易用的優(yōu)勢(shì)，但這類方法的準(zhǔn)確性不高，提取出的關(guān)鍵詞往往包含文章中普遍出現(xiàn)卻與主題無關(guān)的高頻詞。此外，這類方法需統(tǒng)計(jì)所有詞匯出現(xiàn)的頻率，制約了運(yùn)行效率。

機(jī)器學(xué)習(xí)方法是建立在大量語料庫上的關(guān)鍵詞自動(dòng)提取方法，包括基于決策樹的方法、基于Naive Bayes 的方法、基于SVM的方法[ ]、基于最大熵模型的方法等。這類方法將關(guān)鍵詞提取問題視為二元分類問題，構(gòu)造關(guān)鍵詞提取分類模型，判斷詞語類別是否為關(guān)鍵詞。由于在實(shí)際應(yīng)用中有限的訓(xùn)練樣本難以接近整個(gè)樣本空間上的數(shù)據(jù)分布，這類方法很難訓(xùn)練出效果好的分類器。此外，這類方法在訓(xùn)練分類器的過程中可能存在過擬合問題，且生成的分類器只在與訓(xùn)練樣本類似的文章中才能取得較理想效果。

淺層式語義分析方法[ ]是近幾年發(fā)展起來的一種關(guān)鍵詞自動(dòng)提取方法。通常，這類方法借助一種中間模型表示文章語義結(jié)構(gòu)，通過分析詞語間的語義關(guān)系，獲取關(guān)鍵詞。顯然，這類方法需要專業(yè)相關(guān)的先驗(yàn)知識(shí)。

本文提出的基于高維聚類技術(shù)的中文關(guān)鍵詞提取算法是針對(duì)基于統(tǒng)計(jì)信息的方法所作的改進(jìn)。在依據(jù)動(dòng)詞、虛詞、停用詞小詞典實(shí)現(xiàn)快速分詞及二次分詞后，將待處理文本數(shù)據(jù)轉(zhuǎn)化為以句子為對(duì)象、以詞為屬性的高維二態(tài)關(guān)系數(shù)據(jù)。調(diào)用高屬性維聚類算法CABOSFV實(shí)現(xiàn)聚類后，進(jìn)行類內(nèi)詞頻統(tǒng)計(jì)，甄選出其中的高頻詞作為最終的關(guān)鍵詞。分析可知，算法具有更高的準(zhǔn)確度，更好的穩(wěn)定性，并提高了運(yùn)行效率。

3基于高維聚類技術(shù)的中文關(guān)鍵詞提取算法

基于高維聚類技術(shù)的中文關(guān)鍵詞提取算法分為依據(jù)小詞典的快速分詞、二次分詞、高維聚類及關(guān)鍵詞甄選四個(gè)步驟，見圖1。

3.1依據(jù)小詞典快速分詞

漢語以字為單位，詞與詞之間沒有天然的分隔符，因此中文關(guān)鍵詞提取的第一步是進(jìn)行分詞。常用的中文分詞法是依據(jù)名詞、形容詞大詞典的機(jī)械分詞法。由于名詞、形容詞的數(shù)量約占總體詞匯的70%，且難以及時(shí)收錄很多新生詞，所以依據(jù)大詞典進(jìn)行匹配存在效率低、擴(kuò)展性不強(qiáng)的問題。

鑒于此，算法選用較為新穎的依據(jù)動(dòng)詞、虛詞、停用詞小詞典的快速分詞法[ ]。其中，虛詞包括連詞、介詞、副詞及助詞，停用詞包括數(shù)詞、量詞、代詞、方位詞、擬聲詞、嘆詞、無實(shí)際意義的動(dòng)詞（如“可能”）及太過常用的名詞（如“操作”）。

對(duì)于文章中的每個(gè)句子，首先分別依據(jù)這三個(gè)小詞典對(duì)其進(jìn)行切分，即將句中的動(dòng)詞、虛詞、停用詞分別抽取出來，生成集合V，X，T：

V={c | c經(jīng)動(dòng)詞切分后被匹配為動(dòng)詞}；

X={c | c經(jīng)虛詞切分后被匹配為虛詞}；

T={c | c經(jīng)停用詞切分后被匹配為停用詞}，

而每類切分余下的字符串構(gòu)成集合 。

隨后通過下述處理，生成初始分詞集W。設(shè)某句可表示為Sentence = S1，S2，…，Sn，其中，Si，i=1，2，…，n為字符串，則具體操作如下：

While SiSi+1 ∈ ， i=1，2，…，n-1，

{

if [Si (or Si+1)∈ ] [Si+1 (or Si)];

Then W=W∪{ Si+1 (or Si)};

}

由于動(dòng)詞詞典、虛詞詞典以及停用詞詞典的詞匯量不多，算法初次分詞的效率得到改善。同時(shí)由于少有這三類新生詞匯，無需經(jīng)常性地?cái)U(kuò)充詞典，算法具有很好的穩(wěn)定性。

3.2二次分詞

由于沒有與大容量名詞詞庫進(jìn)行匹配，經(jīng)過快速分詞后產(chǎn)生的初始分詞集W中存在不必要的復(fù)合詞。為此，對(duì)初始分詞集進(jìn)行二次切分，生成最終分詞集。二次分詞的具體做法如下：

Step1：假設(shè)初始分詞集W={Z1，Z2，…，Zn}，其中Zi (i =1，2，…，n)代表字符串，設(shè)定字符串長度閾值α；

Step2：對(duì)任意Zi ( i =1，2，…，n)，

{ 若Zi.Length > α，

則將Zi與Z1，Z2，…，Zi-1，Zi+1，…Zn分別匹配，

{若Zi包含Zj ( j#61646;1，2，…，n且j≠i)；

則將Zi以Zj為界進(jìn)行切分，并用切分后

的詞替換原詞，存入集合W；}

}

經(jīng)過二次切分后，清除了詞與詞之間不必要的包含關(guān)系，生成了最終分詞集，為后續(xù)聚類做好鋪墊。

3.3高維聚類

將最終分詞集中的詞視作屬性，將文章中的每個(gè)句子視作對(duì)象，若某個(gè)句子中包含某個(gè)詞，則該句子對(duì)象相應(yīng)的詞屬性取值為1，否則為0。經(jīng)過這樣的處理將原來的文本信息被轉(zhuǎn)化成一張高屬性維稀疏二維表。針對(duì)該表，調(diào)用高維聚類算法CABOSFV（Clustering Algorithm Based On Sparse Feature Vector）[ ]對(duì)句子對(duì)象進(jìn)行聚類。

CABOSFV算法專門用于求解二態(tài)變量高屬性維稀疏聚類問題，利用其稀疏差異度計(jì)算方法及“稀疏特征向量”對(duì)數(shù)據(jù)進(jìn)行有效壓縮，只需一次數(shù)據(jù)掃描就可完成聚類。假設(shè)有n個(gè)對(duì)象，描述第i個(gè)對(duì)象的m個(gè)稀疏特征取值分別對(duì)應(yīng)于二態(tài)變量值xi1， xi2，…， xim，一個(gè)類內(nèi)對(duì)象的差異度上限為b，則算法處理步驟如下：

Step1：為每個(gè)對(duì)象建立一個(gè)集合，分別記為 ，i#61646;{1，2，…，n}。

Step2：計(jì)算 和 合并后集合的稀疏差異度，若不大于類內(nèi)對(duì)象的差異度上限b，則將 和 合并到一個(gè)集合，作為一個(gè)初始類，記為 ；若合并后集合的內(nèi)部差異度大于上限b，那么將 和 分別作為一個(gè)初始類，記為 和 。將類的個(gè)數(shù)記為c。

Step3：針對(duì)集合 ，計(jì)算其與現(xiàn)存所有類合并后的集合稀疏差異度，并尋找i0，使得 與類 合并后的差異度最小。隨后判斷其是否符合b的要求，若符合，將 加入到類 中；否則，則將 作為一個(gè)新的初始類，記為 ，類的個(gè)數(shù)c=c+1。

Step4： 對(duì) ， ，依次進(jìn)行類似于Step3的操作。

Step5：在最終形成的每一個(gè)類 ，k#61646;1，2，…，c中，刪除對(duì)象個(gè)數(shù)較少的孤立點(diǎn)，余下各類為最終聚類結(jié)果。

算法詳見文獻(xiàn)[9]。

由于將文本信息轉(zhuǎn)化成了計(jì)算機(jī)易于處理的結(jié)構(gòu)化數(shù)據(jù)，且CABOSFV計(jì)算復(fù)雜度低，整體算法的處理速度非常理想。同時(shí)，由于將文章中一些主題不相關(guān)的句子判斷為孤立點(diǎn)刪除，保證了后續(xù)關(guān)鍵詞甄選的準(zhǔn)確率。

3.4關(guān)鍵詞甄選

通過高維聚類技術(shù)CABOSFV，算法將文章中意思相近的句子聚集在一起，它們對(duì)文章主題具有更強(qiáng)的表達(dá)力。因此，以高維聚類結(jié)果中的各個(gè)類為基礎(chǔ)，對(duì)詞頻進(jìn)行統(tǒng)計(jì)，并甄選出文章的關(guān)鍵詞，具體做法如下：

Step1：計(jì)算最終分詞集中每個(gè)詞的類內(nèi)詞頻，即用包含該詞的類內(nèi)句子數(shù)除以類內(nèi)句子總數(shù)。

Step2：判斷每個(gè)詞的類內(nèi)詞頻是否大于事先設(shè)定的詞頻閾值λ，將大于閾值的詞加入到初始關(guān)鍵詞集。

Step3：結(jié)合具體問題，對(duì)初始關(guān)鍵詞集進(jìn)行修剪，生成最終關(guān)鍵詞集。

算法在類內(nèi)統(tǒng)計(jì)詞頻，避免了傳統(tǒng)統(tǒng)計(jì)方法將常用名詞誤判為關(guān)鍵詞的情況，提高了關(guān)鍵詞抽取的準(zhǔn)確率。

4算法實(shí)驗(yàn)

為檢驗(yàn)算法效果，對(duì)《智利發(fā)生8.8級(jí)強(qiáng)震，多國拉響海嘯預(yù)警》[ ]、《莫斯科地鐵遭兩女人彈襲擊，至少38人喪生》[ ]及《云南局部干旱已達(dá)100年一遇》[ ]三篇發(fā)表于新華網(wǎng)、人民網(wǎng)上的新聞文章進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)信息見表1。

在依據(jù)小詞典分詞及二次分詞后，將文本數(shù)據(jù)轉(zhuǎn)化為二維表。表2所示為文章智利地震對(duì)應(yīng)的二維表。

調(diào)用CABOSFV算法聚類后，計(jì)算最終分詞集中每個(gè)詞的類內(nèi)詞頻，并判斷產(chǎn)生初始關(guān)鍵詞集。三篇文章初始關(guān)鍵詞的類內(nèi)詞頻統(tǒng)計(jì)分別見圖2、圖3及圖4。

經(jīng)過對(duì)初始關(guān)鍵詞集的修剪，三篇文章生成的最終關(guān)鍵詞集分別為{智利、地震}、{地鐵、爆炸}及{云南、干旱}。

結(jié)合原文可以看出，基于高維聚類技術(shù)的中文關(guān)鍵詞提取算法準(zhǔn)確挖掘出了文章的關(guān)鍵詞。此外，從運(yùn)行時(shí)間可以看出，算法具有較高的效率。

5 結(jié)論

通過依據(jù)動(dòng)詞、虛詞、停用詞小詞典的快速分詞、針對(duì)復(fù)合詞拆分的二次分詞、基于CABOSFV算法的高維聚類、類內(nèi)詞頻統(tǒng)計(jì)及關(guān)鍵詞的最終甄選，基于高維聚類技術(shù)的中文關(guān)鍵詞提取算法完成了對(duì)關(guān)鍵詞的識(shí)別。理論分析和實(shí)驗(yàn)結(jié)果顯示，算法的準(zhǔn)確度較高，運(yùn)算效率理想，并具有很強(qiáng)的穩(wěn)定性。

主要參考文獻(xiàn)

[1] Luhn H P. A statistical approach to the mechanized encoding and searching of 1iterary information. IBM Journal of Research and

Development，1957，1(4):309-317.

[2] Li Juanzi， Fan Qina， Zhang Kuo. Keyword extraction based on TF/IDF for Chinese news document. Wuhan University Journal of Natural Sciences，2007，12(5).

[3] 趙鵬，蔡慶生．一種基于復(fù)雜網(wǎng)絡(luò)特征的中文文檔關(guān)鍵詞抽取算法．模式識(shí)別與人工智能，2007，20(6)：827-831．

[4] Zhang K， Xu H， Tang J. Keyword extraction using support vector machine. In: Proceedings of the Seventh International Conference on Web-Age Information Management， Hong Kong ， 2006:85-96.

[5] 索紅光，劉玉樹，曹淑英．一種基于詞匯鏈的關(guān)鍵詞抽取方法．中文信息學(xué)報(bào)，2006，20(6)：25-30．

[6] 羅杰，陳力，夏德麟．基于新的關(guān)鍵詞提取方法的快速文本分類系統(tǒng)．計(jì)算機(jī)應(yīng)用研究，2006 (4)：32-34．

[7] 武森，高學(xué)東，M Bastian．高維稀疏聚類知識(shí)發(fā)現(xiàn)．北京：冶金工業(yè)出版社，2002．

[8] 趙世俊．智利發(fā)生8.8級(jí)強(qiáng)震 多國拉響海嘯預(yù)警．新華網(wǎng)，2010[2010-2-28]．http://news.Xinhuanet

.com/world/2010-02/28/content_13065435.htm．

[9] 高軼軍．莫斯科地鐵遭兩女人彈襲擊 至少38人喪生．人民網(wǎng)，2010 [2010-3-30]．http://world.

people.com.cn/GB/1029/11252259.html．

[10] 蘇楠．云南局部干旱已達(dá)100年一遇．人民網(wǎng)，2010 [2010-3-16]．http://society.people.com.cn/GB/41158/11154789.html．

作者簡介

高學(xué)東（1963-），男，河北唐山人，北京科技大學(xué)經(jīng)濟(jì)管理學(xué)院教授，博士生導(dǎo)師，主要研究方向：管理過程優(yōu)化，數(shù)據(jù)挖掘.

吳玲玉（1983-），女，內(nèi)蒙人，博士研究生，主要研究方向：數(shù)據(jù)挖掘