張樂園，李佳燁，李鵬清

(廣西師范大學(xué) 計算機科學(xué)與信息工程學(xué)院，廣西 桂林 541004))(*通信作者電子郵箱zhang7681193@163.com)

0 引言

圖像處理[1-2]和數(shù)據(jù)挖掘等領(lǐng)域常用高維的矩陣來存儲數(shù)據(jù)[3]。高維的矩陣在存儲大量信息的同時，也會帶來屬性冗余、占用大量存儲空間等問題。為了能夠提取這些數(shù)據(jù)的有效信息，并提升處理效率，需要對這些數(shù)據(jù)進行預(yù)處理。因此屬性約簡成為了越來越重要的一個研究領(lǐng)域[4]。

屬性選擇是常見的屬性約簡方法。它主要是按照某種標(biāo)準(zhǔn)從紛繁雜亂的屬性中選出能夠最好表示出數(shù)據(jù)的原始屬性的子集。屬性選擇廣泛應(yīng)用于模式識別、機器學(xué)習(xí)以及其他領(lǐng)域中[5-6]。之前的大部分研究都是基于線性條件下的屬性選擇，然而現(xiàn)實生活中的數(shù)據(jù)之間往往不是恰好線性的關(guān)系，有時需要去更多地考慮數(shù)據(jù)之間的非線性關(guān)系，因此可以引入核函數(shù)來實現(xiàn)非線性的屬性選擇[7]。

本文提出了一種基于核函數(shù)的屬性自表達(dá)無監(jiān)督屬性選擇算法——低秩約束的非線性屬性選擇算法(Low Rank Non-linear Feature Selection algroithm, LRNFS)。首先,用核函數(shù)將數(shù)據(jù)的每個屬性映射到核空間上，在核空間中這些數(shù)據(jù)是線性可分的，然后在核空間上進行線性屬性選擇，即相當(dāng)于進行了非線性屬性選擇[8]。其次用得到的屬性核矩陣去作屬性選擇，同時通過屬性自表達(dá)和偏差項得到一個自表達(dá)矩陣[9]，去解決無監(jiān)督屬性選擇方法中無類標(biāo)簽的問題；然后在線性回歸的模型框架中進行低秩屬性選擇，其中低秩屬性選擇運用了稀疏(利用l2,1-范數(shù)來去除冗余的屬性)和低秩(假設(shè)矩陣具有低秩，以此來排除噪聲的干擾)兩種方法[9]。最后，提出一種新的優(yōu)化方法，即對目標(biāo)函數(shù)按順序迭代執(zhí)行低秩屬性選擇和l1-范數(shù)處理[10]的優(yōu)化求解算法，不斷交替迭代使得結(jié)果達(dá)到最優(yōu)，最終取得全局最優(yōu)解。由于本文引入了核函數(shù)進行非線性屬性選擇，所以比一般的線性屬性選擇學(xué)習(xí)方法具有更好的效果。實驗結(jié)果表明，所提算法在分類準(zhǔn)確率上能夠達(dá)到較好的效果。

1 相關(guān)工作

參考模式識別理論[11]可知，低維空間中線性不可分的數(shù)據(jù)可以通過映射到高維空間中去實現(xiàn)線性可分。但是如果直接將低維數(shù)據(jù)映射到高維空間上進行機器學(xué)習(xí)的相關(guān)工作，將在高維空間上運算中出現(xiàn)“維數(shù)災(zāi)難”[12]，因此引入核函數(shù)這一概念來降低其計算復(fù)雜度。

設(shè)x,z∈X,X?Rn，非線性函數(shù)Φ實現(xiàn)低維數(shù)據(jù)集X到高維空間F上的映射，這里F?Rm,n?m。由核方法可得：

K(x,z)=〈Φ(x),Φ(z)〉

(1)

其中：〈,〉為內(nèi)積；K(x,z)為核函數(shù)。引入式(1)中核函數(shù)可以巧妙地把高維空間上的內(nèi)積運算轉(zhuǎn)化成低維空間上的計算，因此可以避免高維空間中高計算復(fù)雜度等問題，這樣可以實現(xiàn)在高維空間中的一些機器學(xué)習(xí)問題。

依據(jù)Mercer定理，去確定一個核函數(shù)并不難[11]。常用的核函數(shù)有如下幾種：

1)高斯核函數(shù)K(x,xi)=exp(-‖x-xi‖2/(2σ2))；

2)多項式核函數(shù)K(x,xi)=(x·xi+1)d,d=1,2,…,N；

3)感知器核函數(shù)K(x,xi)=tanh(βxi+b)；

4)樣條核函數(shù)K(x,xi)=B2n+1(x-xi)。

目前，核函數(shù)在機器學(xué)習(xí)領(lǐng)域已經(jīng)得到廣泛的應(yīng)用，它具有以下優(yōu)點：

1)避免了“維數(shù)災(zāi)難”，降低了計算復(fù)雜度；

2)函數(shù)Φ的具體形式和參數(shù)不需要知道；

3)核函數(shù)通過其形式和具體參數(shù)的調(diào)整可以改變低維空間到高維核空間的映射，從而對高維核空間的性質(zhì)產(chǎn)生影響，最終改變各種核方法的性能；

4)核方法可以應(yīng)用到不同的算法中，從而將一些線性算法轉(zhuǎn)換為非線性的算法，并且可以對于不同的應(yīng)用選取不同的核函數(shù)。

2 算法介紹與優(yōu)化

2.1 符號表示

用K(i)表示第i個屬性映射到高維核空間上所對應(yīng)的核矩陣。對于一個矩陣X=[xij]，它的第i行和第j列表示為Xi和Xj。矩陣X的跡表示為tr(X),XT代表矩陣X的轉(zhuǎn)置。同時，把矩陣X的Frobenius范數(shù)和l2,p-范數(shù)分別表示為：

2.2 LRNFS

一般情況下，作屬性選擇時，通常把一個數(shù)據(jù)集表示為X∈Rn×d的形式，在有監(jiān)督學(xué)習(xí)情況下，屬性選擇模型[9]為：

(2)

其中φ(W)是關(guān)于W的正則化因子。大部分情況下，數(shù)據(jù)之間的關(guān)系都不剛好是線性關(guān)系，式(2)通常不能表示出數(shù)據(jù)之間的非線性關(guān)系，因此需要引入核函數(shù)來對本文的目標(biāo)函數(shù)來進行改進。

參考廣義多核學(xué)習(xí)(Generalized Multiple Kernel Learning, GMKL)算法[8]，上面目標(biāo)函數(shù)可以變成:

K(i)∈Rn×n,Y∈Rn×c,W∈Rn×c,α∈Rd×1

(3)

這樣，W并不能起到對屬性進行選擇的作用，所以需要引入新的屬性選擇系數(shù)向量α，因此這里對W不用l2,1-范數(shù)，而是用l2-范數(shù)，它比較容易優(yōu)化。對于α用一個l1-范數(shù)去得到稀疏的結(jié)果，顯然，α是一個有d個元素的向量。如果α某個位置是0，對應(yīng)X的那個屬性就是被當(dāng)作冗余的屬性。

式(3)中的模型將數(shù)據(jù)的相似性和選擇特征一起考慮。盡管它被廣泛應(yīng)用于許多屬性選擇方法中，但很難去選擇合適的響應(yīng)矩陣。由于屬性的自表征性質(zhì)的存在，本文提出了一個用于無監(jiān)督屬性選擇的的正則化自表征模型。本文提出的模型簡單地利用矩陣X作為響應(yīng)矩陣，每個屬性可以被所有屬性很好地表示出來。對于每個X中屬性fi，將其表示為其他屬性的線性組合：

(4)

那么對于所有屬性有:

(5)

通過將每個屬性作為一項任務(wù)去預(yù)測，并使用l2,p-范數(shù)正則化項去約束任務(wù)之間的稀疏性。然后，定義了一個新的屬性自表征目標(biāo)函數(shù)如下：

λ2‖α‖1}

(6)

其中：λ1和λ2是控制參數(shù)，分別去影響系數(shù)矩陣W和向量α的稀疏性；l1-范數(shù)正則化項‖α‖1同時懲罰α中所有的元素去實現(xiàn)在屬性選擇向量α的稀疏來作出屬性的選擇和不選擇的決定；p(0

在實際應(yīng)用中，通常會發(fā)現(xiàn)噪聲或異常數(shù)據(jù)會增加自表征系數(shù)矩陣的秩[13]，所以，低秩約束在處理高維數(shù)據(jù)時就顯得特別合理。對W的秩施加約束[13]，即：

rank(W)=r；r≤min(n,d)

(7)

其中：n和d分別是樣本和屬性的數(shù)量。這樣，對于W的低秩約束可以自然地表示為如下兩個r秩矩陣的乘積：

W=AB

(8)

其中：A∈Rd×r,B∈Rr×d。那么最終的目標(biāo)函數(shù)變?yōu)椋?/p>

λ2‖α‖1}

(9)

其中：X∈Rd×r；λ1、λ2都是可調(diào)節(jié)參數(shù)。

2.3 優(yōu)化過程

這一節(jié)給出目標(biāo)函數(shù)式(9)的優(yōu)化過程。由于本文用l2,p-范數(shù)去除異常值樣本以及用l1-范數(shù)去實現(xiàn)屬性選擇，目標(biāo)函數(shù)不能求出一個閉式解。同時，對于4個變量A、B、b、α，目標(biāo)函數(shù)不是共凸的。因此，參照具有收斂速度快、逼近真實值等優(yōu)點的迭代重新加權(quán)最小二乘法(Iteratively Re-weighted Least Squares, IRLS)[14]的思想，本文提出了一種新的用A、B、b、α迭代優(yōu)化的方法。詳細(xì)地說，本文迭代地執(zhí)行以下三個步驟直到滿足預(yù)定條件。

1)用固定的α、A、B更新b。

當(dāng)α、A、B被固定，目標(biāo)函數(shù)式(9)中的后面兩項都可以被看作常數(shù)，其關(guān)于b的導(dǎo)數(shù)自然為0。將目標(biāo)函數(shù)式(9)對b進行求導(dǎo)，令其為0：

(10)

經(jīng)過簡單計算得出：

b=(eTX-eTZAB)/n

(11)

2)用固定的α、b更新A、B。

把式(11)帶入式(9)可以得到：

λ1‖AB‖2,p}

(12)

令H=In-eeT/n,H∈Rn×n,In∈Rn×n是一個單位矩陣，式(12)可以重寫為：

(13)

λ1tr(BTATQAB)

(14)

式中：P∈Rn×n,Q∈Rd×d，是兩個對角矩陣。其中：

i=1,2,…,n,0

(15)

(16)

對B求導(dǎo),令其為0可以得到：

B=(AT(ZTHTPHZ+λ1Q)A)-1ATZTHTPHX

(17)

把式(17)代入式(14)可得：

λ1Q)A)-1ATZTHTPHXXTHTPTHZA

(18)

注意到：

St=ZTHTPHZ+λ1Q

(19)

Sb=ZTHTPHXXTHTPTHZ

(20)

式中：St和Sb分別是線性判別分析(Linear Discriminant Analysis, LDA)中定義的總類散布矩陣和類間散布矩陣。因此式(18)的解可以寫成：

(21)

3)用固定的A、B、b更新α。

(22)

令K(i)W=Q(i)∈Rn×d,式(22)等價為：

λ2‖α‖1}

(23)

(24)

λ2‖α‖1}

(25)

(26)

(27)

令：

式(27)可以記為:

F(α)=f(α)+λ2‖α‖1

(28)

α的l1-范數(shù)使用一般的方法并不能得優(yōu)化出來，這里使用加速近端梯度下降(Accelerated Proximal Gradient Descent, APGD)算法[10，15]來對α的l1-范數(shù)進行優(yōu)化求解，具體過程如下：

(29)

Gηt(α,αt)=f(αt)+〈▽f(αt),α-αt〉+

ηt‖α-αt‖2/2+λ2‖α‖1

(30)

λ2‖α‖1/ηt}

(31)

令Ut=αt-▽f(αt)/ηt,有：

λ2‖α‖1/ηt}

(32)

令αi表示α的i第個分量，將式(31)按照分量展開可以看出，其中不存在αiαj(i≠j)這樣的項，所以式(31)有如下閉式解：

(33)

同時，為了加速式(29)中的近似梯度法，本文進一步引入輔助變量V(t+1)，即:

V(t+1)=α(t)+(α(t+1)-α(t))(β(t)-1)/

β(t+1)

(34)

其中系數(shù)β(t+1)通常設(shè)置為:

(35)

至此，對于目標(biāo)函數(shù)式(9)的優(yōu)化已經(jīng)完成，可由下面的算法1給出其具體的偽代碼。

算法1 求解式(9)的偽代碼。

輸入η(0),β(1)=1,γ,X∈Rn×d，λ1,λ2,p,r；

輸出α。

初始化t=1;

隨機初始化α(1)∈Rd×1，P(1)為一個n×n對角陣，Q(1)為一

個d×d對角陣，令V(1)=α(1)；

repeat；

更新A(k+1)基于式(21)；

更新B(k+1)基于式(17)；

更新b(k+1)基于式(11)；

計算P(k+1)基于式(15)；

計算Q(k+1)基于式(16)；

whileF(α(t))>Gη(t-1)(πη(t-1))(α(t),α(t)) do

setη(t-1)=γη(t-1)；

end while

setη(t)=η(t-1)；

計算β(t+1)基于式(35)；

計算V(t+1)基于式(34)；

t=t+1；

unitil式(9)收斂。

2.4 收斂性證明

下面說明α優(yōu)化的收斂性。

定理1 設(shè){α(t)}是由算法1產(chǎn)生的序列，那么對于?t≥1，式(36)成立:

(36)

定理1的證明詳見文獻(xiàn)[16]。定理1表明本文所用的加速近似梯度算法的收斂率為O(1/t2)，其中t是算法1的迭代次數(shù)。

接下來可以證明式(13)中的目標(biāo)函數(shù)值在每次迭代中單調(diào)遞減。目標(biāo)函數(shù)式(13)等價于：

λ1tr(BTATQAB)

(37)

即要證明：

tr((HX-HZA(t+1)B(t+1))TP(t)(HX-HZA(t+1)B(t+1)))+

λ1tr((B(t+1))T(A(t+1))TQA(t+1)B(t+1))≤

tr((HX-HZA(t+1)B(t+1))TP(t)(HX-HZA(t)B(t)))+

λ1tr((B(t))T(A(t))TQA(t)B(t))

(38)

令Y=HX-HZAB，然后可以得到：

(39)

對于每個i，能夠得到如下不等式：

(40)

對于每個j，可以得到：

(41)

由式(40)和式(41)可得：

(42)

然后合并式(39)和式(42)可得：

(43)

得證

通過上面分析可以看出，每次迭代過程中目標(biāo)函數(shù)式(9)的值是單調(diào)遞減的，同時目標(biāo)函數(shù)式(9)對于A、B、b是凸函數(shù)，因此依據(jù)式(38)以及定理1可以得出目標(biāo)函數(shù)式(9)會逐漸收斂到全局最優(yōu)解。

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

3.1 實驗數(shù)據(jù)集和對比算法

本文在6個數(shù)據(jù)集[17]上測試所提出的屬性選擇算法的性能，Glass、Hill-Valley1(含有大量噪聲)、Hill-valley2(沒有噪聲)、Yale、Colon、Arrhythmia數(shù)據(jù)集詳情如表1所示。

所有實驗均在Windows 7系統(tǒng)下使用Matlab 2014a軟件進行測試。選擇5種對比算法來與本文算法LRNFS進行比較，有：

1)LDA[18]：是一種全局子空間學(xué)習(xí)方法，旨在最大限度地減少類間距離，同時在進行特征選擇時最大化類間距離。

2)結(jié)構(gòu)化最優(yōu)圖特征選擇(Structured Optimal Graph Feature Selection, SOGFS)算法[19]：給出了一種進行特征選擇和保持局部結(jié)構(gòu)學(xué)習(xí)的無監(jiān)督屬性選擇算法，同時適應(yīng)性地去確定相似度矩陣，對相似度矩陣的限制可以保留更多的數(shù)據(jù)結(jié)構(gòu)的信息。

3)重新調(diào)整的線性平方回歸(Rescaled Linear Square Regression, RLSR)算法[20]：提出了一種可以學(xué)習(xí)投影矩陣的全局和稀疏解的新型半監(jiān)督特征選擇方法，在最小二乘回歸中用一組比例因子調(diào)整回歸系數(shù)，這些比例因子用于對各屬性進行排名。

4)正則化自表征(Regularized Self-Representation, RSR)算法[21]：通過范數(shù)來規(guī)范化自表征系數(shù)矩陣以選擇具有代表性的屬性，并確保對離群點的健壯性。

5)希爾伯特-施密特獨立標(biāo)準(zhǔn)壓縮(Hilbert-Schmidt Independence Criterion Lasso, HSICLasso)估計算法[22]:通過核函數(shù)的映射使得數(shù)據(jù)線性可分，同時用Lasso來對屬性權(quán)重向量進行稀疏，從而實現(xiàn)屬性約簡。

3.2 結(jié)果分析

本文采用分類準(zhǔn)確率作為評價指標(biāo)，分類準(zhǔn)確率越高表示算法效果越好，并且引入P_value進行算法之間的顯著性差異分析。實驗通過10折交叉驗證的方法把原始數(shù)據(jù)劃分為訓(xùn)練集和測試集，再使用LIBSVM工具箱[23]在支持向量機(Support Vector Machine, SVM)上對使用各算法進行屬性選擇之后的數(shù)據(jù)集進行分類，得出其分類準(zhǔn)確率。對于每個算法在每個數(shù)據(jù)集上進行10次實驗并取10次實驗結(jié)果的均值作為最終的分類準(zhǔn)確率，這樣可以降低實驗過程中的偶然性，并取其標(biāo)準(zhǔn)差來預(yù)測模型的穩(wěn)定性。

表1 實驗中使用的數(shù)據(jù)集Tab. 1 Datasets used in the experiment

在各數(shù)據(jù)集上不同算法進行屬性選擇之后的分類準(zhǔn)確率如圖1所示。由圖1可以看出，LRNFS在絕大多數(shù)情況下是優(yōu)于對比算法的。由于Hill-Valley1數(shù)據(jù)集中含有大量噪聲，所以各算法的分類準(zhǔn)確率的波動比較大，導(dǎo)致有部分實驗中效果比對比算法略差，但整體還是優(yōu)于對比算法的，這點在表2中可以證實。

圖1 不同數(shù)據(jù)集上各算法的實驗結(jié)果Fig. 1 Experimental results of different algorithms on different datasets表2 不同屬性選擇算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率Tab. 2 Classification accuracy of different feature selection algorithms on different data sets

算法分類準(zhǔn)確率均值/%glassHill-Valley1Hill-valley2YalecolonArrhythmia分類準(zhǔn)確率標(biāo)準(zhǔn)差/%glassHill-Valley1Hill-valley2YalecolonArrhythmia平均準(zhǔn)確率均值/%平均準(zhǔn)確率標(biāo)準(zhǔn)差/%P_valueLDA69.6172.3475.0074.3664.5554.710.902.502.151.310.200.2168.431.200.0541SOGFS69.8172.3481.9073.5884.4070.531.002.501.041.070.870.9075.431.230.0030RLSR70.3972.5880.0973.5284.1070.570.961.421.421.581.190.6975.211.210.0046RSR70.1671.7381.5073.3984.2470.331.463.121.291.881.300.6275.231.610.0023HSICLasso68.0275.5680.9475.0983.2168.351.260.790.420.771.530.7175.200.910.0622LRNFS71.5774.1083.0876.2985.1071.671.282.821.151.221.080.5176.971.34—

各屬性選擇算法在不同數(shù)據(jù)集上的分類準(zhǔn)確率如表2所示。從表2可以看出，LRNFS的平均分類準(zhǔn)確率較傳統(tǒng)的LDA提升了12.48%，較SOGFS提升了2.04%，較RLSR提升了2.34%，較RSR和HSICLasso分別提升了2.31%和2.35%。SOGFS、RLSR和RSR均是近幾年性能較優(yōu)的屬性選擇算法，在使用徑向基函數(shù)(Radial Basis Function, RBF)核的SVM的情況下，本文方法的分類準(zhǔn)確率得到了明顯的提升。由此可以看出，LRNFS在屬性選擇的時候擁有較優(yōu)的性能。從P_value可以看出，由于LRNFS采用了LDA思想和HSICLasso中核函數(shù)方法，所以其P_value值分別達(dá)到了0.054 1和0.062 2，而與其余對比算法的P_value都在0.01以下。

4 結(jié)語

本文在線性屬性選擇的基礎(chǔ)上引入核函數(shù)，考慮了數(shù)據(jù)之間的非線性關(guān)系，并解決了數(shù)據(jù)在低維特征空間上線性不可分的問題，提升了屬性選擇的準(zhǔn)確率。但引入核函數(shù)的同時，計算復(fù)雜度增加了，這是需要進一步解決的問題，而且通過實驗結(jié)果可以看出，LRNFS的魯棒性還有待提升。接下來的工作中，將拓展LRNFS為半監(jiān)督屬性選擇算法，并逐步改進其計算復(fù)雜度和魯棒性。