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

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

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

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

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

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

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

1.1 模擬退火算法

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

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

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

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

斑點(diǎn)鬣狗的個(gè)體位置更新為

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

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

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

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

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

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

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

2.2 模擬退火斑點(diǎn)鬣狗混合算法

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

圖1 混合算法的流程圖

3 實(shí)驗(yàn)設(shè)計(jì)

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

實(shí)驗(yàn)基于UCI數(shù)據(jù)存儲(chǔ)庫(kù)中的8個(gè)數(shù)據(jù)集測(cè)試來(lái)評(píng)價(jià)混合算法的性能[17]，每個(gè)數(shù)據(jù)集的特征個(gè)數(shù)和樣本個(gè)數(shù)如表1所示，可以根據(jù)二進(jìn)制方案進(jìn)行有效測(cè)試。

表1 實(shí)驗(yàn)數(shù)據(jù)集列

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

3.3 測(cè)試評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

4.1 原始算法與混合算法的對(duì)比

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

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

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

表5 2種算法的平均運(yùn)行時(shí)間s

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

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

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

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

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

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

圖6 所提算法與其他算法的平均運(yùn)行時(shí)間比較

5 結(jié)論

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

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

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

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

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