基于ReliefF和蟻群算法的特征基因選擇方法分析

楊麗

摘要：文章以獲得最佳特征分類效果為前提，針對(duì)ReliefF算法和蟻群算法，對(duì)其在特征基因選擇中的運(yùn)用展開了分析，從而確定了這兩種方法對(duì)于特征分類的重要意義。

關(guān)鍵詞：ReliefF；蟻群算法；特征基因選擇方法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）32-0199-02

在確定特種基因選擇方法時(shí)，一般會(huì)運(yùn)用蟻群算法、ReliefF算法。其中，螞蟻算法主要用于組合優(yōu)化問題求解的元啟發(fā)式方法，體現(xiàn)了非常強(qiáng)的健壯性、回饋控制、Agent系統(tǒng)等優(yōu)勢(shì)，此外，螞蟻算法本身所體現(xiàn)的貪心策略、隨機(jī)策略也在原來的基礎(chǔ)上提高了全局搜索水平。通常在微陣列數(shù)據(jù)當(dāng)中，經(jīng)常出現(xiàn)標(biāo)記錯(cuò)誤或者類別標(biāo)簽錯(cuò)誤的樣品，這時(shí)便可以運(yùn)用蟻群算法，利用不同特征的冗余性組織分析，將以上相關(guān)問題合理解決。Relief算法則是一種非常經(jīng)典的Filter 方法，也是一種非常普及、高效率的維數(shù)約簡(jiǎn)法。Relief算法中包含了Relief、Relief和ReliefF，ReliefF更多使用與多分類、數(shù)據(jù)不足、噪聲等問題的求解。Relief 算法的時(shí)間復(fù)雜程度比較低，使用時(shí)也不需要分類精度這種評(píng)價(jià)函數(shù)，然而因?yàn)樵撍惴ㄊ且蕴卣鳈?quán)重算法為基礎(chǔ)，所以在選擇特征時(shí)只是提升與標(biāo)簽相關(guān)的特征權(quán)重值，將權(quán)重值低特征予以剔除，這樣一來就無法剔除冗余特征?；诖耍挛某鲇趯?duì)以上兩種算法優(yōu)良性能的考慮，以此為前提分析了特種基因的選擇方法。

1 Relief 算法與特征基因選擇方法結(jié)合

Relief算法在實(shí)際應(yīng)用中是一種效率非常高的 Filter 算法，按照特征的重要程度，對(duì)其進(jìn)行排序，以超出指定閾值的特征當(dāng)做特征子集。在訓(xùn)練集中可以確定Relief的任意樣本R，針對(duì)所有樣本都有2個(gè)最近鄰，分別來自于同類樣本H和異類樣本M[1]。如果選擇的樣本R和樣本H在訓(xùn)練集當(dāng)中出現(xiàn)與特征A相關(guān)的差異，那么特征A便會(huì)被賦予比較低的權(quán)重。樣本R和M在訓(xùn)練集中發(fā)生關(guān)于特征A的差異，那么特征A便會(huì)被賦予比較高的權(quán)重。由此一來，特征A可以通過Relief 對(duì)權(quán)重W[A]進(jìn)行更新，

即

W[A]=W[A]-diff（A，R，H）/m+diff（A，R，M）/m （1）

在公式（1）中，m為隨機(jī)抽樣個(gè)數(shù)，diff函數(shù)代表給定函數(shù)2個(gè)樣本差異。對(duì) W[A]進(jìn)行計(jì)算時(shí)，要使用m對(duì)其進(jìn)行歸一化處理，確保權(quán)重值在-1～1之間。

一旦特征屬性是標(biāo)稱屬性，這時(shí)對(duì)于diff（A，Ix，Iy）的計(jì)算需要按照如下公式進(jìn)行：

[diff（A，Ix，Iy）=0；value（A，Ix）value（A，Iy）I；otherwise] （2）

一旦特征屬性是數(shù)值屬性時(shí)，這時(shí)對(duì)于diff（A，Ix，Iy）的計(jì)算需要按照如下公式計(jì)算：

[diff（A，Ix，Iy）=|value（A，Ix）-value（A，Iy）|max（A）-min（A）] （3）

如果在計(jì)算時(shí)使用傳統(tǒng)的算法，那么會(huì)將計(jì)算局限在二分類問題中，也無法對(duì)數(shù)據(jù)缺失、噪聲等問題進(jìn)行很好的解決。早在20世紀(jì)末，便已經(jīng)有專家將Relief算法進(jìn)行了拓展，并且在原來的基礎(chǔ)上提出了ReliefF算法，將以上提出的一系列問題全部解決。ReliefF算法將所有樣本同類的k個(gè)最近鄰差異值、其余異類k個(gè)最近鄰差異值進(jìn)行平均，以此來解決數(shù)據(jù)內(nèi)噪聲帶來的影響。選擇最近鄰樣本數(shù)主要體現(xiàn)的是ReliefF、Relief二者的基本差異，保證了ReliefF算法本身所具有的魯棒性。

為了將數(shù)據(jù)缺失這一問題予以解決，相關(guān)專家對(duì)原有的diff（A，Ix，Iy）函數(shù)進(jìn)行了優(yōu)化，優(yōu)化之后的函數(shù)可以有效計(jì)算出屬性缺失值。如果樣本Ix存在缺失值，那么diff（A，Ix，Iy）的計(jì)算則是如下形式：

[diff（A，Ix，Iy）=1-P（value（A，Iy）|class（Ix））] （4）

如果樣本Ix與樣本Iy均含有缺失值，那么diff（A，Ix，Iy）函數(shù)計(jì)算則要按照如下形式進(jìn)行：

[diff（A，Ix，Iy）=|-V#value（A）P（V|class（Ix））×P（V|class（A，Iy）））] （5）

在公式（5）中，V代表全部樣本內(nèi)特征A的數(shù)值，ReliefF算法描述算法具體表現(xiàn)為如下算法1模式：

算法1

輸入：訓(xùn)練集D，迭代次數(shù)m，最近鄰樣本數(shù)k。

輸出：特征權(quán)重向量W。

初始化特征權(quán)重：

for i=1 to m

從D當(dāng)中選擇一個(gè)隨機(jī)樣本Ri；

For each classC=class（Ri）；

確定一個(gè)和Ri同類的k個(gè)最近鄰樣本，即Hj；

For each classC≠class（Ri）；

確定一個(gè)和Ri不同類的k個(gè)最近鄰樣本，即Mj（C）；

For A：I to All feature；

[W[A]=W[A]j=1kdiff（A，Ri，Hj）/mk]

[+C≠class（Ri）pi（C）1-p（class（Ri））j=ikdiff（A，Ri，Mj（C））/mk]

每次ReliefF在D中隨機(jī)選擇樣本Ri，隨后在從相同類別樣本內(nèi)確定k個(gè)最近鄰樣本，即Hj，在所有和Ri不同類樣本內(nèi)k個(gè)最近鄰樣本Mj（C），再對(duì)權(quán)重進(jìn)行更新，反復(fù)進(jìn)行上述流程，m次之后便可以完成權(quán)重排序，選擇低權(quán)重的特征。

2 螞蟻算法與特征基因選擇方法結(jié)合

2.1 螞蟻算法

專家在觀察螞蟻覓食的過程中發(fā)現(xiàn)，螞蟻前進(jìn)途中會(huì)在之前行走的路途中放射一種化學(xué)物質(zhì)，即信息素，其余螞蟻會(huì)按照道路上釋放信息素濃度的不同，尋找自己行走的路線，在之前的基礎(chǔ)上釋放出更多信息素[2]。如果一條道路螞蟻數(shù)量多，那么則證明信息素多，便會(huì)吸引更多的螞蟻，通過這種方式來確定食物、巢穴之間的最短路途。由此可以證明，盡管一只螞蟻的力量小，但是集合所有螞蟻卻能發(fā)揮出無窮的力量[3]。endprint

在20世紀(jì)末，比利時(shí)的專家克羅尼和多里格等人便通過對(duì)蟻群的研究確定了從起點(diǎn)到終點(diǎn)最近的路徑。在基因全集中放置m只螞蟻，螞蟻需要走過所有基因，再利用蟻群之間的合作確定最終是否選擇這一基因。在試驗(yàn)過程中，每個(gè)基因都被視為一個(gè)結(jié)點(diǎn)，兩個(gè)相鄰結(jié)點(diǎn)之間都有2條路線，即0，1。螞蟻需要路過所有結(jié)點(diǎn)，并且在行進(jìn)的過程中選擇一個(gè)路徑，一旦螞蟻選擇路徑1，那么代表這一基因被選擇，0則沒有被選擇。假設(shè)其中一個(gè)路徑{1，0，1，0，1}代表第1個(gè)、3個(gè)、5個(gè)基因，將其確定為特征基因，那么基因2和基因4則表示沒有被選擇。當(dāng)m只螞蟻經(jīng)過了所有路徑之后，便可以獲得m個(gè)基因子集。螞蟻之間利用信息素展開合作，路徑上的信息素濃度高，針對(duì)的路徑被選率則越高。一旦螞蟻到了指定食物處，便要通過一些方法評(píng)估特征子集，以此確定一個(gè)最佳特征基因子集。

2.2 設(shè)置參數(shù)與算法描述

在以上分析的螞蟻算法模型當(dāng)中，其中還存在幾個(gè)亟待解決的問題：其一，信息素初始值設(shè)置與更新[4]；其二，路徑被選概率設(shè)置；其三，特征子集質(zhì)量評(píng)估。在路徑1中，信息素初始濃度通過基因i，并且在決策屬性D重要程度的基礎(chǔ)上進(jìn)行了定義，即SGF（i，C，D）；將路徑0中信息素濃度設(shè)置為1，如此一來便可以提高該路徑被選幾率，對(duì)特征子集長(zhǎng)度進(jìn)行合理控制，從而加快算法收斂速度，使運(yùn)算效率更高。

通過路徑選擇概率結(jié)構(gòu)模式為：

[Pkij（t）=τijkjτij] （6）

在公式（6）中，[τij]是第i個(gè)基因第j條路徑信息素濃度，k則是j可能取值。當(dāng)完成迭代之后，這對(duì)全部路徑中信息素濃度需要進(jìn)行更新，具體如公式（7）所示：

[τi（t+1）=（1-η）×τi（t）+Δτi（t）] （7）

在公式（7）中，[η]是信息素蒸發(fā)因子，對(duì)自然環(huán)境下螞蟻分泌信息素?fù)]發(fā)之后使其濃度不斷變淡的成效，[Δτi（t）]是信息素增量，具體如公式（8）所示：

[Δτi（t）=1/（θ×L（k）+（1-θ）×γ（k））-1），psthway∈S0，pathway?S] （8）

在上述公式（8）中，L（k）代表螞蟻k收集的特征子集長(zhǎng)度，也就是在路徑1中數(shù)量。[γ（k）]是決策屬性對(duì)于這一特征子集所呈現(xiàn)的依賴度[5]。[θ]∈（0，1）的作用是對(duì)特征子集長(zhǎng)度、性能進(jìn)行控制。為了將計(jì)算量簡(jiǎn)化，使其能夠有效區(qū)別不同路徑中信息素濃度，S一般取前10%螞蟻所針對(duì)路徑。通常L（k）數(shù)值越小，[γ（k）]數(shù)值就越大，這時(shí)則代表新素增量大，即螞蟻選擇該條路徑的幾率越大，如此一來特征子集便會(huì)快速實(shí)現(xiàn)距離最短、決策屬性依賴度最大的發(fā)展目標(biāo)[6]。一旦螞蟻找到了食物，便會(huì)將特征子集屬性依賴度和長(zhǎng)度進(jìn)行結(jié)合，以此完成特征子集質(zhì)量的評(píng)估，具體定義為：

[ε（S=n/（θ×L（S）+（1-θ）×（γ（S））-1）] （9）

在公式（9）中，n是數(shù)據(jù)集基因數(shù)。在評(píng)價(jià)函數(shù)的基礎(chǔ)上，可以確定決策屬性依賴度最大、最短的特征基因子集。

3 結(jié)果分析

為了對(duì)ReliefF和蟻群算法的特征基因選擇性能進(jìn)行評(píng)估，下面重點(diǎn)以實(shí)際基因數(shù)據(jù)集的方式進(jìn)行驗(yàn)證，并分析最終結(jié)果。

如下表1是結(jié)腸和白血病數(shù)據(jù)集，其中白血病數(shù)據(jù)集中樣本數(shù)量共75個(gè)，其中有45個(gè)急性淋巴白血病樣本，30個(gè)急性骨髓白血病樣本，所有樣本中都有7215個(gè)基因。結(jié)腸數(shù)據(jù)集中共有63個(gè)樣本，其中腫瘤樣本30個(gè)，正常結(jié)腸組織樣本33個(gè)，所有樣本中都有2005個(gè)基因。

通過計(jì)算機(jī)、編譯軟件、分類器進(jìn)行試驗(yàn)。螞蟻數(shù)量m=50，最大迭代次數(shù)Wmax=50，蒸發(fā)因子[η]=0.5，參數(shù)[θ]=0.2。通過一系列分析以及建模解析，可以確定白血病數(shù)據(jù)集分類準(zhǔn)確率是85.2%，結(jié)腸數(shù)據(jù)集分類準(zhǔn)確率是84.6%。最后使用ReliefF算法和蟻群算法選擇最佳特征基因子集，并對(duì)分類效果進(jìn)行觀察，可以確定的是，白血病數(shù)據(jù)集特征子集規(guī)模為10，結(jié)腸數(shù)據(jù)集特征子集規(guī)模為7，分類準(zhǔn)確率都達(dá)到了最高。

4 結(jié)束語

綜上所述，使用ReliefF算法和蟻群算法進(jìn)行的特征基因選擇，能夠有效提升分類準(zhǔn)確率，并且獲得最佳的特征基因組合，這為今后相關(guān)工作的進(jìn)行提供了有效的參考。

參考文獻(xiàn)：

[1] 魏峻.基于全局和聲搜索算法的特征基因選擇方法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，44（03）：372-379.

[2] 劉建華，楊建國，劉華平，等.基于勢(shì)場(chǎng)蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015，46（09）：18-27.

[3] 王立國，魏芳潔.結(jié)合遺傳算法和蟻群算法的高光譜圖像波段選擇[J].中國圖象圖形學(xué)報(bào)，2013，18（02）：235-242.

[4] 吳華鋒，陳信強(qiáng)，毛奇凰，等.基于自然選擇策略的蟻群算法求解TSP問題[J].通信學(xué)報(bào)，2013，34（04）：165-170.

[5] 萬曉鳳，胡偉，方武義，等.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃研究[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（18）：63-66.

[6] 李麗，李霞，郭政，等.兩種過濾特征基因選擇算法的有效性研究[J].生命科學(xué)研究，2013（4）：369-373+376.endprint