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

王金杰，李 煒

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

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

1 引言

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

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

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

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

2 背景介紹

2.1 PSO 算法

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

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

第t次迭代產生的第i個粒子的速度表示為：

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

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

2.2 互信息

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

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

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

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

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

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

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

2.3 多目標優化

多目標優化一般涉及到最大化或者最小化多個沖突目標函數。用數學術語，最小化多目標函數的公式可被寫為[5]：

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

假設y和z是k個目標最小化問題的兩個解，如果滿足：

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

對于兩個目標的問題，如圖1。

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

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

2.4 特征選擇

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

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

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

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

3 基于混合PSO 和MI 算法的多目標特征選擇方法

3.1 基于互信息方法的局部學習策略

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

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

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

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

根據上面定義的兩個集合概念，再結合差集運算，本文定義以下幾個關系概念。

定義1（>）假設有集合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 基于互信息的插入刪除操作

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

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

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

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

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

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

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

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

3.1.3 精英策略

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

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

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

3.2 自適應突變操作

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

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

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

3.3 gbest的選取

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

3.4 Archive的更新

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

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

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

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

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

圖4 為本文算法流程圖。

4 實驗設計和結果分析

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

4.1 數據集和實驗參數設置

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

Table 1 Information of datasets表1 數據集信息

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

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

算法的具體參數如下，局部搜索中提出的α=0.02，種群的大小P=30，最大迭代次數為100，Archive的大小為30。本文提出的方法HMIPSO、CMDPSO和MOPSO 算法的公共參數設置相同：學習因子c1和c2取區間[1.5,2.0]的隨機值，慣性權重ω取區間[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 算法中，限制參數limit=100，參數T=10 000。對于每個數據集都被獨立運行40 次。

4.2 實驗結果分析

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

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

4.2.1 HMIPSO 對分類的影響

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

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

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

4.2.2 HMIPSO、CMDPSO和MOPSO之間的比較

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

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

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

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

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

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

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

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

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

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

5 結束語

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