改進的粒子群算法優化的特征選擇方法

李 煒，巢秀琴

1.安徽大學 計算機科學與技術學院，合肥 230601

2.安徽大學 計算智能與信號處理教育部重點實驗室，合肥 230601

1 引言

特征選擇問題也稱特征子集選擇問題，是指從已有的M個特征中選擇N個特征使系統特定目標最優，從而降低數據維度，提高學習算法性能[1]。近年來，隨著數據挖掘、機器學習和計算科學等領域的發展，越來越多高維數據集應用于各個領域的信息系統之中，例如金融分析、商業管理和醫療研究等領域[2]。高維數據集帶來的維度災難使得數據處理的復雜程度急劇增加，因此刪減多余或信息量少的特征，選擇出最優的特征子集將大大提升后續學習算法的效率[3]。

特征子集選擇方法可分為嵌入式（embedded）、過濾式（filter）和封裝式（wrapper）三種。嵌入式方法將特征選擇過程嵌入到學習模型中，作為訓練過程的一個部分，而不是將數據集分為訓練集和測試集[4]。過濾式方法中，所有特征按照特定的統計或數學屬性進行排序，例如特征對類的可分性或者熵值[1]，最后根據排序選擇特征子集[4]。封裝式方法則是通過學習算法對候選的特征子集進行評價，并通過多次迭代改變候選特征子集，然后根據分類精度和特征數等評價標準選擇最優特征子集[5]。

假設數據集中有n維特征，則全部搜索空間大小為2n，故特征選擇問題是一個NP-hard問題[6-7]。因此，窮舉搜索最優特征子集將會耗費大量計算和時間成本，不適用于解決大量高維數據集的特征子集選擇問題。同時，由于啟發式搜索算法的自身優勢，一次運行就得到一組解，能夠耗費較小時間和計算成本搜索到理想的解集，近年來越來越多基于啟發式算法的特征選擇方法被提出來，用于解決特征選擇問題，并取得很好的效果[8]。例如遺傳算法（genetic algorithm，GA）[9]、蟻群算法（ant colony algorithm，ACO）[10]、人工蜂群算法（artificial bee colony algorithm，ABC）和粒子群優化算法（particle swarm optimization algorithm，PSO）[11]等。其中，粒子群優化算法[12]由于其收斂速度快，搜索能力強的優點受到諸多學者關注并提出了大量改進算法。文獻[13]提出了基于粗糙集的PSO算法來搜索最優特征子集，并得出結論：基于PSO的特征選擇方法比基于GA的方法能更有效地解決特征選擇問題。文獻[14]提出一種新的變異策略改進PSO算法，通過隨機翻轉粒子的位置，避免算法陷入局部最優。文獻[15]提出基于PSO和粗糙集特征選擇技術結合的方法，解決腦-機接口運動圖像研究中的特征降維問題，實驗結果顯示，將該方法選擇出來的特征子集應用于提出的多類運動圖像分類的領域粗糙集分類器方法中，取得良好效果。文獻[16]提出一種基于多目標粒子群優化算法的特征排序方法，將特征頻率進行存檔并引導粒子進化，在9個基準數據集上進行測試性能，取得了理想效果。文獻[17]基于粒子群優化算法和邏輯回歸模型，提出將貝葉斯信息準則作為適應度函數，在大量數據集上進行實驗，實驗結果顯示該方法顯著提高了分類性能并減少了特征數目。

同時，一些學者還將PSO與不同的分類器結合來解決特征選擇問題。文獻[18]提出PSO與支持向量機（support vector machine，SVM）結合的特征選擇方法，并通過使用Web服務技術的分布式體系結構來減少時間成本。文獻[19]提出一種基于改進PSO的過濾-封裝特征選擇方法來解決圖像處理中的特征選擇問題。該方法分為兩個階段：在第一個階段中，采用兩種典型的過濾式技術，t檢驗和多元回歸，根據特征識別能力選擇圖像；第二階段則通過在PSO算法中動態改變種群規模，并采用SVM作為分類進行特征測試。實驗結果表明，該方法能夠顯著提高分類精度且降低特征維度。文獻[20]在解決癌癥分類問題時，首先通過快速相關特征選擇（fast correlationbased feature selection，FCBC）方法對不相關和冗余特征進行過濾，后期采用PSO對SVM進行優化操作。在9個癌癥數據集上的實驗結果顯示，該文獻提出的PA-SVM在處理復雜非線性問題時具有良好的靈活性和適應性。文獻[21]提出將GA與PSO相結合的方法用于解決醫學診斷中的特征選擇問題。首先利用GA來選擇特征子集，然后利用PSO對SVM的參數進行優化。由于PSO在搜索合適的連續變量方面表現出優勢，最終在UCI數據進行實驗，結果顯示，該文獻中提出的混合方法比單一算法更能夠為SVM選擇最佳的支持向量機模型參數和更具相關性的特征子集，從而進一步提高了醫療診斷問題的分類性。文獻[22]在二進制粒子群優化算法中提出新的初始化策略和更新策略，且該方法使用K近鄰（Knearest neighbor，KNN）作為分類器。文獻[23]在對離散的共生體搜索算法（symbiotic organisms search，SOS）進行相關改進時，其中一種采用了BPSO（binary particle swarm optimization）與SOS結合的方式，使用KNN作為分類器，通過分類精度和計算時間來評價算法性能，在多個數據集上進行對比實驗的結果顯示，改進后的算法性能顯著提升。

另一方面，除了啟發式搜索算法，近年越來越多研究者提出圖論與社團檢測算法結合來解決特征選擇問題[24]。首先，將特征集表示為一個無向帶權圖，圖的頂點表示不同的特征，邊的權重值則反映出特征之間的相似性，且權值通過一些統計指標來計算，如皮爾森相關系數等[25]。然后使用社團檢測算法將圖中特征頂點劃分為不同的簇，同一個簇中的特征相似性較大，而不同簇中的特征之間相似性則相對較小。

本文組織結構如下：第2章對BPSO算法步驟進行介紹，然后提出本文算法的改進；第3章介紹本文算法框架的具體過程；第4章介紹文中使用的數據集、相關實驗參數的設置，并對算法的各個改進模塊的有效性進行實驗論證，并將改進后的算法與當前代表性優化算法進行對比實驗；第5章總結全文。

2 BPSO算法

BPSO算法是Kennedy于1997年在連續性PSO算法基礎上提出的，用于解決離散的優化問題[26]。BPSO算法通過模擬鳥類飛行覓食過程，種群中每個粒子相當于解空間中的一個解，粒子具有速度和位置兩個屬性，位置向量表示該粒子對應的解，速度向量則是為了調整粒子下一次飛行，從而進行位置更新搜索新的解集。粒子飛行過程中根據自己的歷史飛行經驗和種群中其他粒子的飛行經驗調整自身的飛行方向和速度。其中，每個粒子歷史飛行過程中的最優位置稱為個體最優解pbest，整個種群在歷史飛行過程中所經過的最好位置為gbest，稱為全局最優解[26]，粒子之間通過pbest、gbest共享信息，從而在進化過程中影響種群的搜索行為。

2.1 種群初始化

2.2 粒子速度與位置更新

任意粒子i(i=1,2,…,N)根據式（1）更新速度向量：

其中，ω表示慣性權重，衡量粒子學習過程中上一代粒子對當代粒子的影響權重；c1、c2表示學習因子；rand1、rand2表示0～1之間的隨機數。

其中，rand是0～1之間的隨機數。

2.3 種群評價

對于種群中的每一個粒子，用適應度值來評價該粒子對應的解的優劣。任意粒子i(i=1,2,…,N)，計算對應的適應度值為Fitness(i)。

得到種群每一個粒子的適應度值之后，判斷粒子在對應個體飛行過程以及種群飛行過程中的優劣。若粒子i適應度值比粒子i歷史最優pbesti對應的適應度值更好，則粒子i搜索到當前飛行過程歷史中的最優位置，故用粒子i位置向量來更新pbesti向量；否則，pbesti向量保持不變。同理，若粒子i適應度值比種群全局最優gbest對應的適應度值更好，則粒子i搜索到整個種群在當前飛行歷史中的最優位置，故用粒子i的位置向量更新gbest向量；否則，gbest向量保持不變。

2.4 算法終止條件

如果滿足最大迭代次數，則終止算法并輸出最優解gbest對應的特征選擇方案。否則，返回2.2節進行下一次迭代操作。

3 算法設計

3.1 改進的種群初始化策略

初始化種群的優劣對BPSO算法后續搜索性能具有很大影響[22]，因此大量研究者在改進BPSO算法解決特征選擇問題的時候，也提出了新的種群初始化策略，后續實驗結果也證明這些初始化策略能有效提高BPSO算法搜索更優質特征子集。文獻[27]提出用非線性單純形法產生初始種群，通過在14個標準測試函數上進行檢測實驗，表明該初始化方法在數據維度較低情況下能夠明顯提高BPSO算法性能。對于高維特征選擇問題，文獻[28]在PSO算法中提出基于中心旋渦的初始化策略，該策略的目標是降低初始化粒子的特征數目，從而減少每次評價的計算成本。而文獻[29]則認為在初始化過程中均勻分布的粒子可以提高PSO算法性能。同時比較了三種不同的初始化策略，即正交矩陣初始化策略、基于混沌技術的初始化策略和反向初始化策略，這三種初始化策略對于不同的特征選擇問題有不用的效果。文獻[22]則基于傳統的初始化方法提出三種新的初始化策略：最大初始化、最小初始化及混合初始化。明顯提高了PSO算法性能。

基于初始化策略對于BPSO算法的重要性及特征選擇問題的具體性，本文提出了一種基于特征聚類信息的種群初始化策略，從而得到更理想的初始化種群。

3.1.1 預處理

對數據集標準化處理：實驗結果證明特征值的標準化可以提高分類精度，因此在預處理過程中需對數據集作標準化處理，將數據集中每一維特征值縮放到-1到1之間[3]。對于M維特征，n個樣本的數據集，任意一維特征i在第j個樣本中對應取值為xij，按式（4）得到標準化后的取值xij′:

其中，ximax表示特征i在所有樣本中的最大取值，ximin表示特征i在所有樣本中的最小取值。

3.1.2 特征鄰接圖

在圖論中，系統中兩個元素或多個元素之間的關系可由圖來表示[30]。其中，一個圖G={V,E,W}的結構由點集V、邊集E和每條邊的權重W構成[31]。

在特征選擇問題中，每個頂點可對應表示一個特征，每條邊表示兩個特征之間的關系，且每條邊的權重取值則對應兩個特征之間的關系強度。本文基于特征之間信息的共性，確定特征F1與特征F2之間的相似性。且對于特征F1與特征F2，應用皮爾森相關系數（Pearson's correlation coefficient，PC）來衡量這兩個特征之間的相似性，皮爾森相關系數（PC）按照式（5）計算：

其中，SN表示數據集中的樣本個數。

根據所有特征之間的皮爾森相關系數，構成特征的PCC矩陣，矩陣中每一個元素PCCij表示特征i與特征j之間的皮爾森相關系數。本文應用中位數切割策略，由PCC矩陣得到特征之間的鄰接矩陣（Neighbor）用于后續社團檢測進行特征分組。PCC中所有元素的中位數（Med）作為閾值，對于PCC矩陣中任意元素PCCij，若PCCij≥Med，則對應的Neighborij=1；否則，若PCCij＜Med，則Neighborij=0。由此，得到與PCC矩陣大小相同的Neighbor矩陣，且Neighbor矩陣所有元素取值為0或1，取值為0表示在特征鄰接圖中，對應兩個特征頂點之間沒有邊相連，取值為1則表示對應兩個特征頂點之間有邊相連。

3.1.3 特征分組

社團結構是網絡中的重要模塊之一，通過社團檢測識別網絡中的社團有助于理解網絡中的復雜關系[32]。社團檢測的目的是將網絡中相似性大的頂點聚類為一個社團，從而與其他頂點區分開，同一社團內的頂點具備相似的屬性，相似性較大。因此，在特征選擇問題中，通過社團檢測算法將特征網絡按照相似性進行劃分，同一個社團中的特征相似性大，不同社團中的特征相似性較小。

其中，Louvain社團檢測算法是一種簡單高效的社團檢測方法，該算法通過最大化模塊函數來實現網絡中的社團檢測[33]。本文應用Louvain社團檢測方法對特征網絡進行特征聚類，基于PCC矩陣，將特征按照相似性劃分為不同的特征聚類{community1,community2,…,communitycNum}，其中，cNum為聚類數目。

3.1.4 種群初始化

數據集維度為D，種群大小為N。種群中每個粒子表示特征選擇問題中的一個解，即代表一種特征選擇方案。本文采用二進制編碼，粒子的每一維取值只能為0或1，取值為0表示對應維度的特征未被選擇；相反，取值為1則表示對應維度的特征被選擇。因此，每個粒子中所有取值為1的維度代表的特征構成該粒子對應的特征選擇方案。每個粒子的具體初始化方式如下：

首先初始化每個粒子對應的特征數目Pi(i=1,2,…,N)，為了控制初始粒子的特征數目，Pi取值不超過總特征數的60%，即|Pi|＜60%×D。Pi個特征分別從各個特征分組中隨機選擇：如果Pi≤cNum，則隨機選擇|Pi|個不同的特征分組，并從每個分組中隨機選擇一個特征。如果Pi＞cNum，則先從所有特征分組中隨機選擇一個特征放入粒子中，剩余(PicNum)個特征再次從各特征分組中隨機選擇。

3.1.5pbest與gbest初始化

對于種群中的每一個粒子i(i=1,2,…,N),初始pbesti就是粒子i本身，而初始gbest則記錄為種群中第一個粒子。

3.2 粒子速度與位置更新

本文算法中，粒子速度更新與BPSO算法一致，即每個粒子的速度與位置按照2.2節介紹的更新方式進行操作。

3.3 交互操作

眾所周知，BPSO算法的收斂性很強，但后期搜索容易陷入局部最優，即粒子之間相似性增大，算法搜索性能受到極大限制。因此本文根據種群進化過程中粒子在決策空間中的相似性來對粒子進行自適應的交互操作：粒子在種群中相似性大，則相應粒子進行交互的概率大；反之，粒子進行交互的概率小。進行交互操作的目的是從決策空間的角度，增加種群中粒子的多樣性，從而避免算法陷入到局部最優狀態，提高搜索性能。交互操作過程如下：

3.3.1 定義粒子相似

本文定義了基于粒子在決策空間中的相似性指標衡量粒子在種群中的相似性，對于粒子i(i=1,2,…,N)，判斷其與種群中其他粒子j(i=1,2,…,N|j≠i)的相似性規則如下：

其中，Fi、Fj分別表示粒子i與粒子j對應的特征子集。因此，S1表示Fi、Fj共有的特征結合，S2表示僅在Fi中存在且不在Fj中存在的特征集合。

本文實驗中，若|S1|≥0.6且|S2|≤0.4，則判定粒子j是粒子i的相似粒子，由此統計出種群中所有粒子i的相似粒子集合simi。

同時，定義指標Coni來衡量種群其他粒子j(j=1,2,…,N且j≠i)中特征與粒子i中特征的重合程度，Coni按照式（6）計算：

Coni的值越大，表明粒子j與粒子i的公共特征數目占粒子i中特征數目的比例越大，則粒子j對于粒子i的包含程度越高。由于粒子群優化算法進化后期，粒子之間相似性增大，則粒子之間的包含程度也隨之增大。因此，本文實驗中將通過選擇種群中與當前粒子包含程度最小的粒子來進行交互操作，從而增大種群的多樣性，避免算法過早收斂。

3.3.2 計算相似性指數

對粒子i(i=1,2,…,N)，相似性指數按式（7）計算：

3.3.3 交互操作

進行交互操作之前，首先按照式（8）計算粒子i的交互概率Interratei：

由式（8）可知，隨著粒子在決策空間中的相似性增大，粒子的交互概率也隨之增大，從而進一步增大后期對相似性較大的粒子的擾動力度，降低種群中粒子的相似性，避免種群搜索陷入局部最優。

對任意粒子i(i=1,2,…,N)，用隨機函數產生隨機數randi，若randi≤Localratei，則需對粒子i進行交互操作。交互操作規則如下：

（1）根據指標Coni對應的最小值，找出粒子i的交互粒子j。

（2）將粒子i與粒子j中元素“1”所對應的特征序號分別提取出來，構成臨時交互父代個體Pti與Ptic，如果Pti與Ptic維度不相同，則在維度小的臨時父代中隨機補充0元素直到兩個父代個體維度相同為止。

（3）隨機產生交互位置，從交互位置開始進行判斷：首先判斷Ptic對應位置的特征是否存在于Pti中，如果該特征不在Pti中存在，則繼續產生隨機數rand，若rand≤Localratei，則交換Pti與Ptic中對應位置的特征，完成該位置的交互操作。除此之外所有情況下，臨時父代個體Pti與Ptic均不進行交互操作，直到Pti的最后一維判斷結束。

（4）對Pti進行交互操作之后，得到新的粒子Pti′，最終需將其轉化為二進制編碼形式。轉化過程如下：首先將粒子i的每一個維度初始取值均設置為“0”。然后在粒子i中，將所有Pti′的非零元素對應的位置取值重置為“1”，得到新的粒子i′。

對種群粒子之間進行交互操作之后，需進一步對種群中的粒子進行自我調整操作，避免粒子內部的特征高度集中于單個或極少特征聚類中，造成特征之間的信息冗余。粒子的自我調整過程如下：

（1）統計每個粒子中的特征所在的特征聚類信息：Gi={g1,g2,…,ginum}，其中，ginum表示粒子i中出現的聚類數目。

圖1為粒子i的交互操作過程實例。

3.4 種群評價

Fig.1 Interaction process of particlei圖1 粒子i的交互操作過程

種群更新之后，需對更新后的種群進行評價。由于特征選擇的最終目標是在減少特征數目的同時，保留有效特征，從而保證后續學習算法的學習性能不受影響。因此在各種特征選擇算法中，應用不同的分類器來評價特征子集的質量，如：支持向量機（SVM）[29]、K近鄰分類器（KNN）[34]等。

本文實驗中，在對數據集進行標準化操作之后，將其劃分為訓練集和測試集：70%數據樣本作為訓練集，30%數據樣本作為測試集。訓練過程中，通過使用5-NN分類器并采用十折交叉驗證（10-fold cross validation method）[35]計算種群中的每一個粒子所代表的特征子集選擇方案的分類錯誤率和特征數目，并計算粒子的適應度值對粒子進行評論。算法最后，在測試集上對粒子進行測試得到算法的最終結果。分類錯誤率按式（9）計算：

其中，FP表示負樣本被預測錯誤的個數，FN表示正樣本被預測錯誤的個數，TP表示正樣本被預測正確的個數，TN表示負樣本被正確預測的個數。

本文采用分類錯誤率與特征數目的加權和作為適應度函數，用于評價種群中的每一個粒子的優劣。對于粒子i(i=1,2,…,N)，按照式（10）計算其適應度函數值：

其中，ErrorRate(i)表示粒子i的分類錯誤率，FeatureNum(i)表示粒子i對應的特征數目。

得到種群中每一個粒子適應度函數值之后，對pbest與gbest進行更新，對于任意粒子i(i=1,2,…,N)，更新策略如下：

（1）若Fitness(pbesti)＜Fitness(i)，則不更新對應的pbesti；若Fitness(pbesti)＞Fitness(i)，則用粒子i更新對應的pbesti；若Fitness(pbesti)=Fitness(i)，則比較pbesti與粒子i的特征數目，將特征數少的作為pbesti。

（2）若Fitness(gbest)＜Fitness(i)，則不更新gbest；若Fitness(gbest)＞Fitness(i)，則用粒子i更新gbest；若Fitness(gbest)=Fitness(i)，則比較gbest與粒子i的特征數目，將特征數少的作為gbest。

3.5 更新種群

交互操作和自我調整操作結束后得到新的種群構成新一代種群，并按照3.3節評價種群更新pbest和gbest。

圖2為本文算法流程圖。

Fig.2 Flow chart of BPSOBCI圖2BPSOBCI算法流程圖

4 實驗

為證明本文改進策略的有效性和改進后算法的優越性，設置兩組對比實驗。第一組對比實驗分別驗證本文提出的基于特征聚類信息的初始化策略的有效性及基于粒子在決策空間中密度的交互操作的有效性。第二組對比實驗則將本文改進后的特征選擇算法與三個具有代表性的特征選擇算法進行對比，驗證本文算法的優越性。

4.1 實驗參數設置

本文所有對比實驗均在內存10.0 GB的PC機上運行，運行環境為Matlab R2016b。所有算法均使用五近鄰算法（5-NN）作為分類器評價種群中粒子所代表的特征選擇方案的優劣，且種群大小設置為40，學習因子c1=c2=2，慣性權重ω=0.9，粒子最大速度vmax=4，最小速度vmin=-4。

表1所示為本文實驗采用的11個UCI數據集信息，其中包括二分類及多分類數據集，特征數目最少為13，最多為309。

Table1 Information of datasets表1 數據集信息

4.2 閾值φ取值實驗

由于閾值φ的作用是判斷粒子內部特征是否過于集中于相關特征聚類中的標準，且不必要的冗余特征將對分類性能產生不良影響。若閾值φ取值過大，則粒子進行自我調整的力度也將增大，過大的擾動操作會直接影響搜索穩定性。相反，若閾值φ取值過小，則粒子進行自我調整的力度相應減小，過小的擾動操作，將無法發揮調整作用。因此，閾值φ的選擇應當兼顧穩定性和擾動合理性，本文在進行后續實驗之前，首先對閾值φ的取值進行了相關實驗，進一步對閾值進行選擇。

實驗分別在11個數據集上進行10次獨立運行實驗，每次運行最大迭代次數為100。所有取值性能均由最終平均特征數及平均分類錯誤率作為各個取值的性能評價標準。表2所示為閾值φ分別取0.1、0.2、0.3、0.4、0.5、0.6及0.7時的實驗結果，其中，加粗字體表示各個數據集上進行實驗所得到的最小平均錯誤率及最小特征數。

由表2的實驗結果顯示，φ取值為0.5時，在所有數據集上都得到了最小的平均分類錯誤率。其中，在特征數較多的幾個數據集上，φ取0.5時取得的結果優勢尤其明顯。具體對其中3個數據集進行分析，LVST數據集有309個特征，φ取值為0.5時，平均分類錯誤率為0.088 5，比φ取值0.6時，錯誤率降低2.5%的同時，平均特征數減少了5.1。與φ取0.1的情況相比，平均特征數雖然只減少了0.4，但平均分類錯誤率卻降低了17.6%。在Musk1數據集上，φ取值0.5時，平均錯誤率為0.108 2，比φ取值0.4時得到的0.113 8降低了4.92%，平均特征數也減少了0.5。φ取值0.6時，雖然平均特征數只相差0.3，但平均分類錯誤率同時降低了12.17%。Hillvalley數據集上，φ取值0.5時，得到平均分類錯誤率為0.414 9，比φ取值0.2時得到的0.416 7降低了0.43%，平均特征數減少了1.8。除了在Ionosphere數據集上，φ取值0.5未得到最小的平均特征數之外，在其他所有數據集上，均可以得到最小的平均特征數。

基于不同的特征規模，特征聚類后，采用閾值φ來衡量每種特征選擇方案中特征的聚集程度，從而靈活地對粒子進行相應調整。實驗結果證明，綜合分類錯誤率和特征數兩個指標上的表現，φ取0.5均得到了最好的結果。也說明了在特征規模不定的情況下，φ取0.5能夠更有效地平衡特征選擇過程中的穩定性及該策略的有效性，從而提高算法的整體性能。因此，在后續相關實驗中，閾值φ的取值均設為0.5。

4.3 策略驗證實驗結果分析

為驗證本文提出的初始化策略及交互操作能夠有效提高粒子群優化算法的性能，本文在第一組實驗中，除了BPSO之外，將基于特征聚類信息的初始化策略及基于粒子決策空間密度的交互操作分別加入粒子群算法中，得到基于聚類信息的BPSO（binary particle swarm optimization based on cluster，BPSOBC）、基于交互策略的BPSO（binary particle swarm optimization based on interaction，BPSOBI）及基于聚類信息和交互的BPSO（binary particle swarm optimization based on cluster and interaction，BPSOBCI）。4個算法分別在上述11個數據集上進行實驗，算法最大迭代次數為200，根據算法適應度值的變化趨勢來評價算法的收斂和搜索性能，從而驗證本文提出的兩個策略的有效性。

圖3所示為BPSO、BPSOBC、BPSOBI和BPSOBCI分別在11個數據集上進行對比實驗的結果。其中，X軸坐標表示迭代次數，Y軸坐標表示適應度函數值。從圖3中折線圖趨勢可以看出，隨著算法迭代次數的增加，適應度值均在降低，但相較于BPSO，BPSOBC和BPSOBI在搜索次數相同的情況下，搜索到適應度值更小的粒子。而BPSOBCI則能夠在11個數據集上搜索到比其他3種算法更優質的粒子。這充分驗證了本文所提出的兩個改進策略的有效性。

對策略效果進行具體分析，如圖3結果顯示，在BPSO基礎上加入基于特征聚類信息的初始化策略之后，在11個數據集上，BPSOBC均可以在初始情況下，降低種群的適應度值。其中，對于Hillvalley數據集，BPSO得到初始種群gbest對應的適應度值為0.459 1，而BPSOBC的初始值為0.363 3。在數據集Musk1上，BPSO得到初始種群gbest對應的適應度值為0.233 0，而BPSOBC得到的值為0.185 1。對于LVST數據集，BPSO得到初始種群gbest對應的適應度值為0.216 5，BPSOBC得到的值則為0.172 2。在這3個數據集上，BPSOBC得到初始適應度值明顯降低。Hillvalley數據集的特征數為100，Musk1數據集的特征數為166，LVST數據集的特征數為309，特征數目較多時，社團檢測算法能夠更加靈敏地將特征劃分為多個特征聚類，從而對特征進行更精確的區分。也正是由于這個原因，Wine數據集特征數目只有13，特征數目過少，社團劃分算法對特征進行聚類的效果不明顯，在控制特征數目的基礎上，再采用聚類結果對特征進行選擇，會導致特征中有效信息的損失。因此BPSOBC在特征規模較小時，適應度值沒有高維特征集中同樣顯著的優勢。但從總體上說，只有Wine是BPSOBC在11個數據集上唯一沒有得到明顯優質初始種群的數據集，因此本文提出的基于特征聚類信息的初始化策略雖然有損失有效信息的可能性，但總體表現穩定。迭代200次之后，BPSOBC在11個數據集上得到的解的適應度值均比BPSO更小，這顯示BPSOBC得到優質的初始化種群之后，經過進化算法能夠搜索到更理想的結果。綜合11個數據集的實驗結果，充分驗證了本文提出的基于特征聚類信息的初始化策略能夠減少冗余特征的同時提高分類性能，明顯提升BPSO的性能。

分析BPSOBI的實驗結果，圖3實驗曲線顯示，BPSOBI在大部分數據集上進行200次迭代后得到的適應度值比BPSO要小。本文提出交互操作的目的在于通過粒子在決策空間中的密度對密度過大的粒子進行交互操作，避免種群陷入局部最優，從而增強種群的搜索性能。在圖3實驗圖中，BPSOBI在11個數據集上均能夠在很少的迭代次數下搜索到比當前適應度值更小的粒子，體現出BPSOBI較強的全局搜索能力及收斂性。在Hillvalley數據集上，BPSOBI的初始gbest對應的適應度值為0.425 2，迭代20次后，搜索到的gbest適應度值為0.396 5，迭代30次后，搜索到的gbest適應度值進一步降低為0.386 9的粒子，迭代40次后，再一次搜索到比當前適應度更小的粒子，說明算法具備良好的收斂性能。迭代100次后，BPSO、BPSOBC和BPSOBI實驗曲線不再變動，算法搜索陷入局部最優狀態，而BPSOBI在第150次迭代時仍搜索到適應度值為0.367 6的粒子，最終得到的gbest適應度值也比BPSO小，表現出BPSOBI具備較強的全局搜索能力。同樣的，在Spectf數據集上，BPSOBI的搜索性能則得到更好的驗證，初始gbest對應的適應度值為0.266 0，迭代30次后，gbest適應度值迅速下降到0.218 4。而算法迭代30次后，BPSO的gbest適應度值由初始的0.201 4降低到0.187 2，適應度值的降低幅度遠小于BPSOBI，表現出BPSOBI的優秀收斂性能。且后續搜索中，BPSO和BPSOBC實驗結果曲線變動幅度很小，BPSO在迭代到80次時才搜索到適應度值為0.183 9的粒子，BPSOBC在第70次迭代時才搜索到適應度值為0.161 9的粒子，兩個算法在此之后均未搜索到適應度值更小的粒子，而BPSOBI則在第50次迭代時搜索到適應度值為0.213 6的粒子，迭代到第80次時搜索到適應度值為0.203 9的粒子，且在迭代到100次和130次時仍能夠繼續搜索到適應度值為0.200 6和0.171 1的粒子。此外，在LVST數據集、Libras數據集、Lung cancer數據集和Wine數據集上，BPSOBI在算法初期搜索中，將初始gbest的適應度值迅速降低到很小的水平，體現了本文提出的交互策略能有效提升算法的收斂性能。且由后期的搜索曲線分析，也充分驗證了本文提出的交互策略能夠在算法陷入局部最優狀態之后，仍然保證算法具備有效的全局搜索能力，繼續搜索到比當前更優秀的特征子集。

Fig.3 Experimental results on 11 datasets of two strategies圖3 兩種策略在11個數據集上的驗證實驗結果

分別驗證本文提出的兩種策略的有效性之后，由圖3中BPSOBCI的實驗曲線分析，在11個數據集上，BPSOBCI無論是在初始適應度值上，還是搜索性能上都比BPSO更優越，且在11個數據集上，BPSOBCI最后搜索到的適應度值均比BPSO搜索到的適應度值小。在Hillvalley數據集上，BPSO最終搜索到的gbest適應度值為0.387 2，而BPSOBCI最終搜索到的gbest適應度值為0.345 1，降低了10.87%。在Libras數據集上，BPSO搜索到的粒子最小適應度值為0.289 8，而BPSOBCI搜索到的粒子最小適應度值為0.240 6，降低了16.98%。在Parkinsons數據集上，BPSO搜索到的最小適應度值為0.253 7，同時，BPSOBCI搜索到最小適應度值為0.065 4，降低了74.22%。另一方面，BPSOBCI在大部分數據集上能夠搜索到比BPSOBC和BPSOBI適應度值更小的粒子。因此驗證了本文提出的兩種改進策略組合能夠極大提升BPSO算法的穩定性和搜索性能。

4.4 算法效果對比實驗結果分析

在4.3節中分別驗證了本文提出的兩種策略的有效性，4.4節中進一步將本文算法與人工蜂群算法（ABC）、PSO(4-2)和PSO-2stage進行對比實驗。其中，BPSOBCI、ABC和PSO(4-2)在11個數據集上分別運行20次進行測試，算法迭代200代。PSO-2stage則按論文運行40次，每次運行迭代100代。所有算法均以運行過程中的最終平均特征數及平均分類錯誤率作為算法性能的衡量指標。

表3所示為BPSOBCI與3個對比算法在11個數據集上的實驗結果。其中，加粗字體表示所有算法里最小的平均分類錯誤率和最小平均特征數目。表3所示的結果顯示，在11個數據集上，BPSOBCI得到的平均特征數比ABC、PSO(4-2)和PSO-2stage都要小，且除了Wine數據集，BPSOBCI在其他所有數據集上最終的平均分類錯誤率均要小于另外3個對比算法。實驗結果充分驗證了本文算法的優越性。

具體分析各個數據集的實驗結果，LVST數據集特征數目為309，樣本數目為126。在該數據集上的實驗結果顯示，BPSOBCI最終的平均分類錯誤率為0.098 8，相比PSO-2stage，BPSOBCI的分類錯誤率降低了約8%。平均特征數為121.1，PSO-2stage最終的平均特征數為153.025，平均特征數目減少了31.925。

Musk1數據集特征數目為166，樣本數為476，BPSOBCI分類錯誤率至少降低約0.000 1，同時平均特征數目至少降低了22.3。Libras數據集，特征數目為90，樣本數為360，BPSOBCI分類錯誤率降低約0.47%，平均特征數卻比ABC、PSO(4-2)和PSO-2stage分別減少了10.95、18.75和13.675。而且Libras數據集分類數目為15，本文算法與其他3個對比算法相比，依然取得了最高的分類精度和最少的特征數目。在這3個具有代表性的數據集上，實驗結果直接驗證了本文算法在消除冗余特征方面有很強的優越性，且在其他數據集上均能取得較好的分類精度，同時大大減少冗余特征數目。然而在Wine數據集上，本文算法的分類精度比PSO-2stage降低了0.006，但與此同時，平均特征數目降低了約58.74%。相較于ABC，雖然平均特征數目只減少了0.05，但平均分類錯誤率同時降低了約30.8%，算法整體的穩定性也由此可以驗證。

另一方面，從表3的對比實驗結果中可以看出：同等條件下運行20次之后，本文算法在絕大部分數據集上，無論是分類錯誤率的標準差還是平均特征數的標準差相較于對比的3個算法要小很多。首先，所有數據集上得到的平均錯誤率的標準差均接近于0，足以顯示算法在隨機運行的情況下的穩定性。對于Musk1數據集，BPSOBCI分類錯誤率的標準差為0.018 3，比PSO-2stage的0.019 3降低了5.18%，平均特征數的標準差也減少了0.494 9。Sonar數據集上，BPSOBCI多次運行后，在平均分類錯誤率上的標準差為0.013 2，相較于PSO(4-2)得到的0.015 7，降低了15.92%。同時，平均特征數上的標準差為2.560 3，比ABC取得的3.278 3減少了0.718。Spectf數據集上，BPSOBCI分類錯誤率的標準差為0.020 7，比PSO-2stage的0.037 1降低了21.59%。平均特征數的標準差也減少了1.430 2。在平均分類錯誤率和平均特征數兩個指標上取得優勢的基礎上，BPSOBCI上同時得到了最小的標準差，證明BPSOBCI在每次運行時，都能夠穩定地搜索到最好的特征子集，有效地反映了BPSOBCI的穩定性。

Table3 Comparison between BPSOBCI and contrast algorithms on 11 datasets表3 BPSOBCI與對比算法在11個數據集上的對比實驗結果

綜上所述，對多個特征規模及樣本數量各不相同的數據集的實驗結果進行分析，分析結果顯示，本文算法能夠穩定地在兼顧提升分類精度的同時大大減少冗余特征的數目。在樣本數目少，訓練不足的情況下仍然可以取得穩定的實驗結果。同時，在特征數目多的數據集上本文算法能夠極大減少特征數目且保證分類精度穩定，優勢十分明顯。多分類和二分類數據集上也都可以取得良好的實驗效果。

5 結束語

由于粒子群算法容易陷入局部最優狀態，本文針對這一缺陷，根據粒子在決策空間中的密度，對粒子進行判斷后進行交互操作，及時調整粒子，保持種群的多樣性，避免算法過早收斂。同時，在算法中，結合特征聚類信息，改進PSO的初始化策略，提高了初始種群的質量。在11個數據集上的結果顯示，與其他3個相關算法相比，本文算法在保證特征分類精度的同時，能夠大大減少特征選擇方案中的冗余特征，算法性能得到明顯提升。