賈鶴鳴,姜子超,李 瑤,孫康健
(1.三明學(xué)院信息工程學(xué)院,福建三明 365004;2.東北林業(yè)大學(xué)機電工程學(xué)院,哈爾濱 150040)
(*通信作者電子郵箱jiaheminglucky99@126.com)
隨著各領(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),提高全局搜索精度,在解決封裝式特征選擇問題時效果顯著。
標(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)離,再次尋找和攻擊獵物,從而進行全局搜索。
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ù)。
標(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ù)雜性問題時的不足。
據(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)定性。
在群智能算法中,種群初始化方法決定了全局搜索的質(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)伯努利位移變換后可得:
錦標(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)成新一代斑點鬣狗種群為止。
本文所提的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
自適應(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
特征選擇可視為多個目標(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)P偷哪芰?,但這可能會導(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]。
基于以上兩處設(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é)束算法流程。
為了驗證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.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
針對機器學(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 算法適合解決封裝式特征選擇問題。在運行時間上,本文算法改善效果不夠顯著,因此在未來的研究中仍需做進一步的改進。