基于?2，1范數的在線流特征選擇算法?

吳中華 鄭 瑋

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

在數據挖掘和機器學習算法研究中，對高維數據的降維是避免維數災難［1］的重要研究手段。特征選擇方法通過在原始特征集合中選擇部分相關特征子集來實現降維目的。隨著各種特征選擇算法被相繼提出，這些算法已經表明在不損失模型的預測精度的條件下，特征選擇極大降低了模型所用的特征維數，進而顯著提高模型的可理解性和效率［2～3］。傳統的特征選擇方法假設訓練數據的所有特征在特征選擇算法開始之前預先給定，即訓練數據集的特征空間是靜止且已知的。然而，現實應用領域并不一定支持這個假設條件，在現實應用中，往往由于特征提取的高代價性或者特征空間的動態性使得訓練數據的全部特征在特征選擇之前不一定被全部獲取，從而造成特征空間是動態且未知的。例如，高分辨率行星圖像上的火星隕石坑檢測是行星研究中一項很重要的任務，隕石坑計數提供了測量行星表面相對年齡的有效方法。提取紋理特征用于隕石坑檢測已經被證明是實現自動隕石坑檢測有效的途徑之一［4～5］。因高昂的特征抽取代價和抽取多大規模的紋理特征集合是未知的，從覆蓋火星表面的行星圖像上預先生成所需要的紋理特征集合幾乎是不可行的。

特征空間隨時間變化而變化的動態特征空間被定義為流特征。流特征概念下的特征選擇過程中，因預先沒有給定整個特征空間知識，局限于靜態特征空間的傳統特征選擇方法已經不能夠滿足這種場景下的特征選擇要求。因此，新的基于流特征概念下的特征選擇方法被提出來處理特征空間是動態且未知的條件下的特征選擇問題［6］。由此，流特征選擇問題被定義為樣本空間不變的條件下，特征空間維度隨時間而增加，且每個新流入的特征被立即在線處理而不需要預先獲得訓練數據的整個特征空間的先驗信息。這樣，把動態、未知條件下的特征選擇問題轉化為流特征概念下的在線特征選擇問題。目前已有相關研究來解決流特征選擇問題，Perkins 等提出一種基于逐步梯度下降的流特征選擇框架，使用?1范數作為約束條件提出Grafting 算法［6］。這個算法后來被Glocer 等用于圖像處理中的邊的在線偵測問題［7］。Zhou 等提出一種基于逐步回歸的在線特征選擇算法：Alpha-investing 算法［8～9］，該算法需要知道候選特征構成的先驗知識，然后根據先驗知識對初始特征進行變換。Wu 等根據對特征子集的四種定義：不相關特征［10］，冗余特征，非冗余特征［11］和強相關特征，提出OSFS（Online Streaming Feature Selection）算法［12］選擇出動態流特征環境下的非冗余特征和強相關特征。算法利用統計檢驗的方法檢測特征與標簽，特征與特征直接的相關性。在大數據的應用中，特征選擇技術是非常重要的，Wu 等在osfs 算法基礎上提出了SAOLA（Scalable and Accurate OnLine Approach）算法［13］，一種可擴展和準確的在線選擇方法。但是由于算法采用基于統計量判斷的Filter特征選擇方法帶來的局限性，以及為加快運行速度而僅僅采用成對對比的判斷策略，使得saola 算法在分類任務上沒有明顯優勢。Jundong Li等將流特征選擇算法應用于社交媒體的特征選擇問題中，提出一種無監督的流特征選擇算法：USFS（Unsupervised Streaming Feature Selection）算法［14］。社交媒體數據增長迅速，數據的特征空間以動態未知的情形增長，傳統的靜態特征選擇算法不適用在這種場景下。同時社交媒體數據多為無標簽信息的數據，文獻［14］通過提取用戶鏈接關系中的社交潛在因素信息作為流特征選擇算法的約束條件，提出社交媒體的無監督流特征特征選擇算法。

相較于?0范數和?1范數易受噪聲干擾的缺點，?2，1范數對噪聲不敏感，同時具有行稀疏性質，適用于約束結構化稀疏問題。目前已有關于?2，1范數應用于傳統靜態特征選擇作為約束條件的研究［15～17］，此類算法通過對特征選擇矩陣進行?2，1范數最小化約束來選擇特征。為解決在線流特征選擇問題，本文提出了新的基于?2，1范數約束條件下的流特征選擇模型及流特征場景下的優化算法。

2 流特征選擇模型

對于一個流特征空間數據集，定義每一個樣本向量xi的類別為，若xi屬于第k 類，則yi，k=1，其余值為0，類別標簽矩陣為，其中n 為樣本數，c 為類別數。設流特征空間在t時刻流入數據空間的樣本數據為，此時的特征權重矩陣為。

定義t時刻的特征選擇損失函數為

為簡便起見，偏置項bt被添加進入Wt矩陣，同時在數據矩陣Xt中增加全1 列向量。由此損失函數變成：

這里，損失函數為樣本權重積與類別的最小殘差平方和模型，即預測值與實際值殘差的Frobenius范數。增加對特征權重矩陣Wt的正則化約束R(Wt)和系數λ以避免模型過擬合，目標函數為

本文使用?2，1范數作為約束條件，目標函數可重寫為

式（4）中：λ是一個權衡參數；‖ ? ‖2，1表示?2，1范數，?2，1范數正則化能控制權重矩陣Wt的數據尺度并同時保證Wt的行稀疏性，使得模型能夠選擇出最優的特征子集。

3 流特征選擇算法

3.1 接收新特征

流特征環境下，每個特征逐個到達并即刻在線處理，完整的特征空間預先不可知，特征空間動態變化。設在t 時刻新到達特征，其特征權重向量，此時的特征空間為，特征權重矩陣為這里，新特征ft是特征空間Xt的第t 列，權重向量wt是權重矩陣的Wt的第行。若新添加的特征ft使得目標函數取得最優值時，其特征權重向量wt=0，即新特征ft的加入對于模型的優化沒有起到作用，此時拒絕并丟棄新特征ft；否則，新特征ft接收進入模型。因此可以通過判斷目標函數J(Wt)是否在坐標原點取得最優值來判斷是否接收新特征ft。

因?2，1范數在原點處不可導，故目標函數在原點處亦不可導，但是目標函數在原點處的任意方向梯度均存在。若原點為目標函數極值點，則目標函數在原點處的任意方向的方向導數均為正數。此時，在非常接近原點處的任一方向取得采樣點

使用點ω的方向導數代表原點處目標函數的方向導數。有：

因此，若對于原點領域內任意采樣點，式（5）均滿足，則拒絕新特征ft。否則，只要存在一個采用點不滿足式（5），則接收新特征。理論上，ε值越小，目標函數在采樣點ω處的方向導數越接近原點處的方向導數。但隨類別數c 的增加，目標函數空間維度增加，使得高維空間累計誤差增加，所以ε在目標函數維度過高時不宜過小。

式（5）可約簡為

此時拒絕新流入的特征ft。由此，新特征ft被接收的條件為其權重向量wt滿足：

采樣策略為高維空間的超球面上均勻采樣。為方便計算，可以在高維空間的超立方體表面均勻采樣。

接下來根據矩陣的求導法則，求出目標函數對新到達特征的權重向量wt的梯度。對目標函數做恒等變換：

這里，?2，1范數在原點處不光滑，借助輔助矩陣D轉化為一個次梯度的形式。D是一個對角矩陣，對角線上的值為

利用范數和矩陣跡的求導公式可得損失函數對于特征向量wt的梯度為

這樣可以得到目標函數對新特征權重向量的導數為

可得到針對本文提出的特征選擇模型在t時刻到達的新特征ft接收條件為其權重向量wt滿足：

3.2 更新模型

通過接收條件檢測的新特征即表明這個特征是一個對模型有用的特征，則接收新特征進入模型。在每次新接收一個特征之后，重新對模型進行整體優化，更新所有已接收特征的權重。本文使用共軛梯度法（conjugate gradient algorithm）優化模型［18］，因為其收斂速度快速，計算開銷低。

若在t 時刻，新特征ft被接收，新增的特征可能會使得已接收的最優特征子集中存在冗余特征，即新特征的接收造成已選特征的冗余，或者新特征雖然通過接收條件的檢測，但新特征對于已接收最優特征子集是冗余的，此時需要去除冗余特征。每次接收新特征之后，重新對模型做一次整體優化，因新特征的加入，冗余特征的權重向量會變為0 向量。去除權重向量?1范數趨近于0 的特征，即可去除冗余特征。

3.3 算法框架

根據上述理論推導，將算法框架描述如下。算法1 描述完整的流特征選擇算法總體框架。當t時刻新特征ft到達，若新特征通過梯度測試，則接收新特征ft進入當前最優特征子集BFSt，使用共軛梯度法更新當前最優特征子集的權重向量并刪除冗余特征。

算法1 流特征選擇算法

輸入：X，Y，λ，ε

輸出：t時刻的最優特征子集BFSt

1）Initial：BFSt=，Wt=1

2）Wt=update_weigh（tWt，BFSt，Y，λ）

3）While not convergence：

4）//在t時刻，新特征ft到達

5）ft=get_new_feature（）

6）//檢測新特征是否通過梯度檢測

7） If gradient_validation（ft，Wt-1，BFSt-1，Y，λ，ε）：

8）//新特征通過梯度測試，接收進入模型并更新模型

9）BFSt=[BFSt-1，ft]

10）Wt=update_weigh（tWt，BFSt，Y，λ）

11）//去除冗余特征

12）Wt，Xt=refresh_selected（Wt，Wt）

13） End if

14）End while

15）//返回收斂后的最優特征子集

16）ReturnBFSt

算法1中的梯度檢驗算法如算法2描述。根據接收新特征的條件，若存在某一方向，使得目標函數J(Wt)滿足式（13），則返回真，新特征通過梯度測試條件。否則，返回假，新特征未通過接受條件。

算法2 梯度檢驗（gradient validation）

輸入：ft，Wt-1，BFSt-1，Y，λ，ε

輸出：布爾值，是否通過梯度驗證

1）Initial：BFSt=[BFSt-1，ft]

2）//產生多個采樣方向

3）sample_directions=generate_sample_directions（ε）

4）//判斷是否存在一個方向使得接收條件滿足

5）for direction in sample_directions：

6）//計算目標函數在采樣方向的導數

7） grad=derivative（direction，J，BFSt，Y，λ）

8） If grad*direction＜0：

9） Return True

10）//所有采樣方向均不滿足接收條件，未通過檢測

11）Return False

4 實驗分析

為了驗證提出的流特征選擇算法效果，在多個數據集上進行了實驗，使用多個高維數據集模擬流特征環境下的特征選擇問題。為將本文的算法與現有流特征選擇算法做比較，使用sklearn 科學工具包中的線性svm分類器對算法進行5折交叉驗證方法，平均分類精度和選擇的特征數量作為評價算法性能的兩種標準。

4.1 數據集

實驗中使用12 個數據集來驗證本文提出的流特征選擇算法。數據集全部來自于亞利桑那州立大學（Arizona State University）的特征選擇數據庫。其中序號為1～3 的是人臉圖像數據集，序號為4～9的是生物信息數據集，序號為10 的是來自于NIP2003 特征選擇挑戰比賽數據集，序號為11～12的是文本數據集。所有數據集的描述在表1給出。

表1 實驗中使用的數據集

4.2 數據預處理

為保持所有的特征在相似的尺度標準中，對每一個特征進行歸一化到標準正態分布的處理。在特征選擇之前，將特征重新調節為標準正態分布。對于特征f，標準化之后的特征為

4.3 對比實驗

為評估本文提出的算法的有效性，與現有流特征選擇算法進行了多個數據集的對比實驗。圖1顯示了本文提出的算法與現有算法的對比實驗結果。實驗中使用的對比算法均來自于LOFS提供的在線流特征選擇算法［19］。根據算法庫的使用手冊設置了實驗中算法的最優參數。sfs_l21 為本文提出的算法，算法引入了兩個參數λ和ε。通過參數調優，對于實驗中參數進行了最優設置。實驗結果對比圖中下半部分表示不同算法選擇出的特征個數，選擇的特征個數越少，表明算法的壓縮性能越好。上半部分表示在對應壓縮率情況下的分類識別率率，識別率越高表明算法的識別性能越好。

4.3.1 與grafting算法實驗結果對比

圖1 描述與grafting 算法相比較的結果。可以看出，本文提出的算法在所有數據集上均得到了更高的分類識別率。在其中的6 個數據集上選擇了更少的特征，同時保持更高的分類識別率。在12個數據集中的10 個數據集選擇出了同數量級的特征個數，但是卻得到明顯優于grafting 算法的分類識別率。文本數據集的最優特征子集規模比較大，在兩個文本數據集上，本文的算法選擇出的特征個數較高，能得到更好的分類識別率。得出結論，本文提出的算法在保持相近的壓縮率的同時，在分類識別率上明顯優于grafting算法。

圖1 與grafting算法實驗結果對比

4.3.2 與osfs算法實驗結果對比

對比實驗中osfs算法為fast版本：fast_osfs在alpha=0.01 下的結果。osfs 算法的fast 版本不會降低選擇的特征的質量，同時能加速算法的運行。圖2與osfs算法相比較可以看出，本文提出的算法在10個數據集上的識別率都要高于osfs算法。osfs算法運行復雜度隨選擇的特征個數成指數增長，為了提高算法效率的考慮，總是選擇出最少的特征，這樣不可避免地會去除掉好的特征。本文提出的算法雖然壓縮率比osfs 算法稍差，但是在分類識別率方面明顯優于osfs算法。

圖2 與osfs算法實驗結果對比

4.3.3 與Alpha_investing算法實驗結果對比

圖3 與Alpha_investing 算法相比較，本文提出的算法在11 個數據集上得到更高的分類正確率，在另外1 個數據集上選出更少的特征個數，得到了相近的分類精度。本文提出的算法與Alpha_investing 算法對比，具有相近的壓縮率，同時具有更好的分類識別率。

圖3 與Alpha_investing算法實驗結果對比

4.3.4 與saola算法實驗結果對比

實驗中的saola算法參數alpha可取的值為0.01或0.05，alpha 值的選擇不會明顯的影響算法的結果。為了對比結果的方便，實驗中設置alpha=0.01。圖4 與saola 算法相比較，本文提出的算法在11 個數據集上得到的更好的分類精度。可以看出，在多數數據集上本文提出的算法識別性能更優，能得到更好的分類精度。同時在壓縮率上沒有明顯的劣勢，與saola算法大致持平。

與grafting，osfs，Alpha_investing 和saola 算法對比，可以得出結論，本文提出的sfs_l21 算法在壓縮率較低的情況下，識別率達到了較高的水平，在多數數據集上能得到最優的分類識別率。

圖4 與saola算法實驗結果對比

4.4 未知特征空間下的流特征選擇結果分析

在上述實驗中，使用的是已知特征空的數據集來驗證流特征選擇算法的實驗結果。為進一步研究流特征選擇算法在未知特征空間的情況下的算法性能，使用分類精度為標準來研究流特征選擇過程中算法的穩定性。實驗中選擇了6 個數據集，pixraw10P，TOX_171，SMK_CAN_187，Prostate_GE，arcene 和PCMAC 作為實驗數據集。同樣使用sklearn工具包中的線性svm算法做5折交叉驗證的平均分類精度作為評價標準。

從圖5 中可以看出，在特征逐個流入的過程中，本文提出的算法在pixraw10P，SMK_CAN_187和PCMAC 數據集上，當特征流入數據空間的比例到達50%之后，分類識別度都保持在所有算法中的最高水平。在arcene和Prostate_GE數據集上面，數據空間到達30%之后，分類識別率就已經高于其他算法。在TOX_171 數據集上也會在數據空間達到60%之后保持較高的分類識別率。由此可見，本文提出的算法不需要預先獲得整個特征空間的全部信息就可以達到最優分類精度，6 個數據集上均能持續保持較高的分類識別精度。

圖5 分類進度隨著特征數量的不斷流入而變化

可以得出結論，相比與grafting，osfs，Alpha_investing 和saola 算法，在未知空間的流特征選擇中，本文提出的算法在模型預測精度方面獲得了更高的和更穩定的性能。

4.5 參數分析

算法中引入兩個參數λ和ε，λ與特征選擇模型相關，ε控制選擇特征個數來間接影響分類精度，兩個參數相互獨立，互不干擾。通過固定其中一個參數值，考察另一個參數對分類精度的影響的方法來分析參數對算法影響。

4.5.1ε的影響分析

實驗中固定參數λ=0.2，考察ε在0.01～0.20范圍內變化對數據集SMK_CAN_171，GLIOMA，Prostate_GE 和arcene 選擇特征個數和分類識別率的影響。

圖6 參數ε 對4個數據集影響

圖7 參數λ 對4個數據集的影響

圖6 描述了隨ε值的增加，選擇的特征個數明顯減少，分類精度有下降的趨勢。可以看出，ε的選擇對選擇的特征個數和分類正確率是敏感的，對選擇特征個數敏感度較高。ε的經驗值設置為ε=0.05，此時分類精度和選擇特征個數可以達到一個權衡。ε對算法的影響受數據集的最優特征子集的規模大小影響較大。ε設置越小，選擇出的特征子集規模越大。

4.5.2λ的影響分析

實驗中，固定參數ε=0.05，考察λ在0.1～0.5范圍內數據集SMK_CAN_171，GLIOMA，Prostate_GE 和arcene 選擇特征個數和分類識別率的影響。

從圖7 可以看出，λ值的改變對數據集分類正確率和選擇特征個數影響較小，在4 個數據集上選擇出的特征個數和分類精度變化幅度較小，對算法的影響敏感度較低。

5 結語

針對流特征場景下的在線特征選擇問題，本文提出了基于?2，1約束的流特征選擇算法，可以有效地解決流特征下的在線特征選擇問題。通過對比實驗分析，本文提出的算法比現有流特征選擇算法在基因表達數據集上能選出更優的特征子集，使得分類精度較高，同時選擇的特征個數適中。實驗中分析了參數對算法的影響，算法對λ的敏感度較低，對ε的敏感度較高，ε可以顯著地影響選擇的特征數量，進而間接影響分類正確率。本文提出的流特征選擇算法能較好解決流特征場景下的特征選擇問題，在動態的、未知的特征空間中選擇出更優的特征子集。