侯遠韶

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

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

1 蟻群算法

1.1 蟻群算法思想

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

圖1 基于蟻群的特征選擇

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

(1)

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

(2)

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

(3)

2 特征選擇

2.1 特征選擇理論

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

圖2 特征選擇流程

2.2 特征選擇標準

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

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

(4)

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

y=(y1,y2,…yT)

(5)

(6)

(7)

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

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

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

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

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

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

本文采用基于蟻群算法與粗糙集的特征基因選擇算法。粗糙集作為研究不確定性方法，利用已知知識刻畫不確定知識，可以解釋不精確數(shù)據(jù)間的關系。定義信息系統(tǒng)可以由S=〈U,A,V,f〉表示，A表示非空有限條件屬性集合，V表示屬性的值域，U為非空有限條件對象集合，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ù)信息進行重置初始化。

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

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

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

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

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

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

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

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

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

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

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

4 實驗仿真

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

表1 實驗數(shù)據(jù)說明

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

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

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

5 總結(jié)展望

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