基于語義和圖的文本聚類算法研究

蔣 旦，周文樂，朱 明

(中國科學技術大學 信息科學技術學院，安徽 合肥230027)

基于語義和圖的文本聚類算法研究

蔣 旦，周文樂，朱 明

(中國科學技術大學 信息科學技術學院，安徽 合肥230027)

傳統的文本聚類往往采用詞包模型構建文本向量，忽略了詞語間豐富的語義信息。而基于中心劃分的聚類算法，容易將概念相關的自然簇強制分開，不能很好地發現人們感興趣的話題。該文針對傳統文本聚類算法的缺點，提出一種基于語義和完全子圖的短文本聚類算法，通過對目前主流的三大語義模型進行了實驗和對比，選擇了一種較為先進的語義模型，基于該語義模型進行了聚類實驗，發現新算法能較好地挖掘句子的語義信息且較傳統的K-means有更高的聚類純度。

文本聚類；完全子圖；語義相似度；詞向量

1 引言

文本聚類，在自然語言處理、人工智能和機器學習領域占有重要地位，它提供了一種從文本數據中自動學習知識的方法，可以從海量數據中挖掘人們感興趣的話題。而文本(語義)相似度的計算是文本聚類的先決條件。

經典的自然語言處理方法主要有兩種： 一種是基于詞包(bag-of-words)的統計數學模型，采用one-hot 的表示方法將詞轉換成一個高維的稀疏向量，維數等于詞匯量的大小，進而由詞向量的加和表示語句，忽略詞語之間語義聯系以及詞序。這種基于統計模型的方法雖然簡單，但是由于沒有考慮語言的語義這一重要屬性，表達能力有限，在復雜的涉及語義理解的文本聚類、機器翻譯等任務中表現不佳；另一種是基于語義詞典的方法，基于人工編纂的語義詞典，通過兩個詞在詞典樹形關系圖中的距離以及同義反義詞關系來計算兩個詞之間的語義相似度，然后通過某一種特定的詞匯組合方式表達句子之間的相似度。這方面的研究成果有英文的WordNet、中文的《知網》《同義詞詞林》等。然而這類方法存在很多缺陷[1]： 詞典的編纂需要投入大量的人力且嚴重依賴人的主觀判斷，更新速度慢，覆蓋的詞匯范圍非常有限。于是一方面人們期望建立好的語言模型和相似度度量，作為文本聚類和機器學習的基礎；另一方面，人們也期望不采用人工而是通過機器學習的方法，自動學習詞語的語義表示，更好地挖掘文本的深層信息。

我們的研究正是機器學習與自然語言處理的融合。具體來說，我們首先通過機器學習完成語義模型的訓練；然后設計實驗觀察實驗效果選擇好的語義模型，并且基于選擇的語義模型，提出一種基于圖的文本聚類算法；最后通過實驗證明了算法的可行性和優點。

本文章節安排如下： 第二節介紹了關于語義模型和圖聚類算法的相關工作；第三節闡述了本文提出的基于語義和圖的文本聚類算法的框架；第四節介紹了關于選擇語義模型和算法驗證的兩組實驗設計及結果；第五節對本文工作進行了總結并提出了對未來工作的展望。

2 相關工作

國內關于語義相似度的研究一直比較少，其中較為突出的是文獻[2]中劉群等提出的基于《知網》以及另一個同樣基于詞典的哈工大的《同義詞詞林》的詞匯語義相似度計算，而中文方面也缺少比較權威的語義相似度的測試集。

國外比較早的研究有由Scott Deerwester等于1990年提出的潛在語義分析算法[3](LSA，Latent Semantic Analysis)，LSA算法構造單詞—文檔矩陣，基于單詞在文檔中TF-IDF(詞頻—逆文檔頻率)統計發掘詞語之間的潛在語義關系，并通過SVD(奇異值分解)將文檔向量映射到LSA語義空間，以達到降維和降噪的目的，此時便可以在低維的LSA語義空間計算文檔的相似度。該算法已經在信息檢索領域取得巨大成功并得到廣泛應用。

之后針對潛在語義分析Gabrilovich于2006年提出另一著名算法顯明語義分析[4-5](ESA，Explicit Semantic Analysis)，ESA算法同樣構造一個單詞-文檔矩陣，不過此時每一個文檔對應于Wikipedia中的一個詞條，也即一個概念，單詞在該詞條文檔中的TF-IDF值表明了單詞與概念的相關度。于是ESA算法將單詞與文檔映射到Wikipedia概念空間，得到單詞或文檔的一個高維向量表示，進而計算單詞或文檔的相似度。該算法在WordSimilarity-353測試集上取得了0.75的準確率，代表了當時的最高成就。

近年來，基于神經網絡(深度學習)的語言模型重新得到重視。Bengio在文獻[6]中提出一種神經網絡概率語言模型，該模型為由一個線性映射層和一個非線性隱層構成的前向神經網絡，其中提到通過訓練語言模型可以同時得到詞向量(Distributed representations of words in a vector space)。之后Mikolov在研究中簡化了Bengio提出的神經網絡模型，提出CBOW模型和Skip-gram模型[7-8]，這兩個模型的最終目的并不是為了訓練一個語言模型，而只是為了得到單詞的語義向量，簡化后的模型提高了訓練速度，而得到的詞向量則可以被利用在各種不同的自然語言處理任務中。除了Mikolov提出的詞向量模型外，文獻[9-10]等也提出了類似的詞向量模型，文獻[11]則將這一模型利用于構建中文分詞系統，取得一定成效。

有關圖的聚類算法較為經典的有變色龍算法(Chameleon Algorithm)和譜聚類算法(Spectral clustering)。基于圖的聚類算法基本思想是將一般的聚類問題通過鄰近度矩陣轉換成圖的劃分問題。而譜聚類算法又巧妙地將圖的分割問題轉換成拉普拉斯矩陣特征向量的聚類問題[12]。Chameleon算法則在圖分割后采用層次聚類進一步合并圖分割中產生的各個小簇，得到最終的聚類結果[13]。本文提出的基于語義和完全子圖的聚類算法，結構上和Chameleon算法非常類似，它們之間的區別將在下文介紹。

3 基于完全子圖的聚類算法

3.1 圖的基本理論

圖1 無向圖

3.2 算法描述

基于語義和完全子圖的聚類算法步驟如下：

算法3．2 基于語義和圖的聚類算法1：對于給定的文檔集xi{}，計算文檔對象之間的語義距離矩陣Dij{}2：構建圖GV，E()，并選擇恰當的距離閾值，進行圖的稀疏化3：將圖G的所有邊對象edgei，j，w()按距離w升序排列得到ES，index=-14：repeat：5： repeat：6： index++7： until：index≥ES或者graph中存在邊ESindex[]8： ifindex≥ESthen將剩余孤立點分別作為單獨的簇加入CS，break9： endif10： 選取ESindex[]的頂點作為擴展的初始結點np加入到簇C，將所有與np連接的頂點按距離升序排列得到VS11： repeat：12： 依次從VS中選取頂點加入到簇C，并判斷是否滿足完全子圖的要求，滿足保留，否則拋棄13： until：VS為空14： 得到一個簇C，加入CS，從G中刪除C15：until：G為空16：得到所有的簇CS，計算簇之間的距離矩陣DCij{}17：對簇集合CS重復2～15得到簇的聚類CCS18：綜合CS和CCS輸出最后聚類結果

由于基于完全子圖的聚類要求結點之間具有全連接，可以保證聚類的結點都有較高的語義相似度，但是此時得到的聚類數目可能較多，我們需要進一步的聚合。算法3.2中的16～17即是對初次聚合的簇進行二次聚類。簇之間的距離度量可以采用層次聚類[15]中三種簇的鄰近性度量中的任何一種： 單鏈： 兩個簇中距離最小的兩個點的距離；全鏈： 兩個簇中距離最大的兩個點的距離；組平均： 兩個簇中所有點兩兩之間距離的均值。本文采用第三種對噪聲數據不太敏感的組平均度量。

綜合兩次聚合結果，即可得到最終的聚合簇。

3.3 算法復雜度分析

3.4 與傳統聚類算法的對比

相比于K-means算法，圖聚類算法不受質心的約束，并通過強連接性保證簇的純度，而且無需指定最終的聚類類別(K-means的K值)就能自動完成聚類。

從結構上來看，本文提出的算法與Chameleon算法非常相似。算法大體分為三個步驟： (1)稀疏化； (2)圖劃分； (3)聚類。前者采用固定閾值稀疏化，而Chameleon采用k近鄰稀疏化；前者通過提取團來對圖進行分割，后者則通過多層圖劃分將圖分割到足夠小，而兩者的目的都是為保證子簇的純度；對于聚類，前者依舊采取團提取方式，而后者采用層次聚類。基于完全子圖的聚類算法和Chameleon算法具有相同的計算復雜度。

4 實驗及結果

4.1 語義模型訓練及選擇

本文采用的訓練語料庫為截止至2015年3月1號的中文維基百科所有詞條文檔。維基百科是當前最具影響的互聯網百科全書，由來自世界各地的志愿者合作編輯而成，內容覆蓋廣、更新速度快、詞條質量高(這一要求對于基于概念的ESA模型是至關重要的，ESA模型將每一個文檔視為語義空間的一個概念，因此要求文檔內容是概念相關并且盡量準確的)。經過文本提取、繁化簡、分詞、過濾短文本和過濾低頻詞預處理，最后剩下308 345個詞條，包含的詞匯大小為665 941，文本總大小約1GB。

分別訓練了LSA，ESA以及詞向量模型，其中LSA和詞向量維數均為100維(選取更大維數，得到的詞或文檔向量將包含更多的語義信息，但訓練時間更長，存儲更大)。對于詞向量模型，正如Mikolov在文獻[7]中提到的，向量之間滿足一定程度的線性運算關系，我們測試了向量[“中科大”]-向量[“中國”]+向量[“美國”]得到的最相似的結果是向量[“普渡大學”](0.755，相似度)，而向量[“哈佛大學”]-向量[“美國”]+向量[“中國”]得到的最相似的結果是向量[“北京大學”](0.761)。

我們設計了一個檢索實驗來考察三個語義模型的效果，實驗數據為從互聯網爬取的約48萬條各類新聞標題中隨機抽取的1 000條，首先分別轉換成三個語義模型下的向量，然后通過選取不同類別中具有代表性的條目，計算圍繞該樣本條目最相似的k=10個樣本，通過人工評測比較不同語義模型下的檢索結果。經過多組對比實驗發現詞向量能較好地捕獲文本深層次的語義信息。表1中以“文化”類別為例，列舉了三個模型前五條檢索結果。

表1 LSA、ESA、W2V模型語義檢索實驗結果

表1中第(1)條為檢索條目，(2～5)為檢索的相似結果，分別按語義距離排名，條目前列出了兩位小數的距離值，不同語義模型之間的距離不具有可比性。從檢索結果看出，LSA和ESA模型側重于關鍵字“上海”，結果中均是屬于上海的新聞，而W2V模型則側重于“文化”這一主題。雖然三種模型在不同環境下各有優勢，但是對于新聞，人們的興趣可能更傾向于相似的主題。

另外我們統計了1 000條新聞標題之間的語義距離得到如下語義距離的概率密度曲線。

圖2 距離概率密度曲線(LSA、ESA、W2V)

綜合評估下，我們選用了傾向相似主題并具有較好區分度的W2V(詞向量)模型作為比較K-means和完全子圖聚類算法的語義模型。

4.2 基于語義和圖的文本聚類實驗

以W2V語義模型為基礎，我們通過實驗對比了基于圖的聚類算法和傳統的K-means算法的聚類效果。實驗設計如下： 依然采用前面抽取的1 000條新聞標題作為數據集，轉化為W2V空間的語義向量并計算距離矩陣；分別采用基于圖的聚類算法和K-means算法聚類；隨機選擇不同類別中若干具有代表性的樣本，計算樣本所在類別中與該樣本最鄰近的n個樣本作為聚類代表，最后分析和評價聚類效果。

關于K-means算法中的K值選取，我們參考了K-means方法在上述數據集上的SSE(Sum of the Squared Error)曲線和平均輪廓系數(Silhouette Coefficient)曲線[15]，如圖3所示。從圖中可以看出，SSE曲線隨簇數增加而遞減但并沒有明顯的轉折點，而輪廓系數曲線存在多個波峰，其中四個明顯的波峰分別是8、12、17和21，為了獲得較多的感興趣簇，我們選擇了K=21。對于基于圖聚類算法中圖稀疏化閾值的選取，初始聚類和對簇的二次聚類我們均采取保留1/3連接的策略，即對距離矩陣升序排序后選擇排序在1/3處的距離作為閾值，這樣選取的是因為一方面保留1/3的邊連接可以保證相連結點之間相似度較高；另一方面在該實驗中除去少數孤立點后，也可以得到近20個簇，和K-means中的K值相當。

圖3 K-means算法SSE曲線(左)、輪廓系數曲線(右)

表2中列舉了五個不同標簽下的聚類結果，表中第一列標示了所采用的算法，以及聚類后人為標定的標簽。第二列和表1中的含義相同。

表2 W2V模型下K-means和完全子圖聚類結果

續表

續表

對比于表3中基于W2V語義模型的K-means聚類結果，基于完全子圖的聚類表現出一定的優勢，“國際”標簽中后者聚類的結果更加貼合選擇的代表樣本(1)中“合作”這一主題；“事故”標簽中后者更強調“墜機”事件；“大賽”標簽中則注重于“文化”領域；“城市”標簽也更貼合“品牌”這一主題。對于“體育”、“財經”、“政治”等特征比較明顯的標簽，則兩種算法的聚類幾乎差不多，表中未一一列舉。

分析實驗數據我們還可以發現盡管一些樣本和選擇的代表樣本本身相似度更高(同一語義模型下的距離更小)，按照K-means它們將聚為一類，而基于完全子圖的算法卻沒有把它們聚成一類，例如，“事故”標簽K-means聚類中的(2)(以下記作K-2)與(1)的距離為0.72，而完全子圖算法中(2)(以下記作G-2)與(1)的距離為0.73，完全子圖算法聚合了G-2這一樣本卻沒有包含K-2，K-(3～5)樣本的距離也分別小于G-(3～5)的距離。同樣的現象也出現在“大賽”、“城市”標簽的聚類結果中。

這種現象可以簡單地解釋如下： 如果已知A和B相似，現在判斷C是否與A相似，根據K-means算法，只要C和A足夠近似就可以了，而完全子圖還需要C和B也足夠近似，這個要求體現在滿足極大完全子圖的條件中。因此完全子圖聚類能夠得到一個相關度更強的類。

當然基于極大完全子圖的聚類算法也有一定的缺陷，即容易產生孤立點(本文對孤立點的處理方式是讓其單獨成簇)，而K-means的聚類則不會出現這樣的現象。

5 總結與展望

本文基于中文維基百科訓練并比較了三種語義模型，并提出一種基于語義和圖的文本聚類算法，該算法能夠從語義層次對文本進行聚類，并且相對于傳統的K-means算法具有一定的優勢。文中詳細闡述了算法的原理及特點，并通過實驗驗證了算法的可行性及優勢，在語義聚類方面表現出巨大潛力。

在語義模型方面，本文采用詞向量加和構成句子的語義向量。而文獻[17]中提出的PV(Paragraph Vector)算法則試圖直接訓練句子或文檔的語義向量。由于詞向量的這種簡單組合方式并不能很好地表示句法結構，直接訓練句子的語義向量在語義挖掘上可能會更具優勢。另外，近年來深度學習在圖像處理、語音識別領域取得了突破性進展，其強大的特征提取能力也有望在自然語言處理領域做出貢獻[18]。

在聚類算法方面，隨著機器學習與各學科的融合，聚類算法被應用到各個領域，同時也出現許多從具體領域衍生出的聚類算法。例如，曾應用于計算機視覺領域的譜聚類[12]算法現在作為一種通用機器學習方法表現十分突出。而基于圖的聚類算法依然具有很大的挖掘空間，仍將會是機器學習領域研究的熱點。

[1] Ping L. 詞匯相似度研究進展綜述[J]. 現代圖書情報技術, 28(7/8): 82-89.

[2] 劉群, 李素建. 基于《知網》 的詞匯語義相似度計算[J]. 中文計算語言學, 2002, 7(2): 59-76.

[3] Deerwester S C, Dumais S T, Landauer T K, et al. Indexing by latent semantic analysis[J]. JAsIs, 1990, 41(6): 391-407.

[4] Gabrilovich E, Markovitch S. Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis[C]//Proceedings of IJCAI.2007, 7: 1606-1611.

[5] Gabrilovich E, Markovitch S. Wikipedia-based semantic interpretation for natural language processing[J]. Journal of Artificial Intelligence Research, 2009: 443-498.

[6] Bengio Y, Ducharme R, Vincent P, et al. A neural probabilistic language model[J]. The Journal of Machine Learning Research, 2003, 3: 1137-1155.

[7] Mikolov T, Chen K, Corrado G, et al. Efficient estimation of word representations in vector space[J]. arXiv.2013: 1301,3781.

[8] Mikolov T, Sutskever I, Chen K, et al. Distributed representations of words and phrases and their compositionality[C]//Proceedings of the Advances in Neural Information Processing Systems.2013: 3111-3119.

[9] Collobert R, Weston J, Bottou L, et al. Natural language processing (almost) from scratch[J]. The Journal of Machine Learning Research, 2011, 12: 2493-2537.

[10] Pennington J,Socher R, Manning C D. Glove: Global vectors for word representation[J]. Proceedings of the Empiricial Methods in Natural Language Processing (EMNLP 2014), 2014: 12.

[11] 來斯惟, 徐立恒, 陳玉博, 等. 基于表示學習的中文分詞算法探索[J]. 中文信息學報, 2013, 27(5): 8-14.

[12] Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and computing, 2007, 17(4): 395-416.

[13] Karypis G, Han E H, Kumar V. Chameleon: Hierarchical clustering using dynamic modeling[J]. Computer, 1999, 32(8): 68-75.

[14] Bron C, Kerbosch J. Algorithm 457: finding all cliques of an undirected graph[J]. Communications of the ACM, 1973, 16(9): 575-577.

[15] Tan P N, Steinbach M, Kumar V. Introduction to data mining[M]. Boston: Pearson Addison Wesley, 2006.

[16] Karp R M. Reducibility among combinatorial problems[M]. springer US, 1972.

[17] Le Q V, Mikolov T. Distributed representations of sentences and documents[J]. arXiv.2014: 1405,4053.

[18] Mnih A, Hinton G. Three new graphical models for statistical language modelling[C]//Proceedings of the 24th international conference on Machine learning. ACM, 2007: 641-648.

Research on Text Clustering Based on Semantics and Graph

JIANG Dan， ZHOU Wenle， ZHU Ming

(School of Information Science and Technology ,University of Science and Technology of China,Hefei，Anhui 230027,China)

Traditional methods for text clustering have generally taken the BOW (bag-of-words) model to construct the vector of document, ignoring semantic information between words. And partitioning clustering method based on centroid tends to split concept closely related clusters stiffly, not suitable for mining interesting topics. To address these issues, , this paper proposes a text clustering method based on semantics and cliques. Compared with three popular semantic models, experiments reveal that our method performs better than K-means on semantic clustering task.

text clustering method；complete sub-graph；semantic similarity；distributed representations of words in a vector space

蔣旦(1992—)，碩士，主要研究領域為自然語言處理與數據挖掘。E?mail：djiang@mail．ustc．edu．cn周文樂(1989—)，碩士，主要研究領域為推薦系統，數據挖掘。E?mail：zhouwenle@outlook．com朱明(1963—)，博士，教授，博士生導師，主要研究領域為視頻大數據分析，智能機器人，未來網絡。E?mail：mzhu@ustc．edu．cn

1003-0077(2016)05-0121-08

2015-04-07 定稿日期： 2015-06-02

海量網絡數據流海云協同實時處理系統(子課題)(XDA06011203);電視商務綜合體新業態運營支撐系統開發(2012BAH73F01)