融入混沌與對立學習機制的二進制粒子群特征選擇算法

袁明鋒 步中華 王 強

1(重慶輕工職業學院大數據與信息產業系 重慶 401329) 2(青島中石大科技創業有限公司 山東 青島 266580) 3(青島理工大學信息學院 山東 青島 266580)

0 引 言

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

本文提出一種基于改進二進制粒子群優化的特征選擇算法。將特征選擇問題形式化為粒子最優位置的搜索過程，引入對立學習機制對隨機初始化過程做出改進，并利用混沌系統和基于適應度的動態慣性權重提升粒子尋優性能，通過建立的二進制粒子群優化對最優文本特征子集進行選擇與搜索。同時，在評估粒子位置適應度過程中，引用詞條方差和平均絕對差兩種適應度評估方法，得出文本的最優特征子集。基于獲得的最優特征子集，利用K均值算法對文本文檔數據集進行了聚類分析，驗證了在所獲文本特征最優子集的前提下文本特征維度得到了有效降低，文檔聚類準確率也得到了極大提升，有效證明了融入混沌和對立學習機制的二進制粒子群優化特征選擇算法是有效可行的。

1 相關研究

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

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

2 詞條權重計算模型

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

(1)

式中：TF(i,j)表示文檔i中詞條j的頻率；n表示文檔集合文檔總量；DF(j)為包含詞條j的文檔數量；IDF(i,j)為文檔頻率倒數。

本文將利用一種新的詞條權重計算方法NTW，改進思路主要在于：首先，TF-IDF方法中，主要用到詞條的文檔頻率倒數IDF，而忽略了每個詞條的文檔頻率DF，由于當詞條出現在大多數文檔，則DF可以通過增加的權重分值影響其重要性，因此，DF將作為一個參數考慮在新的詞條權重計算中。其次，TF-IDF方法忽略了文檔中所有詞條的數量，該參數有助于選擇較少數量的信息化特征。最后，最大詞條頻率可用于區分文檔詞條，若文檔包含大量詞條，則表明詞條特征重要性要小于少數量詞條的情形。基于以上三個因素的考慮，改進詞條權重計算方法NTW定義為：

(2)

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

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

(3)

3 二進制粒子群優化算法

粒子群算法是受鳥類、魚群社會行為啟發得到的一種元啟發式算法。粒子群中的個體稱為一個粒子，種群由S個粒子構成，每個粒子代表在d維空間內的一個候選問題解。粒子i在d維空間內的位置向量為Xi=(xi1,xi2,…,xid)，粒子速度向量為Vi=(vi1,vi2,…,vid)。所有粒子在搜索空間內移動以尋找其全局最優解，粒子的移動會受到自身已知的個體最優位置pbest和種群的已知全局最優位置gbest的影響。粒子i的個體最優位置可表示為pbesti=(pbesti1,pbesti2,…,pbestid)，種群的全局最優位置可表示為gbesti=(gbest1,gbest2,…,gbestd)。粒子位置優劣由預定義的適應度函數評估。粒子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]內均勻分布的隨機數；c1和c2分別為認知權重因子和社會權重因子，通常固定取值在[0,2]之間；w為[0,1]間的慣性權重，用于控制粒子先代速度的影響。較大慣性權重w利于粒子對新區域的全局勘探，較小慣性權重w利于粒子的局部開發，因此，慣性權重可以均衡全局勘探和局部開發過程。

傳統粒子群優化算法是連續空間內的粒子群算法，即粒子位置可在連續空間位置上移動。對于特征選擇問題而言，當以粒子位置代表特征選擇解時，單個特征是否被選擇僅有選擇與不選擇兩種情形，因此，粒子位置僅有兩種取值情形，此時可以二進制形式定義粒子位置。粒子位置更新代表對應位置比特值的改變，粒子速度則代表粒子位置改變為1的概率。利用S形函數將連續位置信息映射為二進制位置信息。速度的S形函數定義為：

(6)

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

(7)

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

4 基于混沌和對立學習的二進制粒子群優化特征選擇算法COBPSO

4.1 特征選擇模型

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

4.2 特征選擇解編碼

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

表1 特征選擇解編碼結構

4.3 適應度函數

適應度函數用于計算文檔中的特征相關性分值，即為評估個體粒子位置所代表的特征選擇解的優劣。本文引用兩種特征相關分值計算方法，一種是詞條方差法TV，一種是平均中位數法MM。

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

(8)

(9)

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

(10)

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

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

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

FS3=FS1∪FS2

(11)

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

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

FS4=FS1∩FS2

(12)

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

4.4 基于對立學習機制的粒子種群初始化

傳統元啟發式算法以隨機方式生成初始種群，然后逐步迭代接近全局最優解改善種群個體，其搜索過程在滿足預定義終止條件時結束。因此，算法的收斂速度與初始種群與最優解間的距離直接相關。最差情形中，最優解離隨機初始種群較遠，則搜索尋優可能無法完成。對立學習可以通過同步考慮當前解及其對立解改善候選解的質量，收斂速度可以通過同步考慮當前解及其對立解予以改善。研究表明，約50%隨機初始解會比其對立解離最優解更遠。因此，將隨機初始解及其對立解聯合考慮在初始種群中，可以加快搜索收斂速度。

定義1對立數。令x為區間[l,u]內的實數，x∈[l,u]，其對立數x′為：

x′=u+l-x

(13)

基于對立學習的種群初始化步驟如算法1所示。

算法1對立學習機制的粒子種群初始化

輸入：種群規模S。

輸出：規模S的粒子集合X。

1.隨機生成粒子數為S的初始種群{X}；

2.fori=1 toSdo

//所有粒子上遍歷

3.forj=1 toddo

//所有位置維度上遍歷

//粒子位置的對立點

5.endfor

6.endfor

7.X″=X∪X′

//融合原始粒子和對立粒子為新種群

8.計算新種群X″中粒子的適應度；

9.根據適應度對X″中的粒子作降序排列；

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

11.返回初始種群X。

4.5 基于適應值的動態慣性權重機制

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

(14)

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

(15)

(16)

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

由于需要尋找更高聚類內相似度和更低聚類間相似度的粒子聚類，因此，適應值更高的粒子應優先選擇。換言之，基于適應值的動態慣性權重將分配高慣性權重至低適應值粒子，促進該類粒子在搜索空間內對未知區域的全局勘探；而會分配低慣性權重至高適應值粒子，促進該類粒子在搜索空間內作進一步局部開發。因此，粒子慣性權重將依據粒子當前的適應值與當前最優適應值進行計算：

(17)

式中：fiti為粒子i的適應值；fitbest為全局最優粒子gbest的適應值。基于動態慣性權重，粒子的速度更新可改進為：

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

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

(18)

由式(18)可知，融入適應值的動態慣性權重至粒子速度更新可以根據粒子當前狀態動態調整粒子速度，較大的慣性權重可以增加較低適應值粒子的速度步長，促進其搜索空間內的全局勘探過程；而較小的慣性權重可以減小較高適應值粒子的速度步長，促進其搜索空間內的局部開發過程。

4.6 基于對立學習的學習因子調整

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

4.7 基于混沌理論的隨機搜索機制

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

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

(19)

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

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

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

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

(20)

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

算法2改進二進制粒子群優化特征選擇算法COBPSO

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

輸出：全局最優粒子gbest。

1.算法相關參數初始化；

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

3.利用算法1的對立學習機制生成粒子初始種群；

4.搜索個體最優pbest、全局最優gbest和全局最差gworst；

5.whilenot satisfy maximum iterationsdo

//若干次迭代尋優

6.forp=1 toSdo

//所有粒子上遍歷

7.根據式(17)計算自適應慣性權重值；

8.ifcount>δandxpisgworstthen

9.設置不均等學習因子(c1,c2)；

10.else

11.設置均等學習因子(c1,c2)；

12.endif

13.forq=1 toddo

//所有位置維度上遍歷

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

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

16.根據式(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全局最優粒子gbest未發生變化then

31.count=count+1；

32.else

33.count=0；

34.endif

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

36.ifcount<δthen

37.對全局最差粒子gworst作變異；

38.else

39.對全局最差粒子gworst作對立學習更新；

40.endif

41.endwhile

42.return最優粒子gbest作為最優特征選擇子集。

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

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

5 實驗與結果分析

5.1 測試文本說明

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

表2 測試文檔數據集

續表2

5.2 評估標準

利用F度量FM和準確率AC兩個主要指標度量特征選擇后的文本聚類性能。F度量根據給定的分類標簽通過計算精確率P和召回率R計算，分別表示為：

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

(21)

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

(22)

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

(23)

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

(24)

準確率AC用于計算正確分配至每個聚類中的文檔比例，表示為：

(25)

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

5.3 測試算法說明

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

表3 測試算法組合

性能對比算法選擇未作特征選擇的傳統K均值算法、基于遺傳算法的特征選擇算法GAFS[8]和基于傳統二進制粒子群算法的特征選擇算法BPSOFS[10]進行對比分析。對于兩種智能群體算法而言，種群規模設置為200，種群個體進化的最大迭代次數設置為400，GAFS算法的遺傳交叉概率設為0.7，遺傳變異概率設為0.3，BPSOFS算法的粒子慣性權重最小值設為0.4，最大值設為0.9，兩個學習因子均設置為0.5。

5.4 實驗結果

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

表4為聚類評估指標的比較結果。表格最右側的K均值算法表示未使用任何特征選擇的傳統聚類算法，明顯其聚類性能是最差的，這是因為不做文本特征選擇會導致很多冗余和非信息化特征在聚類過程中被考慮，噪聲太大，聚類準確性較差。使用BPSO和GA這類群體智能算法進行文本特征選擇可以明顯提升文本聚類性能。同時，比較傳統二進制粒子群優化和遺傳算法的特征選擇，本文設計的基于混沌與對立學習機制的二進制粒子群優化特征選擇算法在多數測試數據集中可以得到更高的準確率和F度量值，這說明所生成的特征子集準確度更高，特征空間維度得以有效降低。總體而言，新的詞條權重計量方式NTW比傳統計量方式TF-IDF得到的聚類性能也略有上升。利用TV和MM兩種不同的相關性分值計算方式后，對所生成的特征子集作出特征合并或特征交叉后，對聚類性能也可以產生較積極的影響，各項聚類指標均有一定程度提升，說明融合不同評估方法的特征子集處理機制是有效可行的。

表4 聚類評估指標對比

續表4

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

6 結 語

本文提出一種基于改進二進制粒子群優化的特征選擇算法。將文本特征選擇建模為粒子最優位置的搜索過程，引入對立學習機制改進隨機種群初始化，并利用混沌映射和基于適應度的動態慣性權重提高粒子尋優性能。通過改進的二進制粒子群優化求解最優文本特征子集選擇解。同時，在評估粒子位置適應度過程中，結合詞條方差和平均絕對差兩種特征評估方法的優勢，得到最優文本特征子集。基于獲得的最優特征子集，進一步利用K均值算法對文本文檔數據集進行了聚類分析，驗證了在所獲文本特征最優子集的前提下文本特征維度得到了有效降低，文檔聚類準確率也得到了極大提升，說明融入混沌和對立學習機制的二進制粒子群優化特征選擇算法是行之有效的方法。