高新成,周中雨,王莉利,邵國(guó)銘,張 強(qiáng)

(1.東北石油大學(xué) 現(xiàn)代教育技術(shù)中心,黑龍江 大慶 163318; 2.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,黑龍江 大慶 163318)

0 引 言

文本聚類是將給定對(duì)象的集合劃分為不同子集的過(guò)程,目標(biāo)是使每個(gè)子集內(nèi)部的元素盡量相似,不同子集間的元素盡量迥異,其在文本挖掘中應(yīng)用廣泛.空間矢量模型VSM(vector space model)是文本數(shù)據(jù)挖掘的常用模型,其通過(guò)把詞條變成一維空間向量便于進(jìn)行空間向量計(jì)算.因此,聚類效果主要受特征維度[1]大小和冗余特征的影響,文本特征中存在冗余特征,無(wú)監(jiān)督特征選擇是選取非冗余特征,使聚類效果得到明顯提升.

傳統(tǒng)的特征選擇方式有文檔頻率DF、互信息MI、卡方檢驗(yàn)CHI和信息增益,這些方式均存在局限性且特征選擇后的精度較低問(wèn)題.目前特征選擇的目標(biāo)有兩個(gè): 一是基于特征選擇后聚類效果得到提升; 二是如何獲得最多有用的文本特征[2-3].因此,本文設(shè)計(jì)一種基于二進(jìn)制蜉蝣算法優(yōu)化的特征選擇及文本聚類算法,首先對(duì)文本特征進(jìn)行選擇,選擇出最優(yōu)子集并把特征選擇的最優(yōu)解作為K-means++算法的輸入,得到最優(yōu)的聚類效果.

目前已有的特征選擇方法主要有3種: 過(guò)濾法、嵌入法和封裝法.過(guò)濾法是一種基于數(shù)學(xué)的統(tǒng)計(jì)方法,其特征選擇方法與后面的模型訓(xùn)練分開,聚類效果較差; 嵌入法是將學(xué)習(xí)器訓(xùn)練過(guò)程與特征選擇過(guò)程融為一體,二者在同一優(yōu)化過(guò)程中完成,在學(xué)習(xí)器訓(xùn)練過(guò)程中自動(dòng)進(jìn)行特征選擇[4],但參數(shù)設(shè)置需要較深的背景知識(shí),不利于實(shí)際推廣; 封裝法利用搜索策略尋找優(yōu)質(zhì)特征子集,并基于學(xué)習(xí)算法得到優(yōu)質(zhì)特征子集,是直接面向算法優(yōu)化,不需要太多的知識(shí),也是最常用的特征選擇方法.

元啟發(fā)式算法已廣泛應(yīng)用于最優(yōu)化問(wèn)題求解中,且已被應(yīng)用到文本挖掘領(lǐng)域中特征選擇的求解問(wèn)題[5-6],主要包括一些智能優(yōu)化算法,如蟻群算法、遺傳算法、粒子群優(yōu)化算法、野草算法等.這類問(wèn)題通過(guò)迭代的方式不斷去搜索最優(yōu)解.劉占峰等[7]提出了一種基于粒子群優(yōu)化的模糊粗糙集和實(shí)例聯(lián)合選擇算法,算法用于特征和實(shí)例聯(lián)合選擇任務(wù)中識(shí)別高質(zhì)量的模糊粗糙雙約簡(jiǎn)集,通過(guò)ε-雙約簡(jiǎn)的適應(yīng)度函數(shù)評(píng)估約簡(jiǎn)集的質(zhì)量,并把粒子群算法用于搜索過(guò)程中,實(shí)現(xiàn)特征的約減與精準(zhǔn)分類; Chen等[8]用混沌蟻獅算法與特征選擇模型結(jié)合并對(duì)文本特征進(jìn)行篩選,在11個(gè)基準(zhǔn)函數(shù)上利用3個(gè)文本數(shù)據(jù)集和其他4種分類算法比較,該方法能減少文本特征,具有較好的分類效果; 張陽(yáng)等[9]提出了一種基于Word2Vec詞嵌入和高維生物基因選擇遺傳算法的文本特征選擇方法,對(duì)高維詞向量模擬基因表達(dá)方式進(jìn)行迭代進(jìn)化,用Word2vec把文本轉(zhuǎn)換成基因的詞向量,最后基于遺傳算法搜索策略,在特征縮減率和文本聚類精度方面性能良好; Mahdieh等[10]提出了一種多目標(biāo)相對(duì)判別準(zhǔn)則(MORDC),平衡了最小冗余特征及與目標(biāo)最大相關(guān)的特征,并采用多目標(biāo)進(jìn)化框架,通過(guò)解空間進(jìn)行搜索文本特征,該方法具有較好的分類性能; 王琛等[11]把灰狼尋找食物的過(guò)程模擬成特征選擇的過(guò)程,對(duì)特征子集合并然后交叉,選出最優(yōu)的子集,最后得到特征子集與多目標(biāo)的K-means算法進(jìn)行融合,經(jīng)多方面評(píng)估性能良好.因此,元啟發(fā)式算法在縮減特征數(shù)量與優(yōu)質(zhì)特征選擇上效果較好,但以上早期的智能群體算法尋優(yōu)能力不強(qiáng),且收斂速度較慢,與過(guò)濾的方法相結(jié)合效果也不明顯.而蜉蝣算法(mayfly algorithm,MA)是一種結(jié)合粒子群優(yōu)化算法(particle swarm optimization,PSO)[12]、遺傳算法(genetic algorithm,GA)[13]、螢火蟲算法(firefly algorithm,FA)[14]等優(yōu)點(diǎn)的群體智能優(yōu)化算法,具有極強(qiáng)的尋優(yōu)能力,但受限于解決連續(xù)型問(wèn)題.因此,本文將傳統(tǒng)蜉蝣算法改進(jìn)為解決離散型問(wèn)題的蜉蝣優(yōu)化算法,即二進(jìn)制蜉蝣優(yōu)化算法(MOMA).該算法對(duì)傳統(tǒng)二進(jìn)制位置更新公式進(jìn)行改進(jìn),克服了局部尋優(yōu)能力弱的缺點(diǎn),并提出新的交配與變異操作,提高了全局尋優(yōu)能力.

1 算法設(shè)計(jì)

為更好實(shí)現(xiàn)聚類效果,本文首先利用二進(jìn)制蜉蝣優(yōu)化算法對(duì)文本特征進(jìn)行選擇,獲得去除冗余特征的最優(yōu)子集,然后在最優(yōu)特征子集上進(jìn)行聚類分析.算法過(guò)程分3個(gè)階段: 第一階段構(gòu)建向量空間模型,其中涉及必要的文本預(yù)處理步驟; 第二階段用二進(jìn)制蜉蝣優(yōu)化算法對(duì)特征進(jìn)行選擇,得到初始的信息化特征子集; 第三階段在最優(yōu)特征子集的基礎(chǔ)上[15],利用文本聚類算法K-means++進(jìn)行聚類,得到文檔最終聚類效果.

1.1 構(gòu)建空間向量模型

構(gòu)建空間向量模型主要分4步: 1) 分詞,根據(jù)空格和標(biāo)點(diǎn)符號(hào)把文本和文檔分割成詞語(yǔ)和詞條,并移除空格; 2) 去除停用詞,去除小權(quán)重、高頻率詞語(yǔ),如果這些詞語(yǔ)存在于文檔中將會(huì)影響聚類的結(jié)果; 3) 提取詞干,去除詞匯的前綴和后綴,轉(zhuǎn)換為相同詞根,并將相同詞定義為一個(gè)特征,該步驟可進(jìn)行提詞器操作; 4) 計(jì)算文本詞條權(quán)重,當(dāng)詞條在不同文檔中的頻率較高時(shí),可利用該詞區(qū)分文檔內(nèi)容,且詞條應(yīng)被賦予更高的權(quán)重值.目前,應(yīng)用的主要詞條權(quán)重計(jì)算方法為統(tǒng)計(jì)分析算法中的逆文檔頻率指數(shù)TF-IDF方法,計(jì)算公式為

(1)

其中wi,j為文檔i中詞條j的權(quán)重,TF(i,j)為文檔i中詞條j的頻率,IDF(i,j)為倒數(shù)文檔頻率,n為文檔數(shù)量,DF(j)為包括特征j的文檔數(shù)量.構(gòu)造空間向量模型VSM如下:

(2)

1.2 基于二進(jìn)制蜉蝣優(yōu)化算法的特征選擇策略

1.2.1 特征選擇模型

特征選擇的目標(biāo)是選出具有明顯區(qū)分性的樣本特征,而文本特征選擇就是選出代表文檔主要含義的特征詞.假設(shè)給定文本特征集合為F,表示為Fi={fi,1,fi,2,…,fi,j,…,fi,t},其中t表示預(yù)處理后唯一文本特征數(shù)量,i為文檔數(shù)量.FS經(jīng)過(guò)特征選擇算法選擇后選出新的特征子集FSi={fsi,1,fsi,2,fsi,j,…,fsi,m},其中m為選擇后的特征長(zhǎng)度,fsi,j∈{1,0},j=1,2,…,m.若fsi,j=1,則表明文檔中所選特征j為優(yōu)質(zhì)特征; 若fsi,j=0,則表明文檔中所選特征j為無(wú)用特征.

1.2.2 解表示

在用二進(jìn)制蜉蝣算法對(duì)文本特征進(jìn)行選擇過(guò)程中,每個(gè)雄雌蜉蝣的位置代表一個(gè)特征文檔的子集,如表1所示.蜉蝣種群包括蜉蝣的位置集合,其中位置集合由二進(jìn)制0或1表示,每個(gè)蜉蝣的位置表示文檔是否選擇其特征.蜉蝣第j個(gè)位置表示文檔第j個(gè)特征的位置.

表1 特征選擇的解表示

該算法從隨機(jī)解開始搜索,不斷地選擇高質(zhì)量的特征并改進(jìn)蜉蝣種群總體以獲得全局最優(yōu)解,最優(yōu)蜉蝣的位置表示最優(yōu)解和新文檔的子集.在給定的數(shù)據(jù)集中,每個(gè)特征都被視為一個(gè)搜索空間.表1中假設(shè)蜉蝣位置值為1,則表示該位置的特征為信息特征; 蜉蝣位置值是0,則表示特征j會(huì)被選擇為非信息特征.

1.2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評(píng)價(jià)算法的候選解,每一代都要計(jì)算候選解的適應(yīng)度值.若解的適應(yīng)度值較大,則該解用于替換當(dāng)前較小適應(yīng)度值的解.平方誤差(MAD)是特征選擇領(lǐng)域常用的度量方式,本文使用MAD作為特征選擇的適應(yīng)度函數(shù),并作為評(píng)判蜉蝣位置的目標(biāo)函數(shù).MAD可由均值與Xi,j的中值之差表示:

(3)

(4)

1.3 二進(jìn)制蜉蝣優(yōu)化算法

受蜉蝣生物活動(dòng)啟發(fā),Zervoudakis等[16]提出了蜉蝣算法,每只蜉蝣在搜索空間中的位置表示問(wèn)題的解.算法工作原理: 隨機(jī)產(chǎn)生兩組蜉蝣種群,其中分別表示雄性和雌性蜉蝣種群.每只蜉蝣被隨機(jī)放置在問(wèn)題空間中,作為由d維向量表示的候選解x=(x1,x2,…,xd),并結(jié)合目標(biāo)函數(shù)f(x)對(duì)其性能進(jìn)行評(píng)估.蜉蝣的速度v=(v1,v2,…,vd)定義為其位置的變化,每只蜉蝣的飛行方向是個(gè)體和社會(huì)飛行經(jīng)驗(yàn)的動(dòng)態(tài)交互作用.每只蜉蝣都會(huì)調(diào)整自己的軌跡,使其向個(gè)人最佳位置(pbest)以及整個(gè)過(guò)程中蜉蝣所獲得的最佳位置(gbest)飛行.算法偽代碼如下:

算法1蜉蝣優(yōu)化算法特征選擇算法MA.

Initializing the male mayfly populationxi(i=1,2,…,N) and speedvmi//初始化雄蜉蝣種群位置及速度

Initializing the female mayfly populationyi(i=1,2,…,M) and speedvFi//初始化雌蜉蝣種群位置及速度

Evaluate the fitness values of each mayfly//評(píng)估每只蜉蝣的適應(yīng)度

Find the global optimal solutiongbest//發(fā)現(xiàn)全局最好的蜉蝣位置

Do While the termination criteria are not met//為滿足終止規(guī)則

Update male and female mayfly speed reconciliation//更新雄性和雌性蜉蝣的速度和位置

Evaluation of solution//評(píng)估解

Mayflies sorting//蜉蝣排序

Mayflies mate//蜉蝣交配

Evaluation of offspring//評(píng)估子代

Randomly divide the offspring into male and female//隨機(jī)將子代分為雄性與雌性

Updatepbestandgbest//更新全局最優(yōu)解與蜉蝣歷史位置最優(yōu)解

End while.

每只蜉蝣位置表示的候選解通過(guò)式(3)定義的適應(yīng)度函數(shù)進(jìn)行評(píng)估.在MA算法中,解包含單個(gè)實(shí)體(特征),且算法不斷對(duì)蜉蝣位置進(jìn)行評(píng)估.蜉蝣當(dāng)前的位置按適應(yīng)度函數(shù)進(jìn)行評(píng)估,全局最好的蜉蝣由自身速度更新位置,其余雄蜉蝣按全局最好位置和歷史最佳位置更新位置,而雌蜉蝣由雄蜉蝣位置更新速度與方向.直到取得表示問(wèn)題最優(yōu)解的蜉蝣位置.

二進(jìn)制蜉蝣個(gè)體更新策略如下: 雄蜉蝣位置更新公式為

(5)

雄蜉蝣移動(dòng)速率更新公式為

(6)

實(shí)際上,為繁衍雌蜉蝣會(huì)一直向雄蜉蝣運(yùn)動(dòng),吸引過(guò)程取決于解的質(zhì)量,雌蜉蝣的位置更新公式為

(7)

速度更新公式為

(8)

針對(duì)傳統(tǒng)蜉蝣算法僅解決連續(xù)性問(wèn)題,不適用于特征選擇的離散性問(wèn)題,本文借鑒劉建華等[18]提出的基于改進(jìn)二進(jìn)制粒子群算法的優(yōu)化思路,在保持速度公式不變的前提下,對(duì)雄雌蜉蝣的速度概率映射函數(shù)進(jìn)行重新定義,表示為

(9)

圖1 映射概率函數(shù)值Fig.1 Mapping probability function values

(10)

(11)

由于最初雄蜉蝣位置的舞蹈系數(shù)d很大,導(dǎo)致映射的概率很大,因此位置改變概率也會(huì)變大,這種情況下,最優(yōu)雄蜉蝣位置容易變化,可增強(qiáng)算法全局的搜索能力.隨著迭代次數(shù)的增加,最優(yōu)的雄蜉蝣速度逐漸變小,位置變化概率也會(huì)變小,此時(shí)全局搜索能力變?nèi)?局部探測(cè)能力變強(qiáng).對(duì)于非最優(yōu)雄蜉蝣,速度的更新是由最優(yōu)位置和歷史最優(yōu)位置決定的.當(dāng)速度為0時(shí),最優(yōu)蜉蝣和歷史最優(yōu)位置相等,位置一般不需要改變.當(dāng)速度為負(fù)時(shí),利用式(10)進(jìn)行位置更新,此時(shí)最優(yōu)雄蜉蝣位置和歷史最優(yōu)位置很可能為0,雄蜉蝣的位置很可能為1,因此位置需大概率變?yōu)?.當(dāng)速度為正時(shí),利用式(11)對(duì)位置進(jìn)行更新,此時(shí)最優(yōu)雄蜉蝣位置可能為1,而雄蜉蝣的位置很可能是0,所以位置需要最大概率變?yōu)?.對(duì)于雌蜉蝣,其位置由雄蜉蝣的位置確定.當(dāng)優(yōu)于對(duì)應(yīng)的雄蜉蝣位置時(shí),雌蜉蝣根據(jù)自身的速度進(jìn)行變化,隨著迭代次數(shù)的增加,雌蜉蝣速度趨于0,位置改變概率也逐漸變小,這種情況下雌蜉蝣位置小概率會(huì)改變.當(dāng)劣于對(duì)應(yīng)的雄蜉蝣位置時(shí),雌蜉蝣的位置由雄蜉蝣的位置更新,當(dāng)雌蜉蝣速度為負(fù)時(shí),對(duì)應(yīng)的雄蜉蝣位置很大可能為0,而雌蜉蝣位置很大可能是1,此時(shí)雌蜉蝣的位置可能為0.當(dāng)雌蜉蝣速度為正時(shí),對(duì)應(yīng)的雄蜉蝣位置很可能為1,而雌蜉蝣位置很可能為0,所以雌蜉蝣的位置可能變?yōu)?.

1.4 進(jìn)化策略

1.4.1 交配操作

蜉蝣交配根據(jù)解的質(zhì)量將同等級(jí)的雄雌蜉蝣進(jìn)行交配,產(chǎn)生兩個(gè)后代.為解決原始蜉蝣算法只能求解連續(xù)值的問(wèn)題,現(xiàn)對(duì)蜉蝣的交叉策略進(jìn)行改變.本文采用多點(diǎn)交叉的方式,隨機(jī)生成初始交叉點(diǎn)和交叉結(jié)束點(diǎn),如圖2所示,[1,0,0,1,1]為雄蜉蝣位置,[0,0,1,0,0]為雌蜉蝣位置,[0]和[1]為雄、雌蜉蝣隨機(jī)生成的初始交叉點(diǎn),[1]和[0]為雄、雌蜉蝣隨機(jī)生成的交叉結(jié)束點(diǎn),雄、雌蜉蝣通過(guò)交換選中區(qū)間完成交叉,最終生成兩個(gè)子代.

圖2 交配操作示意圖Fig.2 Schematic diagram of mating operation

1.4.2 變異操作

原始的蜉蝣算法變異是高斯近似變異,應(yīng)用于連續(xù)值問(wèn)題的求解,并不適用于二進(jìn)制變異策略.本文采用基本位變異方法,該方法隨機(jī)生成一個(gè)(0,1)的隨機(jī)數(shù),當(dāng)隨機(jī)數(shù)小于變異概率時(shí)進(jìn)行變異,為增加種群的多樣性,采用多點(diǎn)變異的方式,如圖3所示.由圖3可見,蜉蝣位置第一個(gè)隨機(jī)選[0]為變異初始點(diǎn),第二個(gè)[0]為變異結(jié)束點(diǎn),變異操作即對(duì)變異區(qū)間的數(shù)取反.原始蜉蝣位置由[1,0,1,1,0,1]變?yōu)閇1,1,0,0,1,1].

圖3 變異操作示意圖Fig.3 Schematic diagram of mutation operation

1.5 基于K-means++算法聚類分析

K-means算法[19]是目前常用的聚類算法之一,已在許多領(lǐng)域中得到成功應(yīng)用,實(shí)用性良好,但傳統(tǒng)的K-means算法存在聚類中心參數(shù)難以確定且聚類結(jié)果不穩(wěn)定的問(wèn)題.本文利用提出的二進(jìn)制蜉蝣優(yōu)化算法對(duì)K-means++算法進(jìn)行聚類優(yōu)化.K-means++算法采用一定策略選擇質(zhì)心,其中輪盤賭算法是最簡(jiǎn)單有效的策略.在輪盤賭算法中,第m個(gè)質(zhì)心的選取取決于選取數(shù)據(jù)點(diǎn)距離第(m-1)個(gè)質(zhì)心的距離,度量距離越大則越有可能被選取.假設(shè)K-means++算法的輸入樣本集為D={x1,x2,…,xm},聚類的簇?cái)?shù)為k,則經(jīng)過(guò)N次迭代后算法停止.K-means++算法的運(yùn)行步驟如下.

1) 找出k個(gè)聚類中心點(diǎn): 從文本數(shù)據(jù)集D中隨機(jī)選出一個(gè)樣本作為初始的質(zhì)心向量c1,計(jì)算每只樣本與最近的質(zhì)心向量距離和Sum(D(x)),取一個(gè)能位于Sum(D(x))中的隨機(jī)值Random,并令Random-=D(x),直到其值≤0,此時(shí)的點(diǎn)便可作為下一個(gè)質(zhì)心點(diǎn).重復(fù)上述步驟,直到k個(gè)聚類中心被選出來(lái),k個(gè)聚類中心可記作{c1,c2,…,ck}.

2) 利用這k個(gè)初始聚類中心運(yùn)行K-means算法,對(duì)于n=1,2,…,N進(jìn)行如下操作:

① 將簇劃分Ci,初始化為Ci={ci}(i=1,2,…,k);

② 對(duì)i=1,2,…,m分別計(jì)算樣本xi和各質(zhì)心向量cj(j=1,2,…,k)的距離ci,j,其中ci,j=‖xi-cj‖,將最小的xi標(biāo)記為di,j所對(duì)應(yīng)的類別j,然后更新C=Cj∪{xi};

④ 如果k個(gè)質(zhì)心的位置都未發(fā)生變化,則終止算法,轉(zhuǎn)步驟3).

3) 輸出結(jié)果簇劃分C={C1,C2,…,Ck}.

2 實(shí)驗(yàn)對(duì)比及分析

本文用Python編寫二進(jìn)制蜉蝣優(yōu)化算法,用該算法進(jìn)行文本特征選擇[20],尋求擁有更多有用特征的最優(yōu)子集,利用K-means++算法對(duì)選擇的特征進(jìn)行文本聚類,并通過(guò)實(shí)驗(yàn)驗(yàn)證基于二進(jìn)制蜉蝣算法特征選擇后的聚類效果.

2.1 測(cè)試文本數(shù)據(jù)集

為驗(yàn)證算法的穩(wěn)定性和適應(yīng)性,本文采用智能實(shí)驗(yàn)室LABIC(http://sites.labic.icme.usp.br/text_collections/)提供的5種基準(zhǔn)數(shù)據(jù)集進(jìn)行測(cè)試,測(cè)試文檔數(shù)據(jù)集信息列于表2.

表2 測(cè)試文檔數(shù)據(jù)集信息

2.2 算法評(píng)估指標(biāo)

準(zhǔn)確率(Accuracy)、查準(zhǔn)率(Precision)、查全率(Recall)和F度量(F-measure)是文本聚類常用的指標(biāo),為驗(yàn)證二進(jìn)制蜉蝣優(yōu)化算法的效果,引入特征選擇的數(shù)量和適應(yīng)度值與迭代次數(shù)的關(guān)系.

1) 準(zhǔn)確率.準(zhǔn)確率用于計(jì)算真實(shí)樣本被分為正確類別的比例,計(jì)算公式為

(13)

其中K表示總聚類數(shù)量,p(i,j)表示聚類j中分類i的精確值.

2) 查準(zhǔn)率.查準(zhǔn)率P表示相關(guān)文檔占所有聚類中i文檔總量的比例,計(jì)算公式為

(14)

3) 查全率.查全率R表示相關(guān)文檔實(shí)際數(shù)量占所有文檔的比例,計(jì)算公式為

(15)

其中R(i,j)表示聚類j中分類i的召回值,ni表示分類i中的實(shí)際樣本數(shù)量.

4)F度量.F度量根據(jù)查準(zhǔn)率P和查全率R計(jì)算,其中F是0～1的小數(shù),其值越接近1效果越好,聚類j中分類i的F度量計(jì)算公式為

(16)

所有聚類的F-measure可表示為

(17)

5) 特征數(shù)量.該指標(biāo)表示基于元啟發(fā)式算法對(duì)特征選擇后得到的特征個(gè)數(shù),特征數(shù)量的選擇影響文本聚類效率與準(zhǔn)確性.

6) 收斂性能.該指標(biāo)用于衡量算法的尋優(yōu)能力,本文通過(guò)計(jì)算進(jìn)行特征選擇的適應(yīng)度函數(shù)值評(píng)估算法的性能,算法收斂值即通過(guò)若干次迭代后的最優(yōu)適應(yīng)度值.

7) 收斂時(shí)間.收斂時(shí)間是指進(jìn)行特征選擇和文本聚類所用的總時(shí)間(s),該指標(biāo)用于衡量算法的收斂速度.

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

2.3.1 文本特征縮減率對(duì)比

在5個(gè)測(cè)試文本數(shù)據(jù)集上,用傳統(tǒng)元啟發(fā)式算法和本文提出的二進(jìn)制蜉蝣優(yōu)化算法得到的特征選擇情況對(duì)比結(jié)果如圖4所示.由圖4可見: 在特征縮減方面,遺傳算法特征縮減率約為50%,表現(xiàn)較差; 二進(jìn)制粒子群優(yōu)化算法特征縮減率為50%～70%,表現(xiàn)一般; 二進(jìn)制蜉蝣算法的特征縮減率達(dá)到75%～80%,相比于前兩種算法,二進(jìn)制蜉蝣算法對(duì)特征縮減率的效果更好,表明二進(jìn)制蜉蝣算法和特征選擇模型的結(jié)合,可降低冗余性特征,并降低維度空間.此外,二進(jìn)制蜉蝣算法在5種數(shù)據(jù)集中保持穩(wěn)定且領(lǐng)先的特征縮減率,也說(shuō)明其具有良好的普適性和廣泛性.

2.3.2 算法收斂性對(duì)比

MOMA,GA和PSO三種算法的復(fù)雜度對(duì)比列于表3.由表3可見,當(dāng)種群個(gè)數(shù)和迭代次數(shù)為N時(shí),3種啟發(fā)式算法的時(shí)間復(fù)雜度理論上均為O(n2),但在實(shí)際運(yùn)行過(guò)程中,PSO和MOMA算法尋優(yōu)具有方向性,因此這兩種算法運(yùn)行中所用的時(shí)間比GA算法低.而MOMA算法與PSO算法相比,前者的尋優(yōu)能力較強(qiáng),其迭代次數(shù)通常比N小,因此MOMA算法在實(shí)際運(yùn)行過(guò)程中時(shí)間小于GA算法與PSO算法.在空間復(fù)雜度上,由于GA算法是無(wú)記憶性算法,只需要得到種群中最大的適應(yīng)度值,因此其空間復(fù)雜度是O(1),而PSO和MOMA算法要記錄個(gè)體的當(dāng)前位置與種群的最佳位置,且所占空間和種群大小有關(guān),因此其空間復(fù)雜度為O(n).由于種群個(gè)數(shù)通常較小,所以3種算法分配的內(nèi)存空間差距較小.

表3 不同算法的復(fù)雜度對(duì)比

5個(gè)數(shù)據(jù)集基于3種元啟發(fā)式算法在特征選擇方面的算法收斂性實(shí)驗(yàn)結(jié)果如圖5所示.通過(guò)計(jì)算適應(yīng)度函數(shù)值評(píng)價(jià)算法的收斂性能,算法收斂即通過(guò)若干次迭代得到最優(yōu)適應(yīng)度的值.由圖5可見,二進(jìn)制蜉蝣算法約在300代收斂,而其他兩種算法約在500代收斂,因此二進(jìn)制蜉蝣算法收斂性能較好.在文本特征選擇中,二進(jìn)制蜉蝣算法得到的特征結(jié)果也具有較高的適應(yīng)度,表明其尋優(yōu)能力較好,再次證明了二進(jìn)制蜉蝣算法的有效性.

圖5 不同算法在5個(gè)數(shù)據(jù)集上的收斂性對(duì)比Fig.5 Comparison of convergence of different algorithms on 5 datasets

2.3.3 算法精度對(duì)比

3種算法在5個(gè)公共數(shù)據(jù)集上得到的類準(zhǔn)確率、查準(zhǔn)率、查全率和F度量值的指標(biāo)對(duì)比結(jié)果列于表4.由表4可見:K-means++的聚類評(píng)估指標(biāo)較其他算法差,因?yàn)镵-means++算法未經(jīng)過(guò)特征選擇機(jī)制,文本中存在大量的非信息化特征; 經(jīng)過(guò)元啟發(fā)式算法進(jìn)行選擇后,聚類精度得到一定提升; 二進(jìn)制蜉蝣算法在5個(gè)指標(biāo)上明顯優(yōu)于其他兩種傳統(tǒng)算法.因?yàn)槎M(jìn)制蜉蝣算法是在螢火蟲、遺傳和粒子群優(yōu)化算法基礎(chǔ)上改進(jìn)而來(lái)的,其尋優(yōu)能力強(qiáng),能選取表示文檔意義的適應(yīng)度值,所以精度顯著提高.

2.3.4 算法收斂時(shí)間對(duì)比

不同算法在進(jìn)行文本特征選擇時(shí)的收斂時(shí)間對(duì)比結(jié)果如圖6所示.時(shí)間越短說(shuō)明算法運(yùn)行的速度越快,3種算法在5個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試的結(jié)果表明,在進(jìn)行特征選擇過(guò)程中,相比其他傳統(tǒng)的遺傳和粒子群優(yōu)化算法,二進(jìn)制蜉蝣算法運(yùn)行時(shí)間短,運(yùn)行速度較快.此外,在特征選擇時(shí),算法的運(yùn)行時(shí)間長(zhǎng)短與文本的特征數(shù)目和文檔數(shù)量有關(guān),文檔數(shù)目越多,特征越多,進(jìn)行特征選擇的時(shí)間越長(zhǎng).

表4 不同算法精度的對(duì)比

圖6 不同算法收斂時(shí)間的對(duì)比Fig.6 Comparison of convergence time of different algorithms

綜上所述,針對(duì)文本冗余特征導(dǎo)致聚類精度較低的問(wèn)題,本文提出了一種基于二進(jìn)制蜉蝣優(yōu)化的特征選擇算法(MOMA).首先對(duì)文本進(jìn)行分詞、去停用詞以及計(jì)算文本權(quán)重構(gòu)造向量空間模型; 然后改進(jìn)蜉蝣位置更新和交叉變異策略,并結(jié)合特征模型選出優(yōu)質(zhì)特征,將其輸入到K-means++算法中; 最后利用5個(gè)公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明,本文提出的二進(jìn)制蜉蝣優(yōu)化的特征選擇算法能有效選取信息化特征,大幅度縮減特征維度,聚類效率較好.