基于BSO-OS算法的兩階高維數(shù)據(jù)特征選擇

田浩楠，周 暉

(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院，江蘇 南通 226019)

0 引 言

隨著云計算和大數(shù)據(jù)的迅速發(fā)展，海量數(shù)據(jù)不斷呈現(xiàn)，數(shù)據(jù)維度不斷增加[1]。特征選擇從給定特征集合中選取相關(guān)特征子集，以降低數(shù)據(jù)維度、簡化學(xué)習(xí)模型、加速學(xué)習(xí)過程[2,3]。

高維數(shù)據(jù)的搜索空間遠大于一般數(shù)據(jù)，其特征選擇非常困難[4]。群集智能(swarm intelligence, SI)搜索能力強、魯棒性好，而被應(yīng)用于高維數(shù)據(jù)特征選擇。文獻[5,6]將位置更新與變異機制以及模糊規(guī)則引入二進制PSO(binary particle swarm optimization, BPSO)算法以搜索特征子集。文獻[7]采用PSO算法搜索特征子集，該算法引入新的局部搜索機制和重置gbest機制以提高搜索能力。文獻[8，9]將PSO算法和過濾式方法相結(jié)合來選取特征子集。文獻[10]提出一種兩階方法，首先采用F統(tǒng)計量選擇特征，然后使用BPSO算法在這些特征中選取最優(yōu)特征子集。

然而，上述方法存在以下不足：其一，僅采用群集智能選取的特征子集特征數(shù)量多，且運行效率差；其二，采用群集智能和過濾式方法相結(jié)合選取特征子集，雖然取得良好效果，但沒有考慮多特征間的冗余性；其三，兩階方法的第1階段所選特征數(shù)量需人工指定。

針對上述問題，提出基于BSO-OS(brain storm optimization in objective space)的兩階高維數(shù)據(jù)特征選擇算法(two-stage feature selection algorithm for high-dimensional data based on BSO-OS, BSFS)。首先，針對高維數(shù)據(jù)特征選擇問題設(shè)計BSO-OS算法，并采用BSO-OS算法搜索分類性能較好、特征數(shù)量較少的特征子集；然后，采用快速近似聯(lián)合互信息(fast approximate joint mutual information, FAMIR)對上述所選特征子集中分類精度最高的特征子集進行特征排序，去除冗余、不相關(guān)特征。在6個高維數(shù)據(jù)集上進行實驗，結(jié)果驗證了所提算法的有效性。

1 BSO-OS算法

BSO(brain storm optimization)是一種新的群集智能算法[11]。該算法模擬人類創(chuàng)造性解決問題的思路和過程，是一種很有潛力的群集智能算法。而BSO-OS算法使用簡單分類操作代替BSO算法中的聚類算法，特別適用于解決高維問題[12]。

BSO-OS算法中，新解是對所選解加上高斯隨機值而生成，如式(1)所示

(1)

(3)

其中， logsig() 是S型對數(shù)傳遞函數(shù)，T為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，k用來改變logsig() 的斜率， rand() 產(chǎn)生(0,1)間的隨機值。

然而BSO-OS算法適用于連續(xù)函數(shù)優(yōu)化，而特征選擇是組合優(yōu)化問題，根據(jù)高維數(shù)據(jù)特征選擇的特點設(shè)計BSO-OS算法。

(1)個體初始化：每一個個體表示一個所選特征子集，個體初始化為：Xi=[x1,…,xi,…,xn]， 其中Xi表示第i個個體，n為特征數(shù)量，xi為隨機產(chǎn)生的(0,1)間的值表示選擇第i個特征的概率。使用式(4)對個體每個維度進行離散化

(4)

(2)個體更新:使用式(1)對個體進行更新，對更新后的個體的每個維度使用式(5)進行離散化

(5)

其中， sig() 是S型傳遞函數(shù)， rand() 產(chǎn)生(0,1)間的隨機值。

(3)擾動更新:BSO-OS算法中，擾動更新過程僅改變一個維度的值，這在個體維度很高時并不適用。因此，本文在擾動更新時改變特征數(shù)量1%個維度的值，其值改變?nèi)缡?6)所示

(6)

2 FAMIR

基于信息準則的方法中，推薦使用聯(lián)合互信息(joint mutual information，JMI)[13]，JMI計算公式為

(7)

其中，F(xiàn)i是候選特征，F(xiàn)j是已選特征，S是已選特征集合，Y是類標簽。

然而JMI計算復(fù)雜度是特征數(shù)量的二次方，這限制其在高維數(shù)據(jù)中的應(yīng)用。針對上述問題，文獻[14]提出JMI快速近似算法即FAMIR，以加速JMI計算。該方法主要思想是對每項I(Fi,Fj;Y) 計算上下界，利用其上下界近似求其值。上界計算公式為

(8)

其中，Q={I(Fi,Fj),I(Fi,Y),I(Fj,Y)}。

下界計算公式為

(9)

因此I(Fi,Fj;Y) 近似計算為

I(Fi,Fj;Y)=β1L(Fi,Fj;Y)+β2U(Fi,Fj;Y)+β0

(10)

其中，β0、β1、β2為參數(shù)。

計算候選特征Fi的JMI值時，首先計算前λ項I(Fi,Fj;Y) 的值及其上下界(λ一般取特征數(shù)量的5%)，然后采用最小二乘法計算每一個β參數(shù)。在隨后每項I(Fi,Fj;Y) 計算中使用式(10)近似計算以達到加速目的。

3 BSFS算法

群集智能由于搜索能力強、魯棒性好而在高維數(shù)據(jù)特征選擇中得到應(yīng)用，但僅采用群集智能搜索的特征子集特征數(shù)量多，而過濾式方法能有效去除不相關(guān)和冗余特征，因而提出將群集智能和過濾式方法相結(jié)合的BSFS算法。

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

個體迭代更新過程中，個體優(yōu)劣是由適應(yīng)度函數(shù)決定。采用式(11)所示適應(yīng)度函數(shù)對特征子集進行計算，其中μ為加權(quán)系數(shù)

fitness=μ×balanced_accuracy+(1-μ)×distance

(11)

其中

(12)

其中，n是不同類的數(shù)量，TPi是類i中被正確分類的樣本數(shù)量， |Si| 是類i的樣本總數(shù)。計算算法產(chǎn)生的候選特征子集的分類性能時采用K近鄰算法(K-nearest neighbor，KNN)。

其中

(13)

其中

(14)

(15)

Dis(Vi,Vj) 用于度量向量Vi和Vj之間的距離，采用向量Vi和Vj之間，對應(yīng)維度值相同的數(shù)量除以向量維度的值作為距離值。Db是每個樣本與不同類中最近樣本之間距離的平均值，Dw表示相同類中每個樣本與最遠樣本之間距離的平均值， |S| 是樣本總數(shù)。

3.2 算法實現(xiàn)

BSFS算法包括兩個階段：首先采用BSO-OS算法搜索特征子集，再對上述所選特征子集中分類精度最高的特征子集使用FAMIR。BSO-OS算法的具體過程如圖1所示，算法中采用式(11)所示適應(yīng)度函數(shù)對所選特征子集進行計算。

圖1 BSO-OS算法的具體過程

4 實驗設(shè)置和結(jié)果分析

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

為了測試所提算法性能，采用6個高維基因表達數(shù)據(jù)集，數(shù)據(jù)集信息見表1，數(shù)據(jù)集可從以下網(wǎng)址下載：http://www.gems-system.org。表1中第5列表示具有最少樣本的類其樣本占總樣本的百分比，第6列表示具有最多樣本的類其樣本占總樣本的百分比。

從表1可見，相比特征數(shù)量，數(shù)據(jù)集樣本很少，且具有最多樣本的類和具有最少樣本的類，其樣本百分比差異很大。這些因素導(dǎo)致高維數(shù)據(jù)集的特征選擇非常困難。

4.2 實驗配置和參數(shù)設(shè)置

實驗中，采用k=3的KNN算法。計算分類精度時，使用十折交叉驗證，其中一折用作測試集，其余用作訓(xùn)練集，最后分類精度取10次測試集上的平均。對于每個數(shù)據(jù)集，進行30次獨立運行。考慮到計算和存儲資源，將個體數(shù)量n限制為150。實驗中，BSO-OS算法參數(shù)設(shè)置見表2。

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

本文使用式(11)所示適應(yīng)度函數(shù)，其中參數(shù)μ的取值會影響B(tài)SO-OS算法所選特征子集的性能，為選取更好μ值，首先比較μ取不同值,即μ取0.5、0.6、0.7、0.8、0.9和1.0時,BSO-OS算法所選特征子集的性能，結(jié)果見表3。

在表3中，首先比較每個數(shù)據(jù)集上μ取不同值時所選特征子集的平均精度和平均特征數(shù)量，若平均精度越高同

表1 實驗所用數(shù)據(jù)集

表2 實驗參數(shù)值

表3 μ取不同值時的實驗結(jié)果

時平均特征數(shù)量越少，則對應(yīng)μ值越好。但是僅通過平均精度和平均特征數(shù)量有時很難區(qū)分不同μ值的優(yōu)劣，因此表3添加最好精度一列，該列表示所選特征子集中獲得的最好分類精度，同時給出該精度對應(yīng)特征子集的特征數(shù)量。添加該列進行比較的原因是第2階段僅對第1階段所選分類精度最高的特征子集使用FAMIR。若通過平均精度和平均特征數(shù)量不能區(qū)分μ值優(yōu)劣，則比較所選特征子集的最好分類精度，最好分類精度越高則對應(yīng)μ值越好。每個數(shù)據(jù)集的最好μ值已用粗體標出。從表3可見，μ取0.7時在6個數(shù)據(jù)集的4個上獲得最好結(jié)果，μ取0.8時在6個數(shù)據(jù)集的兩個上獲得最好結(jié)果。為方便起見，所有數(shù)據(jù)集取相同μ值，因此，下列所有實驗取μ=0.7。

表4給出所提算法的實驗結(jié)果。其中“Full”表示使用數(shù)據(jù)集的所有特征，“BSO-OS”表示第1階段采用BSO-OS算法選擇的特征子集中分類精度最高的特征子集，“BSFS”表示所提算法的最終結(jié)果。從表4可見，所提算法在全部數(shù)據(jù)集相比原始數(shù)據(jù)集選出很少特征，同時所選特征子集的分類精度都有提高。在Prostate_Tumor數(shù)據(jù)集，所選特征子集的特征數(shù)量只有原始數(shù)據(jù)集的2.2%，但分類精度卻提高10.6%。除9_Tumors數(shù)據(jù)集，在其余數(shù)據(jù)集，所選特征子集的特征數(shù)量都不超過原始數(shù)據(jù)集的10%，同時分類精度都有提高。在11_Tumors數(shù)據(jù)集，分類精度提高11.2%，但特征數(shù)量只有原始數(shù)據(jù)集的4.9%。圖2給出所提算法在每個數(shù)據(jù)集所選特征子集的分類精度隨特征數(shù)量的變化，其中橫坐標表示所選特征子集的特征數(shù)量，縱坐標表示所選特征子集的分類精度。表4還可看出，所提算法中每階算法的有效性，采用BSO-OS算法選出的特征子集相比原始數(shù)據(jù)集具有較少特征，同時特征子集的分類精度都有提高，在Leukemia2數(shù)據(jù)集，BSO-OS算法選出的特征子集的特征數(shù)量只有原始數(shù)據(jù)集的10.8%，但分類精度提高9.4%。對BSO-OS算法選出的特征子集使用FAMIR算法后，可以得到特征數(shù)量更少的特征子集，同時特征子集的分類精度都有提高。在Prostate_Tumor數(shù)據(jù)集，使用FAMIR算法后，特征子集的特征數(shù)量減少92.0%，但分類精度略有提高。

表4 所提算法的實驗結(jié)果

圖2 所選特征子集的分類精度隨特征數(shù)量的變化

本文將BSO-OS算法應(yīng)用于高維數(shù)據(jù)特征選擇，為驗證其有效性，與標準BPSO算法的實驗結(jié)果進行比較，結(jié)果見表5。從表5可見，在全部數(shù)據(jù)集，采用BSO-OS算法選出的特征子集的平均分類精度和平均特征數(shù)量都優(yōu)于BPSO算法選出的特征子集。在Lung_Cancer數(shù)據(jù)集，BSO-OS算法選出的特征子集的平均特征數(shù)量只有BPSO算法的46.3%，但平均分類精度卻提高2.0%。在9_Tumors數(shù)據(jù)集，BSO-OS算法比BPSO算法選出的特征子集的平均分類精度高11.1%，但平均特征數(shù)量卻只有BPSO算法的65.1%。同時，將BSO-OS算法與BPSO算法的運行時間進行比較，結(jié)果如圖3所示，該圖中運行時間指的是平均每輪的運行時間。從圖3可見，在全部數(shù)據(jù)集，BSO-OS算法的運行效率都優(yōu)于BPSO算法，其運行時間分別只有 BPSO 算法的51%，72%，63%，54%，62%，63%。

為進一步驗證所提算法的有效性，分別與一階方法(PSO-LSSU)[8]和兩階方法(CDMC)[10]所選特征子集中分類精度最高的特征子集進行比較。表6給出所提算法與PSO-LSSU和CDMC在6個數(shù)據(jù)集的實驗結(jié)果。為與CDMC進行公平比較，在表6的第4行給出所提算法得到與CDMC分類精度相似時的特征子集的特征數(shù)量和分類精度，正如“BSFS(*)”一行所示。

從表6可見，與PSO-LSSU的結(jié)果相比，在全部數(shù)據(jù)集，所提算法所選特征子集的特征數(shù)量和分類精度都優(yōu)于PSO-LSSU所選特征子集。與CDMC的結(jié)果相比，在6個數(shù)據(jù)集的4個上所提算法所選特征子集的特征數(shù)量和分類精度優(yōu)于CDMC所選特征子集，在Prostate_Tumor數(shù)據(jù)集，在分類精度略高的情況下，所提算法所選特征子集的特征數(shù)量只有CDMC所選特征子集特征數(shù)量的5.2%。在Leukemia2數(shù)據(jù)集具有與CDMC相似的性能，僅在9_Tumors數(shù)據(jù)集的性能略差于CDMC。

表5 BSO-OS和BPSO的對比結(jié)果

圖3 BSO-OS與BPSO運行時間對比

圖4給出3種方法各自的運行時間，其中運行時間指的是平均每輪的運行時間。為公平比較，分別將CDMC第1階段和所提算法第2階段的運行時間平均到每輪運行時間中。從圖4可見，所提算法在全部數(shù)據(jù)集的運行效率優(yōu)于PSO-LSSU，與CDMC的運行效率相比，所提算法在6個數(shù)據(jù)集的3個上運行效率占優(yōu)，在Lung_Cancer數(shù)據(jù)集具有類似的運行效率，在Leukemia2和Prostate_Tumor數(shù)據(jù)集，運行效率略差。

5 結(jié)束語

針對高維數(shù)據(jù)特征選擇問題，將BSO-OS和FAMIR算法相結(jié)合，提出一種兩階特征選擇算法BSFS。實驗結(jié)果表明：所提算法能有效實現(xiàn)BSO-OS和FAMIR兩者的優(yōu)勢互補，在第1階段，BSO-OS算法在高維數(shù)據(jù)特征選擇中具有更好的搜索能力和運行效率；在第2階段，F(xiàn)AMIR算法能有效去除特征子集中的不相關(guān)和冗余特征。整個算法分類精度高，同時具有良好的運行效率。

表6 BSFS與PSO-LSSU和CDMC的對比結(jié)果

圖4 3種方法運行時間對比