侯澤民，巨 筱

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

0 引言

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

1 相關技術

1.1潛在語義索引

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

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

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

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

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

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

本文給出的改進算法中，在聚類預處理階段，應用潛在語義索引理論和奇異值分解算法來表示文本特征向量，以體現特征詞的語義關系并實現特征向量的降維。

1.2 自組織映射網絡

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

SOM網絡的工作原理為:競爭、合作、自適應[9]。

1)競爭。

競爭過程就是選擇獲勝神經元過程。設m為輸入層向量空間維數，輸入層空間向量模式記為:

SOM網絡中輸出層神經元向量空間與輸入層向量空間維數相同。所以將輸出層神經元節(jié)點j向量記為:

其中k為SOM網絡輸出層神經元節(jié)點總數。計算輸入向量X與輸出層神經元節(jié)點之間的距離，距離最小的輸出層神經元即為獲勝神經元。

2)合作。

合作過程就是根據競爭過程獲得的獲勝神經元，計算獲勝神經元節(jié)點的拓撲鄰域。

設hj，i為獲勝神經元節(jié)點i為中心的拓撲鄰域，dj，i為獲勝神經元節(jié)點i與興奮神經元節(jié)點j之間的側向距離。則 hj，i和 dj，i之 間的關系為:

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

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

公式(4)中的hj，i(x)(n)稱為鄰域函數。根據鄰域函數hj，i(x)(n)可以計算確定獲勝神經元節(jié)點的拓撲鄰域。

3)自適應。

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

2 改進的基于潛在語義索引的文本聚類算法

2.1 傳統SOM算法的局限性

SOM算法是常用的、經典的無導師學習算法，可以將高維向量空間模型轉化為二維向量空間表示;抗噪聲能力強;能進行并行化處理;可視化效果好。但是SOM算法也存在一些局限性:

1)SOM算法需要提前確定聚類類別數目[10]，即輸出層神經元節(jié)點的數目和結構層次。

2)SOM網絡進行訓練時，一些輸出層神經元節(jié)點的連接權值與輸入層模式相差較大，始終不能獲勝，成為“死神經元[11-12]”。

3)SOM算法缺乏具體的目標函數[13-14]。

2.2 SOM算法的改進策略

從2.1節(jié)內容可以看出，傳統SOM算法依然存在著一些局限性。2.1節(jié)中提到的局限性1)，在實際聚類過程中，大多數研究者們也只是根據自己豐富的經驗和專業(yè)的知識來確定聚類類別數目，而且是多次嘗試，直至得到正確的結果。這種方法有很大的盲目性和不確定性，若得出錯誤的聚類類別數目，最終的聚類效果也會很差。基于此，本文針對2.1節(jié)內容的局限性1)，給出相應的解決方案:即改進傳統的kmeans聚類算法得出聚類初始值，作為聚類類別數目。將此準確聚類類別數目作為SOM網絡模型輸出層神經元節(jié)點數目。

2.3 獲取SOM算法聚類類別數目的值

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

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

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

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

圖1 聚點-深度變化曲線

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

2.4 改進的基于潛在語義索引的文本聚類算法

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

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

在文本聚類階段，對傳統的SOM算法進行改進，算法流程如下:

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

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

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

其中k為SOM網絡輸出層神經元節(jié)點總數。

4)更新獲勝神經元節(jié)點及鄰域內節(jié)點的權值向量:

5)更新學習率η(n):

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

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

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

3 實驗結果及分析

3.1 聚類效果評價方法

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

其中:

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

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

3.2 測試數據集

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

表1 測試數據集數據

3.3 實驗結果及分析

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

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

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

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

4 結束語

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

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

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

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

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

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

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

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

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

[9] 劉云峰.基于潛在語義分析的中文概念檢索研究[D].武漢:華中科技大學，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)擴散機理的新型自組織模型[J].中國科學(E輯:信息科學)，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] 劉遠超，王曉龍，劉秉權.一種改進的k-means文檔聚類初值選擇算法[J].高技術通訊，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.