基于分解的自適應(yīng)鄰域替換策略的特征選擇算法

馬 璐，蘇 華

(天津工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300387)

0 引言

如今各種技術(shù)飛速發(fā)展，數(shù)據(jù)呈爆發(fā)式增長，數(shù)據(jù)集中通常存在很多無關(guān)特征和冗余特征，這會降低數(shù)據(jù)精度。特征選擇是提高特征數(shù)據(jù)集質(zhì)量最有效的方法之一。對于一個分類問題來說，特征選擇的目的是提取具有高識別能力的小部分特征子集[1]。然而，由于特征之間具有復(fù)雜的相互作用，隨著特征數(shù)量的增加，搜索空間呈指數(shù)增長，特征選擇越來越具有挑戰(zhàn)性。

目前已有很多優(yōu)秀的多目標(biāo)優(yōu)化方法被提出，例如，DEB等[2]提出的非支配排序遺傳算法NSGA-II，ZITZLER等[3]提出的增強(qiáng)Pareto進(jìn)化算法SPEA2，ZHANG等[4]提出的基于分解的多目標(biāo)優(yōu)化算法MOEA/D。各類算法在解決不同類型的特征選擇問題上有著不同的特點和優(yōu)勢。相比之下，MOEA/D算法可以將復(fù)雜的多目標(biāo)優(yōu)化問題分解為多個子問題來求解，具有更好的搜索能力。

傳統(tǒng)的MOEA/D算法通過計算所有權(quán)重向量之間的Euclidean距離給每個子問題劃分對應(yīng)的鄰域，利用鄰域內(nèi)其他的子問題來完成協(xié)同進(jìn)化[5]。但是在進(jìn)化過程中，使用固定規(guī)模的鄰域會使種群進(jìn)化緩慢，從而影響分類性能。因此，為了確保早期搜索階段的種群多樣性，并使搜索將重點放在后期的開發(fā)上，本文提出了一個基于分解的自適應(yīng)鄰域替換策略(Adaptive Replacement，AR)，在種群進(jìn)化的不同時期，動態(tài)地為種群提供不同規(guī)模的鄰域，以平衡種群的多樣性和收斂性，提高進(jìn)化效率，得到更優(yōu)秀的特征子集。

1 相關(guān)工作

1.1 相關(guān)定義

特征選擇是指從一個數(shù)據(jù)集中選擇一組最優(yōu)特征的過程[6]。相比于單目標(biāo)，多目標(biāo)特征選擇可以很好地權(quán)衡多個相互沖突的目標(biāo)，如降低特征數(shù)量和分類錯誤率[7]。通過多目標(biāo)優(yōu)化技術(shù)利用進(jìn)化算法，同時優(yōu)化兩個目標(biāo)，最終可以得到一組多目標(biāo)最優(yōu)解。再通過進(jìn)一步分析，選擇出特征數(shù)量較少且分類錯誤率相對較低的特征子集[8]。

本文將特征數(shù)量f1和分類錯誤率f2作為兩個優(yōu)化目標(biāo)，研究多目標(biāo)特征選擇問題，定義如下：

minF(x)=[f1(x),f2(x)],

(1)

(2)

(3)

在式(2)中，f1表示特征集合M中被選中的特征個數(shù)。

在式(3)中，P和N表示真實樣本是否屬于某個類別，T和F表示預(yù)測結(jié)果，該樣本的觀察和預(yù)測結(jié)果一致為T，否則為F，該計算值f2就是分類錯誤率。

1.2 算法思想

對于一個解x，如果子問題j滿足以下條件，則稱子問題j是最適合x的子問題：

(4)

為了簡單起見，替換策略并不限制被新解所取代的解的數(shù)量，所有的Tr相鄰解都有可能被相同的新解所取代，因此，Tr是控制收斂性和多樣性平衡的一個關(guān)鍵參數(shù)。在不同的進(jìn)化階段需要不同的Tr值。在種群進(jìn)化的早期搜索階段，應(yīng)設(shè)置一個較小的Tr值，以保持良好的種群多樣性；但在種群進(jìn)化后期，應(yīng)設(shè)置一個較大的Tr值，以提高種群收斂速度。因此，應(yīng)在種群進(jìn)化期間增加Tr值，本文采用如下方式來增加Tr值。

(5)

其中，「·?是上限函數(shù)，Tmax是Tr的最大值，k是當(dāng)前代數(shù)，K是最大代數(shù)，γ是一個控制參數(shù)，γ∈[0,1)，確定Tr隨著搜索的進(jìn)行而增加的方式。

2 基于分解的自適應(yīng)鄰域替換策略

基于分解的自適應(yīng)鄰域替換策略(MOEA/D-AR)的特征選擇算法執(zhí)行過程如下：

輸入：原始數(shù)據(jù)集OTD；種群規(guī)模N；均勻分布的權(quán)重向量W={λ1,…,λN}；鄰域大小T，變異概率Pm，交叉概率Pc；最大迭代代數(shù)Maxgen；種群規(guī)模pop；

輸出：非支配特征子集的特征數(shù)和分類錯誤率；

Step1 初始化；

Step1.1 計算任意兩個權(quán)重向量之間的Euclidean距離，為每個權(quán)重向量選出最近的T個權(quán)重向量作為其初始鄰域。設(shè)B(i)={i1,i2,…,iT}，i=1,2,…,N,其中，λi1,λi2,…,λiT是距離λi最近的T個權(quán)重向量；

Step1.2 初始化種群P，并計算初始個體xi的函數(shù)值Fi(f1,f2)；

Step1.3 初始化理想點Z*={min(f1),min(f2)}；

Step2 更新：fori=1 toN，do

Step2.1 在每代更新之前計算每代的選擇鄰域Bm(i)，計算替換鄰域Tr值，計算Br(i)；

Step2.2 繁殖：從Bm(i)中隨機(jī)選擇兩個鄰居xk,xl，通過遺傳算子由xk,xl進(jìn)行交叉變異生成新解；

Step2.3 修正：應(yīng)用問題特定的啟發(fā)式的改進(jìn)策略作用于y生成y′；

Step2.4 更新Z*：若Zj

Step2.5 更新解：采用更新函數(shù)更新Z*,Br(i),y,P,W；

Step3 停止判斷：當(dāng)達(dá)到最大迭代次數(shù)時，則輸出Pareto非支配解，否則返回Step2繼續(xù)執(zhí)行；

Step4 選擇PF(Pareto Front)中合適的非支配解作為特征子集；

Step5 計算特征子集中個體的特征數(shù)和分類錯誤率并作為結(jié)果返回。

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集與參數(shù)設(shè)置

本文在UCI machine learning repository[12]中選取了表1所示的5個數(shù)據(jù)集。并將所提出的MOEA/D-AR算法分別與如下3種著名的多目標(biāo)算法進(jìn)行了比較：標(biāo)準(zhǔn)的MOEA/D[4]、NSGA-II[2]、SPEA2[3]。在測試中，所有算法都采用十折交叉驗證的KNN[13]計算訓(xùn)練集的分類誤差率。然后在測試集上對進(jìn)化的特征子集進(jìn)行評估，以獲得其測試精度。KNN中的近鄰數(shù)設(shè)為5，以避免出現(xiàn)冗余的實例，同時保持其效率。最大迭代次數(shù)為20次，種群大小為50，閾值θ設(shè)置為0.6，用來決定特征是否被選中。所有的算法都在測試中獨立運(yùn)行30次，然后在測試集上對進(jìn)化的特征子集進(jìn)行評估，以獲得其測試精度。

表1 數(shù)據(jù)集及參數(shù)設(shè)置

3.2 實驗結(jié)果

本文算法和其他3種算法在各數(shù)據(jù)集上的最優(yōu)非支配解集對應(yīng)的帕累托前沿如圖1所示。MOEA/D-AR在5個數(shù)據(jù)集上得到的分類錯誤率，不僅明顯優(yōu)于使用全部特征時的分類錯誤率，而且相較于3個對比算法， MOEA/D-AR在大多數(shù)情況下都更優(yōu)于其他算法。

(a)Wine

(b)Australian

(c)Zoo

(d)Ionosphere

(e)Hill-valley圖1 各算法在不同數(shù)據(jù)集上最優(yōu)非支配解集對應(yīng)的Pareto前沿

在Wine數(shù)據(jù)集中，MOEA/D-AR算法只需要選取15%的特征數(shù)，也就是13個特征里面選擇了2個就能達(dá)到比使用全部特征更小的分類錯誤率。在Australian中，MOEA/D-AR算法只選取了21%的特征，即14個特征中選擇了3個，得到的分類錯誤率就小于總分類錯誤率。在Zoo中，MOEA/D-AR選擇了24%的特征數(shù)，即17個中選擇了4個，就能得到比使用全部特征更小的分類錯誤率。在Hill-valley中，MOEA/D-AR只選擇了總特征數(shù)的10%，就使分類錯誤率低于使用全部特征時的分類錯誤率。在Ionosphere數(shù)據(jù)集中，MOEA/D的性能略低于NSGA-II，排名第二，選擇了30%的特征，即34個中選擇了10個，就使分類錯誤率低于總分類錯誤率，選取的特征數(shù)比排名第一的NAGA-II僅高4%。

表2給出了5種算法在測試結(jié)果中分類錯誤率低于使用所有特征時的最小特征數(shù)和對應(yīng)的分類錯誤率。由表2可以看出，除了Ionosphere數(shù)據(jù)集，MOEA/D-AR在其他4個數(shù)據(jù)集中，都能得到更小的特征數(shù)目；且當(dāng)所選取的特征數(shù)目相等時，MOEA/D-AR所選取的特征子集的分類錯誤率也更低。研究結(jié)果表明，MOEA/D-AR可以選取出性能更優(yōu)的特征子集。

表2 分類錯誤率低于使用全部特征時各算法所對應(yīng)的最小特征數(shù)及分類錯誤率

4 結(jié)語

為了避免使用經(jīng)典的MOEA/D算法進(jìn)行特征選擇時，由于鄰域規(guī)模固定而導(dǎo)致種群喪失多樣性且進(jìn)化效率低，從而產(chǎn)生過多冗余數(shù)據(jù)的問題，本文提出了一種基于分解的自適應(yīng)鄰域替換策略(MOEA/D-AR)的特征選擇算法，該算法根據(jù)進(jìn)化過程中鄰域規(guī)模的大小，自適應(yīng)地替換鄰域解，并保證每個解都對應(yīng)其最合適的子問題。實驗結(jié)果表明，本文提出的算法可以得到特征數(shù)目少且分類錯誤率更低的優(yōu)秀特征子集。

同時該算法也存在一定的缺陷，例如，使用的固定參數(shù)較多，這些參數(shù)大多不可以自主學(xué)習(xí)，在一定程度上影響了算法性能。在今后的工作中將對以上問題加以改進(jìn)，使這些固定參數(shù)也可以隨著迭代過程進(jìn)行動態(tài)調(diào)整，進(jìn)一步優(yōu)化算法。