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

童坤 鈕焱 李軍

（湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 武漢 430068）

1 引言

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

2 基于距離貪心策略的GWO

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

2.1 距離貪心策略

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

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

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

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

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

圖1 貪心策略圖示

2.2 基于距離貪心策略的GWO

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

1）計(jì)算連續(xù)編碼距離向量

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

其中t為當(dāng)次迭代的次數(shù)，maxiter為算法迭代的總次數(shù)。

2）距離映射

特征選擇問題中的連續(xù)型變量的搜索區(qū)間是任意設(shè)置的，通常情況下，特征選擇問題的搜索區(qū)間可以被人為設(shè)置為［0，1］。當(dāng)問題搜索區(qū)間設(shè)置不為［0，1］時(shí)候，則需要通過一個(gè)映射函數(shù)將該問題轉(zhuǎn)換為在區(qū)間［0，1］上的問題。假設(shè)問題搜索區(qū)間為［a，b］，一個(gè)最簡單的映射函數(shù)G（）構(gòu)造如下：

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

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

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

其中rand為［0，1］區(qū)間里任意的隨機(jī)數(shù)，其中hold和change表示對(duì)的操作，操作后的取值作為xd的值。change和hold的兩個(gè)操作表示為如式（13）、（14）：

更新策略根據(jù)Dd的取值來采取相應(yīng)的操作，按照所選的操作來更新xd的取值，算法1表示該算法的執(zhí)行步驟：

算法1 基于貪心策略灰狼優(yōu)化算法

輸入：種群中灰狼個(gè)體的數(shù)目n

算法迭代的總次數(shù)max_itr

初始化a，A和C三個(gè)控制參數(shù)。

隨機(jī)初始化n頭灰狼的位置向量

通過計(jì)算每個(gè)灰狼的適應(yīng)值來找出α，β和δ的位置向量。

t=1

While（t

For狼群中的每一頭狼i

For狼的位置向量的每一維

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

End

End

Ⅰ更新a，A和C三個(gè)控制參數(shù)

Ⅱ計(jì)算更新后每一頭灰狼的適應(yīng)值

Ⅲ更新α，β和δ

End

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

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

3.1 數(shù)據(jù)集及分類器準(zhǔn)備

本文實(shí)驗(yàn)所使用的數(shù)據(jù)集為UCI數(shù)據(jù)庫所提供的一組心臟病數(shù)據(jù)集，一共303條數(shù)據(jù)，每條數(shù)據(jù)記錄了心臟病人的所有生理指標(biāo)。該數(shù)據(jù)特征表如表1。

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

表1 心臟病數(shù)據(jù)特征表

3.2 算法參數(shù)設(shè)置

算法參數(shù)設(shè)置如表2所示。

表2 BGWO和EBGWO算法參數(shù)設(shè)置

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

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

圖2 四種不同算法進(jìn)行特征選擇的檢測錯(cuò)誤率對(duì)比

圖3 四種不同算法進(jìn)行特征選擇后的特征選擇數(shù)目對(duì)比

4 結(jié)語

本文提出了一種新的灰狼算法的二元編碼化版本：基于距離貪心策略的二元灰狼算法。通過實(shí)驗(yàn)表明，在相同條件下，該算法在特征選擇方面能夠取得較好的效果?？v向?qū)Ρ龋撍惴ㄌ卣鬟x擇后的檢測錯(cuò)誤率優(yōu)于原始的BGWO，在特征選擇數(shù)目方面優(yōu)于改進(jìn)版的EBGWO，總體來講集合了兩種算法的優(yōu)點(diǎn)。橫向?qū)Ρ?，該算法無論從特征選擇數(shù)還是檢測錯(cuò)誤率，都優(yōu)于PSO和GA，而且該算法收斂速度較快，能在較少的迭代次數(shù)下達(dá)到較好的效果。