基于距離貪心策略的灰狼特征選擇算法研究*

童坤 鈕焱 李軍

（湖北工業大學計算機學院 武漢 430068）

1 引言

現今科技高速發達的今天，醫療檢測系統不斷更新換代，檢測體系日趨成熟。心臟病作為人類健康的殺手，在疾病發作之前對其進行檢測具有重大的意義。而病人生理數據特征量大且冗雜，冗雜的特征使得心臟病檢測的工作量變得巨大，且效果還會變得不佳。灰狼優化算法（Grey wolf optimization，GWO）是現在被投入使用的群體智能算法，該算法通過模擬狼群捕食獵物的過程，來確定所要捕食的獵物的位置，也就是優化問題的最優解，并且被大量用于特征選擇部分中［2～9］，但是本身算法收斂速度較慢，搜索效率較低。本文提出了一個改進的灰狼算法用于特征選擇部分，該算法用貪心策略代替了一般灰狼算法位置更新部分，提高了最優價的搜索效率，從而能抽取出較好的特征集，有利于樣本的檢測。

2 基于距離貪心策略的GWO

本文基于貪心策略，提出了一個GWO的新的二元編碼化方法。該策略以個體離迭代最優點的距離為參照，其中離最優點最近的個體點最不容易改變編碼，而距離最遠的點則有最大的概率改變自己的編碼。

2.1 距離貪心策略

該策略是基于灰狼個體和獵物之間的距離大小來實現的。一般來講，貪心策略是在求解問題是，總是做出在當前看來是最好的選擇，在灰狼算法的更新問題上，貪心策略可以設置為：在某一維距離最優點越近，其改變編碼的概率越小，而距離最優點越遠，則改變的概率越大。由圖1可知，中心點為最優點prey，則有：

1）對于A狼和C狼來說，②的長度遠小于③，則根據貪心策略，A狼在x軸上改變編碼的概率遠小于C狼。

2）對于A狼和C狼來說，④的長度遠小于①，則根據貪心策略，C狼在y軸上改變編碼的概率遠小于A狼。

3）對于B狼來說，⑤和⑥的長度都比較大，故B狼無論x軸還是y軸，其改變的概率都較大。

故由以上貪心策略分析可知，編碼在某一維改變的概率和該點某一維距離最優點的長度成正比，算法的中心則變成了如何計算出改變的概率。

圖1 貪心策略圖示

2.2 基于距離貪心策略的GWO

該算法步驟分為三部分：計算連續編碼距離向量，距離映射和更新離散編碼距離向量。

1）計算連續編碼距離向量

為了得出該個體二元編碼向量的概率，必須先求出該個體距離最優點的連續位置距離，而在GWO中，最優點的位置由α，β和δ的位置所假設表示，當個體的位置離α，β和δ越近，則表明該個體所攜帶的解越優。故可以用離α，β和δ的距離來得出該個體距離最優點的連續位置距離。連續編碼距離向量由式（1）計算出：和表示該個體距離α，β和δ的距離，其定義如下：和可有式（5）～（7）算出：和表示在第t次迭代中前三個最優的候選解。

其中t為當次迭代的次數，maxiter為算法迭代的總次數。

2）距離映射

特征選擇問題中的連續型變量的搜索區間是任意設置的，通常情況下，特征選擇問題的搜索區間可以被人為設置為［0，1］。當問題搜索區間設置不為［0，1］時候，則需要通過一個映射函數將該問題轉換為在區間［0，1］上的問題。假設問題搜索區間為［a，b］，一個最簡單的映射函數G（）構造如下：

其中Dnave表示由式（1）所算出的第n維度的值，Dnavenew表示向量第n維度的值。

3）更新離散編碼距離向量

更新編碼向量的原則為以個體離迭代最優點的距離為參照，離最優點最近的個體點最不容易改變編碼，而距離最遠的點則有最大的概率改變自己的編碼，當我們獲得了取值范圍在［0，1］的連續編碼向量或）時，將和該個體二元編碼向量作為更新策略f的輸入，得到下一次迭代t+1中該個體的二元編碼向量。設中的第d維取值為和連續編碼向量的第d維取值為Dd，則對于每一維d，其更新策略如式（12）：

其中rand為［0，1］區間里任意的隨機數，其中hold和change表示對的操作，操作后的取值作為xd的值。change和hold的兩個操作表示為如式（13）、（14）：

更新策略根據Dd的取值來采取相應的操作，按照所選的操作來更新xd的取值，算法1表示該算法的執行步驟：

算法1 基于貪心策略灰狼優化算法

輸入：種群中灰狼個體的數目n

算法迭代的總次數max_itr

初始化a，A和C三個控制參數。

隨機初始化n頭灰狼的位置向量

通過計算每個灰狼的適應值來找出α，β和δ的位置向量。

t=1

While（t

For狼群中的每一頭狼i

For狼的位置向量的每一維

根據式（12）更新狼i第d維的取值

End

End

Ⅰ更新a，A和C三個控制參數

Ⅱ計算更新后每一頭灰狼的適應值

Ⅲ更新α，β和δ

End

3 實驗及其結果分析

本文使用uci數據庫中的一組心臟病數據做為實驗數據集，將優化過后算法和GWO，遺傳算法（GA），粒子群算法（PSO）作為特征選擇部分的算法，使用KNN作為樣本分類器，將樣本分類錯誤率和最終特征選擇數目作為比較指標，比較使用這四種不同特征選擇算法在不同的運行次數下的平均性能指標。。

3.1 數據集及分類器準備

本文實驗所使用的數據集為UCI數據庫所提供的一組心臟病數據集，一共303條數據，每條數據記錄了心臟病人的所有生理指標。該數據特征表如表1。

KNN算法是一種簡單的監督學習分類算法，它通過度量該樣本在空間中的K個最相似的鄰居（特征空間中最鄰近的樣本）大多數是屬于哪一類，則該樣本就屬于這一類，所有的鄰居都為已正確分類的對象。由于KNN分類器無需建立任何模型，只需要通過有限的鄰居來確定所屬類別，所以KNN被普遍用于各大分類問題中，KNN算法具有特別的優勢［10～15］。

表1 心臟病數據特征表

3.2 算法參數設置

算法參數設置如表2所示。

表2 BGWO和EBGWO算法參數設置

3.3 實驗結果

實驗比較了四種不同特征選擇算法在不同算法運行次數下的性能指標，算法運行次數從20次開始不斷增加，一直到200次。圖1和圖2的橫坐標表示的是算法運行次數，1表示第一次實驗運行次數為20次，10表示第十次實驗運行次數為200次。Errorb和countb表示使用原始灰狼算法做特征選擇部分后的錯誤率和特征選擇數，而Errore和counte表示使用改進后的灰狼算法做特征選擇部分后的錯誤率和特征選擇數。由圖1可知，除了第2次實驗之外（40次運行次數）之外，改進后的算法的分類準確度都優于其余所有的算法，平均錯誤率均在1.85%以下，效果有明顯的提升，且波動幅度較小，運行效果較為穩定。由圖2可知，在十次實驗中，使用改進后算法的平均特征選擇數都小于3.85，均低于PSO和GA的特征選擇數目。而與改進前的灰狼算法相比，特征選擇數減少了許多，且波動性也較為穩定。

圖2 四種不同算法進行特征選擇的檢測錯誤率對比

圖3 四種不同算法進行特征選擇后的特征選擇數目對比

4 結語

本文提出了一種新的灰狼算法的二元編碼化版本：基于距離貪心策略的二元灰狼算法。通過實驗表明，在相同條件下，該算法在特征選擇方面能夠取得較好的效果。縱向對比，該算法特征選擇后的檢測錯誤率優于原始的BGWO，在特征選擇數目方面優于改進版的EBGWO，總體來講集合了兩種算法的優點。橫向對比，該算法無論從特征選擇數還是檢測錯誤率，都優于PSO和GA，而且該算法收斂速度較快，能在較少的迭代次數下達到較好的效果。