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

劉紹海，安娜，祁越

（1.武警警種學(xué)院訓(xùn)練部，北京102202；2.裝備學(xué)院航天裝備系，北京101416）

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

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

（1.武警警種學(xué)院訓(xùn)練部，北京102202；2.裝備學(xué)院航天裝備系，北京101416）

提出一種將概念格和社團(tuán)劃分方法兩種理論結(jié)合的文本聚類方法，首先將節(jié)點(diǎn)特征值權(quán)值按照從大到小的順序映射到形式背景中，然后通過計(jì)算出形式背景中概念相似度的大小，構(gòu)造L網(wǎng)絡(luò)，最后根據(jù)局部模塊度社團(tuán)劃分算法規(guī)則對待聚類文本進(jìn)行聚類。

復(fù)雜網(wǎng)絡(luò)；文本聚類；綜合特征值；局部模塊度

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

形式概念分析方法是將概念和概念層次用數(shù)學(xué)形式清楚地表示出來，是一種聚類分析方法。通過本文分析，由形式背景生成概念的過程本質(zhì)上可看作概念聚類的過程，另外通過研究發(fā)現(xiàn)，尋找復(fù)雜網(wǎng)絡(luò)[1]中節(jié)點(diǎn)的社團(tuán)結(jié)構(gòu)，也是一種聚類過程。基于形式概念分析和復(fù)雜網(wǎng)絡(luò)的思想，本文提出了基于局部模塊度社團(tuán)劃分算法的文本概念聚類新方法，在文本空間向量模型的基礎(chǔ)上，應(yīng)用局部模塊度社團(tuán)劃分的思想，實(shí)現(xiàn)文本概念聚類，為文本聚類提供了一個(gè)新的思路和方法。

1 預(yù)備知識(shí)

1.1 概念相似度

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

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

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

1.2 節(jié)點(diǎn)的綜合特征值

定義1：節(jié)點(diǎn)的聚類系數(shù)[1]：是指與該節(jié)點(diǎn)相連的近鄰節(jié)點(diǎn)之間互連的比例。

依據(jù)復(fù)雜網(wǎng)絡(luò)中鄰居節(jié)點(diǎn)的概念，ki個(gè)節(jié)點(diǎn)之間最多可能有ki（ki-1）/2條邊。下式（2）為節(jié)點(diǎn)vi的聚類系數(shù)Ci：

其中，Ei表示ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)。

本文通過節(jié)點(diǎn)的度和聚類系數(shù)Ci計(jì)算節(jié)點(diǎn)的綜合特征值CFi：

其中，0＜α＜1，N為節(jié)點(diǎn)的個(gè)數(shù)。

1.3 局部模塊度

2001年，Girvan和Newnan提出GN算法，它是一個(gè)基于邊介數(shù)的社團(tuán)發(fā)現(xiàn)算法，雖然GN算法有很多優(yōu)點(diǎn)，但其需要大量的計(jì)算，因此，為了規(guī)避該這個(gè)缺點(diǎn)，clauset將局部模塊度的思想引入到GN算法中，通過大量的實(shí)驗(yàn)驗(yàn)證，該方法不僅大大降低了算法的時(shí)間復(fù)雜度，其聚類效果也非常理想。局部模塊度[3]定義為：

Lin指若將節(jié)點(diǎn)加入該社團(tuán)內(nèi)，社團(tuán)內(nèi)部邊的數(shù)目；Lout指若將節(jié)點(diǎn)加入該社團(tuán)內(nèi)，該社團(tuán)內(nèi)節(jié)點(diǎn)與不屬于該社團(tuán)的節(jié)點(diǎn)連接的邊的數(shù)目；本文提出算法的主要思想是對候選集中的每個(gè)節(jié)點(diǎn)vk，假如將節(jié)點(diǎn)vk是加入到社團(tuán)C中，計(jì)算將vk加入到社團(tuán)C后社團(tuán)C的Q值，則將使Q值最大的節(jié)點(diǎn)加入到社團(tuán)C中，同時(shí)更新節(jié)點(diǎn)候選集合，當(dāng)節(jié)點(diǎn)局部模塊度值不再改變，表明社團(tuán)C形成，不會(huì)再有節(jié)點(diǎn)屬于該社團(tuán)，其它社團(tuán)形成也采用上述方法，直到所有節(jié)點(diǎn)都有所歸屬的社團(tuán)，則網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)形成。

本文的初始節(jié)點(diǎn)CFi選取節(jié)點(diǎn)最大的節(jié)點(diǎn)。如圖1表示，網(wǎng)絡(luò)的節(jié)點(diǎn)分為三部分。點(diǎn)集C表示屬于某個(gè)社團(tuán)的節(jié)點(diǎn)集合；點(diǎn)集β表示并未屬于到任何社團(tuán)但與C中的點(diǎn)與β中的點(diǎn)有連接的點(diǎn)的集合，點(diǎn)集β作為社團(tuán)的候選集合；點(diǎn)集μ表示與C中的點(diǎn)無連接邊且不屬于任何社團(tuán)的點(diǎn)的集合。

圖1 節(jié)點(diǎn)分析方法

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

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

該算法描述如下：

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

輸出：聚類結(jié)果；

Step1：提取每篇文檔各關(guān)鍵詞并計(jì)算關(guān)鍵詞的特征詞權(quán)值；關(guān)鍵詞的自明度as（）從專家?guī)熘凶x?。?/p>

Step3：應(yīng)用建格算法構(gòu)造概念；

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

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

Step6：掃描矩陣L，對每個(gè)節(jié)點(diǎn)都建立一個(gè)線性動(dòng)態(tài)鏈表T.

IDCCFCw

I表示節(jié)點(diǎn)標(biāo)號；D表示該節(jié)點(diǎn)的度；C表示節(jié)點(diǎn)的聚類系數(shù)；CF表示綜合特征值，通過公式（3）計(jì)算；Cw表示節(jié)點(diǎn)所在的社團(tuán)標(biāo)號，當(dāng)其值為0時(shí)，表示節(jié)點(diǎn)為候選集節(jié)點(diǎn)，未被分配到社團(tuán)中。此時(shí)各節(jié)點(diǎn)的社團(tuán)標(biāo)號值設(shè)為0.

Step7：選取初始節(jié)點(diǎn)。首先在動(dòng)態(tài)鏈表中對各節(jié)點(diǎn)的綜合特征值按從大到小進(jìn)行排序，新社團(tuán)的初始點(diǎn)為社團(tuán)標(biāo)號為0且CFi最大的節(jié)點(diǎn)。

Step8：確定候選集合。

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

將在動(dòng)態(tài)鏈表中的社團(tuán)標(biāo)號為0且與Cw中的點(diǎn)相連的點(diǎn)的集合作為候選集合B，若所有節(jié)點(diǎn)的社團(tuán)標(biāo)號均不為0，此時(shí)社團(tuán)w己形成，執(zhí)行步驟11；

Step9：社團(tuán)結(jié)構(gòu)的形成。

對于候選集合B中的每個(gè)節(jié)點(diǎn)vk，如果將點(diǎn)vk屬于社團(tuán)Cw，計(jì)算社團(tuán)Cw的模塊度qk；通過計(jì)算，得到加入新節(jié)點(diǎn)后，社團(tuán)Cw最大的模塊度qk；如果qk大于qc，則更新qc值（qc為未加入新節(jié)點(diǎn)時(shí)的社團(tuán)Cw的局部模塊度），并將相應(yīng)的qk所對應(yīng)的節(jié)點(diǎn)vk并入到社團(tuán)Cw中，并將該節(jié)點(diǎn)的社團(tuán)標(biāo)號更改為w；如果qk小于qc，表示社團(tuán)已形成，執(zhí)行步驟11；

Step10：執(zhí)行8、9；

Step11：得到社團(tuán)w；

Step12：執(zhí)行7、8、9、10、11；

Step13：得到聚類結(jié)果；

從Step6到算法結(jié)束，是應(yīng)用局部模塊度社團(tuán)劃

分方法進(jìn)行文本概念聚類。

3 例子

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

圖2 21個(gè)文檔的形式背景

根據(jù)算法，首先使用建格軟件，將形式背景轉(zhuǎn)化成Hasse圖，Hasse圖共有五層，產(chǎn)生95個(gè)概念。由于篇幅有限，本文節(jié)選出出現(xiàn)概率較大的10個(gè)概念：

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.

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

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

表1 網(wǎng)絡(luò)結(jié)點(diǎn)動(dòng)態(tài)鏈表T

4 結(jié)論

本文是作者在先前研究工作的基礎(chǔ)上提出了改進(jìn)的文本聚類的算法。將局部模塊度社團(tuán)劃分算法應(yīng)用到文本概念聚類中，衡量網(wǎng)絡(luò)劃分模塊標(biāo)準(zhǔn)的提出，極大地降低了算法的復(fù)雜度；同時(shí)通過定義概念格相似度，將對象和屬性同時(shí)應(yīng)用到相似度計(jì)算中，使用文本相似度的計(jì)算方法更加全面準(zhǔn)確，實(shí)驗(yàn)結(jié)果驗(yàn)證了聚類算法的正確性。本文提出的算法適用于海量文本這種高維數(shù)據(jù)，為文本聚類提供一個(gè)新的研究方法。

[1]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[2]謝福鼎，安娜，黃丹.一種基于內(nèi)容相似度和推薦反饋的信息模型[J].計(jì)算機(jī)科學(xué)，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-），女，遼寧鞍山人，碩士研究生，講師，主要研究領(lǐng)域：人工智能。