基于模擬退火斑點鬣狗優(yōu)化算法的特征選擇

賈鶴鳴，姜子超，李瑤，孫康健，李金奪，彭曉旭

東北林業(yè)大學(xué) 機電工程學(xué)院，黑龍江 哈爾濱 150040

數(shù)據(jù)預(yù)處理是數(shù)據(jù)挖掘的一部分，可顯著地改善數(shù)據(jù)挖掘的性能。特征選擇是數(shù)據(jù)預(yù)處理的重要步驟，在減少處理時間的同時，處理更多的特征，進而提高機器學(xué)習(xí)的準(zhǔn)確性[1]。特征選擇問題是從某些特征中選取部分特征作為特征子集，所選子集具有比原特征集更優(yōu)秀的分類效果，其中分類精度與選擇特征個數(shù)是特征選擇的基本評價標(biāo)準(zhǔn)。特征選擇分為子集生成、子集評估、停止標(biāo)準(zhǔn)、結(jié)果驗證4個步驟，過濾式和封裝式是特征選擇的2種基本方法[2]，過濾式可以較快地獲取結(jié)果，但無關(guān)于后續(xù)的學(xué)習(xí)算法；而封裝式雖然速度上有劣勢，但準(zhǔn)確率高、偏差小，更適合結(jié)合優(yōu)化算法提高運行效率和精度，因此近年來多種混合元啟發(fā)式算法已在特征選擇領(lǐng)域進行了相關(guān)研究。賈鶴鳴等[3]提出一種基于熱交換的混合海鷗優(yōu)化算法應(yīng)用于特征選擇問題，極大地改善了原算法的信息分類與選擇能力；Wu等[4]將遺傳算法的交叉算子用于模擬退火算法，對支持向量機回歸的輸入特征子集選擇、核函數(shù)類型和核參數(shù)設(shè)置進行優(yōu)化，效果顯著；Basiri等[5]提出了一種混合蟻群和遺傳算法，并將其應(yīng)用于文本文檔的分類中，分類效果良好；Mafarja等[6]提出了一種基于模擬退火的混合鯨魚優(yōu)化算法，并將其應(yīng)用于特征選擇中，明顯改善了分類精度。上述所提出的混合元啟發(fā)式算法在特征選擇中均體現(xiàn)出明顯的優(yōu)勢，但是No-Free-Lunch定理表明沒有一種算法可以解決所有優(yōu)化問題，這促使我們不斷探索更優(yōu)秀的優(yōu)化算法以解決特征選擇問題[3]。

斑點鬣狗優(yōu)化是印度塔帕爾大學(xué)Dhiman等[7]提出的一種新的優(yōu)化算法，它主要模擬了斑點鬣狗的狩獵行為。斑點鬣狗依靠可信賴的朋友網(wǎng)絡(luò)和識別獵物的能力來捕食獵物，這種狩獵方法可以在更短的時間內(nèi)找到更好的解決方案。斑點鬣狗優(yōu)化極大地增強了算法的自適應(yīng)性，同時可以擴展到更高的維度，在優(yōu)化問題中得以廣泛應(yīng)用，但受隨機因子影響仍存在局部最優(yōu)、復(fù)雜優(yōu)化效果不良等缺陷；模擬退火算法是由Kirkpatrick等[8]提出的元啟發(fā)式算法，算法從一個較高的溫度開始，在溫度持續(xù)下降和概率函數(shù)組合的條件下去搜索空間中目標(biāo)函數(shù)的全局最優(yōu)解。模擬退火算法具有強大的局部搜索功能，將其應(yīng)用于混合算法中可以改善局部最優(yōu)解。

針對班點鬣狗算法受隨機因子的影響而導(dǎo)致的全局優(yōu)化效果差、局部易陷入最優(yōu)等問題，結(jié)合模擬退火算法的優(yōu)點，本文提出一種模擬退火斑點鬣狗優(yōu)化的混合元啟發(fā)式算法，采用封裝式的方法并將其應(yīng)用于特征選擇。在混合算法中，模擬退火算法作為斑點鬣狗算法中的一部分，2種算法均在每次迭代中運行一次，有效地提高了斑點鬣狗算法的利用率。為檢驗混合優(yōu)化算法在特征選擇中優(yōu)越性，通過特征選擇的8個數(shù)據(jù)集進行測試實驗，采用平均分類精度、適應(yīng)度、選擇特征個數(shù)（平均值，標(biāo)準(zhǔn)差）、運行時間4個指標(biāo)來評價優(yōu)化效果，與原始優(yōu)化算法、其他4種算法 (蟻群優(yōu)化 (ant colony optimization, ACO)[9]、混合鯨魚模擬退火優(yōu)化算法(hybrid whale optimization algorithm with simulated annealing, WOASA)[6]、正余弦算法(sine cosine algorithm, SCA)[10]、混合海鷗優(yōu)化算法(hybrid seagull optimization algorithm, HSOA)[3])對比。

1 原始優(yōu)化算法

1.1 模擬退火算法

模擬退火算法以一定的概率接受比當(dāng)前解更差的解，因此可以跳出局部最優(yōu)解并且獲得全局最優(yōu)解。模擬退火算法起始于隨機生成的解，根據(jù)預(yù)先定義的鄰域結(jié)構(gòu)，在每次迭代中產(chǎn)生最佳的鄰域解，利用適應(yīng)度函數(shù)進行評估[11]。當(dāng)鄰域解比當(dāng)前解更好時，將其認(rèn)為是最新的解，否則由Boltzmann概率確定最新解的概率，Boltzmann概率表示為

1.2 斑點鬣狗優(yōu)化算法

斑點鬣狗是非常聰明的群體社交動物，它們通過多種感官來識別親屬和其他個體，并對同一種族的關(guān)系進行了排名，群體中具有高地位的個體優(yōu)先獲得信任。由于這種生活習(xí)性，斑點鬣狗在群體狩獵方面具有非常高的成功率。斑點鬣狗種群的捕食機制包括搜索、包圍、狩獵和攻擊獵物四個過程[7]。斑點鬣狗算法的基本原理如下：

1)包圍機制：斑點鬣狗具有熟悉并判斷獵物的位置，從而包圍它們的能力。該行為的數(shù)學(xué)模型由具體描述為

斑點鬣狗的個體位置更新為

2)狩獵機制：斑點鬣狗通常依靠可信賴的種群網(wǎng)絡(luò)及識別獵物位置的能力來生活和分組捕殺。該機制的具體描述為

3)攻擊獵物（局部搜索）：斑點鬣狗在獵食的最后階段開始攻擊獵物，當(dāng)收斂因子時，斑點鬣狗個體便會向獵物發(fā)動攻擊。全局最優(yōu)解通過求取當(dāng)前最優(yōu)解集的平均值來確定斑點鬣狗搜索個體的更新趨勢。攻擊獵物的數(shù)學(xué)公式具體描述如下：

4)搜索機制（全局探索）：斑點鬣狗大多根據(jù)位于最優(yōu)解群集中的斑點鬣狗群或群集的位置來搜尋獵物，當(dāng)收斂因子時，斑點鬣狗將分散，遠離當(dāng)前的獵物，并尋找更合適的獵物位置。這種機制使得算法可在全局搜索。

2 混合優(yōu)化算法模型

2.1 二進制方案與適應(yīng)度函數(shù)

特征選擇的本質(zhì)是二元優(yōu)化問題，其解僅限于二進制{0,1}值，因此在使用斑點鬣狗優(yōu)化算法的特征選擇問題中需要制定二進制方案。優(yōu)化中，一維向量可以表示一個解決方案，其長度是原始數(shù)據(jù)集中的特征數(shù)目。解中的每個值均可由“0”或“1”表示，值“0”表示未選擇該特征，值“1”表示選擇了該特征[13-14]。

特征選擇可以看作是一個多目標(biāo)優(yōu)化的問題，其中主要有2個目標(biāo)相互矛盾：分類精度與選擇的特征個數(shù)。當(dāng)分類結(jié)果中分類精度較高，選擇特征個數(shù)較少時表明所得分類效果較好[15]。在整個迭代過程中，一般采用適應(yīng)度函數(shù)來評估每個解的質(zhì)量。因此，模擬退火和斑點鬣狗優(yōu)化算法可以平衡分類精度和選擇特征個數(shù)這2個標(biāo)準(zhǔn)。根據(jù)KNN分類器得到的解的分類精度和選擇的特征個數(shù)，所得適應(yīng)度函數(shù)為

2.2 模擬退火斑點鬣狗混合算法

斑點鬣狗優(yōu)化是一種在諸多優(yōu)化問題上取得良好效果的算法，強大的局部搜索能力是模擬退火的優(yōu)勢，把斑點鬣狗優(yōu)化算法得到的解作為初始狀態(tài)，然后利用模擬退火對其進行優(yōu)化，增強整個搜索過程中的局部尋優(yōu)能力，進而得到整體最優(yōu)解，形成新的混合模擬退火斑點鬣狗優(yōu)化算法(simulated annealing spotted hyena optimization,SASHO)，其中模擬退火用作班點鬣狗算法的優(yōu)化算子。混合算法的流程圖如圖1所示。

圖1 混合算法的流程圖

3 實驗設(shè)計

3.1 數(shù)據(jù)集

實驗基于UCI數(shù)據(jù)存儲庫中的8個數(shù)據(jù)集測試來評價混合算法的性能[17]，每個數(shù)據(jù)集的特征個數(shù)和樣本個數(shù)如表1所示，可以根據(jù)二進制方案進行有效測試。

表1 實驗數(shù)據(jù)集列

3.2 實驗參數(shù)設(shè)置

在實驗中，選擇原始算法與混合算法作為測試算法，種群大小設(shè)置為30，最大迭代次數(shù)取100。交叉驗證劃分每個數(shù)據(jù)集可評估算法的有效性，基于歐幾里得距離矩陣的KNN分類器(K=5)可以產(chǎn)生最佳的化簡效果。在K-fold交叉驗證中，訓(xùn)練和驗證的子集個數(shù)為(K-1)，測試子集個數(shù)為1，重復(fù)M次，則每個優(yōu)化算法對每個數(shù)據(jù)集進行KM次評估[18-20]。此外，實驗中還選擇了一些較新的優(yōu)化算法在UCI數(shù)據(jù)集上進行測試，包括ACO、WOASA、SCA和HSOA算法，其參數(shù)設(shè)置列在表2中。這些優(yōu)化算法均適用于特征選擇，因此與所提算法形成對比。實驗運行環(huán)境為MATLAB2016a。

表2 4種對比算法的參數(shù)

3.3 測試評價標(biāo)準(zhǔn)

為證明優(yōu)化算法在特征選擇過程中的優(yōu)化效果，本文采用以下標(biāo)準(zhǔn)評估每個優(yōu)化算法[21]：

平均分類精度：描述了所選特征集的分類精度的平均值。分類精度計算如下：

適應(yīng)度標(biāo)準(zhǔn)差δstd：表示在執(zhí)行次優(yōu)化算法后得到的最優(yōu)解的變化，可表示為

平均運行時間：表示每次運行算法的平均時間（s）。計算以下內(nèi)容：

4 實驗結(jié)果及分析

4.1 原始算法與混合算法的對比

為了驗證所提算法的在特征選擇則中的有效性與優(yōu)越性，將原始算法與混合算法在8個數(shù)據(jù)集上進行測試，測試結(jié)果分別從平均分類精度、平均選擇特征個數(shù)、適應(yīng)度（平均值/標(biāo)準(zhǔn)差）與平均運行時間上進行評價?；?種算法在分類精度和選擇特征個數(shù)上的測試結(jié)果如表3所示，數(shù)據(jù)表明：在分類精度上，所提混合算法可以對數(shù)據(jù)集更準(zhǔn)確地分類，在選擇特征個數(shù)上，所提混合算法可以對數(shù)據(jù)集選取更少的特征個數(shù)。因此所提混合算法在特征選擇中表現(xiàn)良好，表明算法有效；基于2種算法在特征選擇中的適應(yīng)度（平均值、標(biāo)準(zhǔn)偏差）實驗結(jié)果如表4所示，數(shù)據(jù)表明：所提混合算法在適應(yīng)度(Mean、std)值上表現(xiàn)良好。因此，所提混合算法比原始算法具有更好的效果和穩(wěn)定性；基于2種算法的平均運行時間如表5所示。數(shù)據(jù)表明：在8個數(shù)據(jù)集的運行時間上，原始算法略小于所提算法，這是由模擬退火算法中的適應(yīng)度函數(shù)的運行時間略長所造成的。綜上所述，實驗測試結(jié)果表明：在特征選擇中，所提混合算法有效且比原始算法有一定的優(yōu)越性。

表3 2種算法在分類精度和所選特征平均數(shù)的測試結(jié)果

表4 2種算法的適應(yīng)度（平均值、標(biāo)準(zhǔn)差）值測試結(jié)果

表5 2種算法的平均運行時間s

4.2 混合算法與其他優(yōu)化算法的對比

在前文中，所提混合算法在特征選擇中的分類精度和選擇特征個數(shù)上優(yōu)于原始算法，下面將所提算法與其他用于解決特征選擇問題的4種優(yōu)化算法進行對比，評價標(biāo)準(zhǔn)與前文2種對比算法相同?；谒崴惴ㄅc其他4種優(yōu)化算法在分類精度和選擇特征個數(shù)上的測試結(jié)果如圖2、3所示，結(jié)果表明：所提算法使分類精度平均提高了10.3%，平均減少了2.7個特征。因此，所提算法在特征選擇中的分類精度與選擇特征個數(shù)上優(yōu)于其他優(yōu)化算法；基于所提算法與其他4種優(yōu)化算法的適應(yīng)度（平均值、標(biāo)準(zhǔn)差）值測試結(jié)果如圖4、5所示，結(jié)果表明：所提算法的適應(yīng)度平均改善了46.1%，在特征選擇中表現(xiàn)較好，SCA在適應(yīng)度的標(biāo)準(zhǔn)差中具有相對穩(wěn)定的性能。綜合來看，在特征選擇中，所提算法具有更好、更穩(wěn)定的適應(yīng)度；基于所提算法與其他4種優(yōu)化算法的平均運行時間如圖6所示。數(shù)據(jù)表明：SCA時間最短，其次是HSOA，所提算法時間與其他算法無明顯特點，仍需改進。因此綜上所述，與其他4種優(yōu)化算法相比，所提算法在特征選擇中整體性良好，具有一定優(yōu)勢。

圖2 所提算法與其他算法的分類精度比較

圖3 所提算法與其他算法在選擇特征數(shù)平均值的比較

圖4 所提算法與其他算法的適應(yīng)度平均值比較

圖5 所提算法與其他算法的適應(yīng)度標(biāo)準(zhǔn)差比較

圖6 所提算法與其他算法的平均運行時間比較

5 結(jié)論

針對封裝式方法下的特征選擇問題，本文提出了一種基于模擬退火與斑點鬣狗優(yōu)化的混合算法，通過在UCI存儲庫中的8個標(biāo)準(zhǔn)數(shù)據(jù)集上的分類實驗來評估所提算法的性能，并與SHO、ACO、WOASA、HSOA、SCA算法進行對比。實驗結(jié)果表明：

1) 在8個數(shù)據(jù)集中，從分類精度與選擇特征個數(shù)上來看，所提出的SASHO算法能夠顯著提高分類精度，同時減少選擇特征的數(shù)目，優(yōu)于其他算法的特征選擇能力。

2) 與其他算法在適應(yīng)度的平均值與標(biāo)準(zhǔn)差上相比，SASHO算法具有有效的搜索空間，避免局部最優(yōu)，同時表現(xiàn)出良好的穩(wěn)定性。

3) 在平均運行時間上，SASHO算法雖然無明顯改善，但在分類精度與特征選擇個數(shù)方面仍具有較大優(yōu)勢。

因此，混合算法(SASHO)在空間搜索和特征屬性選擇方面具有出色表現(xiàn)。