田浩楠,周 暉
(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南通 226019)
隨著云計算和大數(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é)果驗證了所提算法的有效性。
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)
基于信息準則的方法中,推薦使用聯(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)近似計算以達到加速目的。
群集智能由于搜索能力強、魯棒性好而在高維數(shù)據(jù)特征選擇中得到應(yīng)用,但僅采用群集智能搜索的特征子集特征數(shù)量多,而過濾式方法能有效去除不相關(guān)和冗余特征,因而提出將群集智能和過濾式方法相結(jié)合的BSFS算法。
個體迭代更新過程中,個體優(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ù)。
BSFS算法包括兩個階段:首先采用BSO-OS算法搜索特征子集,再對上述所選特征子集中分類精度最高的特征子集使用FAMIR。BSO-OS算法的具體過程如圖1所示,算法中采用式(11)所示適應(yīng)度函數(shù)對所選特征子集進行計算。
圖1 BSO-OS算法的具體過程
為了測試所提算法性能,采用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ù)集的特征選擇非常困難。
實驗中,采用k=3的KNN算法。計算分類精度時,使用十折交叉驗證,其中一折用作測試集,其余用作訓(xùn)練集,最后分類精度取10次測試集上的平均。對于每個數(shù)據(jù)集,進行30次獨立運行。考慮到計算和存儲資源,將個體數(shù)量n限制為150。實驗中,BSO-OS算法參數(shù)設(shè)置見表2。
本文使用式(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ù)集,運行效率略差。
針對高維數(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種方法運行時間對比