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

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

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

0 引言

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

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

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

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

1 相關(guān)算法

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

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

1）包圍過程。

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

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

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

2）狩獵過程。

斑點鬣狗依靠信任等級制度來進行分組捕殺。在種群中定義最佳搜索個體，其他斑點鬣狗搜索個體將朝著最佳搜索個體聚集，并組成最佳搜索組。因此該行為具體定義為：

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

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

3）攻擊過程（局部搜索）。

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

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

4）搜索過程（全局探索）。

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

1.2 差分進化算法

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

1）變異算子。

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

2）交叉算子。

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

3）選擇算子。

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

2 改進斑點鬣狗優(yōu)化算法

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

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

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

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

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

2.2 混沌初始化策略

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

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

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

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

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

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

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

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

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

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

2.4 ADESHO算法

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

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

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

3.1 搜索粒子設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟6 將數(shù)據(jù)集中選出的特征和γ、C一起輸入SVM 分類器中進行分類測試，交叉拆分樣本集，采用10 折交叉驗證方法訓(xùn)練SVM 分類器來計算適應(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 實驗與分析

4.1 實驗設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

平均運行時間M次算法運行所需的平均時間，如下：

式中Runtime(i)為算法第i次運行所需時間。

4.2 實驗結(jié)果與分析

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

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

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

圖5 本文算法與原算法特征選擇后的F1值對比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)確地對數(shù)據(jù)進行分類；在所選特征平均數(shù)上，ADESHO 算法能夠在多數(shù)數(shù)據(jù)集中選取更少的特征，較標(biāo)準(zhǔn)SHO與傳統(tǒng)SVM的網(wǎng)格搜索算法更適合特征選擇。

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

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

4.2.2 本文算法與其他算法的特征選擇對比

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

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

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

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

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

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

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

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

4.2.3 本文算法與同類改進算法的特征選擇對比

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

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

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

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

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

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

5 結(jié)語

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