基于新冗余度的特征選擇方法

李占山，呂艾娜

(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春 130012)

特征選擇是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中一個(gè)重要的數(shù)據(jù)預(yù)處理過(guò)程.特征選擇的目的是從原始特征集中選出相關(guān)特征子集，這些子集可以有效地描述樣本數(shù)據(jù)，減少冗余或無(wú)關(guān)特征對(duì)預(yù)測(cè)結(jié)果的影響.目前特征選擇有過(guò)濾式、包裹式、嵌入式三種類(lèi)型.過(guò)濾式方法基于一些衡量指標(biāo)，如距離[1]或互信息[2]評(píng)估特征，結(jié)合基于貪心思想的搜索方法，如順序向前SFS向后SBS[3]進(jìn)行特征選擇，生成特征子集.這會(huì)導(dǎo)致算法過(guò)早收斂,陷入局部最優(yōu).包裹式方法則直接針對(duì)給定學(xué)習(xí)器進(jìn)行優(yōu)化.由于包裹式方法在特征選擇過(guò)程中需要多次訓(xùn)練學(xué)習(xí)器，因此包裹式特征選擇的計(jì)算開(kāi)銷(xiāo)要比過(guò)濾式方法大得多.在過(guò)濾式和包裹式方法中，特征選擇過(guò)程與學(xué)習(xí)器訓(xùn)練過(guò)程有明顯的分別.而嵌入式方法則是在學(xué)習(xí)器訓(xùn)練過(guò)程中自動(dòng)地進(jìn)行特征選擇.

特征選擇本質(zhì)上是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，通過(guò)最大化特征與標(biāo)簽的相關(guān)度，同時(shí)最小化特征間的冗余度，篩選出對(duì)學(xué)習(xí)器貢獻(xiàn)大的特征.由于多目標(biāo)進(jìn)化算法的啟發(fā)式搜索可以有效地避免搜索陷入局部最優(yōu)陷阱，因此現(xiàn)有過(guò)濾式特征選擇算法通常結(jié)合進(jìn)化計(jì)算方法生成特征子集.但是目前過(guò)濾式結(jié)合多目標(biāo)進(jìn)化算法進(jìn)行特征選擇的方法存在兩個(gè)問(wèn)題:①衡量特征間冗余度時(shí)沒(méi)有考慮標(biāo)簽信息對(duì)特征的影響；②現(xiàn)有方法采用的多目標(biāo)算法大都是基于非支配排序框架，而大量實(shí)驗(yàn)結(jié)果表明基于分解的框架，可以獲得更低的時(shí)間復(fù)雜度，找到更好的Pareto前沿面，得到對(duì)學(xué)習(xí)器貢獻(xiàn)更大的特征子集.

本文利用多目標(biāo)進(jìn)化算法能充分考慮特征空間的優(yōu)勢(shì)，結(jié)合新的冗余度衡量標(biāo)準(zhǔn)MIFS-CR[4]及基于分解框架的多目標(biāo)優(yōu)化算法MOEA/D-DE[5]，將特征選擇問(wèn)題轉(zhuǎn)化為一個(gè)多目標(biāo)優(yōu)化問(wèn)題.同時(shí)為保證子集的稀疏性，引入l1正則化作為稀疏項(xiàng).實(shí)驗(yàn)表明本文的方法能很好地縮減特征子集的維度并提高學(xué)習(xí)器的學(xué)習(xí)率.

1 基于信息論的過(guò)濾式方法

熵與互信息(mutual information,MI)是信息論中兩個(gè)重要的概念.熵(H)是隨機(jī)變量不確定度的度量指標(biāo).互信息(I)則用來(lái)衡量?jī)蓚€(gè)隨機(jī)變量之間的相關(guān)性，互信息和熵具有以下關(guān)系，如式(1)和圖1所示.

I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=
H(X)+H(Y)-H(X,Y).

(1)

近年來(lái)，涌現(xiàn)出大量基于信息論的特征選擇方法并取得了令人滿意的結(jié)果.Battit首先提出MIFS[6]方法來(lái)解決特征間冗余度問(wèn)題.MIFS采用的衡量標(biāo)準(zhǔn):

(2)

其中:fi表示待選特征;fs是已選特征;C是標(biāo)簽.J(fi)越大，特征fi對(duì)提高學(xué)習(xí)器準(zhǔn)確率的貢獻(xiàn)程度越高.參數(shù)β用來(lái)調(diào)節(jié)相關(guān)度與冗余度的相對(duì)重要程度.

Kwak等[7]提出了MIFS-U方法:

I(fi|fs;C)=I(fi;C)-{I(fs;fi)-I(fs;fi|C)}.

(3)

其中,I(fi|fs;C)表示在fs給定的條件下，標(biāo)簽C與特征fi之間的互信息.I(fi|fs;C)可以根據(jù)假設(shè)：信息在整個(gè)H(fs)區(qū)域均勻分布，進(jìn)行適當(dāng)估計(jì):

(4)

該方法認(rèn)為特征間的冗余信息受標(biāo)簽信息的影響，并提出新的熵與互信息的關(guān)系，見(jiàn)圖2.

H(fs)=H(fs|C)-I(fs;C),

(5)

(6)

經(jīng)過(guò)式(5)，式(6)的推導(dǎo)，MIFS-U最終的特征選擇標(biāo)準(zhǔn):

(7)

由于將標(biāo)簽信息考慮進(jìn)來(lái)，因此MIFS-U能比MIFS方法更好地衡量特征之間的關(guān)系.

2 MOEA/D-DEFS方法

2.1 新冗余度衡量標(biāo)準(zhǔn)

實(shí)際上I(fi;fs)中的信息分布取決于fs和fi，不像MIFS-U中那樣僅認(rèn)為I(fi;fs)區(qū)域中的信息分布由H(fs)中的信息分布確定.類(lèi)似MIFS-U，本文假設(shè)信息也是均勻分布在H(fi)區(qū)域中的，那么有

(8)

改進(jìn)后的特征間冗余度標(biāo)準(zhǔn):

(9)

2.2 目標(biāo)函數(shù)

特征選擇的目的是找到一個(gè)特征子集S，保證組成該特征子集的特征與標(biāo)簽高度相關(guān).

(10)

同時(shí)特征之間的冗余度FRED最小:

(11)

為了讓搜索到的特征子集的維度|S|盡可能小，本文引入了一個(gè)稀疏項(xiàng)l1正則化，保證特征子集的稀疏性.文中定義了兩個(gè)目標(biāo)函數(shù)F1，F(xiàn)2.

(12)

其中，F(xiàn)REL用來(lái)衡量特征與標(biāo)簽的相關(guān)度.由于FREL恒正，本文取FREL的相反數(shù)，保證在求解多目標(biāo)問(wèn)題(13)時(shí)，特征與標(biāo)簽間的相關(guān)度更大，能找到更好的解.λ1，λ2是懲罰系數(shù)，經(jīng)過(guò)在不同數(shù)據(jù)集上的實(shí)驗(yàn)，當(dāng)λ1=0.03，λ2=0.01時(shí)實(shí)驗(yàn)效果最好.

至此特征選擇被轉(zhuǎn)化為求解一個(gè)多目標(biāo)優(yōu)化問(wèn)題:

(13)

多目標(biāo)優(yōu)化問(wèn)題指的是要同時(shí)優(yōu)化的多個(gè)目標(biāo)之間存在相互沖突，一個(gè)解在某個(gè)目標(biāo)上是好的，而在其他目標(biāo)上卻可能是較差的.因此，存在一個(gè)折中解的集合，稱為Pareto最優(yōu)解集.

2.3 MOEA/D-DEFS

本文采用基于分解的框架MOEA/D結(jié)合差分進(jìn)化(DE)算子將特征選擇問(wèn)題視為一個(gè)二目標(biāo)問(wèn)題.通過(guò)找到一組相關(guān)度大、冗余度小的特征子集，訓(xùn)練分類(lèi)器并驗(yàn)證特征子集對(duì)分類(lèi)準(zhǔn)確率的影響.MOEA/D-DE算法的具體實(shí)現(xiàn)及其相應(yīng)的偽代碼，詳見(jiàn)2.3.1～2.3.3節(jié).

算法1 MOEA/D-DEFS框架

輸入：多目標(biāo)優(yōu)化問(wèn)題(13);N:子問(wèn)題數(shù)量;T:鄰居集合大小;λ1,λ2,…,λN:一組隨機(jī)分布權(quán)重向量.

輸出：分類(lèi)準(zhǔn)確率.

1)MOEA/D-DEFS;

2)生成Pareto 非支配解(特征子集);

3)返回生成的特征子集及其對(duì)應(yīng)的分類(lèi)準(zhǔn)確率.

2.3.1 MOEA/D方法及其初始化

MOEA/D采用近鄰思想:子問(wèn)題與其對(duì)應(yīng)鄰居子問(wèn)題擁有相似的最優(yōu)解.將多目標(biāo)優(yōu)化問(wèn)題分解成N個(gè)單目標(biāo)優(yōu)化子問(wèn)題并相應(yīng)地為每個(gè)子問(wèn)題賦予一個(gè)權(quán)重向量λ.由于權(quán)重向量的距離較小, 因此子問(wèn)題與對(duì)應(yīng)鄰居子問(wèn)題擁有相似的最優(yōu)解.依照權(quán)重距離的大小為每個(gè)子問(wèn)題構(gòu)建鄰居集合B，通過(guò)比較當(dāng)前個(gè)體與對(duì)應(yīng)鄰居子問(wèn)題擇優(yōu)替換，更新參考點(diǎn)z.

MOEA/D方法的初始化:

1)通過(guò)計(jì)算任意兩個(gè)權(quán)重向量之間的歐氏距離，初始化鄰居集合B；

2)在目標(biāo)空間中隨機(jī)初始化種群{x1,…,xN};

3)通過(guò)公式(13)計(jì)算子問(wèn)題的目標(biāo)函數(shù)F(xi),?i=1，…，N;

根據(jù)近鄰思想, 針對(duì)繁殖算子和替換策略，通過(guò)維護(hù)鄰居集合, 在選擇繁殖個(gè)體和替換個(gè)體時(shí)均從相應(yīng)的鄰居集合里選擇.

2.3.2 繁殖算子與修復(fù)策略

DE算子[8]和多項(xiàng)式突變[9]已被證明對(duì)于大多數(shù)多目標(biāo)優(yōu)化問(wèn)題是高效的.本文采用DE算子生成子代解，通過(guò)多項(xiàng)式突變策略，維護(hù)種群的多樣性，充分利用的特征空間，來(lái)提升算法性能.DE算子生成子代解的過(guò)程如下:

(14)

式中：xr1是當(dāng)前迭代子問(wèn)題的解；xr2，xr3是其鄰域中隨機(jī)選擇的兩個(gè)解；CR和F是差分進(jìn)化的兩個(gè)參數(shù)；rand是均勻分布在[0,1]間的隨機(jī)數(shù).再對(duì)中間解ui依照多項(xiàng)式變異策略生成新解xi.

(15)

(16)

由于差分進(jìn)化算子本身是求解連續(xù)空間中的多目標(biāo)優(yōu)化問(wèn)題，因此，需要一個(gè)閾值Δ與每個(gè)決策變量進(jìn)行比較，將連續(xù)的決策空間修復(fù)為0，1組成的離散空間.僅當(dāng)決策變量大于閾值Δ時(shí)才選擇相應(yīng)的特征.為了限制所選特征的數(shù)量，本文取Δ=0.6.決策變量的值的可行域?yàn)閇0,1]的概率值.

2.3.3 替換策略

替換策略在MOEA/D框架中起著非常重要的作用，實(shí)際上，它決定了如何保留解、分配何種子問(wèn)題為解.MOEA/D有4種分解方法[10]，將多目標(biāo)規(guī)劃(MOP)問(wèn)題的PF近似值轉(zhuǎn)換為多個(gè)單目標(biāo)優(yōu)化問(wèn)題.

1) Tchebycheff(TCH)方法.

(17)

2) Penalty Boundary Intersection(PBI)方法.

(18)

z*是參考點(diǎn)，與TCH方法相同；θ>0是一個(gè)懲罰參數(shù)，通常θ=5.

3) Normalization Tchebycheff(NTch)方法.

(19)

4) 改進(jìn)的Tchebycheff(MTch)方法.

(20)

當(dāng)分母λi=0時(shí)，本文將其替換為一個(gè)較小值10-6.

本文研究了4種不同的分解方法，來(lái)尋找組成Pareto前沿面的Pareto最優(yōu)解集P*，以確定采用何種分解方式生成的特征子集更利于提高學(xué)習(xí)器的學(xué)習(xí)率.

替換更新:

1)fori←1,…,Ndo

4)替換:B中每個(gè)索引j∈B(i)={i1,…,iT},如果滿足g(xnew|λj,z)≤g(xj|λj,z)則xj=xnew,同時(shí)F(xj)=F(xnew).

5)end for

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

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

為了驗(yàn)證所提出算法的執(zhí)行效率，本文在來(lái)自真實(shí)世界的15個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)源來(lái)自UCI數(shù)據(jù)庫(kù)，詳見(jiàn)表1.

表1 數(shù)據(jù)集

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

在實(shí)驗(yàn)中本文采用knn-5分類(lèi)器作為學(xué)習(xí)器，分別獨(dú)立進(jìn)行了10次10折交叉驗(yàn)證.DE算子中的參數(shù)CR與F分別為1和0.5.多項(xiàng)式變異算子中的參數(shù)設(shè)為η=20，pm=1/n，n是特征子集特征的維數(shù).對(duì)比算法信息詳見(jiàn)表2.

表2 對(duì)比算法的信息

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

實(shí)驗(yàn)通過(guò)對(duì)分類(lèi)器分類(lèi)準(zhǔn)確率(Acc)的提升效果和算法所選擇的特征數(shù)(Atts)來(lái)評(píng)估本文算法及表2中算法的執(zhí)行效率.

表3給出了不同分解方式對(duì)實(shí)驗(yàn)結(jié)果的影響.從實(shí)驗(yàn)結(jié)果來(lái)看，兩種基于改進(jìn)的TCH分解方式生成的特征子集的準(zhǔn)確率和維度縮減的程度要優(yōu)于TCH方法和PBI方法，能更好地提高學(xué)習(xí)器的學(xué)習(xí)效果.在TCH方法表現(xiàn)不好的數(shù)據(jù)集上基于PBI的分解方法能獲得更好的分類(lèi)準(zhǔn)確率.例如在Zoo和Wine數(shù)據(jù)集上基于PBI分解的方法分別比基于TCH的分類(lèi)準(zhǔn)確率高出2.73%和1.63%.

表3 不同分解方式對(duì)分類(lèi)準(zhǔn)確率和特征的影響

表4中列出本文的方法與表2中對(duì)比算法運(yùn)行的結(jié)果.與同SFS，SBS比較，本文提出的方法在大部分?jǐn)?shù)據(jù)集上的表現(xiàn)都是最好的，僅有Zoo的分類(lèi)準(zhǔn)確率要略差一些.這是因?yàn)镾FS與SBS方法實(shí)際上屬于貪心搜索方法.這類(lèi)方法存在明顯的缺點(diǎn):在選擇特征時(shí)它們沒(méi)有考慮特征間的相關(guān)性對(duì)學(xué)習(xí)器的影響，僅以準(zhǔn)確率衡量特征的重要程度，特征一旦被加入或剔除特征子集就不能再修改，容易出現(xiàn)生成的子集陷于局部最優(yōu)陷阱，影響學(xué)習(xí)器的學(xué)習(xí)效果.GWOFS方法雖然采用了啟發(fā)式搜索，但它的搜索是盲目的，同樣沒(méi)有考慮冗余度的影響.因此得到的結(jié)果大部分落后于本文方法.另外同其他基于互信息的方法相比較，本文方法的學(xué)習(xí)效果都優(yōu)于它們.例如在Heart數(shù)據(jù)集上本文方法在選擇更少特征的情況下比MOEA_MIFS與DEMOFS的準(zhǔn)確率分別高出5.53%和3.26%.這表明，本文采用的新冗余度衡量標(biāo)準(zhǔn)，對(duì)衡量特征間的冗余度是高效的，同時(shí)稀疏項(xiàng)的引入能夠保證特征子集的維度盡可能小.同SWFS方法相比，本文的結(jié)果表現(xiàn)得更好，因?yàn)楸疚氖菑男畔⒄摰慕嵌热タ紤]問(wèn)題，而SWFS僅僅考慮數(shù)據(jù)點(diǎn)之間的距離，隨著特征維度的增加，SWFS方法搜索最具判別力特征的能力逐漸下降.

表4 本文方法與其他算法的比較

4 結(jié) 論

1) 本文方法引入的稀疏項(xiàng)l1正則化，能最大程度縮減特征子集的維度.

2) 從實(shí)驗(yàn)結(jié)果看TCH方法由于簡(jiǎn)單易實(shí)現(xiàn)更適用于作為MOEA/D-DEFS的替換策略來(lái)獲得特征子集，提高學(xué)習(xí)器的學(xué)習(xí)率.

3) 采用啟發(fā)式策略可以有效地改善貪心搜索陷入局部最優(yōu)陷阱，獲得更好的特征子集.