基于BSO-OS算法的兩階高維數據特征選擇

田浩楠，周 暉

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

0 引 言

隨著云計算和大數據的迅速發展，海量數據不斷呈現，數據維度不斷增加[1]。特征選擇從給定特征集合中選取相關特征子集，以降低數據維度、簡化學習模型、加速學習過程[2,3]。

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

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

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

1 BSO-OS算法

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

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

(1)

(3)

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

然而BSO-OS算法適用于連續函數優化，而特征選擇是組合優化問題，根據高維數據特征選擇的特點設計BSO-OS算法。

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

(4)

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

(5)

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

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

(6)

2 FAMIR

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

(7)

其中，Fi是候選特征，Fj是已選特征，S是已選特征集合，Y是類標簽。

然而JMI計算復雜度是特征數量的二次方，這限制其在高維數據中的應用。針對上述問題，文獻[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為參數。

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

3 BSFS算法

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

3.1 適應度函數

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

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

(11)

其中

(12)

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

其中

(13)

其中

(14)

(15)

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

3.2 算法實現

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

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

4 實驗設置和結果分析

4.1 數據集

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

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

4.2 實驗配置和參數設置

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

4.3 實驗結果與分析

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

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

表1 實驗所用數據集

表2 實驗參數值

表3 μ取不同值時的實驗結果

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

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

表4 所提算法的實驗結果

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

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

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

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

表5 BSO-OS和BPSO的對比結果

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

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

5 結束語

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

表6 BSFS與PSO-LSSU和CDMC的對比結果

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