一種改進(jìn)的基于潛在語義索引的文本聚類算法

侯澤民，巨 筱

(鄭州科技學(xué)院信息工程學(xué)院，河南 鄭州 450064)

0 引言

自20世紀(jì)90年代以來，計算機(jī)網(wǎng)絡(luò)技術(shù)的高速發(fā)展，導(dǎo)致信息量迅速增加。人們可以輕易地從Internet、新聞媒體、數(shù)字圖書館等數(shù)字載體上面獲得數(shù)目龐大的文本文檔。人們可以輕易收集數(shù)量龐大的信息，卻無法進(jìn)行精確定位，找到自己真正所需的信息，出現(xiàn)了“數(shù)據(jù)爆炸但知識貧乏”的怪現(xiàn)象。因此，人們迫切需要一種手段能夠高效、快速地獲取自己真正所需信息。文本聚類是文本挖掘的研究內(nèi)容之一，通過文本聚類，可以從海量數(shù)據(jù)當(dāng)中挖掘和提取有用信息，提高信息檢索的速度和效率。王禮禮[1]曾提出一種基于潛在語義索引的文本聚類算法，其算法在文本聚類階段使用的是k-means算法。本文提出的基于潛在語義索引的文本聚類算法，在文本聚類階段使用的是SOM算法，只是在聚類之初，引用了改進(jìn)的k-means算法的初值，二者有本質(zhì)區(qū)別。SOM算法和k-means算法是目前文本聚類研究中比較常用的2種算法。羅克剛[2]曾對這2種算法從性能上做了一個比較，表明SOM算法的聚類效果要優(yōu)于k-means算法的聚類效果。實驗結(jié)果驗證了本文算法的優(yōu)越性。

1 相關(guān)技術(shù)

1.1潛在語義索引

在傳統(tǒng)的文本聚類研究中，文本的表示主要采用向量空間模型[3](Vector Space Model，VSM)。使用計算公式將文本之間相似度表示出來。文本之間相似度量方式為余弦距離。但由于VSM只是詞語表面上的匹配，對多義詞和同義詞非常敏感。例如“電腦”和“計算機(jī)”這2個詞在很多情況下是同一個意思，但在向量模型中卻不能匹配?；诖?，本文給出的改進(jìn)算法中，引入了潛在語義索引理論。

潛在語義索引[4-5](Latent Semantic Index，LSI)或潛在語義分析(Latent Semantic Analysis，LSA)，是1988年S.T.Dumais等人提出的一種新的信息檢索代數(shù)模型，它運(yùn)用統(tǒng)計計算方法對文檔集中的大量文本進(jìn)行分析，從而挖掘出文本中詞與詞之間隱藏的語義結(jié)構(gòu)關(guān)系，并用這種潛在的語義結(jié)構(gòu)關(guān)系，表示詞與文本之間的關(guān)系，從而消除詞語之間的相關(guān)性，降低文本空間維數(shù)，節(jié)省文本聚類的時間，并取得更好的聚類效果。

奇異值分解[6](Singular Value Decomposition，SVD)是潛在語義索引LSI的一個重要應(yīng)用算法，是線性代數(shù)中一種重要的矩陣分解，可以用它進(jìn)行多維矩陣的空間降維。

定理1 設(shè)A為m×n的矩陣，則存在m階矩陣U和n階矩陣V，使得:

其中，S=diag(σ1，σ2，…，σr)，σi＞0。

矩陣A是初始的特征矩陣，在文本挖掘中，A就是t(term)行d(document)列的矩陣，每列是一篇文章，每行是一個單詞，每個單元格的值為當(dāng)前單詞在當(dāng)前文章里的出現(xiàn)次數(shù)。U是一個t行r列的矩陣，V是一個r行d列的矩陣，S是一個r行r列的對角矩陣。這里r的大小是A的秩。那么U和V中分別是A的奇異向量，而S是A的奇異值。AAT的正交單位特征向量組成U，特征值組成STS，ATA的正交單位特征向量組成V，特征值組成SST。

本文給出的改進(jìn)算法中，在聚類預(yù)處理階段，應(yīng)用潛在語義索引理論和奇異值分解算法來表示文本特征向量，以體現(xiàn)特征詞的語義關(guān)系并實現(xiàn)特征向量的降維。

1.2 自組織映射網(wǎng)絡(luò)

芬蘭赫爾辛基大學(xué)教授Teuvo Kohonen于1982年提出了自組織映射(Self-Organizing Maps，SOM)網(wǎng)絡(luò)[7-8]。SOM網(wǎng)絡(luò)是一種無指導(dǎo)學(xué)習(xí)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)，自組織過程其實就是無指導(dǎo)學(xué)習(xí)過程。自組織映射網(wǎng)絡(luò)SOM由輸入層和輸出層(競爭層)組成。輸入層通過權(quán)值向量將文本信息匯集到輸出層各個神經(jīng)元，輸入層的神經(jīng)元個數(shù)與樣本維數(shù)相同。輸出層即競爭層，其神經(jīng)元節(jié)點(diǎn)數(shù)可按多種方式進(jìn)行排列，例如有一維線陣、二維平面陣、三維柵格陣等。

SOM網(wǎng)絡(luò)的工作原理為:競爭、合作、自適應(yīng)[9]。

1)競爭。

競爭過程就是選擇獲勝神經(jīng)元過程。設(shè)m為輸入層向量空間維數(shù)，輸入層空間向量模式記為:

SOM網(wǎng)絡(luò)中輸出層神經(jīng)元向量空間與輸入層向量空間維數(shù)相同。所以將輸出層神經(jīng)元節(jié)點(diǎn)j向量記為:

其中k為SOM網(wǎng)絡(luò)輸出層神經(jīng)元節(jié)點(diǎn)總數(shù)。計算輸入向量X與輸出層神經(jīng)元節(jié)點(diǎn)之間的距離，距離最小的輸出層神經(jīng)元即為獲勝神經(jīng)元。

2)合作。

合作過程就是根據(jù)競爭過程獲得的獲勝神經(jīng)元，計算獲勝神經(jīng)元節(jié)點(diǎn)的拓?fù)溧徲颉?/p>

設(shè)hj，i為獲勝神經(jīng)元節(jié)點(diǎn)i為中心的拓?fù)溧徲?，dj，i為獲勝神經(jīng)元節(jié)點(diǎn)i與興奮神經(jīng)元節(jié)點(diǎn)j之間的側(cè)向距離。則 hj，i和 dj，i之 間的關(guān)系為:

其中σ為鄰域半徑，σ是動態(tài)變化的，其變化規(guī)律如公式(3)所示:

其中，σ0為鄰域半徑初始值，τ1為常數(shù)，表示時間。將σ(n)代入公式(2)可得:

公式(4)中的hj，i(x)(n)稱為鄰域函數(shù)。根據(jù)鄰域函數(shù)hj，i(x)(n)可以計算確定獲勝神經(jīng)元節(jié)點(diǎn)的拓?fù)溧徲颉?/p>

3)自適應(yīng)。

自適應(yīng)過程使興奮神經(jīng)元通過對自身突觸權(quán)值的適當(dāng)改變，以增加它們關(guān)于該輸入模式的判別函數(shù)值。所作的改變使獲勝神經(jīng)元節(jié)點(diǎn)對以后相似輸入模式的響應(yīng)增強(qiáng)了。隨著對樣本數(shù)據(jù)的反復(fù)訓(xùn)練，鄰域更新會使得突觸權(quán)值趨于服從輸入向量的分布。

2 改進(jìn)的基于潛在語義索引的文本聚類算法

2.1 傳統(tǒng)SOM算法的局限性

SOM算法是常用的、經(jīng)典的無導(dǎo)師學(xué)習(xí)算法，可以將高維向量空間模型轉(zhuǎn)化為二維向量空間表示;抗噪聲能力強(qiáng);能進(jìn)行并行化處理;可視化效果好。但是SOM算法也存在一些局限性:

1)SOM算法需要提前確定聚類類別數(shù)目[10]，即輸出層神經(jīng)元節(jié)點(diǎn)的數(shù)目和結(jié)構(gòu)層次。

2)SOM網(wǎng)絡(luò)進(jìn)行訓(xùn)練時，一些輸出層神經(jīng)元節(jié)點(diǎn)的連接權(quán)值與輸入層模式相差較大，始終不能獲勝，成為“死神經(jīng)元[11-12]”。

3)SOM算法缺乏具體的目標(biāo)函數(shù)[13-14]。

2.2 SOM算法的改進(jìn)策略

從2.1節(jié)內(nèi)容可以看出，傳統(tǒng)SOM算法依然存在著一些局限性。2.1節(jié)中提到的局限性1)，在實際聚類過程中，大多數(shù)研究者們也只是根據(jù)自己豐富的經(jīng)驗和專業(yè)的知識來確定聚類類別數(shù)目，而且是多次嘗試，直至得到正確的結(jié)果。這種方法有很大的盲目性和不確定性，若得出錯誤的聚類類別數(shù)目，最終的聚類效果也會很差?；诖耍疚尼槍?.1節(jié)內(nèi)容的局限性1)，給出相應(yīng)的解決方案:即改進(jìn)傳統(tǒng)的kmeans聚類算法得出聚類初始值，作為聚類類別數(shù)目。將此準(zhǔn)確聚類類別數(shù)目作為SOM網(wǎng)絡(luò)模型輸出層神經(jīng)元節(jié)點(diǎn)數(shù)目。

2.3 獲取SOM算法聚類類別數(shù)目的值

劉遠(yuǎn)超等[15]改進(jìn)了傳統(tǒng) k-means算法，提出了一種基于最小最大原則的k-means聚類初始值選擇算法，該算法能夠確定k-means聚類的初始聚點(diǎn)及聚類類別數(shù)目。本文借鑒該改進(jìn)算法，對傳統(tǒng)k-means算法進(jìn)行改進(jìn)，得到聚類類別數(shù)目，然后應(yīng)用于SOM算法，作為SOM網(wǎng)絡(luò)模型輸出層神經(jīng)元節(jié)點(diǎn)數(shù)目。下面介紹k-means算法的改進(jìn)策略及算法過程。

假設(shè)要將原始文檔集聚類成k個模式類，那么首先要選取2個距離最遠(yuǎn)即余弦相似度最小的聚點(diǎn)x1，x2，而剩余聚點(diǎn)的確定則可通過迭代公式推出。設(shè)已經(jīng)選取確定了m個聚點(diǎn)，則第m+1個聚點(diǎn)可通過公式(5)推出:

在公式(5)中，min、max表示聚點(diǎn)之間的最小最大距離，即用 min{d(xm+1，xr)，r=1，2，…，m}表示2個聚點(diǎn)的最小距離，記為mindist。通過文本聚類規(guī)則知道，類內(nèi)文本之間距離小即相似度大，而類間文本之間距離大即相似度小。公式(5)是一個遞推迭代公式，可用來選取下一個聚點(diǎn)。采用深度[16](depth)曲線來描述聚點(diǎn)與最小距離之間的變化。聚點(diǎn)的深度值為該聚點(diǎn)與左鄰點(diǎn)的最小距離的差的絕對值和該聚點(diǎn)與右鄰點(diǎn)的最小距離的差的絕對值的和，如公式(6)所示。

利用公式(6)，可以得出聚點(diǎn)與深度之間的變化曲線，如圖1所示。

圖1 聚點(diǎn)-深度變化曲線

從圖1聚點(diǎn)與深度之間的變化曲線可以很容易看出，有一臨界點(diǎn)深度值最大，臨界點(diǎn)所對應(yīng)的聚點(diǎn)即為真實聚類類別數(shù)目的值。

2.4 改進(jìn)的基于潛在語義索引的文本聚類算法

本文針對傳統(tǒng)SOM算法的局限性提出了2個改進(jìn)策略，引入潛在語義索引LSI解決文本中同義詞、多義詞的敏感問題，使用改進(jìn)的k-means初始值選擇算法確定聚類類別數(shù)目，作為SOM模型輸出層神經(jīng)元節(jié)點(diǎn)數(shù)目。下面，將具體描述改進(jìn)的基于潛在語義索引的文本聚類算法。

在文本預(yù)處理階段，通過詞根還原、分詞、詞性標(biāo)注、聽用詞過濾、名實體識別、關(guān)鍵詞抽取得到詞-文檔矩陣。然后使用潛在語義索引中的奇異值分解SVD對詞-文檔矩陣進(jìn)行分解及降維。

在文本聚類階段，對傳統(tǒng)的SOM算法進(jìn)行改進(jìn)，算法流程如下:

1)根據(jù)2.3節(jié)給出的改進(jìn)k-means初值選擇算法可以得出聚類類別數(shù)目值，將此值作為SOM網(wǎng)絡(luò)模型輸出層神經(jīng)元節(jié)點(diǎn)數(shù)目值，構(gòu)建一個二維平面陣列結(jié)構(gòu)的SOM網(wǎng)絡(luò)模型。

2)初始化，時間步長為 n=0，1，2，…，輸出節(jié)點(diǎn)權(quán)值向量初始值為Wj(0);向量各元素從區(qū)間(0，1)上隨機(jī)取值;學(xué)習(xí)率初始值盡量取大些，最好接近1;鄰域半徑初始值也要取大些，盡可能多地包含臨近神經(jīng)元。

3)對于訓(xùn)練樣本集中各個輸入向量X，求競爭獲勝神經(jīng)元節(jié)點(diǎn)i(x):

其中k為SOM網(wǎng)絡(luò)輸出層神經(jīng)元節(jié)點(diǎn)總數(shù)。

4)更新獲勝神經(jīng)元節(jié)點(diǎn)及鄰域內(nèi)節(jié)點(diǎn)的權(quán)值向量:

5)更新學(xué)習(xí)率η(n):

其中η0為初始值，τ2為時間常數(shù)。

6)使用公式(4)更新鄰域函數(shù)值。

7)當(dāng)特征映射不再發(fā)生明顯變化或達(dá)到最大網(wǎng)絡(luò)訓(xùn)練次數(shù)時退出;否則令n=n+1，轉(zhuǎn)入步驟3)。

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

3.1 聚類效果評價方法

本文采用F-measure方法[17]來評價聚類算法的效果。F-measure方法中precision為查準(zhǔn)率，表示聚類的準(zhǔn)確度，recall為查全率，表示聚類類別文本的覆蓋程度。而F-measure方法是它們的調(diào)和平均數(shù)。

其中:

在求出某個類別的F(r，s)值之后，取各個F值中的最大值，記為Fmax，然后求出所有類別的平均F值，此F值即可表示最終的聚類效果。

其中，T表示測試數(shù)據(jù)集中所有聚類類別的集合，|t|為測試數(shù)據(jù)集類別t中的文本數(shù)量。F值越大說明聚類效果越好。

3.2 測試數(shù)據(jù)集

下面選擇6個主題的新聞，每個新聞報道含50篇文本，共300篇文本，然后將這些新聞報道處理成純文本格式。這6個主題共300篇文本即為本文的測試數(shù)據(jù)集。測試數(shù)據(jù)集的6個主題分別為:馬航失聯(lián)事件、烏克蘭沖突事件、霧霾天氣、釣魚島事件、食品安全、騰訊入股京東。詳細(xì)情況如表1所示。

表1 測試數(shù)據(jù)集數(shù)據(jù)

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

下面利用測試數(shù)據(jù)集，來驗證本文算法的優(yōu)越性。

本文的測試數(shù)據(jù)集為D1至D6共6個類別300個文本。應(yīng)用公式(10)來計算F-measure方法中的F值，比較傳統(tǒng)k-means算法、SOM算法以及本文改進(jìn)算法的F值和聚類時間，如表2所示。

表2 不同算法的F值及聚類時間比較

實驗結(jié)果表明，本文算法得到的F值比傳統(tǒng)kmeans算法和SOM算法得到的F值要高。根據(jù)F-measure評價方法，可以說明本文算法的聚類效果明顯好于傳統(tǒng)k-means算法和SOM算法，而且本文算法的聚類時間也更少。

4 結(jié)束語

本文首先引入潛在語義索引，消除詞語之間的相關(guān)性，降低文本空間維數(shù)，節(jié)省文本聚類的時間，然后，改進(jìn)k-means文本聚類算法，計算出聚類類別數(shù)目，作為SOM算法的聚類類別數(shù)目。根據(jù)以上策略，本文給出了一種改進(jìn)的基于潛在語義索引的文本聚類算法。實驗結(jié)果表明，本算法的聚類效果更好，聚類時間更少。

[1] 王禮禮.基于潛在語義索引的文本聚類算法研究[D].成都:西南交通大學(xué)，2008.

[2] 羅克剛.基于自組織映射的文本聚類研究[D].哈爾濱:哈爾濱工業(yè)大學(xué)，2007.

[3] 郭武斌，周寬久，張世榮.基于潛在語義索引的SVM文本分類模型[J].情報學(xué)報，2009，28(6):827-833.

[4] 廖一星.一種新的監(jiān)督潛在語義模型[J].計算機(jī)工程與應(yīng)用，2009，45(33):117-119.

[5] 常利偉.基于多系統(tǒng)融合的潛在語義分析技術(shù)研究[D].沈陽:沈陽航空航天大學(xué)，2013.

[6] 吳志媛.基于潛在語義索引的Web文本挖掘[D].無錫:江南大學(xué)，2013.

[7] 劉遠(yuǎn)超.基于動態(tài)自組織映射模型的文本聚類研究[D].哈爾濱:哈爾濱工業(yè)大學(xué)，2006.

[8] 劉旭政，張春榮，陳水生.基于模糊神經(jīng)網(wǎng)絡(luò)的拉索耐久性評價模型[J].華東交通大學(xué)學(xué)報，2010，27(2):8-12.

[9] 劉云峰.基于潛在語義分析的中文概念檢索研究[D].武漢:華中科技大學(xué)，2005.

[10] Alahakoon D，Halgamuge S K，Srinivasan B.Dynamic self-organizing maps with controlled growth for knowledge discovery[J].IEEE Transactions on Neural Networks，2000，11(3):601-614.

[11] Jin Huidong，Shum Wing-Ho，Leung Kwong-Sak，et al.Expanding self-organizing map for data visualization and cluster analysis[J].Information Sciences，2004，163(1-3):157-173.

[12] 尹峻松，胡德文，陳爽，等.DSOM:一種基于NO時空動態(tài)擴(kuò)散機(jī)理的新型自組織模型[J].中國科學(xué)(E輯:信息科學(xué))，2004，34(10):1094-1109.

[13] Pal S K，Dasgupta B，Mitra P.Rough self-organizing map[J].Applied Intelligence，2004，21(3):289-299.

[14] Hussin M F，Kamel M.Document clustering using hierarchical SOMATR neural network[C]//Proceedings of the 2003 IEEE International Joint Conference on Neural Networks.2003，3:2238-2242.

[15] 劉遠(yuǎn)超，王曉龍，劉秉權(quán).一種改進(jìn)的k-means文檔聚類初值選擇算法[J].高技術(shù)通訊，2006，16(1):11-15.

[16] Hearst M A.TextTiling:Segmenting text into multi-paragraph subtopic passages[J].Computational Linguistics，1997，23(1):33-64.

[17] Ayad H，Kamel M.Topic discovery from text using aggregation of different clustering methods[C]//Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence.2002:161-175.