吳中華 鄭 瑋

（南京理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

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

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

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

2 流特征選擇模型

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

定義t時刻的特征選擇損失函數(shù)為

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

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

本文使用?2，1范數(shù)作為約束條件，目標(biāo)函數(shù)可重寫為

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

3 流特征選擇算法

3.1 接收新特征

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

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

使用點ω的方向?qū)?shù)代表原點處目標(biāo)函數(shù)的方向?qū)?shù)。有：

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

式（5）可約簡為

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

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

接下來根據(jù)矩陣的求導(dǎo)法則，求出目標(biāo)函數(shù)對新到達(dá)特征的權(quán)重向量wt的梯度。對目標(biāo)函數(shù)做恒等變換：

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

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

這樣可以得到目標(biāo)函數(shù)對新特征權(quán)重向量的導(dǎo)數(shù)為

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

3.2 更新模型

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

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

3.3 算法框架

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

算法1 流特征選擇算法

輸入：X，Y，λ，ε

輸出：t時刻的最優(yōu)特征子集BFSt

1）Initial：BFSt=，Wt=1

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

3）While not convergence：

4）//在t時刻，新特征ft到達(dá)

5）ft=get_new_feature（）

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

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

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

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）//返回收斂后的最優(yōu)特征子集

16）ReturnBFSt

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

算法2 梯度檢驗（gradient validation）

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

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

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

2）//產(chǎn)生多個采樣方向

3）sample_directions=generate_sample_directions（ε）

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

5）for direction in sample_directions：

6）//計算目標(biāo)函數(shù)在采樣方向的導(dǎo)數(shù)

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

8） If grad*direction＜0：

9） Return True

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

11）Return False

4 實驗分析

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

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

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

表1 實驗中使用的數(shù)據(jù)集

4.2 數(shù)據(jù)預(yù)處理

為保持所有的特征在相似的尺度標(biāo)準(zhǔn)中，對每一個特征進(jìn)行歸一化到標(biāo)準(zhǔn)正態(tài)分布的處理。在特征選擇之前，將特征重新調(diào)節(jié)為標(biāo)準(zhǔn)正態(tài)分布。對于特征f，標(biāo)準(zhǔn)化之后的特征為

4.3 對比實驗

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

4.3.1 與grafting算法實驗結(jié)果對比

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

圖1 與grafting算法實驗結(jié)果對比

4.3.2 與osfs算法實驗結(jié)果對比

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

圖2 與osfs算法實驗結(jié)果對比

4.3.3 與Alpha_investing算法實驗結(jié)果對比

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

圖3 與Alpha_investing算法實驗結(jié)果對比

4.3.4 與saola算法實驗結(jié)果對比

實驗中的saola算法參數(shù)alpha可取的值為0.01或0.05，alpha 值的選擇不會明顯的影響算法的結(jié)果。為了對比結(jié)果的方便，實驗中設(shè)置alpha=0.01。圖4 與saola 算法相比較，本文提出的算法在11 個數(shù)據(jù)集上得到的更好的分類精度?？梢钥闯觯诙鄶?shù)數(shù)據(jù)集上本文提出的算法識別性能更優(yōu)，能得到更好的分類精度。同時在壓縮率上沒有明顯的劣勢，與saola算法大致持平。

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

圖4 與saola算法實驗結(jié)果對比

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

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

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

圖5 分類進(jìn)度隨著特征數(shù)量的不斷流入而變化

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

4.5 參數(shù)分析

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

4.5.1ε的影響分析

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

圖6 參數(shù)ε 對4個數(shù)據(jù)集影響

圖7 參數(shù)λ 對4個數(shù)據(jù)集的影響

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

4.5.2λ的影響分析

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

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

5 結(jié)語

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