改進遺傳算法在文本聚類中的應用研究

吳曉琴 陳圣兵 何立新

（合肥學院網絡與智能信息處理重點實驗室，安徽 合肥 230601）

1 引言

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

2 文本表示和相似度度量

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

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

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

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

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

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

圖1 算法基本流程圖

3.1 編碼方式

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

3.2 適應度函數的確定

適應度函數的定義將影響整個算法效率，聚類結果類間距離越大、類內距越小表明聚類效果越好，本文根據聚類類間距和類內距來確定適應度函數：

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

3.3 選擇算子

本文采用經典的輪盤賭選擇法，每個染色體的適應度值除以與種群的所有選擇染色體的適應度值構成選擇概率，即產生一個隨機數，將隨機數作為選擇指針，根據選擇概率確定選擇個體，當然選擇概率大，個體被選中的概率也越高。

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

3.4 交叉算子

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

圖2 交叉算子圖解

3.5 變異算子

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

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

2 ）對每一個變異點以變異概率Pm從對應基因的取值范圍內取一個隨機數來替換對應的基因值，即變異點的新基因值為：

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

3.6 交叉、變異概率

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

4 實驗結果分析

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

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

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

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

圖4 最大、平均適應度變化曲線

5 結束語

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

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

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

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

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

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

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