改進(jìn)遺傳算法在文本聚類中的應(yīng)用研究

吳曉琴 陳圣兵 何立新

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

1 引言

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

2 文本表示和相似度度量

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

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

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

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

3 基于改進(jìn)遺傳算法的文本聚類方法

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

圖1 算法基本流程圖

3.1 編碼方式

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

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

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

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

3.3 選擇算子

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

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

3.4 交叉算子

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

圖2 交叉算子圖解

3.5 變異算子

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

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

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

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

3.6 交叉、變異概率

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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