基于Synonyms、k-means的短文本聚類算法

回玥婷 夏懿嘉 陳紫荷 佟鑫

摘要：當今社會，網絡搜索成為人們獲取資訊的主流。短文本因特征信息不足且高維稀疏等特點，導致傳統文本聚類算法應用于短文本聚類時效率低下。為此，我們采用為關鍵詞以及k-means和synonyms相結合的方法，提高主題歸類精確度。實驗證明，我們提出的s-k（Synonyms-k-means）主題聚類算法不僅有效歸類主題，而且能挖掘出詞語的潛在含義。

關鍵詞：文本聚類;短文本;k-means;synonyms

中圖分類號：TP301? ? ? ? 文獻標識碼：A? ? ? ? 文章編號：1009-3044（2019）01-0005-02

1 引言

網絡社交平臺的廣泛應用，使得人們越發偏向通過閱讀屏幕上的文本內容獲得自己想要了解的信息，網絡搜索成為人們獲取資訊的主流，以提高用戶的使用舒適度為目的，國內外的研究人員針對主題檢索和文本聚類方法在不斷地進行完善。如何提高文本聚類的準確度是研究人員需要繼續改進的問題?；ヂ摼W的信息呈現多元化，文本內容冗雜不一，并且微博等短文本具有文本短小的特征，針對中文新生詞語詞義以及主題的歧義之特點，傳統的文本檢索方法不足滿足當前用戶的需求。因此，得出一種更加快速、高效的短文本聚類方法顯得極為迫切。

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

針對傳統文本聚類方法存在的詞義分析不確切的不足，我們在目前已有的基礎上，采用k-means和synonyms相結合的算法，該算法具有更大的詞匯量，更便于針對中文詞語進行語意辨析，通過計算強化了詞語之間的近似度，有效地進行近義詞的辨析，提高了文本類簇主題的精確度，實現了對短文本主題進行更加快速準確的檢索，以最大程度滿足用戶需求。

2 算法內容

2.1文本預處理

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

分詞過后，將得到的分詞遍歷一下載入的停用詞表，去掉停用詞。停用詞主要包括英文字符、數字、數學字符、標點符號及使用頻率特高的單漢字等。將停用詞扔掉減少了索引量，增加了檢索效率，提高檢索的效果。

2.2 TF-IDF關鍵詞提取

TF-IDF是一種統計方法，用以評估一字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現的次數成正比增加，但同時會隨著它在語料庫中出現的頻率成反比下降。TF-IDF加權的各種形式常被搜索引擎應用，作為文件與用戶查詢之間相關程度的度量或評級。TFIDF的主要思想是：如果某個詞或短語在一篇文章中出現的頻率TF高，并且在其他文章中很少出現，則認為此詞或者短語具有很好的類別區分能力，適合用來分類。某一特定文件內的高詞語頻率，以及該詞語在整個文件集合中的低文件頻率，可以產生出高權重的TF-IDF。因此，TF-IDF傾向于過濾掉常見的詞語，保留重要的詞語。①

3 改進k-means算法

K-MEANS算法是輸入聚類個數k，以及包含 n個數據對象的數據庫，輸出滿足方差最小標準k個聚類的一種算法。k-means 算法接受輸入量 k ;然后將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高;而不同聚類中的對象相似度較小。

基本步驟：

（1） 從 n個數據對象任意選擇 k 個對象作為初始聚類中心;

（2） 根據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離;并根據最小距離重新對相應對象進行劃分;

（3） 重新計算每個（有變化）聚類的均值（中心對象）;

（4） 計算標準測度函數，當滿足一定條件，如函數收斂時，則算法終止;如果條件不滿足則回到步驟（2）。

聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”（引力中心）來進行計算的。②

Synonyms是一個開源的中文近義詞工具包?？梢杂糜谧匀徽Z言理解的很多任務：文本對齊，推薦算法，相似度計算，語義偏移，關鍵字提取，概念提取，自動摘要，搜索引擎等。目前很缺乏質量好的中文近義詞庫，于是便考慮使用 word2vec 訓練一個高質量的同義詞庫將“非標準表述”映射到“標準表述”，這就是 Synonyms 的起源。在經典的信息檢索系統中，相似度的計算是基于匹配的，而且是 Query 經過分詞后與文檔庫的嚴格的匹配，這種就缺少了利用詞匯之間的“關系”。而 word2vec 使用大量數據，利用上下文信息進行訓練，將詞匯映射到低維空間，產生了這種“關系”，這種“關系”是基于距離的，有了這種“關系”，就可以進一步利用詞匯之間的距離進行檢索。所以，在算法層面上，檢索更是基于了“距離”而非“匹配”，基于“語義”而非“形式”。②

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

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

同時運用k-means算法和Synonyms工具包就可以得到文本的幾個簇，解決了文本主題的單一性。語料庫中每篇文檔可以統計出多個主題，根據主題不同，多篇文檔有多種聚類組合方式。

4 總結與展望

s-k（Synonyms-k-means）主題聚類算法解決了文本主題單一的問題，改善了k-means存在的隨機性大的問題，改善了僅用關鍵詞聚類的不精確，利用關鍵詞間的語義聯系提高了聚類的準確度。但算法用到的tf-idf算法更適用于長文本，所以在關鍵詞提取方面還有提升空間。

注釋：

① 來源于百度百科.

② 來源于自然語言處理之近義詞包 Synonyms——胡小夕.

參考文獻：

[1] 吳啟明，易云飛. 文本聚類綜述[J].. 河池學院學報，2008（2）.

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

[3] 田久樂，趙蔚. 基于同義詞詞林的詞語相似度計算方法[J].. 吉林大學學報（信息科學版），2010（6）.

[4] 李國佳. 基于知網的中文詞語相似度計算[J]. 智能計算機與應用，2015（3）.

[5] 張丹. 基于主題模型的話題聚類算法的研究. 北京郵電大學碩士論文，2017.

[6] 吳敏.網絡短文本主題聚類研究. 華中科技大學，2015.

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

[8] 張亞男. 基于混合聚類算法的微博熱點話題發現的研究[J]. 杭州電子科技大學學報， 2018（1）.

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