一種基于最大公共子圖的文本譜聚類算法

馮仁群山 陳笑蓉

摘 要：傳統(tǒng)的基于空間向量的文本譜聚類方法容易忽略文本上下文之間的語義聯(lián)系，通過圖結(jié)構(gòu)進(jìn)行文本表示可以很好的解決這一問題，在此基礎(chǔ)上，本文提出了基于最大公共子圖的譜聚類算法——SC-MCS算法。該算法通過求解文本之間的最大公共子圖來進(jìn)行文本相似度的計算，最后進(jìn)行文本聚類。實驗結(jié)果表明，與傳統(tǒng)的基于空間向量的文本譜聚類方法相比，該算法在準(zhǔn)確率和召回率都取得了一定的提升。

關(guān)鍵詞：文本聚類；譜聚類；最大公共子圖

中圖分類號：TP391.1

文獻(xiàn)標(biāo)識碼： A

隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們訪問和獲取的信息呈幾何級數(shù)急劇增長，如何有效地對海量文本信息進(jìn)行聚類一直是文本挖掘領(lǐng)域的一個研究熱點。大多數(shù)傳統(tǒng)的聚類算法都是基于凸樣本空間，當(dāng)樣本空間不凸時，算法容易陷入局部最優(yōu)。為了對任意形狀的樣本空間都能夠進(jìn)行聚類并收斂到全局最優(yōu)解，學(xué)者們提出了一種新的聚類算法——譜聚類算法 [1]。首先，根據(jù)給定的樣本數(shù)據(jù)集定義一個相似矩陣來描述數(shù)據(jù)點之間的相似性，然后計算矩陣的特征值和特征向量，最后針對不同的數(shù)據(jù)點選取合適的特征向量來完成聚類。譜聚類算法已成功地應(yīng)用于語音識別、圖像和視頻分割、文本聚類等領(lǐng)域。

譜聚類算法是一種基于圖論的聚類算法，其本質(zhì)是將聚類問題轉(zhuǎn)化為圖的最優(yōu)切分問題，在文本聚類方面具有很好的應(yīng)用前景。傳統(tǒng)的譜聚類算法是基于向量空間模型（Vector Space Model）來進(jìn)行相似矩陣的構(gòu)造，VSM模型通過向量空間進(jìn)行文本表示，進(jìn)而將文本轉(zhuǎn)換為向量形式，并在向量空間中計算文本相似度[2]。雖然該模型具有簡單高效、處理方便的優(yōu)點，然而該模型也存在一些不足之處：一是特征維度較高，冗余信息和稀疏數(shù)據(jù)較多；二是特征項相互獨立，無法體現(xiàn)特征項在文本中出現(xiàn)的順序、特征項之間的關(guān)聯(lián)等文本結(jié)構(gòu)信息。針對基于VSM的文本聚類存在的問題，Adam Schenker等人提出用圖結(jié)構(gòu)來進(jìn)行文本的表示，該模型利用圖結(jié)構(gòu)中的邊來體現(xiàn)文本中上下文之間的潛在關(guān)系[3]。在此基礎(chǔ)之上，本文提出了一種基于最大公共子圖的譜聚類算法（Spectral Clustering algorithm based on Maximum Common Subgraph）簡稱SC-MCS算法，同時設(shè)計了實驗，將SC-MCS算法與基于VSM的譜聚類算法進(jìn)行對比，并且對不同文本長度的聚類環(huán)境進(jìn)行了探究，結(jié)果表明SC-MCS算法相比與傳統(tǒng)基于向量空間的文本聚類算法在準(zhǔn)確率、召回率有一定提升。

1 譜聚類基本理論

1.1 圖劃分準(zhǔn)則

譜聚類算法最初源于圖劃分理論，通過將每個數(shù)據(jù)樣本映射為圖中的頂點V，樣本之間的相似度映射為頂點間的邊E的權(quán)重值W，這樣就得到了一個基于樣本相似度的無向加權(quán)圖G=（V，E，W）。進(jìn)而在圖G中，就可以將傳統(tǒng)的聚類問題轉(zhuǎn)化為在圖G上的圖劃分問題。同時定義圖劃分準(zhǔn)則，通過最優(yōu)化圖劃分準(zhǔn)則，使得同一類內(nèi)的點相似性較高，而不同類之間的點相似性較低。劃分準(zhǔn)則的優(yōu)劣將對聚類結(jié)果產(chǎn)生直接影響，主要的劃分準(zhǔn)則有最小切分準(zhǔn)則、規(guī)范化切分準(zhǔn)則以及多路規(guī)范化切分準(zhǔn)則等[4]。

在圖劃分理論中，定義將圖G劃分為A，B兩個子圖的代價函數(shù)：

1.2 相似矩陣及拉普拉斯矩陣

傳統(tǒng)方法求解圖劃分準(zhǔn)則的最優(yōu)解是一個NP難問題，進(jìn)而考慮問題的連續(xù)放松形式——求圖的拉普拉斯矩陣的譜分解問題，可以認(rèn)為譜聚類是對圖劃分準(zhǔn)則的一種逼近。

在譜聚類算法中，相似矩陣A的定義：

拉普拉斯（Laplacian）矩陣分為非規(guī)范拉普拉斯矩陣和規(guī)范拉普拉斯矩陣。非規(guī)范拉普拉斯矩陣表示為L =D -A， 規(guī)范拉普拉斯矩陣有兩種形式， 分別是

根據(jù)不同的劃分準(zhǔn)則及相似矩陣的構(gòu)造方法，譜聚類有不同的具體實現(xiàn)方法，其主要的過程：

構(gòu)建樣本集的相似矩陣A；

構(gòu)造拉普拉斯矩陣L；

計算L的特征值與特征向量，構(gòu)成特征向量空間；

對特征向量采用k-means或其他經(jīng)典聚類算法進(jìn)行聚類。

2 SC-MCS算法

傳統(tǒng)的文本譜聚類算法在構(gòu)造相似矩陣時，不能充分體現(xiàn)文本上下文之間的潛在關(guān)系，針對這一問題，本文提出了一種基于最大公共子圖的譜聚類（SC-MCS）算法。SC-MCS算法采用圖結(jié)構(gòu)來表示文本，通過計算文本圖結(jié)構(gòu)之間的最大公共子圖來體現(xiàn)文本之間的相似性，進(jìn)而構(gòu)造出基于最大公共子圖的相似矩陣。SC-MCS算法的具體過程如圖1所示。

圖2是單個文本圖結(jié)構(gòu)構(gòu)建的示意圖。

圖結(jié)構(gòu)中的節(jié)點反映了文本的特征項信息，邊體現(xiàn)了特征項的共現(xiàn)信息及語序信息，邊的權(quán)重反映了特征項之間語義關(guān)聯(lián)程度。

2.2 最大公共子圖求解

基于最大公共子圖的文本相似度計算的理論依據(jù)是：如果兩個圖結(jié)構(gòu)越相似，那么它們的公共部分就越多，即存在一個公共子圖，因此可以用它們的最大公共子圖來度量兩個圖結(jié)構(gòu)的相似程度。先給出最大公共子圖的相關(guān)定義[8]。

兩個圖結(jié)構(gòu)G1和G2的最大公共子圖，就是以G1和G2全部共有的節(jié)點作為自己的節(jié)點，全部共有的邊作為自己的邊，取共有邊上較小的權(quán)值作為自己邊的權(quán)值所構(gòu)成的圖，即圖結(jié)構(gòu)G1和G2的最大重疊部分。兩個圖結(jié)構(gòu)重疊的部分越多，則它們就越相似。因此可以用最大公共子圖mcs（G1，G2）對兩個圖結(jié)構(gòu)的相似度進(jìn)行度量。最大公共子圖生成的示意圖如圖3所示。

已知兩個圖結(jié)構(gòu)G1和G2，它們之間存在最大公共子圖g，則g的求解過程分以下兩個步驟進(jìn)行：

遍歷圖結(jié)構(gòu)G1和G2的節(jié)點，對節(jié)點進(jìn)行比較，取圖結(jié)構(gòu)G1和G2的公共節(jié)點作為g的節(jié)點；

取g的節(jié)點集合中任意兩個節(jié)點，如果這兩個節(jié)點在圖結(jié)構(gòu)G1和G2中都是鄰接的，則產(chǎn)生一體邊作為圖結(jié)構(gòu)g的邊。

2.3 文本相似度計算

利用文本的最大公共子圖來進(jìn)行文本的相似度計算，最大公共子圖充分包含了文本之間的相似信息，可以根據(jù)其在文本圖結(jié)構(gòu)中所占的比例大小來完成相似度估計，具體相似度計算公式：

公式前半部分是對圖結(jié)構(gòu)G1和G2中節(jié)點的相似度的度量，G1和G2最大公共子圖的節(jié)點數(shù)越多，且與G1，G2自身的節(jié)點數(shù)越接近，則G1，G2節(jié)點的相似度就越大，取值越接近于1；后半部分是對圖結(jié)構(gòu)G1，G2的邊及權(quán)重的度量，G1，G2相同邊的權(quán)重越接近，即min（wij，wi′j′）/max（wij，wi′j′）的值越接近于1。將所有相同邊的個數(shù)求和便得到最大公共子圖邊的個數(shù)，其與G1，G2邊的個數(shù)比值體現(xiàn)了G1，G2邊的相似度。二者的線性組合代表了用圖結(jié)構(gòu)表示的兩個文本間的相似程度。

2.4 文本聚類過程

文本聚類實驗可以進(jìn)一步地檢驗基于最大公共子圖的文本相似度的實際效果。文本聚類是將一個文檔集合分成若干聚類簇的過程，每個聚類簇的成員之間擁有較大的相似性，而不同聚類簇之間的成員則具有較低的相似性。對于給定的文本集合D={d1，d2，…，dn}，聚類算法將每對文本（di，dj）之間的文本相似度作為輸入，通過特定聚類算法進(jìn)行處理，最后將聚類結(jié)果輸出。

本文采用譜聚類算法進(jìn)行文本聚類處理，相比于其他傳統(tǒng)聚類方法，譜聚類具有明顯的優(yōu)勢，它能夠?qū)Ψ峭狗植嫉臉颖究臻g進(jìn)行聚類，在實際問題的處理中取得了較好的效果，而且執(zhí)行起來比較容易。算法實現(xiàn)過程：

輸入：文本相似矩陣和聚類數(shù)目k

輸出：文本聚類結(jié)果

Step1 構(gòu)造無向加權(quán)圖的鄰接矩陣A，計算得到拉普拉斯矩陣L；

Step2 計算矩陣L的前k個特征值和特征向量，構(gòu)造特征向量空間；

Step3 使用k-means算法對特征向量空間聚類；

Step4 根據(jù)特征向量聚類結(jié)果，返回文本集聚類結(jié)果。

3 實驗及結(jié)果分析

為了驗證SC-MCS算法的有效性及穩(wěn)定性，本文分別進(jìn)行了SC-MCS算法與傳統(tǒng)基于VSM譜聚類算法的橫向?qū)Ρ葘嶒炓约霸诓煌谋鹃L度環(huán)境下的縱向?qū)Ρ葘嶒灐?/p>

3.1 實驗數(shù)據(jù)集

本實驗選用的是搜狗實驗室提供的中文文本分類語料庫Sogou-C，該語料庫來源于Sohu新聞網(wǎng)保存的大量手工整理和分類的新聞?wù)Z料，數(shù)據(jù)一共分為10個類別，如表1所示。

文本字?jǐn)?shù)差別的大小會對最大公共子圖的計算產(chǎn)生較大影響，為了保證實驗的穩(wěn)定性，本課題選擇數(shù)據(jù)集當(dāng)中文本字?jǐn)?shù)差別較小的8個類別進(jìn)行實驗，即篩除了招聘類和文化類，每個類別隨機(jī)選擇200篇文本，總共1600篇文本進(jìn)行實驗。

3.2 評價指標(biāo)

由于本文是對已知類別的文本內(nèi)容進(jìn)行聚類，實驗采用準(zhǔn)確率（Precision）和召回率（Recall）兩個外部評價指標(biāo)對實驗結(jié)果進(jìn)行測評，其中準(zhǔn)確率考察聚類的精確度，而召回率考察聚類的完整性。

3.3 實驗結(jié)果

為了驗證文本提出基于最大公共子圖的譜聚類算法（SC-MCS）的有效性，本文與傳統(tǒng)的基于空間向量的譜聚類算法（VSM）進(jìn)行了對比實驗，表2是兩種聚類算法的實驗結(jié)果對比。

從表2可以看出，相對于傳統(tǒng)的VSM算法，SC-MCS算法在準(zhǔn)確率和召回率兩方面均有一定的提升，實驗結(jié)果驗證了本文所提出的SC-MCS算法的有效性，體現(xiàn)出了基于圖結(jié)構(gòu)的文本表示更好的效果。能夠出現(xiàn)這樣的結(jié)果，主要是因為SC-MCS聚類算法利用圖結(jié)構(gòu)考慮到了文本上下文之間的語義關(guān)系，而VSM聚類算法則是將不同特征詞作為相互獨立的向量來處理的，忽略了它們之間潛在的語義內(nèi)涵，所以SC-MCS聚類算法能夠在同樣的測試樣本下取得更好的實驗效果。

同時，為了驗證算法的穩(wěn)定性，本文采取了不同長度的文本進(jìn)行了縱向的對比實驗，來觀測隨著文本長度的改變算法的效果會發(fā)生如何變化，圖4是不同文本長度下算法平均準(zhǔn)確率和平均召回率的對比。

從上圖可以看出，隨著文本長度的增加，算法的平均準(zhǔn)確率和召回率起初有一定幅度的增長，而隨著文本長度的持續(xù)增加，算法的平均準(zhǔn)確率和召回率出現(xiàn)了大幅度的降低，造成這種結(jié)果的主要原因在于：當(dāng)文本長度過長時，文本之間的最大公共子圖很難準(zhǔn)確獲取，進(jìn)而導(dǎo)致無法體現(xiàn)文本之間的相似性。因此，我們可以針對不同聚類環(huán)境來選取合適文本長度，以確保基于最大公共子圖的文本聚類算法可以取得較好的效果。

4 結(jié)語

本文提出了一種基于最大公共子圖的文本聚類算法，利用文本的圖結(jié)構(gòu)表示來反映不同特征詞之間的語義內(nèi)涵，同時通過計算文本間的最大公共子圖來表示文本相似度，相比于傳統(tǒng)的基于空間向量的聚類算法取得了較好的聚類效果。

同時，本方法還存在待改進(jìn)的地方。文本的共現(xiàn)單元選取長度可以考慮進(jìn)行適當(dāng)?shù)脑黾?，但這也會為最大公共子圖的計算帶來一定困難。下一步工作可以考慮引入特征擴(kuò)展的方法來對算法進(jìn)行改進(jìn)。

參考文獻(xiàn)：

[1]VONLUXBURG U. A tutorial on spectral clustering[J]. Statistics and computing， 2007， 17（4）： 395-416.

[2]SALTON G， WONG A， YANG C S. A vector space model for automatic indexing[J]. Communications of the Acm， 1975， 18（11）：613-620.

[3]SCHENKER A， LAST M， BUNKE H， et al. Comparison of distance measures for graph-based clustering of documents[C]// Iapr International Conference on Graph Based Representations in Pattern Recognition. York， UK： Springer-Verlag， 2003：202-213.

[4]BUNKE H， FOGGIA P， GUIDOBALDI C， et al. A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs[C]// Joint Iapr International Workshop on Structural， Syntactic， and Statistical Pattern Recognition. Italy： Springer-Verlag， 2002：123-132.

[5]SHI J， MALIK J. Normalized Cuts and ImageSegmentation[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2000， 22（8）：888-905.

[6]蔡曉妍，戴冠中，楊黎斌. 譜聚類算法綜述[J]. 計算機(jī)科學(xué)， 2008， 35（7）：14-18.

[7]周昭濤，卜東波， 程學(xué)旗. 文本的圖表示初探[J]. 中文信息學(xué)報， 2005， 19（2）：36-43.

[8]劉巧鳳. 基于圖結(jié)構(gòu)的中文文本聚類方法研究[D]. 大連：大連理工大學(xué)， 2009.

（責(zé)任編輯：周曉南）