基于復雜網絡理論的中文文本聚類算法

李 培

（西安郵電大學,西安,710061）

0 引言

在信息時代的今天，信息的極大豐富也帶來了信息處理的極大困難，無論是信息的存儲、查詢或是檢索，或多或少都需要對信息進行前期的分類，在浩如煙海的眾多信息中，文本信息占據了絕大多數，同時，很多其他類型信息的重要內容都體現在其文本的部分，可將轉換為文本，因此，最終的問題歸咎於文本分類問題。而這些繁雜的信息往往沒有明確的分類標準和歸屬類別。傳統的按照已有的類別進行分門別類的分類技術已經被聚類技術所取代，聚類算法可以將文本信息根據其特點自動地劃分類別，分成合適數目的幾類，使其具有類中相似和類間相異的特點。

本文主要針對在中文文本聚類中普遍存在的對潛在語義考慮不足、文本特征表示不夠準確且對于海量數據處理效率低下這三個方面，提出了一種基于圖的中文文本聚類算法，采用基于小世界網絡模型提取關鍵字作為文本特征進行文本表示，并輔以基于《知網》的語義相似度算法來計算文本相似度。可以達到處理大規模海量數據、精簡的表示文本并考慮中文語義的目的，使得聚類性能更好。

1 基于小世界網絡模型提取關鍵字的文本表示方法

簡單文本聚類算法就是將數據聚類的算法應用到文本集合,研究這種類型的文本聚類算法主要考慮對文本進行數據表示、特征選擇和提取,將文本集合表示成特征矩陣的形式。為了將文本集合表示為特征矩陣,需要對文本進行建模。在建模時,需要考慮文本和在文本中出現的詞,可以把文本看成是詞的集合,也可以看成是詞的某種序列。最常見的模型是向量空間模型（VSM），即文本表示為T = (t1,t2,…,tn)，分量ti是各個詞條。根據常識可以知道，在中文的語句中，描述簡單的內容就需要相對較多的詞條。因此，直接由分詞結果構成的向量空間模型數據量往往存在過大的問題，對后期的處理和聚類帶來了很多問題，降低了實際應用的價值，增加了復雜度。

但是，我們也知道在日常生活中常常會用某篇文章的一些關鍵詞語來描述該文章的主題，大家都認可關鍵詞語能夠反映出其所對應的文章的主要內容。由于一篇文章的關鍵詞語與其分詞得到的大量詞條相比是非常少的，所以采用關鍵詞語來作為文本特征表示文本可以作為一個大大降低算法復雜度和難度，同時又不影響算法準確性的最佳選擇。

這里。我們對傳統的文本表示方法進行改進，用文本的關鍵詞語集合來表示文本。同時，利用復雜網絡理論中的小世界網絡模型來獲取關鍵詞語。

小世界網絡理論是復雜網絡中的一個經典理論，它集中體現了在我們日常生活中隨處可見的小世界現象，即聚合效應，在很多構成網狀結構的問題中都有應用。我們在對文本進行研究的同時也發現了文本中的各個詞條之間通過其語義連接形成的結構圖恰恰是網狀結構，而且文本中的關鍵詞語還存在明顯的小世界現象。

具體算法如下：

Step1：對中文文本進行中文分詞，這些分詞詞條就構成了小世界網絡圖的各個結點。

研究和改革無機化學課程教學不但可以從源頭提高化學教師的素養，而且為解決新課程實施中的問題提供根本保障．“實踐+反思=教師成長”已經成為共識．一些發達國家紛紛建立實習實訓基地，目的是讓學生在實地觀察、體驗教學及與指導教師的交流中獲得實踐性知識，在不斷實踐反思的過程中形成技能．這為無機化學課程改革提供理論支持和可操作的教學策略．

Step2：構圖：即連接各個結點。結點之間是否有連接的判斷是基于連接范圍因子。符合要求的結點之間通過連接就形成了邊。從而由單個的詞條變成了詞條網絡G1。

Step3：對于上一步產生的詞條網絡得到其最大連通圖G2，從而構成文本的語義結構關系圖，并驗證其小世界特性。

Step4：計算語義結構關系圖G2中每個結點的平均路徑變化量和平均簇系數變化量集合△L和 △C。

Step5：根據集合△L和 △C，將集合中排名靠前的p%個元素取出形成候選關鍵詞。

Step6：合并候選關鍵詞形成最終的關鍵詞集合。

按照上述的算法處理文本，以一篇與體育有關的新聞報道為例，經過六步的處理，最終得到關鍵詞集合為：{中國、甲A聯賽、足球、比賽}，我們可以將該報道的文本T1表示為KeyWord(T1)={中國、甲A聯賽、足球、比賽}，與新聞報導原文的內容比照，關鍵詞組成的向量集合可以比較準確的表示文本內容。

2 基于《知網》語義相似度計算的文本相似度計算

在前面的分析中，我們認可了使用向量空間模型來表示文本的方法，但是不管是由分詞直接構成向量集合，還是采用上一節中提到的文本關鍵詞來構成向量集合，再后續的文本相似度計算中，都會把向量空間集合中的各個分量作為獨立的分子來進行處理，也就是各個詞語之間沒有任何的聯系。但眾所周知，中文語義豐富多彩，很多詞語可以表達相近或是相似的含義，而一個意思也可以有各種說法，也就是說構成向量空間的各個分量之間不是完全獨立沒有聯系的，各個詞語分量之間有可能存在近似的關系，同時，在計算文本相似度時，不同文本之間不同的分量也可能存在相似的情況，如果將這些相似的分量在計算時都作為不同的獨立特征項對待，勢必導致明明相似度很高的兩個文本計算之后得到低相似度的結果，而使得相似度精度大大降低，從而影響后續的文本聚類結果。

鑒于以上原因，我們的文本相似度計算時就必須要考慮詞語之間的語義相似度。我們參考文獻提出的基于《知網》的詞匯語義相似度計算算法，并采用了該算法所提供的DLL進行詞語語義計算，從而降低相似詞語對文本相似度的影響。

具體的文本相似度計算方法，在參考傳統的度量兩個距離的歐氏距離、余弦函數等的計算公式，提出了基于《知網》語義相似度計算的文本相似度計算算法。

具體算法如下：

Step1:文本T1表示為KeyWord(T1)＝{wi|wi表示T1`的第i個關鍵字 }；文本T2表示為KeyWord(T2)＝{wi|wi表示T2`的第i個關鍵字 }；

Step2 查找Keyword(T1)和KeyWord(T2)集合中詞語相似度大于閾值的詞語數量N。

Step3 計算N占關鍵詞語的比率作為文本相似度的度量標準。

該算法就是通過發現兩篇文本中關鍵詞語的語義相似性，默認，如果兩篇文本中的大部分關鍵詞語相似或是相同，則兩篇文本就是相似的。

3 算法驗證及分析評價

我們采用文本集合{474.txt，476.txt，477.txt，7117.txt，7118.txt，8219.txt，8221.txt}來驗證這種基于復雜網絡理論的中文文本聚類算法。其中Q表示圖的Q值表示圖經過簇合并后的新的Q值。，在這個文本集合中，文本的命名代表了其不同的分類，其中凡是數字4開頭的文本內容屬于交通類，數字7開頭的文件屬于醫藥類，數字8開頭的文件屬于體育類。上述文本均取自課題組使用網絡爬蟲程序得到的新聞網頁。

首先，對以上7篇文本進行分詞，按照小世界網絡模型提取關鍵字來表示各個文本。

其次，采用《知網》提供的計算接口程序，計算各個文本之間的文本相似度。

最后，將文本相似度達于閾值的文本之間建立連線。構成文本聚類的初始狀態圖。

具體參數設置：文本相似度閾值為0.18，詞語相似度閾值為0.92。

構圖過程是：按照文本的順序將其序號作為其編號，結點0和結點1的相似度為0.667，則在0、1結點之間加邊；結點0和結點2的相似度為0.333，則在0、2結點之間加邊；結點1和結點2的相似度為0.333，則在1、2結點之間加邊；結點3和結點4的相似度為0.333，則在3、4結點之間加邊；結點5和結點6的相似度為0.2，則在5、6結點之間加邊。其余結點之間相似度低于閾值，則不存在邊。

基于圖的聚類算法的處理過程如下：以“{結點，結點，…}”形式表示簇。初始化各個簇為 {0}、{1}、{2}、{3}、{4}、{5}、{6}；通過計算各種合并組合的 Q值，得出簇1、簇2合并之后會使得Q值的增量最大，故選擇合并簇1和2，而簇結構變為：{0}、{1，2}、{3}、{4}、{5}、{6}；接下來，按照同樣的標準，合并0和1，簇結構變為：{0，1，2}、{3}、{4}、{5}、{6}；繼續按照同樣的標準，合并簇3和4，簇結構變為：{0，1，2}、{3}、{4}、{5，6}；繼續按照同樣的標準，合并簇1和2，簇結構變為：{0，1，2}、{3，4}、{5，6}，最終＝0，聚類過程結束。

圖1 基于復雜網絡的文本聚類算法圖解

根據上述圖解的聚類過程，可以清晰地看到，最終，文檔編號第一位相同的文本被歸為一類，即，聚類結果與我們已知的文本分類情況完全相符。

通過分析算法執行的步驟可以分析該算法的復雜度：根據貪婪算法的原理，每次合并應該沿著使Q增大最多或者減少最小的方向進行，也就是進行合并運算的算法復雜度為。每次合并以后，對相應的元素更新，并將與簇相關的行和列相加，相關運算的算法復雜度為。因此，該算法總的算法復雜度為對于稀疏網絡則為。通過理論分析可以看到該算法的復雜度是具有可行性的。

4 結論

本文主要針對在中文文本聚類的算法進行了研究，基于目前對該問題的研究現狀，針對已有算法存在的不足尋找解決方案。其中將中文文本的語義特征通過基于《知網》的語義相似度算法引入到文本聚類中，充分體現了中文文本聚類算法有別于其他語言的不同之處。并利用先進的復雜網絡的相關理論中與圖相關的算法解決大規模海量數據聚類的效率問題。在理論研究的基礎上，又通過實際的中文文本集合數據進行實際應用的測試，驗證了其算法的有效性，特別是可行性。基于以上的研究，說明該基于復雜網絡理論的中文文本聚類算法是可以應用于各類實際應用中。當然，該算法在細節上還有很多可改進的空間，我們會在今后繼續深入研究，將該算法進一步完善優化。

[1]周雅夫，馬力，董洛兵.基于SMW理論提取復合關鍵字系統的設計與實現.西安郵電學院學報，2007(5)：82～85.

[2]Watts,D.J.and S.H.Strogatz,Collective dynamics of'small-world' networks.Nature.1998 Jun 4,1998.VOL 393: p.440-442.

[3]劉群,李素建.基于《知網》的詞匯語義相似度計算.第三屆漢語詞匯語義學研討會.臺北: 2002.