基于二進(jìn)制灰狼優(yōu)化的特征選擇及文本聚類

王 琛，董永權(quán)

(1.江蘇建筑職業(yè)技術(shù)學(xué)院 信電工程學(xué)院，江蘇 徐州 221116；2.江蘇師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

0 引 言

文本聚類作為最適宜于將大量文檔集合劃分為預(yù)定義數(shù)量聚類的方法已經(jīng)得到廣泛研究[1]，被應(yīng)用在信息挖掘的諸多領(lǐng)域。矢量空間模型VSM作為文本數(shù)據(jù)挖掘領(lǐng)域最常用模型，可將文本特征表示為詞條權(quán)重矢量，且每個詞條權(quán)重為一維空間。因此，文本聚類性能極大地受到維度空間和非信息化特征的影響[2]。文本包括信息化和非信息化特征，非信息化特征一般為噪聲、不相關(guān)冗余特征[3,4]。無監(jiān)督特征選擇可用于尋找信息化特征子集。傳統(tǒng)特征選擇方法主要包括文檔頻率DF、交互信息MI、信息增益IG、卡方檢驗(yàn)CHI，但這類方法缺乏數(shù)學(xué)模型較難改進(jìn)，特征子集精度較低。而特征選擇的目標(biāo)有以下兩點(diǎn)：一是如何基于特征選擇優(yōu)化后期文本聚類的性能，二是如何盡可能降低非信息化特征數(shù)量，提高文本聚類效率[5]。

提出一種基于二進(jìn)制灰狼優(yōu)化的特征選擇和文本聚類方法。算法將特征選擇建模為灰狼的覓食過程，通過灰狼位置的更新最后收斂在最優(yōu)位置代表的特征選擇最優(yōu)解上。為了兼顧不同灰狼個體適應(yīng)度評估方法的優(yōu)點(diǎn)，引入詞條方差和平均絕對差兩種適應(yīng)度評估方法，進(jìn)而可以在該階段得到兩種不同的信息化特征子集。引入特征歸并對兩類特征子集進(jìn)行合并與交叉，進(jìn)一步得出最優(yōu)特征子集。最后，設(shè)計(jì)多目標(biāo)優(yōu)化K均值聚類算法對相應(yīng)文本進(jìn)行聚類，得到最優(yōu)文檔聚類結(jié)果。通過實(shí)驗(yàn)測試和評估指標(biāo)對比，驗(yàn)證了算法的可行性和有效性。

1 相關(guān)研究

已有特征選擇方法可以有3類：過濾法、包裝法和混合法。過濾法未考慮與學(xué)習(xí)算法的相互作用，通過得知特征相關(guān)性分值選擇特征子集，是一種數(shù)學(xué)統(tǒng)計(jì)分析法。包裝法利用搜索策略決定特征子集，并基于學(xué)習(xí)算法得到特征子集?；旌戏▌t兼顧兩種方法的優(yōu)勢尋找更加準(zhǔn)確的信息化特征子集[6]。

元啟發(fā)式算法可廣泛用于最優(yōu)化問題求解，且已被用在文本挖掘領(lǐng)域中的特征選擇求解[7,8]，主要包括群體智能方法，如和聲搜索算法、遺傳算法、粒子群算法、蟻群算法和貓群算法等。這類方法主要利用先前迭代中的種群信息改進(jìn)已有問題解。文獻(xiàn)[9]基于詞條權(quán)重策略的重要性因子提出基于遺傳算法的特征選擇算法GA-TC，算法以最小計(jì)算時間和最大性能為目標(biāo)選擇最優(yōu)特征子集，并利用郵件文本對特征選擇性能進(jìn)行了測試。文獻(xiàn)[10]為了降低特征空間維度，設(shè)計(jì)了兩階段特征選擇算法。階段一利用詞條方差和平均中位數(shù)進(jìn)行初步特征選擇，階段二利用改進(jìn)差分進(jìn)化算法進(jìn)一步做特征封裝，得到最優(yōu)特征子集。文獻(xiàn)[11]先利用信息增益作特征初選，再利用螢火蟲算法進(jìn)一步搜索最優(yōu)特征子集。文獻(xiàn)[12]聯(lián)合利用卡方檢測和信息增益進(jìn)行特征初選，再以二進(jìn)制和聲搜索對預(yù)選特征進(jìn)化優(yōu)選，特征準(zhǔn)確率得到了提高。文獻(xiàn)[13]通過改進(jìn)和聲搜索設(shè)計(jì)了自適應(yīng)特征選擇算法，算法利用音調(diào)調(diào)整、限制特征域和內(nèi)存合并改善傳統(tǒng)和聲搜索過程。文獻(xiàn)[14]提出基于粒子群優(yōu)化的特征選擇算法PSO-TC。算法利用新的動態(tài)慣性權(quán)重策略對粒子進(jìn)化操作進(jìn)行改進(jìn)，特征選擇策略下生成的文本聚類在準(zhǔn)確度和效率上均有一定效果。文獻(xiàn)[15]通過修正的貓群算法設(shè)計(jì)了特征選擇算法，實(shí)驗(yàn)結(jié)果也證實(shí)利用貓群算法后的聚類明顯優(yōu)于僅使用詞條頻率的聚類。可以肯定的是，智能群體算法在求解特征選擇上具有很好的可行性，但以上所涉及的早期智能群體算法在尋優(yōu)過程中都有局限性，或模型復(fù)雜，或依賴的前期參數(shù)較多等；即使結(jié)合傳統(tǒng)特征選擇的過濾法，也未考慮不同方法的優(yōu)勢。灰狼算法[16]是一種新型智能群體算法，特點(diǎn)是模型簡單、設(shè)置參數(shù)少且尋優(yōu)性能好，研究表明其尋優(yōu)性能要明顯優(yōu)于GA、PSO和和聲搜索等傳統(tǒng)算法，已廣泛應(yīng)用在路徑規(guī)劃、風(fēng)險防控、電力系統(tǒng)調(diào)度等領(lǐng)域。本文將應(yīng)用灰狼優(yōu)化算法進(jìn)行特征選擇，并將傳統(tǒng)連續(xù)型灰狼優(yōu)化算法改進(jìn)為可適用于文本特征選擇領(lǐng)域的二進(jìn)制灰狼優(yōu)化算法，通過灰狼種群在覓食過程中的位置更新尋找最優(yōu)特征子集。

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

為了更好地實(shí)現(xiàn)文本數(shù)據(jù)的聚類分析，本文將設(shè)計(jì)在文本特征選擇基礎(chǔ)上的聚類算法，通過特征選擇及相應(yīng)特征處理，獲取文本中的最優(yōu)信息化特征，盡可能消除非信息化特征，降低文本特征維度，在擁有更低維度空間的信息化特征最優(yōu)子集的基礎(chǔ)上進(jìn)行文本聚類分析。具體算法的實(shí)施過程有以下4個階段：第一個階段對文本數(shù)據(jù)進(jìn)行預(yù)處理并表達(dá)為矢量空間模型VSM；第二個階段利用二進(jìn)制灰狼優(yōu)化算法對文本特征進(jìn)行選擇，得到初選的信息化特征子集；第三個階段對第二個階段中不同特征相關(guān)分值計(jì)算方法得到的初選特征子集進(jìn)行合并與交叉操作，進(jìn)一步得到新的最優(yōu)特征子集；第四階段在第三階段生成的特征子集的基礎(chǔ)上，利用多目標(biāo)優(yōu)化的K均值算法對文本進(jìn)行聚類，得出最優(yōu)文檔聚類結(jié)果。

2.1 基于矢量空間模型VSM的文本數(shù)據(jù)表達(dá)

獲取文本信息后，需要對文本進(jìn)行預(yù)處理，包括對詞語切分、移除文本中的終止詞、提取詞干以及計(jì)算詞條權(quán)重值，將其表達(dá)為矢量空間模型VSM[17]。詞語切分過程是將原始文本信息分割為獨(dú)立詞條(也稱為令牌)的過程，同時需要移除空格符號信息；終止詞移除是將文本中出現(xiàn)頻率較高但對文本含義表達(dá)權(quán)重較小的詞匯進(jìn)行移除，該類詞匯目前總計(jì)約有571個；提取詞干的目標(biāo)是通過移除詞匯的前綴和后綴部分將其轉(zhuǎn)換為相同詞根的過程，而相同詞根即可定義為文本的一個特征，該部分工作可以通過通用提詞器進(jìn)行操作；詞條權(quán)重計(jì)算是文本信息預(yù)處理最重要的過程，該過程的目標(biāo)是計(jì)算特征詞條在文檔中的權(quán)重值。顯然，若特征詞條在不同文檔中出現(xiàn)頻率較高，那么該詞條可以更好區(qū)分文檔本質(zhì)內(nèi)容，該詞條也應(yīng)擁有更高的權(quán)重值。目前應(yīng)用的主要詞條權(quán)重計(jì)算方式為詞頻逆文本頻率指數(shù)TF-IDF方法，具體模型如下：

令集合D包含n個文檔，表示為D={d1,d2,…,di,…,dn}，其中，di表示集合D中的第i個文檔，n表示集合中的文檔總量。利用詞頻逆文本頻率指數(shù)TF-IDF方法，文檔i可表示為矢量di={wi,1,wi,2,…,wi,j,…,wi,t}，文檔長度為t，即所含詞條數(shù)量，wi,j為通過TF-IDF計(jì)算的文檔i中詞條j的權(quán)重值，且

(1)

式中：TF(i,j)表示文檔i中詞條j的頻率，n表示文檔集合的文檔總量，DF(j)為包含詞條j的文檔數(shù)量，IDF(i,j)為文檔頻率倒數(shù)。通過矢量空間模型VSM，可將整個文檔集合D表示為

(2)

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

灰狼在食物鏈中屬于頂級捕食者，且擁有嚴(yán)格的社會等級層次。灰狼優(yōu)化算法基于灰狼的社會分級進(jìn)行建模。社會分級頂端為領(lǐng)導(dǎo)者，稱為α狼，負(fù)責(zé)捕獵決策，處于統(tǒng)治地位。次層為β狼，地位僅次于α狼，負(fù)責(zé)協(xié)助α狼的決策制定。第三層為δ狼，服從于α狼和β狼。最低層為ω狼。通常，由于獵物所代表的最優(yōu)解位置是無從準(zhǔn)確知曉的，因此會將α狼視為侯選的最優(yōu)解。而當(dāng)前狼群中適應(yīng)度最高的個體即可視為α狼，α狼會引導(dǎo)其它狼群個體向食物源的方向搜索，也會按照α狼、β狼和δ狼的位置變化改變自身的位置，直到完成狩獵過程。

2.2.1 特征選擇模型

令t為預(yù)處理后原始文本的唯一特征數(shù)量，文本特征選擇的目標(biāo)是在維持原始特征較高準(zhǔn)確性基礎(chǔ)上，尋找規(guī)模為m的最優(yōu)文本特征子集，m

2.2.2 特征選擇解編碼

利用灰狼優(yōu)化算法求解特征選擇問題，即一頭灰狼在搜索空間中的位置信息可視為一種特征選擇可行解。由于傳統(tǒng)灰狼優(yōu)化算法是連續(xù)灰狼算法，即灰狼位置可以搜索空間內(nèi)任意點(diǎn)移動，由前文特征選擇模型可知，特征選擇解將離散分布在二進(jìn)制數(shù)0和1之間，所以，表達(dá)特征選擇可行解的灰狼算法需要轉(zhuǎn)換成二進(jìn)制形式。

令一頭灰狼h的位置表示為矩陣Xh

(3)

2.2.3 解的更新機(jī)制

隨著灰狼個體在搜索空間內(nèi)的捕獵行為的進(jìn)行，會導(dǎo)致灰狼位置發(fā)生變化，即特征選擇解會發(fā)生更新。二進(jìn)制灰狼優(yōu)化過程的位置更新方式通過以下轉(zhuǎn)換函數(shù)完成

(4)

(5)

(6)

(7)

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

A=2a·r1-a

(8)

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

a=2-2×t/Tmax

(9)

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

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

Dα=|C1·Xα-X|

(10)

Dβ=|C2·Xβ-X|

(11)

Dδ=|C3·Xδ-X|

(12)

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

C=2r2

(13)

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

函數(shù)sigmoid(x)定義為

(14)

基于二進(jìn)制灰狼優(yōu)化的特征選擇過程如算法1所示。

算法1：基于二進(jìn)制灰狼優(yōu)化算法的特征選擇算法GWO-TC

(1)initialize randomly the grey wolf population anda,AandC

(2)compute the fitness of each grey wolf individual

(3)setXαas the best grey wolf

(4)setXβas the second best grey wolf

(5)setXδas the third best grey wolf

(6)whilet

(7)foreach grey wolf

(8) update the position of the current grey wolf by Equ.(4)

(9)endfor

(10)update parametera,AandC

(11)compute the fitness of all grey individuals

(12)updateXα,XβandXδof the grey wolf population

(13)t=t+1

(14)endwhile

(15)returnXαas the best feature selection solution

算法過程詳細(xì)說明：步驟(1)根據(jù)式(3)對灰狼種群位置和參數(shù)a、A和C進(jìn)行初始化，步驟(2)根據(jù)適應(yīng)度函數(shù)(即式(15)或式(17))計(jì)算灰狼個體適應(yīng)度值，步驟(3)～步驟(5)根據(jù)灰狼適應(yīng)度值選取適應(yīng)度排序前三的灰狼作為α狼、β狼和δ狼；若當(dāng)前未達(dá)到迭代的最大次數(shù)，步驟(7)～步驟(9)根據(jù)式(4)更新每個灰狼個體的位置信息，此過程中需要計(jì)算灰狼個體與α狼、β狼和δ狼間的距離，并基于3頭狼搜索方向指導(dǎo)其它灰狼個體的搜索過程?；依俏恢酶潞?，步驟(10)重新更新參數(shù)a、A和C，步驟(11)重新計(jì)算所有灰狼個體的適應(yīng)度值，并在步驟(12)重新得到3個頭狼α狼、β狼和δ狼的位置，該過程會重復(fù)直到達(dá)到最大迭代次數(shù)為止，最后在步驟(15)算法將α狼的位置所解碼出的特征選擇解輸出為特征選擇最優(yōu)解。

2.2.4 特征相關(guān)性分值計(jì)算

特征相關(guān)性分值即為評估灰狼位置所代表的特征選擇解的適應(yīng)度[18]。引入兩種特征相關(guān)分值計(jì)算方法：詞條方差法和平均絕對差法。前者具有更好的特征類別區(qū)分能力，但忽略了特征相關(guān)性；后者則可以選擇具有更好相關(guān)性的特征。兩種特征相關(guān)性分值計(jì)算方法將在本文中結(jié)合使用，實(shí)現(xiàn)優(yōu)勢互補(bǔ)。

詞條方差TV通過計(jì)算與均值間的方差分配特征相關(guān)性分值，該方法的出發(fā)點(diǎn)是考慮到所有文檔中非均勻分布的特征比均勻分布特征能更好描述文檔含義。詞條特征的TV值計(jì)算為

(15)

式中：xi,j表示文檔i中特征j的矢量權(quán)重值，ai表示文檔i中所選特征數(shù)量，t為文檔特征總量，x′i表示文檔i的特征權(quán)重均值

(16)

平均絕對差MAD通過計(jì)算與均值間的差分配特征相關(guān)性分值。每個詞條特征的MAD值計(jì)算為

(17)

TV和MAD均可用于評估GWO-TC算法中灰狼個體的適應(yīng)度，即通過兩種計(jì)算方式，可以得到兩種特征選擇解。那么，二進(jìn)制灰狼優(yōu)化算法執(zhí)行特征選擇時可以分為兩種形式，以詞條方差TV評估灰狼適應(yīng)度時命名為GWOTV-TC算法，以平均絕對差MAD評估灰狼適應(yīng)度時命名為GWOMAD-TC算法。

2.3 特征子集歸并

特征子集歸并主要包括特征合并與特征交叉，其目標(biāo)是融合詞條方差TV和平均絕對差MAD兩種特征相關(guān)性評估方法的優(yōu)勢。令D為文檔集，經(jīng)過預(yù)處理后得到特征集合T，令T={t1,t2,…,tf} 代表初始特征集合。令FS1={t11,t12,…,tq} 為GWOTV-TC算法得到的所選特征子集，tq表示該算法所選特征數(shù)量為q，且q<

2.3.1 特征合并

特征合并操作定義為Union。設(shè)FS1為GWOTV-TC算法得到的所選特征子集，包括q個所選特征，F(xiàn)S2為GWOMAD-TC算法得到的所選特征子集，包括l個所選特征。利用特征合并方法建立新的特征子集FS3，即通過合并特征子集FS1和特征子集FS2可以得到，表示為

FS3=FS1∪FS2

(18)

令特征子集FS3包含U個特征，則U≥{q,l}。

2.3.2 特征交叉

特征交叉操作定義為Intersection。設(shè)FS1為GWOTV-TC算法得到的所選特征子集，包括q個所選特征，F(xiàn)S2為GWOMAD-TC算法得到的所選特征子集，包括l個所選特征。利用特征交叉方法建立新的特征子集FS4，即通過特征子集FS1和特征子集FS2的交叉操作可以得到，表示為

FS4=FS1∩FS2

(19)

令特征子集FS4包含I個特征，則I≤{q,l}。

2.3.3 改進(jìn)特征合并

特征合并和特征交叉可以歸并兩種不同評估標(biāo)準(zhǔn)下二進(jìn)制灰狼優(yōu)化算法得到的特征子集。合并方法考慮了兩種標(biāo)準(zhǔn)所生成的所有特征，會增加特征總量。而交叉方法僅僅選擇不同評估標(biāo)準(zhǔn)下的共有特征，會減小特征規(guī)模，會可能導(dǎo)致重要特征丟失?；诖丝紤]，為了得到頂層特征為共有特征，需要進(jìn)一步對特征合并方式進(jìn)行改進(jìn)。具體過程如下：首先，根據(jù)每個特征的相關(guān)性分值對特征進(jìn)行降序排列，構(gòu)建排列后的特征列表；為了從兩個特征列表中選擇高分值特征，在排序靠前的特征(假設(shè)占比為C1)上引入特征合并操作，在剩余特征(假設(shè)占比為C2)上引入特征交叉操作，得到新的特征子集。此時，特征合并可以確保高排序特征不被丟失，而特征交叉則可以確保部分共有特征可以保留。

改進(jìn)特征合并MUnion操作如下：新的特征子集FS5的生成方式為

FS5={C1%FS1∪C1%FS2}∪{C2%FS1∩C2%FS2}

(20)

令特征子集FS3包含MU個特征，則MU≥{q,l}。

2.4 基于多目標(biāo)優(yōu)化的K均值聚類

利用灰狼優(yōu)化的特征選擇算法GWO-TC及相應(yīng)特征子集歸并機(jī)制得到文本特征子集后，本文提出多目標(biāo)K均值算法對文本進(jìn)行聚類分析，通過聚類結(jié)果觀測特征選擇過程對于聚類效果的影響。K均值文本聚類的目標(biāo)是將文檔集合D劃分為K個聚類，每個聚類一個質(zhì)心，表示為C={C1,C2,…,CK}，質(zhì)心Ck表示為詞條權(quán)重矢量，即Ck={c1,c2,…,ct}，t為質(zhì)心長度。

2.4.1 聚類目標(biāo)定義

文本文檔聚類的目標(biāo)是劃分相似文檔到同一聚類，而不相似文檔則在不同聚類中。余弦相似度是度量文檔相似性的一種標(biāo)準(zhǔn)度量方式，定義為

(21)

式(21)表示文檔di與聚類質(zhì)心Ck的余弦相似度。wi,j表示文檔i中詞條j的權(quán)重值，wk,j表示聚類質(zhì)心Ck所代表的文檔k中詞條j的權(quán)重值。若文檔di與質(zhì)心Ck越相似，余弦值接近于1；文檔di與質(zhì)心Ck相似性越差，則余弦值接近于0。

歐氏距離是計(jì)算歐氏空間內(nèi)文檔與聚類質(zhì)心距離的計(jì)算方法。文檔di與聚類質(zhì)心Ck的歐氏距離定義為

(22)

可以看到，歐氏距離取值空間在0至1之間。若文檔與聚類質(zhì)心間的歐氏距離接近于0，則表明該文檔與該聚類質(zhì)心具有較大相似性，可劃分至相應(yīng)聚類中；若文檔與聚類質(zhì)心間的歐氏距離接近于1，則表明該文檔與該聚類質(zhì)心相距較遠(yuǎn)。

余弦相似度衡量文檔與質(zhì)心相似性，歐氏距離度量文檔與質(zhì)心間的距離。本文將相似性和距離均考慮在聚類目標(biāo)函數(shù)中。為文檔選擇聚類質(zhì)心時，應(yīng)盡可能選擇相似度高且距離較近的質(zhì)心。因此，聚類目標(biāo)可設(shè)置為同步優(yōu)化的雙目標(biāo)形式

obj(di,Ck)=b×Cos(di,Ck)+g×(1-Dis(di,Ck))

(23)

式中：Cos(di,Ck)表示余弦相似度，由式(21)計(jì)算，Dis(di,Ck)表示歐氏距離，由式(22)計(jì)算，b表示相似度因子，g表示歐氏距離因子，用于描述聚類過程中對兩個指標(biāo)的偏好，b和g均屬于0至1之間，且b+g=1。由目標(biāo)可知，余弦相似度越大，歐氏距離越小，目標(biāo)函數(shù)值越大。

2.4.2 聚類過程

多目標(biāo)優(yōu)化K均值聚類中，聚類質(zhì)心Ck的計(jì)算方式為

Ck=1/nk∑di∈Ckdi

(24)

式中：di為文檔i，nk為聚類k中文檔的數(shù)量，Ck為聚類k的質(zhì)心，di∈Ck表明屬于聚類k的所有文檔。式(24)表明聚類中所有文檔的矢量權(quán)重和除以聚類內(nèi)的文檔數(shù)量即為該聚類質(zhì)心。

多目標(biāo)優(yōu)化的K均值聚類算法可以通過聚類數(shù)K、初始聚類質(zhì)心以及余弦相似度和歐氏距離衡量的目標(biāo)函數(shù)將文檔劃分至相應(yīng)質(zhì)心內(nèi)，并通過若干次的質(zhì)心迭代更新，得到最優(yōu)聚類解。算法以矩陣A[K][n]代表文檔聚類解，K表示聚類數(shù)量，n表示文檔集合中的文檔數(shù)量，矩陣元素A[k][i]定義為

(25)

若文檔di劃分至質(zhì)心Ck，則A[k][i]=1；否則，A[k][i]=0。多目標(biāo)優(yōu)化的K均值聚類算法執(zhí)行過程如算法2所示：

算法2：基于多目標(biāo)優(yōu)化的K均值聚類過程

(1)input: text document setDand clustering numberK

(2)output: clustering solution matrixA[K][n]

(3)select randomKdocuments as clusters centroidC=(C1,C2,…,CK)

(4)initialize all elements as zeros in matrixA[K][n]

(5)whilet

(6)foreach documentdiinDdo

(7)k=argmaxk∈{1 to K}based onobj(di,Ck)

(8) allocatedito the clusterCkandA[k][i]=1

(9)endfor

(10)update the clusters centroid by Eq.(24)

(11)t=t+1

(12)endwhile

(13)returndocument clustering solution

算法過程詳細(xì)說明：步驟(1)將文本文檔集合D和聚類數(shù)量K作為算法輸入，步驟(2)輸出聚類解，以二進(jìn)制數(shù)據(jù)填充的矩陣A[K][n]表示。步驟(3)在初始文檔集中隨機(jī)選擇K個文檔作為初始的聚類質(zhì)心，步驟(4)將聚類解矩陣A[K][n]全部以0進(jìn)行初始化，步驟(5)～步驟(12)在集合中的全部文檔間進(jìn)行迭代，即通過步驟(7)尋找使得目標(biāo)函數(shù)(23)達(dá)到最大的目標(biāo)聚類質(zhì)心，再通過步驟(8)將各文檔分配至對應(yīng)質(zhì)心的聚類中，并將對應(yīng)矩陣元素更新為1；步驟(10)重新通過式(24)更新聚類質(zhì)心，在達(dá)到最大迭代次數(shù)后，最后在步驟(13)返回文檔集合的聚類結(jié)果。

圖1是特征選擇與文本聚類流程。圖左側(cè)步驟是聚類第一階段，包括對文檔集合預(yù)處理，即分割詞語、移除終止詞、提取相應(yīng)詞干，然后利用TF-IDF計(jì)算詞條權(quán)重，并基于詞條權(quán)重將文檔表示為矢量空間模型。圖右側(cè)進(jìn)入第二階段，先利用二進(jìn)制灰狼優(yōu)化的特征選擇策略選擇信息化特征子集，該階段可分別利用詞條方差TV法和平均絕對差MAD法對二進(jìn)制灰狼優(yōu)化算法中的特征選擇解進(jìn)行適應(yīng)度評估，因此可以生成兩種不同的最優(yōu)特征子集；然后，進(jìn)入第三階段，為了兼顧不同適應(yīng)度評估方法的優(yōu)勢，在兩種不同特征子集上引入特征歸并機(jī)制，包括特征合并、特征交叉以及改進(jìn)特征合并，生成最終的最優(yōu)特征子集；最后，進(jìn)入第四階段，利用提出的同步考慮余弦相似度和歐氏距離兩種聚類度量指標(biāo)的多目標(biāo)優(yōu)化K均值聚類算法對文檔進(jìn)行聚類分析，得到最終的文本聚類結(jié)果。

圖1 文本特征選擇及聚類流程

3 實(shí)驗(yàn)分析

3.1 測試文本

利用Matlab平臺編寫測試程序，并利用表1中由計(jì)算智能實(shí)驗(yàn)室LABIC(http://sites.labic.icmc.usp.br/text_collections/)提供的6種基準(zhǔn)文本數(shù)據(jù)集測試算法性能。表1中給出了數(shù)據(jù)集的來源、所含文檔數(shù)、詞條數(shù)以及分類數(shù)。數(shù)據(jù)類型包括常規(guī)的技術(shù)報(bào)告、Web網(wǎng)頁以及不同類型的文本檢索文件，可用于測試特征選擇后文檔聚類的適應(yīng)性和穩(wěn)定性。

表1 測試文檔數(shù)據(jù)集

3.2 測試算法及相關(guān)參數(shù)

基于灰狼優(yōu)化的特征選擇策略中，選用不同適應(yīng)度評估標(biāo)準(zhǔn)，可以得到不同的特征子集；同時，利用不同的特征子集歸并方法，也可以得到不同的特征子集。本文將通過不同的策略組合方式，得到多種測試算法，包括：當(dāng)不利用特征子集歸并機(jī)制時，基于二進(jìn)制灰狼優(yōu)化算法和詞條方差TV的特征選擇算法GWOTV-TC、基于二進(jìn)制灰狼優(yōu)化算法和平均絕對差MAD的特征選擇算法GWOMAD-TC；利用特征子集歸并機(jī)制時，此時需要通過TV和MAD生成兩個特征子集，然后再通過特征歸并機(jī)制可以有3種算法組合，即：基于特征合并的特征選擇算法GWO-TC-U、基于特征交叉的特征選擇算法GWO-TC-I以及基于改進(jìn)特征合并的特征選擇算法GWO-TC-MU。

除此之外，為了觀測灰狼優(yōu)化算法在進(jìn)行文本特征選擇的有效性，選擇傳統(tǒng)K均值聚類算法K-means和另外兩種智能群體算法進(jìn)行性能對比，包括基于遺傳算法的特征選擇算法GA-TC[8]和基于粒子群優(yōu)化算法的特征選擇算法PSO-TC[10]。3種群體智能算法中的種群規(guī)模設(shè)置為100，最大迭代次數(shù)均設(shè)置為500。GA-TC算法中遺傳交叉概率為0.7，遺傳變異概率為0.3。PSO-TC算法中粒子慣性權(quán)重的最小值和最大值分別設(shè)置為0.4和0.9，兩個學(xué)習(xí)因子均設(shè)置為0.49。GWO-TC算法中參數(shù)a、A和C均是根據(jù)[0,1]間的隨機(jī)值相應(yīng)生成，因此無需提前配置。改進(jìn)特征合并機(jī)制中占比C1和C2均設(shè)置為50%進(jìn)行實(shí)驗(yàn)。

3.3 評估指標(biāo)

利用文本聚類的4種常用評估指標(biāo)對算法聚類效果進(jìn)行評估，包括：精確率Precision(簡稱P)、準(zhǔn)確率Accuracy(簡稱A)、召回率Recall(簡稱R)和F度量F-meansure(簡稱F)。此外，為了驗(yàn)證灰狼優(yōu)化的特征選擇及特征歸并機(jī)制的效果，再引入特征選擇數(shù)量和相應(yīng)聚類的迭代時間兩個指標(biāo)進(jìn)行性能度量。

(1)精確率

精確率P表示所有相關(guān)文檔與所有聚類中文檔總量的比例，表示為

P(i,j)=ni,j/nj

(26)

式中：P(i,j)表示聚類j中分類i的精確值，ni,j表示聚類j中分類i的實(shí)際成員數(shù)量，nj為聚類j中的所有成員數(shù)量。

(2)召回率

召回率R表示相關(guān)文檔實(shí)際數(shù)量與所有聚類文檔的比例，該指標(biāo)根據(jù)給定的分類標(biāo)簽對每個聚類進(jìn)行計(jì)算，表示為

R(i,j)=ni,j/ni

(27)

式中：R(i,j)表示聚類j中分類i的召回值，ni表示分類i中的實(shí)際成員數(shù)量。

(3)F度量

F度量根據(jù)精確率P和召回率R計(jì)算。最佳文本聚類效果是F度量值盡可能接近于1。聚類j中分類i的F度量計(jì)算為

(28)

所有聚類的F度量表示為

(29)

式中：n表示文檔集合D中的文檔總量。

(4)準(zhǔn)確率

準(zhǔn)確率用于計(jì)算分配至每個聚類的真實(shí)文本文檔所占的比例，表示為

(30)

式中：K表示總聚類量，P(i,j)表示聚類j中分類i的精確值。

(5)特征數(shù)量

該指標(biāo)表示利用基于二進(jìn)制灰狼優(yōu)化算法的特征選擇后以及進(jìn)一步利用3種特征歸并機(jī)制得到的特征數(shù)量。特征數(shù)量的有效選取決定了文本聚類效率與準(zhǔn)確度，是一個關(guān)鍵指標(biāo)。

(6)聚類迭代時間

該指標(biāo)可以衡量特征選擇后文本聚類的效率。

3.4 實(shí)驗(yàn)分析

圖2是6種測試文本數(shù)據(jù)集利用不同算法最終得到的特征數(shù)量情況。由于傳統(tǒng)K均值聚類算法進(jìn)行文檔聚類前未做任何特征選擇，是將原始文檔中的所有特征(信息化特征和非信息特征)考慮在內(nèi)的，所以未列入比較范圍。特征選擇量是特征降維的明確表現(xiàn)，降維過程中會盡可能提煉出可表現(xiàn)文檔內(nèi)容的信息化特征。從結(jié)果可以看出，比較PSO-TC和GA-TC兩種算法，本文提出的二進(jìn)制灰狼優(yōu)化算法特征選擇可以有效降低特征選擇量，說明灰狼優(yōu)化算法的尋優(yōu)性能是更加優(yōu)秀的，應(yīng)用于特征選擇問題求解上是有效可行的。總體來說，兩種特征相關(guān)性分值計(jì)算方式TV和MAD得到的特征選擇量較為接近，在6種測試數(shù)據(jù)集中均表現(xiàn)得較穩(wěn)定。而進(jìn)行特征合并后，特征選擇量明顯增加。利用改進(jìn)的特征合并機(jī)制后，特征選擇量有所降低。特征選擇量最少的特征交叉機(jī)制。結(jié)合所有數(shù)據(jù)結(jié)果來看，本文設(shè)計(jì)的二進(jìn)制灰狼優(yōu)化算法的特征選擇策略可以明顯降低特征選擇量，但是由于合并方法考慮了兩種標(biāo)準(zhǔn)所生成的所有特征，會增加特征總量；而交叉方法僅僅選擇不同評估標(biāo)準(zhǔn)下的共有特征，會減小特征規(guī)模，也可能導(dǎo)致重要特征丟失。因此，還需要通過在已有特征選擇量的基礎(chǔ)上做聚類分析進(jìn)行進(jìn)一步性能測試。

圖2 特征選擇量

此外，從6種不同類型的測試文本數(shù)據(jù)集的測試效果來看，基于二進(jìn)制灰狼優(yōu)化算法的特征選擇策略還是具有較好的適應(yīng)性的，并不會因?yàn)閿?shù)據(jù)集的來源不同和所包含的文檔和詞條量的不同而出現(xiàn)性能的較大差異，這說明算法針對不同類型的文本文檔內(nèi)容還是具有很好的適應(yīng)度和穩(wěn)定性的。

表2是8種算法在6種測試數(shù)據(jù)集上得到的聚類精確率、準(zhǔn)確率、召回率和F度量指標(biāo)上的性能表現(xiàn)。K均值算法的聚類效果明顯是最差的，由于傳統(tǒng)的K均值算法并沒有利用任何文本選擇機(jī)制，這導(dǎo)致有很多冗余和非信息化特征在聚類過程中需要考慮，噪聲太多，準(zhǔn)確性較差。其它智能群體算法在使用特征選擇策略后可以明顯提升聚類性能。相比較粒子群和遺傳算法兩種特征選擇方法，本文的二進(jìn)制灰狼優(yōu)化算法的特征選擇機(jī)制絕大多數(shù)測試數(shù)據(jù)中可以進(jìn)一步改善聚類效果，說明前期的特征選擇中有效分離出非信息化特征，得到了最優(yōu)的特征子集。利用不同的相關(guān)性分值計(jì)算方式后，對所生成的特征子集做出特征合并或特征交叉后，對聚類性能也可以產(chǎn)生較積極的影響，各項(xiàng)聚類指標(biāo)均有一定程度提升，說明本文利用特征歸并機(jī)制是有效的。明顯地，改進(jìn)的特征合并機(jī)制下的聚類性能是最優(yōu)的，它可以有效選擇最能描述文本內(nèi)容的高相關(guān)性文本特征，改進(jìn)后期聚類效果。

表2 聚類性能指標(biāo)

圖3是8種算法的聚類迭代時間對比情況。傳統(tǒng)K均值算法未作任何文本特征選擇的基礎(chǔ)上進(jìn)行文檔聚類，聚類最快，但從表2的結(jié)果得知，其聚類準(zhǔn)確率較差。進(jìn)行特征選擇后，雖然聚類時間有所增加，但聚類性能表現(xiàn)更好。此外，聚類迭代時間與測試數(shù)據(jù)集中的文檔數(shù)量和詞條數(shù)量是緊密相關(guān)的，而特征選擇量也會相應(yīng)影響聚類時間?？傮w而言，利用二進(jìn)制灰狼優(yōu)化算法進(jìn)行文本特征選擇時，比較另外兩種智能群體算法，執(zhí)行效率有了明顯提升，這與灰狼尋優(yōu)機(jī)制密切相關(guān)。

圖3 聚類迭代時間

4 結(jié)束語

提出基于二進(jìn)制灰狼優(yōu)化算法的特征選擇與文本聚類算法，算法首先對文本數(shù)據(jù)進(jìn)行預(yù)處理；其次利用二進(jìn)制灰狼優(yōu)化對文本特征進(jìn)行選擇，得到最優(yōu)的信息化特征子集；然后對上一階段中不同特征相關(guān)分值計(jì)算方法得到的最優(yōu)特征子集進(jìn)行合并與交叉操作，進(jìn)一步得到新的最優(yōu)特征子集；第四階段基于新的特征子集利用同步考慮余弦相似和歐氏距離指標(biāo)的多目標(biāo)優(yōu)化K均值算法對文本進(jìn)行聚類，得到最終的文本聚類解。結(jié)果表明，該算法可以有效降低特征維度，聚類性能更好。進(jìn)一步的研究，一是對灰狼優(yōu)化的收斂系數(shù)做出改進(jìn)，使系數(shù)隨著搜索過程呈非線性改變，增強(qiáng)特征選擇的尋優(yōu)性能；二是如何融合其它過濾式特征初選方法和智能群體算法的優(yōu)勢做更準(zhǔn)確的特征空間降維，進(jìn)一步提升文本聚類精度。