蔣 旦，周文樂(lè)，朱 明

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥230027)

基于語(yǔ)義和圖的文本聚類(lèi)算法研究

蔣 旦，周文樂(lè)，朱 明

(中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥230027)

傳統(tǒng)的文本聚類(lèi)往往采用詞包模型構(gòu)建文本向量，忽略了詞語(yǔ)間豐富的語(yǔ)義信息。而基于中心劃分的聚類(lèi)算法，容易將概念相關(guān)的自然簇強(qiáng)制分開(kāi)，不能很好地發(fā)現(xiàn)人們感興趣的話(huà)題。該文針對(duì)傳統(tǒng)文本聚類(lèi)算法的缺點(diǎn)，提出一種基于語(yǔ)義和完全子圖的短文本聚類(lèi)算法，通過(guò)對(duì)目前主流的三大語(yǔ)義模型進(jìn)行了實(shí)驗(yàn)和對(duì)比，選擇了一種較為先進(jìn)的語(yǔ)義模型，基于該語(yǔ)義模型進(jìn)行了聚類(lèi)實(shí)驗(yàn)，發(fā)現(xiàn)新算法能較好地挖掘句子的語(yǔ)義信息且較傳統(tǒng)的K-means有更高的聚類(lèi)純度。

文本聚類(lèi)；完全子圖；語(yǔ)義相似度；詞向量

1 引言

文本聚類(lèi)，在自然語(yǔ)言處理、人工智能和機(jī)器學(xué)習(xí)領(lǐng)域占有重要地位，它提供了一種從文本數(shù)據(jù)中自動(dòng)學(xué)習(xí)知識(shí)的方法，可以從海量數(shù)據(jù)中挖掘人們感興趣的話(huà)題。而文本(語(yǔ)義)相似度的計(jì)算是文本聚類(lèi)的先決條件。

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

我們的研究正是機(jī)器學(xué)習(xí)與自然語(yǔ)言處理的融合。具體來(lái)說(shuō)，我們首先通過(guò)機(jī)器學(xué)習(xí)完成語(yǔ)義模型的訓(xùn)練；然后設(shè)計(jì)實(shí)驗(yàn)觀察實(shí)驗(yàn)效果選擇好的語(yǔ)義模型，并且基于選擇的語(yǔ)義模型，提出一種基于圖的文本聚類(lèi)算法；最后通過(guò)實(shí)驗(yàn)證明了算法的可行性和優(yōu)點(diǎn)。

本文章節(jié)安排如下： 第二節(jié)介紹了關(guān)于語(yǔ)義模型和圖聚類(lèi)算法的相關(guān)工作；第三節(jié)闡述了本文提出的基于語(yǔ)義和圖的文本聚類(lèi)算法的框架；第四節(jié)介紹了關(guān)于選擇語(yǔ)義模型和算法驗(yàn)證的兩組實(shí)驗(yàn)設(shè)計(jì)及結(jié)果；第五節(jié)對(duì)本文工作進(jìn)行了總結(jié)并提出了對(duì)未來(lái)工作的展望。

2 相關(guān)工作

國(guó)內(nèi)關(guān)于語(yǔ)義相似度的研究一直比較少，其中較為突出的是文獻(xiàn)[2]中劉群等提出的基于《知網(wǎng)》以及另一個(gè)同樣基于詞典的哈工大的《同義詞詞林》的詞匯語(yǔ)義相似度計(jì)算，而中文方面也缺少比較權(quán)威的語(yǔ)義相似度的測(cè)試集。

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

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

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

有關(guān)圖的聚類(lèi)算法較為經(jīng)典的有變色龍算法(Chameleon Algorithm)和譜聚類(lèi)算法(Spectral clustering)?；趫D的聚類(lèi)算法基本思想是將一般的聚類(lèi)問(wèn)題通過(guò)鄰近度矩陣轉(zhuǎn)換成圖的劃分問(wèn)題。而譜聚類(lèi)算法又巧妙地將圖的分割問(wèn)題轉(zhuǎn)換成拉普拉斯矩陣特征向量的聚類(lèi)問(wèn)題[12]。Chameleon算法則在圖分割后采用層次聚類(lèi)進(jìn)一步合并圖分割中產(chǎn)生的各個(gè)小簇，得到最終的聚類(lèi)結(jié)果[13]。本文提出的基于語(yǔ)義和完全子圖的聚類(lèi)算法，結(jié)構(gòu)上和Chameleon算法非常類(lèi)似，它們之間的區(qū)別將在下文介紹。

3 基于完全子圖的聚類(lèi)算法

3.1 圖的基本理論

圖1 無(wú)向圖

3.2 算法描述

基于語(yǔ)義和完全子圖的聚類(lèi)算法步驟如下：

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

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

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

3.3 算法復(fù)雜度分析

3.4 與傳統(tǒng)聚類(lèi)算法的對(duì)比

相比于K-means算法，圖聚類(lèi)算法不受質(zhì)心的約束，并通過(guò)強(qiáng)連接性保證簇的純度，而且無(wú)需指定最終的聚類(lèi)類(lèi)別(K-means的K值)就能自動(dòng)完成聚類(lèi)。

從結(jié)構(gòu)上來(lái)看，本文提出的算法與Chameleon算法非常相似。算法大體分為三個(gè)步驟： (1)稀疏化； (2)圖劃分； (3)聚類(lèi)。前者采用固定閾值稀疏化，而Chameleon采用k近鄰稀疏化；前者通過(guò)提取團(tuán)來(lái)對(duì)圖進(jìn)行分割，后者則通過(guò)多層圖劃分將圖分割到足夠小，而兩者的目的都是為保證子簇的純度；對(duì)于聚類(lèi)，前者依舊采取團(tuán)提取方式，而后者采用層次聚類(lèi)?；谕耆訄D的聚類(lèi)算法和Chameleon算法具有相同的計(jì)算復(fù)雜度。

4 實(shí)驗(yàn)及結(jié)果

4.1 語(yǔ)義模型訓(xùn)練及選擇

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

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

我們?cè)O(shè)計(jì)了一個(gè)檢索實(shí)驗(yàn)來(lái)考察三個(gè)語(yǔ)義模型的效果，實(shí)驗(yàn)數(shù)據(jù)為從互聯(lián)網(wǎng)爬取的約48萬(wàn)條各類(lèi)新聞標(biāo)題中隨機(jī)抽取的1 000條，首先分別轉(zhuǎn)換成三個(gè)語(yǔ)義模型下的向量，然后通過(guò)選取不同類(lèi)別中具有代表性的條目，計(jì)算圍繞該樣本條目最相似的k=10個(gè)樣本，通過(guò)人工評(píng)測(cè)比較不同語(yǔ)義模型下的檢索結(jié)果。經(jīng)過(guò)多組對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)詞向量能較好地捕獲文本深層次的語(yǔ)義信息。表1中以“文化”類(lèi)別為例，列舉了三個(gè)模型前五條檢索結(jié)果。

表1 LSA、ESA、W2V模型語(yǔ)義檢索實(shí)驗(yàn)結(jié)果

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

另外我們統(tǒng)計(jì)了1 000條新聞標(biāo)題之間的語(yǔ)義距離得到如下語(yǔ)義距離的概率密度曲線(xiàn)。

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

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

4.2 基于語(yǔ)義和圖的文本聚類(lèi)實(shí)驗(yàn)

以W2V語(yǔ)義模型為基礎(chǔ)，我們通過(guò)實(shí)驗(yàn)對(duì)比了基于圖的聚類(lèi)算法和傳統(tǒng)的K-means算法的聚類(lèi)效果。實(shí)驗(yàn)設(shè)計(jì)如下： 依然采用前面抽取的1 000條新聞標(biāo)題作為數(shù)據(jù)集，轉(zhuǎn)化為W2V空間的語(yǔ)義向量并計(jì)算距離矩陣；分別采用基于圖的聚類(lèi)算法和K-means算法聚類(lèi)；隨機(jī)選擇不同類(lèi)別中若干具有代表性的樣本，計(jì)算樣本所在類(lèi)別中與該樣本最鄰近的n個(gè)樣本作為聚類(lèi)代表，最后分析和評(píng)價(jià)聚類(lèi)效果。

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

圖3 K-means算法SSE曲線(xiàn)(左)、輪廓系數(shù)曲線(xiàn)(右)

表2中列舉了五個(gè)不同標(biāo)簽下的聚類(lèi)結(jié)果，表中第一列標(biāo)示了所采用的算法，以及聚類(lèi)后人為標(biāo)定的標(biāo)簽。第二列和表1中的含義相同。

表2 W2V模型下K-means和完全子圖聚類(lèi)結(jié)果

續(xù)表

續(xù)表

對(duì)比于表3中基于W2V語(yǔ)義模型的K-means聚類(lèi)結(jié)果，基于完全子圖的聚類(lèi)表現(xiàn)出一定的優(yōu)勢(shì)，“國(guó)際”標(biāo)簽中后者聚類(lèi)的結(jié)果更加貼合選擇的代表樣本(1)中“合作”這一主題；“事故”標(biāo)簽中后者更強(qiáng)調(diào)“墜機(jī)”事件；“大賽”標(biāo)簽中則注重于“文化”領(lǐng)域；“城市”標(biāo)簽也更貼合“品牌”這一主題。對(duì)于“體育”、“財(cái)經(jīng)”、“政治”等特征比較明顯的標(biāo)簽，則兩種算法的聚類(lèi)幾乎差不多，表中未一一列舉。

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

這種現(xiàn)象可以簡(jiǎn)單地解釋如下： 如果已知A和B相似，現(xiàn)在判斷C是否與A相似，根據(jù)K-means算法，只要C和A足夠近似就可以了，而完全子圖還需要C和B也足夠近似，這個(gè)要求體現(xiàn)在滿(mǎn)足極大完全子圖的條件中。因此完全子圖聚類(lèi)能夠得到一個(gè)相關(guān)度更強(qiáng)的類(lèi)。

當(dāng)然基于極大完全子圖的聚類(lèi)算法也有一定的缺陷，即容易產(chǎn)生孤立點(diǎn)(本文對(duì)孤立點(diǎn)的處理方式是讓其單獨(dú)成簇)，而K-means的聚類(lèi)則不會(huì)出現(xiàn)這樣的現(xiàn)象。

5 總結(jié)與展望

本文基于中文維基百科訓(xùn)練并比較了三種語(yǔ)義模型，并提出一種基于語(yǔ)義和圖的文本聚類(lèi)算法，該算法能夠從語(yǔ)義層次對(duì)文本進(jìn)行聚類(lèi)，并且相對(duì)于傳統(tǒng)的K-means算法具有一定的優(yōu)勢(shì)。文中詳細(xì)闡述了算法的原理及特點(diǎn)，并通過(guò)實(shí)驗(yàn)驗(yàn)證了算法的可行性及優(yōu)勢(shì)，在語(yǔ)義聚類(lèi)方面表現(xiàn)出巨大潛力。

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

在聚類(lèi)算法方面，隨著機(jī)器學(xué)習(xí)與各學(xué)科的融合，聚類(lèi)算法被應(yīng)用到各個(gè)領(lǐng)域，同時(shí)也出現(xiàn)許多從具體領(lǐng)域衍生出的聚類(lèi)算法。例如，曾應(yīng)用于計(jì)算機(jī)視覺(jué)領(lǐng)域的譜聚類(lèi)[12]算法現(xiàn)在作為一種通用機(jī)器學(xué)習(xí)方法表現(xiàn)十分突出。而基于圖的聚類(lèi)算法依然具有很大的挖掘空間，仍將會(huì)是機(jī)器學(xué)習(xí)領(lǐng)域研究的熱點(diǎn)。

[1] Ping L. 詞匯相似度研究進(jìn)展綜述[J]. 現(xiàn)代圖書(shū)情報(bào)技術(shù), 28(7/8): 82-89.

[2] 劉群, 李素建. 基于《知網(wǎng)》 的詞匯語(yǔ)義相似度計(jì)算[J]. 中文計(jì)算語(yǔ)言學(xué), 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] 來(lái)斯惟, 徐立恒, 陳玉博, 等. 基于表示學(xué)習(xí)的中文分詞算法探索[J]. 中文信息學(xué)報(bào), 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—)，碩士，主要研究領(lǐng)域?yàn)樽匀徽Z(yǔ)言處理與數(shù)據(jù)挖掘。E?mail：djiang@mail．ustc．edu．cn周文樂(lè)(1989—)，碩士，主要研究領(lǐng)域?yàn)橥扑]系統(tǒng)，數(shù)據(jù)挖掘。E?mail：zhouwenle@outlook．com朱明(1963—)，博士，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橐曨l大數(shù)據(jù)分析，智能機(jī)器人，未來(lái)網(wǎng)絡(luò)。E?mail：mzhu@ustc．edu．cn

1003-0077(2016)05-0121-08

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

海量網(wǎng)絡(luò)數(shù)據(jù)流海云協(xié)同實(shí)時(shí)處理系統(tǒng)(子課題)(XDA06011203);電視商務(wù)綜合體新業(yè)態(tài)運(yùn)營(yíng)支撐系統(tǒng)開(kāi)發(fā)(2012BAH73F01)