基于蟻群優化的特征基因選擇算法

侯遠韶

(河南工業貿易職業學院 機電工程系，河南 鄭州 451191)

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

1 蟻群算法

1.1 蟻群算法思想

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

圖1 基于蟻群的特征選擇

1.2 蟻群算法數學模型

(1)

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

(2)

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

(3)

2 特征選擇

2.1 特征選擇理論

為了降低數據維數，避免維數災難的發生，需要從高維數據集中選擇具有代表性的特征子集來表示原始的特征集，這一過程即為特征選擇[6]。特征選擇的數學描述為：假設一個原始數據集中有n個特征分別為X1,X2,X3,…Xn，可以分為Y類，通過有監督訓練學習算法，得到能表示整個特征集的特征子集XOPT，即特征子集XOPT根據相應的評價準則確定為整個特征集的最優特征子集。特征選擇具體流程如圖2所示。

圖2 特征選擇流程

2.2 特征選擇標準

特征選擇主要有3個步驟：首先，利用數學方法將圖像數據轉化為矩陣形式，通過函數來表示圖像特征即為特征的形成；其次，通過對原始圖像數據集進行映射或者壓縮感知等變換，將高維數據低維化，利用低維數據表示圖像原始信息，即為特征提取；最后，依據相應的評價準則，從提取到的特征集中選擇最優的、全面的、必需的特征子集，去除冗余的子集，即為特征選擇。評價特征選擇方法的優劣主要從魯棒性、相異性、單獨性(即相關性)和少量性等方面進行評判[7]。

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

(4)

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

y=(y1,y2,…yT)

(5)

(6)

(7)

只有當取Fd最小值時，表明選擇的子集為最優特征子集。

3 基于蟻群優化的特征基因選擇

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

a.增強概率的自適應性。蟻群算法將路徑結點作為特征，邊緣作為下一特征選擇，因此對選擇下一結點概率算法進行優化。

b.蟻群通過每個特征結點的信息素表達最優的路徑，螞蟻之間在某一路徑傳達的信息素濃度越高就意味著此路徑的選擇概率越大。因此，為了使信息素分配更加合理，對信息素更新規則進行優化。

c.將蟻群算法與其他智能優化算法相結合，如與粗糙集等相結合。

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

輸入：信息系統S=〈U,A,V,f〉。

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

(1)將原始數據信息進行重置初始化。

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

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

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

(2)生成特征解和評價結點重要性函數。

a.構造解：在起始點隨機放入m只螞蟻，進行屬性集遍歷；

b.評價解：所有螞蟻遍歷后，選擇最好的螞蟻作為迭代的最優結果，通過評價結點重要性函數來得到特征子集的是否為最優子集。

(3)驗證算法的終止條件。假如得到了特征子集且最大重復反饋次數已經到達了最大值，則進行步驟6，否則進行步驟4。

(4)環境信息素更新。將信息素的揮發和螞蟻自身信息素的混合對結點信息素濃度的影響考慮進去，對屬性結點的信息素濃度進行更新。

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

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

圖3 蟻群優化的特征基因選擇算法流程

4 實驗仿真

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

表1 實驗數據說明

為了驗證算法的優劣，將本文算法與基于貪婪法的特征選擇算法在實驗數據集上進行測試，實驗結果如表2所示。

表2 本文算法與基于貪婪法的特征選擇實驗性能

由實驗結果可知，基于蟻群優化的特征基因選擇算法和傳統特征提取算法相比，不管是在準確率上還是在運行速度上都有一定的優勢，可以大大提高分類效果，具有一定的應用價值。

5 總結展望

分析了蟻群算法的模型以及現有算法在進行特征選擇時存在的不足之處。為了提高蟻群算法的準確性，利用特征對不同數據集的敏感度，尋找最優基因，濾除無關基因，同時引入粗糙集的屬性重要度和依賴度，改進蟻群算法的參數選擇方法，有效地提高了蟻群搜索的效率。實驗結果表明，該算法具有一定的實用性和應用價值。