基于改進(jìn)灰狼優(yōu)化的文本聚類多階段特征選擇算法

劉泓鑠 王詩瑤 周靈鴿 張建鋒

(西北農(nóng)林科技大學(xué)信息工程學(xué)院 陜西 楊凌 712100)

0 引 言

文本聚類是大數(shù)據(jù)分析的重要手段,廣泛應(yīng)用于主題劃分、網(wǎng)絡(luò)輿情分析、經(jīng)濟(jì)預(yù)測和情感分析等領(lǐng)域[1]。文本聚類的效果與文本特征選擇結(jié)果密切相關(guān)。而通常預(yù)處理后的初始文本特征集合具有高維度和稀疏性特點(diǎn),因此,如何對(duì)文本進(jìn)行特征選擇和特征提取,降低特征維度和移除冗余特征,得到最優(yōu)特征子集成為直接關(guān)系文本聚類效果的關(guān)鍵問題[2]。

目前,文本特征選擇主要有三類方法:過濾法、封裝法和混合法。過濾法是一種統(tǒng)計(jì)分析方法,與具體分類算法無關(guān),主要根據(jù)某一種數(shù)據(jù)特性對(duì)所選特征進(jìn)行排序,判斷特征優(yōu)劣,篩選特征子集。常用過濾法包括:文檔頻率法DF[3]、卡方檢測法CHI[4]、信息增益法IG[5]和互信息法MI[6]。過濾法簡單易行,計(jì)算效率也較高,但經(jīng)過文本聚類后其特征選擇精度較差,特征冗余較多,直接影響了聚類效果。主要體現(xiàn)在:DF可能刪除信息量較大但出現(xiàn)頻率較低的詞,CHI僅關(guān)注詞條是否出現(xiàn)但忽略了詞頻,IG僅考慮詞條在文本集中的影響,而忽略是否具有分類信息,MI則較多關(guān)注頻詞?？傮w而言,過濾法綜合性能欠佳。比較過濾法,封裝法將特征空間與分類算法密切關(guān)聯(lián),考慮了特征相互關(guān)聯(lián),能有效剔除冗余特征,提高聚類準(zhǔn)確度。不足在于計(jì)算效率低于過濾法。該類方法通常借用智能群體算法提高特征選取時(shí)的搜索效率,如:遺傳算法[7-8]、粒子群算法[9-10]、和聲搜索算法[11-12]、差分進(jìn)化算法[13]、蛙跳算法[14]、螢火蟲算法[15]、蟻群算法[16]和貓群算法[17]等。文獻(xiàn)[7]首先利用詞頻/逆文檔頻計(jì)算詞條權(quán)重,然后利用傳統(tǒng)遺傳算法進(jìn)行文本特征選擇,不僅保證了文本分類準(zhǔn)確度,還降低了特征維度。文獻(xiàn)[8]根據(jù)詞條權(quán)重性因子設(shè)計(jì)了基于遺傳算法的特征選擇算法GAFS,以計(jì)算時(shí)間最小、性能最大為目標(biāo)優(yōu)化特征子集選擇,并用郵件文本測試了性能。文獻(xiàn)[9]通過小生境改進(jìn)了傳統(tǒng)粒子群算法,以增強(qiáng)的粒子搜索性能對(duì)文本特征選擇進(jìn)行進(jìn)化求解,獲得的文本分類效率得到有效提升。文獻(xiàn)[10]提出一種新的基于粒子群優(yōu)化的特征選擇算法PSO-TC。算法利用新的動(dòng)態(tài)慣性權(quán)重策略對(duì)粒子進(jìn)化操作進(jìn)行改進(jìn),而最終的三類文本數(shù)據(jù)集的測試也證明在新的特征選擇策略下生成的聚類在準(zhǔn)確度和效率上均有一定改進(jìn)。文獻(xiàn)[11]通過改進(jìn)和聲搜索過程設(shè)計(jì)了一種自適應(yīng)特征選擇算法,算法利用三種動(dòng)態(tài)策略,包括音調(diào)調(diào)整、限制特征域和內(nèi)存合并率改善傳統(tǒng)和聲搜索過程。最后在多維度數(shù)據(jù)集的測試下驗(yàn)證算法在選擇最優(yōu)特征子集上的有效性。文獻(xiàn)[12]利用傳統(tǒng)過濾法對(duì)特征進(jìn)行初選,然后輸入至二進(jìn)制和聲搜索算法中對(duì)特征優(yōu)選,證實(shí)分類準(zhǔn)確率得到了提高。文獻(xiàn)[13]首先聯(lián)合平均中位值和詞條方差建立相關(guān)特征子集,然后在該特征子集上利用改進(jìn)差分進(jìn)化算法對(duì)特征進(jìn)行二次精選,增強(qiáng)了特征子集的擾動(dòng)性和收斂速度。文獻(xiàn)[14]通過信息增益和卡方檢測對(duì)初始特征初選,然后引入改進(jìn)蛙跳算法建立二次特征優(yōu)選模型,有效排除了噪聲特征干擾。文獻(xiàn)[15]首先根據(jù)文本特征的信息增益值對(duì)所有特征降序排列,然后優(yōu)選排序前列的特征作為螢火蟲算法的初始種群,并利用螢火蟲的捕食過程對(duì)特征做進(jìn)一步選擇,效果明顯好于單純信息增益法和螢火蟲算法。文獻(xiàn)[16]設(shè)計(jì)了基于蟻群算法的文本特征選擇算法,有效實(shí)現(xiàn)了特征降維。文獻(xiàn)[17]通過修正的貓群算法設(shè)計(jì)了文本分類下的特征選擇算法。實(shí)驗(yàn)結(jié)果也證實(shí)利用貓群算法后的聚類明顯優(yōu)于僅使用詞條頻率下的聚類效果。顯然,傳統(tǒng)的特征選擇更多依賴于特征對(duì)于后續(xù)分類的貢獻(xiàn)度,貢獻(xiàn)度越大,越有可能被選擇為有用特征。然而,特征詞之間的聯(lián)系是相對(duì)復(fù)雜的,這樣得到的特征詞的聚類效果肯定存在很多偏差。而在過濾生成特征子集初始解后,再引入智能群體算法對(duì)特征子集做進(jìn)一步評(píng)估和提取,將可以提高聚類效率和降低特征維度。灰狼優(yōu)化算法GWO[18]是一種新型的智能群體算法,其模型更為簡單、參數(shù)依賴較少且尋優(yōu)性能好,研究表明它的尋優(yōu)性能要明顯優(yōu)于以上遺傳算法、粒子群算法、差分進(jìn)化算法和蟻群算法等,近年來得到廣泛研究認(rèn)可。本文將設(shè)計(jì)一種多階段的特征選擇與特征提取算法,在融合不同相關(guān)性特征分值計(jì)算方式的基礎(chǔ)上,先對(duì)文本特征進(jìn)行初選;然后基于余弦相似度對(duì)特征進(jìn)行冗余剔除;在此基礎(chǔ)上,引入改進(jìn)二進(jìn)制灰狼優(yōu)化算法對(duì)上一步的特征子集作特征精煉,得到最優(yōu)特征子集。在多個(gè)文本數(shù)據(jù)集的測試下,驗(yàn)證了本文算法的性能優(yōu)勢。

1 文本特征模型

令集合D包含m個(gè)文檔,表示為D={d1,d2,…,di,…,dm},di表示D中的第i個(gè)文檔,m表示集合中的文檔總量。將預(yù)處理后的文檔i表示為向量di={wi,1,wi,2,…,wi,j,…,wi,n},n表示特征數(shù)量。利用詞頻逆文本頻率指數(shù)TF-IDF計(jì)算文本特征權(quán)重,wi,j表示文檔i中特征j的權(quán)重,且:

wi,j=TF(i,j)×IDF(i,j)

(1)

其中:

(2)

式中:TF(i,j)表示文檔i中特征j的頻率;z(i,j)表示特征j在文檔i中出現(xiàn)的次數(shù),分母表示文檔i中所有特征的出現(xiàn)次數(shù)總和;IDF(i,j)為文檔頻率倒數(shù);m表示文檔集合中的文檔總量;DF(j)表示出現(xiàn)特征j的文檔數(shù)量,加1可確保分母不為0。

計(jì)算特征權(quán)重后,文本文檔集合D中的每個(gè)文檔di(i=1,2,…,m)可表示為其所有特征的向量di={wi,1,wi,2,…,wi,j,…,wi,n}。而含有n個(gè)特征的文本集合D則可表達(dá)以下的向量空間模型:

2 特征選擇與特征融合

獲取初始特征集合后,需要對(duì)特征過濾,得到相關(guān)度高的特征子集。引用兩種方法計(jì)算特征相關(guān)性分值:平均絕對(duì)差MAD和平均中位數(shù)MM。MAD可以較準(zhǔn)確地表征特征對(duì)文檔的類別區(qū)分能力,所選擇的特征具有更好的類別信息。MM則相對(duì)可以選擇具有相關(guān)性的特征。結(jié)合兩種特征選擇方法計(jì)算特征相關(guān)性分值,可以實(shí)現(xiàn)特征選擇的優(yōu)勢互補(bǔ),更準(zhǔn)確地得到相關(guān)特征子集。

MAD是詞條方差TV的簡化形式,通過計(jì)算樣本與均值之差為特征分配相關(guān)性分值。特征j的平均絕對(duì)值定義為:

(6)

MM是傾斜率的簡化形式,通過計(jì)算均值與中位數(shù)間的絕對(duì)差為特征分配相關(guān)性分值。特征j的平均絕對(duì)值定義為:

式中:median(xj)表示特征j的權(quán)重值的中位數(shù)。

為了實(shí)現(xiàn)MAD和MM兩種特征相關(guān)性分值計(jì)算方法的優(yōu)勢,提出將兩種方法的特征選擇子集進(jìn)行融合。D為文本文檔集合,經(jīng)過預(yù)處理步驟后,得到特征集合T,令T={t1,t2,…,tn}代表預(yù)處理后的特征集合。利用MAD計(jì)算集合T中每個(gè)特征的相關(guān)性分值,并對(duì)特征按照相關(guān)性分值作降序排列,選擇前q個(gè)為MAD生成的特征候選子集,表示為FSMAD={t11,t12,…,tq},顯然,q<

利用特征合并U建立新特征子集FSU,即合并特征子集FSMAD和FSMM,表示為:

FSU=FSMAD∪FSMM

(8)

令特征子集FSU包含U個(gè)特征,則U≥q和p。

利用特征交叉I建立新的特征子集FSI,即交叉特征子集FSMAD和FSMM,表示為:

FSI=FSMAD∩FSMM

(9)

令特征子集FSI包含I個(gè)特征,則I≤q和p。

令n′表示特征選擇后的特征子集長度。

算法1說明:步驟1首先根據(jù)MAD或MM(式(5)或式(7))計(jì)算每個(gè)特征的相關(guān)性分值,然后在步驟2根據(jù)相關(guān)性分值對(duì)特征作降序排列。步驟3將兩個(gè)參數(shù)初始為0,CR用于記錄特征相關(guān)性分值的累計(jì)值,sum用于記錄所有特征的相關(guān)性分值之和。步驟4-步驟6計(jì)算當(dāng)前所有特征的相關(guān)性分值之和。步驟7-步驟14則用于依次判斷是否每個(gè)特征會(huì)被選入特征子集中,其中:步驟8計(jì)算更新CR,步驟9判斷CR是否小于等于閾值,若滿足,則在步驟10將該特征加入最后的所選特征子集中;否則,在步驟12退出。遍歷完所有排序后的特征后,步驟15可以根據(jù)兩種不同的特征相關(guān)性分值計(jì)算方法進(jìn)行特征子集的合并和交叉。最終,步驟16返回維度為n′的不同方式生成的相關(guān)性特征子集。

算法1特征選擇與特征融合

輸入:文檔數(shù)量m,初始特征數(shù)量n,閾值Threshold1。

輸出:FSMAD,FSMM,FSU,FSI,特征子集(特征數(shù)為n′)。

1.計(jì)算每個(gè)特征的相關(guān)性分值Relj;

2.按相關(guān)分值對(duì)特征作降序排列;

3.CR=0,sum=0;

4.forj=1 tondo

6.endfor

7.forj=1 tondo

8.CR=CR+Relj/sum;

9.ifCR≤Threshold1then

10.FSMAD/MM=FSMAD/MM+FRElj;

11.else

12.break;

13.endif

14.endfor

15.FSU=FSMAD∪FSMM,FSI=FSMAD∩FSMM;

16.returnFSMAD,FSMM,FSU,FSI,特征量n′

3 特征提取

由于特征之間可能存在相似性,因此,特征選擇階段可能存在冗余特征。特征提取FE用于對(duì)特征選擇階段的特征子集進(jìn)行冗余特征移除。通過兩個(gè)特征向量間角度的余弦值度量特征間的相似性,定義為:

式中:wα和wβ表示兩個(gè)特征向量,〈·〉表示點(diǎn)乘;‖·‖表示歐氏距離。該值度量了兩個(gè)特征度量間的角度,取值范圍為[0,1]。若余弦值為0,表明特征間是正交的;若余弦值為1,表明特征是共線的。

令n″表示特征提取后的特征子集長度。

算法2說明:算法的主要過程是按序依次遍歷所有特征(步驟1-步驟9),根據(jù)式(10)計(jì)算相鄰兩個(gè)特征間的相似性(步驟2),并判斷是否小于等于預(yù)定義的閾值,若滿足,則將前一特征提取至最后的特征子集中(步驟3-步驟4);若當(dāng)前特征是子集中的最后一個(gè)特征,則直接提取至最后的特征子集中(步驟6-步驟7)。最后,步驟10輸出維度為n″的特征子集,作為下一階段的特征精煉基礎(chǔ)。

算法2基于余弦相似性的特征提取FE

輸入:特征子集(特征數(shù)為n′),閾值Threshold2。

輸出:特征子集(特征數(shù)為n″)。

1.forj=1 ton′do

2.s=cossim(Fj,Fj+1) ;

3.if(s≤Threshold2)then

4.FSFE=FSFE∪Fj;

5.endif

6.if((j+1)=n′)then

7.FSFE=FSFE∪Fj+1;

8.endif

9.endfor

10.return特征子集FSFE(特征數(shù)為n″)

4 基于改進(jìn)二進(jìn)制灰狼優(yōu)化的特征精煉

經(jīng)過特征選擇和特征提取的特征過濾步驟后,可以生成初選的文本特征子集。為了進(jìn)一步降低特征維度空間,本文引入IBGWO,在特征提取得到的特征子集基礎(chǔ)上進(jìn)行特征精煉,該步驟屬于封裝。GWO是一種新型的群體智能算法,模擬了自然界中灰狼的等級(jí)制度和捕食行為,通過灰狼群體搜索、包圍及追捕攻擊獵物等過程實(shí)現(xiàn)目標(biāo)搜索。研究表明,GWO在求解問題精度和穩(wěn)定性上優(yōu)于傳統(tǒng)的PSO、GA和DE,已在調(diào)度和規(guī)劃優(yōu)化問題上做了一系列應(yīng)用。

4.1 特征精煉解編碼

利用GWO進(jìn)行特征精煉,即一頭灰狼在搜索空間中的位置信息可視為一種可行解。傳統(tǒng)灰狼優(yōu)化算法是連續(xù)灰狼算法,灰狼位置在搜索空間內(nèi)可任意移動(dòng)。由特征選擇模型可知,特征精煉解將離散分布在二進(jìn)制數(shù)0和1之間,所以,表達(dá)特征精煉可行解的灰狼優(yōu)化算法需轉(zhuǎn)換成二進(jìn)制形式。將一頭狼的位置編碼為表1的二進(jìn)制形式。編碼中上層向量代表特征序號(hào)(維度),下層向量代表灰狼在各維度上的二進(jìn)制位置,搜索空間維度n″對(duì)應(yīng)特征提取后的文本特征數(shù)量,二進(jìn)制向量Xh=(xh,1,xh,2,…,xh,n″),若xh,j=1,則表明灰狼h位置所代表的特征精煉候選解中,特征j選擇為信息化特征;若xh,j=0,則表明灰狼h位置所代表的特征精煉候選解中,特征j不被選擇定信息化特征,不包括在最優(yōu)特征子集中。

表1 特征精煉解編碼結(jié)構(gòu)

4.2 基于反向?qū)W習(xí)機(jī)制的種群初始化

傳統(tǒng)灰狼優(yōu)化算法隨機(jī)進(jìn)行種群初始化,然后通過優(yōu)良個(gè)體保存策略逐步迭代,接近全局最優(yōu),改善種群個(gè)體,其搜索過程在滿足預(yù)定義終止條件時(shí)結(jié)束。由于對(duì)全局最優(yōu)沒有任何先驗(yàn)知識(shí),初始種群應(yīng)盡可能均勻分布于搜索空間。算法的收斂速度與初始種群與最優(yōu)解間的距離直接相關(guān)。若隨機(jī)初始種群本身離全局最優(yōu)距離較遠(yuǎn),灰狼尋優(yōu)可能無法完成。研究表明,接近一半的隨機(jī)初始種群個(gè)體比較其反向解距離最優(yōu)解更遠(yuǎn)。反向?qū)W習(xí)機(jī)制[19]可以通過同步考慮當(dāng)前解及其反向解改善候選解的質(zhì)量,并加快算法的收斂速度。因此,可將隨機(jī)初始解及其反向解均考慮在初始種群中。以下對(duì)反向?qū)W習(xí)機(jī)制的概念作說明。

定義1反向數(shù)。令x為區(qū)間[l,u]內(nèi)的實(shí)數(shù),x∈[l,u],其對(duì)立數(shù)x′為:

x′=u+l-x

(11)

基于反向?qū)W習(xí)的灰狼種群初始化步驟如算法3所示。

算法3反向?qū)W習(xí)機(jī)制的種群初始化

輸入:種群規(guī)模S。

輸出:規(guī)模為S的灰狼種群X。

1.初始化規(guī)模為S的隨機(jī)灰狼種群X

2.fori=1 toSdo

3.forj=1 toddo

4.endfor

5.endfor

6.X″=X∪X′

7.計(jì)算灰狼適應(yīng)度;

8.根據(jù)適應(yīng)度對(duì)種群X″作降序排列;

9.X=top({X″}/2);

10.returnX

算法3說明:步驟1首先隨機(jī)生成規(guī)模為S的灰狼個(gè)體位置,步驟2-步驟5在所有灰狼個(gè)體的所有位置維度上計(jì)算其反向點(diǎn),然后在步驟6融合原始初始種群和由反向點(diǎn)組成的種群,形成規(guī)模為2S的灰狼種群結(jié)構(gòu)X″。步驟7根據(jù)式(12)計(jì)算當(dāng)前種群所有個(gè)體的適應(yīng)度,然后在步驟8根據(jù)適應(yīng)度對(duì)X″中的灰狼個(gè)體位置作降序排列,并在步驟9選取排序前S的灰狼種群X作為最終初始種群,最后在步驟10返回新生成的初始種群。

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

適應(yīng)度函數(shù)用于評(píng)估灰狼位置代表的特征精煉解的質(zhì)量。特征精煉應(yīng)盡可能選取適應(yīng)度更優(yōu)的灰狼個(gè)體保留至下一種群世代中。對(duì)于文本特征而言,其重要程度不僅與其在文檔中出現(xiàn)的次數(shù)相關(guān),還與特征在文檔中出現(xiàn)的頻率相關(guān)。因此,將特征的累計(jì)詞頻與文檔頻率作加權(quán)計(jì)算特征精煉解的適應(yīng)度[13],灰狼個(gè)體h的適應(yīng)度計(jì)算為:

式中:σ和γ表示權(quán)重因子,分別用于表示特征的累計(jì)詞頻和文檔頻率對(duì)特征精煉解的偏好程度,σ、γ∈[0,1],且σ+γ=1;DFj表示特征j的文檔頻率;∑TF(i,j)表示特征j的累積詞頻。同時(shí):

DFj=DF(j)/m

(14)

4.4 解的更新

隨著灰狼個(gè)體在搜索空間內(nèi)的捕獵行為的進(jìn)行,會(huì)導(dǎo)致灰狼位置發(fā)生變化,即代表相應(yīng)的特征精煉解會(huì)更新。對(duì)于二進(jìn)制灰狼優(yōu)化算法而言,利用S型函數(shù)可將連續(xù)位置映射為二進(jìn)制位置,具體轉(zhuǎn)換函數(shù)為:

式中:x1,j、x2,j和x3,j分別代表灰狼個(gè)體h與當(dāng)前的α狼、β狼和δ狼之間的距離;xh,j(t+1)表示迭代t+1時(shí)灰狼個(gè)體h的位置向量中第j維的二進(jìn)制位置更新,代表灰狼個(gè)體h是否選擇特征j為信息化特征;rand表示[0,1]內(nèi)的隨機(jī)生成數(shù)。函數(shù)sigmoid(x)定義為:

x1,j、x2,j、x3,j計(jì)算方式如下:

x1,j=|xα,j-A1·Dα|

(17)

x2,j=|xβ,j-A2·Dβ|

(18)

x3,j=|xδ,j-A3·Dδ|

(19)

式中:xα,j、xβ,j和xδ,j分別表示當(dāng)前灰狼種群中適應(yīng)度最優(yōu)的三頭狼α狼、β狼和δ狼所代表的特征精煉解中,特征j是否選擇為信息化特征。

系數(shù)A計(jì)算方式如下:

A=2a·r1-a

(20)

式中:r1表示[0,1]內(nèi)的隨機(jī)生成值;a表示收斂系數(shù)。a定義為:

式中:Tmax表示最大迭代次數(shù)。

Dα、Dβ和Dδ分別代表灰狼個(gè)體與α狼、β狼和δ狼之間的距離,計(jì)算方式為:

Dα=|C1·Xα-X|

(22)

Dβ=|C2·Xβ-X|

(23)

Dδ=|C3·Xδ-X|

(24)

式中:Xα、Xβ和Xδ分別代表α狼、β狼和δ狼的當(dāng)前位置;X表示灰狼個(gè)體的當(dāng)前位置。系數(shù)C的計(jì)算方式為:

C=2r2

(25)

式中:r2表示[0,1]內(nèi)的隨機(jī)生成值。

4.5 非線性收斂系數(shù)更新機(jī)制

由灰狼優(yōu)化模型可知,灰狼對(duì)獵物的包圍由收斂系數(shù)a決定,該系數(shù)決定灰狼的尋優(yōu)能力,即局部開發(fā)與全局勘探能力。由收斂系數(shù)a的計(jì)算公式可知,a值變化呈線性遞減趨勢。對(duì)于灰狼優(yōu)化算法而言,迭代初期,較大a值可以增大灰狼搜索步長,提高全局勘探能力,避免尋優(yōu)過程過快收斂和早熟;迭代后期,較小a值可以減小灰狼搜索步長,提高局部開發(fā)能力,加快算法收斂。然而,兩種搜索類型并不是完全線性切換的,收斂系數(shù)的線性遞減并不能實(shí)際體現(xiàn)灰狼的復(fù)雜搜索過程,尤其出現(xiàn)多峰值情形時(shí),易于陷入局部最優(yōu)。本文將收斂系數(shù)a的變化改進(jìn)為非線性遞減形式,表示為:

式中:aini為收斂系數(shù)初值,通常為2;Tmax為最大迭代數(shù),t為當(dāng)前迭代數(shù)。式(26)表明,收斂系數(shù)a呈非線性衰減。迭代初期,衰減速率較慢,可以有效進(jìn)行全局勘探;迭代末期衰減速率加快,可以更好進(jìn)行局部開發(fā)。非線性衰減的收斂系數(shù)也因此更好地均衡了灰狼種群的全局勘探和局部開發(fā)能力。

4.6 精英反向?qū)W習(xí)機(jī)制

由灰狼優(yōu)化過程可知,搜索過程由當(dāng)前灰狼種群中適應(yīng)度最優(yōu)的三頭灰狼α狼、β狼和δ狼引領(lǐng)。在搜索過程末期,所有灰狼向決策層的三個(gè)頭狼附近區(qū)域逼近,此時(shí)缺失群體多樣性,收斂速度明顯變慢或停滯,最終會(huì)陷入局部最優(yōu)。算法繼續(xù)引入反向?qū)W習(xí)機(jī)制,在α狼、β狼和δ狼的選取上同步引入其精英反向點(diǎn),擴(kuò)大灰狼的搜索范圍,勘探新搜索區(qū)域。

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

利用MATLAB平臺(tái)編寫測試程序,硬件環(huán)境為Windows 10操作系統(tǒng),Core i7處理器以及4 GB內(nèi)存容量。所有文本特征選擇算法以Java平臺(tái)編寫程序,最后的文本聚類測試則以K均值算法在MATLAB平臺(tái)進(jìn)行。

5.1 測試數(shù)據(jù)集

引入三種不同的經(jīng)典基準(zhǔn)數(shù)據(jù)集進(jìn)行性能測試:Reuters- 21578[20]、Classic4[21]和WebKB[22]。三種數(shù)據(jù)集預(yù)定義劃分為若干分類,分類信息在聚類過程中是未知的。Reuters- 21578數(shù)據(jù)集是路透社新聞專線發(fā)布的新聞集,包括21 578個(gè)文檔,非均勻地分布于135個(gè)主題間。本文隨機(jī)選取屬于8個(gè)不同分類中的1 339個(gè)文檔進(jìn)行聚類分析。Classic4數(shù)據(jù)集包括7 095個(gè)文檔,每個(gè)文檔屬于CACM、CRAM、CISI和MED四種分類中的一種。本文隨機(jī)選取2 000個(gè)文檔(一種分類500個(gè)文檔)進(jìn)行聚類分析。WebKB數(shù)據(jù)集即全球知識(shí)庫,包括來自于四個(gè)學(xué)術(shù)領(lǐng)域內(nèi)的8 282個(gè)Web頁面,初始擁有7種分類,最后只有課程、學(xué)院、學(xué)生和項(xiàng)目四個(gè)分類被有效利用。本文從中隨機(jī)選取2 803個(gè)文檔進(jìn)行聚類分析。從初始特征空間中隨機(jī)抽取文檔子集并不會(huì)轉(zhuǎn)變數(shù)據(jù)集的屬性,也不會(huì)影響算法的計(jì)算需求。三種數(shù)據(jù)集的詳細(xì)統(tǒng)計(jì)如表2所示,可見,所有數(shù)據(jù)集擁有完全不同的文檔數(shù)量、特征、偏斜度和稀疏性。

5.2 性能指標(biāo)

為了驗(yàn)證特征選擇算法的性能,利用K均值算法根據(jù)特征選擇算法求解的最優(yōu)特征子集進(jìn)行文本聚類,并以聚類性能分析特征選擇性能。引入以下三個(gè)性能度量指標(biāo):

準(zhǔn)確率P表明文本聚類結(jié)果的準(zhǔn)確性,衡量查準(zhǔn)率。P越大,聚類準(zhǔn)確性越高,定義為:

式中:TP表示聚類解中被正確聚類的文檔數(shù)量;FP表示錯(cuò)誤聚類的文檔數(shù)量。

召回率R表明文本聚類結(jié)果的完整性,即查全率。R越大,完整性越好,定義為:

式中:FN表示不該分開的文檔被錯(cuò)誤分開的文檔數(shù)量。

F1度量:綜合評(píng)定準(zhǔn)確率和召回率。F1值越大,聚類性能越優(yōu),定義為:

5.3 測試算法及參數(shù)

本文設(shè)計(jì)的最優(yōu)文本特征子集生成分成四個(gè)階段:特征選擇-特征合并/交叉-特征提取-特征精煉。令預(yù)處理后的文本特征規(guī)模為n。首先,特征選擇階段中,根據(jù)MAD或MM生成相關(guān)性特征子集,再對(duì)兩類特征子集進(jìn)行合并U或交叉I,得到規(guī)模為n′的特征子集,n′

表3 測試算法

除表3的算法外,性能對(duì)比算法選擇基于遺傳算法的特征選擇算法GAFS[8]、基于二進(jìn)制粒子群算法的特征選擇算法BPSOFS[10]和基于改進(jìn)差分進(jìn)化的特征選擇算法IDEFS[13]進(jìn)行對(duì)比分析。對(duì)于三種智能群體算法,種群規(guī)模設(shè)置為400,算法最大迭代次數(shù)設(shè)置為500,遺傳交叉概率設(shè)為0.8,遺傳變異概率設(shè)為0.2,粒子慣性權(quán)重最小值為0.4,最大值設(shè)為0.9,兩個(gè)學(xué)習(xí)因子均設(shè)置為0.5。灰狼算法中的收斂系數(shù)初值設(shè)為2,系數(shù)A、C均隨機(jī)生成,因此無須提前配置。

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

實(shí)驗(yàn)1確定IBGWO中適應(yīng)度函數(shù)的權(quán)重因子σ和γ。由于σ+γ=1,可以僅以σ為參考,確定其參數(shù)取值。圖1為改變?chǔ)胰≈禃r(shí)利用Reuters- 21578數(shù)據(jù)集進(jìn)行聚類測試得到的準(zhǔn)確率均值情況。σ調(diào)節(jié)步長為0.1,當(dāng)增加σ取值時(shí),則γ相應(yīng)遞減。從結(jié)果可知,聚類準(zhǔn)確性整體是隨著σ取值先上升后下降的,這說明適應(yīng)度函數(shù)中的特征累計(jì)詞頻與文檔頻率兩種要素會(huì)對(duì)聚類準(zhǔn)確率產(chǎn)生影響,并且兩個(gè)因素是相互制約的。在σ取值為0.4時(shí),聚類準(zhǔn)確率最佳。因此,后續(xù)實(shí)驗(yàn)測試中,將σ取值0.4、γ取值0.6進(jìn)行實(shí)驗(yàn)分析。進(jìn)一步需要說明的是,0.4/0.6的權(quán)重因子取值不一定是聚類準(zhǔn)確率達(dá)到最高的取值組合,由于兩個(gè)權(quán)重因子取值是可以在區(qū)間[0,1]內(nèi)任意取值的,所以并不能確定其聚類準(zhǔn)確率最大時(shí)的取值組合,但這并不會(huì)對(duì)后續(xù)實(shí)驗(yàn)分析產(chǎn)生不利影響。

圖1 適應(yīng)度函數(shù)權(quán)重因子的選取

實(shí)驗(yàn)2確定IBGWO在原始二進(jìn)制灰狼優(yōu)化算法BGWO基礎(chǔ)上改進(jìn)措施的有效性。圖2為改進(jìn)二進(jìn)制灰狼優(yōu)化算法與傳統(tǒng)二進(jìn)制灰狼優(yōu)化算法在適應(yīng)度方面的比較?？梢钥吹?改進(jìn)二進(jìn)制灰狼優(yōu)化算法可以有效提高灰狼個(gè)體所表征的特征精煉解的適應(yīng)度值,這說明IBGWO中基于反向?qū)W習(xí)機(jī)制的初始種群生成方法可以優(yōu)化初始種群結(jié)構(gòu),提升種群多樣性。而非線性收斂系數(shù)衰減和精英反向?qū)W習(xí)機(jī)制,則可以有效提升灰狼算法的尋優(yōu)性能,更加有助于灰狼個(gè)體的尋優(yōu)收斂性,并最終得到最優(yōu)文本特征子集。

圖2 IBGWO的性能

實(shí)驗(yàn)3觀察算法在特征降維方面的有效性。圖3為所有算法在三種測試數(shù)據(jù)集中得到的最優(yōu)特征子集維度,圖4相應(yīng)給出了算法在數(shù)據(jù)集原始特征規(guī)模下生成最優(yōu)特征子集的降維比例情況。綜合結(jié)果可以看到,傳統(tǒng)過濾式特征選擇方法MM和MAD對(duì)于特征空間維度的降低還是比較有限的,基本僅能降低全部初始特征空間的一半左右。融合特征合并和合并機(jī)制后,得到的特征規(guī)模并沒有呈現(xiàn)大幅度增加或降低的趨勢,這說明兩種計(jì)算特征相關(guān)性分值的特征選擇方法會(huì)產(chǎn)生很多交集,所選擇的特征具有很大的相似性。而在引入余弦相似性的特征提取機(jī)制后,對(duì)相似性較高的冗余特征作了剔除,較大程度降低了特征規(guī)模。而引入改進(jìn)二進(jìn)制灰狼優(yōu)化的多階段特征精煉后,特征子集維度進(jìn)一步有所減小,這說明本文所設(shè)計(jì)的特征選擇-特征提取-特征精煉的多階段降維機(jī)制是有效可行的,在降低相似性特征比例、提取信息化特征方面具有很好的優(yōu)勢。相比較GAFS、BPSOFS和IDEFS三種對(duì)比特征選擇算法,本文的IBGWO同樣具有進(jìn)一步特征降維的優(yōu)勢,其中原因除了灰狼優(yōu)化算法模型更為簡單、參數(shù)依賴較少且尋優(yōu)性能好之外,還在于本文灰狼優(yōu)化中引入反向?qū)W習(xí)機(jī)制對(duì)灰狼種群的隨機(jī)初始化作了改進(jìn),以及非線性收斂系數(shù)衰減模式和精英反向?qū)W習(xí)機(jī)制,最大限度地有效提升了灰狼算法的尋優(yōu)性能,得到最優(yōu)文本特征子集。

圖3 最優(yōu)特征子集規(guī)模

圖4 特征降維比例

實(shí)驗(yàn)4進(jìn)行系統(tǒng)的文本聚類性能分析。表4為11種算法在三個(gè)測試數(shù)據(jù)集上得到的聚類精確率、召回率和F1度量指標(biāo)上的性能表現(xiàn)。綜合結(jié)果可以看到,傳統(tǒng)的過濾式特征選擇方法MM和MAD對(duì)于特征空間維度降低比較有限,導(dǎo)致其冗余特征過多、噪聲太大、信息化特征子集的提煉準(zhǔn)確度過低,進(jìn)而導(dǎo)致其聚類準(zhǔn)確性較差。其他智能群體算法在進(jìn)一步改進(jìn)特征選擇策略后,可以明顯地提升聚類性能。相比較遺傳GAFS、二進(jìn)制粒子群BPSOFS、改進(jìn)差分進(jìn)化IDEFS三種對(duì)比特征選擇算法,本文的改進(jìn)二進(jìn)制灰狼優(yōu)化算法的多階段特征選擇機(jī)制在多數(shù)測試數(shù)據(jù)集均可以進(jìn)一步改善聚類效果,說明引入的余弦相似性的冗余剔除機(jī)制可以有效分離出非信息化特征。而在二進(jìn)制灰狼優(yōu)化算法上進(jìn)一步設(shè)計(jì)的反向?qū)W習(xí)機(jī)制對(duì)灰狼種群的隨機(jī)初始化所作改進(jìn),以及非線性的收斂系數(shù)衰減模式和精英反向?qū)W習(xí)機(jī)制,最大程度地提升了灰狼算法的尋優(yōu)性能,得到最優(yōu)文本特征子集,不僅有效降低了特征維度,而且極大改善了文本聚類準(zhǔn)確性。

表4 聚類性能對(duì)比

6 結(jié) 語

為了降低特征空間維度,提高文本聚類準(zhǔn)確度,設(shè)計(jì)一種多階段的特征選擇與特征提取算法,在融合不同相關(guān)性特征分值計(jì)算方式的基礎(chǔ)上,先對(duì)特征進(jìn)行初選;然后基于余弦相似度對(duì)特征進(jìn)行冗余剔除,在此基礎(chǔ)上,引入改進(jìn)二進(jìn)制灰狼優(yōu)化算法對(duì)上一步的特征子集作特征精煉,得到最優(yōu)特征子集。在多個(gè)文本數(shù)據(jù)集的測試下,驗(yàn)證了本文算法的性能優(yōu)勢。進(jìn)一步的研究可集中于嘗試?yán)闷渌^濾式特征初選方式,并將其初選特征子集作為智能群體算法的初始種群結(jié)構(gòu),再進(jìn)行特征提取和特征精煉,實(shí)現(xiàn)準(zhǔn)確度更高的特征選擇以及性能更優(yōu)的文本聚類。