基于局部模塊度社團劃分算法的文本概念聚類新方法

劉紹海，安娜，祁越

（1.武警警種學院訓練部，北京102202；2.裝備學院航天裝備系，北京101416）

基于局部模塊度社團劃分算法的文本概念聚類新方法

劉紹海1，安娜2，祁越1

（1.武警警種學院訓練部，北京102202；2.裝備學院航天裝備系，北京101416）

提出一種將概念格和社團劃分方法兩種理論結合的文本聚類方法，首先將節點特征值權值按照從大到小的順序映射到形式背景中，然后通過計算出形式背景中概念相似度的大小，構造L網絡，最后根據局部模塊度社團劃分算法規則對待聚類文本進行聚類。

復雜網絡；文本聚類；綜合特征值；局部模塊度

隨著計算機網絡的高速發展，導致信息量的激增，人們必須通過一種高效快捷的方法才能使這些海量數據為我所用。通過文本聚類的方法，可以從中挖掘和提取有用信息，提高信息檢索的速度和效率。文本聚類方法較多，主要有劃分的方法、基于密度的聚類方法、基于SOM神經網絡方法等。這些方法在不同的領域都分別得到了成功的應用。

形式概念分析方法是將概念和概念層次用數學形式清楚地表示出來，是一種聚類分析方法。通過本文分析，由形式背景生成概念的過程本質上可看作概念聚類的過程，另外通過研究發現，尋找復雜網絡[1]中節點的社團結構，也是一種聚類過程。基于形式概念分析和復雜網絡的思想，本文提出了基于局部模塊度社團劃分算法的文本概念聚類新方法，在文本空間向量模型的基礎上，應用局部模塊度社團劃分的思想，實現文本概念聚類，為文本聚類提供了一個新的思路和方法。

1 預備知識

1.1 概念相似度

形式概念分析本質上是一種概念聚類技術，它是通過概念格形式表現出來，可以分析概念間關系，挖掘語義關系，為了分析概念之間的關系，本文引用作者之前研究的概念相似度公式。

定義1：一個背景中的兩個概念C1=（A1，B1），C2=（A2，B2），其概念相似度[2]定義如下：

其中，|B1|=m；|B2|=n；O=max{|A1|，|A2|}；k={j|as。其中，w是權值，它的取值范圍是0≤w≤1，它表示概念中對象和屬性重要程度。as（）表示兩個屬性的自明相似度。

1.2 節點的綜合特征值

定義1：節點的聚類系數[1]：是指與該節點相連的近鄰節點之間互連的比例。

依據復雜網絡中鄰居節點的概念，ki個節點之間最多可能有ki（ki-1）/2條邊。下式（2）為節點vi的聚類系數Ci：

其中，Ei表示ki個節點之間實際存在的邊數。

本文通過節點的度和聚類系數Ci計算節點的綜合特征值CFi：

其中，0＜α＜1，N為節點的個數。

1.3 局部模塊度

2001年，Girvan和Newnan提出GN算法，它是一個基于邊介數的社團發現算法，雖然GN算法有很多優點，但其需要大量的計算，因此，為了規避該這個缺點，clauset將局部模塊度的思想引入到GN算法中，通過大量的實驗驗證，該方法不僅大大降低了算法的時間復雜度，其聚類效果也非常理想。局部模塊度[3]定義為：

Lin指若將節點加入該社團內，社團內部邊的數目；Lout指若將節點加入該社團內，該社團內節點與不屬于該社團的節點連接的邊的數目；本文提出算法的主要思想是對候選集中的每個節點vk，假如將節點vk是加入到社團C中，計算將vk加入到社團C后社團C的Q值，則將使Q值最大的節點加入到社團C中，同時更新節點候選集合，當節點局部模塊度值不再改變，表明社團C形成，不會再有節點屬于該社團，其它社團形成也采用上述方法，直到所有節點都有所歸屬的社團，則網絡的社團結構形成。

本文的初始節點CFi選取節點最大的節點。如圖1表示，網絡的節點分為三部分。點集C表示屬于某個社團的節點集合；點集β表示并未屬于到任何社團但與C中的點與β中的點有連接的點的集合，點集β作為社團的候選集合；點集μ表示與C中的點無連接邊且不屬于任何社團的點的集合。

圖1 節點分析方法

2 基于局部模塊度社團劃分算法的文本概念聚類新方法

本文基于概念格的相關理論和局部模塊的思想提出了一種基于局部模塊度社團劃分算法的文本概念聚類新方法。首先對待聚類的文檔集進行預處理；然后根據概念格構造理論，構造形式背景，其方法是將節點特征值按照從大到小的順序完成形式背景的建立，采用作者之前的研究成果相似度公式，計算形式背景中概念相似度，構造特征概念相似度矩陣；最后，應用局部模塊度社團劃分方法進行文本聚類。

該算法描述如下：

輸入：待聚類的文檔及閾值λ；

輸出：聚類結果；

Step1：提取每篇文檔各關鍵詞并計算關鍵詞的特征詞權值；關鍵詞的自明度as（）從專家庫中讀取；

Step3：應用建格算法構造概念；

Step4：構造相似矩陣。采用公式（1）計算各概念間的相似度Sim（C1，C2），構造相似矩陣；

Step5：構造矩陣L.將Sim（C1，C2）大于θ的轉化為1，Sim（C1，C2）小于θ的轉化為0，形成新的矩陣L=（Sim（Ci，Cj））n×n；

Step6：掃描矩陣L，對每個節點都建立一個線性動態鏈表T.

IDCCFCw

I表示節點標號；D表示該節點的度；C表示節點的聚類系數；CF表示綜合特征值，通過公式（3）計算；Cw表示節點所在的社團標號，當其值為0時，表示節點為候選集節點，未被分配到社團中。此時各節點的社團標號值設為0.

Step7：選取初始節點。首先在動態鏈表中對各節點的綜合特征值按從大到小進行排序，新社團的初始點為社團標號為0且CFi最大的節點。

Step8：確定候選集合。

矯形方式為棒平移矯形，邊界條件為約束T1椎體上部在X、Y軸方向上的自由度，同時約束骶骨和骨盆的自由度。矯形上棒時將棒預彎一定角度，凹側上棒矯形。手術節段為T2 ～ L2。上棒矯形過程中沒有考慮肌肉和胸廓對手術的影響。術后測量胸椎、胸腰段和腰椎曲度，同時測量螺釘對應的拔出力。

將在動態鏈表中的社團標號為0且與Cw中的點相連的點的集合作為候選集合B，若所有節點的社團標號均不為0，此時社團w己形成，執行步驟11；

Step9：社團結構的形成。

對于候選集合B中的每個節點vk，如果將點vk屬于社團Cw，計算社團Cw的模塊度qk；通過計算，得到加入新節點后，社團Cw最大的模塊度qk；如果qk大于qc，則更新qc值（qc為未加入新節點時的社團Cw的局部模塊度），并將相應的qk所對應的節點vk并入到社團Cw中，并將該節點的社團標號更改為w；如果qk小于qc，表示社團已形成，執行步驟11；

Step10：執行8、9；

Step11：得到社團w；

Step12：執行7、8、9、10、11；

Step13：得到聚類結果；

從Step6到算法結束，是應用局部模塊度社團劃

分方法進行文本概念聚類。

3 例子

本文通過實例給出了基于局部模塊度社團劃分算法的文本概念聚類新方法計算過程。圖2表示本例的形式背景。

圖2 21個文檔的形式背景

根據算法，首先使用建格軟件，將形式背景轉化成Hasse圖，Hasse圖共有五層，產生95個概念。由于篇幅有限，本文節選出出現概率較大的10個概念：

x1（2 5 7 13，ack）x2（14 16，adj）

x3（15 16 20 21，afgj）x4（4 8 9，abei）

x5（1 9 11，abio）x6（1 3 11，adio）

x7（11 16，adfgo）x8（17 19，agjln）

x9（2 9，acfhi）x10（10 11 12，abdgn）

自明度為：as（eg）=0.9as（co）=0.7

as（dl）=0.9as（cd）=0.9as（fk）=0.8

as（fn）=0.9as（ki）=0.9as（ij）=0.9

as（eo）=0.8as（kj）=0.8.

由于相似度的計算要需要對象和屬性的權重，屬性的權重要大一些，因此假定屬性的權值設為0.8，則對象權值為0.2.應用相似度公式（1）得到矩陣R=（Sim（Ci，Cj））1010；

本例設θ=0.52，對矩陣進行θ=0.52截處理得矩陣L.通過查看網絡結點動態鏈表T（表1），節點1的綜合征值0.5為最大，則選取節點1為初始節點，初始節點選取后候選集也確定了，候選集β為β= {2、5、6、7、9}；在β中，找到使局部模塊度最大的點并入到社團1中，這一步通過公式（4）計算，更新β，最后得到Q為0.556，此時Q值不再增加，根據算法的思想，第一個社團已經形成，更新社團內節點動態鏈表中的社團標號為1；從動態鏈表中社團標號為0的節點選出一個綜合特征值最大的節點，本例中為節點8，重復上述步驟，當局部模塊度為0.417時，Q值不再增加，第二個社團己形成，將這些節點動態鏈表中社團標號標識為2.此時動態鏈表中社團標號沒有社團標號為0的節點，表明所有節點都歸屬于某個社團，網絡的社團結構已經形成，因此10個概念的劃分結果為：{x1x2x4x5x6x9}{x3x7x8x10}.

表1 網絡結點動態鏈表T

4 結論

本文是作者在先前研究工作的基礎上提出了改進的文本聚類的算法。將局部模塊度社團劃分算法應用到文本概念聚類中，衡量網絡劃分模塊標準的提出，極大地降低了算法的復雜度；同時通過定義概念格相似度，將對象和屬性同時應用到相似度計算中，使用文本相似度的計算方法更加全面準確，實驗結果驗證了聚類算法的正確性。本文提出的算法適用于海量文本這種高維數據，為文本聚類提供一個新的研究方法。

[1]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

[2]謝福鼎，安娜，黃丹.一種基于內容相似度和推薦反饋的信息模型[J].計算機科學，2009，36（4）：215-231.

[3]Xutao Wang，Guanrong Chen，Hongtao Lu.A very fast algo rithm for detecting community structures in complex networks [J].Physica A384（2007）：667-674.

A New Method for Text Concept Clustering based on Detecting Community Structures by Local Modularity in Complex Network

LIU Shao-hai1，AN Na2，QI Yue1
（1.Training Department，Specialized Forces College of Capf，Beijing 102202，China；2.Department of Space Equipment，Equipment Academy，Beijing 101416，China）

This paper gives a new text clustering method which takes the advantages of concept lattice and complex network.The algorithm firstly computes the weights of the key words and then the formal context is constructed in terms of key words which have the proper weight.Secondly，building L network，the similarities between concepts are computed，clustering the text of cluster by detecting community structures by local modularity algorithm rule，clustering results can be received.

complex networks；text clustering；multifactor value；local modularity

TP391

：A

：1672-545X（2017）01-0012-04

2016-10-02

劉紹海（1978-），男，遼寧人，博士，講師，研究方向：人工智能；安娜（1983-），女，遼寧鞍山人，碩士研究生，講師，主要研究領域：人工智能。