基于改進(jìn)斑點(diǎn)鬣狗優(yōu)化算法的同步優(yōu)化特征選擇

賈鶴鳴，姜子超，李 瑤，孫康健

（1.三明學(xué)院信息工程學(xué)院，福建三明 365004；2.東北林業(yè)大學(xué)機(jī)電工程學(xué)院，哈爾濱 150040）

（*通信作者電子郵箱jiaheminglucky99@126.com）

0 引言

隨著各領(lǐng)域的信息計(jì)算需求不斷增加，數(shù)據(jù)挖掘技術(shù)發(fā)展日新月異，人類進(jìn)入大數(shù)據(jù)時(shí)代［1］。海量的數(shù)據(jù)不僅給人們帶來(lái)繁重的處理工作，也無(wú)法準(zhǔn)確地從中提取有效信息，機(jī)器學(xué)習(xí)的出現(xiàn)提升了數(shù)據(jù)處理的效果與能力。作為數(shù)據(jù)挖掘技術(shù)的一個(gè)分支，數(shù)據(jù)分類是一項(xiàng)重要的基礎(chǔ)工作，而數(shù)據(jù)中冗余、不相關(guān)的特征或噪聲屬性常常會(huì)影響分類的性能。特征選擇是重要的數(shù)據(jù)預(yù)處理環(huán)節(jié)，其基于某種評(píng)價(jià)標(biāo)準(zhǔn)從原特征空間中選擇特征子集，通過(guò)消除數(shù)據(jù)中的冗余和不相關(guān)特征來(lái)減少計(jì)算時(shí)間，提升學(xué)習(xí)準(zhǔn)確率［2］，故所選特征子集比原特征集具有更優(yōu)秀的分類效果，從而顯著改善數(shù)據(jù)挖掘的能力。特征選擇依據(jù)其與學(xué)習(xí)器結(jié)合的方式不同可分為過(guò)濾式、封裝式、嵌入式與集成式四種［3］，本文主要研究的是封裝式特征選擇方法，對(duì)于分類問(wèn)題而言，其核心研究?jī)?nèi)容為如何利用搜索策略與學(xué)習(xí)算法在高分類準(zhǔn)確率上獲取最優(yōu)特征子集，兩者矛盾是特征選擇的主要挑戰(zhàn)。

因特征選擇可視為最優(yōu)化問(wèn)題，為提高傳統(tǒng)封裝式特征選擇所得最優(yōu)特征子集的分類準(zhǔn)確性，故諸多學(xué)者采取元啟發(fā)式優(yōu)化算法作為搜索策略對(duì)其進(jìn)行研究。在K最近鄰學(xué)習(xí)算法中，Jia 等［4］針對(duì)封裝式特征選擇分類性能差設(shè)計(jì)了一種混合海鷗優(yōu)化算法，通過(guò)引入熱交換原理來(lái)增強(qiáng)海鷗算法的局部搜索能力，有效提高了數(shù)據(jù)分類準(zhǔn)確率并減少計(jì)算時(shí)間；張翠軍等［5］提出一種多目標(biāo)骨架粒子群優(yōu)化的封裝式特征選擇算法，該方法顯著改善了數(shù)據(jù)分類的性能與效率；Mafarja等［6］提出了一種基于鯨魚(yú)優(yōu)化的封裝式特征選擇方法，利用二進(jìn)制鯨魚(yú)優(yōu)化算法來(lái)搜索最優(yōu)特征子集完成分類任務(wù)，效果良好；張霞等［7］提出一種增強(qiáng)蜂群算法優(yōu)化的封裝式特征選擇方法，極大地提高了數(shù)據(jù)分類的準(zhǔn)確率。在支持向量機(jī)（Support Vector Machine，SVM）的學(xué)習(xí)算法［8］中，通過(guò)引用核函數(shù)技術(shù)生成精確模型，提高了計(jì)算效率與準(zhǔn)確率，但其懲罰因子與核函數(shù)參數(shù)的選取會(huì)影響算法的泛化學(xué)習(xí)能力，而參數(shù)的調(diào)整與選擇亦可視為優(yōu)化問(wèn)題來(lái)研究。莊嚴(yán)等［9］將蟻群優(yōu)化算法引入SVM 參數(shù)的調(diào)整選擇中，效果良好但未對(duì)原優(yōu)化算法做出特征選擇的應(yīng)用研究；Huang 等［10］將遺傳算法用于同步優(yōu)化支持向量機(jī)的參數(shù)調(diào)整與特征選擇，改善了SVM分類的效果，雖克服了對(duì)其單獨(dú)優(yōu)化的缺陷，但未對(duì)遺傳算法做出改進(jìn)研究；張進(jìn)等［11］提出了一種基于改進(jìn)粒子群優(yōu)化的SVM 特征選擇與參數(shù)聯(lián)合優(yōu)化方法，有效提高了特征選擇的性能，但所選優(yōu)化算法較為陳舊，優(yōu)化性能有待進(jìn)一步提升。上述研究所采取的元啟發(fā)式優(yōu)化算法均體現(xiàn)出一定優(yōu)勢(shì)，但在特征選擇及SVM 參數(shù)同步優(yōu)化的實(shí)際應(yīng)用中，待優(yōu)化目標(biāo)體現(xiàn)出的復(fù)雜性與多樣性使得部分優(yōu)化算法在搜索計(jì)算時(shí)表現(xiàn)不佳，因此對(duì)優(yōu)化機(jī)制新穎、求解精準(zhǔn)、綜合計(jì)算能力強(qiáng)的優(yōu)化算法探究仍是封裝式特征選擇的重要研究方向之一，本文針對(duì)SVM 參數(shù)調(diào)整與特征選擇聯(lián)合同步優(yōu)化效果做出深入研究，使得SVM 學(xué)習(xí)算法獲取更精確的分類模型，降低單獨(dú)優(yōu)化的時(shí)間成本，同時(shí)改善封裝式特征選擇的性能。

受生物行為與自然現(xiàn)象啟示的元啟發(fā)式優(yōu)化算法已有二十余年的研究，其主要包括進(jìn)化類與群智能類。以遺傳算法（Genetic Algorithm，GA）［10］為主的進(jìn)化類包括：差分進(jìn)化（Differential Evolution，DE）［12］算法、生物地理學(xué)優(yōu)化（Biogeography Based Optimizer，BBO）［13］等；以粒子群優(yōu)化（Particle Swarm Optimization，PSO）［14］算法為主的群智能類包括：布谷鳥(niǎo)搜索（Cuckoo Search，CS）［15］算法、灰狼優(yōu)化（Grey Wolf Optimizer，GWO）［16］算 法、鯨魚(yú)優(yōu)化算法（Whale Optimization Algorithm，WOA）［17］等。盡管兩類算法優(yōu)化機(jī)制不同，但優(yōu)化目標(biāo)均為求解某一范圍內(nèi)的最優(yōu)值。上述優(yōu)化算法在現(xiàn)實(shí)的復(fù)雜工程問(wèn)題中得到了有效的應(yīng)用，但No-Free-Lunch 定理［18］表明沒(méi)有一種算法能解決所有優(yōu)化問(wèn)題，因此對(duì)更優(yōu)秀的優(yōu)化算法的探索仍具有較高的研究?jī)r(jià)值。Dhiman 等［19］提出的斑點(diǎn)鬣狗優(yōu)化（Spotted Hyena Optimizer，SHO）算法在諸多工程優(yōu)化中效果良好，其與GWO 等均為群智能類優(yōu)化算法，因此近年來(lái)諸多學(xué)者對(duì)其優(yōu)化能力進(jìn)行了相關(guān)研究。Kumar 等［20］基于SHO 設(shè)計(jì)了其二進(jìn)制版本算法（Binary Spotted Hyena Optimizer，BSHO），將其離散化處理后應(yīng)用于封裝式特征選擇中，通過(guò)數(shù)據(jù)集的特征選擇實(shí)驗(yàn)仿真驗(yàn)證了二進(jìn)制的斑點(diǎn)鬣狗優(yōu)化算法在特征選擇領(lǐng)域中的優(yōu)越性與可行性；Jia 等［21］針對(duì)SHO 算法的局部?jī)?yōu)化效果不佳，混入模擬退火算法來(lái)增強(qiáng)搜索能力，提出斑點(diǎn)鬣狗模擬退火（Spotted Hyena Optimizer Simulated Annealing，SHOSA）算法，結(jié)合K 最近鄰學(xué)習(xí)算法應(yīng)用于封裝式的特征選擇中，提高了分類精度與特征選擇性能。綜上所述，SHO 算法在封裝式特征選擇的應(yīng)用中表現(xiàn)良好、效果顯著，與其他群智能優(yōu)化算法相比具有一定的競(jìng)爭(zhēng)性，故本文采用該算法進(jìn)行封裝式特征選擇方面的研究。

本文主要研究?jī)?nèi)容如下：首先在DE算法中引入自適應(yīng)控制參數(shù)［22］，增強(qiáng)原算法搜索能力，提出自適應(yīng)差分進(jìn)化（Adaptive Differential Evolution，ADE）算法；其次用混沌初始化［23］、錦標(biāo)賽選擇策略［24］與ADE 算法對(duì)標(biāo)準(zhǔn)SHO 算法進(jìn)行改進(jìn)，增強(qiáng)原算法的局部搜索能力，提高其尋優(yōu)效率與求解精度；隨后利用改進(jìn)算法優(yōu)化支持向量機(jī)學(xué)習(xí)器，將這種模型用于封裝式的特征選擇中，同步處理特征子集選取與支持向量機(jī)參數(shù)調(diào)節(jié)；最后利用標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行測(cè)試仿真實(shí)驗(yàn)，對(duì)比分析評(píng)價(jià)指標(biāo)，證明本文所提算法能夠避免局部最優(yōu)，提高全局搜索精度，在解決封裝式特征選擇問(wèn)題時(shí)效果顯著。

1 相關(guān)算法

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

標(biāo)準(zhǔn)斑點(diǎn)鬣狗優(yōu)化算法源于非洲斑點(diǎn)鬣狗的種群狩獵覓食機(jī)制，主要包括對(duì)獵物的搜索、包圍、狩獵和攻擊過(guò)程［19］。

1）包圍過(guò)程。

斑點(diǎn)鬣狗首先會(huì)尋找獵物，依靠視覺(jué)來(lái)判斷獵物的位置。將此刻與獵物距離最近的那只斑點(diǎn)鬣狗視為當(dāng)前最優(yōu)解，隨后其他斑點(diǎn)鬣狗的位置將依據(jù)最優(yōu)解進(jìn)行更新，從而獲得全局最優(yōu)解。數(shù)學(xué)模型的描述如式（1）和（2）所示：

式中：Dh定義為斑點(diǎn)鬣狗與獵物間的距離；x為當(dāng)前迭代數(shù)；P是斑點(diǎn)鬣狗位置；Pp代表獵物位置；B和E分別為搖擺因子和收斂因子，具體定義如下：

式中，rd1與rd2為［0，1］區(qū)間隨機(jī)值；h為控制因子，迭代過(guò)程中從5 線性遞減到0；iter=1，2，…，Maxiter，Maxiter為最大迭代次數(shù)。

2）狩獵過(guò)程。

斑點(diǎn)鬣狗依靠信任等級(jí)制度來(lái)進(jìn)行分組捕殺。在種群中定義最佳搜索個(gè)體，其他斑點(diǎn)鬣狗搜索個(gè)體將朝著最佳搜索個(gè)體聚集，并組成最佳搜索組。因此該行為具體定義為：

式中：Ph為第一個(gè)最佳搜索個(gè)體位置；其他個(gè)體位置定義為Pk；Ch為最佳搜索組位置；N為斑點(diǎn)鬣狗數(shù)量，定義如下所示：

式中：M為一個(gè)［0.5，1］的隨機(jī)向量，nos表示所有可行解的數(shù)量。該過(guò)程與在給定搜索空間中尋找最優(yōu)解類似。

3）攻擊過(guò)程（局部搜索）。

在此階段斑點(diǎn)鬣狗將繼續(xù)更新自己的位置，最終對(duì)獵物發(fā)動(dòng)攻擊?？刂埔蜃訉㈦S著迭代次數(shù)增加從5線性減小到0，同時(shí)收斂因子E也逐漸減小。當(dāng)|E|＜1 時(shí)，斑點(diǎn)鬣狗將發(fā)動(dòng)攻擊。攻擊獵物的數(shù)學(xué)公式如下所示：

式中P(x+1)為當(dāng)前最優(yōu)解集的平均值。

4）搜索過(guò)程（全局探索）。

多數(shù)斑點(diǎn)鬣狗根據(jù)最佳搜索組Ch中的斑點(diǎn)鬣狗的位置來(lái)搜索獵物，然而當(dāng)收斂因子|E|＞1 時(shí)，斑點(diǎn)鬣狗會(huì)彼此遠(yuǎn)離，再次尋找和攻擊獵物，從而進(jìn)行全局搜索。

1.2 差分進(jìn)化算法

Storn 等［12］提出的差分進(jìn)化算法與遺傳算法類似，包括變異、交叉和選擇操作。該算法從初始種群開(kāi)始，把兩個(gè)隨機(jī)個(gè)體的向量差與第三個(gè)個(gè)體求和來(lái)得到變異個(gè)體，然后將變異個(gè)體與父代種群中相應(yīng)的個(gè)體按一定規(guī)則交叉產(chǎn)生新個(gè)體。通過(guò)進(jìn)化，優(yōu)勝劣汰，保留優(yōu)良個(gè)體，向最優(yōu)解進(jìn)行搜索。算法中“變異”“交叉”和“選擇”算子如下所示。

1）變異算子。

DE算法的變異操作定義為：

2）交叉算子。

其中：rand是［0，1］的隨機(jī)數(shù)；CR表示交叉概率。

3）選擇算子。

式中f為適應(yīng)度函數(shù)。

2 改進(jìn)斑點(diǎn)鬣狗優(yōu)化算法

標(biāo)準(zhǔn)斑點(diǎn)鬣狗算法參數(shù)設(shè)置簡(jiǎn)單、結(jié)構(gòu)清晰，同時(shí)全局搜索能力較強(qiáng)，但該算法尚處于研究初級(jí)階段，仍存在一些缺陷，如局部搜索能力弱、后期收斂速度慢等。因此，本文將使用混沌初始化策略［23］、錦標(biāo)賽選擇策略［24］和ADE 算法對(duì)其進(jìn)行改進(jìn)，提出一種自適應(yīng)差分進(jìn)化斑點(diǎn)鬣狗優(yōu)化（Adaptive Differential Evolution Spotted Hyena Optimizer，ADESHO）算法來(lái)改善其優(yōu)化復(fù)雜性問(wèn)題時(shí)的不足。

2.1 自適應(yīng)差分進(jìn)化算法

據(jù)差分進(jìn)化算法表達(dá)式可知，SF和CR是DE 算法中的兩個(gè)重要參數(shù)，該參數(shù)的選擇會(huì)影響優(yōu)化效果。但在DE 算法中，其值均為常數(shù)，不足以適應(yīng)各類問(wèn)題，特別是復(fù)雜的求解問(wèn)題，因此引入可自適應(yīng)控制參數(shù)［22］改進(jìn)DE 算法，即ADE 算法。自適應(yīng)控制參數(shù)SF和CR分別表示為：

式中：rand1～rand4均為0～1 的隨機(jī)數(shù)；τ1和τ2表示轉(zhuǎn)換概率；SFl和SFu為邊界縮放因子。在本文中，τ1與τ2為0.1；SF及CR的初始值［22］分別為0.5與0.9。ADE算法流程如圖1所示。

圖1 ADE算法流程Fig.1 Flowchart of ADE algorithm

ADE 與GA 類似，雖均包括變異、交叉、選擇操作，但ADE算法源于DE，仍與GA 有一定的區(qū)別。從優(yōu)化機(jī)制上來(lái)看，GA［10］模擬基因重組與進(jìn)化的自然過(guò)程，把待解決優(yōu)化問(wèn)題的參數(shù)編成二進(jìn)制或十進(jìn)制碼等的基因，若干基因組成一個(gè)染色體（個(gè)體），而染色體進(jìn)化類似于自然選擇、配對(duì)交叉和變異的運(yùn)算，經(jīng)過(guò)多次重復(fù)迭代（即世代遺傳）直到獲得最終優(yōu)化結(jié)果，其較容易陷入局部最優(yōu)，存在一定的早熟現(xiàn)象；而ADE算法則是基于種群隨機(jī)選擇個(gè)體向量，將差分向量賦予權(quán)值后與第3 個(gè)隨機(jī)選擇的個(gè)體向量疊加，產(chǎn)生新的變異個(gè)體，在原DE［12］算法的基礎(chǔ)上進(jìn)行自適應(yīng)參數(shù)運(yùn)算，與預(yù)先確定的父代個(gè)體向量交叉產(chǎn)生實(shí)驗(yàn)向量，在不斷的進(jìn)化下評(píng)價(jià)種群，保留優(yōu)秀個(gè)體，引導(dǎo)搜索過(guò)程向最優(yōu)解逼近，改善優(yōu)化效果。綜上，ADE 算法在DE 算法中引入自適應(yīng)參數(shù)，主要是利用差分的機(jī)制平衡啟發(fā)式算法的探索與利用水平，而GA 則是通過(guò)原始種群間的基本遺傳變異、進(jìn)化操作進(jìn)行算法在解空間的探索與利用，因此基于以上兩者區(qū)別，本文選擇優(yōu)勢(shì)較強(qiáng)的ADE算法進(jìn)行相關(guān)混合優(yōu)化研究。

Lin 等［22］提出混合免疫算法和自適應(yīng)差分進(jìn)化算法增強(qiáng)了免疫算法的收斂速度和種群多樣性；Elaziz等［25］提出混合飛蛾搜索差分進(jìn)化算法（Moth Search and Differential Evolution Algorithm，MSDEA），增強(qiáng)了飛蛾搜索算法的局部搜索能力，在云計(jì)算任務(wù)調(diào)度問(wèn)題上效果顯著。在上述混合算法應(yīng)用啟發(fā)下，為避免算法陷入局部最優(yōu)，本文將ADE 算法與SHO 算法混合優(yōu)化，以提高SHO的求解精度和穩(wěn)定性。

2.2 混沌初始化策略

在群智能算法中，種群初始化方法決定了全局搜索的質(zhì)量和效率。初始種群的多樣性可以提高搜索的效率，增強(qiáng)算法的計(jì)算能力。標(biāo)準(zhǔn)SHO 算法采用隨機(jī)初始化策略，具有一定概率的重復(fù)性，可能不會(huì)遍歷搜索空間，未能最大限度發(fā)揮SHO算法的優(yōu)化能力。

混沌理論有強(qiáng)大的隨機(jī)性、遍歷性、敏感性和非重復(fù)性。作為一種優(yōu)化策略，該理論已經(jīng)被有效地應(yīng)用于粒子群算法和人工蜂群算法等群智能算法中產(chǎn)生初始種群［23］。因此，利用混沌理論可增強(qiáng)初始種群的多樣性，使算法以更高的效率對(duì)搜索空間進(jìn)行尋優(yōu)。目前群智能算法多采用Logistic 映射進(jìn)行混沌初始化，但均勻性較差。相對(duì)于Logistic 映射，Tent映射具有結(jié)構(gòu)簡(jiǎn)單，遍歷均勻性更好的優(yōu)點(diǎn)，因此，本文選擇Tent 映射產(chǎn)生的混沌序列對(duì)斑點(diǎn)鬣狗種群進(jìn)行混沌初始化。Tent 映射產(chǎn)生的種群會(huì)更均勻地分布在搜索空間，減小陷入局部最優(yōu)的概率，間接增強(qiáng)全局搜索能力，提高求解質(zhì)量和效率［23］。Tent映射的表達(dá)式如下：

經(jīng)伯努利位移變換后可得：

2.3 錦標(biāo)賽選擇策略

錦標(biāo)賽選擇策略是一個(gè)類似于比賽選拔的機(jī)制，隨機(jī)選取適應(yīng)度值優(yōu)秀的個(gè)體，不需要對(duì)所有的適應(yīng)度值進(jìn)行排序處理。這種策略不僅簡(jiǎn)單易行，而且計(jì)算復(fù)雜度低，可并行化處理，不易陷入局部最優(yōu)，具體選擇策略過(guò)程如圖2所示。

圖2 錦標(biāo)賽選擇策略的選擇Fig.2 Selection of tournament selection strategy

由圖2 可知，錦標(biāo)賽選擇策略簡(jiǎn)單直觀，它先從總體（種群個(gè)數(shù)為10）中隨機(jī)挑選一部分個(gè)體（挑選的個(gè)體數(shù)設(shè)置為5），使其進(jìn)行適應(yīng)度值的比較，選取其中最好的個(gè)體（F=3）進(jìn)入子代種群。反復(fù)進(jìn)行這個(gè)操作，直到子代種群的數(shù)量達(dá)到原來(lái)種群的數(shù)量，選擇結(jié)束［24］。本文利用該策略對(duì)斑點(diǎn)鬣狗種群個(gè)體適應(yīng)度值進(jìn)行選擇，具體步驟如下：

步驟1 首先確定每次選擇的斑點(diǎn)鬣狗個(gè)體數(shù)量。

步驟2 其次從種群中隨機(jī)選擇個(gè)體（每個(gè)個(gè)體入選概率相同）構(gòu)成組，根據(jù)每個(gè)個(gè)體的適應(yīng)度值，選擇組中適應(yīng)度值最好的斑點(diǎn)鬣狗個(gè)體進(jìn)入子代種群。

步驟3 重復(fù)步驟2，直到子代種群的數(shù)量達(dá)到原來(lái)種群的數(shù)量，得到的個(gè)體構(gòu)成新一代斑點(diǎn)鬣狗種群為止。

2.4 ADESHO算法

本文所提的ADESHO 算法首先進(jìn)行斑點(diǎn)鬣狗種群的混沌初始化，選擇種群的初始參數(shù)；其次計(jì)算斑點(diǎn)鬣狗種群每個(gè)個(gè)體的適應(yīng)度值，將斑點(diǎn)鬣狗種群進(jìn)行錦標(biāo)賽選擇；隨后依據(jù)收斂因子E的值判斷算法進(jìn)行全局搜索還是局部搜索。若|E|＜1，則使用ADE 算法進(jìn)行局部搜索，首先更新自適應(yīng)控制參數(shù)SF和CR，隨后進(jìn)行變異、交叉和選擇操作，計(jì)算每個(gè)新個(gè)體的適應(yīng)度。此時(shí)，若沒(méi)有達(dá)到算法終止條件，則繼續(xù)進(jìn)行錦標(biāo)賽選擇來(lái)產(chǎn)生下一代個(gè)體，判斷下一步進(jìn)行全局搜索還是局部搜索。若達(dá)到算法終止條件，則輸出最優(yōu)解，算法結(jié)束。若|E|＞1，則算法進(jìn)行全局搜索，按照式（8）、（9）來(lái)搜索斑點(diǎn)鬣狗新的組解，計(jì)算每個(gè)個(gè)體的適應(yīng)度值，判斷算法是否到達(dá)終止條件，輸出保留的最優(yōu)解，結(jié)束算法。ADESHO 算法的具體流程如圖3所示。

圖3 ADESHO算法流程Fig.3 Flowchart of ADESHO algorithm

3 ADESHO算法優(yōu)化SVM與特征選擇

3.1 搜索粒子設(shè)計(jì)

自適應(yīng)差分進(jìn)化斑點(diǎn)鬣狗優(yōu)化算法可以解決離散化問(wèn)題，對(duì)于特征選擇組合優(yōu)化類問(wèn)題時(shí)，需要將數(shù)據(jù)集中的特征改為二進(jìn)制字符串進(jìn)行實(shí)驗(yàn)。本文首先對(duì)特征進(jìn)行二進(jìn)制編碼，得到一個(gè)二進(jìn)制字符串，如果某一特征被選中，則對(duì)應(yīng)的二進(jìn)制位為“1”；否則對(duì)應(yīng)的二進(jìn)制位為“0”。在算法輸出結(jié)束時(shí)通過(guò)二進(jìn)制轉(zhuǎn)換機(jī)制進(jìn)行解碼輸出特征數(shù)目，實(shí)現(xiàn)SHO算法在特征組合優(yōu)化類問(wèn)題中的有效應(yīng)用。

支持向量機(jī)在構(gòu)建分類模型的時(shí)候，需要確定核函數(shù)參數(shù)γ和懲罰因子C。若依照所有特征訓(xùn)練模型，進(jìn)行參數(shù)優(yōu)化，再進(jìn)行特征選擇的流程，支持向量機(jī)所采用的關(guān)鍵特征在特征選擇中沒(méi)有被選擇，則訓(xùn)練模型結(jié)果不夠精確；若先進(jìn)行特征選擇，然后進(jìn)行參數(shù)挑選，訓(xùn)練模型的時(shí)間成本過(guò)大。鑒于以上兩種單獨(dú)計(jì)算優(yōu)化的不足，本文提出將SVM 的參數(shù)優(yōu)化和特征選擇同步進(jìn)行的方法，提高分類模型的精確性并極大降低時(shí)間計(jì)算的成本。每一個(gè)搜索個(gè)體搜索的維度包括兩部分：前部分為γ和C；后部分代表數(shù)據(jù)集特征的二進(jìn)制字符串，n為數(shù)據(jù)集中的特征個(gè)數(shù)［26］。粒子設(shè)計(jì)示意圖如圖4所示。

圖4 搜索粒子設(shè)計(jì)示意圖Fig.4 Schematic diagram of search particle design

3.2 適應(yīng)度函數(shù)

特征選擇可視為多個(gè)目標(biāo)優(yōu)化問(wèn)題，主要包括兩個(gè)相互矛盾目標(biāo)：分類準(zhǔn)確率與所選特征的個(gè)數(shù)。當(dāng)分類結(jié)果中分類準(zhǔn)確率較高，選擇特征個(gè)數(shù)較少時(shí)說(shuō)明所得分類效果優(yōu)秀。在算法迭代過(guò)程中，本文采用適應(yīng)度函數(shù)來(lái)評(píng)估每個(gè)解的質(zhì)量。ADESHO 算法與SVM 可平衡分類準(zhǔn)確率和所選特征個(gè)數(shù)這兩個(gè)指標(biāo)，因此，根據(jù)SVM 分類器所得到的解的分類準(zhǔn)確率與所選特征個(gè)數(shù)的關(guān)系［26］，設(shè)計(jì)適應(yīng)度函數(shù)如下：

式中：accuracy是指分類結(jié)果的正確率；R表示所選擇的特征個(gè)數(shù)；N表示該數(shù)據(jù)集擁有的總特征數(shù)；α與β分別表示分類精確性與所選特征的重要性［27］，且α+β=1，α屬于（0，1），本文α取0.99。

機(jī)器學(xué)習(xí)中通常將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集來(lái)檢驗(yàn)?zāi)Ｐ偷哪芰?，但這可能會(huì)導(dǎo)致訓(xùn)練出的模型效果差、泛化能力較弱等問(wèn)題，交叉驗(yàn)證法可以解決上述問(wèn)題［28］。K折交叉驗(yàn)證是將原始數(shù)據(jù)分為K份子集，其中K-1 份子集作為訓(xùn)練集，余下一份為測(cè)試集，重復(fù)此過(guò)程K次，得到K個(gè)結(jié)果，取其平均值作為模型的性能指標(biāo)。該方法可有效利用樣本數(shù)據(jù)，所得結(jié)果客觀、準(zhǔn)確，故本文利用K折交叉驗(yàn)證來(lái)保證模型的泛化能力（K=10）［28］。

3.3 ADESHO優(yōu)化SVM與特征選擇

基于以上兩處設(shè)計(jì)，本文所提ADESHO 算法同步優(yōu)化SVM與特征選擇的方法流程如下。

步驟1 預(yù)處理數(shù)據(jù)，LIBSVM函數(shù)輸入樣本數(shù)據(jù)集。

步驟2 將樣本數(shù)據(jù)每一個(gè)特征進(jìn)行二進(jìn)制編碼（數(shù)據(jù)歸一化后與0.5比較，若大于則記為1；否則記為0）。

步驟3 產(chǎn)生混沌初始化的斑點(diǎn)鬣狗種群；選擇初始化所需的參數(shù)（包括種群大小、搜索維度、最大迭代數(shù)目、隨機(jī)向量M、控制因子h、常值比例因子SF、交叉概率CR等）。

步驟4 初始化SVM 核參數(shù)γ及懲罰因子C，使用ADESHO算法對(duì)γ、C和二進(jìn)制編碼特征同時(shí)進(jìn)行搜索。

該客戶端主要針對(duì)消費(fèi)者進(jìn)行開(kāi)發(fā)，主要實(shí)現(xiàn)農(nóng)產(chǎn)品從生產(chǎn)到銷售各個(gè)階段的實(shí)時(shí)溯源信息的查詢和展示工作，通過(guò)掃碼進(jìn)行信息的自動(dòng)查詢。主要的界面如下圖所示：

步驟5 將搜索后的樣本二進(jìn)制特征進(jìn)行解碼，二進(jìn)制碼為“1”的特征從數(shù)據(jù)集中挑選出來(lái)。

步驟6 將數(shù)據(jù)集中選出的特征和γ、C一起輸入SVM 分類器中進(jìn)行分類測(cè)試，交叉拆分樣本集，采用10 折交叉驗(yàn)證方法訓(xùn)練SVM 分類器來(lái)計(jì)算適應(yīng)度值（式（18）），若有比當(dāng)前最優(yōu)解更好的解，則更新最優(yōu)解。

步驟7 判斷是否滿足終止條件，若滿足則停止優(yōu)化并保存當(dāng)前最優(yōu)解，否則返回步驟5。

步驟8 輸出并保存最優(yōu)解（γ、C、最優(yōu)特征子集及分類準(zhǔn)確率），結(jié)束算法流程。

4 實(shí)驗(yàn)與分析

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

為了驗(yàn)證ADESHO 算法優(yōu)化SVM 與特征選擇的有效性，本文采用UCI［29］數(shù)據(jù)庫(kù)中經(jīng)典數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)共分3 部分：第1 部分為本文算法與標(biāo)準(zhǔn)SHO、傳統(tǒng)SVM 算法［26］進(jìn)行特征選擇對(duì)比實(shí)驗(yàn)；第2 部分為本文算法與其他四種元啟發(fā)式優(yōu)化算法［14-17］的特征選擇對(duì)比實(shí)驗(yàn)；第3部分為本文算法與同類改進(jìn)算法研究的橫向?qū)Ρ葘?shí)驗(yàn)。實(shí)驗(yàn)所涉及8 個(gè)數(shù)據(jù)集信息列于表1，所有對(duì)比算法參數(shù)列于表2，其來(lái)源于文獻(xiàn)［14-17］、［19］、［21］及［25］。

表1 UCI數(shù)據(jù)集的詳細(xì)信息Tab.1 Details of UCI datasets

表2 所有對(duì)比算法實(shí)驗(yàn)參數(shù)Tab.2 Experimental parameters of all comparison algorithms

在原始數(shù)據(jù)集中，數(shù)據(jù)類型及大小參差不齊會(huì)影響SVM的分類效果，因此在進(jìn)行特征選擇仿真實(shí)驗(yàn)之前，數(shù)據(jù)集需預(yù)處理。本文首先將字符串類型的特征轉(zhuǎn)化為數(shù)值型特征，其次為平衡所有特征屬性的選擇可能，利用數(shù)值歸一化［26］公式將所有數(shù)值均歸一化到［0，1］內(nèi)，如下所示：

式中：X表示原始數(shù)據(jù)，Xnorm表示歸一化后的數(shù)據(jù)，Xmin和Xmax分別代表此特征取值范圍的最小值和最大值。

實(shí)驗(yàn)仿真環(huán)境為Windows 7 系統(tǒng)，微處理器主頻為3.30 GHz，仿真軟件為Matlab 2016a，采用LIBSVM 工具箱。種群大小與最大迭代數(shù)設(shè)為30 與100，每種算法在每個(gè)數(shù)據(jù)集上進(jìn)行30次實(shí)驗(yàn)，取平均值作為最終結(jié)果。

為驗(yàn)證優(yōu)化算法性能，本文選取如下幾種性能指標(biāo)［21］進(jìn)行評(píng)估（指標(biāo)公式中M均為算法運(yùn)行次數(shù)）：

式中：TP（True Positive）表示分類結(jié)果為真陽(yáng)性；FP（False Positive）代表分類結(jié)果為假陽(yáng)性；FN（False Negative）表示分類結(jié)果為假陰性。

平均分類準(zhǔn)確率 是運(yùn)行M次算法后所得分類結(jié)果的平均正確率，公式如下：

式中Accuracy(i)為算法第i次運(yùn)行后的分類正確率。

平均選擇特征個(gè)數(shù) 指M次算法運(yùn)行后所選擇特征個(gè)數(shù)的平均值，計(jì)算如下：

式中Size(i)為算法第i次運(yùn)行后所選擇特征的個(gè)數(shù)。

適應(yīng)度值 表示分類準(zhǔn)確率和選擇特征數(shù)目的綜合評(píng)價(jià)指標(biāo)，也是訓(xùn)練特征選擇模型時(shí)的標(biāo)準(zhǔn)，計(jì)算公式與式（18）相同，取其平均值與標(biāo)準(zhǔn)差來(lái)評(píng)價(jià)算法性能，如下：

式中fitness(i)為算法第i次運(yùn)行中的適應(yīng)度值。

平均運(yùn)行時(shí)間M次算法運(yùn)行所需的平均時(shí)間，如下：

式中Runtime(i)為算法第i次運(yùn)行所需時(shí)間。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 標(biāo)準(zhǔn)SHO、傳統(tǒng)SVM與本文算法的特征選擇對(duì)比

為驗(yàn)證本文算法在特征選擇中的有效性，本節(jié)將本文算法與標(biāo)準(zhǔn)SHO、傳統(tǒng)SVM 算法作為選擇特征子集的方法，進(jìn)行特征選擇的實(shí)驗(yàn)對(duì)比。傳統(tǒng)SVM 算法對(duì)數(shù)據(jù)分類使用的是網(wǎng)格搜索法［26］，尋找最優(yōu)的核參數(shù)和懲罰因子，然后進(jìn)行特征選擇。

圖5 為本文算法與原SHO、傳統(tǒng)SVM 算法在二分類數(shù)據(jù)集中特征選擇所獲得的F1值，結(jié)果表明ADESHO 算法的搜索效果良好，改進(jìn)有效。

圖5 本文算法與原算法特征選擇后的F1值對(duì)比Fig.5 Comparison of F1-score between the proposed and original algorithms after feature selection

表3為本文算法、標(biāo)準(zhǔn)SHO、傳統(tǒng)SVM 算法特征選擇后的平均分類準(zhǔn)確率與所選特征平均數(shù)，在平均分類準(zhǔn)確率上，本文算法在全部數(shù)據(jù)集中均具有最高分類準(zhǔn)確率，證明本文算法能夠更準(zhǔn)確地對(duì)數(shù)據(jù)進(jìn)行分類；在所選特征平均數(shù)上，ADESHO 算法能夠在多數(shù)數(shù)據(jù)集中選取更少的特征，較標(biāo)準(zhǔn)SHO與傳統(tǒng)SVM的網(wǎng)格搜索算法更適合特征選擇。

表3 本文算法與原算法的平均分類準(zhǔn)確率和所選特征平均數(shù)測(cè)試結(jié)果Tab.3 Test results of average classification accuracy and average number of selected features of the proposed and original algorithms

基于本文算法與標(biāo)準(zhǔn)SHO、傳統(tǒng)SVM 算法特征選擇的適應(yīng)度值與平均運(yùn)行時(shí)間如表4 所示。從適應(yīng)度值上可知，雖部分?jǐn)?shù)據(jù)特征選擇不夠穩(wěn)定，但在平均適應(yīng)度值中，本文算法效果良好，相對(duì)穩(wěn)定，證明本文改進(jìn)方法有效；在算法的平均運(yùn)行時(shí)間上，本文所提算法計(jì)算效率一般，不及標(biāo)準(zhǔn)SHO 算法，但卻優(yōu)于傳統(tǒng)網(wǎng)格搜索SVM 最優(yōu)參數(shù)后特征選擇的方法，故本文改進(jìn)依舊有效。綜上所述，在特征選擇問(wèn)題上，ADESHO 的同步優(yōu)化方法在各方面均優(yōu)于標(biāo)準(zhǔn)SHO、傳統(tǒng)優(yōu)化SVM 的網(wǎng)格搜索算法，故本文后續(xù)將使用ADESHO 方法與其他優(yōu)化算法進(jìn)行特征選擇對(duì)比實(shí)驗(yàn)。

表4 本文算法與原算法的適應(yīng)度值和平均運(yùn)行時(shí)間測(cè)試結(jié)果Tab.4 Test results of fitness value and average running time of the proposed and original algorithms

4.2.2 本文算法與其他算法的特征選擇對(duì)比

前一節(jié)已證明本文算法特征選擇效果顯著優(yōu)于標(biāo)準(zhǔn)SHO與傳統(tǒng)SVM 算法，為進(jìn)一步證明本文算法在特征選擇中的優(yōu)越性，本節(jié)將所提算法與其他四種元啟發(fā)式優(yōu)化算法進(jìn)行特征選擇實(shí)驗(yàn)對(duì)比。圖6展示了ADESHO 算法與其他四種優(yōu)化算法在4 個(gè)二分類數(shù)據(jù)集中的F1值，雖未在全部數(shù)據(jù)集中效果最佳，但本文算法仍在空間搜索與優(yōu)化中表現(xiàn)良好；基于本文所提算法與其他四種優(yōu)化算法在平均分類準(zhǔn)確率和所選特征平均數(shù)上的仿真測(cè)試結(jié)果如圖7～8所示，實(shí)驗(yàn)結(jié)果表明：在平均分類準(zhǔn)確率上，本文算法在6 個(gè)數(shù)據(jù)集中平均分類準(zhǔn)確率均最高，平均提高了3 個(gè)百分點(diǎn)，數(shù)據(jù)分類效果優(yōu)于其他四種算法；在所選特征的平均數(shù)上，本文算法在6 個(gè)數(shù)據(jù)集中所選特征子集數(shù)目平均值均最少，平均減少了2.7 個(gè)特征，相較于其他算法，本文算法有效地降低了數(shù)據(jù)維度。

圖6 本文算法與其他優(yōu)化算法的F1值對(duì)比Fig.6 Comparison of F1-score between the proposed and other optimization algorithms

圖7 本文算法與其他優(yōu)化算法的平均分類準(zhǔn)確率對(duì)比Fig.7 Comparison of average classification accuracy between the proposed and other optimization algorithms

基于本文算法與其他四種算法特征選擇時(shí)的適應(yīng)度值如表5 所示，在適應(yīng)度平均值上，ADESHO 算法未在全部數(shù)據(jù)集中表現(xiàn)最優(yōu)，但與其他算法對(duì)比，本文所提算法在多數(shù)數(shù)據(jù)集中表現(xiàn)良好；在適應(yīng)度標(biāo)準(zhǔn)差上，GWO 算法具有一定的競(jìng)爭(zhēng)性，但本文算法仍在半數(shù)數(shù)據(jù)集中具有相對(duì)穩(wěn)定的優(yōu)化性能，因此，從適應(yīng)度值上來(lái)看，本文算法在特征選擇中更好地平衡了準(zhǔn)確率與特征數(shù)目?jī)烧叩拿埽瑫r(shí)具有良好的穩(wěn)定性。

表5 ADESHO與其他優(yōu)化算法的適應(yīng)度值測(cè)試結(jié)果Tab.5 Test results of fitness value of ADESHO and other optimization algorithms

圖8 本文算法與其他優(yōu)化算法的所選特征平均數(shù)對(duì)比Fig.8 Comparison of average number of selected features between the proposed and other optimization algorithms

圖9 為本文算法與其他四種算法特征選擇的平均運(yùn)行時(shí)間，測(cè)試結(jié)果表明：GWO 算法用時(shí)較少，而本文算法用于特征選擇時(shí)計(jì)算效率一般，無(wú)明顯優(yōu)勢(shì)，仍需加以改進(jìn)。綜上所述，本文所提出的ADESHO 算法具有優(yōu)秀的搜索能力與求解精度，尤其在特征選擇中表現(xiàn)出明顯的優(yōu)勢(shì)。

圖9 本文算法與其他優(yōu)化算法的平均運(yùn)行時(shí)間對(duì)比Fig.9 Comparison of average running time between the proposed and other optimization algorithms

4.2.3 本文算法與同類改進(jìn)算法的特征選擇對(duì)比

為全面綜合驗(yàn)證本文算法在特征選擇應(yīng)用中的有效性與優(yōu)越性，本節(jié)對(duì)同類混合改進(jìn)優(yōu)化算法SHOSA 算法與MSDEA 進(jìn)行橫向?qū)Ρ鹊奶卣鬟x擇實(shí)驗(yàn)研究。在圖10 中，展示了本文算法與其他兩種同類改進(jìn)算法在4 個(gè)二分類數(shù)據(jù)集中的F1值結(jié)果。數(shù)據(jù)表明，本文算法較其他同類改進(jìn)算法特征選擇時(shí)具有更好的分類效果；圖11～12 分別為ADESHO 與SHOSA、MSDEA 特征選擇平均分類準(zhǔn)確率與所選特征平均數(shù)，數(shù)據(jù)結(jié)果表明ADESHO 算法在多數(shù)數(shù)據(jù)集中可以準(zhǔn)確分類并有效降低子集特征數(shù)目，優(yōu)化特征選擇的能力仍優(yōu)于其他同類改進(jìn)算法。

圖10 ADESHO算法與其他同類改進(jìn)算法的F1值對(duì)比Fig.10 Comparison of F1-score between ADESHO algorithm and other similar improved algorithms

圖11 ADESHO與同類改進(jìn)算法的平均分類準(zhǔn)確率對(duì)比Fig.11 Comparison of average classification accuracy between ADESHO and similar improved algorithms

表6 為本文算法與SHOSA、MSDEA 在適應(yīng)度值及平均運(yùn)行時(shí)間上的對(duì)比結(jié)果，從表中可以看出，雖然MSDEA 的適應(yīng)度標(biāo)準(zhǔn)差與SHOSA 的適用度平均值部分表現(xiàn)優(yōu)于本文方法，但整體上ADESHO 仍較其他兩種改進(jìn)算法在特征選擇中效果顯著。而對(duì)于平均運(yùn)行時(shí)間而言，本文算法與另外兩種改進(jìn)的混合算法表現(xiàn)均不夠良好，因?qū)煞N算法進(jìn)行混合操作，在每個(gè)粒子進(jìn)行搜索計(jì)算最優(yōu)解時(shí)，時(shí)間復(fù)雜度隨著兩種算法的迭代次數(shù)與搜索維度增加而變高，因此將兩種算法進(jìn)行混合優(yōu)化時(shí)會(huì)產(chǎn)生時(shí)間復(fù)雜度變高的弊端，如何能夠在混合優(yōu)化能力增強(qiáng)的同時(shí)降低算法的時(shí)間復(fù)雜度將是未來(lái)混合優(yōu)化中一項(xiàng)極具挑戰(zhàn)的研究工作。

表6 ADESHO與同類改進(jìn)算法適應(yīng)度值及平均運(yùn)行時(shí)間的測(cè)試結(jié)果Tab.6 Test results of fitness value and average running time between ADESHO and similar improved algorithms

圖12 ADESHO與同類改進(jìn)算法的所選特征平均數(shù)對(duì)比Fig.12 Comparison of average number of selected features between ADESHO and similar improved algorithms

5 結(jié)語(yǔ)

針對(duì)機(jī)器學(xué)習(xí)中封裝式特征選擇的分類問(wèn)題，本文提出一種自適應(yīng)差分進(jìn)化斑點(diǎn)鬣狗優(yōu)化算法，并將其應(yīng)用于特征選擇與SVM 參數(shù)選取的同步優(yōu)化中。通過(guò)UCI中8個(gè)數(shù)據(jù)集的分類仿真實(shí)驗(yàn)來(lái)評(píng)估本文算法的優(yōu)化性能，與標(biāo)準(zhǔn)SHO、傳統(tǒng)SVM 網(wǎng)格搜索尋優(yōu)、PSO、CS、GWO、WOA 及同類改進(jìn)混合SHOSA、MSDEA 進(jìn)行對(duì)比分析，實(shí)驗(yàn)結(jié)果表明，ADESHO 算法能夠有效降低所選特征數(shù)目并提高數(shù)據(jù)分類準(zhǔn)確率，優(yōu)于原算法與其他優(yōu)化算法的特征選擇能力，同時(shí)本文算法具有更好、更穩(wěn)定的適應(yīng)度值，證明了ADESHO 算法適合解決封裝式特征選擇問(wèn)題。在運(yùn)行時(shí)間上，本文算法改善效果不夠顯著，因此在未來(lái)的研究中仍需做進(jìn)一步的改進(jìn)。