自調優自適應遺傳算法的WKNN特征選擇方法

陳倩茹，李雅麗，許科全，劉銥龍，王淑琴

天津師范大學 計算機與信息工程學院，天津 300387

隨著大數據時代的到來，高維數據集的處理已不可避免。訓練時間隨著特征空間維數的增加而增加，不斷增加的維度會導致“維度詛咒”的問題[1]。特征選擇是解決“維度詛咒”問題的重要降維方法之一[2]。通常情況下，分類器處理的數據集中存在許多冗余或不相關的特征，這不僅增加了訓練時間，而且降低了學習后分類器的分類精度。特征選擇是克服這類問題的一項重要的數據預處理技術，它涉及到從原始的特征空間中選擇相關特征的最小子集，從而減少訓練時間，提高學習性能[3]。

在過去的幾十年里，特征選擇算法得到了廣泛的應用。根據特征選擇搜索如何與分類模型的構建相結合，特征選擇方法一般分為三類：Filter、Wrapper和Embedded[4]。Filter方法通過只考慮數據的內在屬性來評估特征的相關性，并基于統計或信息度量選擇高級特征。Wrapper方法利用所選特征訓練分類器，根據分類器在測試集上的表現來評價所選特征。Embedded方法在考慮分類器構造的同時，篩選出關鍵特征。

K近鄰（K-Nearest Neighbors，KNN）算法是一種基于對象相似度的原型方法，常用于解決分類和回歸任務[5]。近年來，K近鄰被擴展成不同的方式，應用于特征選擇。Park等[6]提出了一種基于最近鄰集成分類器的Wrapper特征選擇方法。該方法利用序列隨機K近鄰（SRKNN）作為隨機森林在高維數據建模中的替代方法，通過迭代過程尋找重要特征。Wang等[7]提出了一種利用嵌入KNN分類器來加速基于Wrapper的特征子集選擇方法。該方法通過構造一個分類器距離矩陣來存儲映射到所選特征上的實例之間的距離，從而加速基于Wrapper的特征選擇。宋寶燕等[8]提出了一種基于Voronoi劃分的位置數據KNN查詢處理方法，通過R樹確定查詢點所在的Voronoi單元，進一步通過VHash獲得KNN查詢結果；在VHash、VR二級索引更新期間，針對變化的位置數據，實現了近似查詢及精確查詢。大多方法在計算兩個樣本距離時都認為每個特征的重要程度是相同的，但事實上，大多特征對類別的貢獻度應不同。因此，本文使用加權K近鄰（WeightedK-Nearest Neighbor，WKNN）計算距離。

進化計算（Evolutionary computation，EC）方法中的自適應機制引起了研究者的廣泛關注[9]。一般而言，具有自適應機制的EC算法可以在迭代過程中自動調整算法的參數。特別是遺傳算法，種群規模在遺傳算法整個尋優過程中扮演著重要的角色，它規定了搜索樣本的數目，交叉算子是生成新個體的主要方法，可以從全局搜索優良的個體，變異算子能夠從局部搜索出發，使個體更加接近最優解，從而提高算法的局部搜索能力。通過自適應地調整遺傳算法的參數，可以避免算法過早收斂和后處理速度慢。Koromyslova等[10]提出了一種自配置遺傳算法（SCGA）。所有類型的遺傳算子用相同的概率用于新的子代，通過評估遺傳算子類型的適應度，對概率進行動態調整。自適應遺傳算法（AGAs）[11]通過同時修改交叉值和變異值來確保種群多樣性，從而為神經網絡學習提供理想的初始權值。這一現象對于消除局部收斂和防止算法停滯是很重要的。

針對大多已有基于K近鄰和遺傳算法的特征選擇方法中沒有考慮各個特征的重要度不同，以及出現的過早收斂，特別是局部最優解問題，本文提出了一種基于自調優自適應遺傳算法的WKNN特征選擇方法，簡記為WKNNSTA_GAFS（WeightedK-Nearest Neighbor Feature Selection Based on Self-Tuning Adaptive Genetic Algorithm）。該方法將WKNN和自調優自適應遺傳算法結合起來，首先使用WKNN預測樣本的類別，為每個特征分配一個權重來衡量特征的分類能力。在計算樣本類別時既考慮了每個特征的不同分類能力，又考慮了最近鄰的距離。然后利用自調優自適應遺傳算法，對變異率、種群規模和收斂閾值進行參數調整，在迭代過程中搜索最優特征權重向量。不僅能克服局部最優解問題，還能消除過早收斂和防止由于參數調優反饋不穩定而產生的過高的計算成本。

1 自調優自適應遺傳算法的WKNN特征選擇方法

1.1 加權K近鄰

傳統的KNN方法中，預測樣本類別時，使用相同權重的K個最近鄰，即權值為1/K。但事實上不同近鄰的重要性可能是不同的，兩個樣本越接近，類別可能越相同，對目標類別預測的影響越大。因此，應該根據K個近鄰與預測樣本之間的距離，為每個近鄰分配相應的權值。距離越近，分配的權值越大。

在本文中，如果沒有特殊說明，均假設處理回歸任務。給定一個回歸問題D=(F,X,Y)，F={f1,f2,…,f m}為特征集合，X={x1,x2,…,xn}為包含n個樣本的數據集，Y={y1,y2,…,y n}為目標變量集合。給定一個特征權重向量ωf=(ωf1,ωf2,…,ωf m)，則特征加權后測試樣本x i=(x i1,xi2,…,xi m)(1≤i≤n)的觀測值可以用Hadamard積表示為：

使用特征加權后樣本x i與x j的歐幾里德距離公式為：

則基于距離和特征加權K近鄰的樣本xi的預測值Pi(ωf)為：

其中，j∈N Ki表示樣本xi的K個近鄰的指標集，即x j為x i的第j個近鄰。

本文采用的距離加權函數定義為：

1.2 自調優自適應遺傳算法

遺傳算法是一類借鑒生物界自然選擇和遺傳機制的隨機搜索算法[12-13]。傳統的遺傳算法在遺傳進化的過程中采用固定參數，容易導致進化過程中出現過早收斂和停滯現象。因此，一種自調優自適應遺傳算法（簡稱為STA_GA）被提出對遺傳算法參數和收斂閾值進行自動調整，以提高收斂精度。

由于種群的多樣性是保證遺傳算法找到全局最優解的前提條件，因此，STA_GA算法的目的是通過對遺傳算法參數的更新增加種群的多樣性。在進化過程中，遺傳算法的選擇操作削弱了種群的多樣性，交叉算子只有滿足一定的條件才能保持種群的多樣性，而變異操作則是保持種群多樣性的有效算子[14]。種群規模越大也可以增加種群多樣性，因此，本文提出方法將在遺傳迭代過程中，對變異率、種群規模和收斂閾值三個參數進行自適應調整。

為了便于敘述，首先設在靜態遺傳算法中，Pm表示初始變異率，PS表示種群規模，Time表示迭代次數，cgen為當前代的迭代次數，θ表示收斂閾值。STA_GA采用傳統的初始化策略，根據特征的數量和單個特征的組合，隨機初始化每個粒子。

STA_GA將一個預定的候選評估數定義為收斂閾值，然后在自適應調整的過程中，判斷當前代的靜態迭代次數是否大于收斂閾值或者全局最優解是否更新，如果當前代的靜態迭代次數大于收斂閾值，或者全局最優解始終沒有得到更新，則對變異率、種群規模和收斂閾值三個參數進行重新調整。

變異率的更新公式為：

種群規模也會隨之更新，更新公式為：

其中，gaiter表示靜態迭代次數，即迭代過程中一代或幾代連續沒有獲得更好最優解的個體總數。那么種群規模會增加這個個體總數的G倍。

如果當前靜態迭代次數大于收斂閾值時，表示已經有超過收斂閾值個數的連續個體未更新最優解，本文中收斂閾值的初值為種群規模PS，即連續至少超出種群規模個體都未更新最優解，則種群規模會更新變大，因此，收斂閾值也應隨之增加，本文中其增量為上一代種群規模，其更新公式為：

相比參數更新前，更新后的種群會包含更多個體，多樣性也會更大，種群產生最優個體的概率也更高，有利于算法搜索到全局最優解。更新后的變異算子可以產生較多的新個體，種群多樣性同樣得到了提高，并且擴展了搜索空間，變異算子能夠從局部搜索出發，使個體更加接近最優解，提高了算法的局部搜索能力，加快了遺傳算法的收斂速度[15]。

仿真過程中發生收斂時，STA_GA進行參數更新，以便獲得更高數量的候選種群和變異率，而不是在每次迭代中使用相同的遺傳算子參數。當前代的靜態迭代次數小于等于收斂閾值或全局最優解更新時，STA_GA采用靜態的遺傳算法參數設置。與靜態的遺傳參數設置相比，STA-GA參數調優機制的優點在于允許啟發式搜索方法動態地在目標搜索空間中搜索全局最優解。

為了確保反饋的穩定，以及防止由于參數變化過大而導致的不一致的性能，限定了參數值的浮動范圍，其中Pm小于等于0.5或者PS不能超過初始種群的三倍。對于每一代STA_GA，通過判斷當前代的靜態迭代次數是否大于收斂閾值或者全局最優解是否更新，對上述參數值進行重新評估。只有當滿足停止條件時，自適應參數調優才會終止。

1.3 WKNNSTA_GAFS

WKNNSTA_GAFS算法主要包括初始種群、計算預測樣本的類別、計算個體適應度、參數調優、執行遺傳算子和最后得到最優權重向量六個部分。迭代結束后，對結果數組進行排序，得到全局最優特征權重向量ωbestf。通過對最優特征權重降序排序，依次選取對應的前N個特征組成一個子集。然后，利用分類器對其進行評價。

（1）初始化種群。使用[0，1]間的實數隨機初始化含有m位基因的個體，種群中每個個體代表一個特征權重向量。

（2）適應度函數。種群初始化后，使用適應度函數計算每個個體的適應度值。第t個個體適應度函數定義為：

式中，Max是人為給出的使F t(ωf)≥0的正整數。C(ωf)為成本函數，表示為所有訓練樣本損失函數的平均值。成本函數越小說明整體的預測誤差越小。成本函數定義為：

式中，L為損失函數，用預測值P i(ωf)與目標函數的真實值yi之間的差表示。本文損失函數定義為：

（3）STA_GA參數調優。通過判斷，當本次迭代的靜態迭代次數大于收斂閾值或全局最優解未更新時，開始進行參數調優。

（4）選擇算子。選擇是在個體適應度評價的基礎上，從上一代中選擇好的個體到下一代的操作。適應度值越高的個體被選擇的概率越高。本文采用輪盤賭選擇方法[16]。

（5）交叉算子。交叉操作是生成新個體的主要方法，決定了遺傳算法的全局搜索能力。為了下一代能產生優秀的個體，本文采用算術交叉算子。首先根據概率隨機選擇一對父代個體P1、P2作為雙親，然后進行如下隨機線性組合，產生兩個新的子代個體P'1、P'2。

式中，α、β為（0,1)間的隨機數，個體基因的取值范圍為[Gmin,Gmax]。如果(1-α)?P1+β?P2的值小于Gmin（或大于Gmax），則P1'的值為Gmin（或Gmax）；P2'的值同理。

（6）變異算子。本文采用高斯變異算子，原因是它能重點搜索原個體附近的某個局部區域。它用符合均值為μ、方差為σ2的正態分布的一個隨機數Q來替換原來的基因值。Q可由等式（12）求得：

式中，r i是在[0，1]范圍內均勻分布的隨機數，μ和σ的計算如下：

（7）停止標準。當變異率Pm大于最高變異率max_Pm或者種群規模PS超過初始種群的三倍時，算法停止。算法的流程如圖1所示。

圖1 WKNNSTA_GAFS算法流程Fig.1 Flow of WKNNSTA_GAFS

1.4 WKNNSTA_GAFS的收斂性分析

1.4.1 遺傳算法收斂性定義

遺傳算法的收斂性通常指算法所生成的迭代種群逐漸趨于某一穩定狀態，或其適應值的最大或平均值迭代收斂于解的最優值。

設X t={x1(t),x2(t),…,x M(t)}為遺傳算法的t代種群，x i(t)為t代種群中的第i個個體，i=1,2,…,M,M為種群規模。設Z t=max{f(xi(t)|i=1,2,…,M)}為種群中所包含的個體的適應度函數值的最大值，F?=max{f(x)|x∈S}表示全局最優解，S為個體空間，x為S中的任意一個個體。則遺傳算法的全局收斂性定義如下：

其中，P{Zt=F?}表示第t代種群中的最優個體為全局最優的概率。

1.4.2 馬爾科夫鏈定義

設隨機序列X={X n,n=0,1,…}的離散空間為E,如果對于任意n≥0,以及i0,i1,…,i n,j∈E,滿足條件概率：則稱這類隨機過程為離散馬爾科夫鏈。馬爾科夫鏈有無后效性的特點，即當前狀態只與前一狀態有關，而與其他狀態無關。

1.4.3WKNNSTA_GAFS收斂性證明

將WKNNSTA_GAFS看作是一個離散狀態下的隨機序列，把每一代種群P(1),P(2),…看作是一種狀態，種群的代代演化可以看作是狀態之間的轉移，當前種群的狀態僅僅依賴于相鄰的上一代種群，而與以往的種群狀態無關。因此，可以利用馬爾科夫鏈證明算法的收斂性。

假設總體狀態空間為H，算法中每一代種群h(t)對應馬爾科夫鏈中的一個狀態，種群的逐代進化則對應馬爾科夫模型中不同狀態間的轉移過程。標記每個h(i)∈H是否包含最優個體。由WKNNSTA_GAFS收斂性可知，一旦轉移后的狀態包含了當前最優個體，在以后的轉移過程中將不斷逼近包含最優個體的狀態。最終即WKNNSTA_GAFS以概率1收斂到全局最優解。

1.4.4與WKNNSTA_GAFS算法收斂性能有關的參數

與算法收斂性有關的參數主要包括種群規模、交叉率和變異率。通常，種群規模太小，算法性能很差，甚至得不到問題的可行解；種群規模太大，盡管可以防止發生早熟收斂，但是計算量會增大，收斂速度緩慢。交叉率過大，容易使種群中高適應度值的個體被破壞掉，過小則會造成算法停滯不收斂；變異率過大容易使遺傳算法成為隨機搜索算法，過小則不會產生新個體。本文提出的WKNNSTA_GAFS采用自調優自適應遺傳算法，自適應地調整算法變異率、種群規模和收斂閾值，在保證種群多樣性得到提高的同時，加快了種群的進化速度，其收斂速度明顯快于其他比較特征選擇算法。

1.5 WKNNSTA_GAFS時間復雜度分析

傳統遺傳算法的時間復雜度為O(Max_Time×PS)，其中Max_Time為最大迭代次數；PS為種群規模。

WKNNSTA_GAFS算法的時間復雜度也是算法迭代次數Time和種群規模PS的函數。與傳統遺傳算法不同的是迭代次數和種群規模是不固定的，在迭代過程中是變化的。

WKNNSTA_GAFS算法的時間復雜度可表示為O(t0×PS0+t1×PS1+…+t n×PSn)，其中t i表示第i次參數更新與第i+1次參數更新之間迭代的次數，PS i表示相應的種群規模。

根據參數更新公式（5）～（7）可知，當迭代過程中連續至少超出種群規模個體都未更新最優解時，則種群規模會更新變大。因此，本文算法的時間復雜度也會高于傳統遺傳算法。

2 實驗與性能分析

為了驗證WKNNSTA_GAFS算法是否正確和有效，在5個數據集上，使用3種分類器，與其他7種特征選擇算法進行比較實驗。在實驗中對所有數據集進行了歸一化處理。

2.1 數據集

實驗中使用數據集的簡要描述如表1所示。其中，Z-Alizideh、Q_green、brain、TNCI來自UCI機器學習知識庫[17]，Leukemia1下載自基因表達數據庫。

表1 數據集信息Table 1 Information of datasets

2.2 實驗環境及參數設置

在Pycharm集成開發環境下進行實驗。對每個數據集使用五重交叉檢驗，并與7種特征選擇方法進行比較，包括生成子集的GAFS[12]、FCBF[18]和IG-GA[19]方法，以及排序的MIFS[20]、mRMR[21]、WKNNFS[22]和AGASVM[23]方法。使用KNN、支持向量機（Support Vector Machine）和隨機森林（Random Forest）3種分類器進行分類預測。

在實驗中，種群規模、迭代次數、收斂閾值等參數的初始值設置如表2所示。其中收斂閾值的初始值為初始種群規模PS，根據公式（7）收斂閾值的迭代公式可以看出，如果當前靜態迭代次數大于收斂閾值時，表示已經有超過收斂閾值個數的連續個體未更新最優解，本文中收斂閾值的初值為種群規模PS，即連續至少超出種群規模個體都未更新最優解，則種群規模會更新變大，因此，收斂閾值也應隨之增加，而收斂閾值越大也就意味著靜態迭代次數更大時才會更新參數，因此需要的執行時間也會越長，但是算法的性能不一定會隨之增大。為了確定初始的收斂閾值，本文在3個數據集上做了不同初始收斂閾值對算法性能影響的實驗，實驗結果如表3所示。從表3中可以看出初始收斂閾值不同，算法性能也不同，當初始收斂閾值為初始種群規模PS的值時，算法性能也最好，因此，本文選定種群規模PS的值為收斂閾值的初始值。

表2 算法的參數初始化選擇Table 2 Algorithm parameter initialization selection

表3 不同初始收斂閾值對算法性能的影響Table 3 Influence of different initial convergence thresholds on algorithm performance

2.3 實驗結果及性能分析

為了合理比較WKNNSTA_GAFS方法與GAFS、FCBF、IG-GA、MIFS、mRMR、WKNNFS和AGASVM特征選擇方法的性能，進行了兩組實驗。首先，選擇WKNNSTA_GAFS與MIFS、mRMR、WKNNFS和AGASVM四種排序特征選擇方法獲得的特征排序結果中相同個數的特征，分別使用上述3種分類器在5個數據集上進行分類預測，相應實驗結果如圖2所示，橫坐標為排在前面的特征的個數(N)，縱坐標為選擇前面N個特征后使用上述3分類器進行分類預測獲得的準確率的平均值（mean F1 score）。

圖2 WKNNSTA_GAFS、MIFS、mRMR、WKNNFS和AGASVM在5個數據集上的F1 score平均值比較Fig.2 Comparison of mean F1 score of WKNNSTA_GAFS，MIFS，mRMR，WKNNFS and AGASVM on 5 datasets

為了評價所提出算法的性能，計算了不同特征選擇方法在不同數據集和不同分類器上獲得的F1 score平均值以及標準差。實驗結果如表4（Mean±std）所示。Mean表示每種算法獲得最優分類性能的F1 score平均值，std表示標準差。其中Avg表示算法在給定數據集上使用KNN、SVM和RF三種分類器的F1 score平均值，表中黑體部分表示同一數據集中F1 score平均值最高。

表4 各算法使用不同分類器在5個數據集上的均值和標準差Table 4 Mean and standard deviation of each algorithm by using different classifiers on 5 datasets

從表4可以看出，WKNNSTA_GAFS最優分類性能占比和F1 score平均值方面基本上都高于其他對比算法。在Z-Alizideh、Q_green、Leukemia1、brain和TNCI五個數據集上，WKNNSTA_GAFS與生成子集的方法比較，得到了更高的F1 score平均值。WKNNSTA_GAFS與FCBF相比，分別提高了15%、11%、8%、15%和9%；與GAFS相比，分別提高了8%、8%、16%、8%和9%；與IG-GA相比，分別提高了4%、8%、12%、3%和9%。其次，與排序方法的F1 score平均值進行比較，WKNNSTA_GAFS相比MIFS，分別提高了17%、16%、28%、1%和13%；與mRMR相比，分別提高了13%、16%、15%、1%和13%；與AGASVM相比，分別提高了2%、3%、9%、2%和7%；與WKNNFS相比，分別提高了1%、2%、10%、1%和7%。雖然在Z-Alizideh、Q_green和brain數據集上，WKNNSTA_GAFS與WKNNFS的F1 score平均值差異并不顯著，但是WKNNSTA_GAFS的std更低，分類性能更加穩定。綜上所述，WKNNSTA_GAFS方法優于其他FS方法。

3 結束語

本文提出了一種基于自調優自適應遺傳算法的WKNN特征選擇方法，該方法利用WKNN算法預測樣本的類別，為每個特征分配一個權重來衡量特征的分類能力。在計算樣本類別時既考慮了每個特征的不同分類能力，又考慮了最近鄰樣本的距離。并使用自調優自適應遺傳算法搜索最優的特征權重向量。通過STA-GA的自適應參數調優機制對變異率、種群規模和收斂閾值進行調整，以獲得理想的搜索空間，避免局部收斂；其次自定義停止標準，使參數調優反饋穩定，同時避免優化過早終止。在5個真實的數據集上，將該方法與現有的7種特征選擇方法分別進行了對比實驗。實驗結果表明，該特征選擇方法賦予重要的特征更高的權重，從而有效地提高了分類精度。在未來的工作，將努力進一步提高WKNNSTA_GAFS的分類精度，使用更多的分類器評估其應用潛力。