李占山，呂艾娜

(吉林大學 計算機科學與技術學院，吉林 長春 130012)

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

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

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

1 基于信息論的過濾式方法

熵與互信息(mutual information,MI)是信息論中兩個重要的概念.熵(H)是隨機變量不確定度的度量指標.互信息(I)則用來衡量兩個隨機變量之間的相關性，互信息和熵具有以下關系，如式(1)和圖1所示.

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

(1)

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

(2)

其中:fi表示待選特征;fs是已選特征;C是標簽.J(fi)越大，特征fi對提高學習器準確率的貢獻程度越高.參數(shù)β用來調節(jié)相關度與冗余度的相對重要程度.

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

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

(3)

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

(4)

該方法認為特征間的冗余信息受標簽信息的影響，并提出新的熵與互信息的關系，見圖2.

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

(5)

(6)

經(jīng)過式(5)，式(6)的推導，MIFS-U最終的特征選擇標準:

(7)

由于將標簽信息考慮進來，因此MIFS-U能比MIFS方法更好地衡量特征之間的關系.

2 MOEA/D-DEFS方法

2.1 新冗余度衡量標準

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

(8)

改進后的特征間冗余度標準:

(9)

2.2 目標函數(shù)

特征選擇的目的是找到一個特征子集S，保證組成該特征子集的特征與標簽高度相關.

(10)

同時特征之間的冗余度FRED最小:

(11)

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

(12)

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

至此特征選擇被轉化為求解一個多目標優(yōu)化問題:

(13)

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

2.3 MOEA/D-DEFS

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

算法1 MOEA/D-DEFS框架

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

輸出：分類準確率.

1)MOEA/D-DEFS;

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

3)返回生成的特征子集及其對應的分類準確率.

2.3.1 MOEA/D方法及其初始化

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

MOEA/D方法的初始化:

1)通過計算任意兩個權重向量之間的歐氏距離，初始化鄰居集合B；

2)在目標空間中隨機初始化種群{x1,…,xN};

3)通過公式(13)計算子問題的目標函數(shù)F(xi),?i=1，…，N;

根據(jù)近鄰思想, 針對繁殖算子和替換策略，通過維護鄰居集合, 在選擇繁殖個體和替換個體時均從相應的鄰居集合里選擇.

2.3.2 繁殖算子與修復策略

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

(14)

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

(15)

(16)

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

2.3.3 替換策略

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

1) Tchebycheff(TCH)方法.

(17)

2) Penalty Boundary Intersection(PBI)方法.

(18)

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

3) Normalization Tchebycheff(NTch)方法.

(19)

4) 改進的Tchebycheff(MTch)方法.

(20)

當分母λi=0時，本文將其替換為一個較小值10-6.

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

替換更新:

1)fori←1,…,Ndo

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

5)end for

3 實驗結果與分析

3.1 實驗數(shù)據(jù)集

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

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

3.2 實驗參數(shù)設置

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

表2 對比算法的信息

3.3 實驗結果分析

實驗通過對分類器分類準確率(Acc)的提升效果和算法所選擇的特征數(shù)(Atts)來評估本文算法及表2中算法的執(zhí)行效率.

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

表3 不同分解方式對分類準確率和特征的影響

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

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

4 結 論

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

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

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