基于鄰域容差互信息和鯨魚優(yōu)化算法的非平衡數(shù)據(jù)特征選擇

孫 林，黃金旭，徐久成

（1.河南師范大學 計算機與信息工程學院，河南 新鄉(xiāng) 453007；2.智慧商務與物聯(lián)網(wǎng)技術河南省工程實驗室（河南師范大學），河南 新鄉(xiāng) 453007）

0 引言

近年來，數(shù)據(jù)維度爆炸及其類分布的非平衡性給機器學習、數(shù)據(jù)挖掘等領域帶來了巨大的挑戰(zhàn)。在非平衡數(shù)據(jù)中，正類表示樣本較少的類，負類表示樣本較多的類；特征選擇可以通過選擇與少數(shù)類更相關的特征，是提高非平衡數(shù)據(jù)泛化能力和預測性能的一種非常有效的方法［1］。特征選擇作為機器學習、數(shù)據(jù)挖掘等領域數(shù)據(jù)預處理的關鍵技術之一，不僅能夠刪除冗余、不相關的特征，還能夠保證原始數(shù)據(jù)分類能力不變［2］?，F(xiàn)有的特征選擇方法大致分為3 類：過濾、包裝和嵌入［3］。過濾法先篩選特征集，再使用學習算法訓練，過程與學習算法無關，可以快速剔除噪聲特征，計算效率較高、通用性強、復雜性低、所選的特征子集冗余度小，適用于大規(guī)模數(shù)據(jù)集。包裝法依賴于所選擇的學習算法，使用分類器性能評價特征重要程度，特征子集的分類性能較好，但是不適合處理高維數(shù)據(jù)，通用性弱，計算復雜度很高?？笛愕龋?］設計了一種混合花授粉和灰狼優(yōu)化的包裝式特征選擇算法，但是僅能處理100 維以下的低維數(shù)據(jù)集。嵌入法是將特征選擇過程與分類器訓練過程結合，在使用特定學習算法訓練的同時選擇特征，但過度依賴具體的學習算法會出現(xiàn)過擬合現(xiàn)象，缺乏通用性。Aram 等［5］提出了基于支持向量機（Support Vector Machine，SVM）的線性成本敏感最大邊距的嵌入特征選擇方法，但是無法確保找到全局最優(yōu)特征。上述3 種方法均存在各自的優(yōu)勢與不足。為了有效處理高維數(shù)據(jù)集、提升計算效率和避免出現(xiàn)過擬合情況，本文使用過濾法策略設計特征選擇算法。

鄰域粗糙集既能處理離散型數(shù)據(jù)又能處理數(shù)值型和符號型數(shù)據(jù)［6］，當前關于不完備決策系統(tǒng)的研究較少。Sun等［7］針對不完備鄰域決策系統(tǒng)設計了基于悲觀鄰域熵的啟發(fā)式特征選擇算法。目前，大多數(shù)基于鄰域粗糙集的特征選擇算法是利用鄰域構建了依賴度、信息熵和知識粒度等評估函數(shù)，均滿足單調性；但是，當原始數(shù)據(jù)分類能力較差時，利用這些滿足單調性的評估函數(shù)建立的特征選擇算法存在一定的缺陷：這些評估函數(shù)取值較低，因此無法得到更好的約簡結果。為了解決這個問題，Wang 等［8］構建了基于鄰域互信息的相互區(qū)分指數(shù)，表征特征的區(qū)分能力，并設計了一種非單調特征選擇算法；姚晟等［9］利用鄰域粗糙互信息熵的非單調性，從屬性全集中更合理地選擇了具有更高決策公共鄰域粗糙信息量的特征子集，并限定了約簡集的極小性；Sun等［10］基于鄰域可信度和覆蓋度提出了決策鄰域互信息度量，設計了非單調特征選擇算法，更好地反映了高維數(shù)據(jù)的特征決策能力。另外，姚晟等［9］指出：對于原始分類性能較差的數(shù)據(jù)集，單調性約簡算法不能獲得較優(yōu)的約簡結果；但是當非單調性約簡集的分類度量值不低于原始數(shù)據(jù)集的度量值時，最終約簡集具有更優(yōu)的分類性能和更高的約簡率。由此可見，基于鄰域粗糙集的互信息是衡量特征集相關性大小的一種重要方法，具有非單調性變化的特點，是一種有效處理非單調約簡的評估函數(shù)。但是，以上方法只適用于完備型決策系統(tǒng)，不適用于處理不完備數(shù)據(jù)。在上述非單調約簡算法的啟發(fā)下，在不完備鄰域決策系統(tǒng)中，本文基于鄰域容差可信度和鄰域容差覆蓋度定義了鄰域容差互信息，并證明了鄰域容差互信息度量也是非單調的。因此，針對不完備數(shù)據(jù)，該度量方法不僅能有效度量特征之間的相關性，而且能增強不完備數(shù)據(jù)的特征決策能力。

在實際應用中，存在許多分布不均勻的非平衡數(shù)據(jù)。傳統(tǒng)的特征選擇算法在處理非平衡數(shù)據(jù)集時，分類器為了最大化整個數(shù)據(jù)集的分類精度，往往會將少數(shù)類誤分為多數(shù)類，從而忽視了少數(shù)類的影響［11］。林耀進等［12］提出了基于最大決策邊界的高維類非平衡數(shù)據(jù)在線流特征選擇算法；Chen等［13］針對非平衡數(shù)據(jù)設計了基于邊界區(qū)域的鄰域粗糙集特征選擇算法；但是，這些方法未充分考慮特征之間相關性。本文利用鄰域互信息能夠有效評估特征之間相關性的優(yōu)勢，結合基于最大決策邊界的非平衡數(shù)據(jù)重要度與鄰域容差互信息，定義了非平衡數(shù)據(jù)的鄰域容差互信息，提出了基于鄰域容差互信息的非平衡數(shù)據(jù)特征選擇（Feature Selection for Imbalanced Data based on Neighborhood tolerance mutual information，F(xiàn)SIDN）算法。

群智能優(yōu)化算法具有操作簡單、全局尋優(yōu)能力強等優(yōu)勢，通常用來解決特征選擇問題。例如：張亞釧等［14］設計了一種混合人工化學反應和狼群優(yōu)化的包裝式特征選擇算法；但是隨著樣本數(shù)和特征數(shù)的增加，該算法的計算量顯著增加，甚至根本不適用。賈鶴鳴等［15］使用改進的斑點鬣狗優(yōu)化算法設計了包裝式特征選擇方法；但是該方法僅能處理低維UCI數(shù)據(jù)集且計算效率偏低。鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）［16］通過模擬鯨魚的收縮包圍、螺旋式更新位置和隨機捕獵的覓食機制尋優(yōu)，具有參數(shù)設置簡單、收斂快和尋優(yōu)精度高等特點。Agrawal 等［17］提出了基于量子計算WOA 的包裝式特征選擇算法，增強了搜索的多樣化和收斂性。Tawhid等［18］基于二元WOA設計了包裝式特征選擇算法；但該算法須預先建立平衡分類性能的參數(shù)，計算耗時長。因此，這類包裝式方法需要大量計算，非常費時，結果可能是局部最優(yōu)解，存在過適應風險，較側重于評價方法的使用和改進［19］。

盡管群智能優(yōu)化算法在特征選擇上具有優(yōu)勢，但是一些優(yōu)化模型存在機制復雜、參數(shù)偏多等缺陷，導致求解精度與計算效率并不理想［20］。特征選擇算法中參數(shù)的設置會影響選擇結果，對于不同的數(shù)據(jù)集，參數(shù)設置往往是不同的，因此，找到最佳參數(shù)值對算法至關重要。Chen 等［13］使用粒子群優(yōu)化（Particle Swarm Optimization，PSO）優(yōu)化非平衡數(shù)據(jù)特征選擇算法中的3個參數(shù)。姚晟等［21］利用PSO算法，搜索非平衡數(shù)據(jù)屬性約簡中每個數(shù)據(jù)集的最優(yōu)2個參數(shù)值；但該算法仍使用固定的鄰域半徑，存在局限性且實驗耗時長。鑒于WOA顯著的尋優(yōu)性能，本文首先定義新的非線性收斂因子和基于適應度值的慣性權重，提出自適應權重WOA（Adaptive Weight WOA，AWWOA）；然后，利用改進WOA 優(yōu)化基于鄰域容差互信息的非平衡數(shù)據(jù)的特征選擇算法中的參數(shù)。本文的主要工作為：1）為了克服評估函數(shù)單調性存在的局限性，在不完備鄰域決策系統(tǒng)中定義了鄰域容差互信息，并證明了它的非單調性；2）針對現(xiàn)有的非平衡數(shù)據(jù)特征選擇算法未考慮不確定分類子集的影響的問題，引入最大決策邊界的非平衡數(shù)據(jù)重要度度量，并將它與鄰域容差互信息結合，提出了基于鄰域容差互信息的非平衡數(shù)據(jù)特征選擇算法；3）為解決傳統(tǒng)WOA易陷入局部最優(yōu)的問題，定義了新的非線性收斂因子和基于適應度值的慣性權重，設計了自適應權重的WOA；4）為了能夠自適應地獲取算法中參數(shù)的最佳值，利用改進的WOA，獲取不同數(shù)據(jù)集上的最優(yōu)參數(shù)。

1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法（WOA）［16］包括包圍獵物、氣泡網(wǎng)攻擊和隨機搜索3 種行為。

1）包圍獵物。預設初始適應度值最大的鯨魚所在位置為最優(yōu)位置，鯨魚群體會向最優(yōu)位置靠攏，位置更新為：

其中：M為鯨魚個體與最優(yōu)位置間的距離；Q=2k×r1-k和E=2r2為系數(shù)變量；r1和r2為［0，1］的隨機數(shù)；k=2 -為收斂控制因子，從2衰減到0；Maxiter為最大迭代次數(shù)；j為迭代次數(shù)；S′(j)為預設最優(yōu)位置；S(j)為鯨魚個體位置。

2）氣泡網(wǎng)攻擊。通過減小k值實現(xiàn)，-k＜Q＜k，由于k是遞減的，所以Q也是遞減的，因此鯨魚個體逐漸靠近最優(yōu)位置。利用螺旋線公式更新鯨魚的個體位置，表達式為：

其中：M′表示當前鯨魚個體到獵物之間的距離（當前最優(yōu)位置）；h為螺旋線常數(shù)；l為（-1，1）的隨機數(shù)。鯨魚捕捉獵物時螺旋游向獵物和收縮包圍圈同步進行，則氣泡網(wǎng)攻擊的表達式為：

其中p為［0，1］的隨機數(shù)。

3）隨機搜索。當 |Q|＞1 時，強制鯨魚群體根據(jù)隨機選擇的個體更新位置，表達式為：

其中Srand(j)表示當前群體中隨機一個鯨魚的位置。

2 非平衡數(shù)據(jù)特征選擇

2.1 非平衡數(shù)據(jù)的特征重要度

其中δ為不完備鄰域關系下鄰域半徑且0 ≤δ≤1。

2.2 鄰域容差互信息

在鄰域決策系統(tǒng)中可信度和覆蓋度能很好地評估系統(tǒng)的決策能力，具有較高的可信度和覆蓋度的條件特征比決策更重要［10］。受此啟發(fā)，為了有效處理不完備數(shù)據(jù)，運用鄰域互信息作為處理非單調約簡有效的評估函數(shù)的特性，本文在不完備鄰域決策系統(tǒng)中定義了基于容差關系的可信度和覆蓋度，并將它引入互信息中，提出了鄰域容差互信息，使它有效度量特征之間的相關性。

證明 從定義11 和定義12 顯然可以推導。

定理2給定INDS=AT=C∪D，對于任意條件特征子集B?C，H（D|B）不滿足單調性。

證明 由B1?B2?C，根據(jù)定義13 可得：

證明 由定義12～14、定理2 和定理4 顯然可得。

2.3 特征選擇算法

接下來設計FSIDN 算法，如算法1 所示。

算法1 FSIDN 算法。

假設|U|=n，|C|=m，步驟1）～4）復雜度為O(n(n+1)m2)，根據(jù)文獻［9］中的計算方法，步驟5）～6）的計算復雜度為O（mnlogn），步驟7）～8）是對特征子集評估，如果鄰域容差互信息低于特征全集的值，則步驟9）～10）需要搜索剩余特征集，直至滿足終止條件，這4 步的計算復雜度較低，步驟11）和步驟13）為剔除冗余特征的計算過程。綜上所述，算法1 總的計算復雜度約為O（mn2）。

2.4 基于WOA的參數(shù)優(yōu)化選擇

WOA 中的Q受收斂控制因子影響，收斂控制因子呈線性從2 衰減到0，導致算法易陷入局部最優(yōu)，于是提出非線性的收斂控制因子。

定義20 非線性的收斂控制因子表示為：

其中：θ為控制常數(shù)，一般取為2；j為迭代次數(shù)，Maxiter為最大迭代次數(shù)?？芍赪OA 前期，式（33）保證k′遞減速度較慢，使尋優(yōu)空間更大，避免WOA 陷入局部最優(yōu)；在WOA 后期，式（33）確保k′遞減速度較快，使跳出局部最優(yōu)。

適應度值反映了鯨魚個體當前所在位置的優(yōu)劣程度，對于適應度值較大的個體Gi，在Gi的局部區(qū)域內可能存在更優(yōu)的點，為了找到這個點，應該減小慣性權重ω以增強局部尋優(yōu)能力；相反地，對于適應度值較小的個體，應增大慣性權重ω以跳出局部最優(yōu)［20］。受此啟發(fā)，為了平衡WOA 的全局尋優(yōu)能力和局部尋優(yōu)能力，根據(jù)適應度值對慣性權重的取值進行了非線性動態(tài)調整。

定義21 基于適應度值的自適應慣性權重表示為：

其中：fiti為鯨魚個體當前的適應度值，fitavg為所有鯨魚個體當前適應度值平均值，fitmin為所有鯨魚個體當前適應度值的最小值，ωmin為慣性權重最小值，ωmax為慣性權重最大值。

定義22 依據(jù)自適應慣性權重ω，改進的WOA 的收縮包圍和螺旋捕食行為分別表示為：

其中：S′(j)為預設最佳位置；M′表示鯨魚個體與最佳位置之間的距離；h為螺旋線常數(shù)；l為（-1，1）的隨機數(shù)。

定義23 適應度函數(shù)表示為：

其中：?和τ分別表示特征依賴度和特征子集長度的參數(shù)，參照文獻［13，20］，設置?=0.9 和τ=0.1；|R| 為所選特征子集數(shù)；|C|為所有條件特征數(shù)。

算法1中涉及δ、α和β這3個參數(shù)，針對不同數(shù)據(jù)集，它們的取值往往是不同的，會影響特征選擇的結果。因此，針對不同的數(shù)據(jù)集選取最佳參數(shù)值對算法1 至關重要。本節(jié)利用改進WOA設計這3個參數(shù)的優(yōu)化選擇算法，如算法2所示。

算法2 基于自適應慣性權重的WOA 參數(shù)優(yōu)化選擇算法。

假設鯨魚群體大小為n，維度為m，初始化鯨魚種群的計算復雜度為O（nm），計算依賴度的計算復雜度為O（nmlogn），計算慣性權重的計算復雜度為O（n），步驟5）～11）的計算復雜度為O（nm），步驟12）～15）的計算復雜度為常數(shù)項，因此算法2 總的最壞計算復雜度為O（nmlogn）。

3 實驗及結果分析

3.1 改進WOA的性能分析

為了驗證本文提出的自適應權重WOA（AWWOA）的尋優(yōu)能力，選擇文獻［22］中8 個基準函數(shù)，基準函數(shù)具體信息如表1 所示。

表1 8個基準函數(shù)的信息Tab.1 Information of eight benchmark functions

將AWWOA 分別與海洋捕食者算法（Marine Predators Algorithm，MPA）［23］、PSO 算法［24］、WOA［16］、WOA［16］結合本文提出的基于適應度值的自適應慣性權重（WOA with adaptive Weight based on fitness values，WWOA）、WOA［16］結合本文提出基于非線性的收斂控制因子（WOA based on nonlinear Convergence control factor，CWOA）和基于自適應鯨魚優(yōu)化算法（Adaptive WOA，A-WOA）［25］這6 個優(yōu)化算法進行比較，其中MPA、PSO 算法和WOA 均為固定慣性權重。表1 中單峰函數(shù)f1～f4主要用來測試算法的尋優(yōu)精度和收斂能力，多峰函數(shù)f5～f8主要用來檢測算法的全局尋優(yōu)能力和避免局部收斂的能力。為了保證實驗的公平性，上述7 種優(yōu)化算法參數(shù)保持一致，即種群規(guī)模N=30，空間維度dim設置為30 和50，最大迭代次數(shù)Maxiter=300，每種算法分別獨立運行30 次，其他參數(shù)均與文獻［22］中保持一致。表2 展示了7 種優(yōu)化算法在8 個基準函數(shù)的30 維和50 維上的最優(yōu)值、最差值和平均值。

表2 7種優(yōu)化算法在2種維度8個基準函數(shù)上的實驗結果Tab.2 Experimental results of seven optimization algorithms on eight benchmark functions on two dimensions

本文實驗硬件環(huán)境設置為Intel Core i7-3770 CPU 3.40 GHz 和8 GB 內存，軟件環(huán)境配置為Windows 10 下的Matlab R2016a，本文所有實驗結果中的粗體均表示結果最佳值。

由表2 可以看出，當維度dim=30 時，對于函數(shù)f1～f3和f5～f7，AWWOA 的尋優(yōu)結果均是最優(yōu)的，并且大幅優(yōu)于其他6 種算法。值得一提的是，對于函數(shù)f7，AWWOA、A-WOA 和CWOA 的尋優(yōu)結果均達到了最優(yōu)值0；對于函數(shù)f4，PSO 算法取得的最差值為7 種算法中最優(yōu)，但是AWWOA 取得的最差值與PSO 算法相差無幾，并且AWWOA 取得的最優(yōu)值和平均值均大幅優(yōu)于其他對比算法；對于函數(shù)f8，PSO 算法取得的最優(yōu)值為7 種算法中最優(yōu)，AWWOA 取得的最差值和平均值均大幅優(yōu)于其他對比算法，說明在函數(shù)f4和f8上，在迭代過程中，PSO 算法粒子更新的速度和位置較好，同時具有自適應尋優(yōu)機制的AWWOA 表現(xiàn)出的尋優(yōu)能力與PSO 算法接近，并且與WOA 和MPA 相比性能更好。另外，通過WOA、WWOA、CWOA 和AWWOA 的實驗結果可以看出，在函數(shù)f2、f3和f5～f7上，WWOA 和CWOA 取得的結果明顯優(yōu)于WOA，在函數(shù)f1、f4和f8上，WWOA 和CWOA 取得的結果與WOA 相差無幾，但是WOA、WWOA 和CWOA 取得的結果都比AWWOA差?？傮w地，當dim=30 時，AWWOA 表現(xiàn)出了較強的全局尋優(yōu)能力和局部尋優(yōu)能力。當dim=50 時，對于函數(shù)f1、f2、f5和f8，AWWOA 的尋優(yōu)結果均是最優(yōu)的，并且大幅優(yōu)于其他6 種算法；對于函數(shù)f3，PSO 算法取得的最優(yōu)值為7 種算法中最優(yōu)，AWWOA 取得的最優(yōu)值與PSO 算法相差無幾，說明在函數(shù)f3上，在迭代過程中，PSO 算法粒子更新的速度和位置相對較好，使它獲得的最優(yōu)值較好，同時AWWOA 具有自適應的尋優(yōu)機制，使它獲得的最差值和平均值大幅優(yōu)于WOA、PSO算法和MPA；對于函數(shù)f4，MPA 取得的最差值和平均值為7種算法中最優(yōu)，AWWOA 取得的最差值和平均值與MPA 相差無幾，并且AWWOA 取得的最優(yōu)值為7 種算法中最優(yōu)；對于函數(shù)f6，MPA 取得的最差值和平均值為7 種算法中最優(yōu)，但是AWWOA 取得的最優(yōu)值達到了理論最優(yōu)值0；對于函數(shù)f7，MPA 取得的最優(yōu)值和平均值為7 種算法中最優(yōu)，但是AWWOA 取得的最優(yōu)值和平均值，明顯優(yōu)于WOA 和PSO 算法，并且AWWOA 取得的最差值優(yōu)于其他6 種算法，說明MPA 算法中的渦流和魚類聚集效應，使它很好地避開了局部最優(yōu)點，而AWWOA 中的自適應收縮包圍和螺旋捕食機制的尋優(yōu)能力與MPA 相差無幾，并且明顯優(yōu)于WOA 和PSO 算法?？傮w地，當dim=50 時，AWWOA 也表現(xiàn)出了較強的全局尋優(yōu)能力和局部尋優(yōu)能力。綜上所述，由30 維和50 維的測試結果可以看出，本文設計的非線性的收斂控制因子是有效的，同時WOA 系列算法的包圍獵物、氣泡網(wǎng)攻擊和隨機搜索的尋優(yōu)機制明顯優(yōu)于MPA 和PSO 算法，并且AWWOA 的性能優(yōu)于WOA、WWOA、CWOA 和A-WOA。AWWOA 具有較強的局部尋優(yōu)能力和較高的尋優(yōu)精度，能夠較好地避免陷入局部最優(yōu)。但是，AWWOA 在這兩種維度上的8 個基準函數(shù)的實驗結果并不是全優(yōu)，究其原因是：由于AWWOA 一方面通過非線性的收斂控制因子調整WOA 的尋優(yōu)空間，提升了WOA 跳出局部最優(yōu)的能力；另一方面通過自適應慣性權重和螺旋線常數(shù)收縮包圍和螺旋捕食行為，拉近了鯨魚個體與適應度最優(yōu)個體間的距離；盡管這些策略有效提升了AWWOA 在處理單峰與多峰函數(shù)時的尋優(yōu)精度和收斂能力，但也會在一定程度上減弱自身的全局搜索能力。

3.2 FSIDN算法性能分析

為說明FSIDN 算法的分類性能，從UCI Machine Learning Repository（https：//archive.ics.uci.edu/ml）和KEEL Data-Ming Software Too（http：//www.keel.es/software/KEEL_template.zip）中選擇了13 個非平衡數(shù)據(jù)集進行仿真實驗，具體信息如表3 所示，其中，參照文獻［13］和文獻［26］，%P 和%N 分別代表少數(shù)類樣本和多數(shù)類樣本占總樣本的比例，每個類的樣本數(shù)表示原始數(shù)據(jù)集中不同決策類中的樣本數(shù)。在WEKA 軟件中選擇了4 種分類器J48、Naive Bayes、Random Forest 和SVM 驗證FSIDN 算法的分類性能。FSIDN 算法涉及的3 個參數(shù)δ、α和β為AWWOA 尋優(yōu)到每個數(shù)據(jù)集的這3 個參數(shù)的最優(yōu)值。

表3 13個二分類非平衡數(shù)據(jù)集信息Tab.3 Information of thirteen binary imbalanced datasets

3.2.1 FSIDN在二分類數(shù)據(jù)集上的實驗結果

為驗證FSIDN在選擇特征數(shù)量方面的優(yōu)越性，在9個二分類數(shù)據(jù)集（Ionosphere、Heart、Pima、Vehicle3、Wdbc、Wpbc、Zoo、Arrhythmia 和Segment）上，將FSIDN 與F2HARNRS（Fast Forward Heterogeneous Attribute Reduction based on Neighborhood Rough Sets）［27］、WAR（Weighted Attribute Reduction algorithm）［28］、CfsSubsetEval（Correlation based feature selection Subset Evaluation）［29］、RSFSAID（Rough-Set-based Feature Selection Algorithm for Imbalanced Data）［13］這4 種特征選擇算法進行對比。為了衡量對比算法的分類性能，針對二分類數(shù)據(jù)集采用選擇最優(yōu)特征子集、曲線下面積（Area Under Curve，AUC）［13］和分類精度［26］作為性能評價指標。表4給出5種算法選擇的特征子集和特征數(shù)。參照文獻［13］，該二分類數(shù)據(jù)集上的所有實驗均通過5折交叉驗證實現(xiàn)。

表4 五種算法在8個二分類數(shù)據(jù)集上選擇的最優(yōu)特征子集和特征數(shù)Tab.4 Optimal feature subsets and the number of features selected by five algorithms on eight binary datasets

由 表4 可以看 出，F(xiàn)SIDN 在Heart、Vehicle3、Zoo 和Segment 這4 個數(shù)據(jù)集上選出的特征數(shù)比其他4 種對比算法都少；對于Ionosphere 數(shù)據(jù)集，F(xiàn)SIDN 與RSFSAID、WAR 這3種算法所選特征數(shù)相同，均少于CfsSubsetEval 和F2HARNRS；對于Wdbc 數(shù)據(jù)集，F(xiàn)SIDN 與WAR 所選特征數(shù)相同，均少于RSFSAID、CfsSubsetEval 和F2HARNRS；對于Wpbc 數(shù)據(jù)集，雖然FSIDN 所選特征數(shù)比WAR 多2 個，但比RSFSAID、CfsSubsetEval 和F2HARNRS 這3 種算法少很多；對于Arrhythmia 數(shù)據(jù)集，F(xiàn)SIDN 所選特征數(shù)比F2HARNRS 多，但是少于WAR、CfsSubsetEval 和RSFSAID。綜上所述，F(xiàn)SIDN 能夠選擇出最優(yōu)/次優(yōu)的特征子集。

為了驗證FSIDN在ROC（Receiver Operating Characteristic）指標上的分類性能，選取Arrhythmia、Heart 和Vehicle3 這3 個數(shù)據(jù)集，與F2HARNRS［27］、WAR［28］、CfsSubsetEval［29］、RSFSAID［13］、SYMON（feature selection class data using SYMmetrical uncertainty harmONy search for high dimensional imbalanced）［30］和Original（針對原始數(shù)據(jù)處理的特征選擇算法）這6 種算法進行對比，實驗結果如圖1 所示。由圖1 可以看出，黑線（FSIDN 的結果）下的面積均大于其他6 種對比算法，因此，F(xiàn)SIDN優(yōu)于其他算法。

圖1 4種分類器下7種算法在3個二分類數(shù)據(jù)集上的ROCFig.1 ROC of seven algorithms on three binary datasets under four classifiers

為了驗證FSIDN在AUC指標上選擇的特征子集的有效性，分別與F2HARNRS、WAR、CfsSubsetEval、RSFSAID和SYMON、FRSA（Feature Reduction for imbalanced data classification using Similarity-based feature clustering with Adaptive weighted K-nearest neighbors）［26］、FSAWFN［25］這7種特征選擇算法進行對比。為了方便驗證和比較，根據(jù)文獻［13］的實驗設計方法，在J48、Random Forest、Naive Bayes和SVM這4種分類器上進行實驗，如表5所示。

表5 4種分類器下8種算法在9個二分類數(shù)據(jù)集上的AUC值Tab.5 AUC values of eight algorithms on nine binary datasets under four classifiers

由表5 可以看出，在J48 分類器上，F(xiàn)SIDN 在Ionosphere、Heart、Pima、Wdbc、Wpbc 和Arrhythmia 這6 個數(shù)據(jù)集上取得的AUC 為8 種算法中最優(yōu)；對于Vehicle3、Zoo 和Segment 這3個數(shù)據(jù)集，F(xiàn)RSA 最優(yōu)，F(xiàn)SIDN 次優(yōu)。在Random Forest 分類器上，F(xiàn)SIDN 在Ionosphere、Heart、Pima、Wdbc 和Wpbc 這5 個數(shù)據(jù)集上取得的AUC 為8 種算法中最優(yōu)；對于Vehicle3 數(shù)據(jù)集，F(xiàn)SIDN 取得的AUC 值雖然比FRSA 低7.70%，但是比其他6 種算法高3.39%～25.54%；對于Zoo 數(shù)據(jù)集，雖然WAR、RSFSAID 和FRSA 取得的AUC 值比FSIDN 略優(yōu)，但是FSIDN比另外4 種算法高了1.34%～33.90%；對于Arrhythmia 數(shù)據(jù)集，WAR 取得的AUC 為最優(yōu)，但是FSIDN 比其他5 種對比算法 高0.96%～10.18%；對于Segment 數(shù)據(jù)集，RSFSAID、SYMON 和FASA 取得的AUC 為最優(yōu)，但是僅 比FSIDN 高0.02%。在Naive Bayes 分類器 上，F(xiàn)SIDN 在Ionosphere、Heart、Pima、Vehicle3、Wdbc 和Arrhythmia 這6 個數(shù)據(jù)集上取得的AUC 為最優(yōu)；對于Wpbc 和Segment 數(shù)據(jù)集，F(xiàn)SIDN 的AUC 值僅比最優(yōu)值分別低1.34%和0.04%；對于Zoo 數(shù)據(jù)集，F(xiàn)SIDN 取得的AUC 值雖然比FRSA 低15.05%，但是比其他6 種算法高2.41%～31.16%。在SVM 分類器上，F(xiàn)SIDN 在Heart、Pima、Vehicle3、Wdbc、Wpbc、Arrhythmia 和Segment 這7個數(shù)據(jù)集上的AUC 為8 種算法中最優(yōu)；對于Ionosphere 數(shù)據(jù)集，F(xiàn)RSA 取得的AUC 值為最優(yōu)，但是FSIDN 僅比最優(yōu)值低2.82%；對于Zoo 數(shù)據(jù)集，F(xiàn)SIDN 取得的AUC 值雖然比FRSA低33.93%，但是FSIDN 優(yōu)于其他6 種對比算法，而且比這6種算法均高26.20%。整體而言，F(xiàn)SIDN 在4 種分類器上取得的AUC 值優(yōu)于其他7 種對比算法，平均值分別高2.64%～14.18%、1.20%～8.06%、2.27%～7.48% 和5.90%～30.33%。綜上分析可知，F(xiàn)SIDN 在大部分情況下均優(yōu)于其他7 種比較算法，但是在Vehicle3、Zoo 和Segment 這3 個數(shù)據(jù)集上，F(xiàn)SIDN 略次于FRSA。究其原因是：FRSA 提前處理了非平衡數(shù)據(jù)，降低了數(shù)據(jù)對應的非平衡率，有利于達到較優(yōu)的分類效果，但也降低了錯分類的比例。

為了驗證FSIDN 在不同分類器下的分類精度，選取Arrhythmia、Bands、Vehicle3、Wdbc、Wpbc 和Zoo 這6 個數(shù)據(jù)集，將FSIDN 與以下4 種特征選擇算法NNRS［31］、ARMDNRS（Attribute Reduction of Mixed Data based on Neighborhood Rough Set）［32］、RSFSAID［13］和ARIHISUD（Attribute Reduction of Incomplete Hybrid Information System based on Unbalanced Data）［21］在Naive Bayes 和SVM 分類器下得到的分類精度進行比較，結果如表6 所示。由表6 可知，F(xiàn)SIDN 在Naive Bayes和SVM 分類器上的分類精度在大多數(shù)情況下為5 種算法中最優(yōu)，分別比其他5 種對比算法平均分類精度高2.19%～10.71%和0.58%～8.98%。在Naive Bayes 分類器上，在5 個數(shù)據(jù)集上，F(xiàn)SIDN 得到的分類精度均為最大；但是在Zoo 數(shù)據(jù)集上，F(xiàn)SIDN 僅比最優(yōu)的ARIHISUD 小了1.80%。在SVM分類器上，除了Wpbc 和Pima 數(shù)據(jù)集外，在其他4 個數(shù)據(jù)集上FSIDN 的分類精度均為最大，其中Pima 數(shù)據(jù)集上僅比最大值小0.88%，在Wpbc 數(shù)據(jù)集上僅比最優(yōu)值小1.52%，但比另外3 種算法大1.13%～5.41%。究其略差的可能原因是：在這兩個數(shù)據(jù)集上，F(xiàn)SIDN 濾除了個別相對重要的特征，因此FSIDN 能夠得到較優(yōu)的分類精度，具有良好的分類性能。

表6 Naive Bayes和SVM分類器下5種算法在6個二分類數(shù)據(jù)集上的分類精度Tab.6 Classification accuracy of five algorithms on six binary datasets under Navie Bayes and SVM classifiers

最后，為了驗證FSIDN 的時效性，以CPU 運行時間為評價指標，參照文獻［21］，選取6 個數(shù)據(jù)集Arrhythmia、Bands、Vehicle3、Wdbc、Wpbc 和Zoo，選 擇4 種對 比算法NNRS［31］、ARMDNRS［32］、RSFSAID［13］和ARIHISUD［21］，如圖2 所示。

圖2 5種算法在6個數(shù)據(jù)集上的運行時間比較Fig.2 Comparison of running time of five algorithms on six datasets

從圖2 可以看出，F(xiàn)SIDN 所需的時間整體上比另外4 種算法少。其中，在Pima、Vehicle3、Wdbc、Wpbc 和Arrhythmia這5 個數(shù)據(jù)集上，F(xiàn)SIDN 的運行時間明顯比其他4 種算法少；在Zoo 數(shù)據(jù)集上，F(xiàn)SIDN 比RSFSAID 和ARIHISUD 耗時多，但是比NNRS 和ARMDNRS 耗時少。整體而言，F(xiàn)SIDN 算法具有更優(yōu)秀的運行時效性。

3.2.2 FSIDN在高維基因數(shù)據(jù)集上的實驗結果

為了驗證FSIDN 在高維基因數(shù)據(jù)集上的分類性能，選擇基因數(shù)大于500 的DLBCL、Lung、SRBCT 和Breast 這4 個數(shù)據(jù)集。為了初步降低算法的時空復雜度，采用Fisher Score 算法［10］對這4 個數(shù)據(jù)集降維，在WEKA 中驗證Fisher Score 算法在不同維度下的分類精度。4 個數(shù)據(jù)集的分類精度隨所選基因數(shù)的變化趨勢如圖3 所示。由圖3 可知，每個基因數(shù)據(jù)集選擇合適的維度分別為：DLBCL 數(shù)據(jù)集為200 維，SRBCT和Lung 數(shù)據(jù)集為50 維，Breast 數(shù)據(jù)集為100 維。參照文獻［26］，在高維數(shù)據(jù)集上的實驗使用10 折交叉驗證。

圖3 4個高維基因數(shù)據(jù)集上的分類精度與所選基因數(shù)Fig.3 Classification accuracy and the number of selected genes on four high-dimensional gene datasets

針對這4 個高維基因數(shù)據(jù)集，采用幾何均值準則（Geometric mean criterion，G-mean）［26］作為分類性能的評價指標，將FSIDN 與以下6 種特征選擇算法：OSFS（Online Streaming Feature Selection）［33］、SAOLA（Scalable and Accurate OnLine Approach for feature selection）［34］、OFS_A3M（Online streaming Feature Selection using Adapted neighborhood rough set in terms of 3 Maximal evaluation criteria）［35］、OFS-Density（Online streaming Feature Selection method based on adaptive Density neighborhood relation）［36］、α-investing（streamwise feature selection using α-investing）［37］和FRSA［26］，在KNN（K-Nearest Neighbors）、CART（Classification And Regression Tree）和SVM 分類器下的G-mean 值進行比較，結果如圖4 所示。根據(jù)文獻［26，37］中的實驗參數(shù)和結果，OSFS 和SAOLA的顯著性水平參數(shù)設置為0.01。α-investing 算法的參數(shù)設置與文獻［34］一致。

圖4 3種分類器下7種算法在4個高維數(shù)據(jù)集上的G-meanFig.4 G-mean of seven algorithms on four high-dimensional datasets under three classifiers

由圖4 可以看出，在KNN 分類器下，F(xiàn)SIDN 在DLBCL、Lung 和SRBCT 數(shù)據(jù)集上的G-mean 值最大，F(xiàn)SIDN 在Breast數(shù)據(jù)集上的G-mean 值，雖然低于OSFS 和OSFS_A3M，但是高于SAOLA、OFS-Density、α-investing 和FRSA 這4 種算法。在CART 分類器下，F(xiàn)SIDN 在DLBCL、Lung 和Breast 數(shù)據(jù)集上的G-mean 值在7 種算法中明顯是最大的，F(xiàn)SIDN 在SRBCT 數(shù)據(jù)集上的G-mean 值，低于OSFS 和FRSA，但是高于SAOLA、OSFS_A3M、OFS-Density 和α-investing。在SVM 分類器下，F(xiàn)SIDN 在Lung、SRBCT 和Breast 數(shù)據(jù)集上的G-mean 值在7 種算法中最大，雖然FSIDN 在DLBCL 數(shù)據(jù)集上的G-mean 值低于 SAOLA，但是高于 OSFS、OSFS_A3M、OFS-Density、α-investing 和FRSA 這5 種算法。綜上所述，F(xiàn)SIDN 在這4 個非平衡高維基因數(shù)據(jù)集上擁有較強的分類能力。

3.2.3 FSIDN在多分類數(shù)據(jù)集上的實驗結果

對于多分類數(shù)據(jù)集，兩個多數(shù)類或少數(shù)類之間可能是非平衡的，多分類數(shù)據(jù)的特征重要度與二分類數(shù)據(jù)也是不同的，所以需要重新定義適應于多分類數(shù)據(jù)的特征重要度度量。

針對表7 中的多分類數(shù)據(jù)集，采用平均F 測度（Mean F-Measure，MFM）［13］作為分類性能的評價指標。為了驗證FSIDN 在多分類數(shù)據(jù)集上的性能，分別與Original（原始）、RSFSAID-M［13］和SYMON［30］這3 種算法 在J48、Random Forest、Naive Bayes 和SVM 這4 種分類器上進行對比實驗，實驗結果如表8 所示。除了FSIDN，其余實驗結果和參數(shù)設計均來自文獻［13］。依據(jù)文獻［13］，采用MFM 評價指標，通過5 折交叉驗證衡量多分類數(shù)據(jù)集上對比算法的分類性能。

表7 4個多分類非平衡數(shù)據(jù)集的信息Tab.7 Information of four multi-class imbalanced datasets

表8 4種分類器下不同算法在4個多分類數(shù)據(jù)集上的MFMTab.8 MFM of four algorithms on four multi-class datasets under four classifiers

由表8 可以看出，在Lymphography、Solar-flare_2、Vehicle和Car_df 這4 個數(shù)據(jù)集上，F(xiàn)SIDN 在J48 和Naive Bayes 分類器上明顯優(yōu)于其他3 種對比算法；在SVM 分類器上，除了Solar-flare_2 數(shù)據(jù)集，F(xiàn)SIDN 明顯優(yōu)于其他3 種對比算法，并且在Solar-flare_2 數(shù)據(jù)集上，F(xiàn)SIDN 僅比最優(yōu)值低1.65%；在Random Forest 分類器上，除了Vehicle 數(shù)據(jù)集以外，F(xiàn)SIDN 優(yōu)于其他3 種對比算法，并且在Vehicle 數(shù)據(jù)集上，F(xiàn)SIDN 僅比最優(yōu)值低0.40%。究其原因是：在這兩個數(shù)據(jù)集上，F(xiàn)SIDN可能存在樣本誤分類的情況。綜上所述，F(xiàn)SIDN 在多分類數(shù)據(jù)集上同樣也具有較好的分類性能。

4 結語

本文提出了基于鄰域容差互信息和改進WOA 的非平衡數(shù)據(jù)特征選擇方法。首先，考慮非平衡數(shù)據(jù)中類的不均勻分布和上下邊界域的模糊性，針對二分類和多分類數(shù)據(jù)集，提出了兩種非平衡數(shù)據(jù)的特征重要度度量；然后，為了充分反映不完備混合型鄰域決策系統(tǒng)中特征的決策能力和特征之間的相關性，定義了鄰域容差互信息；最后，將非平衡數(shù)據(jù)特征重要度度量與鄰域容差互信息結合，提出了基于鄰域容差互信息的非平衡數(shù)據(jù)特征選擇算法，利用WOA 確定該算法的最優(yōu)參數(shù)，針對WOA 存在易陷入局部最優(yōu)的問題，引入非線性收斂因子和自適應慣性權重改進WOA。在13 個非平衡數(shù)據(jù)集上的實驗結果表明，本文所提特征選擇算法是有效的。但是，在非平衡數(shù)據(jù)集中，少數(shù)類中的信息往往是最重要的，如果少數(shù)類中存在噪聲數(shù)據(jù)，可能會影響特征選擇的結果，在未來的研究中，我們將進一步研究非平衡數(shù)據(jù)特征選擇方法，降低噪聲數(shù)據(jù)的影響。