基于自適應粒子群算法的特征選擇

李 策，王保云，高 浩

(南京郵電大學 自動化學院，江蘇 南京 210003)

基于自適應粒子群算法的特征選擇

李 策，王保云，高 浩

(南京郵電大學 自動化學院，江蘇 南京 210003)

在模式分類問題中，數據往往存在不相關或冗余的特征，從而影響分類的準確性。特征選擇的提出，很好地解決了這一問題。特征選擇的關鍵在于利用最少的特征獲得最佳的分類效果。為了達到這一目的，一種基于自適應粒子群的特征選擇的理論被提出。相比于原始的粒子群算法，在初始過程中引入混沌模型增加其初始粒子的多樣性，在更新機制中引入自適應因子增加其全局搜索能力。同時將特征數目引入到適應度函數中，在迭代前期通過懲罰因子調節分類準確率和特征數目對于適應度函數的影響，在迭代中后期懲罰因子恒定，使特征數目對于適應度函數的影響趨于穩定。自適應粒子群算法具有很好的全局收斂性,能夠避免陷入局部最優,尤其適合高維數據的降維問題。大量的理論分析和仿真實驗的結果表明,與其他粒子群算法(PSO)的特征選擇結果相比,在數據特征數目各異的情況下,該算法具有更好的分類效果，同時表明了所提算法的可行性以及優越性。

特征選擇；粒子群算法；分類；自適應；封裝

0 引 言

特征選擇也叫特征子集選擇。指從已有的特征中選擇N個特征使系統的特定目標最優化,從輸入特征中選擇出一些最有效特征以降低數據集維度的過程[1]，是提高學習算法性能的一個重要手段，也是模式識別中關鍵的數據預處理步驟。特征選擇應用在分類，對于機器學習和數據挖掘是一項重要的任務。分類過程中，數據集往往包含大量的特征，但是并不是所有的特征對于分類都是有用的，其中很多無關和冗余的特征會導致分類效果的不佳，同時導致維數的復雜性，因而特征選擇是一種非常有效的解決方式[2]。

特征選擇算法根據評價函數的不同可以分為封裝模式和過濾模式[3]。其中過濾模式通過分析特征子集內部的特點來衡量其好壞，一般用作預處理，與分類器的選擇無關。封裝模式實質上是一個分類器，用選取的特征子集對樣本集進行分類，分類精度作為衡量特征子集好壞的標準。在過濾模式中，學習算法作為獨立的一部分，而在封裝模式中是作為評價功能的一部分，可以取得較好的分類效果。選擇以粗糙集作為分類器的封裝模型。特征選擇的任務實際是一個組合優化問題[4]，特征選擇過程中，往往特征數目繁多，搜索空間較大，所以需要搜索算法去獲得最優的選擇方案，存在的搜索方法有序列前向選擇(SFS)[5]和序列后向選擇(SBS)[6]。但是這些算法不僅需要很大的計算代價，同時容易陷入局部最優。因此需要具有全局搜索能力的算法應用到特征選擇中。例如，粒子群算法(PSO)[7-10]、遺傳算法(GA)[11]和遺傳編程算法(GP)[12]。三種算法相比，粒子群算法具有快速、簡單等優勢，因而基于粒子群算法的特征選擇往往具有更好的應用效果。而基于自適應粒子群的特征選擇方法，相比于原始的粒子群算法，在初始過程引入混沌模型增加其初始粒子的多樣性，在更新機制引入自適應因子增加其全局搜索能力。同時將特征數目引入到適應度函數中，在迭代前期通過懲罰因子調節分類準確率和特征數目對于適應度函數的影響，在迭代中后期懲罰因子恒定，使特征數目對于適應度函數的影響趨于穩定。實驗結果表明，該算法具有優越性。

1 特征選擇和粒子群算法

1.1 封裝模式的特征選擇

特征選擇是選取一系列的特征構成一個特征子集，能夠使得這個子集有比特征全集相同或者更好的分類功能。一般分為四個過程：產生過程、評價函數、停止準則、驗證過程。一般流程如圖1所示[2]。

圖1 特征選擇的一般流程

特征選擇中的封裝模式最早由John等于1994年提出[1]。在該模式中，分類學習算法封裝在特征選擇的過程中，并以特定學習算法的性能作為子集的評價標準。在特征空間中搜索出對分類器具有較高性能的特征子集，直接構造分類模型。當滿足一定條件(一般設定的迭代次數)時，將最優的特征子集輸出，同時獲得一個具有較高分類性能的模型。在封裝模式的特征選擇方法中，有很多用來評價特征子集的學習算法，如貝葉斯分類器、近鄰法、支持向量機及神經網絡等，這些方法都是直接利用分類器的分類性能來評價特征子集的優劣。

1.2 粒子群算法

粒子群算法是于1995年由Kennedy和Eberhart提出的，通過模擬鳥群覓食行為而發展起來的一種基于群體協作的隨機搜索算法[13]。其描述如下：

假設在一個D維的目標搜索空間，m個粒子組構成一個群落，其中第i(i=(1,2,…,m))個粒子表示一個D維向量Xi=(xi1,xi2,…,xiD)。第i個粒子在目標搜索空間的位置是xi。每一個粒子所在的位置就是一個潛在的備選解，將xi帶入到目標函數中，計算其適應度值。每個粒子i還有一個速度決定它們飛翔的方向和距離，Vi=(vi1,vi2,…,viD)也是一個D維向量。第i粒子搜索到的最優位置記為pb(局部最優解)，整個粒子群迄今為止搜索到的最佳位置記為pg(全局最優解)。

粒子速度和位置的更新公式如下：

(1)

(2)

其中，d=1,2,…,D，i=1,2,…,m,m為種群規模；c1和c2為加速常數；rand為[0，1]之間任意的隨機數；t為迭代次數。

上述的粒子群算法，只適應于連續問題的求解。1997年，Kennedy和Eberhart提出了離散二進制粒子群算法(BPSO)[14]，這種算法采用的是二進制的編碼形式。在二進制的粒子群算法中，粒子的位置Xi，是用二進制的字符串表示(10110011)而速度向量不做這種要求。粒子的位置更新公式變為：

(3)

2 自適應粒子群算法

在原始粒子群算法的基礎上提出自適應粒子群算法，舍棄粒子的速度，采用高斯模型，利用粒子局部的全局最優解來更新粒子的位置公式：

(4)

cr=rand

(5)

該初始化模式增加了種群的多樣性，避免粒子陷入局部最優。

粒子的局部和全局的位置更新公式分別為：

Pbi(t+1)=

(6)

Pgi(t+1)=

(7)

其中，Pbi(t+1)為粒子個體的最優位置；Pgi(t+1)為粒子整體的最優位置；F為適應度函數；Xi(t+1)為粒子的當前位置；N為特征數目。

粒子的位置更新是與一般的位置更新方式不同，當適應度值與最優值相等時，通過比較特征數目來更新當前位置。特征選擇的目標是利用較少的特征達到最佳的優化效果，位置更新公式的改進有利于利用更少的特征數目。

3 適應度函數

傳統的基于粒子群算法的特征選擇方法采用封裝模式的評價函數，由于追求高的分類效果，一般設計：

(8)

其中，Accuracy為最終特征子集的分類精確率；#features為準確預測的樣本特征；#allfeatures為輸入的特征樣本。

3.1 改進的適應度函數

每個特征子集包含一定數量的特征，如果兩個特征子集取得準確率相同，包含特征數目較少的特征子集就該被選中。所以，在適應度函數中引入被選擇的特征子集的數目是很有必要的，所以適應度函數為：

(9)

其中，#S為被選擇的特征子集的特征數目；α為一個懲罰因子，是控制分類精確率和特征數目對于適應度函數的影響，其取值范圍為[0，1]；T為迭代次數；t為當前迭代次數。

在封裝模式中，適應度函數用來評價特征子集的好壞，數據分類的準確率在適應度函數中應該起到主導作用。該實驗中，迭代次數為100，隨著迭代次數的增加，迭代的后期α不斷增大，導致特征數目成為適應度函數的主導，直接導致迭代后期分類精確率的下降。所以應該控制t的取值范圍。實驗數據表明，當t最大值取20時，數據的分類精確率相比于其他算法有一定的提高，還能降低被選擇特征子集中的特征數目。當t為20時，即前20次的迭代過程中，迭代開始分類準確率主導適應度函數，隨著迭代次數的增加被選特征子集中的特征數目對于適應度函數的影響增加，當迭代到達20次時，α的取值固定為0.8。迭代的中期以及后期，特征數目分類準確率對于適應度函數的影響達到平衡。

3.2 鄰近算法

封裝模式的算法都需要學習算法對特征子集進行評估。采用的算法是鄰近算法[15]。鄰近算法也稱K最近分類算法，是數據挖掘分類技術中最簡單的方法之一。KNN算法的核心思想是，如果一個樣本在特征空間中的K個最相鄰的樣本中的大多數屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。KNN算法中，所選擇的鄰居都是已經正確分類的對象。同時它依賴于極限定理，在類別決策時，只與極少量的相鄰樣本有關。鄰近算法具有簡單，易于理解，易于實現，無需估計參數，無需訓練等特點。

由于鄰近算法具有的優勢，將其作為特征選擇的分類評價函數。采用留一驗證(LOOCV)的一階鄰近算法(K取1)。LOOCV指只使用原本樣本中的一項來當作驗證資料，而剩余的則留下來當作訓練資料。這個步驟一直持續到每個樣本都被當作一次測試資料。實驗中采用留一驗證，將輸入數據分成訓練集和測試集，并用鄰近算法對選出的特征子集進行評價。這個過程一直持續到迭代結束。

4 解 碼

(10)

當eij=1時，就代表第j個特征被選進特征子集。如果為0，不被選中。在統計被選中的特征數目時，可直接統計eij中1的個數，直接對其求和就可以計算出被選中的特征數目。

5 實驗設計

實驗采用UCI[16]機器學習庫中的數據，選擇其中的Glass，Sonar，Wine，Vowel，WDBC，Segmentation，Satellite，Ionosphere這些最為常用的數據進行分類比較。

5.1 數據表格

數據表格如表1所示。

5.2 參數設定

粒子群種群數目為20，迭代次數為100，鄰近算法K值取1。

為了更好地說明自適應粒子群算法對于數據分類的優越性，選擇離散粒子群算法(BPSO)[9]和混沌映射離散粒子群算法(CBPSO)[7]；還有Barebones離散粒子群算法[10]、CatfishBPSO(基于鯰魚效應的離散粒子群算法[17])、APSO(改進的適應度函數的算法)。比較不同算法作用在相同數據集上的分類效果，同時比較被選特征子集中的特征數目。上述其他算法的迭代次數同樣設置為100。

表1 實驗數據

6 實驗結果分析

在表2中，可以明顯發現，基于自適應粒子群算法的特征選擇方法相比于其他算法能夠取得很好的分類效果，同時還減少了被選擇特征的數目。數據集特征數目比較小時，例如Glass(D=10)，基于粒子群算法的特征選擇分類方法都能取得百分之百的分類效果。自適應粒子群算法分類效果也能夠達到百分之百，被選特征子集中的特征數目多一個。在數據集特征數目較少時，自適應粒子群算法不具有優勢。在數據集Vowel中，自適應粒子群算法相比于其他算法的效果會好很多，不僅分類的精確度高，相比于BPSO提高了接近0.5%，相比于其他算法提高了0.3%。而且被選的特征數目也比其他粒子群算法要少，相比Barebones粒子群算法特征數目少了一半。在數據Wine中，自適應粒子群算法分類效果能夠達到百分之百，相比于Barebones粒子群算法提高了0.6%。同時被選的特征數目相比于其他粒子群算法要少。在數據集Vehicle中，各種算法對于該數據集的分類效果普遍不高，APSO相比于其他算法分類的準確率有明顯提高，相比于Barebones粒子群算法提高了近1%，同時被選特征的數目與Barebones粒子群算法接近。當在數據集特征數目較多，例如在數據集Satellite和Sonar中，APSO相比于Barebones粒子群算法的優勢更加明顯，不僅能夠獲得很好的分類效果，同時有效減少了被選特征的數目。

將特征子集的特征數目引入到適應度函數中，對于特征子集進行評價，不僅能夠降低特征子集的特征數目，同時對于分類效果也產生了有益的影響。改進的適應度函數相比于改進算法更新機制對于特征選擇有更加直接的效果。特別是在特征數目較多的特征子集進行分類的過程中，影響體現的更加明顯。

表2 各算法分類效果對比

7 結束語

基于自適應粒子群的特征選擇的算法,在初始過程中引入混沌模型增加了初始粒子的多樣性，在更新機制中引入自適應因子增加其全局搜索能力。同時將特征數目引入到適應度函數中，在迭代前期通過懲罰因子調節分類準確率和特征數目對于適應度函數的影響，在迭代中后期懲罰因子恒定，使特征數目對于適應度函數的影響趨于穩定。自適應粒子群算法具有很好的全局收斂性,能夠避免陷入局部最優,尤其適合高維數據的降維問題。實驗結果表明,與其他粒子群算法的特征選擇結果相比,在數據特征數目各異的情況下,該算法具有更好的分類效果。

[1] 張麗新,王家欽,趙雁南,等.機器學習中的特征選擇[J].計算機科學,2004,31(11):180-184.

[2]DashM,LiuH.Featureselectionforclassification[J].IntelligentDataAnalysis,1997,1(1):131-156.

[3] 周 城,葛 斌,唐九陽,等.基于相關性和冗余度的聯合特征選擇方法[J].計算機科學,2012,39(4):181-184.

[4] 陳 彬,洪家苯.最優特征子集選擇問題[J].計算機學報,1997,20(2):133-138.

[5]MarillT,GreenDM.Ontheeffectivenessofreceptorsinrecognitionsystems[J].IEEETransactionsonInformationTheory,1963,9(1):11-17.

[6]WhitneyAW.Adirectmethodofnonparametricmeasurementselection[J].IEEETransactionsonComputers,1971,20(9):1100-1103.

[7]Heidari-BateniG,McGillemCD.Achaoticdirect-sequencespread-spectrumcommunicationsystem[J].IEEETransactionsonCommunications,1994,42(234):1524-1527.

[8]UnlerA,MuratA.Adiscreteparticleswarmoptimizationme-thodforfeatureselectioninbinaryclassificationproblems[J].EuropeanJournalofOperationalResearch,2010,206(3):528-539.

[9]YangCS,ChuangLY,KeCH,etal.Booleanbinaryparticleswarmoptimizationforfeatureselection[C]//ProceedingsofCEC.[s.l.]:IEEE,2008:2093-2098.

[10]ZhangY,GongD,HuY,etal.Featureselectionalgorithmbasedonbarebonesparticleswarmoptimization[J].Neurocomputing,2015,148:150-157.

[11]YuanH,TsengSS,GangshanW,etal.Atwo-phasefeatureselectionmethodusingbothfilterandwrapper[C]//IEEEinternationalconferenceonsystems,man,andcybernetics.[s.l.]:IEEE,1999:132-136.

[12]NeshatianK,ZhangM.Dimensionalityreductioninfacedetection:ageneticprogrammingapproach[C]//24thinternationalconferenceonimageandvisioncomputing.NewZealand:IEEE,2009:391-396.

[13]KennedyJ.Particleswarmoptimization[C]//Internationalconferenceonneuralnetworks.[s.l.]:IEEE,1995:1942-1948.

[14]KennedyJ,EberhartRC.Adiscretebinaryversionoftheparticleswarmalgorithm[C]//Internationalconferenceonsystems,man,andcybernetics.[s.l.]:IEEE,1997:4104-4108.

[15]CoverTM,HartPE.Nearestneighborpatternclassification[J].IEEETransactionsonInformationTheory,1967,13(1):21-27.

[16]AsuncionA,NewmanD.UCImachinelearningrepository[R].California:UniversityofCaliforniaIrvine,2007.

[17]ChuangLY,TsaiSW,YangCH.Improvedbinaryparticleswarmoptimizationusingcatfisheffectforfeatureselection[J].ExpertSystemswithApplications,2011,38(10):12699-12707.

Feature Selection Based on Adaptive Particle Swarm Optimization

LI Ce，WANG Bao-yun，GAO Hao

(College of Automation,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In pattern classification problems,there is often irrelevant or redundant features in data,thus affecting the accuracy of the classification.Feature selection is proposed to be a good solution to this problem.The key of feature selection is to use the least feature for the best classification results.In order to achieve this object,a theory based on adaptive particle swarm feature selection is presented.Compared to the original particle swarm optimization,chaos model is introduced in the initial process of increasing its diversity of primary particles,the introduction of adaptive factor to increase its global search capability in the update mechanism.At the same time the number of features will be introduced to the fitness function,in the early iterations adjustment classification accuracy and the number of features by penalizing factor for adapting to the impacts of the function,in the latter part of the penalty factor constant iteration,bringing the number of features of the fitness function tends to affect stable.Adaptive particle swarm algorithm has good global convergence and can avoid falling into local optimum,especially for lower-dimensional problem of high dimensional data.A large number of theoretical analysis and simulation results show that compared with other PSO feature of the election results,in the case where the number of different data characteristics,this algorithm has better classification results.Also it shows that the proposed algorithm is feasible and superior.

feature selection;PSO;classification;adaptive;wrapper

2016-05-08

2016-09-08

時間：2017-03-07

國家自然科學基金資助項目(61271232,61372126)；東南大學移動通信國家重點實驗室開放研究基金(2012D05)

李 策(1991-)，男，碩士研究生，研究方向為特征選擇；王保云，博士，教授，博導，研究方向為香農信息論，無線通信中的博弈與協作、信號處理技術，視頻信息的分析與理解；高 浩，博士，副教授，研究方向為優化算法、圖像處理的理論和實際應用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0921.024.html

TP391

A

1673-629X(2017)04-0089-05

10.3969/j.issn.1673-629X.2017.04.020