李 策，王保云，高 浩

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

基于自適應(yīng)粒子群算法的特征選擇

李 策，王保云，高 浩

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

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

特征選擇；粒子群算法；分類；自適應(yīng)；封裝

0 引 言

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

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

1 特征選擇和粒子群算法

1.1 封裝模式的特征選擇

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

圖1 特征選擇的一般流程

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

1.2 粒子群算法

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

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

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

(1)

(2)

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

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

(3)

2 自適應(yīng)粒子群算法

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

(4)

cr=rand

(5)

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

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

Pbi(t+1)=

(6)

Pgi(t+1)=

(7)

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

粒子的位置更新是與一般的位置更新方式不同，當(dāng)適應(yīng)度值與最優(yōu)值相等時，通過比較特征數(shù)目來更新當(dāng)前位置。特征選擇的目標(biāo)是利用較少的特征達(dá)到最佳的優(yōu)化效果，位置更新公式的改進(jìn)有利于利用更少的特征數(shù)目。

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

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

(8)

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

3.1 改進(jìn)的適應(yīng)度函數(shù)

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

(9)

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

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

3.2 鄰近算法

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

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

4 解 碼

(10)

當(dāng)eij=1時，就代表第j個特征被選進(jìn)特征子集。如果為0，不被選中。在統(tǒng)計被選中的特征數(shù)目時，可直接統(tǒng)計eij中1的個數(shù)，直接對其求和就可以計算出被選中的特征數(shù)目。

5 實(shí)驗設(shè)計

實(shí)驗采用UCI[16]機(jī)器學(xué)習(xí)庫中的數(shù)據(jù)，選擇其中的Glass，Sonar，Wine，Vowel，WDBC，Segmentation，Satellite，Ionosphere這些最為常用的數(shù)據(jù)進(jìn)行分類比較。

5.1 數(shù)據(jù)表格

數(shù)據(jù)表格如表1所示。

5.2 參數(shù)設(shè)定

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

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

表1 實(shí)驗數(shù)據(jù)

6 實(shí)驗結(jié)果分析

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

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

表2 各算法分類效果對比

7 結(jié)束語

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

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

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

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

[4] 陳 彬,洪家苯.最優(yōu)特征子集選擇問題[J].計算機(jī)學(xué)報,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

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

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

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