李 培

（西安郵電大學(xué),西安,710061）

0 引言

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

本文主要針對(duì)在中文文本聚類中普遍存在的對(duì)潛在語(yǔ)義考慮不足、文本特征表示不夠準(zhǔn)確且對(duì)于海量數(shù)據(jù)處理效率低下這三個(gè)方面，提出了一種基于圖的中文文本聚類算法，采用基于小世界網(wǎng)絡(luò)模型提取關(guān)鍵字作為文本特征進(jìn)行文本表示，并輔以基于《知網(wǎng)》的語(yǔ)義相似度算法來(lái)計(jì)算文本相似度。可以達(dá)到處理大規(guī)模海量數(shù)據(jù)、精簡(jiǎn)的表示文本并考慮中文語(yǔ)義的目的，使得聚類性能更好。

1 基于小世界網(wǎng)絡(luò)模型提取關(guān)鍵字的文本表示方法

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

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

這里。我們對(duì)傳統(tǒng)的文本表示方法進(jìn)行改進(jìn)，用文本的關(guān)鍵詞語(yǔ)集合來(lái)表示文本。同時(shí)，利用復(fù)雜網(wǎng)絡(luò)理論中的小世界網(wǎng)絡(luò)模型來(lái)獲取關(guān)鍵詞語(yǔ)。

小世界網(wǎng)絡(luò)理論是復(fù)雜網(wǎng)絡(luò)中的一個(gè)經(jīng)典理論，它集中體現(xiàn)了在我們?nèi)粘Ｉ钪须S處可見的小世界現(xiàn)象，即聚合效應(yīng)，在很多構(gòu)成網(wǎng)狀結(jié)構(gòu)的問題中都有應(yīng)用。我們?cè)趯?duì)文本進(jìn)行研究的同時(shí)也發(fā)現(xiàn)了文本中的各個(gè)詞條之間通過其語(yǔ)義連接形成的結(jié)構(gòu)圖恰恰是網(wǎng)狀結(jié)構(gòu)，而且文本中的關(guān)鍵詞語(yǔ)還存在明顯的小世界現(xiàn)象。

具體算法如下：

Step1：對(duì)中文文本進(jìn)行中文分詞，這些分詞詞條就構(gòu)成了小世界網(wǎng)絡(luò)圖的各個(gè)結(jié)點(diǎn)。

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

Step2：構(gòu)圖：即連接各個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)之間是否有連接的判斷是基于連接范圍因子。符合要求的結(jié)點(diǎn)之間通過連接就形成了邊。從而由單個(gè)的詞條變成了詞條網(wǎng)絡(luò)G1。

Step3：對(duì)于上一步產(chǎn)生的詞條網(wǎng)絡(luò)得到其最大連通圖G2，從而構(gòu)成文本的語(yǔ)義結(jié)構(gòu)關(guān)系圖，并驗(yàn)證其小世界特性。

Step4：計(jì)算語(yǔ)義結(jié)構(gòu)關(guān)系圖G2中每個(gè)結(jié)點(diǎn)的平均路徑變化量和平均簇系數(shù)變化量集合△L和 △C。

Step5：根據(jù)集合△L和 △C，將集合中排名靠前的p%個(gè)元素取出形成候選關(guān)鍵詞。

Step6：合并候選關(guān)鍵詞形成最終的關(guān)鍵詞集合。

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

2 基于《知網(wǎng)》語(yǔ)義相似度計(jì)算的文本相似度計(jì)算

在前面的分析中，我們認(rèn)可了使用向量空間模型來(lái)表示文本的方法，但是不管是由分詞直接構(gòu)成向量集合，還是采用上一節(jié)中提到的文本關(guān)鍵詞來(lái)構(gòu)成向量集合，再后續(xù)的文本相似度計(jì)算中，都會(huì)把向量空間集合中的各個(gè)分量作為獨(dú)立的分子來(lái)進(jìn)行處理，也就是各個(gè)詞語(yǔ)之間沒有任何的聯(lián)系。但眾所周知，中文語(yǔ)義豐富多彩，很多詞語(yǔ)可以表達(dá)相近或是相似的含義，而一個(gè)意思也可以有各種說(shuō)法，也就是說(shuō)構(gòu)成向量空間的各個(gè)分量之間不是完全獨(dú)立沒有聯(lián)系的，各個(gè)詞語(yǔ)分量之間有可能存在近似的關(guān)系，同時(shí)，在計(jì)算文本相似度時(shí)，不同文本之間不同的分量也可能存在相似的情況，如果將這些相似的分量在計(jì)算時(shí)都作為不同的獨(dú)立特征項(xiàng)對(duì)待，勢(shì)必導(dǎo)致明明相似度很高的兩個(gè)文本計(jì)算之后得到低相似度的結(jié)果，而使得相似度精度大大降低，從而影響后續(xù)的文本聚類結(jié)果。

鑒于以上原因，我們的文本相似度計(jì)算時(shí)就必須要考慮詞語(yǔ)之間的語(yǔ)義相似度。我們參考文獻(xiàn)提出的基于《知網(wǎng)》的詞匯語(yǔ)義相似度計(jì)算算法，并采用了該算法所提供的DLL進(jìn)行詞語(yǔ)語(yǔ)義計(jì)算，從而降低相似詞語(yǔ)對(duì)文本相似度的影響。

具體的文本相似度計(jì)算方法，在參考傳統(tǒng)的度量?jī)蓚€(gè)距離的歐氏距離、余弦函數(shù)等的計(jì)算公式，提出了基于《知網(wǎng)》語(yǔ)義相似度計(jì)算的文本相似度計(jì)算算法。

具體算法如下：

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

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

Step3 計(jì)算N占關(guān)鍵詞語(yǔ)的比率作為文本相似度的度量標(biāo)準(zhǔn)。

該算法就是通過發(fā)現(xiàn)兩篇文本中關(guān)鍵詞語(yǔ)的語(yǔ)義相似性，默認(rèn)，如果兩篇文本中的大部分關(guān)鍵詞語(yǔ)相似或是相同，則兩篇文本就是相似的。

3 算法驗(yàn)證及分析評(píng)價(jià)

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

首先，對(duì)以上7篇文本進(jìn)行分詞，按照小世界網(wǎng)絡(luò)模型提取關(guān)鍵字來(lái)表示各個(gè)文本。

其次，采用《知網(wǎng)》提供的計(jì)算接口程序，計(jì)算各個(gè)文本之間的文本相似度。

最后，將文本相似度達(dá)于閾值的文本之間建立連線。構(gòu)成文本聚類的初始狀態(tài)圖。

具體參數(shù)設(shè)置：文本相似度閾值為0.18，詞語(yǔ)相似度閾值為0.92。

構(gòu)圖過程是：按照文本的順序?qū)⑵湫蛱?hào)作為其編號(hào)，結(jié)點(diǎn)0和結(jié)點(diǎn)1的相似度為0.667，則在0、1結(jié)點(diǎn)之間加邊；結(jié)點(diǎn)0和結(jié)點(diǎn)2的相似度為0.333，則在0、2結(jié)點(diǎn)之間加邊；結(jié)點(diǎn)1和結(jié)點(diǎn)2的相似度為0.333，則在1、2結(jié)點(diǎn)之間加邊；結(jié)點(diǎn)3和結(jié)點(diǎn)4的相似度為0.333，則在3、4結(jié)點(diǎn)之間加邊；結(jié)點(diǎn)5和結(jié)點(diǎn)6的相似度為0.2，則在5、6結(jié)點(diǎn)之間加邊。其余結(jié)點(diǎn)之間相似度低于閾值，則不存在邊。

基于圖的聚類算法的處理過程如下：以“{結(jié)點(diǎn)，結(jié)點(diǎn)，…}”形式表示簇。初始化各個(gè)簇為 {0}、{1}、{2}、{3}、{4}、{5}、{6}；通過計(jì)算各種合并組合的 Q值，得出簇1、簇2合并之后會(huì)使得Q值的增量最大，故選擇合并簇1和2，而簇結(jié)構(gòu)變?yōu)椋簕0}、{1，2}、{3}、{4}、{5}、{6}；接下來(lái)，按照同樣的標(biāo)準(zhǔn)，合并0和1，簇結(jié)構(gòu)變?yōu)椋簕0，1，2}、{3}、{4}、{5}、{6}；繼續(xù)按照同樣的標(biāo)準(zhǔn)，合并簇3和4，簇結(jié)構(gòu)變?yōu)椋簕0，1，2}、{3}、{4}、{5，6}；繼續(xù)按照同樣的標(biāo)準(zhǔn)，合并簇1和2，簇結(jié)構(gòu)變?yōu)椋簕0，1，2}、{3，4}、{5，6}，最終＝0，聚類過程結(jié)束。

圖1 基于復(fù)雜網(wǎng)絡(luò)的文本聚類算法圖解

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

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

4 結(jié)論

本文主要針對(duì)在中文文本聚類的算法進(jìn)行了研究，基于目前對(duì)該問題的研究現(xiàn)狀，針對(duì)已有算法存在的不足尋找解決方案。其中將中文文本的語(yǔ)義特征通過基于《知網(wǎng)》的語(yǔ)義相似度算法引入到文本聚類中，充分體現(xiàn)了中文文本聚類算法有別于其他語(yǔ)言的不同之處。并利用先進(jìn)的復(fù)雜網(wǎng)絡(luò)的相關(guān)理論中與圖相關(guān)的算法解決大規(guī)模海量數(shù)據(jù)聚類的效率問題。在理論研究的基礎(chǔ)上，又通過實(shí)際的中文文本集合數(shù)據(jù)進(jìn)行實(shí)際應(yīng)用的測(cè)試，驗(yàn)證了其算法的有效性，特別是可行性?；谝陨系难芯浚f(shuō)明該基于復(fù)雜網(wǎng)絡(luò)理論的中文文本聚類算法是可以應(yīng)用于各類實(shí)際應(yīng)用中。當(dāng)然，該算法在細(xì)節(jié)上還有很多可改進(jìn)的空間，我們會(huì)在今后繼續(xù)深入研究，將該算法進(jìn)一步完善優(yōu)化。

[1]周雅夫，馬力，董洛兵.基于SMW理論提取復(fù)合關(guān)鍵字系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).西安郵電學(xué)院學(xué)報(bào)，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]劉群,李素建.基于《知網(wǎng)》的詞匯語(yǔ)義相似度計(jì)算.第三屆漢語(yǔ)詞匯語(yǔ)義學(xué)研討會(huì).臺(tái)北: 2002.