王立威童林*鄒圓

（1六盤水師范學(xué)院物理與電氣工程學(xué)院，貴州 六盤水 553004；2重慶工商大學(xué)經(jīng)濟學(xué)院，重慶 南岸 400067）

近年來，數(shù)據(jù)分類已經(jīng)成為機器學(xué)習(xí)領(lǐng)域最重要的研究問題之一，隨著研究人員對數(shù)據(jù)分類任務(wù)的精細(xì)化要求不斷提高，在機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域產(chǎn)生了海量的具有不同特征種類的分類數(shù)據(jù)集，這些高維數(shù)據(jù)通常包含大量冗余的特征。特征選擇是在去除不相關(guān)、冗余、有噪聲特征的同時，從原始特征中提取重要特征，實現(xiàn)降維的過程。數(shù)據(jù)特征選擇問題被認(rèn)為是組合優(yōu)化問題[1]，與解決組合優(yōu)化問題方法類似，研究人員通過引入各種啟發(fā)式算法用來尋找數(shù)據(jù)特征選擇問題可接受的解，包括粒子群優(yōu)化算法（Particle swarm algorithm，PSO）[2]、遺傳優(yōu)化算法 （Genetic algorithm，GA）[3]、灰狼優(yōu)化算法[4]、蜻蜓優(yōu)化算法[5]、煙花優(yōu)化算法[6]等，但無論以何種策略建立優(yōu)化算法，仍存在著搜索精度低及易早熟收斂等共性問題[7]，該類問題極大地影響了優(yōu)化算法在數(shù)據(jù)特征選擇上的效果和分類精度。樽海鞘群算法（Salp swarm algorithm,SSA）[8]自2017年被提出以來，該算法就以其參數(shù)少、結(jié)構(gòu)簡單和易實現(xiàn)的優(yōu)點，被得到廣泛應(yīng)用，如多目標(biāo)電力負(fù)荷分配問題[9]、離散域中的任務(wù)分配問題[10]等，但SSA依然存在著陷入局部最優(yōu)和精度低的問題。在SSA改進研究中，文獻[11]提出一種多子群共生非均勻高斯變異的SSA算法，算法尋優(yōu)效果得到改進，但研究者并未將其用于解決數(shù)據(jù)特征選擇或其他實際工程問題。文獻[12]通過在SSA算法中引入正弦余弦因子和干擾算子并用來解決特征選擇問題，文獻[13]將動態(tài)時變策略和優(yōu)勝劣汰解決方案集成在SSA算法中應(yīng)用在機器學(xué)習(xí)中數(shù)據(jù)集的特征選擇中，文獻[14]提出了基于混沌映射的SSA算法。雖然上述改進策略提高了SSA算法的優(yōu)化性能，但仍存在一些問題，包括算法更新方式單一、搜索位置有限、求解高維優(yōu)化問題性能較差等問題。

針對上述問題，本文通過在SSA算法中引入量子計算，使得SSA算法量子化，有機結(jié)合Cauchy變異操作，得到具有量子行為的改進樽海鞘群算法（Quantum Salp swarm algorithm，QSSA），改進后的算法增加了更新方式，擴大了搜索位置，具有量子計算和SSA算法的高性能和高精度優(yōu)勢，增強了算法的高維問題尋優(yōu)能力。最后，將QSSA算法應(yīng)用近鄰（K-Nearest Neighbor，KNN）分類器進行數(shù)據(jù)分類，構(gòu)造基于QSSA的特征選擇算法，與其他算法進行對比進一步驗證該算法的有效性。

1 問題描述和求解框架

數(shù)據(jù)特征選擇問題要求實現(xiàn)所選特征數(shù)量最少、分類精度最高，能夠滿足這兩個條件的數(shù)據(jù)子集為數(shù)據(jù)選擇的最佳解決方案，在實際過程中，其二者相互矛盾，為取得二者間的平衡，文獻[14]定義適應(yīng)度函數(shù)為

式中，NF為選擇出的特征子集的大小，acc是輸入為NF子集情況下的分類精度，NT是全部特征的數(shù)量，是平衡控制分類精度和特征選擇數(shù)量的常數(shù)。通過求解式（1）所示的函數(shù)極小值問題可以實現(xiàn)在所選特征子集NF數(shù)量最少的情況下實現(xiàn)分類精度acc最高，當(dāng)數(shù)據(jù)特征維度較高時，特征子集NF選擇難度較大。

為了求解上述非線性、多約束的高維數(shù)據(jù)特征選取難題，提出了基于QSSA的特征選擇算法，具體求解框架如圖1所示。

圖1 基于QSSA的特征選擇算法框架

由圖1可知，框架使用QSSA算法進行特征選擇包含兩個主要模塊：特征選擇模塊和分類模塊。首先，以原始數(shù)據(jù)集的全部特征為輸入，然后使用QSSA算法確定有價值的特征，考慮到KNN分類器簡單易于實現(xiàn)，僅對樣本之間的距離進行分類，將產(chǎn)生的特征用于輸入KNN分類器，根據(jù)適應(yīng)度函數(shù)平衡特征數(shù)量和分類精度，最后評估結(jié)果。

2 求解算法

2.1 標(biāo)準(zhǔn)樽海鞘群算法

樽海鞘群中領(lǐng)導(dǎo)者覓食行為的數(shù)學(xué)模型可由公式（2）表示

2.2 動態(tài)對立學(xué)習(xí)

SSA算法在首次迭代之前，需要選取一組隨機的值用來初始化種群個體，由于可行解范圍較大，存在初始化位置選擇盲目的問題。改善初始種群的位置可以增加算法收斂速度，基于對立的學(xué)習(xí)(Opposition-based Learning，OBL)已被廣泛用于各種智能算法初始學(xué)習(xí)階段，增強算法的搜索能力[15]，其核心思想是通過計算當(dāng)前值及其對應(yīng)的對立值來尋求更好的候選解決方案[16]。對立學(xué)習(xí)具體定義為

將對立學(xué)習(xí)進一步拓展到高維，公式如（6）所示

式中，ubj和lbj為j維可行解的上下界。為了進一步增強OBL策略，在對立學(xué)習(xí)的基礎(chǔ)上添加隨機因子改進為動態(tài)對立學(xué)習(xí)（Dynamic Opposition-based Learning，DOBL），然后將動態(tài)對立學(xué)習(xí)引入到算法的種群初始化中，大大增加種群的多樣性，動態(tài)對立學(xué)習(xí)定義如下

2.3 量子樽海鞘群算法

通過量子位置的不斷更新，實現(xiàn)了QSSA算法中的整個量子樽海鞘群的演進。

搜索過程中，第i只量子樽海鞘搜索到的最好位置(即局部最優(yōu)位置)表示為Pi=(Pi1,Pi2,…,pij)(i=1,2,…,h)，整個量子樽海鞘群所搜索到的全局最優(yōu)位置（所有局部最優(yōu)位置中的最優(yōu)位置）表示為Pg=(Pg1,Pg2,…,pgl)。在每次循環(huán)中，第i只量子樽海鞘的第j維量子位的量子演進表示如下

式中，i=1,2,…,h;j=1,2,…,D,e1和e2是2個影響因子，分別決定局部最優(yōu)位置和全局最優(yōu)位置對量子旋轉(zhuǎn)角的影響程度，t為迭代次數(shù)。通過以上操作得到了量子樽海鞘群算法。

2.4 Cauchy變異

考慮到跟隨者群體會陷入局部最優(yōu)影響算法精度，在算法搜索后半段，引入Cauchy算子作為變異步長，具體公式如下

式中各項具體含義見式（4），需要說明的是Cauchy是Cauchy算子，其標(biāo)準(zhǔn)分布概率密度函數(shù)公式如下

相比高斯分布，Cauchy分布具有較長的“尾巴”，可使跟隨者群體具有更高概率跳到更優(yōu)位置，同時，中心點較小的峰值表明Cauchy算子搜索領(lǐng)域空間的時間花費更少[18]。通過在SSA算法加入變異策略能降低算法陷入局部最優(yōu)的概率。

2.5 QSSA算法步驟

本文的改進算法是在SSA的基礎(chǔ)上，增加了動態(tài)對立學(xué)習(xí)，增強算法的搜索能力，提升算法收斂速度；引入Cauchy算子，解決SSA算法中跟隨者群體會陷入局部最優(yōu)的問題；采用量子遺傳算法進一步尋優(yōu)，使算法尋優(yōu)值更能接近最優(yōu)值。QSSA偽代碼如算法1所示。

計算樽海鞘對立位置和適應(yīng)度值。//根據(jù)文章中的公式（7）

計算樽海鞘量子位置和計算當(dāng)前適應(yīng)度值。//并根據(jù)文章公式（9）（10）

2.6 算法復(fù)雜度分析和數(shù)值試驗

2.6.1算法復(fù)雜度分析

本文所提的QSSA主要是由對立學(xué)習(xí)種群初始化、Cauchy變異和量子優(yōu)化組成。迭代次數(shù)為T，當(dāng)種群數(shù)目為N，優(yōu)化問題的維度為D，二進制位數(shù)為M的時候，對立學(xué)習(xí)種群初始化的計算復(fù)雜度為O(ND)；在柯西變異環(huán)節(jié)，計算復(fù)雜度為O(ND)；在量子優(yōu)化環(huán)節(jié)，計算復(fù)雜度為O(NDM)。對改進的樽海鞘群算法，每一次迭代過程中，算法的計算復(fù)雜度為O(2ND+NDM)，因此，算法總計算復(fù)雜度為T(n)=O(T(2ND+NDM))

2.6.2 數(shù)值試驗

為了驗證QSSA有效性，選取文獻[11]提出的MSNSSA與其它幾種常見算法模型如粒子群算法（PSO）[19]，正余弦算法 （SCA）[20]、蝴蝶優(yōu)化算法（BOA）[21]和飛蛾火焰算法（MFO）[22]進行實驗對比，為遵循實驗公平性，實驗對比過程中，列出的測試函數(shù)中種群數(shù)量、函數(shù)維度、迭代次數(shù)、獨立運行次數(shù)等基本實驗參數(shù)和對比算法中的各項參數(shù)均與文獻[11]保持一致。針對常見的10個測試函數(shù)最優(yōu)問題，不同算法的尋優(yōu)結(jié)果如表1所示。

表1 算法性能對比

由表1的結(jié)果可知，除Quartic函數(shù)，QSSA算法在求解函數(shù)最優(yōu)問題時表現(xiàn)出的效果最好。在Quartic測試函數(shù)的最優(yōu)值為6.9674e-4，QSSA與BOA、MSNSSA求解精度差距較小，在其余函數(shù)上，QSSA表現(xiàn)出了更高的精度，相比于SSA算法，求解精度提升較大，特別是在Sphere、Schwefel 1.2和Schwefel 2.21函數(shù)上，其收斂精度遠超于其他算法，具備更優(yōu)秀的收斂能力。由于多峰函數(shù)求解相對困難，所列算法求解精度均相對較低，QSSA算法依然展現(xiàn)出了良好的搜索能力，與MSNSSA和相差較小，說明對立學(xué)習(xí)和柯西變異操作有利于SSA算法跳出局部最優(yōu)值，并采用量子遺傳作精細(xì)調(diào)整，找到全局最優(yōu)值。綜上，QSSA算法能夠較好地求解函數(shù)優(yōu)化問題，與其他算法相比，具備較好的綜合求解能力。

2.7 基于QSSA的特征選擇算法步驟

將QSSA算法應(yīng)用KNN分類器進行數(shù)據(jù)分類，構(gòu)造基于QSSA的特征選擇算法，步驟如下：

步驟1：設(shè)定數(shù)據(jù)集中的特征向量分別對應(yīng)QSSA算法種群，加載數(shù)據(jù)集并隨機初始化量子樽海鞘種群；

步驟2：計算QSSA算法種群適應(yīng)度，初始的最佳適應(yīng)度函數(shù)fitness設(shè)置為食物源位置(foodfitness)；

步驟3：利用算法1中的主函數(shù)對SSA個體進行更新，并結(jié)合KNN分類器和式（1）計算fitness；

步驟4：按如下方法更新fitness；

步驟5：重復(fù)第三步和第四步，直到滿足迭代次數(shù)要求；

步驟6：返回量子樽海鞘種群最佳位置；并將包含全部特征NT中的識別特征子集NF作為選擇特征子集再次送入KNN分類器進行模型綜合評估。

3 實驗對比

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

為了驗證算法的有效性，采用加州大學(xué)歐文分校（University of CaliforniaIrvine，UCI）機器學(xué)習(xí)數(shù)據(jù)庫中經(jīng)典的數(shù)據(jù)集對模型進行評估。數(shù)據(jù)集編號（data set ID，DS ID）及其簡要說明，所選數(shù)據(jù)集擁有從6擴展到90的各種特征如表2所示。

表2 UCI機器學(xué)習(xí)數(shù)據(jù)集

數(shù)據(jù)集的類別（從2到15）和實例（從47到5 000）的數(shù)量也各不相同。

實驗中文獻[14]所提算法、PSO和GA對比數(shù)據(jù)引自文獻[14]，為遵循實驗公平性，各項設(shè)置參數(shù)保持一致如表3所示。

表3 實驗參數(shù)設(shè)置

3.2 算法性能對比與分析

該實驗的基本目標(biāo)是評估具有算法的性能。為了將QSSA、文獻[14]所提改進的SSA算法、標(biāo)準(zhǔn)SSA算法和遺傳算法（Genetic algorithm，GA）及粒子群算法（Particle swarm algorithm，PSO）進行全面比較，分別給出了最佳及平均適應(yīng)度值，最優(yōu)值均以粗體顯示，如表4、表5所示。

表4 20次運行的中最佳適應(yīng)度

表5 20次運行的平均適應(yīng)度

通過表4和表5可以看到，經(jīng)過20次程序運行后，在大多數(shù)情況下，具有QSSA的性能優(yōu)于標(biāo)準(zhǔn)SSA和其他算法。其中，QSSA算法在7個數(shù)據(jù)集(D1、D3、D5、D6、D7、D8、D9)表現(xiàn)出最佳適應(yīng)度，在6個數(shù)據(jù)集(D1、D3、D5、D6、D7、D8)中平均適應(yīng)度最佳，效果優(yōu)于文獻[14]提出的算法，文獻[14]所提算法分別從三個數(shù)據(jù)集中取得最佳適應(yīng)度和最優(yōu)平均適應(yīng)度，效果優(yōu)于其他三種算法。最佳適應(yīng)度反應(yīng)算法能夠達到的最佳精度，而平均適應(yīng)度反應(yīng)算法的穩(wěn)定性，與其他算法相比，QSSA算法在適應(yīng)度尋優(yōu)上具有優(yōu)勢，但適應(yīng)度僅綜合反映了特征選擇求解情況，無法具體表現(xiàn)出分類正確率和特征選擇數(shù)量，因此，還需要對準(zhǔn)確率和尋找的特征子集數(shù)量進行對比。程序運行20次后的分類正確率和特征選擇子集數(shù)量如表6和表7所示。

表6 20次運行的分類正確率（%）

表7 運行20次程序的平均特征選擇數(shù)

注：粗體表示分類正確率，正確率最高。

首先，通過表6可知，QSSA算法在7個數(shù)據(jù)集（D1、D4、D5、D6、D7、D8、D9）中獲得了最佳分類精度，文獻[14]所提算法在三個數(shù)據(jù)集中獲得了最佳分類精度；其次，在表7中看到QSSA和文獻[14]所提算法分別在4個數(shù)據(jù)集中尋找的特征子集數(shù)量最少，GA算法在2個數(shù)據(jù)集中特征子集最少?？芍猀SSA在一定程度犧牲了特征選擇數(shù)量換取更高的分類精度，如在D5數(shù)據(jù)集中，QSSA獲取了特征子集數(shù)量雖然達到了14.2，大大高于GA算法求得的3.4，分類正確率提高了11.67%，這種能力更加適合對分類精度要求較高的場景。如果更加注重特征數(shù)量最少，可以通過調(diào)節(jié)參數(shù)來改變該部分在整體適應(yīng)度函數(shù)中的比重。

綜上，QSSA算法分類精度和特征選擇能力能夠得到有效平衡，具有較好的特征選擇能力。

4 結(jié)論

本文提出一種用于數(shù)據(jù)特征選擇的量子樽海鞘群算法，考慮到數(shù)據(jù)特征選擇是一種高維的組合優(yōu)化問題，設(shè)計了量子樽海鞘群算法來求解這一非線性、復(fù)雜的優(yōu)化問題，設(shè)計的算法結(jié)合了量子計算的優(yōu)勢和樽海鞘群生物優(yōu)化機制的優(yōu)勢，得到以下結(jié)論：

第一，相比其他智能優(yōu)化算法，量子樽海鞘群算法所尋函數(shù)最優(yōu)解精度更高，對于工程優(yōu)化問題具有較好的移植性。

第二，針對不同種類的數(shù)據(jù)特性選擇問題，所提方法能夠在保證數(shù)據(jù)分類進度的情況下有效減少數(shù)據(jù)的特征數(shù)據(jù)，能夠為機器學(xué)習(xí)提供一種有效的數(shù)據(jù)特征選擇方法，降低數(shù)據(jù)冗余。

未來將進一步把算法推廣到具體的工程優(yōu)化問題求解上。