孫 林，黃金旭，徐久成

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

0 引言

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

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

在實(shí)際應(yīng)用中，存在許多分布不均勻的非平衡數(shù)據(jù)。傳統(tǒng)的特征選擇算法在處理非平衡數(shù)據(jù)集時(shí)，分類器為了最大化整個(gè)數(shù)據(jù)集的分類精度，往往會將少數(shù)類誤分為多數(shù)類，從而忽視了少數(shù)類的影響［11］。林耀進(jìn)等［12］提出了基于最大決策邊界的高維類非平衡數(shù)據(jù)在線流特征選擇算法；Chen等［13］針對非平衡數(shù)據(jù)設(shè)計(jì)了基于邊界區(qū)域的鄰域粗糙集特征選擇算法；但是，這些方法未充分考慮特征之間相關(guān)性。本文利用鄰域互信息能夠有效評估特征之間相關(guān)性的優(yōu)勢，結(jié)合基于最大決策邊界的非平衡數(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)能力強(qiáng)等優(yōu)勢，通常用來解決特征選擇問題。例如：張亞釧等［14］設(shè)計(jì)了一種混合人工化學(xué)反應(yīng)和狼群優(yōu)化的包裝式特征選擇算法；但是隨著樣本數(shù)和特征數(shù)的增加，該算法的計(jì)算量顯著增加，甚至根本不適用。賈鶴鳴等［15］使用改進(jìn)的斑點(diǎn)鬣狗優(yōu)化算法設(shè)計(jì)了包裝式特征選擇方法；但是該方法僅能處理低維UCI數(shù)據(jù)集且計(jì)算效率偏低。鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）［16］通過模擬鯨魚的收縮包圍、螺旋式更新位置和隨機(jī)捕獵的覓食機(jī)制尋優(yōu)，具有參數(shù)設(shè)置簡單、收斂快和尋優(yōu)精度高等特點(diǎn)。Agrawal 等［17］提出了基于量子計(jì)算WOA 的包裝式特征選擇算法，增強(qiáng)了搜索的多樣化和收斂性。Tawhid等［18］基于二元WOA設(shè)計(jì)了包裝式特征選擇算法；但該算法須預(yù)先建立平衡分類性能的參數(shù)，計(jì)算耗時(shí)長。因此，這類包裝式方法需要大量計(jì)算，非常費(fèi)時(shí)，結(jié)果可能是局部最優(yōu)解，存在過適應(yīng)風(fēng)險(xiǎn)，較側(cè)重于評價(jià)方法的使用和改進(jìn)［19］。

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

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

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

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

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

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

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

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

3）隨機(jī)搜索。當(dāng) |Q|＞1 時(shí)，強(qiáng)制鯨魚群體根據(jù)隨機(jī)選擇的個(gè)體更新位置，表達(dá)式為：

其中Srand(j)表示當(dāng)前群體中隨機(jī)一個(gè)鯨魚的位置。

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

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

其中δ為不完備鄰域關(guān)系下鄰域半徑且0 ≤δ≤1。

2.2 鄰域容差互信息

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

證明 從定義11 和定義12 顯然可以推導(dǎo)。

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

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

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

2.3 特征選擇算法

接下來設(shè)計(jì)FSIDN 算法，如算法1 所示。

算法1 FSIDN 算法。

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

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

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

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

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

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

定義21 基于適應(yīng)度值的自適應(yīng)慣性權(quán)重表示為：

其中：fiti為鯨魚個(gè)體當(dāng)前的適應(yīng)度值，fitavg為所有鯨魚個(gè)體當(dāng)前適應(yīng)度值平均值，fitmin為所有鯨魚個(gè)體當(dāng)前適應(yīng)度值的最小值，ωmin為慣性權(quán)重最小值，ωmax為慣性權(quán)重最大值。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

3.1 改進(jìn)WOA的性能分析

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

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

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

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

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

由表2 可以看出，當(dāng)維度dim=30 時(shí)，對于函數(shù)f1～f3和f5～f7，AWWOA 的尋優(yōu)結(jié)果均是最優(yōu)的，并且大幅優(yōu)于其他6 種算法。值得一提的是，對于函數(shù)f7，AWWOA、A-WOA 和CWOA 的尋優(yōu)結(jié)果均達(dá)到了最優(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 算法粒子更新的速度和位置較好，同時(shí)具有自適應(yīng)尋優(yōu)機(jī)制的AWWOA 表現(xiàn)出的尋優(yōu)能力與PSO 算法接近，并且與WOA 和MPA 相比性能更好。另外，通過WOA、WWOA、CWOA 和AWWOA 的實(shí)驗(yàn)結(jié)果可以看出，在函數(shù)f2、f3和f5～f7上，WWOA 和CWOA 取得的結(jié)果明顯優(yōu)于WOA，在函數(shù)f1、f4和f8上，WWOA 和CWOA 取得的結(jié)果與WOA 相差無幾，但是WOA、WWOA 和CWOA 取得的結(jié)果都比AWWOA差?？傮w地，當(dāng)dim=30 時(shí)，AWWOA 表現(xiàn)出了較強(qiáng)的全局尋優(yōu)能力和局部尋優(yōu)能力。當(dāng)dim=50 時(shí)，對于函數(shù)f1、f2、f5和f8，AWWOA 的尋優(yōu)結(jié)果均是最優(yōu)的，并且大幅優(yōu)于其他6 種算法；對于函數(shù)f3，PSO 算法取得的最優(yōu)值為7 種算法中最優(yōu)，AWWOA 取得的最優(yōu)值與PSO 算法相差無幾，說明在函數(shù)f3上，在迭代過程中，PSO 算法粒子更新的速度和位置相對較好，使它獲得的最優(yōu)值較好，同時(shí)AWWOA 具有自適應(yīng)的尋優(yōu)機(jī)制，使它獲得的最差值和平均值大幅優(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)值達(dá)到了理論最優(yōu)值0；對于函數(shù)f7，MPA 取得的最優(yōu)值和平均值為7 種算法中最優(yōu)，但是AWWOA 取得的最優(yōu)值和平均值，明顯優(yōu)于WOA 和PSO 算法，并且AWWOA 取得的最差值優(yōu)于其他6 種算法，說明MPA 算法中的渦流和魚類聚集效應(yīng)，使它很好地避開了局部最優(yōu)點(diǎn)，而AWWOA 中的自適應(yīng)收縮包圍和螺旋捕食機(jī)制的尋優(yōu)能力與MPA 相差無幾，并且明顯優(yōu)于WOA 和PSO 算法。總體地，當(dāng)dim=50 時(shí)，AWWOA 也表現(xiàn)出了較強(qiáng)的全局尋優(yōu)能力和局部尋優(yōu)能力。綜上所述，由30 維和50 維的測試結(jié)果可以看出，本文設(shè)計(jì)的非線性的收斂控制因子是有效的，同時(shí)WOA 系列算法的包圍獵物、氣泡網(wǎng)攻擊和隨機(jī)搜索的尋優(yōu)機(jī)制明顯優(yōu)于MPA 和PSO 算法，并且AWWOA 的性能優(yōu)于WOA、WWOA、CWOA 和A-WOA。AWWOA 具有較強(qiáng)的局部尋優(yōu)能力和較高的尋優(yōu)精度，能夠較好地避免陷入局部最優(yōu)。但是，AWWOA 在這兩種維度上的8 個(gè)基準(zhǔn)函數(shù)的實(shí)驗(yàn)結(jié)果并不是全優(yōu)，究其原因是：由于AWWOA 一方面通過非線性的收斂控制因子調(diào)整WOA 的尋優(yōu)空間，提升了WOA 跳出局部最優(yōu)的能力；另一方面通過自適應(yīng)慣性權(quán)重和螺旋線常數(shù)收縮包圍和螺旋捕食行為，拉近了鯨魚個(gè)體與適應(yīng)度最優(yōu)個(gè)體間的距離；盡管這些策略有效提升了AWWOA 在處理單峰與多峰函數(shù)時(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 個(gè)非平衡數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，具體信息如表3 所示，其中，參照文獻(xiàn)［13］和文獻(xiàn)［26］，%P 和%N 分別代表少數(shù)類樣本和多數(shù)類樣本占總樣本的比例，每個(gè)類的樣本數(shù)表示原始數(shù)據(jù)集中不同決策類中的樣本數(shù)。在WEKA 軟件中選擇了4 種分類器J48、Naive Bayes、Random Forest 和SVM 驗(yàn)證FSIDN 算法的分類性能。FSIDN 算法涉及的3 個(gè)參數(shù)δ、α和β為AWWOA 尋優(yōu)到每個(gè)數(shù)據(jù)集的這3 個(gè)參數(shù)的最優(yōu)值。

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

3.2.1 FSIDN在二分類數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

為驗(yàn)證FSIDN在選擇特征數(shù)量方面的優(yōu)越性，在9個(gè)二分類數(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 種特征選擇算法進(jìn)行對比。為了衡量對比算法的分類性能，針對二分類數(shù)據(jù)集采用選擇最優(yōu)特征子集、曲線下面積（Area Under Curve，AUC）［13］和分類精度［26］作為性能評價(jià)指標(biāo)。表4給出5種算法選擇的特征子集和特征數(shù)。參照文獻(xiàn)［13］，該二分類數(shù)據(jù)集上的所有實(shí)驗(yàn)均通過5折交叉驗(yàn)證實(shí)現(xiàn)。

表4 五種算法在8個(gè)二分類數(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 個(gè)數(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 個(gè)，但比RSFSAID、CfsSubsetEval 和F2HARNRS 這3 種算法少很多；對于Arrhythmia 數(shù)據(jù)集，F(xiàn)SIDN 所選特征數(shù)比F2HARNRS 多，但是少于WAR、CfsSubsetEval 和RSFSAID。綜上所述，F(xiàn)SIDN 能夠選擇出最優(yōu)/次優(yōu)的特征子集。

為了驗(yàn)證FSIDN在ROC（Receiver Operating Characteristic）指標(biāo)上的分類性能，選取Arrhythmia、Heart 和Vehicle3 這3 個(gè)數(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 種算法進(jìn)行對比，實(shí)驗(yàn)結(jié)果如圖1 所示。由圖1 可以看出，黑線（FSIDN 的結(jié)果）下的面積均大于其他6 種對比算法，因此，F(xiàn)SIDN優(yōu)于其他算法。

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

為了驗(yàn)證FSIDN在AUC指標(biāo)上選擇的特征子集的有效性，分別與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ìn)行對比。為了方便驗(yàn)證和比較，根據(jù)文獻(xiàn)［13］的實(shí)驗(yàn)設(shè)計(jì)方法，在J48、Random Forest、Naive Bayes和SVM這4種分類器上進(jìn)行實(shí)驗(yàn)，如表5所示。

表5 4種分類器下8種算法在9個(gè)二分類數(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 個(gè)數(shù)據(jù)集上取得的AUC 為8 種算法中最優(yōu)；對于Vehicle3、Zoo 和Segment 這3個(gè)數(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 個(gè)數(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 個(gè)數(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個(gè)數(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 個(gè)數(shù)據(jù)集上，F(xiàn)SIDN 略次于FRSA。究其原因是：FRSA 提前處理了非平衡數(shù)據(jù)，降低了數(shù)據(jù)對應(yīng)的非平衡率，有利于達(dá)到較優(yōu)的分類效果，但也降低了錯(cuò)分類的比例。

為了驗(yàn)證FSIDN 在不同分類器下的分類精度，選取Arrhythmia、Bands、Vehicle3、Wdbc、Wpbc 和Zoo 這6 個(gè)數(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 分類器下得到的分類精度進(jìn)行比較，結(jié)果如表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 個(gè)數(shù)據(jù)集上，F(xiàn)SIDN 得到的分類精度均為最大；但是在Zoo 數(shù)據(jù)集上，F(xiàn)SIDN 僅比最優(yōu)的ARIHISUD 小了1.80%。在SVM分類器上，除了Wpbc 和Pima 數(shù)據(jù)集外，在其他4 個(gè)數(shù)據(jù)集上FSIDN 的分類精度均為最大，其中Pima 數(shù)據(jù)集上僅比最大值小0.88%，在Wpbc 數(shù)據(jù)集上僅比最優(yōu)值小1.52%，但比另外3 種算法大1.13%～5.41%。究其略差的可能原因是：在這兩個(gè)數(shù)據(jù)集上，F(xiàn)SIDN 濾除了個(gè)別相對重要的特征，因此FSIDN 能夠得到較優(yōu)的分類精度，具有良好的分類性能。

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

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

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

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

3.2.2 FSIDN在高維基因數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

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

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

針對這4 個(gè)高維基因數(shù)據(jù)集，采用幾何均值準(zhǔn)則（Geometric mean criterion，G-mean）［26］作為分類性能的評價(jià)指標(biāo)，將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 值進(jìn)行比較，結(jié)果如圖4 所示。根據(jù)文獻(xiàn)［26，37］中的實(shí)驗(yàn)參數(shù)和結(jié)果，OSFS 和SAOLA的顯著性水平參數(shù)設(shè)置為0.01。α-investing 算法的參數(shù)設(shè)置與文獻(xiàn)［34］一致。

圖4 3種分類器下7種算法在4個(gè)高維數(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 個(gè)非平衡高維基因數(shù)據(jù)集上擁有較強(qiáng)的分類能力。

3.2.3 FSIDN在多分類數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

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

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

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

表8 4種分類器下不同算法在4個(gè)多分類數(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 個(gè)數(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%。究其原因是：在這兩個(gè)數(shù)據(jù)集上，F(xiàn)SIDN可能存在樣本誤分類的情況。綜上所述，F(xiàn)SIDN 在多分類數(shù)據(jù)集上同樣也具有較好的分類性能。

4 結(jié)語

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