一種基于TextRank的文本二次聚類算法

潘曉英，胡開開，朱 靜

(西安郵電大學 計算機學院，陜西 西安 710121)

一種基于TextRank的文本二次聚類算法

潘曉英，胡開開，朱 靜

(西安郵電大學 計算機學院，陜西 西安 710121)

針對傳統文本聚類技術中存在的聚類精度一般或者運算時間復雜度過高等問題，文中首先介紹了兩種較為常用的文本聚類技術：基于劃分的K-means和基于主題模型的LDA。在分析各自缺陷的基礎上，提出一種基于TextRank的文本二次聚類算法。該算法借鑒主題模型的思想，在傳統的聚類過程中引入詞聚類，并在關鍵詞提取階段融合詞語的位置與跨度特征，減少了由局部關鍵詞作為全局關鍵詞帶來的誤差。實驗結果表明，改進后的算法在聚類效果上要優于傳統的VSM聚類和基于主題模型的LDA算法。

文本聚類；TextRank；

提取；向量空間模型；LDA

1 概 述

隨著大數據時代的來臨，互聯網上的文檔數據呈爆炸式增長，如何從這些海量數據中獲取有效信息已經成為NLP(Nature Language Processing，自然語言處理)領域的重點[1]。作為數據挖掘領域的重要分支，聚類技術被廣泛研究。一種快速、高效的聚類算法能夠自動地將看似雜亂無章的文檔數據集合組織成少量的有意義的簇，進而以簡明、容易訪問的方式提交結果[2]。因此，聚類技術在文本挖掘、Web搜索以及新聞推薦系統等領域中發揮著重要作用[3]。

目前針對文本聚類的方法主要分為兩類：

第一類是向量空間模型[4](Vector Space Model，VSM)。這類算法以關鍵詞權重信息來構建文檔向量，根據所采用的某種相似度度量計算文檔之間的“距離”，隨后采用K-means進行聚類。VSM中最常見的詞加權方式是TF-IDF[5](TermFrequency-InverseDocumentFrequency，詞頻-逆文檔頻率)，但是該模型的缺陷是模型假設各個詞的出現是獨立不相關的，導致無法從語義上分析文檔內容。馬暉男等[6]提出了一種修正的向量空間模型(MVSM)。該模型采用信息短語進行信息表示，對查詢索引項進行擴展，并建立了能夠自動生成的同義詞詞典，有效改善了文本信息檢索系統的性能。宋丹等[7]借助自然語言理解技術，根據語義特征將文檔關鍵詞分為N維向量空間，在每個空間上進行獨立的權重和相似度計算，實驗結果表明該方法在新聞的話題識別和跟蹤技術中要優于傳統方法。相比較TF-IDF，圖方法更能體現文檔關鍵詞之間的結構關系，最具代表性的是TextRank[8]，該算法將文本看作是一個由詞節點組成的網絡，節點之間的鏈接權重代表了詞之間的語義關系。基于TextRank的詞權重排序算法同樣被研究者廣泛關注，其中方康等[9]提出一種基于馬爾可夫模型加權TextRank的單文檔關鍵詞抽取算法，結果表明準確率有所提高。顧益軍等[10]將候選關鍵詞的重要性按照主題影響力和鄰接關系進行非均勻傳遞，并構建新的概率轉移矩陣進行詞圖迭代計算，可以顯著改善關鍵詞的抽取效果。

第二類為潛在狄利克雷分布LDA(LatentDirichletAllocation)：是一種文檔主題生成模型。即一篇文章的每個詞都是以一定概率選擇了某個主題，并從某個主題中以一定概率選擇了某個詞。處理過程中可以將數據建模為混合話題，這些話題不僅僅是文檔簇，同時也是詞的概率分布。該方法具備先驗性假設，不易產生過擬合，更加符合實際文檔的主題分布,缺點是計算復雜度較高，在大規模數據集上會遇到計算瓶頸[11]。Mimno與McCallum[12]提出一種DirichletCompoundMultinomialLDA(DCM-LDA)算法。DCM利用分布式集群進行訓練，集群中的每臺機器首先對分發在其上面的語料進行吉布斯采樣，各自維護一個局部主題模型(LocalTopicModel)，當訓練完成時將所有的主題模型融合在一起，在一定程度上能解決復雜度過高的問題。張小平等[13]提出一種基于高斯函數的加權方法，降低了高頻詞對主題分布的影響，實驗結果表明改進后的模型更能清晰地表達文檔主題。李文波等[14]提出一種附加類別標簽的LDA模型，即在傳統LDA模型訓練過程中融入文本類別信息，克服了訓練過程中強制分配隱含主題的缺陷，可以有效地改進文本分類性能。

文中借鑒主題模型的思想，并充分利用word2vec[15]對于中文文本生成詞向量的高效性以及精確性，提出一種基于TextRank的文本二次聚類方法。該方法在傳統聚類過程中引入了詞聚類，并在關鍵詞提取階段融合詞語的位置與跨度特征，減少了由局部關鍵詞作為全局關鍵詞帶來的誤差。實驗結果表明，該方法在聚類精度以及效率上均有不同程度的提高。

2 文本聚類

傳統的文本聚類方法是將原始文本數據集合進行預處理，隨后進行向量化并對其進行K-means聚類。具體步驟如下：

2.1 文本預處理

首先對數據進行去噪，包括剔除異常值、圖片、視頻、音頻等記錄。隨后利用中文分詞系統進行中文分詞、去除停用詞等。

2.2 文本向量化

要對文本進行聚類，首先要對文本進行向量化表示。經典的方法是用TF-IDF和TextRank來表示文本的詞權重信息。TF-IDF算法的思想是，如果詞在一篇文檔中出現的頻率高而在其他文檔中很少出現，則認為該詞具有很好的區分能力。TextRank算法借鑒Google網頁排名方法PageRank[16]，該算法利用網頁之間的相互投票來迭代計算網頁的重要度。具體到TextRank，即事先設定一個固定的滑動窗口大小K，將窗口內的詞看作是圖中的節點，同一窗口內出現的詞之間通過邊相連，通過不斷地向后移動窗口來增加圖中的邊，隨后通過迭代計算詞的權重。對于單詞i:

(1)TF-IDF的權重信息計算公式為:

(1)

其中，TFi為該詞在文本中的出現頻率；N為文本總數；DFi為該詞出現的文本個數。取對數是為了消除在最終的詞權重中TF的影響。

(2)TextRank的權重信息計算公式為:

WS(vi)=(1-d)+d×

(2)

其中，WS(vi)表示節點vi的權重；In(vi)、Out(vj)分別表示指向節點vi的集合以及節點vj所指向的節點集合；Wji表示連接兩節點之間的邊的權重；d為阻尼系數，取值0.85。

2.3K-means聚類

K-means[17]文本聚類的基本思想是首先從上述向量化后的數據對象中隨機抽取K個對象作為初始聚類中心，隨后計算剩下的對象到這些聚類中心的距離，將其分配給距離最近的類;然后重新計算每個類中新的聚類中心。重復這一過程，直至測度函數收斂。一般采用誤差的平方和作為標準測度函數，其定義為：

(3)

其中，E為數據集中所有對象的誤差平方和；k為聚類個數；p為給定的文本對象；Ci為簇i的中心點。

針對文本聚類，一般采用余弦相似度計算文本之間的“距離”。公式如下：

Dist(di,dj)=1-cos(di,dj)=

其中，di,dj分別表示文本i,j；n表示文本向量的維度；Pik和Pjk分別表示i和j的文本向量在第k維上的取值。

由該公式可知，若兩個文本相同，則cos(di,dj)=1，即Dist()=0，二者距離最小。反之，若兩個文本是“相互獨立”的，則cos(di,dj)=0，即Dist()=1，二者距離最大。

基于VSM的K-means文本聚類算法的優點是實現簡單，時間復雜度較低，可解釋性強。但是，基于VSM的方式對文本進行向量化后無法清晰地表達文本內容，會導致聚類效果不是很好，需要進一步改進。

3 基于TextRank的文本二次聚類

針對上述聚類方法聚類精度不足的缺陷，文中提出一種基于TextRank的文本二次聚類算法，通過減少由局部關鍵詞作為全局關鍵詞帶來的誤差來增強向量化文本的表達能力。首先，利用開源深度學習工具word2vec對預處理過的文檔中的詞生成詞向量，并進行詞聚類[18]。然后，針對每篇文檔，計算文檔中每個詞語的權重值并統計每個詞所屬聚類，對每一個類別下的所有詞進行加權求和，得到該文檔的類別特征分布，進而采用K-means算法進行第二次聚類。改進后的算法流程如圖1所示。

圖1 算法流程圖

3.1 預處理

對文本集合進行預處理采用2.1所述的方式。

3.2 詞聚類

在Linux環境下，運用word2vec工具對輸入的數據進行詞聚類。word2vec是Google于2013年開源推出的一個用于獲取word vector的工具包，它可以將某種格式的輸入文本轉化為一個K維向量。這樣，就可以通過計算向量之間的相似度來表示文本之間的語義相似度。

3.3 關鍵詞權重計算

考慮到傳統的TF-IDF關鍵詞提取技術無法從語義上分析文檔，故文中采用當前比較流行的圖模型(TextRank)并加以改進來進行文檔關鍵詞的提取。直接利用以上公式提取出的關鍵詞會更傾向于局部高頻詞和無用詞，真正能代表文檔的關鍵詞卻因為權值低而被召回。因此，為了提高結果的準確性和說服力，在計算關鍵詞權值時考慮以下特征：

(1)位置。

如果文檔中某候選關鍵詞出現在了該文檔的標題中，那么很明顯該詞作為關鍵詞的概率要大于那些文檔中未出現在標題中的詞。所以，在計算詞語權重時需要將位置信息考慮進來。具體計算公式為：

(5)

(2)詞跨度。

在TextRank算法中，由于滑動窗口的設定，在同一窗口內會經常有若干相同詞的情況，這樣就會導致算法的提取結果是局部關鍵詞而非全局關鍵詞。為了消除這種由于詞的出現范圍而帶來的計算誤差，可將詞的跨度特征也引入到關鍵詞權重計算中。其值為該詞在文檔中第一次出現與最后一次出現的位置之差。如果該值較大，說明其作為全局關鍵詞的可能較越大，從而避免了一些局部關鍵詞被誤作為全局關鍵詞。

通過以上兩個特征的引入，候選關鍵詞i的計算公式如下:

(6)

其中，WSi是i的TextRank值；Loci是i的位置特征值；Spani是i的跨度特征值；Lasti和Firsti分別表示i在該文檔中最后一次和第一次出現的位置，考慮到只出現一次詞語作為文檔關鍵字的可能性極小，為降低該詞權重，文中將每篇文檔中詞語頻度為1的Firsti取值為0，Lasti取值為1；Sum表示文檔的詞語總數。

按照上述權值計算過程，選取文檔中的前N個詞作為文檔的特征關鍵詞，將每篇文檔表示成如下形式：

dj=〈〈word1j,weight1j〉,〈word2j,weight2j〉,…,〈wordNj,weightNj〉〉

3.4 統計文本類別分布

在2.2和2.3的基礎上，統計文本在各個類別下的分布。具體做法如下：首先在每篇文檔中選取N個詞，統計每個詞所屬類別。然后對同一個類下的所有關鍵字進行加權求和并做歸一化處理。得到的每篇文檔的分布特征如下：

dj=〈〈C1,wj1〉,〈C2,wj2〉,…,〈Ck,wjk〉〉

其中，k為類別數目；wjk表示文檔dj在Ck上歸一化處理之后的權值。

3.5 二次聚類

將每篇文檔按照上述方法表示成向量形式，并構建“文檔-類別分布”矩陣：

其中，m為總的文檔數；k為類別數量。

隨后利用K-means算法對所有的文檔向量進行二次聚類，得到最終的聚類結果。

4 實 驗

4.1 實驗語料

實驗語料從搜狗文本語料庫中下載，共涉及經濟、軍事、旅游、體育、文化和醫療六個子集，去噪后的每個子集大概包含300篇新聞文檔，共計1 998篇。

4.2 評測指標

實驗采用F值來衡量聚類效果。F值是一種綜合平衡準確率和召回率的評價指標。一般F值越高，說明聚類的效果越好。準確率、召回率與F值的計算公式如下：

(7)

8)

(9)

(10)

其中,nij為聚類后類別為j中實際類別為i的文檔數目；nj為聚類類別j的文檔總數目；ni為實際類別為i的文檔總數目。

4.3 實驗結果

實驗運行環境為Ubuntu14.04操作系統，CPU為Intel(R) Core(TM)i3-4150 3.50 GHz，4 GB內存，編程工具為Eclipse4.4.0，算法實現語言為Java，中文分詞采用Ansj中文分詞系統，詞聚類的實現借助word2vec。

在式(5)和式(6)計算關鍵詞權重過程中，詞語位置特征權重m取值為3。為了體現該詞語權重計算方法的有效性，文中將其與另外兩種方法得到的關鍵詞結果作對比。評價指標仍以K-means聚類結果的F值為準，如圖2所示。

由圖2可知，文中方法在關鍵詞抽取數量為50時效果最好，且采用該計算方法聚類效果明顯優于另外兩種方法。原因是該方法相當于綜合考慮了文檔的結構和語義信息。

圖2 不同關鍵詞數量下的三種算法聚類效果

在LDA建模階段，利用實驗來確定最優的主題數N，最終結果以最高F值時的主題個數為準。參數估計采用Gibbs抽樣算法[19]，超參數分別取值50/N，0.01，迭代次數設置為2 000次。同樣，采用實驗的方法來確定詞聚類過程中最優的詞聚類類別數量。該過程中的具體參數設置如表1所示。由圖3可知，當主題數目N=80、詞聚類類別數量為100時，聚類效果分別達到最優。

表1 word2vec參數設置情況

以F值為評價標準，得到LDA的最優主題數N及word2vec生成詞聚類過程中的最優詞類別數量。

圖3 不同主題/詞類別的聚類效果

在上述確定最優主題數N和最優詞聚類類別數量的同時，文中對兩者的算法執行時間進行了對比。結果如表2所示。

表2 兩種算法執行時間比較 s

由表2可知，文中方法的效率明顯優于LDA。原因是LDA在訓練過程中需要模擬Dirichlet過程并且不斷進行參數的調整，導致算法復雜度過高。而文中算法無需訓練，并且在利用word2vec進行詞聚類的過程中，由于采用了哈弗曼樹編碼、高頻詞亞采樣等方法，減少了算法執行時間。

實驗中為了消除K-means的不穩定性帶來的誤差影響，將文中提出的算法與傳統的基于VSM的K-means聚類算法(TF-IDF，TextRank)分別運行10次，結果取平均值，比較結果如圖4所示。

圖4 四種方法比較結果

4.4 實驗分析

從圖4中可以看出，文中算法的全局F值相對前三種分別提高了22%，18%，5%，主要原因是文中首先充分利用了word2vec這一工具的有效性，對詞進行聚類，最大程度上將語義相關的詞劃分到同一個類簇中，隨后再進行二次聚類時融入了文檔的關鍵詞位置和跨度特征，相當于綜合考慮了文檔的結構和語義信息。基于VSM的方法沒有考慮文檔的語義信息，所以效果一般。LDA與文中算法的結果雖然相差不大，但是在算法效率有明顯差距。

5 結束語

針對傳統中文文本聚類算法的不足，并借鑒主體模型的思想，文中提出一種基于TextRank的文本二次聚類算法。首次聚類充分利用Google開源深度學習工具word2vec的高效性和有效性，得到詞聚類集合。隨后在利用圖模型TextRank算法提取文檔特征詞階段融入詞的位置和跨度特征，使文本得到了更合理的表示，進而得到文本在詞聚類類別上的混合分布，即“文檔-類別”分布矩陣。二次聚類采用經典的基于劃分的K-means。實驗結果表明，改進算法在聚類效果和運行效率上均有所提高。

[1] 王元卓，靳小龍，程學旗.網絡大數據:現狀與展望[J].計算機學報，2013，36(6):1125-1138.

[2] 范 明，孟曉峰.數據挖掘概念與技術[M].北京：機械工業出版社，2012.

[3] 孟憲軍.互聯網文本聚類與檢索技術研究[D].哈爾濱:哈爾濱工業大學，2009.

[4] 姚清耘，劉功申，李 翔.基于向量空間模型的文本聚類算法[J].計算機工程，2008，34(18):39-41.

[5] 黃承慧，印 鑒，侯 昉.一種結合詞語義信息和TF-IDF方法的文本相似度量方法[J].計算機學報，2011，34(5):856-864.

[6] 馬暉男，吳江寧，潘東華.一種修正的向量空間模型在信息檢索中的應用[J].哈爾濱工業大學學報，2008，40(4):666-669.

[7] 宋 丹，王衛東，陳 英.基于改進向量空間模型的話題識別與跟蹤[J].計算機技術與發展，2006，16(9):62-64.

[8]MihalceaR，TarauP.TextRank:bringingorderintotexts[C]//ProceedingofEMNLP.[s.l.]:[s.n.],2004.

[9] 方 康，韓立新.基于HMM的加權TextRank單文檔的關鍵詞抽取算法[J].信息技術，2015，39(4):114-116.

[10] 顧益軍，夏 天.融合LDA與TextRank的關鍵詞抽取研究[J].現代圖書情報技術，2014(7):41-47.

[11] 劉知遠.基于文檔主題結構的關鍵詞抽取方法研究[D].北京:清華大學，2011.

[12]MimnoDM，McCallumA.OrganizingtheOCA:learningfacetedsubjectsfromalibraryofdigitalbooks[C]//ProcofACM/IEEEjointconferenceondigitallibraries.[s.l.]:IEEE,2007:376-385.

[13] 張小平，周雪忠，黃厚寬,等.一種改進的LDA主題模型[J].北京交通大學學報:自然科學版，2010，34(2):111-114.

[14] 李文波，孫 樂，張大鯤.基于Labeled-LDA模型的文本分類新算法[J].計算機學報，2008，31(4):620-627.

[15] 周 練.word2vec工作原理及應用探究[J].科技情報開發與經濟，2015，25(2):145-148.

[16]PageL，BrinS，MotwaniR，etal.ThePageRankcitationranking:bringingordertotheweb[R].[s.l.]:StanfordDigitalLibraryTechnologiesProject，1998.

[17] 孫吉貴，劉 杰，趙連宇.聚類算法研究[J].軟件學報，2008，19(1)：48-61.

[18] 鄭文超，徐 鵬.利用word2vec對中文詞進行聚類的研究[J].軟件，2013,34(12):160-162.

[19] 尤 芳.Gibbs抽樣在正態混合模型中的參數估計[J].統計與決策，2013(15):150-151.

A Secondary Text Clustering Algorithm Based on TextRank

PAN Xiao-ying，HU Kai-kai，ZHU Jing

(School of Computer,Xi’an University of Posts & Telecommunications,Xi’an 710121,China)

In view of the existing problems in the traditional text clustering technology，such as the general accuracy or the higher time complexity,two kinds of the commonly used text clustering technology are introduced at first,includingK-meansbasedonthedivisionandLDAbasedonthetheme.Onthebasisoftheanalysisoftheirrespectivedefects，asecondarytextclusteringalgorithmbasedontheTextRankispresented.Referenceofideaofthememodel,thealgorithmintroducesthewordclusteringintheprocessoftraditionalclustering,andmergesthefuturesoflocationandspaninthe

extractionphase,reducingtheerrorbylocalkeywordsasglobalkeywords.TheexperimentalresultsshowthattheimprovedalgorithmontheclustereffectissuperiortothetraditionalVSMclusteringandLDAalgorithmbasedonthethememodel.

text clustering；TextRank；keyword extraction；VSM；LDA

2015-09-26

2015-12-29

時間：2016-07-29

國家自然科學基金資助項目(61105064，61203311，61373116)；陜西省教育專項科研計劃(14JK1667)；西安郵電大學研究生創新基金項目(CXL2014-23)

潘曉英(1981-)，女，博士，副教授，研究方向為數據挖掘、計算智能；胡開開(1989-)，男，碩士研究生，研究方向為數據挖掘、推薦系統。

http://www.cnki.net/kcms/detail/61.1450.TP.20160729.1833.014.html

TP

A

1673-629X(2016)08-0007-05

10.3969/j.issn.1673-629X.2016.08.002