吳曉琴 陳圣兵 何立新

（合肥學(xué)院網(wǎng)絡(luò)與智能信息處理重點實驗室，安徽 合肥 230601）

1 引言

文本聚類是文本挖掘和信息檢索領(lǐng)域的重要手段之一，它是依據(jù)一種聚類假設(shè)：同一類的文檔相似度較大，而不同類的文檔相似度較小。其功能是把文本相似度大的文檔聚到一類，目前已被應(yīng)用到信息檢索系統(tǒng)以提高檢索效率，文本聚類方法有多種，其中，K均值聚類算法因其簡單和高效性成為目前應(yīng)用最廣泛應(yīng)用一種文本聚類算法。但K均值聚類算法在聚類之前，首先要確定初始的聚類中心，如初始聚類中心的選擇不當(dāng)，易于陷入局部最優(yōu)解，降低聚類算法的精確性[1-3]，因此K均值聚類算法在文本聚類應(yīng)用中具有一定的局限性，很難得到理想的結(jié)果。針對K均值聚類算法存在的問題，本文提出一種改進遺傳算法的文本聚類方法，并對該方法進行實驗，得到滿意的聚類結(jié)果，提高了文本聚類的準確度和精確度。

2 文本表示和相似度度量

文本聚類前須對原始文本進行必要的處理，使一個無結(jié)構(gòu)的人類自然語言描述的文本轉(zhuǎn)化為結(jié)構(gòu)化的計算機能識別處理的格式，即通過從文本中抽取出的特征項（字、詞、詞組、短語）來量化表示文本信息，目前大多采用向量空間模型（Vector Space Model,VSM）來描述文本向量，VSM是20世紀60年代末期由G.Salton等人提出的，是當(dāng)前自然語言處理中常用的主流模型。在VSM中，一個文檔由若干個特征詞的組成，用向量表示：D（t1，t2，……，tn），其中 tk是特征項。每一個特征項 tk都被賦予一個權(quán)值 wk。文檔D可用特征項所對應(yīng)的權(quán)值所表示：D（w1，w2，……，wn），其中wk就是特征項tk的權(quán)值。本文采用特征項頻率和文檔頻數(shù)來計算文本特征項權(quán)值，具體計算公式如下：

其中，TF（ti）表示特征項ti在文檔中出現(xiàn)的頻率，N為總文檔數(shù)，ni為包含特征項ti的文檔數(shù)。

文本相似性的度量主要有余弦相似度函數(shù)法和距離函數(shù)法，本文采用向量間的余弦相似度來進行度量，如計算文檔D1、D2間的相似度，具體計算公式如下：

其中w1k、w2k分別表示文檔D1、D2中第k個特征值得權(quán)值。

3 基于改進遺傳算法的文本聚類方法

遺傳算法是一種有效地找到近似最優(yōu)解的優(yōu)化方法，從初始解逐步地逼近問題的最優(yōu)解。本文就是針對遺傳操作交叉和變異操作進行改進,對前一階段聚類的劃分結(jié)果進行優(yōu)化。從而來加快搜索速度的。算法基本流程如圖1所示：

圖1 算法基本流程圖

3.1 編碼方式

本文采用改進的遺傳算法對K-means算法中的聚類中心進行優(yōu)化，再用優(yōu)化后的聚類中心實現(xiàn)K-means算法，從而得到較為理想的聚類結(jié)果?？刹捎谜麛?shù)編碼方案。染色體基因由聚類中心組成，因聚類中心個數(shù)是可變的，故染色體的長度不是固定的，也是可變的，具體編碼形式為其中 ai為第 i個聚類中心，（1≤i≤N，N 為文檔總數(shù)）。

3.2 適應(yīng)度函數(shù)的確定

適應(yīng)度函數(shù)的定義將影響整個算法效率，聚類結(jié)果類間距離越大、類內(nèi)距越小表明聚類效果越好，本文根據(jù)聚類類間距和類內(nèi)距來確定適應(yīng)度函數(shù)：

其中ci為類中心，Dmin（x）為類間最小距離，xj類中的對象，C（x）表示類內(nèi)平均距離。

3.3 選擇算子

本文采用經(jīng)典的輪盤賭選擇法，每個染色體的適應(yīng)度值除以與種群的所有選擇染色體的適應(yīng)度值構(gòu)成選擇概率，即產(chǎn)生一個隨機數(shù)，將隨機數(shù)作為選擇指針，根據(jù)選擇概率確定選擇個體，當(dāng)然選擇概率大，個體被選中的概率也越高。

式中：fi——染色體i的適應(yīng)值，Pi——染色體i被選中的概率，m為種群的大小。

3.4 交叉算子

本文采用單點插入，單點交叉相結(jié)合方法，單點插入的主要過程：根據(jù)交叉概率確定交叉點，截取長染色體一段基因，具體段長可在 [k/3，k/2]中產(chǎn)生一個隨機數(shù)整數(shù)（k為染色體長度），并將這段基因插入另一個較短染色體交叉點的位置；對染色體長度相同或相近的兩個個體采用單點交叉，變異后面一段進行交叉，具體操作過程可用圖2表示：

圖2 交叉算子圖解

3.5 變異算子

遺傳算法引入變異算子使該算法具有局部搜索能力，可向最優(yōu)解加速收斂，保持群體多樣性，以防止出現(xiàn)未熟收斂現(xiàn)象。本文采用均勻變異算子，其具體操作過程是：

1 ）確定個體中的變異點，每個基因點的取值范圍為[1,N]（N為文檔數(shù)）

2 ）對每一個變異點以變異概率Pm從對應(yīng)基因的取值范圍內(nèi)取一個隨機數(shù)來替換對應(yīng)的基因值，即變異點的新基因值為：

其中，r為（0，1）范圍內(nèi)符合均勻概率分布的一個隨機數(shù)，Xi取整。

3.6 交叉、變異概率

交叉概率Pc和變異概率Pm的選擇不當(dāng)直接影響遺傳算法的執(zhí)行效率。Pc過大時高適應(yīng)度的個體被破壞，但Pc過小直接影響算法的收斂性,，而Pm過大遺傳算法變成了隨機搜索算法。Pm過小就新個體很難產(chǎn)生，因此本文采用自適應(yīng)[4]交叉概率Pc和變異概率Pm。

4 實驗結(jié)果分析

為了驗證文中提出的算法效率，從國家語委網(wǎng)站http：//www.cncorpus.org/ccindex.aspx現(xiàn)代漢語語料庫中抽取500篇文檔組成的文檔集，其中計算機類、法律類、經(jīng)濟類、歷史類、能源類各100篇進行實驗，實驗中參數(shù)：種群規(guī)模M=80，最大迭代數(shù)MGEN=300,本文實驗操作系統(tǒng)采用的是Windows操作系統(tǒng)，實驗環(huán)境主要應(yīng)用MyEclipse7.0開發(fā)平臺，采用SQL2000做為后臺數(shù)據(jù)庫，用 Java語言分別實現(xiàn)K均值聚類[5]、遺傳算法聚類和本文改進遺傳算法聚類算法。F-Measure[6]作為算法的評價標準,F-Measure定義如下：

其中，P（i， j）表示查準率，R（i， j）表示查全率，n（i， j）為在聚類 i中屬于分類 j的數(shù)目，ni為聚類 i中所有對象的數(shù)目，nj為分類j中所有對象的數(shù)目。三種算法的比較結(jié)果如圖3所示。

圖3 三種算法文本聚類效果的比較

為了進一步驗證算法效率，繪制了算法最大、平均適應(yīng)度變化曲線，如圖4所示

圖4 最大、平均適應(yīng)度變化曲線

5 結(jié)束語

本文利用了遺傳算法的全局優(yōu)化能力對文本聚類算法中聚類中心進行優(yōu)化，從而獲得較優(yōu)化的聚類中心，實驗結(jié)果可知，大大改善了K均值聚類算法的運行效率和文本聚類精確度。由此可得,基于改進遺傳算法的聚類算法具有一定的實用性,但缺點還是存在的,那就是聚類的結(jié)果往往有一定的隨機性,收斂速度也較慢,今后還需對算法進一步改進。

[1]任江濤.一種用于文本聚類的改進的 K 均值算法[J].計算機應(yīng)用，2006，（6）：73-75.

[2]寇蘇玲，蔡慶生.中文文本分類中的特征選擇研究[J].計算機仿真，2007，（3）：100-104.

[3]王國勇，徐建鎖.TCBLSA：一種中文文本聚類新方法[J].計算機工程，2004，（3）：21-22.

[4]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2003：75，78.

[5]任江濤.一種用于文本聚類的改進的均值算法[J].計算機應(yīng)用，2006，（6）：73-75

[6]覃曉，元昌安.基于遺傳算法和自組織特征映射網(wǎng)絡(luò)的文本聚類方法[J].計算機應(yīng)用，2008，（3）：21-22.