基于Synonyms、k-means的短文本聚類(lèi)算法

回玥婷 夏懿嘉 陳紫荷 佟鑫

摘要：當(dāng)今社會(huì)，網(wǎng)絡(luò)搜索成為人們獲取資訊的主流。短文本因特征信息不足且高維稀疏等特點(diǎn)，導(dǎo)致傳統(tǒng)文本聚類(lèi)算法應(yīng)用于短文本聚類(lèi)時(shí)效率低下。為此，我們采用為關(guān)鍵詞以及k-means和synonyms相結(jié)合的方法，提高主題歸類(lèi)精確度。實(shí)驗(yàn)證明，我們提出的s-k（Synonyms-k-means）主題聚類(lèi)算法不僅有效歸類(lèi)主題，而且能挖掘出詞語(yǔ)的潛在含義。

關(guān)鍵詞：文本聚類(lèi);短文本;k-means;synonyms

中圖分類(lèi)號(hào)：TP301? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2019）01-0005-02

1 引言

網(wǎng)絡(luò)社交平臺(tái)的廣泛應(yīng)用，使得人們?cè)桨l(fā)偏向通過(guò)閱讀屏幕上的文本內(nèi)容獲得自己想要了解的信息，網(wǎng)絡(luò)搜索成為人們獲取資訊的主流，以提高用戶(hù)的使用舒適度為目的，國(guó)內(nèi)外的研究人員針對(duì)主題檢索和文本聚類(lèi)方法在不斷地進(jìn)行完善。如何提高文本聚類(lèi)的準(zhǔn)確度是研究人員需要繼續(xù)改進(jìn)的問(wèn)題?；ヂ?lián)網(wǎng)的信息呈現(xiàn)多元化，文本內(nèi)容冗雜不一，并且微博等短文本具有文本短小的特征，針對(duì)中文新生詞語(yǔ)詞義以及主題的歧義之特點(diǎn)，傳統(tǒng)的文本檢索方法不足滿(mǎn)足當(dāng)前用戶(hù)的需求。因此，得出一種更加快速、高效的短文本聚類(lèi)方法顯得極為迫切。

通過(guò)更有效分析詞義和句意是提高文本聚類(lèi)準(zhǔn)確度的關(guān)鍵點(diǎn)。最初由中國(guó)餐廳模型為我們了解文本聚類(lèi)建立了形象的立體概念，但此模型欠缺之處主要在于文本內(nèi)容和表達(dá)方式存在語(yǔ)義詞義的差異，因此容易出現(xiàn)主題分類(lèi)偏差的現(xiàn)象。文獻(xiàn)【1】總結(jié)得出文本聚類(lèi)目前存在的，高維稀疏、近義詞和多義詞技術(shù)難點(diǎn)，這三個(gè)文本數(shù)據(jù)所特有的問(wèn)題使得文本聚類(lèi)具有相當(dāng)高的時(shí)間復(fù)雜度，而且極大干擾了聚類(lèi)算法的準(zhǔn)確性。文獻(xiàn)【2】提出微博主題檢索模型，利用文本聚類(lèi)和LDA潛在主題發(fā)現(xiàn)相結(jié)合的檢索模型，以縮小檢索空間，使其適用于中文微博短文本的處理和分析，實(shí)現(xiàn)了微博信息的有效檢索。然而，從挖掘的類(lèi)簇中看，潛在主題仍舊較為單一。

針對(duì)傳統(tǒng)文本聚類(lèi)方法存在的詞義分析不確切的不足，我們?cè)谀壳耙延械幕A(chǔ)上，采用k-means和synonyms相結(jié)合的算法，該算法具有更大的詞匯量，更便于針對(duì)中文詞語(yǔ)進(jìn)行語(yǔ)意辨析，通過(guò)計(jì)算強(qiáng)化了詞語(yǔ)之間的近似度，有效地進(jìn)行近義詞的辨析，提高了文本類(lèi)簇主題的精確度，實(shí)現(xiàn)了對(duì)短文本主題進(jìn)行更加快速準(zhǔn)確的檢索，以最大程度滿(mǎn)足用戶(hù)需求。

2 算法內(nèi)容

2.1文本預(yù)處理

分詞處理：使用結(jié)巴分詞。結(jié)巴分詞基于前綴詞典實(shí)現(xiàn)高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構(gòu)成的有向無(wú)環(huán)圖 （DAG）;采用了動(dòng)態(tài)規(guī)劃查找最大概率路徑， 找出基于詞頻的最大切分組合;對(duì)于未登錄詞，采用了基于漢字成詞能力的 HMM 模型，采用Viterbi 算法;主要能夠做到分詞，添加自定義詞典，基于TF-IDF算法及TextRank算法的關(guān)鍵詞提取，詞性標(biāo)注，并行分詞，Tokenize：返回詞語(yǔ)在原文的起止位置，ChineseAnalyzer for Whoosh 搜索引擎，命令行分詞。

分詞過(guò)后，將得到的分詞遍歷一下載入的停用詞表，去掉停用詞。停用詞主要包括英文字符、數(shù)字、數(shù)學(xué)字符、標(biāo)點(diǎn)符號(hào)及使用頻率特高的單漢字等。將停用詞扔掉減少了索引量，增加了檢索效率，提高檢索的效果。

2.2 TF-IDF關(guān)鍵詞提取

TF-IDF是一種統(tǒng)計(jì)方法，用以評(píng)估一字詞對(duì)于一個(gè)文件集或一個(gè)語(yǔ)料庫(kù)中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時(shí)會(huì)隨著它在語(yǔ)料庫(kù)中出現(xiàn)的頻率成反比下降。TF-IDF加權(quán)的各種形式常被搜索引擎應(yīng)用，作為文件與用戶(hù)查詢(xún)之間相關(guān)程度的度量或評(píng)級(jí)。TFIDF的主要思想是：如果某個(gè)詞或短語(yǔ)在一篇文章中出現(xiàn)的頻率TF高，并且在其他文章中很少出現(xiàn)，則認(rèn)為此詞或者短語(yǔ)具有很好的類(lèi)別區(qū)分能力，適合用來(lái)分類(lèi)。某一特定文件內(nèi)的高詞語(yǔ)頻率，以及該詞語(yǔ)在整個(gè)文件集合中的低文件頻率，可以產(chǎn)生出高權(quán)重的TF-IDF。因此，TF-IDF傾向于過(guò)濾掉常見(jiàn)的詞語(yǔ)，保留重要的詞語(yǔ)。①

3 改進(jìn)k-means算法

K-MEANS算法是輸入聚類(lèi)個(gè)數(shù)k，以及包含 n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)，輸出滿(mǎn)足方差最小標(biāo)準(zhǔn)k個(gè)聚類(lèi)的一種算法。k-means 算法接受輸入量 k ;然后將n個(gè)數(shù)據(jù)對(duì)象劃分為 k個(gè)聚類(lèi)以便使得所獲得的聚類(lèi)滿(mǎn)足：同一聚類(lèi)中的對(duì)象相似度較高;而不同聚類(lèi)中的對(duì)象相似度較小。

基本步驟：

（1） 從 n個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類(lèi)中心;

（2） 根據(jù)每個(gè)聚類(lèi)對(duì)象的均值（中心對(duì)象），計(jì)算每個(gè)對(duì)象與這些中心對(duì)象的距離;并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分;

（3） 重新計(jì)算每個(gè)（有變化）聚類(lèi)的均值（中心對(duì)象）;

（4） 計(jì)算標(biāo)準(zhǔn)測(cè)度函數(shù)，當(dāng)滿(mǎn)足一定條件，如函數(shù)收斂時(shí)，則算法終止;如果條件不滿(mǎn)足則回到步驟（2）。

聚類(lèi)相似度是利用各聚類(lèi)中對(duì)象的均值所獲得一個(gè)“中心對(duì)象”（引力中心）來(lái)進(jìn)行計(jì)算的。②

Synonyms是一個(gè)開(kāi)源的中文近義詞工具包。可以用于自然語(yǔ)言理解的很多任務(wù)：文本對(duì)齊，推薦算法，相似度計(jì)算，語(yǔ)義偏移，關(guān)鍵字提取，概念提取，自動(dòng)摘要，搜索引擎等。目前很缺乏質(zhì)量好的中文近義詞庫(kù)，于是便考慮使用 word2vec 訓(xùn)練一個(gè)高質(zhì)量的同義詞庫(kù)將“非標(biāo)準(zhǔn)表述”映射到“標(biāo)準(zhǔn)表述”，這就是 Synonyms 的起源。在經(jīng)典的信息檢索系統(tǒng)中，相似度的計(jì)算是基于匹配的，而且是 Query 經(jīng)過(guò)分詞后與文檔庫(kù)的嚴(yán)格的匹配，這種就缺少了利用詞匯之間的“關(guān)系”。而 word2vec 使用大量數(shù)據(jù)，利用上下文信息進(jìn)行訓(xùn)練，將詞匯映射到低維空間，產(chǎn)生了這種“關(guān)系”，這種“關(guān)系”是基于距離的，有了這種“關(guān)系”，就可以進(jìn)一步利用詞匯之間的距離進(jìn)行檢索。所以，在算法層面上，檢索更是基于了“距離”而非“匹配”，基于“語(yǔ)義”而非“形式”。②

對(duì)比Synonyms較之于以上兩者具有更大的詞匯量，更便于針對(duì)中文詞語(yǔ)進(jìn)行語(yǔ)意辨析。下面選擇一些在同義詞詞林、知網(wǎng)和Synonyms都存在的幾個(gè)詞，給出其近似度的對(duì)比：

k-means算法里，需要首先隨機(jī)地選擇k個(gè)對(duì)象代表簇的初始均值或中心;由此看出弊端，直接選取文檔中k個(gè)詞為主簇，并不能準(zhǔn)確地概括出文本的中心主題，加大了聚簇工作量。由于k-means算法在初始化簇的種子對(duì)象時(shí)的隨機(jī)性，被選到的K個(gè)對(duì)象中可能包括詞義遠(yuǎn)離文本主題的詞。不同的初始中心的選擇對(duì)聚類(lèi)結(jié)果有較大的影響。改進(jìn)k-means，以關(guān)鍵詞中的k個(gè)對(duì)象經(jīng)過(guò)Synonyms相近詞聚類(lèi)處理后作為預(yù)判簇的初始中心，解決了上述缺陷，保證了文本中心主題的準(zhǔn)確。

同時(shí)運(yùn)用k-means算法和Synonyms工具包就可以得到文本的幾個(gè)簇，解決了文本主題的單一性。語(yǔ)料庫(kù)中每篇文檔可以統(tǒng)計(jì)出多個(gè)主題，根據(jù)主題不同，多篇文檔有多種聚類(lèi)組合方式。

4 總結(jié)與展望

s-k（Synonyms-k-means）主題聚類(lèi)算法解決了文本主題單一的問(wèn)題，改善了k-means存在的隨機(jī)性大的問(wèn)題，改善了僅用關(guān)鍵詞聚類(lèi)的不精確，利用關(guān)鍵詞間的語(yǔ)義聯(lián)系提高了聚類(lèi)的準(zhǔn)確度。但算法用到的tf-idf算法更適用于長(zhǎng)文本，所以在關(guān)鍵詞提取方面還有提升空間。

注釋?zhuān)?/p>

① 來(lái)源于百度百科.

② 來(lái)源于自然語(yǔ)言處理之近義詞包 Synonyms——胡小夕.

參考文獻(xiàn)：

[1] 吳啟明，易云飛. 文本聚類(lèi)綜述[J].. 河池學(xué)院學(xué)報(bào)，2008（2）.

[2] 唐曉波，房小可. 基于文本聚類(lèi)與 LDA 相融合的微博主題檢索模型研究[J].. 情報(bào)理論與實(shí)踐，2013（8）.

[3] 田久樂(lè)，趙蔚. 基于同義詞詞林的詞語(yǔ)相似度計(jì)算方法[J].. 吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），2010（6）.

[4] 李國(guó)佳. 基于知網(wǎng)的中文詞語(yǔ)相似度計(jì)算[J]. 智能計(jì)算機(jī)與應(yīng)用，2015（3）.

[5] 張丹. 基于主題模型的話(huà)題聚類(lèi)算法的研究. 北京郵電大學(xué)碩士論文，2017.

[6] 吳敏.網(wǎng)絡(luò)短文本主題聚類(lèi)研究. 華中科技大學(xué)，2015.

[7] 張宜浩，金澎，孫銳. 基于改進(jìn) k-means 算法的中文詞義歸納[J]. 計(jì)算機(jī)應(yīng)用.2012，32（5）.

[8] 張亞男. 基于混合聚類(lèi)算法的微博熱點(diǎn)話(huà)題發(fā)現(xiàn)的研究[J]. 杭州電子科技大學(xué)學(xué)報(bào)， 2018（1）.

[9] https：//github.com/huyingxi/Synonyms/.