基于Laplacian 的稀疏化特征選擇方法

吳錦華，萬家山，伍 祥

（安徽信息工程學院 計算機與軟件工程學院，安徽 蕪湖241000）

在機器學習和模式識別領(lǐng)域，傳統(tǒng)的學習算法在處理高維數(shù)據(jù)（如生物特征數(shù)據(jù)、基因數(shù)據(jù)、股票交易數(shù)據(jù)等）時，經(jīng)常會遭遇到“維數(shù)災難”問題[1]。為解決這一問題，目前主要有兩類方法：一類是偏向于高維數(shù)據(jù)的有效表示，如特征選擇、特征提取、稀疏表示等傳統(tǒng)數(shù)據(jù)降維算法；另一類是偏向于構(gòu)建學習模型，如分類回歸模型、聚類模型等，最終的學習模型用于數(shù)據(jù)的預測和分析。筆者通過提出特征選擇方法構(gòu)建分類回歸學習模型，并分析最終的分類性能來檢驗所提方法的有效性。

近些年來，特征選擇方法得到了很多研究人員的關(guān)注，旨在從高維數(shù)據(jù)中提取出有效表示形式，從而為目標學習模型提供幫助。目前特征選擇方法主要有Laplacian Score（LS）[2]、遞歸特征消除法（RFE）[3]、順序向前移動選擇（SFFS）[4]、Fisher Score（FS）[5]、Lasso[6]等，在這些特征選擇算法當中，基于稀疏表示的特征選擇方法得到了廣泛關(guān)注和研究，如Lasso 方法模型中，引入的稀疏項保證有價值的特征能被選擇，并且Lasso 方法模型同時進行回歸分析。然而，該方法在處理高維數(shù)據(jù)時計算速度比較慢，Tibshirani R 等人[7]在Lasso 方法模型的基礎(chǔ)上進行了改進，提出的Fussed Lasso 方法能夠?qū)τ嬎闼俣葍?yōu)化。除此之外，Jie 等人[8]為了解決多模態(tài)分類中的問題，利用Lasso 方法模型的稀疏項，并引入正則化項，提出一種基于流形正則化的多任務(wù)特征選擇方法（M2TFS）。吳錦華等人[9]在Lasso 模型的基礎(chǔ)上，引入判別性正則化項，提出新穎的判別性特征選擇方法。同樣為解決非線性問題，相關(guān)研究人員在Lasso 方法的基礎(chǔ)上引入核函數(shù)并取得不錯效果[10]。在實際應(yīng)用中，Conrad T O F 等人提出一種稀疏蛋白質(zhì)組分析算法（SPA）[11]用于獲取最小判別集，劉宏偉等人[12]將距離特征應(yīng)用至蛋白質(zhì)的無序段建模。從上可以看出，現(xiàn)在很多方法模型利用稀疏理論相關(guān)知識解決一些問題，然而一個主要缺點是在線性映射過程中忽略了一些有用的樣本信息，而最新研究表明，利用數(shù)據(jù)集的判別上下文和聚集多尺度特征可實現(xiàn)更好的模型分類[13]。

為解決上述問題，并受相關(guān)研究工作的啟發(fā)[8－9，13－15]，文中提出了一種特征選擇方法Lap-Spa-Lasso，方法模型中充分保存了樣本之間的結(jié)構(gòu)信息，從而幫助選出更具判別能力的特征。具體而言，Lap-Spa-Lasso 方法模型中方法首先包含一個稀疏正則化項，用于保證只有少數(shù)具有代表性的特征能被選擇。另外引入的Laplacian 正則化項用于保存數(shù)據(jù)集中同類樣本之間的結(jié)構(gòu)信息。進一步，為了提升實驗運行速度，采用加速近似梯度（Accelerated Proximal Gradient，APG）[16－18]算法來優(yōu)化提出的方法模型的求解過程。最后，在8 個數(shù)據(jù)集上對所提出的方法模型進行實驗驗證，并對實驗結(jié)果進行了分析。

論文的組織如下：第一部分簡單介紹Lasso 方法模型；第二部分給出所提方法模型及相應(yīng)的優(yōu)化算法；第三部分給出實驗方法、參數(shù)設(shè)置和運行環(huán)境；第四部分給出了實驗結(jié)果以及結(jié)果數(shù)據(jù)分析；最后部分對全文進行總結(jié)和后續(xù)工作的展望。

1 Lasso 方法

Lasso 方法最早是Robert Tibshirani 提出[6]，具體描述如下：

首先，給定訓練樣本集X＝[x1，x2，…，xN]∈Rd×N，其中xi表示樣本中的第i 個特征向量，N 表示樣本的數(shù)量，d 表示樣本特征維數(shù)。Y＝[y1，y2，…，yN]∈RN表示類標簽向量。在全監(jiān)督分類問題中，yi表示第i 個樣本的類標簽，其值可以為離散值或具體數(shù)值。在文中，為簡單處理，只考慮兩類分類問題，因此,yi∈{-1，+1}。而且通常情況下，Lasso 方法優(yōu)化的目標函數(shù)如下

其中w 表示特征向量的回歸系數(shù)，維數(shù)為d。正則項｜｜w｜｜1為L1-范式，用于在高維特征空間中產(chǎn)生稀疏解，如wi為不相關(guān)或冗余特征，則wi會被置零，而w 中保留的非零系數(shù)表示為樣本中有效的特征，可以用于后續(xù)的分類。其中，λ 是正則項的參數(shù)且大于0，主要用于平衡模型復雜度和數(shù)據(jù)擬合程度之間的相對貢獻，其值通?？赏ㄟ^交叉驗證來獲取。

2 Lap-Spa-Lasso 方法

在Lasso 及其擴展的相關(guān)模型中，一般統(tǒng)一采用線性函數(shù)f（x）=xTW=WTx將原始數(shù)據(jù)從高維映射到一維，但僅僅考慮了樣本和對應(yīng)標簽之間的關(guān)聯(lián)，卻忽略了樣本數(shù)據(jù)之間的內(nèi)在關(guān)聯(lián)關(guān)系，如同種類型樣本，經(jīng)過投影后可能也會產(chǎn)生比較大的偏差，即將原始數(shù)據(jù)從高維映射到一維可能會出現(xiàn)很大位置上的偏差；然而在理論上，如果兩個樣本為同一個類，它們通過映射后應(yīng)靠更近。為了解決這個問題，在所提方法中引入Laplacian 正則化項

公式中，S=[Sij]為近似矩陣，主要用于刻畫樣本之間的相似程度，經(jīng)過簡單步驟的數(shù)學推導而得到的正則化項。L=D-S為Laplacian 矩陣，D為對角矩陣，其中近似矩陣S可以被定義如下

該項可進行如下描述：如果兩個樣本xi和xj來自于同類，那么其經(jīng)過映射后的距離就更??；如果來自于不同類，那么之間的距離就會更大。在某種意義上，公式（2）主要保存通過線性函數(shù)映射后同類樣本數(shù)據(jù)之間的特征空間分布信息，而該分布信息可以提高方法模型的分類性能[9，19]。因此，文中提出一種基于Laplacian稀疏化特征選擇方法，稱為Lap-Spa-Lasso，其目標函數(shù)如下

其中λ＞0 和β＞0 為調(diào)諧參數(shù)，它們的值可以在訓練數(shù)據(jù)的過程中通過交叉驗證來確定。兩個參數(shù)主要用于平衡稀疏項和Laplacian 正則項之間的相對貢獻度。

在所提方法模型中，Lasso 稀疏項主要用于選擇少量有效特征，而Laplacian 正則化項用于保留同類標簽樣本之間內(nèi)在的結(jié)構(gòu)分布信息，從而幫助方法模型選出更具有判別能力的特征集，為后續(xù)分類器提供最有效特征。

3 方法求解優(yōu)化算法

為對方法模型進行求解，文中采用加速近似梯度（Accelerated Proximal Gradient，APG）[16－18]來優(yōu)化所提出的方法模型。具體而言，首先，目標函數(shù)（4）被劃分為兩部分，即平滑部分

和非平滑部分

記得之前在家時，每隔六個多月，我和母親就忙著買回一大堆一模一樣的衣服。大家都穿一樣的東西比較容易分配，可無畏派截然不同。每位無畏者每月都會購置不同的東西，其中當然包括不重樣的衣服。我和克里斯蒂娜跑過狹窄的通道，來到文身店。我們到的時候，艾爾已坐在椅子上，一個瘦小窄肩、身上有文身的地方比沒文的地方還多的男人正小心翼翼地在他手臂上文蜘蛛。

其次，構(gòu)造函數(shù)Ωl來對f（w）+g（w）公式進行求近似解

其中，▽f（wk）是第k 次迭代的wk點的梯度，l 是步長，其值可以通過線性搜索的方式來確定。APG 中w 的更新步驟可被定義如下

其中vk＝wk－（1/l）▽f（wk）。

因此，根據(jù)公式（8），求解優(yōu)化的問題可以被劃分成d 個獨立的子問題。APG 算法的關(guān)鍵是如何對這些獨立的子問題進行求解。根據(jù)文獻[16－17]得知，這些子問題的解析解比較容易求取，即

另外，根據(jù)文獻[17]使用的技巧，文中通過計算如下搜索點來代替在wi上的梯度下降。

以下算法描述總結(jié)了APG 算法優(yōu)化所提方法模型求解過程的細節(jié)，其具體過程如下：

輸入：令X＝[x1，x2，…，xN]∈Rd×N表示包含有N 個訓練樣本的數(shù)據(jù)集，其中d 是樣本的特征維數(shù)。令Y＝[y1，y2，…，yN]∈RN表示每個樣本所對應(yīng)的類標簽，其中每個樣本所對應(yīng)的標簽yi∈{-1，+1}。

輸出：J*

初始化： β≥0，λ≥0，0≤η≤1，l0＞0，w0＝w1＝0，ρ0＝1

For i＝1 to 最大迭代次數(shù)n

1）： 根據(jù)公式（10）計算搜索點Qi

2）： l=li-1；

3）： while

f（wi+1）+g（wi+1）＞Ωl（wi+1，Qi），l=σ*l

通過公式（8）計算wi+1

4）： li=l

End 計算J*={j|wj≠0}

4 實驗及結(jié)果分析

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

文中，實驗在6 個標準UCI 數(shù)據(jù)集上和2 個基因表達式數(shù)據(jù)上來驗證Lap-Spa-Lasso 方法的有效性，表1 中給出了樣本數(shù)據(jù)的特征維數(shù)和樣本個數(shù)。

表1 實驗數(shù)據(jù)集

4.2 實驗設(shè)置

為了驗證所提方法的有效性，實驗采用10 折交叉驗證法。在實驗過程中，將樣本均等的劃分為10 份，其中9 份用于訓練模型，并將其中的1 份用于測試，這個過程重復10 次。最后，將平均分類精度作為結(jié)果。在實驗過程中，為了驗證所提方法的適用性，基于RBF 核支持向量機[19]（SVM）、線性核支持向量機以及KNN核進行分類，并分析其在三種分類器下的性能表現(xiàn)。

4.3 實驗結(jié)果

為評價提出的方法，首先比較Lasso 的特征選擇方法，同時也比較了經(jīng)典的基于特征排名特征選擇方法，包括LS、FS、SFFS 和MMFS_ED[20]方法。表2 中總結(jié)了所有方法在8 個數(shù)據(jù)集上的分類結(jié)果。從表2 可以看出，所提方法效果都要優(yōu)于Lasso 方法，表明提出的Lap-Spa-Lasso 方法誘導出了更具有判別力特征，以完成更好的分類性能，間接驗證了引入的正則化項在分類過程中的重要性。另外，在大部分數(shù)據(jù)上所提出的方法都要優(yōu)于參與比較的方法，這進一步表明了提出方法的有效性。除此之外，論文在線性核分類器和KNN分類器上驗證了所提方法的分類性能，從表3、表4 中可以看出，所提方法都要優(yōu)于Lasso 方法，且在大多數(shù)數(shù)據(jù)集上都有優(yōu)于傳統(tǒng)的特征選擇方法，也說明了所提方法具有很好的推廣性。

表2 不同特征選擇方法在RBF 核上的平均分類精度（±標準差） 單位：%

表3 線性核分類器下不同特征選擇方法的平均分類精度（±標準差） 單位：%

表4 KNN 分類器下不同特征選擇方法的平均分類精度（±標準差） 單位：%

文中所提的方法中，當參數(shù)β=0 時，方法模型將退化成傳統(tǒng)的Lasso 方法。為分析所引入的Laplacian 正則化項的有效性，在8 個數(shù)據(jù)集上進行實驗驗證。圖1（a）、（b）給出了在數(shù)據(jù)集ionosphere 和colic 上的實驗結(jié)果。從圖1 中可以看出，所提方法在不同的參數(shù)λ 上和不同的數(shù)據(jù)集上的分類精度都要優(yōu)于Lasso 方法，除此之外，所提方法所對應(yīng)的曲線相對Lasso 方法顯得更加平穩(wěn)，即分類性能對參數(shù)魯棒，受參數(shù)變化的影響較小。

圖1 固定β 變化λ 時，所提方法Lap-Spa-Lasso 在2 個數(shù)據(jù)集上的分類精度

除此之外，分析了固定λ 變化β時提出Lap-Spa-Lasso 方法在8 個數(shù)據(jù)集上的分類精度。圖2 畫出了在8個數(shù)據(jù)集上隨不同β 值，所提方法分類精度的變化曲線。由圖2 中的曲線分析可見，不同的β 值下所取得的分類結(jié)果基本都要好于β=0 時的結(jié)果，進一步表明增加Laplacian 正則化項能提升模型性能。除此之外，圖2 中絕大數(shù)曲線變化趨勢都相對比較平穩(wěn)，說明該模型對參數(shù)β 也比較魯棒。綜上所述，所提方法對模型中的參數(shù)魯棒，受參數(shù)變化的影響小。

圖2 固定λ 變化β 時，所提方法Lap-Spa-Lasso 在8 個數(shù)據(jù)集上的分類精度

5 結(jié)語

文中提出一種特征選擇方法模型Lap-Spa-Lasso。該方法利用Laplacian 正則化項保留同類樣本的幾何分布信息，結(jié)合Lasso 方法的稀疏項構(gòu)造Lap-Spa-Lasso 方法模型。在8 個數(shù)據(jù)集上進行了有效性實驗，并分析在不同參數(shù)變化下所提方法的性能表現(xiàn)。除此之外，所提方法在三類分類器（即RBF 核分類器、線性分類器和KNN 分類器）上進行了實驗，從分類精度上可以看出所提方法都要優(yōu)于未引入正則項的Lasso 方法，說明了所提方法有很強的性能表現(xiàn)，從而說明引入正則化項不僅僅能改善分類器性能，而且具有很好的推廣性能。然而，所提的特征選擇方法最終是需要應(yīng)用到實際場景中，進一步工作將所提方法應(yīng)用至醫(yī)學圖像分析、生物標識數(shù)據(jù)分析中。