基于蟻群優(yōu)化的特征基因選擇算法

侯遠(yuǎn)韶

(河南工業(yè)貿(mào)易職業(yè)學(xué)院 機(jī)電工程系，河南 鄭州 451191)

特征選擇方法是影響機(jī)器學(xué)習(xí)分類速度和分類精度的重要一環(huán)。為了提高分類精度，減少數(shù)據(jù)計(jì)算的復(fù)雜度，從原始數(shù)據(jù)集中提取出一組最能表達(dá)原始圖像信息的子集，即為特征選擇方法。特征選擇方法是一個(gè)NP問題，具體可以分為三大類即封裝式(Wrapper)、過濾式(Filter)和嵌入式(Embedded)[1]。Wrapper方法首先利用特定的學(xué)習(xí)模型大致確定特征子集，通過學(xué)習(xí)模型的準(zhǔn)確性帶動(dòng)特征搜索過程，將學(xué)習(xí)算法的優(yōu)劣定性為評(píng)估特征選擇的標(biāo)準(zhǔn)，進(jìn)而得到最優(yōu)子集。該方法需要對(duì)分類器進(jìn)行多次訓(xùn)練才能對(duì)每一個(gè)子集進(jìn)行評(píng)價(jià)，雖然精確度有所提高，但數(shù)據(jù)冗余計(jì)算量大，對(duì)數(shù)據(jù)集較大的模型并不適用。Filter特征選擇方法利用數(shù)據(jù)自身的統(tǒng)計(jì)特性作為基因評(píng)價(jià)準(zhǔn)則，通過判斷特征子集與目標(biāo)函數(shù)的相似度得到最優(yōu)子集。該方法分類速度快，但準(zhǔn)確率不高。Embedded特征選擇方法為了得到最優(yōu)特征子集，通過對(duì)原始數(shù)據(jù)進(jìn)行學(xué)習(xí)模型訓(xùn)練，在訓(xùn)練過程中得到基因的最終表達(dá)形式。該方法雖然能夠與學(xué)習(xí)模型互相影響，但時(shí)效性并不高[2]。蚊群算法作為一種解決組合優(yōu)化問題的經(jīng)典算法，可以很好地改善上述算法的不足，快速精確地提取到特征基因，進(jìn)而實(shí)現(xiàn)提升機(jī)器學(xué)習(xí)分類的精度和速度。

1 蟻群算法

1.1 蟻群算法思想

蟻群算法(ACO)又稱螞蟻算法，是意大利人Marco Dorigo在1992年提出的基于模擬蟻群覓食行為尋找優(yōu)化路徑的一種自然估算算法[3]。本質(zhì)上特征選擇問題可以轉(zhuǎn)化為求解離散組合的優(yōu)化，蟻群算法可以通過選擇機(jī)制、協(xié)調(diào)機(jī)制和更新機(jī)制進(jìn)行優(yōu)化。通過分析蟻群的遍歷，得到起點(diǎn)和終點(diǎn)之間所有路徑中最優(yōu)的一條[4]。每個(gè)特征可以理解為蟻群覓食時(shí)經(jīng)過的結(jié)點(diǎn)，通過0或1來表示螞蟻選擇的路徑，0表示該基因沒有被選中，1則表示該基因被選中。假設(shè)路徑為{1,1,0,1,0}則表示第1,2,4個(gè)基因被作為特征基因進(jìn)行下一步分類，而第3和第5個(gè)基因則作為冗余數(shù)據(jù)沒有被選中。每只螞蟻經(jīng)過一次完整的起點(diǎn)到食物的過程稱為遍歷，即一個(gè)子集，則m只螞蟻可以得到m個(gè)基因子集。螞蟻之間通過每個(gè)特征結(jié)點(diǎn)的信息素表達(dá)最優(yōu)的路徑，螞蟻之間在某一路徑傳達(dá)的信息素濃度越高，就意味著此路徑的選擇概率越大。特征子集(即蟻群覓食路徑)的優(yōu)劣可以通過適應(yīng)度函數(shù)來得到，特征子集越好適應(yīng)度函數(shù)越大[5]?；谙伻旱奶卣鬟x擇如圖1所示。

圖1 基于蟻群的特征選擇

1.2 蟻群算法數(shù)學(xué)模型

(1)

τij(t+1)=(1-ρ)τij(t)+Δτij

(2)

式(2)中：ρ∈[0,1]為信息素減弱程度；Δτij為信息素增量，即

(3)

2 特征選擇

2.1 特征選擇理論

為了降低數(shù)據(jù)維數(shù)，避免維數(shù)災(zāi)難的發(fā)生，需要從高維數(shù)據(jù)集中選擇具有代表性的特征子集來表示原始的特征集，這一過程即為特征選擇[6]。特征選擇的數(shù)學(xué)描述為：假設(shè)一個(gè)原始數(shù)據(jù)集中有n個(gè)特征分別為X1,X2,X3,…Xn，可以分為Y類，通過有監(jiān)督訓(xùn)練學(xué)習(xí)算法，得到能表示整個(gè)特征集的特征子集XOPT，即特征子集XOPT根據(jù)相應(yīng)的評(píng)價(jià)準(zhǔn)則確定為整個(gè)特征集的最優(yōu)特征子集。特征選擇具體流程如圖2所示。

圖2 特征選擇流程

2.2 特征選擇標(biāo)準(zhǔn)

特征選擇主要有3個(gè)步驟：首先，利用數(shù)學(xué)方法將圖像數(shù)據(jù)轉(zhuǎn)化為矩陣形式，通過函數(shù)來表示圖像特征即為特征的形成；其次，通過對(duì)原始圖像數(shù)據(jù)集進(jìn)行映射或者壓縮感知等變換，將高維數(shù)據(jù)低維化，利用低維數(shù)據(jù)表示圖像原始信息，即為特征提?。蛔詈?，依據(jù)相應(yīng)的評(píng)價(jià)準(zhǔn)則，從提取到的特征集中選擇最優(yōu)的、全面的、必需的特征子集，去除冗余的子集，即為特征選擇。評(píng)價(jià)特征選擇方法的優(yōu)劣主要從魯棒性、相異性、單獨(dú)性(即相關(guān)性)和少量性等方面進(jìn)行評(píng)判[7]。

不同特征子集可以分類是由于其屬于特征空間中不同的區(qū)域，這些區(qū)域的選擇標(biāo)準(zhǔn)主要有距離度量、信息度量、相關(guān)性度量和一致性度量[8]。當(dāng)特征子集中不同樣本類別距離盡可能大，同類別樣本的距離盡可能小時(shí)，特征子集才是最優(yōu)特征子集[9]。距離度量的數(shù)學(xué)表示為：存在樣本集S中有n個(gè)特征分別為X1，X2,X3,…Xn,可以分為C個(gè)聚類，K1,K2,…KC(i=1,2,…C),每個(gè)樣本維數(shù)為T，距離度量Fd的表達(dá)式為

(4)

式(4)中wi為類中心向量。其中

y=(y1,y2,…yT)

(5)

(6)

(7)

只有當(dāng)取Fd最小值時(shí)，表明選擇的子集為最優(yōu)特征子集。

3 基于蟻群優(yōu)化的特征基因選擇

蟻群算法將路徑結(jié)點(diǎn)作為特征，邊緣作為下一特征選擇，通過每只螞蟻對(duì)整個(gè)路徑的遍歷，得到滿足停止條件的最小數(shù)量的特征和結(jié)點(diǎn)[10]。但蟻群算法容易在局部循環(huán)，同時(shí)收斂速度慢，即螞蟻會(huì)對(duì)同一路徑重復(fù)搜索，導(dǎo)致算法停滯、計(jì)算數(shù)據(jù)量加大。同時(shí)算法對(duì)參數(shù)的要求比較高，參數(shù)的設(shè)置決定了算法的質(zhì)量[11]。因此，需要對(duì)蟻群算法進(jìn)行優(yōu)化和改進(jìn)。以往主要從以下幾個(gè)方面進(jìn)行算法的優(yōu)化和改進(jìn)。

a.增強(qiáng)概率的自適應(yīng)性。蟻群算法將路徑結(jié)點(diǎn)作為特征，邊緣作為下一特征選擇，因此對(duì)選擇下一結(jié)點(diǎn)概率算法進(jìn)行優(yōu)化。

b.蟻群通過每個(gè)特征結(jié)點(diǎn)的信息素表達(dá)最優(yōu)的路徑，螞蟻之間在某一路徑傳達(dá)的信息素濃度越高就意味著此路徑的選擇概率越大。因此，為了使信息素分配更加合理，對(duì)信息素更新規(guī)則進(jìn)行優(yōu)化。

c.將蟻群算法與其他智能優(yōu)化算法相結(jié)合，如與粗糙集等相結(jié)合。

本文采用基于蟻群算法與粗糙集的特征基因選擇算法。粗糙集作為研究不確定性方法，利用已知知識(shí)刻畫不確定知識(shí)，可以解釋不精確數(shù)據(jù)間的關(guān)系。定義信息系統(tǒng)可以由S=〈U,A,V,f〉表示，A表示非空有限條件屬性集合，V表示屬性的值域，U為非空有限條件對(duì)象集合，f則為V的映射即信息函數(shù)。其中?a∈A,x∈U,f(x,a)∈U,f(x,a)∈Va,A=C∩D且C∩D=Φ。具體算法流程如圖3所示。

輸入：信息系統(tǒng)S=〈U,A,V,f〉。

輸出：特征子集CS的最優(yōu)解(Characters-Set)。

(1)將原始數(shù)據(jù)信息進(jìn)行重置初始化。

a.最大重復(fù)反饋次數(shù)max=n，螞蟻數(shù)目m，候選特征子集；

b.選擇初始特征子集S，設(shè)定初始值為零，屬性集的分類個(gè)數(shù)初始值為NULL；

c.將螞蟻置于初始結(jié)點(diǎn)，設(shè)置初始值各特征結(jié)點(diǎn)信息素濃度為τi(0)=τ0。

(2)生成特征解和評(píng)價(jià)結(jié)點(diǎn)重要性函數(shù)。

a.構(gòu)造解：在起始點(diǎn)隨機(jī)放入m只螞蟻，進(jìn)行屬性集遍歷；

b.評(píng)價(jià)解：所有螞蟻遍歷后，選擇最好的螞蟻?zhàn)鳛榈淖顑?yōu)結(jié)果，通過評(píng)價(jià)結(jié)點(diǎn)重要性函數(shù)來得到特征子集的是否為最優(yōu)子集。

(3)驗(yàn)證算法的終止條件。假如得到了特征子集且最大重復(fù)反饋次數(shù)已經(jīng)到達(dá)了最大值，則進(jìn)行步驟6，否則進(jìn)行步驟4。

(4)環(huán)境信息素更新。將信息素的揮發(fā)和螞蟻?zhàn)陨硇畔⑺氐幕旌蠈?duì)結(jié)點(diǎn)信息素濃度的影響考慮進(jìn)去，對(duì)屬性結(jié)點(diǎn)的信息素濃度進(jìn)行更新。

(5)每次完成遍歷性后，生成新的螞蟻。把每只螞蟻的最后一個(gè)結(jié)點(diǎn)作為下一次迭代的開始，重復(fù)步驟2。

(6)輸出最優(yōu)特征子集CS。

圖3 蟻群優(yōu)化的特征基因選擇算法流程

4 實(shí)驗(yàn)仿真

實(shí)驗(yàn)采用Matlab實(shí)驗(yàn)平臺(tái)，電腦Windows XP操作系統(tǒng)，配置CPU為Intel I7處理器，16G內(nèi)存。在進(jìn)行實(shí)驗(yàn)前需要對(duì)樣本數(shù)據(jù)集進(jìn)行歸一化處理，使得每個(gè)樣本特征屬性列的數(shù)據(jù)都屬于[0,1][12]。為了驗(yàn)證算法的有效性和實(shí)用性，采用的樣本數(shù)據(jù)為UCI數(shù)據(jù)庫的3組數(shù)據(jù)和Internet上選定的2組數(shù)據(jù)，這些數(shù)據(jù)具有廣泛的代表性。實(shí)驗(yàn)數(shù)據(jù)描述如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)說明

為了驗(yàn)證算法的優(yōu)劣，將本文算法與基于貪婪法的特征選擇算法在實(shí)驗(yàn)數(shù)據(jù)集上進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果如表2所示。

表2 本文算法與基于貪婪法的特征選擇實(shí)驗(yàn)性能

由實(shí)驗(yàn)結(jié)果可知，基于蟻群優(yōu)化的特征基因選擇算法和傳統(tǒng)特征提取算法相比，不管是在準(zhǔn)確率上還是在運(yùn)行速度上都有一定的優(yōu)勢(shì)，可以大大提高分類效果，具有一定的應(yīng)用價(jià)值。

5 總結(jié)展望

分析了蟻群算法的模型以及現(xiàn)有算法在進(jìn)行特征選擇時(shí)存在的不足之處。為了提高蟻群算法的準(zhǔn)確性，利用特征對(duì)不同數(shù)據(jù)集的敏感度，尋找最優(yōu)基因，濾除無關(guān)基因，同時(shí)引入粗糙集的屬性重要度和依賴度，改進(jìn)蟻群算法的參數(shù)選擇方法，有效地提高了蟻群搜索的效率。實(shí)驗(yàn)結(jié)果表明，該算法具有一定的實(shí)用性和應(yīng)用價(jià)值。