吳清壽,劉長勇,林麗惠

(武夷學院 數(shù)學與計算機學院,武夷山 354300)

(認知計算與智能信息處理福建省高校重點實驗室,武夷山 354300)

引言

在現(xiàn)實應用場景中,樣本的屬性維度經(jīng)常成千上萬,而機器學習的各類方法中,經(jīng)常面對的問題之一是距離的計算,當維度過大的時候,內(nèi)積的計算都難以實現(xiàn).高維數(shù)據(jù)中的冗余特征增加了計算的復雜度,也增加了機器學習的難度.特征降維是緩解維度災難的重要途徑,其主要包括特征提取和特征選擇[1].特征提取通過將原始特征映射到低維空間,并希望能在低維空間中保持原始數(shù)據(jù)的相關(guān)信息；而特征選擇方法是在評價準則的指導下,從數(shù)據(jù)集的全體特征中選取出滿足評價指標的部分特征(也稱為最優(yōu)特征子集) 的過程.根據(jù)特征子集的評估方法,可以將特征選擇分為過濾式、封裝式和嵌入式三種模型[2].

按照特征選擇算法中的搜索策略分類,可將其分為窮舉式、啟發(fā)式與隨機式[3].Focus 算法[4]是典型的窮舉法,其能夠識別出所有的最優(yōu)特征子集.序列前向選擇與序列后向選擇及其各類改進算法[5]屬于啟發(fā)式方法,RFR[6]是一種基于序列前向選擇的自底向上的特征選擇方法,屬于有監(jiān)督學習算法.隨機式無需遍歷所有組合,具有更好的時間復雜度,文獻[7]對粒子群優(yōu)化和蟻群優(yōu)化算法在特征選擇上的應用進行了總結(jié).

將支持向量機(Support Vector Machines,SVM)與特征選擇結(jié)合的研究中,SVM-RFE[8]是基于SVM 的回歸特征消去方法,使用RFE (Recursive Feature Elimination,遞歸特征消除)在特征排序過程選取出最優(yōu)特征子集.K-SVM-RFE[9]將SVM-RFE 和特征聚類算法結(jié)合,用于去除無關(guān)基因.Tan 等人[10]將SVM 加入遺傳算法,并將其與特征選擇算法進行封裝,基于分類準確度迭代求解.文獻[11]提出基于特征子集區(qū)分度衡量準則,以SVM 為分類工具,通過計算特征子集對分類的聯(lián)合貢獻來考慮特征的相關(guān)度.

文獻[12]提出一種基于混合式特征選擇算法,主要對特征過濾階段的CFS 算法進行改進,未對過濾后的精簡子集優(yōu)化處理以提高模型的訓練速度.文獻[13]提出的兩級特征選擇方法對原始特征集合中的噪聲和無關(guān)特征進行過濾,通過Fisher 和信息增益同時計算,最后進行交叉選擇精簡子集,該方法在特定場景下可以有效提高分類準確率,但增加了過濾階段的時間開支.

本文提出一種混合式特征選擇算法,先用卡方檢驗計算特征與類別的相關(guān)度,再采用過濾式選擇方法得到相關(guān)度高的重要特征子集,并對重要特征子集進行標準化縮放,之后在包裹了SVM 的序列后向選擇算法(SBS-SVM)上進一步選出最優(yōu)特征子集.為了評估算法的有效性,本文將SBS-SVM 算法與SBS-NB 和SBS-KNN 的實驗結(jié)果進行比較,對不同算法選取出的最優(yōu)特征子集組合數(shù)量、最高準確度,基于最優(yōu)特征子集訓練的訓練集與數(shù)據(jù)集的準確度與擬合度、維度縮減率等進行了討論.

1 混合式特征選擇算法模型

過濾式特征選擇方法可以根據(jù)特征與目標的相關(guān)性對特征進行過濾,其主要方法之一單變量特征選擇(univariate feature selection)分別計算變量的相關(guān)統(tǒng)計指標,并根據(jù)統(tǒng)計結(jié)果篩選出重要特征子集.本文選擇卡方檢驗對特征與類別的相關(guān)性進行檢驗.

特征縮放(feature scaling)可以提升分類算法和優(yōu)化算法的性能,在進行包裹式特征選擇之前,需要將重要特征子集進行特征縮放.特征縮放的主要方法有歸一化和標準化,其中,標準化方法使得特征值呈正態(tài)分布,利于訓練階段的權(quán)重更新,同時,標準化方法還可以保持異常值的信息,進一步減少異常值對算法的影響.標準化的方法如式(1):

其中,μx和 σx分別表示數(shù)據(jù)集某個特征列的均值和標準差.

包裹式特征選擇方法將學習器的分類準確度作為最優(yōu)特征子集的評價標準,其輸入是上一步驟得到的重要特征子集.在優(yōu)選后的重要特征子集中,采用序列后向選擇可以較為快速的獲得最優(yōu)特征子集.考慮到誤差的評分與所采用的分類器及其精確度計算方式相關(guān),而支持向量機在高維特征空間中的模式識別優(yōu)勢明顯,故將支持向量機與序列后向選擇方法進行包裹封裝.

本文提出的混合式特征選擇算法主要流程如圖1所示.

圖1 混合式特征選擇算法流程

2 算法實現(xiàn)

2.1 序列后向選擇算法

序列后向選擇算法(Sequential Backward Selection,SBS)是序列特征選擇算法的一種典型應用,其基于貪婪搜索算法,用于將原始的n維特征空間縮減到一個k維特征子空間,其中k＜n.

SBS 算法的基本思想是:在分類性能衰減最小的約束下,通過逐步移除不相關(guān)的特征,選取出與問題最相關(guān)的特征子集,從而提高分類學習算法的計算效率,通過縮減不相關(guān)特征可以降低模型的泛化誤差,提高模型的預測能力.

2.2 支持向量機

支持向量機是一種分類方法,其基本模型是定義在特征空間上的間隔最大的線性分類器.SVM 通過確定一個分離超平面,使得不同類別的樣本分別處于超平面的兩側(cè),并使得兩個不同類別的支持向量到超平面的距離之和最大,其中,支持向量到超平面的距離也稱為間隔(或幾何間隔).間隔越大,則算法所產(chǎn)生的超平面的分類結(jié)果越魯棒,其泛化能力也越強.

對于訓練集T={(x1,y1),(x2,y2),···,(xn,yn)},其中xi∈X=Rn,yi∈{-1,+1},i=1.2,···,N,其分離超平面為wTx+b=0.

假設xi是支持向量,則其他樣本點xj到分離超平面的函數(shù)間隔必然大于或等于支持向量到分離超平面的函數(shù)間隔.SVM 的基本思路是求解一個幾何間隔最大而又能正確分離樣本點的分離超平面,其可表示為一個約束最優(yōu)化問題:

在多數(shù)數(shù)據(jù)集上會存在噪音(離群點),這將造成線性不可分的問題,其本質(zhì)就是樣本點(xj,yj)無法滿足函數(shù)間隔≥1的約束條件,給分離超平面的構(gòu)建增加了難度,甚至無法構(gòu)建超平面.解決問題的方法是通過對每個樣本點 (xj,yj) 添加一個松弛變量ξj≥0,使得+ξj≥1,并設置一個懲罰因子C＞0,C是常數(shù),其值越大對誤分類的懲罰越大,對噪聲的容忍度越低.松弛變量的引入將增強模型的容錯能力.加入松弛變量后的目標函數(shù)和約束條件為:

序列最小優(yōu)化(Sequential Minimal Optimization,SMO)算法[14]將一個復雜的優(yōu)化問題轉(zhuǎn)化為一個比較簡單的兩變量優(yōu)化問題,運用SMO 可以快速求解 α?和b.由此可得:

分離超平面為

分類決策函數(shù)為

2.3 混合式特征選擇算法

輸入:數(shù)據(jù)集Ds特征集X分類算法SMO停止條件控制參數(shù)k輸出:最優(yōu)特征子集X-算法步驟:1.用卡方檢驗方法計算特征與類別的相關(guān)性Rf 2.根據(jù) Rf 選擇n 個重要特征集合Xn 3.對 Xn進 行標準化,得到標準化特征子集S Xn 4.用SBS-SVM 對SXn 進 行特征優(yōu)選,得到最優(yōu)特征子集X-

SBS-SVM 算法中,從SXn中逐一減少特征數(shù),并用SMO 算法根據(jù)當前特征集進行分類,評估其分類性能,最后得到一個或多個最優(yōu)特征子集,并在實驗階段討論各最優(yōu)特征子集的實際分類性能.

SBS-SVM 算法1. d=|S Xn|2. X-=S Xn 3. errd=∞4.while d＞k 5.for c in comb(X-,d-1)6. res=S MO(Ds,c)7. err?=1-Accuracy(res)8.if (err?＜errd) then 9. errd=err?10. Xd-=c 11.end if 12.end for 13. X-=Xd-14. d=d-1 15.end while

算法第5-12 行對候選最優(yōu)特征子集X-按照指定的特征子集數(shù)量進行排列組合,并對每一個特征子集組合求誤差(性能損失).

3 實驗

實驗的數(shù)據(jù)集選擇Wine,Iris 和Breast Cancer Wisconsin (WDBC) 等3 個UCI 的常用數(shù)據(jù)集.Wine 數(shù)據(jù)集通過化學成分分析推斷出葡萄酒的起源,其包含178 個樣本,每個樣本有13 個特征值,特征值的數(shù)據(jù)類型是整數(shù)或?qū)崝?shù),都是連續(xù)變量,所有樣本分為3 類.Iris 數(shù)據(jù)集通過鳶尾花的4 個特征預測花卉的種類,共有3 種類型,樣本數(shù)為150 個.WDBC 是有關(guān)乳腺癌的數(shù)據(jù)集,包含569 個樣本,30 個用于診斷的特征,診斷結(jié)果為2 種類型.

為了對比算法的效果,本文將SVM、KNN (K Nearest Neighbor,K 最近鄰)和NB (Naive Bayes,樸素貝葉斯)3 種分類算法封裝到序列后向選擇算法中,對算法在全體特征、最優(yōu)特征子集上的分類準確率、擬合程度等進行比較.實驗中,SBS-SVM 算法的核函數(shù)采用線性核函數(shù),SBS-KNN 算法中K 的值取3,SBSNB 算法的先驗概率為正態(tài)分布.數(shù)據(jù)集中70%的樣本劃分為訓練集,30%的樣本劃分為測試集.

本文的實驗環(huán)境:Intel(R) Core(TM) i5-6500 CPU 3.20 GHz,8 GB 內(nèi)存,Windows7 操作系統(tǒng),算法采用Python3.6 實現(xiàn).

3.1 評價指標

本研究采用的評價指標有三個:分類準確率、F1 得分和維度縮減率.

分類準確率的定義如式(6):

其中,yi′是第i個 樣本的預測值,yi是真實值,1(x)是指示函數(shù),當yi′=yi時 ,即x值為真,則1(x)的值為1,否則為0.

F1 得分的定義如式(7):

其中,P是查準率,R是召回率,TP是真正例,FP是假正例,FN是假反例.對于多分類問題的F1 得分計算,本研究采用micro-F1,其定義如式(8):

維度縮減率的定義如式(9):

其中,S F是最優(yōu)特征子集中的特征數(shù),AF是全體特征數(shù).Dr的取值范圍為[0,1],其值越大,表示維度縮減的效果越好.

3.2 特征過濾實驗

特征過濾實驗中,先用卡方檢驗方法計算各特征與類別的相關(guān)度,再選擇相關(guān)度較高的特征構(gòu)成重要特征子集.如何確定重要特征子集的數(shù)量是一個需要考慮的問題,表2中,縮減率最小的值為0.385,根據(jù)這個結(jié)果,考慮將重要特征子集的數(shù)量設置為全體特征數(shù)的70%.表1為按70%優(yōu)選后的重要特征子集.

表1 卡方檢驗優(yōu)選后的重要特征子集

3.3 算法在重要特征子集上的實驗

為了較為全面的評價SBS-SVM 算法效果,本文對三個數(shù)據(jù)集的重要特征子集進行排列組合,并將其與SBS-KNN 和SBS-NB 兩種分類算法進行對比測試,結(jié)果 如圖2,圖3,圖4所示.

圖2 在Iris 數(shù)據(jù)集上的最高準確率

圖2中,SBS-SVM 算法在特征數(shù)為1、2、3 的三種情況下都能獲得最大準確率為1 的效果,而SBSKNN 和SBS-NB 兩種算法都只能在兩類特征組合中取得1 的準確率.因為Iris 數(shù)據(jù)集的特征數(shù)較少,三種算法的效果對比并不明顯.

在Wine 數(shù)據(jù)集上的實驗結(jié)果中,SBS-SVM 共有5 種最優(yōu)特征子集的組合可以獲得1 的準確率,SBSKNN 算法可以獲得3 種組合的最高準確率,而SBSNB 算法最高只能獲得0.968 的準確率.實驗結(jié)果如圖3所示.

在WDBC 數(shù)據(jù)集上的實驗結(jié)果中,SBS-SVM 共有6 種最優(yōu)特征子集的組合可以獲得1 的準確率,SBS-NB 算法可以獲得4 種組合的最高準確率1,而SBS-KNN 算法只在1 種組合上得到1 的準確率.實驗結(jié) 果如圖4所示.

圖3 在Wine 特征子集組合上的最高準確率

圖4 在WDBC 特征子集組合上的最高準確率

從以上實驗結(jié)果對比可以看成,SBS-SVM 能夠在各種數(shù)據(jù)集及其特征子集組合上取得較高的分類準確率,尤其是特征數(shù)較多的數(shù)據(jù)集,其效果更加明顯.

3.4 算法在最優(yōu)特征子集上的實驗

為了進一步驗證基于SBS-SVM 算法的有效性,將上一節(jié)中識別出的最優(yōu)特征子集組合進行進一步的測試.實驗通過將最優(yōu)特征子集用于重新訓練原訓練集,并用原測試集進行測試,模型評估采用F1 得分,實驗結(jié)果如圖5、圖6所示.

圖5中,在特征數(shù)為8 的特征子集組合上,算法在訓練集上和測試集上都能獲得較高的F1 得分,其值分別為0.952 和0.946,且兩者之間的差距最小,意味著該特征子集組合具有較好的泛化能力.

圖6中,在特征數(shù)為12 的特征子集組合上,算法在訓練集上和測試集上的F1 得分分別為0.980 和0.971.

圖5 在Wine 最優(yōu)特征子集上的實驗

圖6 在WDBC 最優(yōu)特征子集上的實驗

表2中,將三種算法在WDBC 和Wine 兩個數(shù)據(jù)集上進行測試,選取在訓練集和測試集上F1 得分較高且兩個值較為接近的最優(yōu)特征子集進行比較,并計算其維度縮減率Dr.可以看出,SBS-SVM 算法能夠在訓練集合測試集上都取得較高的F1 得分,且兩者之間的差較小,避免了過擬合的問題.在WDBC 數(shù)據(jù)集上,SBS-SVM 與SBS-KNN 的Dr值略小于SBS-NB,在Wine 數(shù)據(jù)集上,SBS-SVM 與SBS-KNN 的Dr值相同,略高于SBS-NB.從維度縮減率看,兩個數(shù)據(jù)集的最優(yōu)特征子集在不同算法中的表現(xiàn)差異較小.

表2 綜合擬合度及F1 得分選擇的特征數(shù)與 Dr值對比

3.5 SBS-SVM 中松弛變量的影響實驗

SBS-SVM 算法中,松弛變量的選擇對實驗結(jié)果也會有一定的影響,本部分實驗在兩個數(shù)據(jù)集上對松弛變量的變化與F1 得分的關(guān)系進行討論.在Wine 數(shù)據(jù)集中選擇的特征數(shù)為7,在WDBC 數(shù)據(jù)集中選擇的特征數(shù)為12.

如圖7所示,松弛變量的取值對訓練集和測試集都有一定的影響,但總體影響不大,在Wine 數(shù)據(jù)集中,訓練集F1 得分最大值和最小值的差為0.01,測試集的F1 得分最大值和最小值的差為0.0175,在WDBC 數(shù)據(jù)集上的差別也很小,在訓練集和測試集上的F1 得分最大值和最小值之差分別為0.008 和0.019.所以,本研究中 所提出的特征選擇算法對松弛變量不敏感.

圖7 松弛變量實驗

4 結(jié)束語

本文將特征選擇分為兩個步驟,首先對特征進行過濾式選擇,得到重要特征子集；之后,對數(shù)據(jù)進行標準化縮放；在包裹式特征選擇階段,將序列后向選擇算法與支持向量機進行封裝,提出一種SBS-SVM 特征選擇算法,將其與SBS-KNN 和SBS-NB 兩種算法在Wine 等3 個數(shù)據(jù)集上進行實驗,比較了算法所選擇的不同特征子集的最高準確率,并根據(jù)特征子集在訓練集和測試集上的F1 得分和擬合度進行最優(yōu)特征子集選擇.實驗結(jié)果表明,SBS-SVM 算法在F1 得分和擬合度上都具有較好的效果,但其所選擇的最優(yōu)特征子集在維度縮減率指標上與其他兩種算法區(qū)分度不明顯.在今后的研究中,針對無標簽數(shù)據(jù)普遍存在的問題,進行無監(jiān)督的特征降維將是值得關(guān)注的研究領域.