基于自適應(yīng)鯨魚優(yōu)化算法和容錯(cuò)鄰域粗糙集的特征選擇算法

孫 林 黃金旭 徐久成 馬媛媛

特征選擇作為數(shù)據(jù)預(yù)處理的關(guān)鍵步驟，目前已廣泛應(yīng)用于機(jī)器學(xué)習(xí)、模式識別、數(shù)據(jù)挖掘等領(lǐng)域[1-2].根據(jù)評價(jià)準(zhǔn)則的不同，特征選擇一般分為3類：包裝法、過濾法和嵌入法[3].包裝法使用已確定的學(xué)習(xí)算法，直接使用分類性能作為特征重要性程度的評價(jià)標(biāo)準(zhǔn).過濾法是先對特征集進(jìn)行篩選，再使用學(xué)習(xí)算法進(jìn)行訓(xùn)練，特征選擇的過程與學(xué)習(xí)算法無關(guān).嵌入法是在使用學(xué)習(xí)算法進(jìn)行訓(xùn)練的過程中，自動(dòng)進(jìn)行特征選擇.過濾法的評價(jià)準(zhǔn)則依賴學(xué)習(xí)算法，所選特征的準(zhǔn)確率低于包裝法，但是包裝法的計(jì)算開銷較大.

粗糙集模型在處理數(shù)值型數(shù)據(jù)時(shí)需要對數(shù)據(jù)進(jìn)行離散化處理，然而離散化處理可能會(huì)導(dǎo)致數(shù)據(jù)出現(xiàn)信息損失[4-6].為此，劉艷等[7]運(yùn)用K-S檢驗(yàn)，提出基于鄰域粗糙集的混合數(shù)據(jù)特征選擇算法，直接處理含有數(shù)值型和符號型數(shù)據(jù)的鄰域信息系統(tǒng).Chen等[8]分析鄰域粗糙集中上下邊界域的模糊性和類的不均勻分布，提出基于差別矩陣的特征選擇算法.Sun等[9]提出基于費(fèi)雪評分算法(Fisher Score)和多標(biāo)記鄰域粗糙集的多標(biāo)簽分類特征選擇方法.

但是，上述鄰域粗糙集模型通常沿用經(jīng)典粗糙集求解上下近似時(shí)的包含關(guān)系，導(dǎo)致鄰域粗糙集理論缺乏一定的容錯(cuò)性[10].為了解決此問題，彭瀟然等[10]利用決策粗糙集模型中的最小風(fēng)險(xiǎn)決策規(guī)則，在鄰域空間中進(jìn)行決策風(fēng)險(xiǎn)分析，提出基于容錯(cuò)改進(jìn)的鄰域粗糙集屬性約簡算法.但是，此研究是基于容錯(cuò)正域的約簡算法，并未討論鄰域粗糙集中依賴度、精度、粗糙度和特征重要度.

當(dāng)前，大部分鄰域粗糙集模型通常僅是從代數(shù)觀點(diǎn)或信息論觀點(diǎn)研究特征選擇方法.Hu等[11]基于矩陣的正域、負(fù)域和邊界域，設(shè)計(jì)動(dòng)態(tài)更新近似方法，提出基于矩陣的特征選擇算法.Wang等[12]基于距離測度,研究模糊粗糙集理論，提出基于依賴度和特征重要度的特征約簡算法.上述文獻(xiàn)都是僅從代數(shù)角度進(jìn)行特征選擇，只能反映特征對確定分類子集的影響[13].

目前，基于信息論的特征選擇已得到廣泛研究.Sun等[14]研究聯(lián)合信息熵，結(jié)合Fisher score設(shè)計(jì)特征選擇算法.然而，如果僅從信息論單方面構(gòu)造特征重要度，那么只能反映特征對不確定分類子集的影響，因此，結(jié)合代數(shù)和信息論觀點(diǎn)成為新的研究課題.Wang[15]給出代數(shù)和信息論觀點(diǎn)下的特征重要度概念，設(shè)計(jì)啟發(fā)式約簡算法.Sun等[16]結(jié)合ReliefF和鄰域互信息，提出特征選擇算法.Sun等[17]基于Lebesgue測度和熵，設(shè)計(jì)FSNTDJE(Fea-ture Selection Algorithm Based on the Neighborhood Tolerance De-pendency Joint Entropy).

群智能優(yōu)化算法具有操作簡單、全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)[18-20].學(xué)者們結(jié)合群智能優(yōu)化算法與粗糙集理論，研究特征選擇算法，已提出大量的群智能優(yōu)化算法.例如：粒子群優(yōu)化算法、蟻群優(yōu)化算法、果蠅優(yōu)化算法、蚱蜢算法、鯨魚優(yōu)化算法(Whale Opti-mization Algorithm, WOA)[20]等.相比傳統(tǒng)的特征選擇方法，結(jié)合群智能優(yōu)化算法的特征選擇方法性能更優(yōu).Wang等[21]提出PSORSFS(Particle Swarm Optimization for Rough Set-Based Feature Selection Algorithm).孫林等[22]提出基于鄰域粗糙集和帝王蝶優(yōu)化的特征選擇算法.

鯨魚優(yōu)化算法(WOA)通過模擬鯨魚的收縮包圍、螺旋式更新位置和隨機(jī)捕獵的覓食機(jī)制進(jìn)行尋優(yōu)，具有參數(shù)設(shè)置簡單、收斂速度較快、尋優(yōu)精度較高等特點(diǎn)，同時(shí)具有良好的尋優(yōu)能力[20].但是，傳統(tǒng)的WOA存在過早收斂和容易陷入局部最優(yōu)的問題[23].因此，本文使用自適應(yīng)慣性權(quán)重改進(jìn)WOA，并與容錯(cuò)鄰域粗糙集結(jié)合，提出基于自適應(yīng)WOA和容錯(cuò)鄰域粗糙集的特征選擇算法(Feature Selection Based on Adaptive WOA and Fault-Tolerance Neighborhood Rough Sets, FSAWFN).首先，提出分段式的動(dòng)態(tài)慣性權(quán)重，改進(jìn)WOA的收縮包圍和螺旋捕食階段，設(shè)計(jì)自適應(yīng)WOA(Adaptive WOA, A-WOA).再針對鄰域粗糙集的零容錯(cuò)問題，引入鄰域內(nèi)相同決策特征比例，給出具有容錯(cuò)性的上下近似、精度、粗糙度的概念.然后，將容錯(cuò)粗糙度引入熵中，提出容錯(cuò)鄰域近似條件熵的概念，實(shí)現(xiàn)代數(shù)觀點(diǎn)和信息論觀點(diǎn)的結(jié)合.最后，基于容錯(cuò)鄰域粗糙集構(gòu)造適應(yīng)度函數(shù)，使用A-WOA,不斷迭代以獲取最優(yōu)子群.針對高維數(shù)據(jù)集，采用Fisher Score進(jìn)行初步降維，降低算法的時(shí)間復(fù)雜度.在8個(gè)低維UCI數(shù)據(jù)集和6個(gè)高維基因數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文算法可有效選擇特征個(gè)數(shù)較少且分類精度較高的特征子集.

1 基礎(chǔ)知識

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

鯨魚優(yōu)化算法(WOA)是模擬座頭鯨捕食行為而提出的一種尋優(yōu)算法，主要包括包圍獵物、氣泡網(wǎng)攻擊和隨機(jī)搜索3種行為[20].下面簡要介紹3種行為的位置更新模型.

1)包圍獵物.由于目標(biāo)位置或最優(yōu)個(gè)體位置未知，WOA需要假設(shè)目標(biāo)位置.一般選擇初始適應(yīng)度值最大的個(gè)體位置為目標(biāo)位置，鯨魚群體就會(huì)游向目標(biāo)位置，位置更新公式如下：

S(j+1)=S*(j)-AM.

其中:M=|ES*(j)-S(j)|，為鯨魚個(gè)體位置到目標(biāo)位置的距離,

E=2r2

(1)

為系數(shù)變量，r2為0～1之間的隨機(jī)數(shù)，S*(j)為假設(shè)的目標(biāo)位置，S(j)為當(dāng)前鯨魚個(gè)體的位置，j為迭代次數(shù)；

A=2kr1-k，

(2)

為系數(shù)變量，

為收斂因子，在2～0之間遞減，r1為0～1之間的隨機(jī)數(shù).

2)氣泡網(wǎng)攻擊.WOA模擬鯨魚的氣泡網(wǎng)攻擊行為模型主要有如下2種.

(1)收縮包圍圈.通過減少A中k值實(shí)現(xiàn)，A的取值范圍為(-k,k)，隨著k在2～0之間遞減，A也在遞減，鯨魚個(gè)體越來越接近目標(biāo)位置.

(2)螺旋更新位置.計(jì)算鯨魚個(gè)體到目標(biāo)位置的距離，利用螺旋線公式進(jìn)行位置更新：

S(j+1)=M′ehlcos(2πl(wèi))+S*(j),

其中,

M′=|S*(j)-S(j)|,

為鯨魚個(gè)體到目標(biāo)位置的距離，h為螺旋線常數(shù)，l為(-1,1)內(nèi)的隨機(jī)數(shù).

一般情況下，鯨魚在捕獵時(shí)是邊螺旋游向獵物，邊收縮包圍圈，以0.5為閾值描述氣泡網(wǎng)攻擊，則

其中，M為鯨魚個(gè)體位置到目標(biāo)位置的距離，p為0～1之間的隨機(jī)數(shù).

3)隨機(jī)搜索.鯨魚還可利用|A|的變化進(jìn)行隨機(jī)搜索.為了增強(qiáng)WOA的全局尋優(yōu)能力，當(dāng)|A| > 1時(shí)，強(qiáng)制鯨魚群體根據(jù)隨機(jī)選擇的個(gè)體進(jìn)行位置更新：

S(j+1)=Srand(j)-AM,

(3)

其中，

M=|ESrand(j)-S(j)|,

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

1.2 鄰域粗糙集

給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，U為論域，C為條件特征集，D為決策特征集，δ∈[0,1]為鄰域半徑參數(shù).對于?xi∈U，條件特征子集B?C，ΔB為距離函數(shù)，則xi關(guān)于B的鄰域類[7]表示為：

給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意特征子集B?C，論域U上任意2個(gè)樣本點(diǎn)xi和yi,i=1,2,…,|U|之間的歐氏距離[8-9]為：

給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，樣本子集X?U，?xi∈U,i=1,2, …,|U|，則X關(guān)于B的鄰域上/下近似集[8]表示為:

給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，樣本子集X?U，則X關(guān)于B的鄰域近似精度和鄰域近似粗糙度[22]為:

給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，決策特征D導(dǎo)出的劃分U/D={D1,D2,…,Dl}，則D關(guān)于B的正域和依賴度[22]為：

其中，Dt∈U/D,t=1,2,…,l.

2 基于自適應(yīng)鯨魚優(yōu)化算法和容錯(cuò)鄰域粗糙集的特征選擇算法

2.1 自適應(yīng)鯨魚優(yōu)化算法

褚鼎立等[23]強(qiáng)調(diào)：慣性權(quán)重的取值對算法的尋優(yōu)能力和收斂能力具有至關(guān)重要的影響.在傳統(tǒng)的WOA中，慣性權(quán)重取較大的固定值，雖然保證WOA的全局尋優(yōu)能力，但不利于WOA后期的局部尋優(yōu).因此，本文將WOA的收縮包圍和螺旋捕食行為都分為前期、中期和后期3個(gè)階段，根據(jù)迭代周期對慣性權(quán)重的取值進(jìn)行動(dòng)態(tài)調(diào)整.

定義1基于迭代周期的分段式動(dòng)態(tài)慣性權(quán)重為：

(4)

其中，rand表示0～1之間的隨機(jī)數(shù)，j為迭代次數(shù)，Maxiter表示最大迭代次數(shù).

在WOA前期，ω仍保持較大的固定值，使鯨魚具有較大的搜索步長；在WOA中后期，隨著迭代的進(jìn)行，ω的取值非線性遞減，使鯨魚向全局最優(yōu)解靠近，加快WOA收斂.

根據(jù)式(4)計(jì)算慣性權(quán)重ω的值.式(4)保證ω的取值在[0,1]內(nèi)，同時(shí)，隨著WOA的執(zhí)行，ω的取值呈現(xiàn)非線性遞減，有利于避免WOA后期陷入局部最優(yōu)、無法跳出的現(xiàn)象.

定義2依據(jù)動(dòng)態(tài)慣性權(quán)重ω，自適應(yīng)WOA的收縮包圍和螺旋捕食行為表示為：

S(j+1)=ωS*(j)-AM,

(5)

S(j+1)=M′ehlcos(2πl(wèi))+ωS*(j),

(6)

其中，ω為動(dòng)態(tài)慣性權(quán)重，A為系數(shù)變量，S*(j)為假設(shè)的目標(biāo)位置，M′表示鯨魚個(gè)體到目標(biāo)位置的距離，h為螺旋線常數(shù)，l為(-1,1)內(nèi)的隨機(jī)數(shù).

A-WOA的具體步驟如下.首先，設(shè)置最優(yōu)位置或目標(biāo)位置；再根據(jù)迭代次數(shù)計(jì)算動(dòng)態(tài)慣性權(quán)重ω；然后，根據(jù)A和E的值，進(jìn)行包圍獵物、氣泡網(wǎng)攻擊和隨機(jī)搜索3種位置更新；最后，確定最優(yōu)解和最優(yōu)位置.

2.2 容錯(cuò)鄰域粗糙集

鄰域粗糙集繼承傳統(tǒng)粗糙集在構(gòu)造上下近似時(shí)的包含關(guān)系，導(dǎo)致鄰域粗糙集缺乏一定的容錯(cuò)性[10].為了解決這一問題，本文將容錯(cuò)性分析推廣到鄰域粗糙集模型中，構(gòu)建容錯(cuò)鄰域粗糙集模型，并定義基于容錯(cuò)的鄰域近似精度、粗糙度和依賴度.

其中Di表示xi對應(yīng)的等價(jià)類.同時(shí)，需要說明的是：

在傳統(tǒng)的鄰域粗糙集中，有正域

和邊界域

定義4給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，樣本子集X?U，則X關(guān)于B的容錯(cuò)鄰域上/下近似集為：

定義5給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，樣本子集X?U，則X關(guān)于B的容錯(cuò)鄰域近似精度和近似粗糙度為:

定義6給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，則決策特征D關(guān)于B的容錯(cuò)依賴度為:

粗糙度反映知識的不確定性程度，鄰域條件熵反映信息粒度引起的知識不確定性[14,17].于是，將基于容錯(cuò)的粗糙度引入鄰域條件熵中，得到基于容錯(cuò)的鄰域近似條件熵.

定義7給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，?xi∈U,i=1,2,…,|U|，U/D={D1,D2,…,Dl}，αB(Dt)為容錯(cuò)鄰域近似精度,ρB(Dt)為近似粗糙度，那么決策特征D相對于B的容錯(cuò)近似條件熵為:

(7)

2)當(dāng)且僅當(dāng)所有對象都是正域中的元素時(shí)，H(D|B)取最小值0.

ρB(Dt)=1， log2(1+ρB(Dt))=1，

又因?yàn)?/p>

因此，H(D|B)取最大值|U|log2(|U|).

再證明2).?xi∈U，xi都是正域中的元素時(shí)，有

αB(Dt)=1，ρB(Dt)=1-αB(Dt)=0，

所以

log2(1+ρB(Dt))=0，

H(D|B)取最小值0.

定理2給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意2個(gè)條件特征子集P?C,Q?C，如果Q?P，那么

H(D|P) ≤H(D|Q).

證明對于任意條件特征子集Q?P?C，樣本xi∈U，

U/D={D1,D2,…,Dl}，

于是可得，

另外

所以

H(D|P)≤H(D|Q).

因此，隨著條件特征的增加，H(D|B)是單調(diào)遞減的.

定義8給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于?B?C，當(dāng)且僅當(dāng)

1)H(D|B) =H(D|C),

2)對于?a∈B，有

H(D|B-{a})>H(D|C)，

則稱B是C相對于D的約簡.

定義9給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，?a∈B相對于D的內(nèi)部特征重要度為：

Siginner(a,B,D)=H(D|B-{a})-H(D|B).(8)

定義10給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于?a∈C，如果

H(D|C-{a})>H(D|C)，

即

Siginner(a,C,D)>0，

稱特征a為C相對于D的核特征.

定義11給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，則對于任意條件特征a∈C-B，關(guān)于決策特征D的外部特征重要度為：

Sigouter(a,B,D)=H(D|B)-H(D|B∪{a}).

Sigouter(a,B,D)的值越大，說明在已知B的條件下，特征a對于決策特征D越重要.

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

目前，適應(yīng)度函數(shù)中的特征依賴度只針對已選取的特征進(jìn)行計(jì)算，而缺少對特征空間中其它特征的分析和評價(jià)[18,24].如果加入一個(gè)特征后不改變論域中確定分類的實(shí)例，但是不確定性卻有所變化，則該特征的重要度在代數(shù)觀點(diǎn)下為0，在信息論觀點(diǎn)下重要度卻不為0.因此，本文引入基于容錯(cuò)鄰域近似條件熵的特征重要度，結(jié)合特征依賴度構(gòu)造適應(yīng)度函數(shù).

定義12給定鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，對于任意條件特征子集B?C，任意條件特征a∈C-B，基于容錯(cuò)鄰域粗糙集的新的適應(yīng)度函數(shù)為：

其中，λ1為特征依賴度參數(shù)，λ2為特征重要度參數(shù)，λ3為特征子集長度參數(shù)，λ1+λ2+λ3=1，γ′B(D)為決策特征D關(guān)于B的依賴度，Sigouter(a,B,D)為決策特征D的外部特征重要度，|B|為選擇特征子集的個(gè)數(shù)，|C|為所有條件特征的個(gè)數(shù).該適應(yīng)度函數(shù)能對所有特征進(jìn)行評價(jià)，并選擇依賴度較大、剩余特征重要度較小、長度較短的特征子集.

2.4 算法步驟

FSAWFN首先初始化鯨魚群體.然后根據(jù)更新策略更新位置，選擇適應(yīng)度最佳的個(gè)體.最后利用信息熵進(jìn)行特征選擇.具體偽代碼如算法1所示.

算法1FSAWFN

輸入鄰域決策系統(tǒng)NDS=〈U,C,D,δ〉，

鯨魚群體N，最大迭代次數(shù)Maxiter，

依賴度限制因子α、β，權(quán)重系數(shù)λ

輸出特征子集R

1.隨機(jī)產(chǎn)生大小為N、維度為|C|的鯨魚群體

POP={S1,S2,…,SN}，Si={s1,s2,…,s|C |}，

si∈[0,1]，R=?；

2.Foriter=1,2,…,Maxiter

3.將鯨魚群體POP轉(zhuǎn)化為二進(jìn)制POP′;

4.根據(jù)式(4)計(jì)算慣性權(quán)重ω；

5.根據(jù)式(1)和式(2)計(jì)算A、E；

6.If |A|<1

7.Ifp>0.5.

8.根據(jù)式(5)更新鯨魚個(gè)體的位置si；

9.Else

根據(jù)式(6)更新鯨魚個(gè)體的位置si；

10.End if

11.Else

根據(jù)式(3)更新鯨魚個(gè)體的位置si；

12.End if

13.End for

14.計(jì)算適應(yīng)度值，選擇適應(yīng)度值最佳的個(gè)體ai；

15.根據(jù)式(7)和式(8)計(jì)算容錯(cuò)鄰域近似條件熵H(D|ai)和特征重要度Siginner(ai,C,D)；

16.IfSiginner(ai,C,D)>0，

則R=R∪{ai}；

17.IfH(D|ai)=H(D|C)

18.令S=C-R，對于?a∈S，計(jì)算

Sigouter(a,C,D)；

19.選出ai，滿足

Sigouter(ai,C,D)=

max{a|Sigouter(a,C,D)，a∈S}；

20.令S=S-ai，R=R∪{ai}，計(jì)算H(D|R)；

21.IfH(D|R)=H(D|C)，

轉(zhuǎn)入26；

22.Else

返回1；

23. End if

24. End if

25.End if

26.輸出特征子集R.

設(shè)群體大小為n，維度為m，初始化種群的時(shí)間復(fù)雜度為O(nm)，計(jì)算慣性權(quán)重的時(shí)間復(fù)雜度為O(n).步驟6～步驟12更新位置的時(shí)間復(fù)雜度為O(nm).在最壞情況下，步驟17計(jì)算H(D|B)的時(shí)間復(fù)雜度為O(n2m)，需要計(jì)算m次，為O(n2m2).步驟16～步驟25計(jì)算每個(gè)特征重要度的時(shí)間復(fù)雜度為O(n2m)，在最壞的情況下需要計(jì)算m次，時(shí)間復(fù)雜度為O(n2m2).因此，F(xiàn)SAWFN總的時(shí)間復(fù)雜度為

O(2n2m2+n2m+ 2nm+n)，

約為O(n2m2).

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

3.1 自適應(yīng)鯨魚優(yōu)化算法性能分析

為了驗(yàn)證動(dòng)態(tài)慣性權(quán)重在WOA搜索后期局部尋優(yōu)的能力，對本文提出的自適應(yīng)WOA(A-WOA)進(jìn)行尋優(yōu)能力測試，選擇文獻(xiàn)[25]中6個(gè)基準(zhǔn)函數(shù)，如表1所示.表中單峰函數(shù)f1～f3主要測試算法的尋優(yōu)精度和收斂能力，多峰函數(shù)f4～f6檢測算法的全局尋優(yōu)能力和避免局部收斂的能力.

表1 基準(zhǔn)函數(shù)信息

對比算法選擇如下：海洋捕食者算法(Marine Predators Algorithm, MPA)[26]、水循環(huán)算法(Water Cycle Algorithm, WCA)[27]、WOA[20].

為了保證實(shí)驗(yàn)的公平性，4種算法參數(shù)保持一致，即種群規(guī)模N=30，空間維度dim=30,50，最大迭代次數(shù)Maxiter=300，每種算法分別獨(dú)立運(yùn)行30次.實(shí)驗(yàn)環(huán)境設(shè)置為Windows 10 、Intel(R) CPU 3.40 GHz、8.00 GB內(nèi)存，MATLAB R2016a.

4種優(yōu)化算法在6個(gè)基準(zhǔn)函數(shù)上的最優(yōu)值、最差值和平均值對比如表2所示，表中黑體數(shù)字表示最優(yōu)值.

表2 各算法在6個(gè)基準(zhǔn)函數(shù)上的性能對比

由表2可看出，A-WOA在6個(gè)基準(zhǔn)函數(shù)上性能最優(yōu)，尤其是在函數(shù)f1～f4、f6上，A-WOA的性能具有較大幅度提升.當(dāng)維度為30時(shí)，在函數(shù)f5上，MPA、WOA和A-WOA最優(yōu)值均為0，另外，A-WOA的最差值和平均值也達(dá)到0.當(dāng)維度為50時(shí)，在函數(shù)f3上，4種算法在最優(yōu)值上相差不大，但是，A-WOA在最差值和平均值上大幅優(yōu)于其它3種算法.在函數(shù)f4上，WOA和A-WOA結(jié)果相差無幾且明顯優(yōu)于MPA和WCA，但是，A-WOA取得的最優(yōu)值和平均值都優(yōu)于WOA.

綜上所述，無論是單峰函數(shù)還是多峰函數(shù)，A-WOA表現(xiàn)出優(yōu)越的局部尋優(yōu)性能,充分說明基于動(dòng)態(tài)慣性權(quán)重改進(jìn)的A-WOA較好地解決WOA容易陷入局部最優(yōu)和局部尋優(yōu)性能不穩(wěn)定的問題.

3.2 算法性能分析

為了說明FSAWFN的分類性能，在14個(gè)數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)，具體信息如表3所示，其中:前8個(gè)數(shù)據(jù)集為低維UCI數(shù)據(jù)集，選自UCI Machine Lear-ning Repository(http://archive.ics.uci.edu/ml/index.php)；后面6個(gè)為高維基因數(shù)據(jù)集，選自Cancer Program Datasets(http://portals.broadinstitute.Org/cgi-bin/cancer/datasets.cgi).

表3 實(shí)驗(yàn)數(shù)據(jù)集

在WEKA軟件中選擇J48、Naive Bayes(NB)、K近鄰(KNext Neighbor, KNN)(k=10)、CART這4種分類器，驗(yàn)證算法的分類性能.

所有實(shí)驗(yàn)都通過10折交叉驗(yàn)證實(shí)現(xiàn)[28-29].依據(jù)文獻(xiàn)[10]、文獻(xiàn)[20]、文獻(xiàn)[30]的參數(shù)設(shè)置方法，分別設(shè)置容錯(cuò)分析閾值α= 0.8，適應(yīng)度函數(shù)參數(shù)λ1=0.6，λ2=0.3,λ3=0.1.

3.2.1種群個(gè)數(shù)和迭代次數(shù)的影響

為了驗(yàn)證鯨魚個(gè)數(shù)和迭代次數(shù)對實(shí)驗(yàn)的影響，選取Ionosphere、Wine、Zoo、Soybean-small、Page-blocks、Breast數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，鯨魚個(gè)數(shù)和迭代次數(shù)對適應(yīng)度值的影響如圖1所示.

(a)鯨魚個(gè)數(shù)

由圖1(a)可看出:當(dāng)鯨魚個(gè)數(shù)由0增至50時(shí)，適應(yīng)度值也增加；當(dāng)鯨魚個(gè)數(shù)由50增至100時(shí)，適應(yīng)度值趨于穩(wěn)定.這說明當(dāng)鯨魚個(gè)數(shù)達(dá)到一定程度時(shí)，F(xiàn)SAWFN趨于穩(wěn)定，對鯨魚數(shù)量不敏感.由(b)可看出，適應(yīng)度值隨著迭代次數(shù)的增加而增加，當(dāng)?shù)螖?shù)增加到一定程度時(shí)，適應(yīng)度值趨于穩(wěn)定，說明FSAWFN經(jīng)過迭代可收斂.因此，本文選取種群個(gè)數(shù)為50，迭代次數(shù)為50，進(jìn)行后續(xù)的特征選擇實(shí)驗(yàn).

3.2.2鄰域半徑的選擇

由于鄰域半徑的不同，特征選擇得到的約簡子集和分類精度也不同，直接影響實(shí)驗(yàn)結(jié)果，于是通過研究不同鄰域參數(shù)對特征子集的約簡率[1]和分類精度的影響，為每個(gè)數(shù)據(jù)集選擇最優(yōu)的鄰域半徑.對于6個(gè)高維基因數(shù)據(jù)集，為了有效降低算法的時(shí)空復(fù)雜度，采用Fisher score[9,14]初步降維，在WEKA上獲取7種不同維度下的分類精度如表4所示,表中黑體數(shù)字表示最優(yōu)結(jié)果.由表可見，當(dāng)分類精度最優(yōu)時(shí)，Colon數(shù)據(jù)集上選擇合適的維度是500維，DLBCL、Leukemia數(shù)據(jù)集上選擇合適的維度是300維，Breast數(shù)據(jù)集上選擇合適的維度是50維，Prostate數(shù)據(jù)集上選擇合適的維度是100維，MLL數(shù)據(jù)集上選擇合適的維度是200維.

表4 6個(gè)高維基因數(shù)據(jù)集在7種不同維度下的分類精度

在14個(gè)數(shù)據(jù)集上，使用WEKA中的J48和NB分類器計(jì)算分類精度，參照文獻(xiàn)[1]、文獻(xiàn)[17]最大限度地平衡分類精度和約簡率的方法，通過實(shí)驗(yàn)選擇最優(yōu)鄰域半徑，設(shè)置鄰域半徑δ∈[0.05, 0.95]，以0.1為步長.于是，F(xiàn)SAWFN在不同的鄰域半徑下進(jìn)行特征選擇，平衡分類精度和約簡率,為每個(gè)數(shù)據(jù)集選擇最優(yōu)的鄰域半徑，具體如表5所示.

表5 2個(gè)不同分類器在14個(gè)數(shù)據(jù)集上的最優(yōu)鄰域半徑

3.2.3優(yōu)化特征選擇算法性能對比

為了有效體現(xiàn)WOA[20]在特征選擇上的運(yùn)用及其實(shí)驗(yàn)效果，本文構(gòu)建基于WOA的特征選擇算法(Feature Selection Based on WOA, WOAFS)和基于A-WOA的特征選擇算法(Feature Selection Based on A-WOA, A-WOAFS)，進(jìn)一步分析WOAFS、A-WOAFS和FSAWFN的分類性能.從表3中選擇10個(gè)數(shù)據(jù)集進(jìn)行特征選擇實(shí)驗(yàn)，分類精度如表6所示,表中黑體數(shù)字表示最優(yōu)結(jié)果.

表6 3種基于WOA的優(yōu)化特征選擇算法的分類精度

由表6可知，A-WOAFS選擇的特征個(gè)數(shù)均少于WOAFS，在分類精度方面，除了Wine、Tic-tac-toe數(shù)據(jù)集以外，A-WOAFS在J48和NB分類器上所得的分類精度高于WOAFS.在Wine數(shù)據(jù)集上，雖然A-WOAFS在J48和NB分類器上所得的分類精度略低于WOAFS，但特征個(gè)數(shù)少于WOAFS，獲得的分類精度僅略低于WOAFS.在Tic-tac-toe數(shù)據(jù)集上，雖然A-WOAFS在NB分類器上的分類精度比WOAFS降低0.032，但A-WOAFS選擇特征個(gè)數(shù)少于WOAFS，并且在J48分類器上的分類精度高于WOAFS，因此，A-WOAFS性能優(yōu)于WOAFS. FSAWFN在10個(gè)數(shù)據(jù)集上選擇特征個(gè)數(shù)少于A-WOAFS，并且分類精度高于A-WOAFS，由此可看出，將本文改進(jìn)的A-WOA與容錯(cuò)鄰域粗糙集結(jié)合能選擇特征個(gè)數(shù)較少且分類精度較高的特征子集.

3.2.4在低維UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

根據(jù)由表5得到的鄰域半徑，從選擇的特征數(shù)量和分類精度兩方面對比分析FSAWFN在低維UCI數(shù)據(jù)集上的分類性能.對比算法如下：PSORSFS[21]、DQBGOA_MR(Dynamic Population Quantum Binary Grasshopper Optimization Algorithm Based on Mutual Information and Rough Set Theory)[30]、ARRSFA(Attribute Reduction Based on Rough Sets and Discrete Firefly Algorithm)[31]、FSARSR(Fin-ding Rough Set Reducts with Fish Swarm Algori-thm)[32]、QCSIA_FS(Cooperative Swarm Intelligence Algorithm for Feature Selection Based on Quan-tum-Inspired and Rough Sets)[33].對比算法實(shí)驗(yàn)結(jié)果均來自于文獻(xiàn)[30].

各算法在8個(gè)低維UCI數(shù)據(jù)集上選擇的特征個(gè)數(shù)如表7所示，表中黑體數(shù)字表示最優(yōu)結(jié)果.由表可看出，F(xiàn)SAWFN在8個(gè)低維UCI數(shù)據(jù)集上選擇的特征個(gè)數(shù)較少，優(yōu)勢較明顯，選擇的平均特征個(gè)數(shù)最少.在Soybean-small、Zoo數(shù)據(jù)集上，F(xiàn)SAWFN和DQ-BGOA_MR得到的平均特征個(gè)數(shù)相近，但都達(dá)到最小值，并且少于其它4種算法得到的平均特征個(gè)數(shù).在Ionosphere、Mushroom、Tic-tac-toe、Vote數(shù)據(jù)集上，F(xiàn)SAWFN選擇的平均特征個(gè)數(shù)均達(dá)到最小值，優(yōu)勢顯著.在Wine數(shù)據(jù)集上,FSAWFN選擇的平均特征個(gè)數(shù)較多.在Page-blocks數(shù)據(jù)集上，F(xiàn)SAWFN的平均特征個(gè)數(shù)與QCSIA_FS和DQBGOA_MR相同，但都是最小值.

表7 各算法在8個(gè)低維UCI數(shù)據(jù)集上選擇的特征個(gè)數(shù)對比

綜上所述，F(xiàn)SAWFN在8個(gè)低維UCI數(shù)據(jù)集上能選擇較小的特征子集.最終FSAWFN選擇的最優(yōu)特征子集如表8所示.

表8 FSAWFN在8個(gè)低維UCI數(shù)據(jù)集上選擇的最優(yōu)特征子集

各算法在J48和NB分類器上得到的分類精度和標(biāo)準(zhǔn)差如表9所示，表中黑體數(shù)字表示最優(yōu)結(jié)果.由表可知，F(xiàn)SAWFN在J48和NB分類器上的分類精度多數(shù)能達(dá)到最大值，大于其它5種算法.在J48分類器上，除了Mushroom、Vote數(shù)據(jù)集以外，F(xiàn)SAWFN在其它6個(gè)數(shù)據(jù)集上均得到最大分類精度，并且在Mushroom、Vote數(shù)據(jù)集上僅比最大值分別降低0.21%和0.54%，同時(shí)FSAWFN在這2個(gè)數(shù)據(jù)集上也選擇最小的特征子集.在NB分類器上，除了Ionosphere、Page-blocks數(shù)據(jù)集以外，F(xiàn)SAWFN在其它6個(gè)數(shù)據(jù)集上均得到最大分類精度，尤其在Tic-tac-toe、Vote、Wine、Zoo數(shù)據(jù)集上優(yōu)勢更顯著.在Iono-sphere、Page-blocks數(shù)據(jù)集上，F(xiàn)SAWFN在NB分類器上的分類精度雖然略低于最大分類精度，但是，結(jié)合表7可知，F(xiàn)SAWFN選擇的特征子集最小.結(jié)合表9給出的J48和NB分類器上的分類精度對應(yīng)的標(biāo)準(zhǔn)差可看出，J48和NB分類器對應(yīng)的標(biāo)準(zhǔn)差能達(dá)到較小值.

表9 J48和NB分類器上6種算法的分類精度

綜上所述，F(xiàn)SAWFN在J48和NB分類器上能得到較小的特征子集、較大的分類精度和較小的標(biāo)準(zhǔn)差，因此具有較好的分類性能.

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

為了驗(yàn)證FSAWFN在高維基因數(shù)據(jù)集上的分類性能，選擇如下對比算法:FSNTDJE[17]、CFS(Co-rrelation Feature Selection)[29]、FCBF(Fast Correla-tion-Based Filter Algorithm)[34]、INT(Interacting Fea-tures Selection Algorithm)[34]、IG(Information Gain Based Feature Selection Algorithm)[35].

為了方便驗(yàn)證和實(shí)驗(yàn)對比，根據(jù)文獻(xiàn)[17]和文獻(xiàn)[32]的實(shí)驗(yàn)設(shè)計(jì)，選擇Colon、DLBCL、Breast、Prostate高維基因數(shù)據(jù)集,在J48和NB分類器上進(jìn)行對比實(shí)驗(yàn).

通過10折交叉驗(yàn)證，各算法選擇的基因個(gè)數(shù)如表10所示,表中黑體數(shù)字表示最優(yōu)結(jié)果.FSAWFN選擇的最優(yōu)基因子集如表11所示.

表11 FSAWFN在2個(gè)分類器上選擇的最優(yōu)基因子集

由表10可看出，除了DLBCL數(shù)據(jù)集以外，F(xiàn)SAWFN優(yōu)勢明顯，均選擇最小的基因子集.在DLBCL數(shù)據(jù)集上，盡管FSAWFN選擇的特征個(gè)數(shù)多于IG，但優(yōu)于CFS、FCBF、INT和FSNTDJE.在NB分類器上，F(xiàn)SAWFN在Colon數(shù)據(jù)集上優(yōu)勢顯著，選擇最小的基因子集；在J48分類器上，F(xiàn)SAWFN在Prostate數(shù)據(jù)集上優(yōu)勢顯著.總之，F(xiàn)SAWFN能選擇較小基因子集,并獲得較少平均基因個(gè)數(shù).

表10 各算法在4個(gè)高維基因數(shù)據(jù)集上選擇的基因個(gè)數(shù)

下面依據(jù)文獻(xiàn)[17]和文獻(xiàn)[25]中3個(gè)評價(jià)指標(biāo)，即精度(Accuracy, Acc)、真正例率(True Posi-tive Rate, TPR)、假正例率(False Positive Rate, FPR)，評價(jià)FSAWFN在Colon、DLBCL、Breast、Pros-tate數(shù)據(jù)集上的分類結(jié)果.通常TPR越大，F(xiàn)PR越小，算法性能越優(yōu).NB和J48分類器上各算法在4個(gè)數(shù)據(jù)集上的指標(biāo)值如表12和表13所示，表中ODP表示原始數(shù)據(jù)處理算法，黑體數(shù)字表示最優(yōu)值.

由表12和表13可看出，除了J48分類器上的DLBCL數(shù)據(jù)集和NB分類器上的Prostate數(shù)據(jù)集以外，F(xiàn)SAWFN都能得到較好的分類精度.從整體上看，相比其它算法，F(xiàn)SAWFN能得到較高的Acc值和較低的FPR值.在NB分類器上，在DLBCL數(shù)據(jù)集上，雖然FSAWFN選擇的基因個(gè)數(shù)多于IG，但3個(gè)指標(biāo)值均優(yōu)于IG，并且TPR達(dá)到最大值，F(xiàn)PR達(dá)到最小值.對于Acc指標(biāo)，F(xiàn)SAWFN在Colon、Breast、Prostate數(shù)據(jù)集上表現(xiàn)較優(yōu).對于TPR指標(biāo)，F(xiàn)SAWFN在DLBCL數(shù)據(jù)集上達(dá)到最大值1.對于FPR指標(biāo)，F(xiàn)SAWFN在DLBCL、Prostate數(shù)據(jù)集上達(dá)到最小.

表12 各算法在NB分類器下的指標(biāo)值

表13 各算法在J48分類器下的指標(biāo)值

同樣地，在J48分類器上，F(xiàn)SAWFN在Prostate數(shù)據(jù)集上獲得的Acc、TPR值都略小于最優(yōu)值，但是選擇的基因個(gè)數(shù)最少，并且FPR也達(dá)到最小值.對于Acc指標(biāo)，F(xiàn)SAWFN在Colon、DLBCL、Breast數(shù)據(jù)集上表現(xiàn)較優(yōu).對于TPR指標(biāo)，F(xiàn)SAWFN在DLBCL數(shù)據(jù)集上達(dá)到最大值1.對于FPR指標(biāo)，F(xiàn)SAWFN在Prostate數(shù)據(jù)集上達(dá)到最小.

為了進(jìn)一步驗(yàn)證FSAWFN在高維數(shù)據(jù)集上的分類性能，選取Colon、Leukemia、Breast、MLL數(shù)據(jù)集.對比算法選擇ODP、FSNTDJE[17]、DMRA(Dis-cernibility Matrix-Based Reduction Algorithm)[36]、FPR(Fuzzy Positive Region Reduction)[37]、FRFS(Fuzzy-Rough Feature Selection Algorithm)[38]、IFPR(Intuitionistic Fuzzy Positive Region Based Gene Selection Algorithm)[39].通過10折交叉驗(yàn)證，獲得KNN(k=10)和CART分類器上的分類精度如表14所示.

由表14可見，F(xiàn)SAWFN在4個(gè)高維數(shù)據(jù)集上均取得最大的分類精度.在KNN分類器上，F(xiàn)SAWFN在Leukemia、Breast數(shù)據(jù)集上優(yōu)勢明顯.在Colon、MLL數(shù)據(jù)集上，F(xiàn)SAWFN分類精度略高于FSNTDJE，但優(yōu)于ODP、DMRA、FPR、FRFS、IFPR.在CART分類器上， FSAWFN在Leukemia、Breast、MLL數(shù)據(jù)集上優(yōu)勢明顯.在Colon數(shù)據(jù)集上，F(xiàn)SAWFN分類精度率略高于FSNTDJE，但優(yōu)于ODP、DMRA、FPR、FRFS、IFPR.因此FSAWFN具有較好的分類效果.

表14 KNN和CART分類器上7種算法的分類精度

3.3 統(tǒng)計(jì)分析

為了對FSAWFN的分類結(jié)果進(jìn)行統(tǒng)計(jì)驗(yàn)證，選擇Friedman檢驗(yàn)和Bonferroni-Dunn檢驗(yàn)，分別定義如下：

其中，s為算法數(shù)量，T為數(shù)據(jù)集數(shù)量，Ra(a=1,2,…,s)為第a種算法的平均排序.FF服從F分布，如果通過Friedman檢驗(yàn)得到的所有算法性能明顯不一樣，需要post-hoc檢驗(yàn)以對比各算法，常用的后續(xù)檢驗(yàn)為Nemenyi檢驗(yàn)，臨界差值[40]為：

其中，α為顯著性水平，這里選擇α=0.1，qα為臨界值.

根據(jù)表9中各算法在8個(gè)UCI數(shù)據(jù)集上的分類精度，進(jìn)行Friedman檢驗(yàn)，結(jié)果如表15所示.當(dāng)α=0.1時(shí)，

由表15可知，在J48和NB分類器上各對比算法性能顯著不同，于是進(jìn)行post-hoc檢驗(yàn).

表15 J48和NB分類器上6種算法的統(tǒng)計(jì)結(jié)果

為了直觀說明算法的差異，6種算法在J48和NB分類器上的Bonferroni-Dunn檢驗(yàn)結(jié)果如圖2所示.

由圖2(a)可知，F(xiàn)SAWFN平均排序最小，與DQBG-OA_MR、FSARSR、PSORSFS無顯著性差距，但明顯優(yōu)于ARRSFA和QCSIA_FS.由(b)可知，F(xiàn)SAWFN平均排序最小，明顯優(yōu)于FSARSR.總之，F(xiàn)SAWFN性能最優(yōu).

(a)J48 (b)NB

對表14中4個(gè)高維基因數(shù)據(jù)集的分類精度進(jìn)行Friedman檢驗(yàn)，結(jié)果如表16所示.當(dāng)α=0.1時(shí)，

q0.1=2.326，CD=3.077，

根據(jù)表16可知，在KNN和CART分類器上各算法的性能顯著不同，因此進(jìn)行post-hoc檢驗(yàn).

表16 KNN和CART分類器上6種算法的統(tǒng)計(jì)結(jié)果

各算法在KNN和CART分類器上的Bon-ferroni-Dunn檢驗(yàn)結(jié)果如圖3所示.由(a)可看出，F(xiàn)SAWFN平均排序最小，與FSNTDJE、DMRA、IFPR無顯著性差距，優(yōu)于FRFS和FPR.由(b)可知，F(xiàn)SAWFN平均排序最小，優(yōu)于FRFS、FPR、DMRA.總之，F(xiàn)SAWFN明顯優(yōu)于其它算法.

(a)KNN (b)CART

4 結(jié) 束 語

利用WOA操作簡單、計(jì)算參數(shù)較少、全局尋優(yōu)能力較強(qiáng)等優(yōu)點(diǎn)，本文提出基于自適應(yīng)WOA和容錯(cuò)鄰域粗糙集的特征選擇算法(FSAWFN).首先，提出動(dòng)態(tài)慣性權(quán)重，設(shè)計(jì)自適應(yīng)WOA.然后，解決鄰域粗糙集缺乏容錯(cuò)性問題，提出容錯(cuò)上下近似集、容錯(cuò)近似精度、容錯(cuò)近似粗糙度、容錯(cuò)依賴度及容錯(cuò)近似條件熵.最后，使用自適應(yīng)WOA進(jìn)行預(yù)處理,獲取最優(yōu)子群，進(jìn)而結(jié)合容錯(cuò)鄰域粗糙集設(shè)計(jì)特征選擇算法.在8個(gè)UCI數(shù)據(jù)集和6個(gè)高維基因數(shù)據(jù)集上的實(shí)驗(yàn)表明：本文算法是有效的，通過對WOA進(jìn)行的自適應(yīng)改進(jìn)，能更容易收斂到最優(yōu)或接近最優(yōu)解；將自適應(yīng)WOA與容錯(cuò)鄰域粗糙集結(jié)合能使算法更快找到最小特征子集.但是，在運(yùn)行時(shí)效上，本文算法的改善效果并不明顯，這是下一步需要研究的內(nèi)容.