混合互信息和粒子群算法的多目標(biāo)特征選擇方法*

王金杰，李 煒

1.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥230601

2.安徽大學(xué) 計算智能與信號處理重點實驗室，合肥230039

1 引言

在機器學(xué)習(xí)和數(shù)據(jù)挖掘中，分類是一個很重要的任務(wù)。在沒有先驗知識的情況下，很難決定哪個特征是有用的，導(dǎo)致了數(shù)據(jù)集中包含了相關(guān)的、不相關(guān)的以及冗余的特征。在進行分類時，由于不相關(guān)的和冗余的特征帶來的維度災(zāi)難，不僅沒用，而且還會降低分類性能[1]。特征選擇通過選出具有代表性的特征子集，提高了算法效率，減少了計算開銷，同時避免了過擬合問題，提高了泛化能力[2]。特征選擇技術(shù)主要分為三類：過濾式、封裝式以及嵌入式[3]。過濾式方法先通過對數(shù)據(jù)集進行特征選擇，然后再進行訓(xùn)練學(xué)習(xí)。而封裝式方法直接把最終將要使用的學(xué)習(xí)器的性能作為特征子集的評價標(biāo)準(zhǔn)。嵌入式方法則是將特征選擇過程與學(xué)習(xí)訓(xùn)練過程融為一體，兩者在同一個優(yōu)化過程完成。

特征選擇有兩個最主要的沖突：最小化分類錯誤率和最小化特征個數(shù)，故可以將特征選擇看成一個多目標(biāo)問題。由于PSO（particle swarm optimization）算法具有較小的計算花費以及快速的收斂優(yōu)點，其是特征選擇中一個有效的技術(shù)方法[4]。Xue 等人曾在2013 年提出了一篇基于擁擠距離（crowding）、突變策略（mutation）和支配關(guān)系（dominance）的PSO 算法的多目標(biāo)方法，命名為CMDPSO[5]。通過該方法能獲得一個較好的特征子集的集合，然而仍然有很大的潛力去探索和提升帕累托前沿面；Nguyen 等人在2016 年提出了基于PSO 用相似距離來選取gbest以及更新Archive 的多目標(biāo)特征選擇方法MOPSO-SiD（multiobjective particle swarm optimization using subset similarity distance）[6]。該方法在一定程度上提升了帕累托前沿面，但是由于沒有較好提升種群的探索能力，導(dǎo)致當(dāng)種群迭代到后期時還是容易陷入局部最優(yōu)；在2016 年，Nguyen 等人在CMDPSO 算法的基礎(chǔ)上進行改進，通過一個局部搜索策略包括插入（inserting，I）、交換（swapping，S）和刪除（removing，R）三個操作去提升外部文檔集合，提出一個新的Archive 機制的ISRPSO 算法[7]。雖然通過該機制獲得了更好的分類性能，但是本質(zhì)上并沒有改進種群本身，而且花費了大量的計算代價在評估上。近些年來也有越來越多的人提出了基于差分進化算法（differential evolution algorithm，DE）的多目標(biāo)特征選擇方法[8-9]，以及基于人工蜂群算法（artificial bee colony algorithm，ABC）的多目標(biāo)特征選擇方法[10-11]等，并且也在不斷完善。

除此之外，早在2009 年，Estévez 等人提出了一個將互信息與遺傳算法（genetic algorithm，GA）相結(jié)合的特征選擇的方法GAMIFS（genetic algorithm mutual information feature selection）[12]。該方法利用互信息改進種群的初始化以及利用NMIFS（normalized mutual information feature selection）標(biāo)準(zhǔn)提出了一個突變操作，克服了類似mRMR（minimal redundancy maximal relevance）增量搜索算法的限制，同時還在一定程度上提升算法的探索能力。在2015年Butler-Yeoman等人提出了兩種基于粒子群優(yōu)化（PSO）的過濾式-封裝式混合特征選擇算法：第一種算法FastPSO 將過濾式和封裝式方法結(jié)合到PSO 的搜索過程中進行特征選擇，大部分評價為過濾式方法，少量評價為封裝式方法；第二個名為RapidPSO 的算法進一步減少了封裝式方法的計算數(shù)量[13]。但是提出的兩種方法與封裝式PSO 算法比較獲得相似的分類性能，時間也較短，但是特征數(shù)量更多；同時與傳統(tǒng)的啟發(fā)式搜索方法相比也沒有解決特征數(shù)量較多的問題。Tran 等人在2016 年利用互信息對粒子的pbest進行更新，但是該方法是一個針對高維度數(shù)據(jù)集進行分類的方法[14]。在2017 年，Nayak 等人提出了將DE 和MI（mutual information）相結(jié)合的具有有效冗余度量的過濾方法[15]。雖然該方法的評估標(biāo)準(zhǔn)優(yōu)于文中提出的對比方法，但是由于每代種群的產(chǎn)生都是由父代種群和子代種群結(jié)合通過精英策略產(chǎn)生，種群在迭代早起失去了多樣性，容易導(dǎo)致過早收斂的問題。在2018年，Hammami 等人提出了一篇基于GA 和MI 的FW-NSGA-II（filter-wrapper-based nondominated sorting genetic algorithm-II）混合的多目標(biāo)特征選擇算法[16]，使用一個基于指標(biāo)的多目標(biāo)局部搜索（indicator based multiobjective local search，IBMOLS）方法去提升種群的非支配面等。

綜合上述文獻，本文針對粒子群容易陷入早熟的特點提出一個自適應(yīng)突變策略去擾動種群，同時為了獲得更好的非支配面集合，本文利用粒子群算法的全局搜索能力卓越的優(yōu)點和互信息自身的特點去平衡種群的全局和局部搜索。

2 背景介紹

2.1 PSO 算法

PSO 算法是模仿了一群鳥兒在飛行時相互交流，每只鳥都有一個特定的方向，當(dāng)它們在一起交流時，它們會識別出最佳位置的鳥。然后，每只鳥從新的局部位置調(diào)查搜索空間，然后重復(fù)這個過程，直到鳥群到達預(yù)期的目的地。這一過程包括鳥類從它們自己的經(jīng)驗（局部搜索）中學(xué)習(xí)和從它們周圍的其他鳥（全局搜索）的經(jīng)驗中學(xué)習(xí)[17]。

在傳統(tǒng)的PSO 中，種群是由粒子集合組成，每個粒子都代表一個優(yōu)化問題潛在的解。在種群中，把第t次迭代產(chǎn)生的第i個粒子的位置表示為：

第t次迭代產(chǎn)生的第i個粒子的速度表示為：

在t+1 代粒子的速度和位置根據(jù)式（3）和式（4）兩個公式進行更新：

pbesti表示第i個粒子目前最好的位置，gbest表示所有粒子目前為止發(fā)現(xiàn)的最好的位置。加速系數(shù)c1和c2是控制pbest和gbest對搜索過程影響的非負(fù)常數(shù)；ω表示控制粒子在搜索空間中的探索的慣性權(quán)重。r1和r2是[0，1]內(nèi)的兩個隨機值。

2.2 互信息

在概率論和信息熵領(lǐng)域中，互信息是用來測量兩個變量之間的依賴性的方法。兩個隨機變量X和Y之間的互信息可以被表示為：

其中，H(X)是隨機變量X的熵；p(x,y)為聯(lián)合概率質(zhì)量函數(shù)；p(x)和p(y)為邊緣概率。X和Y之間關(guān)系越緊密，I(Xi;Y)的值越大，如果兩個變量之間相互獨立，則I(Xi;Y)的值為0。

將互信息應(yīng)用在特征選擇問題上時，當(dāng)隨機變量X表示粒子特征，隨機變量Y表示標(biāo)簽時，I(Xi;Y)計算出的值表示粒子和標(biāo)簽之間的相關(guān)性，值越大，特征與標(biāo)簽之間的相關(guān)性越大，反之越小。如果變量X和Y都表示特征，I(Xi;Y)計算出的值表示粒子之間的冗余性，值越大，特征之間的冗余性越大，反之越小。

在基于互信息的特征選擇研究上，Peng 等人[18]提出了最小冗余性最大相關(guān)性（mRMR）評估標(biāo)準(zhǔn)，其目標(biāo)函數(shù)定義為：

其中，m是已選特征子集S的特征個數(shù)，Xi為第i個候選特征。對于順序向前搜索的方法，每次從候選集中加入一個式（6）值最大的特征進入已選特征集中，直到滿足停止標(biāo)準(zhǔn)為止。

由互信息的定義可以得出：

Vinh 等人基于上式，重寫了式（6），使得對式（6）里兩個子項都進行了標(biāo)準(zhǔn)化[19]。

2.3 多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化一般涉及到最大化或者最小化多個沖突目標(biāo)函數(shù)。用數(shù)學(xué)術(shù)語，最小化多目標(biāo)函數(shù)的公式可被寫為[5]：

其中，x是決策變量，fi(x)是x的函數(shù)，k是最小化的目標(biāo)函數(shù)的個數(shù)，gi(x)和hi(x)是問題的約束條件。

假設(shè)y和z是k個目標(biāo)最小化問題的兩個解，如果滿足：

其中，i,j∈{1,2,…,k}。那么稱y支配z。

對于兩個目標(biāo)的問題，如圖1。

Fig.1 Minimization problem with two objective functions圖1 兩個目標(biāo)的最小化問題

x1支配x2和x3，而x2既不支配x3，x3也不支配x2，故x2和x3互不支配。當(dāng)一個解不受其他解支配時，稱為帕累托最優(yōu)解（Pareto）。在搜索空間中，所有帕累托最優(yōu)解的集合形成了平衡曲面，稱為帕累托前沿面（Pareto front，PF）。利用多目標(biāo)優(yōu)化算法能夠去探索非支配解集。

2.4 特征選擇

特征選擇是一種典型的組合優(yōu)化問題，其從N個特征集合中選出M個特征的子集(M≤N)，去除冗余或不相關(guān)的特征，使得處理后的數(shù)據(jù)集不僅包含的特征個數(shù)更少，而且能夠提高分類算法在原有特征集合的分類性能[20]。

特征選擇中主要的兩種方法：過濾式和封裝式。如圖2 所示[21]，過濾式方法是對數(shù)據(jù)集本身進行評價（如互信息）。封裝式方法直接把最終將要使用的學(xué)習(xí)器的性能作為特征子集的評價標(biāo)準(zhǔn)（如粒子群），如圖3 所示[21]。

Fig.2 Filter feature selection圖2 過濾式特征選擇

Fig.3 Wrapper feature selection圖3 封裝式特征選擇

3 基于混合PSO 和MI 算法的多目標(biāo)特征選擇方法

3.1 基于互信息方法的局部學(xué)習(xí)策略

3.1.1 外部文檔和非支配面的集合概念

由于外部文檔（Archive）中存放的是到目前為止所迭代產(chǎn)生的最優(yōu)解。在每次迭代時，粒子群算法會在外部文檔中選擇一個gbest用來指引粒子的飛行。因此，在Archive 中的每個粒子都很重要。同時Archive成員選擇的特征可以被視為重要特征。

Archive 中的第i個粒子的已選特征集合定義為A_Si，則未選擇的特征集合定義為A_USi。假設(shè)特征維度為8，可表示為{f1,f2,f3,f4,f5,f6,f7,f8}。Archive中包含3 個非支配解Archive={A1,A2,A3}，根據(jù)上面的集合定義，Archive 中3 個解對應(yīng)的A_Si和A_USi集合可表示為：

同時種群每次迭代都會產(chǎn)生PF，里面存放著當(dāng)前種群的非支配解的集合。故PF 里面的第j個粒子的已選特征集合定義為F_Sj，則未選擇的特征集合定義為F_USj。假設(shè)PF 中包含3 個粒子，根據(jù)上面的集合定義，PF 中3 個粒子對應(yīng)集合可表示為：

根據(jù)上面定義的兩個集合概念，再結(jié)合差集運算，本文定義以下幾個關(guān)系概念。

定義1（>）假設(shè)有集合A和集合B，AB不為空，BA等于空，則集合A大于集合B。例如：

稱F_S1大于A_S1。

定義2（<）如果AB等于空，BA不為空，則集合A小于集合B。例如：

稱F_S2小于A_S2。

定義3（=）如果AB等于空，BA等于空，則集合A等于集合B。例如：

稱F_S3等于A_S3。

定義4（<>）如果AB不為空，BA不為空，則集合A與集合B互不包含。例如：

稱F_S1與A_S2互不包含。

3.1.2 基于互信息的插入刪除操作

當(dāng)種群每一次迭代時，對種群產(chǎn)生的PF 中的第j個粒子(particlej)，本文采用隨機選擇策略從Archive中選擇一個引導(dǎo)粒子（lead）。本文對particlej進行插入刪除操作規(guī)則如下：

（1）如果particlej已選的特征集合F_Sj小于lead已選擇的特征集合A_Slead，則認(rèn)為lead中含有particlej沒有選擇的相關(guān)特征。particlej插入僅存在lead中的特征Set_Only_In_A_Slead=A_SleadF_Sj。

（2）如果F_Sj大于A_Slead，則認(rèn)為particlej可能選擇一些不相關(guān)和冗余的特征，因此刪除lead中沒有選的特征Set_Only_In_F_Sj=F_SjA_Slead。

（3）如果F_Sj和A_Slead兩個集合是相等的或者互不包含的，隨機選擇插入操作或者刪除操作。①假如兩個集合是相等的，如果是插入操作，則插入的特征是particlej中沒有選擇的特征F_USj，如果是刪除操作，則刪除particlej中已選擇的特征F_Sj。②假設(shè)兩個集合互不包含，如果是插入操作，particlej插入僅存在lead中的特征，如果是刪除操作，則particlej刪除僅自己選擇而lead沒有選擇的特征。

對粒子插入刪除的特征個數(shù)受多個因素限制，包括particlej已選的特征個數(shù)，lead已選的特征個數(shù)等。故本文對于粒子插入刪除的特征個數(shù)設(shè)置了一個最大值，這個最大值是根據(jù)粒子的維度以及百分比α來決定的。

Insert：將式（6）計算得出的結(jié)果稱為Relevant，對于粒子的插入操作，插入Relevant 值最大的特征f。如果插入的特征個數(shù)大于1，則將剛插入的特征f加入已選特征集中，從候選特征集中刪除特征f，再重新計算Relevant，繼續(xù)進行插入操作。

Delete：對于粒子的刪除操作，定義兩個公式：

其中，US為將要刪除的特征集合。（1）如果選擇刪除不相關(guān)的特征，則利用式（13）計算待刪除的特征集合對應(yīng)的Irrelevant 值，其中Irrelevant 值最小的特征被定義為最不相關(guān)的特征，將其刪除。（2）如果刪除冗余特征，通過式（14）計算對應(yīng)的Redundant 值，找到最大Redundant 值，其值對應(yīng)的是兩個特征之間的相關(guān)性，再利用式（13）計算這兩個特征的Irrelevant值，刪除Irrelevant值最小的特征。

3.1.3 精英策略

Deb 在2002 年提出了快速精英策略的多目標(biāo)遺傳算法[22]NSGA-II。文章將父代種群和子代種群相結(jié)合，通過精英策略產(chǎn)生新的父代種群。實驗證明精英策略可以加速算法的執(zhí)行速度，由于該策略擴大了采樣空間，在一定程度上確保己經(jīng)找到的最優(yōu)解不會丟失。

故本文將PF 的粒子通過互信息進行插入刪除操作后得到新的粒子集合，通過將兩個粒子集合進行合并，使用精英策略能夠保留最優(yōu)的粒子，不僅能改善PF，還能優(yōu)化Archive。同時采用擁擠距離進行比較，能夠使得PF 中的粒子均勻分布，保證種群的多樣性。

算法1 是針對本文提出的局部搜索算法的偽代碼。第2 行MaxChangeNum表示粒子改變維度的最大個數(shù)，第31 行的Container是一個集合，用來存放每次學(xué)習(xí)后的粒子。第6～12 行根據(jù)3.1.1 小節(jié)介紹的集合概念計算PF 中的粒子i和Archive 中的粒子lead對應(yīng)的集合，lead是在外部文檔中隨機選擇的一個引導(dǎo)粒子，第14～32 行對粒子進行插入刪除操作，第33 行利用精英策略進行篩選，獲得更好的PF。

3.2 自適應(yīng)突變操作

粒子群算法具有較快的收斂速度。然而，快速的收斂速度往往使基于粒子群的算法收斂到錯誤的PF 中。然而已研究的文章較多是通過基因算法中的突變操作來解決的，而突變概率是不變的。針對種群中每個粒子，并不都是隨著迭代次數(shù)增加而陷入停滯，故本文針對種群中每個粒子采用非線性函數(shù)Pm自適應(yīng)控制每個粒子的突變概率和突變范圍,來擴展該算法在勘探中的應(yīng)用能力。

其中，MaxIter代表最大迭代次數(shù)，UnupdateNumi表示第i個粒子當(dāng)前的pbest距離其上一次pbest更新的次數(shù)。可以看出，隨著迭代次數(shù)增加，種群越容易陷入局部最優(yōu)，導(dǎo)致粒子對應(yīng)pbest不能更新，Pm的值隨著UnupdateNum增加，趨向于以指數(shù)增加。如算法2 所示：如果rand＜Pm，對當(dāng)前粒子執(zhí)行突變，rand∈[0,1]。首先從該粒子中隨機選取k個元素，然后在搜索空間中重新初始化相應(yīng)維度的值。這里k的值是用于控制突變范圍的整數(shù)。

其中，Poplength表示粒子的維度。

3.3 gbest的選取

在Archive 中，粒子的擁擠距離越大，表示解空間中，在該粒子局部范圍內(nèi)分布的粒子越少。本文通過二進制錦標(biāo)賽的方法，從Archive 中選擇兩個粒子。再比較兩個粒子擁擠距離，選擇擁擠距離大的粒子作為gbest。通過該方法選擇gbest能夠使得種群在不斷的迭代中獲得更均勻，分布性更好的PF。

3.4 Archive的更新

每次迭代后，將種群的PF 加入Archive 中，通過支配和非支配關(guān)系，將被支配的解全部從Archive 中刪除，保留非支配解。如果非支配解的個數(shù)超出Archive 的大小，則根據(jù)擁擠度依次從小到大從Archive中刪除粒子，直到滿足條件為止。

3.5 種群的編碼、解碼與評價

對于種群中的每個粒子，其位置向量每一維均表示為0～1 之間的實數(shù)。根據(jù)特征選擇問題的特殊性，設(shè)置一個閾值Threshold，如果位置向量某個維度的值大于閾值Threshold，則表示對應(yīng)維度的特征被選擇；反之，如果小于閾值Threshold，則表示對應(yīng)維度的特征未被選擇。

本文采用在特征選擇中最普遍的兩個相互矛盾的目標(biāo)函數(shù)：特征子集中的特征數(shù)目和對應(yīng)的分類錯誤率。其中，在相關(guān)文獻中[23-24]，采用分類錯誤率作為適應(yīng)度函數(shù)直接對粒子進行評價。分類錯誤率按式（17）計算：

其中，F(xiàn)P表示負(fù)樣本被預(yù)測成正樣本的個數(shù)，F(xiàn)N表示正樣本被預(yù)測成負(fù)樣本的個數(shù)，TP表示正樣本被預(yù)測成正樣本的個數(shù)，TN表示負(fù)樣本被預(yù)測成負(fù)樣本的個數(shù)。

圖4 為本文算法流程圖。

4 實驗設(shè)計和結(jié)果分析

為證明本文提出的基于混合PSO 和MI 的多目標(biāo)特征選擇方法的有效性和優(yōu)越性，首先將提出的HMIPSO 方法與MOPSO 算法以及Xue 等人在2013年提出的經(jīng)典的CMDPSO 算法進行對比[5]，證明了本文提出的HMIPSO 方法能有效改善PSO 算法在多目標(biāo)特征選擇應(yīng)用上的性能；然后還比較了NSGA-II算法[22]以及在2017 年由Hancer 等人提出的基于人工蜂群算法的帕累托面特征選擇方法[11]，本文對比的是Hancer 提出的BMOABC（binary multi-objective artificial bee colony）算法。實驗結(jié)果證明了本文提出的方法比傳統(tǒng)的方法和最新的技術(shù)方法在性能上都有提升。本文所有實驗均在內(nèi)存16.0 GB 的PC 機上運行，運行環(huán)境為Matlab R2016b。

4.1 數(shù)據(jù)集和實驗參數(shù)設(shè)置

Fig.4 Flow chart of HMIPSO圖4 HMIPSO 算法流程圖

Table 1 Information of datasets表1 數(shù)據(jù)集信息

表1 是在本次實驗中使用到的15 個數(shù)據(jù)集，是從UCI 機器學(xué)習(xí)庫中選擇出來的。這些數(shù)據(jù)集的特征個數(shù)從Wine 最小的13 個到LSVT 最大的310 個，樣本個數(shù)從Lung Cancer 最少的32 個到German 最多的1 000 個，具有充分的代表性。因此對算法的優(yōu)化能力提出了很高的要求。

在進行實驗時，每個數(shù)據(jù)集都被劃分成70%的訓(xùn)練集和30%的測試集。每個粒子都代表一個特征子集。訓(xùn)練集中被選擇的特征子集是通過十折交叉、五近鄰（5-NN）的方法來評價分類性能。并在算法的最后，對在訓(xùn)練集中得到Archive 中的粒子集合利用測試集進行評價。

算法的具體參數(shù)如下，局部搜索中提出的α=0.02，種群的大小P=30，最大迭代次數(shù)為100，Archive的大小為30。本文提出的方法HMIPSO、CMDPSO和MOPSO 算法的公共參數(shù)設(shè)置相同：學(xué)習(xí)因子c1和c2取區(qū)間[1.5,2.0]的隨機值，慣性權(quán)重ω取區(qū)間[0.1,0.5]的隨機值，粒子最大速度vmax=0.6，最小速度vmin=-0.6，閾值Threshold=0.6。在NSGA-II 和BMOABC算法中，采用的是二進制編碼，每個粒子是由n個二進制串組成，n為粒子的維度，每位的值為0 表示特征沒有被選擇，值為1 表示特征被選擇。NSGA-II 算法中的突變概率為1/n，交叉概率0.9。BMOABC 算法中，限制參數(shù)limit=100，參數(shù)T=10 000。對于每個數(shù)據(jù)集都被獨立運行40 次。

4.2 實驗結(jié)果分析

對于每個數(shù)據(jù)集，由于要獨立運行40 次，故將每次運行得到的外部文檔聯(lián)合成一個并集。在這個并集中，對于有相同特征個數(shù)的特征子集，計算它們的平均分類錯誤率。除此之外，并集中的所有非支配解稱之為最優(yōu)解，并計算最優(yōu)解的分類錯誤率。

首先HMIPSO 與MOPSO、CMDPSO 進行比較，證明HMIPSO 通過結(jié)合互信息的方法提升了PSO 算法的性能。圖5 是其最終的并集在測試集上的比較。而 圖6 是HMIPSO 和NSGA-II、BMOABC 算 法在測試集上的比較。在這些圖中，“-A”表示40 次獨立運行獲得的平均分類性能，“-B”表示40 次獨立運行獲得的最優(yōu)解的分類性能。其中X軸表示粒子選擇的特征個數(shù)，Y軸表示分類錯誤率，圖的正上方表示數(shù)據(jù)集名稱以及特征維度和未進行特征選擇的分類錯誤率。

4.2.1 HMIPSO 對分類的影響

圖5 和圖6 正上方信息為不同數(shù)據(jù)集使用全部可使用的特征進行評估的分類錯誤率以及對應(yīng)的特征個數(shù)。數(shù)據(jù)集Musk1 的特征維度為166，用這166個特征進行分類所得的分類錯誤率為16.823%。利用本文提出的HMIPSO 算法進行特征選擇所得最優(yōu)解Pareto 面（圖中“-B”表示），最大的分類錯誤率為28.67%，特征個數(shù)為12；最小分類錯誤率為13.14%，特征個數(shù)為27?？梢钥闯鲭m然使用HMIPSO 算法獲得的最小特征個數(shù)對應(yīng)的分類錯誤率要大于未進行特征選擇進行分類的錯誤率，但是最優(yōu)解中獲得的最大特征個數(shù)對應(yīng)的錯誤率比未進行特征選擇進行分類的錯誤率降低了3.783%，同時特征個數(shù)也減少了139 個。

而數(shù)據(jù)集Wine 特征維度為13，用這13 個特征進行分類所得的分類錯誤率為30.883%。利用本文提出的HMIPSO 算法進行特征選擇所得最優(yōu)解中，最大的分類錯誤率為9.33%，降低了21.553%，特征個數(shù)為1，減少了12 個特征個數(shù)；最小分類錯誤率為1.67%，降低了29.213%，特征個數(shù)為4，降低了9 個特征個數(shù)?？煽闯鰯?shù)據(jù)集Wine 使用HMIPSO 進行分類比直接使用全部特征進行分類特征個數(shù)不僅減少了，同時分類錯誤率也降低了。

根據(jù)以上分析可得，利用HMIPSO 算法進行分類相對于直接使用所有特征進行分類，能夠有效降低分類錯誤率，同時能很大程度上減少特征個數(shù)。

4.2.2 HMIPSO、CMDPSO和MOPSO之間的比較

從圖5 可以看出本文提出的混合互信息與粒子群算法的HMIPSO 方法的最優(yōu)解Pareto 面（圖中“-B”表示）大部分都是優(yōu)于MOPSO 和CMDPSO 方法。并且隨著特征的維度增加，HMIPSO 效果則表現(xiàn)越明顯。例如，從圖5 中可看出在某些維度較小的數(shù)據(jù)集上，HMIPSO 效果優(yōu)勢并不十分明顯。例如維度為24 的數(shù)據(jù)集German，利用MOPSO 算法得到的解分類錯誤率為21.67%，特征個數(shù)為1；利用CMDPSO 算法得到的最大特征分類錯誤率為23.00%，特征個數(shù)為2，最小分類錯誤率為22.67%，特征個數(shù)為5；利用HMIPSO 算法得到的German 特征數(shù)為2 和特征數(shù)為4 的時候?qū)?yīng)的錯誤率分別為25.67%和21.00%。通過數(shù)據(jù)集German 的實驗結(jié)果可知，雖然HMIPSO 算法最大特征個數(shù)比MOPSO算法所獲得的特征個數(shù)要大，但是分類錯誤率降低了0.67%；相比較CMDPSO算法，雖然最小分類錯誤率要大于CMDPSO 算法的最小分類錯誤率，但是特征個數(shù)要少于CMDPSO 算法，同時CMDPSO 算法中特征個數(shù)為5 時，其分類錯誤率為22.67%，比HMIPSO 算法中特征個數(shù)為4，分類錯誤率為21.00%高了1.67%。因此HMIPSO 算法所獲得的帕累托面雖然不是完全優(yōu)于另兩種算法，但是在一定程度上也提升了解的質(zhì)量。

Fig.5 Experimental results of HMIPSO,CMDPSO and MOPSO on test set圖5 HMIPSO、CMDPSO 和MOPSO 在測試集上的實驗結(jié)果

Fig.6 Experimental results of HMIPSO,NSGA-II and BMOABC on test set圖6 HMIPSO，NSGA-II和BMOABC 在測試集上的實驗結(jié)果

除此之外，HMIPSO 在大部分維度較低的數(shù)據(jù)集上仍能夠得到優(yōu)于其他算法的結(jié)果。在保證特征數(shù)目不增加的基礎(chǔ)上，仍能夠降低相應(yīng)的分類錯誤率。比如數(shù)據(jù)集Vehicle，3 個算法均得到了特征為1、2 和4 的3 個結(jié)果，但MOPSO 和CMDPSO 算法在特征數(shù)為1、2和4時分類錯誤率分別為46.48%、30.31%、29.43%和45.32%、31.92%、28.75%，而HMIPSO 得到的分類錯誤率為40.82%、29.09%、25.58%，明顯降低了分類錯誤率。

隨著數(shù)據(jù)集維度的增加，HMIPSO 在降低分類錯誤率的同時，特征個數(shù)也明顯減少,獲得的最優(yōu)解Pareto 面要優(yōu)于另兩種算法所獲得Pareto 面。具體分析為：對于維度為90 的數(shù)據(jù)集Libras，其中HMIPSO算法獲得最小分類錯誤率為37.45%，對應(yīng)的最大特征個數(shù)為9。相比較MOPSO 算法的最小分類錯誤率為42.27%，最大特征個數(shù)為11，分類錯誤率降低了4.82%，同時特征個數(shù)減少了兩個；相比較CMDPSO算法最小分類錯誤率為37.64%，最大特征個數(shù)為15，分類錯誤率降低了0.19%的同時，特征個數(shù)減少了6個。對于維度為279的數(shù)據(jù)集Arrhythmia，HMIPSO算法在特征個數(shù)為47 時獲得最小分類錯誤率30.66%，MOPSO 算法獲得最小分類錯誤率為32.47%，特征個數(shù)為61，CMDPSO算法獲得最小分類錯誤率為32.42%，特征個數(shù)為74。HMIPSO 算法相對于MOPSO 算法在降低1.81%錯誤率的前提下，還使得特征個數(shù)減少了14，而相對于CMDPSO 算法在降低1.76%錯誤率的前提下，特征個數(shù)減少了27。

由以上分析，證明基于互信息的局部搜索策略，能夠有效減少第一非支配面中粒子的冗余和不相關(guān)特征，同時加入了相關(guān)特征。在大部分維度較低的數(shù)據(jù)集上，特征數(shù)目相同的情況下，通過局部搜索策略能有效提高算法的分類性能。在高維數(shù)據(jù)集上表現(xiàn)更為明顯。HMIPSO 算法通過局部搜索策略能夠搜索到更好的解，對第一非支配面進一步優(yōu)化，提升特征選擇方法的整體性能。

4.2.3 HMIPSO、NSGA-II和BMOABC之間的比較

如圖6 可以看出，HMIPSO 算法的最優(yōu)解（圖中“-B”表示），在數(shù)據(jù)集Vehicle 上雖然在特征數(shù)為3的時候分類錯誤率要高于NSGA-II 算法，但要低于BMOABC 算法。3 個算法都獲得了特征數(shù)為1 和2的兩個解，而對應(yīng)的HMIPSO 算法的分類錯誤率40.82%、29.09%都比另兩種算法要低。BMOABC 在特征個數(shù)為7 和NSGA-II算法在特征數(shù)為6 的時候分別獲得最小分類錯誤率26.86%和26.38%，而HMIPSO在特征數(shù)為4 的時候獲得最低分類錯誤率25.58%，特征個數(shù)和分類錯誤率都優(yōu)于另兩種算法。故可以看出HMIPSO 算法在數(shù)據(jù)集Vehicle 上優(yōu)于BMOABC算法，但是并不完全優(yōu)于NSGA-II算法。相似的結(jié)果還有數(shù)據(jù)集German，從圖6 中可以看出，HMIPSO 算法在數(shù)據(jù)集German 上獲得Pareto 面優(yōu)于NSGA-II 所獲得的Pareto 面；與MOABC 算法相比，HMIPSO 除了特征個數(shù)為2 時分類錯誤率高于MOABC，其他兩個解都優(yōu)于MOABC。而對于其他的低維的數(shù)據(jù)集，明顯能看出HMIPSO 算法優(yōu)化了Pareto 面。

對于較高維數(shù)據(jù)集，在降低錯誤率的同時，減少了冗余特征，大大降低了特征子集的維度。例如，在維度為60 的Sonar數(shù)據(jù)集上，HMIPSO 獲得3 個解，特征數(shù)為1 的時候，錯誤率為22.38%，特征數(shù)為2 的時候，錯誤率為16.90%，特征數(shù)為5 的時候，錯誤率為12.14%。NSGA-II算法在特征數(shù)為1的時候錯誤率為39.52%，比HMIPSO 高了17.14%；特征數(shù)為2時，錯誤率為26.67%，比HMIPSO 高了9.77%；特征數(shù)為5 時，錯誤率為15.59%，比HMIPSO 高了3.45%。BMOABC算法在特征數(shù)1 時錯誤率為24.52%，比HMIPSO 高了2.14%；在特征數(shù)為2 時錯誤率為22.62%，比HMIPSO高了5.72%。雖然BMOABC 算法沒有獲得一個特征個數(shù)為5 的解，但是其獲得的最大特征個數(shù)8 所對應(yīng)的最小分類錯誤率為14.05%，比HMIPSO 算法中特征數(shù)為5 所對應(yīng)的最小分類錯誤率都高。對于維度為100 的數(shù)據(jù)集Hillvalley，HMIPSO 算法獲得解最大特征個數(shù)為14，對應(yīng)的最小分類錯誤率為36.29%。而NSGA-II 算法獲得解最大特征個數(shù)為17，對應(yīng)的最小分類錯誤率為39.06%。BMOABC 算法獲得解最大特征個數(shù)為36，對應(yīng)的最小分類錯誤率為39.53%。HMIPSO 算法相對于NSGA-II 算法在數(shù)據(jù)集Hillvalley 所獲得的解的最大特征個數(shù)降低了3，而相對于BMOABC 算法最大特征個數(shù)降低了22。同時HMIPSO 獲得最小分類錯誤率比NSGA-II 降低了2.77%，比BMOABC 降低了3.24%。

再比較維度更大的數(shù)據(jù)集LSVT，HMIPSO 算法獲得解最大特征個數(shù)為64，對應(yīng)的最小分類錯誤率為10.00%。NSGA-II算法獲得解最大特征個數(shù)為76，對應(yīng)的最小分類錯誤率為17.50%，獲得的最小特征個數(shù)為70，對應(yīng)的最大錯誤率為33.33%。BMOABC 算法獲得解的最大特征個數(shù)為78，對應(yīng)的最小分類錯誤率為21.67%，獲得的最小特征個數(shù)為66，對應(yīng)的最大錯誤率為36.67%?？梢钥闯觯跀?shù)據(jù)集LSVT 上，HIMPSO 不僅獲得的最大特征數(shù)要少于另兩種算法獲得的解集中的任何解的特征數(shù)，而且對應(yīng)的分類錯誤率低于另兩種算法獲得任意一個解。通過以上具體分析，充分驗證了HMIPSO 算法能夠得到比NSGA-II和BMOABC 算法更好的Pareto 面。

5 結(jié)束語

本文利用一個自適應(yīng)突變操作來擾動種群，避免PSO 算法在進行全局搜索時快速收斂但容易陷入局部最優(yōu)的問題，以及利用互信息方法能夠表示數(shù)據(jù)本身之間依賴程度的優(yōu)點，對種群每次迭代產(chǎn)生的Pareto 前沿面進行局部搜索，提出了混合互信息和粒子群算法的多目標(biāo)特征選擇的方法（HMIPSO）。HMIPSO 能有效地使粒子增加相關(guān)特征或刪除不相關(guān)和冗余特征，很好地對粒子起到探索作用，平衡了粒子的全局搜索和局部搜索。通過在15 個數(shù)據(jù)集上進行比較，不僅能提高粒子群算法在多目標(biāo)特征選擇問題上的性能，也優(yōu)于另外提出的兩個算法。