融入混沌與對(duì)立學(xué)習(xí)機(jī)制的二進(jìn)制粒子群特征選擇算法

袁明鋒 步中華 王 強(qiáng)

1(重慶輕工職業(yè)學(xué)院大數(shù)據(jù)與信息產(chǎn)業(yè)系 重慶 401329) 2(青島中石大科技創(chuàng)業(yè)有限公司 山東 青島 266580) 3(青島理工大學(xué)信息學(xué)院 山東 青島 266580)

0 引 言

文本是現(xiàn)代社會(huì)存取信息和交流的主要方式，尤其在移動(dòng)互聯(lián)網(wǎng)時(shí)代，文本信息增長速度呈指數(shù)級(jí)。然而，文本中包含高維度信息化和非信息化特征，非信息化特征通常為冗余、噪聲和不相關(guān)特征，對(duì)提取文本實(shí)質(zhì)內(nèi)容信息相對(duì)無效。因此，應(yīng)該盡可能提煉文本中與本質(zhì)內(nèi)容密切相關(guān)的信息化特征，為進(jìn)一步文本檢索、文本分類及文本信息挖掘作支撐[1]。特征選擇的主要任務(wù)即是從文本中得出信息化特征子集的過程[2]。然而，文本空間的高維度使得特征選擇仍然是NP難問題。

本文提出一種基于改進(jìn)二進(jìn)制粒子群優(yōu)化的特征選擇算法。將特征選擇問題形式化為粒子最優(yōu)位置的搜索過程，引入對(duì)立學(xué)習(xí)機(jī)制對(duì)隨機(jī)初始化過程做出改進(jìn)，并利用混沌系統(tǒng)和基于適應(yīng)度的動(dòng)態(tài)慣性權(quán)重提升粒子尋優(yōu)性能，通過建立的二進(jìn)制粒子群優(yōu)化對(duì)最優(yōu)文本特征子集進(jìn)行選擇與搜索。同時(shí)，在評(píng)估粒子位置適應(yīng)度過程中，引用詞條方差和平均絕對(duì)差兩種適應(yīng)度評(píng)估方法，得出文本的最優(yōu)特征子集?；讷@得的最優(yōu)特征子集，利用K均值算法對(duì)文本文檔數(shù)據(jù)集進(jìn)行了聚類分析，驗(yàn)證了在所獲文本特征最優(yōu)子集的前提下文本特征維度得到了有效降低，文檔聚類準(zhǔn)確率也得到了極大提升，有效證明了融入混沌和對(duì)立學(xué)習(xí)機(jī)制的二進(jìn)制粒子群優(yōu)化特征選擇算法是有效可行的。

1 相關(guān)研究

傳統(tǒng)文本特征選擇算法主要包括文檔頻率DF[3]、互信息MI[4]、信息增益IG[5]和卡方統(tǒng)計(jì)CHI[6]等。DF以文檔頻率為依據(jù)，但忽略了詞條在不同文檔間的分布及詞條關(guān)聯(lián)性對(duì)文本內(nèi)容的表征影響。互信息MI、信息增益IG和卡方統(tǒng)計(jì)CHI三種算法通過引入文本分類信息改善特征詞條的文本表征能力，但同時(shí)也降低了特征維度約減上的效率，忽略了詞條在不同文檔間的分布、詞條位置及詞條相關(guān)性對(duì)于文本內(nèi)容的表示影響。此外，目前初始語料庫中通常會(huì)引入文本文檔的分類信息，這使得以上算法在特征選擇時(shí)無法進(jìn)行無監(jiān)督文本聚類分析。

除了以上傳統(tǒng)特征選擇算法，群體智能算法是目前針對(duì)文本特征選擇求解的另一種主要方法。由于特征選擇的NP屬性，智能群體算法較強(qiáng)的尋優(yōu)性能可以通過不斷對(duì)初始解的迭代更新尋找接近最優(yōu)的特征選擇解，同時(shí)大幅降低特征維度，改善文本聚類效率[7]。相關(guān)研究中，文獻(xiàn)[8]依據(jù)詞條權(quán)重重要性設(shè)計(jì)基于遺傳算法的特征選擇算法GAFS，可以較高效率選擇最優(yōu)特征子集，而其郵件文本對(duì)GAFS的測(cè)試也驗(yàn)證了算法性能。文獻(xiàn)[9]通過改進(jìn)和聲搜索過程設(shè)計(jì)了自適應(yīng)特征選擇算法，利用音調(diào)調(diào)整、限制特征域和內(nèi)存合并率三種動(dòng)態(tài)策略改進(jìn)傳統(tǒng)和聲搜索，多維度數(shù)據(jù)集測(cè)試也驗(yàn)證了最優(yōu)特征子集選擇的有效性。粒子群算法是一種計(jì)算代價(jià)較小且收斂較快的智能算法。文獻(xiàn)[10]提出基于粒子群優(yōu)化的特征選擇算法BPSOFS。利用新的動(dòng)態(tài)慣性權(quán)重策略對(duì)粒子進(jìn)化操作進(jìn)行改進(jìn)，而文本數(shù)據(jù)集的測(cè)試也證明新算法生成的文本聚類在準(zhǔn)確度和效率上均有所提升。文獻(xiàn)[11]結(jié)合遺傳算法和并行協(xié)同進(jìn)化算法求解特征選擇，先利用遺傳算法搜索特征子集，再進(jìn)一步利用進(jìn)化協(xié)同機(jī)制提升搜索效率，得到準(zhǔn)確度更高的特征選擇解。貓群算法也可用于求解優(yōu)化問題。文獻(xiàn)[12]通過修正貓群算法設(shè)計(jì)了特征選擇算法，結(jié)果也證實(shí)利用貓群算法后的聚類明顯然優(yōu)于僅使用詞條頻率下的聚類效果。文獻(xiàn)[13]設(shè)計(jì)了基于蟻群算法的無監(jiān)督概率特征選擇算法，算法利用特征相似性降低特征維度，引入矩陣記錄特征共存率，通過特征提取概率函數(shù)對(duì)特征進(jìn)行排序，并獲取相關(guān)分值更高的特征子集作為聚類特征基礎(chǔ)。文獻(xiàn)[14]通過小生境改進(jìn)了傳統(tǒng)粒子群算法，以增強(qiáng)的粒子搜索性能對(duì)文本特征選擇進(jìn)行進(jìn)化求解，獲得的文本分類效率得到有效提升。總結(jié)已有工作，可將群體智能算法求解特征選擇問題劃分為以下幾類：第一種是直接應(yīng)用某一種智能群體算法將特征選擇形式為一個(gè)優(yōu)化問題，然后利用智能群體的尋優(yōu)機(jī)制得到特征選擇解；第二種是不同智能群體算法的結(jié)合再應(yīng)用于特征選擇求解，這類方法總體來說雖然可以結(jié)合不同智能群體算法在局部和全局尋優(yōu)上的性能，但其搜索過程復(fù)雜性太高，可能導(dǎo)致無法得到滿意的效率；第三種則是將傳統(tǒng)方法與智能群體算法結(jié)合起來，首先在詞條權(quán)重定義方面依然使用基于詞條頻率、文檔頻率、詞條分布等傳統(tǒng)要素，然后在此基礎(chǔ)上，再利用智能群體算法根據(jù)現(xiàn)有詞條權(quán)重根據(jù)所定義的特征相關(guān)性分值尋找最優(yōu)的特征子集。本文將利用第三類方法，首先利用一種改進(jìn)的詞條權(quán)重計(jì)量方法得到初步的特征初選，然后設(shè)計(jì)一種改進(jìn)的二進(jìn)制粒子群優(yōu)化方法進(jìn)行特征子集選擇。為了提升粒子群的搜索能力，引入了混沌系統(tǒng)和對(duì)立學(xué)習(xí)機(jī)制對(duì)粒子的隨機(jī)搜索方向和初始種群分布進(jìn)行了優(yōu)化，更好地實(shí)現(xiàn)特征選擇，而后續(xù)基于所選特征子集的聚類結(jié)果也很好地驗(yàn)證了這一特征選擇方法的有效性。

2 詞條權(quán)重計(jì)算模型

令集合D包含n個(gè)文檔 ，表示為D={d1,d2,…,di,…,dn}，其中：di表示D中的第i個(gè)文檔；n表示集合中的文檔總量。利用傳統(tǒng)的詞頻逆文本頻率指數(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ù)。

本文將利用一種新的詞條權(quán)重計(jì)算方法NTW，改進(jìn)思路主要在于：首先，TF-IDF方法中，主要用到詞條的文檔頻率倒數(shù)IDF，而忽略了每個(gè)詞條的文檔頻率DF，由于當(dāng)詞條出現(xiàn)在大多數(shù)文檔，則DF可以通過增加的權(quán)重分值影響其重要性，因此，DF將作為一個(gè)參數(shù)考慮在新的詞條權(quán)重計(jì)算中。其次，TF-IDF方法忽略了文檔中所有詞條的數(shù)量，該參數(shù)有助于選擇較少數(shù)量的信息化特征。最后，最大詞條頻率可用于區(qū)分文檔詞條，若文檔包含大量詞條，則表明詞條特征重要性要小于少數(shù)量詞條的情形?；谝陨先齻€(gè)因素的考慮，改進(jìn)詞條權(quán)重計(jì)算方法NTW定義為：

(2)

式中：ai表示文檔i中所選特征數(shù)量；maxf(i)表示文檔i中的最大詞條頻率。

通過向量空間模型VSM，可根據(jù)詞條權(quán)重wi,j將整個(gè)文檔集合D表示為：

(3)

3 二進(jìn)制粒子群優(yōu)化算法

粒子群算法是受鳥類、魚群社會(huì)行為啟發(fā)得到的一種元啟發(fā)式算法。粒子群中的個(gè)體稱為一個(gè)粒子，種群由S個(gè)粒子構(gòu)成，每個(gè)粒子代表在d維空間內(nèi)的一個(gè)候選問題解。粒子i在d維空間內(nèi)的位置向量為Xi=(xi1,xi2,…,xid)，粒子速度向量為Vi=(vi1,vi2,…,vid)。所有粒子在搜索空間內(nèi)移動(dòng)以尋找其全局最優(yōu)解，粒子的移動(dòng)會(huì)受到自身已知的個(gè)體最優(yōu)位置pbest和種群的已知全局最優(yōu)位置gbest的影響。粒子i的個(gè)體最優(yōu)位置可表示為pbesti=(pbesti1,pbesti2,…,pbestid)，種群的全局最優(yōu)位置可表示為gbesti=(gbest1,gbest2,…,gbestd)。粒子位置優(yōu)劣由預(yù)定義的適應(yīng)度函數(shù)評(píng)估。粒子i的速度和位置更新方式如下：

vid(t+1)=w×vid(t)+c1×r1×(pbestid-xid(t))+

c2×r2×(gbestd-xid(t))

(4)

xid(t+1)=xid(t)+vid(t+1)

(5)

式中：r1和r2為[0,1]內(nèi)均勻分布的隨機(jī)數(shù)；c1和c2分別為認(rèn)知權(quán)重因子和社會(huì)權(quán)重因子，通常固定取值在[0,2]之間；w為[0,1]間的慣性權(quán)重，用于控制粒子先代速度的影響。較大慣性權(quán)重w利于粒子對(duì)新區(qū)域的全局勘探，較小慣性權(quán)重w利于粒子的局部開發(fā)，因此，慣性權(quán)重可以均衡全局勘探和局部開發(fā)過程。

傳統(tǒng)粒子群優(yōu)化算法是連續(xù)空間內(nèi)的粒子群算法，即粒子位置可在連續(xù)空間位置上移動(dòng)。對(duì)于特征選擇問題而言，當(dāng)以粒子位置代表特征選擇解時(shí)，單個(gè)特征是否被選擇僅有選擇與不選擇兩種情形，因此，粒子位置僅有兩種取值情形，此時(shí)可以二進(jìn)制形式定義粒子位置。粒子位置更新代表對(duì)應(yīng)位置比特值的改變，粒子速度則代表粒子位置改變?yōu)?的概率。利用S形函數(shù)將連續(xù)位置信息映射為二進(jìn)制位置信息。速度的S形函數(shù)定義為：

(6)

式中：Sig(vid(t+1))為d維比特值為1的概率。粒子新位置更新方式為：

(7)

式中：rand(0,1)為[0,1]間的隨機(jī)數(shù)。

4 基于混沌和對(duì)立學(xué)習(xí)的二進(jìn)制粒子群優(yōu)化特征選擇算法COBPSO

4.1 特征選擇模型

特征選擇的目標(biāo)是按某種標(biāo)準(zhǔn)從文本詞條中提煉出與文本內(nèi)容更為貼近的文本特征，即盡可能消除非信息化的冗余特征，得到最優(yōu)的信息化特征子集。令Fi為文檔i的特征集合，表示為向量Fi={fi,1,fi,2,…,fi,j,…,fi,d}，其中，j為特征序號(hào)。經(jīng)過特征選擇后，新的信息化特征子集SFi={sfi,1,sfi,2,…,sfi,j,…,sfi,m}，其中，m為新的特征長度，且m

4.2 特征選擇解編碼

以粒子位置表征特征選擇候選解，即一個(gè)粒子代表一種選擇的文本特征子集，表示為表1所示形式。編碼中上層向量代表特征序號(hào)(維度)，下層向量代表粒子在各維度上的二進(jìn)制位置，粒子搜索的空間維度d對(duì)應(yīng)可能文本特征數(shù)量。二進(jìn)制向量Xi=(xi1,xi2,…,xid)，若xij=1，則表明粒子i位置所代表的特征選擇候選解中，特征j選擇為信息化特征；若xij=0，則表明粒子i位置所代表的特征選擇候選解中，特征j不被選擇定信息化特征，即不包括在最優(yōu)特征子集中。

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

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

適應(yīng)度函數(shù)用于計(jì)算文檔中的特征相關(guān)性分值，即為評(píng)估個(gè)體粒子位置所代表的特征選擇解的優(yōu)劣。本文引用兩種特征相關(guān)分值計(jì)算方法，一種是詞條方差法TV，一種是平均中位數(shù)法MM。

詞條方差法TV可以準(zhǔn)確反映特征對(duì)文本類別的區(qū)分能力，選擇以具有類別信息的特征為主，不足是會(huì)忽略特征間的相關(guān)性。其目標(biāo)是通過計(jì)算與均值間的方差分配特征相關(guān)性分值，該方法的出發(fā)點(diǎn)是考慮所有文檔中非均勻分布的特征比均勻分布特征更能較好描述文檔含義。詞條特征的TV值定義為：

(8)

(9)

平均中位法MM則可以盡可能選擇具有相關(guān)性的特征，通過計(jì)算平均值與中位值間的絕對(duì)差分配特征相關(guān)性分值。詞條特征的MM值定義為：

(10)

式中：median(xt)表示特征t的中位值。

令D為文檔集，文本預(yù)處理后特征集合為T，以T={t1,t2,…,tf}代表初始特征集合，特征數(shù)量為f。通過詞條方差TV計(jì)算特征相關(guān)性分值后，將特征集合T中的特征按照TV值降序排列，令FS1={t11,t12,…,tq}為通過TV選擇的特征子集，tq代表TV所選特征數(shù)量為q，且q<

利用特征合并操作U建立新特征子集FS3，即合并特征子集FS1和特征子集FS2，表示為：

FS3=FS1∪FS2

(11)

若特征子集FS3包含U個(gè)特征，則U≥{q,l}。

利用特征交叉操作I建立新的特征子集FS4，即交叉特征子集FS1和特征子集FS2，表示為：

FS4=FS1∩FS2

(12)

若特征子集FS4包含I個(gè)特征，則I≤{q,l}。

4.4 基于對(duì)立學(xué)習(xí)機(jī)制的粒子種群初始化

傳統(tǒng)元啟發(fā)式算法以隨機(jī)方式生成初始種群，然后逐步迭代接近全局最優(yōu)解改善種群個(gè)體，其搜索過程在滿足預(yù)定義終止條件時(shí)結(jié)束。因此，算法的收斂速度與初始種群與最優(yōu)解間的距離直接相關(guān)。最差情形中，最優(yōu)解離隨機(jī)初始種群較遠(yuǎn)，則搜索尋優(yōu)可能無法完成。對(duì)立學(xué)習(xí)可以通過同步考慮當(dāng)前解及其對(duì)立解改善候選解的質(zhì)量，收斂速度可以通過同步考慮當(dāng)前解及其對(duì)立解予以改善。研究表明，約50%隨機(jī)初始解會(huì)比其對(duì)立解離最優(yōu)解更遠(yuǎn)。因此，將隨機(jī)初始解及其對(duì)立解聯(lián)合考慮在初始種群中，可以加快搜索收斂速度。

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

x′=u+l-x

(13)

基于對(duì)立學(xué)習(xí)的種群初始化步驟如算法1所示。

算法1對(duì)立學(xué)習(xí)機(jī)制的粒子種群初始化

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

輸出：規(guī)模S的粒子集合X。

1.隨機(jī)生成粒子數(shù)為S的初始種群{X}；

2.fori=1 toSdo

//所有粒子上遍歷

3.forj=1 toddo

//所有位置維度上遍歷

//粒子位置的對(duì)立點(diǎn)

5.endfor

6.endfor

7.X″=X∪X′

//融合原始粒子和對(duì)立粒子為新種群

8.計(jì)算新種群X″中粒子的適應(yīng)度；

9.根據(jù)適應(yīng)度對(duì)X″中的粒子作降序排列；

10.以排序前S的粒子種群X作為最終初始種群；

11.返回初始種群X。

4.5 基于適應(yīng)值的動(dòng)態(tài)慣性權(quán)重機(jī)制

二進(jìn)制粒子群優(yōu)化算法中，粒子速度更新與三個(gè)成分相關(guān)：粒子先前速度vid(t)、認(rèn)知成分pbestid-xid(t)、社會(huì)成分gbestd-xid(t)。先前速度即前次迭代的粒子速度，認(rèn)知成分代表粒子自身的信息，社會(huì)成分為種群保留的信息。先前速度對(duì)當(dāng)前速度的影響由慣性權(quán)重w決定，因子c1和r1、c2和r2則分別控制認(rèn)知成分和社會(huì)成分的權(quán)重。本文提出一種動(dòng)態(tài)慣性權(quán)重機(jī)制取代固定慣性權(quán)重，使慣性權(quán)重隨搜索迭代過程進(jìn)行自適應(yīng)更新，以適應(yīng)于粒子搜索過程中在前期的局部開發(fā)和后期的全局勘探間取得均衡。首先將粒子i的適應(yīng)值定義為：

(14)

式中：K為粒子聚類量；d(cl,cg)為聚類cl和cg間的距離；DIA(ck)為聚類k的直徑。同時(shí)：

(15)

(16)

式中：DIS(x,y)表示粒子x與粒子y間的歐氏距離。

由于需要尋找更高聚類內(nèi)相似度和更低聚類間相似度的粒子聚類，因此，適應(yīng)值更高的粒子應(yīng)優(yōu)先選擇。換言之，基于適應(yīng)值的動(dòng)態(tài)慣性權(quán)重將分配高慣性權(quán)重至低適應(yīng)值粒子，促進(jìn)該類粒子在搜索空間內(nèi)對(duì)未知區(qū)域的全局勘探；而會(huì)分配低慣性權(quán)重至高適應(yīng)值粒子，促進(jìn)該類粒子在搜索空間內(nèi)作進(jìn)一步局部開發(fā)。因此，粒子慣性權(quán)重將依據(jù)粒子當(dāng)前的適應(yīng)值與當(dāng)前最優(yōu)適應(yīng)值進(jìn)行計(jì)算：

(17)

式中：fiti為粒子i的適應(yīng)值；fitbest為全局最優(yōu)粒子gbest的適應(yīng)值?；趧?dòng)態(tài)慣性權(quán)重，粒子的速度更新可改進(jìn)為：

vid(t+1)=fwi×vid(t)+c1×r1×(pbestid-xid(t))+

c2×r2×(gbestd-xid(t))

(18)

由式(18)可知，融入適應(yīng)值的動(dòng)態(tài)慣性權(quán)重至粒子速度更新可以根據(jù)粒子當(dāng)前狀態(tài)動(dòng)態(tài)調(diào)整粒子速度，較大的慣性權(quán)重可以增加較低適應(yīng)值粒子的速度步長，促進(jìn)其搜索空間內(nèi)的全局勘探過程；而較小的慣性權(quán)重可以減小較高適應(yīng)值粒子的速度步長，促進(jìn)其搜索空間內(nèi)的局部開發(fā)過程。

4.6 基于對(duì)立學(xué)習(xí)的學(xué)習(xí)因子調(diào)整

粒子速度更新的第二部分和第三部分分別反映粒子的認(rèn)知信息和社會(huì)信息，這兩部分主要受學(xué)習(xí)因子c的影響。越大的學(xué)習(xí)因子c1會(huì)使粒子更快地朝自身已知最優(yōu)位置pbest移動(dòng)，越大的學(xué)習(xí)因子c2會(huì)使粒子更快地朝全局最優(yōu)位置gbest移動(dòng)。通常，兩個(gè)學(xué)習(xí)因子設(shè)置為相同權(quán)重。本文將改變學(xué)習(xí)因子取值以控制認(rèn)知和社會(huì)信息對(duì)粒子速度更新的影響，設(shè)計(jì)基于對(duì)立學(xué)習(xí)的粒子替換策略，避免粒子在局部最優(yōu)解上早熟，促進(jìn)粒子向未知區(qū)域繼續(xù)搜索。具體做法是：首先，生成全局最優(yōu)粒子gbest的對(duì)立位置，用于替換最差適應(yīng)度粒子gworst，從而保留gbest粒子的較優(yōu)解，利用最差粒子gworst搜索未知區(qū)域。對(duì)于所有粒子，除gworst以外，c1和c2設(shè)置為2，而gworst粒子的c1和c2分別設(shè)置為3和1。融入對(duì)立學(xué)習(xí)的差異化學(xué)習(xí)因子設(shè)置可以使粒子移動(dòng)方向的更新朝自身最優(yōu)繼續(xù)移動(dòng)。

4.7 基于混沌理論的隨機(jī)搜索機(jī)制

混沌是一種非線性的動(dòng)態(tài)隨機(jī)非重復(fù)決策系統(tǒng)，表征對(duì)初始條件的敏感依賴性，也是一種無限非穩(wěn)定的周期運(yùn)動(dòng)。由于混沌的可遍歷性及非重復(fù)性，它可以更有效地實(shí)現(xiàn)比隨機(jī)搜索(由隨機(jī)值r1和r2決定)更廣泛的搜索過程。將混沌系統(tǒng)融入二進(jìn)制粒子群優(yōu)化算法中可以增強(qiáng)搜索能力，更好預(yù)防陷入局部最優(yōu)解。本文利用sinusoidal混沌映射生成混沌序列，形式化為：

CH(t+1)=μ×CH(t)2×sin(πCH(t))

(19)

式中：CH(t)表示迭代t時(shí)的混沌值，CH(t)∈[0,1]，初始值CH(0)在不等于0、0.25、0.5、0.75和1的情況下隨機(jī)生成；控制參數(shù)μ∈(0,2.3]，用于控制混沌值的變化行為，可變?chǔ)虒?duì)于混沌映射值的生成影響可參考文獻(xiàn)[15]中的討論。

本文利用混沌系統(tǒng)的非重復(fù)性，生成更均勻的隨機(jī)數(shù)序列提升粒子的搜索速度，主要方法是：利用sinusoidal映射公式生成的混沌序列取代粒子更新中的隨機(jī)值r，則基于sinusoidal映射的改進(jìn)粒子速度更新方式為：

vid(t+1)=fwi×vid(t)+c1×CH×(pbestid-xid(t))+

c2×(1-CH)×(gbestd-xid(t))

(20)

特征選擇算法COBPSO過程如算法2所示。

算法2改進(jìn)二進(jìn)制粒子群優(yōu)化特征選擇算法COBPSO

輸入：c1,c2,fw,CH,pbest,gbest,gworst,X,count,S。

輸出：全局最優(yōu)粒子gbest。

1.算法相關(guān)參數(shù)初始化；

2.隨機(jī)生成初始混沌值CH(0)；

3.利用算法1的對(duì)立學(xué)習(xí)機(jī)制生成粒子初始種群；

4.搜索個(gè)體最優(yōu)pbest、全局最優(yōu)gbest和全局最差gworst；

5.whilenot satisfy maximum iterationsdo

//若干次迭代尋優(yōu)

6.forp=1 toSdo

//所有粒子上遍歷

7.根據(jù)式(17)計(jì)算自適應(yīng)慣性權(quán)重值；

8.ifcount>δandxpisgworstthen

9.設(shè)置不均等學(xué)習(xí)因子(c1,c2)；

10.else

11.設(shè)置均等學(xué)習(xí)因子(c1,c2)；

12.endif

13.forq=1 toddo

//所有位置維度上遍歷

14.根據(jù)式(19)更新粒子混沌值CHq；

15.根據(jù)式(20)更新粒子速度；

16.根據(jù)式(5)更新粒子位置；

17.endfor

18.endfor

19.forp=1 toSdo

//所有粒子上遍歷

20.iff(xp)>f(pbestp)then

21.pbestp=xp；

22.iff(xp)>f(gbest)then

23.gbest=xp；

24.endif

25.endif

26.iff(xp)

27.gworst=xp；

28.endif

29.endfor

30.if全局最優(yōu)粒子gbest未發(fā)生變化then

31.count=count+1；

32.else

33.count=0；

34.endif

35.選擇全局最差粒子gworst；

36.ifcount<δthen

37.對(duì)全局最差粒子gworst作變異；

38.else

39.對(duì)全局最差粒子gworst作對(duì)立學(xué)習(xí)更新；

40.endif

41.endwhile

42.return最優(yōu)粒子gbest作為最優(yōu)特征選擇子集。

算法過程描述：算法輸入?yún)?shù)：學(xué)習(xí)因子、慣性權(quán)重、混沌映射值、粒子個(gè)體最優(yōu)解、全局最優(yōu)解、全局最差解、種群粒子當(dāng)前位置集合、全局最優(yōu)解狀態(tài)因子、種群規(guī)模，輸出為全局最優(yōu)粒子。步驟1和步驟2分別對(duì)粒子群優(yōu)化的相關(guān)參數(shù)和混沌映射值作初始化。步驟3利用算法1的對(duì)立學(xué)習(xí)機(jī)制對(duì)粒子種群進(jìn)行初始化，即得到特征選擇解的初始分布，步驟4根據(jù)適應(yīng)度函數(shù)計(jì)算個(gè)體最優(yōu)解、當(dāng)前種群的全局最優(yōu)解和全局最差解，由于還未迭代尋優(yōu)，個(gè)體粒子當(dāng)前位置即可視為其個(gè)體最優(yōu)解。接下來是若干次的迭代尋優(yōu)過程，即步驟5-步驟41的過程。迭代過程的第一個(gè)for循環(huán)(步驟6-步驟18)遍歷所有種群粒子，步驟7計(jì)算粒子的慣性權(quán)重，步驟8和步驟9對(duì)最差粒子個(gè)體的學(xué)習(xí)因子作不同設(shè)置，步驟 11則對(duì)非最差粒子個(gè)體的學(xué)習(xí)因子作相同設(shè)置。步驟13-步驟17針對(duì)單個(gè)粒子的所有維度位置進(jìn)行更新，首先在步驟14更新混沌值，然后在步驟15和步驟16分別計(jì)算粒子每個(gè)維度上的速度和位置。迭代的第二次for循環(huán)(步驟19-步驟29)依然遍歷所有種群粒子，目標(biāo)是更新個(gè)體最優(yōu)解、全局最優(yōu)解和全局最差解三個(gè)粒子位置。步驟21表明，若當(dāng)前粒子適應(yīng)度大于其個(gè)體最優(yōu)解，則將其個(gè)體最優(yōu)解更新為當(dāng)前的粒子位置；進(jìn)一步，若當(dāng)前粒子適應(yīng)度大于全局最優(yōu)解，則在步驟23將當(dāng)前粒子設(shè)置為全局最優(yōu)解；步驟27表明，若當(dāng)前粒子適應(yīng)度小于全局最差解，則更新全局最差解為當(dāng)前粒子位置。步驟31表明，若全局最優(yōu)解不發(fā)生變化，則全局最優(yōu)粒子狀態(tài)count遞增1；否則，在步驟33將該因子重置為0。步驟35選取當(dāng)前種群中適應(yīng)度最差的粒子gworst。步驟36-步驟40根據(jù)變異(步驟37)或?qū)αW(xué)習(xí)機(jī)制(步驟39)對(duì)全局最差解gworst進(jìn)行更新。具體地，變異操作可根據(jù)變異概率決定是否以當(dāng)前的全局最優(yōu)粒子的對(duì)立點(diǎn)相應(yīng)維度上的位置替換全局最差解gworst的對(duì)應(yīng)維度位置；而對(duì)立學(xué)習(xí)則是以全局最優(yōu)粒子gbest的對(duì)立點(diǎn)粒子替換為當(dāng)前的全局最差解gworst。達(dá)到最大迭代次數(shù)后，最后在步驟42輸出最優(yōu)粒子位置，并解碼出相對(duì)應(yīng)的特征選擇解。

圖1為完整的文本特征選擇及聚類分析流程。首先，需要對(duì)輸入文本數(shù)據(jù)集作預(yù)處理，包括詞語分割、移除終止詞匯、提取詞干，詞條權(quán)重計(jì)算方面可以分別以傳統(tǒng)的TF-IDF方法和本文中的NTW方法進(jìn)行，再根據(jù)詞條權(quán)重將文本表征為向量空間模型。然后，進(jìn)入基于混沌與對(duì)立學(xué)習(xí)機(jī)制的二進(jìn)制粒子群優(yōu)化文本特征選擇步驟，該過程中會(huì)利用混沌系統(tǒng)和對(duì)立學(xué)習(xí)機(jī)制對(duì)二進(jìn)制粒子群優(yōu)化的特征選擇尋優(yōu)過程進(jìn)行改進(jìn)，提升搜索效率和尋優(yōu)準(zhǔn)確度；此外，在粒子位置所代表的特征選擇解的質(zhì)量評(píng)估方面，同時(shí)引用了詞條方差TV和平均中位數(shù)MM兩種方法，并針對(duì)兩種可能的特征選擇解，引入特征合并和特征交叉機(jī)制生成最優(yōu)特征子集，這樣可以同步考慮特征對(duì)文本類別的區(qū)分能力和特征間的相關(guān)性。最后，在所選擇的最優(yōu)特征子集的基礎(chǔ)上，引用K均值算法對(duì)文本數(shù)據(jù)集進(jìn)行聚類，并對(duì)聚類結(jié)果作準(zhǔn)確性和特征降維方面的分析。

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

5.1 測(cè)試文本說明

利用MATLAB編寫測(cè)試程序，利用表2中由計(jì)算智能實(shí)驗(yàn)LABIC提供的八種基準(zhǔn)文本數(shù)據(jù)集測(cè)試算法性能。表2給出了數(shù)據(jù)集來源、所含文檔數(shù)、詞條數(shù)、文本分類數(shù)。測(cè)試數(shù)據(jù)集合中，數(shù)據(jù)集DS1為技術(shù)報(bào)告類文集，數(shù)據(jù)集DS2為Web網(wǎng)頁搜索文集，數(shù)據(jù)集DS3-DS6均是文本信息的檢索內(nèi)容，實(shí)質(zhì)內(nèi)容各有不同，數(shù)據(jù)集DS7為醫(yī)學(xué)信息內(nèi)容，數(shù)據(jù)集DS8為新聞組播內(nèi)容。測(cè)試文本數(shù)據(jù)覆蓋了眾多文本信息領(lǐng)域，可以很好地測(cè)試本文的特征選擇算法的穩(wěn)定性和適應(yīng)性。

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

續(xù)表2

5.2 評(píng)估標(biāo)準(zhǔn)

利用F度量FM和準(zhǔn)確率AC兩個(gè)主要指標(biāo)度量特征選擇后的文本聚類性能。F度量根據(jù)給定的分類標(biāo)簽通過計(jì)算精確率P和召回率R計(jì)算，分別表示為：

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

(21)

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

(22)

式中：ni,j表示聚類j中分類i的成員數(shù)；ni表示分類i中的成員總數(shù)；nj表示聚類j的所有成員數(shù)。聚類j的F度量FM計(jì)算方式如下：

(23)

F度量值FM(j)可用于衡量來自聚類j中分類i的正確文檔的比例。式(24)則可用于計(jì)算所有聚類K的F度量值：

(24)

準(zhǔn)確率AC用于計(jì)算正確分配至每個(gè)聚類中的文檔比例，表示為：

(25)

式中：n表示所有文檔數(shù)量；K表示文本聚類數(shù)。

5.3 測(cè)試算法說明

文本文檔聚類分析的流程是：首先，對(duì)文本信息進(jìn)行詞語分割、終止詞移除、詞干提取，利用詞條權(quán)重策略計(jì)算詞條權(quán)重值(本文可以根據(jù)傳統(tǒng)TF-IDF方法和改進(jìn)策略NTW分別計(jì)算)，并基于詞條權(quán)重將文本集合表示為向量空間模型；然后，利用融入混沌和對(duì)立學(xué)習(xí)的二進(jìn)制粒子群特征選擇算法COBPSO進(jìn)行最優(yōu)特征子集的選擇，該算法執(zhí)行過程中可以詞條方差法TV和平均中位數(shù)法MM分別作為適應(yīng)度函數(shù)進(jìn)行粒子優(yōu)劣評(píng)估，且還可以分別對(duì)兩種適應(yīng)度評(píng)估下的特征子集作合并和交叉處理，因此，這一過程中有以下幾種算法組合：BPSO-TV、BPSO-MM、BPSO-U和BPSO-I；最后，基于前一步驟中得到的最優(yōu)特征子集，利用經(jīng)典的K均值聚類算法對(duì)文本文檔集合進(jìn)行聚類分析，評(píng)估聚類指標(biāo)。因此，本文可以測(cè)試的相關(guān)算法可總結(jié)于表3的形式。

表3 測(cè)試算法組合

性能對(duì)比算法選擇未作特征選擇的傳統(tǒng)K均值算法、基于遺傳算法的特征選擇算法GAFS[8]和基于傳統(tǒng)二進(jìn)制粒子群算法的特征選擇算法BPSOFS[10]進(jìn)行對(duì)比分析。對(duì)于兩種智能群體算法而言，種群規(guī)模設(shè)置為200，種群個(gè)體進(jìn)化的最大迭代次數(shù)設(shè)置為400，GAFS算法的遺傳交叉概率設(shè)為0.7，遺傳變異概率設(shè)為0.3，BPSOFS算法的粒子慣性權(quán)重最小值設(shè)為0.4，最大值設(shè)為0.9，兩個(gè)學(xué)習(xí)因子均設(shè)置為0.5。

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

圖2所示是在八種測(cè)試數(shù)據(jù)集中，在三種不同的特征選擇策略和不同的詞條權(quán)重計(jì)量方式以及不同的特征子集生成方式下得到的特征選擇量。COBPSO為本文設(shè)計(jì)的融入混沌和對(duì)立學(xué)習(xí)機(jī)制的二進(jìn)制粒子群特征選擇算法，BPSO則為傳統(tǒng)二進(jìn)制粒子群特征選擇算法，GA為基于遺傳的特征選擇算法。詞條權(quán)重計(jì)量可以分別利用TF-IDF和NTW進(jìn)行計(jì)算，特征子集生成時(shí)評(píng)估方式可以通過TV和MM，以及TV與MM的合并或交叉機(jī)制予以進(jìn)行。八種測(cè)試數(shù)據(jù)集覆蓋文本廣泛，可以較好測(cè)試算法對(duì)文本特征降維的適應(yīng)性和穩(wěn)定性。從結(jié)果來看，COBPSO算法的特征降維度效果明顯優(yōu)于BPSO和GA。本文在二進(jìn)制粒子群優(yōu)化中引入對(duì)立學(xué)習(xí)機(jī)制改善初始種群所代表的候選解的質(zhì)量，加速了粒子的尋優(yōu)過程，同時(shí)，利用sinusoidal混沌映射生成混沌序列的方式也可以明顯提升粒子的搜索速度，以及基于適應(yīng)度的粒子慣性權(quán)重調(diào)整方式均起到了對(duì)二進(jìn)制粒子群優(yōu)化的性能改進(jìn)作用，進(jìn)而相應(yīng)提升的特征選擇的準(zhǔn)確性，使得相關(guān)性更好的特征擁有更大的機(jī)會(huì)在尋優(yōu)過程中得以保留。在相同的特征選擇適應(yīng)度評(píng)估方式下，本文的NTW方法可以略微減少特征選擇量，證明新的詞條權(quán)重計(jì)量方法是有效可行的。利用TV和MM兩種特征選擇適應(yīng)度評(píng)估方式在特征選擇量方面并沒有反映出明顯區(qū)別，而特征交叉I是可以有效降低特征選擇量的。特征合并U交沒有明顯增加最終的特征選擇量，這說明兩種特征選擇適應(yīng)度評(píng)估方式TV和MM所生成的特征子集大部分是相交的，均能夠以較高的準(zhǔn)確性選擇出反映文本實(shí)質(zhì)內(nèi)容的特征子集，僅在反映文本類別的區(qū)分能力的特征和相關(guān)性特征上會(huì)出現(xiàn)個(gè)別不同的特征個(gè)體，并不會(huì)相互顛覆文本的最優(yōu)特征子集。

表4為聚類評(píng)估指標(biāo)的比較結(jié)果。表格最右側(cè)的K均值算法表示未使用任何特征選擇的傳統(tǒng)聚類算法，明顯其聚類性能是最差的，這是因?yàn)椴蛔鑫谋咎卣鬟x擇會(huì)導(dǎo)致很多冗余和非信息化特征在聚類過程中被考慮，噪聲太大，聚類準(zhǔn)確性較差。使用BPSO和GA這類群體智能算法進(jìn)行文本特征選擇可以明顯提升文本聚類性能。同時(shí)，比較傳統(tǒng)二進(jìn)制粒子群優(yōu)化和遺傳算法的特征選擇，本文設(shè)計(jì)的基于混沌與對(duì)立學(xué)習(xí)機(jī)制的二進(jìn)制粒子群優(yōu)化特征選擇算法在多數(shù)測(cè)試數(shù)據(jù)集中可以得到更高的準(zhǔn)確率和F度量值，這說明所生成的特征子集準(zhǔn)確度更高，特征空間維度得以有效降低?？傮w而言，新的詞條權(quán)重計(jì)量方式NTW比傳統(tǒng)計(jì)量方式TF-IDF得到的聚類性能也略有上升。利用TV和MM兩種不同的相關(guān)性分值計(jì)算方式后，對(duì)所生成的特征子集作出特征合并或特征交叉后，對(duì)聚類性能也可以產(chǎn)生較積極的影響，各項(xiàng)聚類指標(biāo)均有一定程度提升，說明融合不同評(píng)估方法的特征子集處理機(jī)制是有效可行的。

表4 聚類評(píng)估指標(biāo)對(duì)比

續(xù)表4

圖3是利用K均值算法對(duì)經(jīng)過特征選擇后的文本文檔進(jìn)行聚類所需要的時(shí)間的比較。若不經(jīng)過文本特征選擇，直接以K均值算法進(jìn)行文檔聚類，如結(jié)果所示，其聚類迭代時(shí)間是最短的，但是其文本特征維度沒有降低，且其聚類準(zhǔn)確性較差。此外，利用本文的基于混沌和對(duì)立學(xué)習(xí)機(jī)制的二進(jìn)制粒子群算法的特征選擇后的聚類效率顯然高于另外兩種智能群體算法BPSOFS和GA，這說明對(duì)立學(xué)習(xí)機(jī)制下的粒子群初始化可以有效改善初始粒子的分布，加速粒子尋優(yōu)搜索速度；而融入混沌映射的隨機(jī)粒子搜索機(jī)制也可以提升粒子搜索速度，從而得到最優(yōu)的特征子集，提升聚類效率。同時(shí)，相比傳統(tǒng)的詞條權(quán)重計(jì)量方法TF-IDF，利用本文新提出的詞條權(quán)重計(jì)量方法后，聚類效率略有提升，說明NTW中所考慮的三個(gè)要素對(duì)于定義詞要權(quán)重是具有重要影響的。而在利用相同的詞條權(quán)重計(jì)算方法和相同特征選擇策略下，通過特征合并和特征交叉也可以相應(yīng)提升聚類效率，這說明綜合詞條方差和平均中位數(shù)兩種特征選取標(biāo)準(zhǔn)，可以整合兩者優(yōu)勢(shì)，對(duì)精確選取相關(guān)性更好的最優(yōu)特征子集是有益的。

6 結(jié) 語

本文提出一種基于改進(jìn)二進(jìn)制粒子群優(yōu)化的特征選擇算法。將文本特征選擇建模為粒子最優(yōu)位置的搜索過程，引入對(duì)立學(xué)習(xí)機(jī)制改進(jìn)隨機(jī)種群初始化，并利用混沌映射和基于適應(yīng)度的動(dòng)態(tài)慣性權(quán)重提高粒子尋優(yōu)性能。通過改進(jìn)的二進(jìn)制粒子群優(yōu)化求解最優(yōu)文本特征子集選擇解。同時(shí)，在評(píng)估粒子位置適應(yīng)度過程中，結(jié)合詞條方差和平均絕對(duì)差兩種特征評(píng)估方法的優(yōu)勢(shì)，得到最優(yōu)文本特征子集?；讷@得的最優(yōu)特征子集，進(jìn)一步利用K均值算法對(duì)文本文檔數(shù)據(jù)集進(jìn)行了聚類分析，驗(yàn)證了在所獲文本特征最優(yōu)子集的前提下文本特征維度得到了有效降低，文檔聚類準(zhǔn)確率也得到了極大提升，說明融入混沌和對(duì)立學(xué)習(xí)機(jī)制的二進(jìn)制粒子群優(yōu)化特征選擇算法是行之有效的方法。