呂治政，李揚(yáng)定，雷 聰

(廣西師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院,廣西 桂林 541004)

1 引言

隨著云計(jì)算和大數(shù)據(jù)技術(shù)的發(fā)展，大量高維數(shù)據(jù)易于獲取，高維數(shù)據(jù)隨處可見。高維特征數(shù)據(jù)樣本準(zhǔn)確且能夠多樣性地表現(xiàn)樣本的特性[1]，但由于其維數(shù)過(guò)高，不僅增大了數(shù)據(jù)存儲(chǔ)容量，而且在數(shù)據(jù)處理過(guò)程中容易導(dǎo)致“維數(shù)災(zāi)難”問(wèn)題[2]。屬性選擇技術(shù)的興起，使得其能夠按照某種評(píng)價(jià)指標(biāo)，選出最優(yōu)的屬性子集對(duì)數(shù)據(jù)進(jìn)行稀疏重構(gòu)，保持了數(shù)據(jù)內(nèi)在的關(guān)聯(lián)信息，使得分類器在低維子空間上進(jìn)行訓(xùn)練，很大程度上提高了在分類器上的訓(xùn)練效率和預(yù)測(cè)準(zhǔn)確率[3]。屬性選擇既可以使我們更加清楚地知道是哪種屬性導(dǎo)致了分類類別的不同，又可以有效地降低分類算法的計(jì)算復(fù)雜度，提高分類準(zhǔn)確率。

針對(duì)數(shù)據(jù)“維數(shù)災(zāi)難”問(wèn)題，我們真正要解決的就是數(shù)據(jù)降維，通俗地講就是屬性選擇。近幾年對(duì)于屬性選擇的研究主要集中在線性屬性選擇算法和非線性屬性選擇算法。Luebke等人[4]提出了一種新的線性自適應(yīng)屬性選擇算法，自適應(yīng)的屬性選擇算法的優(yōu)點(diǎn)是對(duì)數(shù)據(jù)屬性選擇分類任務(wù)處理過(guò)程是自適應(yīng)的，而且它也適用于各種數(shù)據(jù)類型的數(shù)據(jù)集，缺點(diǎn)就是在處理含有較多噪聲屬性的數(shù)據(jù)集時(shí)，從分類準(zhǔn)確率的角度，還需要對(duì)算法進(jìn)一步優(yōu)化。Magdalinos等人[5]提出了一種屬性選擇效果好且性能優(yōu)的屬性選擇算法，該算法的優(yōu)點(diǎn)是時(shí)間和空間復(fù)雜度小，但是目前該算法只在分類任務(wù)和聚類任務(wù)中得到了驗(yàn)證，在處理高維大數(shù)據(jù)集時(shí)需要進(jìn)一步加以驗(yàn)證。Lee等人[6]基于統(tǒng)計(jì)學(xué)的方法提出了一種“內(nèi)在”距離概念的屬性選擇算法。該算法的缺點(diǎn)是需要引入1個(gè)參數(shù)t，參數(shù)t的選取不是固定的，需要手動(dòng)調(diào)節(jié)，同時(shí)該方法需要在較大的數(shù)據(jù)集上進(jìn)一步驗(yàn)證?，F(xiàn)有的大多數(shù)關(guān)于屬性選擇的方法研究基本都是在傳統(tǒng)的方法上加以改進(jìn)，依然存在很大的局限性。在最近也有了一些其他的屬性選擇方法出現(xiàn)，如：最小二乘回歸、樣本依賴圖、圖優(yōu)化的局部保持投影等。然而這些方法對(duì)參數(shù)是非常敏感的，在實(shí)際問(wèn)題當(dāng)中參數(shù)值的選擇是非常困難的，特別在處理高維數(shù)據(jù)集時(shí)，參數(shù)選擇對(duì)實(shí)驗(yàn)結(jié)果的影響會(huì)很大，不能很好地反映屬性和類標(biāo)簽之間的關(guān)系。

本文針對(duì)以上問(wèn)題運(yùn)用了稀疏表示(Sparse Representation)的思想，提出一種基于核稀疏表示的屬性選擇算法KSFS(Feature Selection based on Kernel Sparse representation)。該算法將核函數(shù)與稀疏學(xué)習(xí)相結(jié)合，通過(guò)核函數(shù)將原始數(shù)據(jù)映射到高維核空間中，使得在低維空間線性不可分的數(shù)據(jù)，在高維核空間中具有更高程度的可分性[7]。同時(shí)，對(duì)核空間的高維數(shù)據(jù)進(jìn)行稀疏表示，按照評(píng)價(jià)指標(biāo)找出最優(yōu)的屬性子集，在一定程度上降低了分類算法的計(jì)算量，提高了分類算法的穩(wěn)定性和準(zhǔn)確率。具體地，該算法首先運(yùn)用核函數(shù)構(gòu)建與屬性相關(guān)聯(lián)的屬性核矩陣，屬性核矩陣數(shù)目與屬性數(shù)目一致，從而可以挖掘?qū)傩院司仃嚭皖悩?biāo)簽之間的非線性關(guān)系；同時(shí)利用L1范數(shù)有效地構(gòu)建屬性評(píng)分選擇機(jī)制來(lái)確定稀疏向量元素取值為0或非0，對(duì)應(yīng)著數(shù)據(jù)屬性的取舍(0代表不選此屬性)，得到原始數(shù)據(jù)集的一種稀疏表示方式；在算法優(yōu)化過(guò)程中引入了低秩約束方法，既去除了噪聲樣本和冗余屬性的影響，又考慮了數(shù)據(jù)之間的全局結(jié)構(gòu)，從而選出最優(yōu)的屬性結(jié)構(gòu)子集[2]。最終將最優(yōu)的屬性結(jié)構(gòu)子集用于分類實(shí)驗(yàn)得到分類準(zhǔn)確率。

2 相關(guān)理論背景及簡(jiǎn)介

2.1 核函數(shù)方法

只要任何1個(gè)對(duì)稱函數(shù)所對(duì)應(yīng)的核矩陣是半正定的，那么就可以稱之為核函數(shù)，可以通過(guò)核函數(shù)構(gòu)建原始樣本的1個(gè)高維特征空間——核空間。核函數(shù)的1個(gè)非常重要的作用就是將原始樣本在低維空間線性不可分的問(wèn)題轉(zhuǎn)化為高維核空間中的線性可分問(wèn)題[8]。

定義k(xi,xj)是在Rn×n上的對(duì)稱函數(shù)，則k是核函數(shù)當(dāng)且僅當(dāng)對(duì)于任意數(shù)據(jù)X∈Rn×d，“核矩陣”K總是半正定的，通過(guò)核函數(shù)k(xi,xj)，將數(shù)據(jù)集每1個(gè)列向量xi∈Rn×1=[x11,x21,…,xn1]T，i=1,2,…,d映射到核空間得到如下形式：

(1)

其中，K(i)∈Rn×n，i=1,2,…,d；m=1,2,…,n。

2.2 常見的核函數(shù)

常用的核函數(shù)主要有以下幾種形式：

多項(xiàng)式核:

(2)

線性核:

(3)

拉普拉斯核:

k(xi,xj)=exp(-‖xi-xj‖2/σ)

(4)

高斯核:

k(xi,xj)=exp(-‖xi-xj‖2/(2σ2))

(5)

2.3 核稀疏表示

稀疏表示理論由于具有堅(jiān)實(shí)的內(nèi)在理論和重要的實(shí)際應(yīng)用價(jià)值，使得稀疏表示得到了快速的發(fā)展，并且已經(jīng)在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等重要領(lǐng)域得到了廣泛的應(yīng)用。

在稀疏學(xué)習(xí)的基礎(chǔ)上，引入核函數(shù)將訓(xùn)練樣本數(shù)據(jù)X∈Rn×d分解成為d個(gè)列向量xi∈Rn×1,i=1,2,…,d，通過(guò)核函數(shù)k(xi,xj)將每1個(gè)列向量xi投影到核空間生成新的屬性核矩陣K(i)∈Rn×n,i=1,2,…,d，進(jìn)一步對(duì)核空間數(shù)據(jù)進(jìn)行稀疏表示，稱為核稀疏表示，即解決問(wèn)題：

(6)

其中，Y表示訓(xùn)練集類標(biāo)簽，W為系數(shù)矩陣，ε為最大誤差容忍變量。式(6)是一個(gè)典型的凸優(yōu)化問(wèn)題，可以通過(guò)優(yōu)化L1范數(shù)得到問(wèn)題的最優(yōu)解[9]。計(jì)算求解其最優(yōu)的稀疏向量α=[α1,α2,…,αd]T。

3 算法描述及優(yōu)化

3.1 算法描述

假設(shè)給定1個(gè)訓(xùn)練集X∈Rn×d，其中n和d分別表示訓(xùn)練集樣本數(shù)目和屬性數(shù)目，Y∈Rn×c表示訓(xùn)練集類標(biāo)簽，n和c分別表示類標(biāo)簽樣本個(gè)數(shù)和類標(biāo)簽類別數(shù)。通常情況下，在有監(jiān)督學(xué)習(xí)情況，屬性選擇的模型為：

(7)

其中,φ(W)是關(guān)于W∈Rd×c的正則化因子。式(7)通常情況下不能表示數(shù)據(jù)之間的非線性關(guān)系[10]，因此我們需要引入核函數(shù)，通過(guò)核函數(shù)把數(shù)據(jù)映射到高維核空間。理論已經(jīng)證明核空間的數(shù)據(jù)是線性可劃分的[9]，利用該方法在核空間上執(zhí)行線性的屬性選擇從而實(shí)現(xiàn)低維空間上的非線性屬性選擇。

本文結(jié)合核函數(shù)和稀疏學(xué)習(xí)模型，將訓(xùn)練樣本數(shù)據(jù)集X∈Rn×d分解成為d個(gè)列向量xi∈Rn×1，i=1,2,…,d，把列向量xi通過(guò)核函數(shù)k(xi,xj)投影到核空間生成新的屬性核矩陣K(i)∈Rn×n,i=1,2,…,d。對(duì)于整個(gè)數(shù)據(jù)集X∈Rn×d通過(guò)核函數(shù)映射會(huì)生成d個(gè)與屬性相關(guān)的核矩陣K(i)∈Rn×n，則核矩陣K(i)中的每1個(gè)元素為ki,j=k(xi,xj)，其中k(xi,xj)為高斯核函數(shù)，具體如式(5)所示，其中σ>0為核函數(shù)的帶寬。

由于屬性和類標(biāo)簽之間存在某種聯(lián)系，在此本文引入核函數(shù)考慮屬性與類標(biāo)簽之間的非線性關(guān)系，把類標(biāo)簽Y作為響應(yīng)矩陣，把X通過(guò)核函數(shù)投影后形成屬性核矩陣K(i),i=1,2,…,d，通過(guò)矩陣Z和屬性選擇系數(shù)αi來(lái)表示響應(yīng)矩陣Y與核矩陣K(i)之間的關(guān)系：

(8)

其中，Y∈Rn×c表示響應(yīng)矩陣，K(i)∈Rn×n表示核矩陣，Z∈Rn×c表示系數(shù)矩陣。

為了使式(8)等號(hào)右邊的式子盡量擬合響應(yīng)矩陣Y，用LF范數(shù)計(jì)算兩者之間的偏差，即可得到如下關(guān)系：

(9)

在式(9)基礎(chǔ)上引入Z的L2,p范數(shù)正則化項(xiàng)調(diào)整類標(biāo)簽和屬性核矩陣之間的關(guān)系，避免模型過(guò)擬合，減少計(jì)算誤差，因此可得到如下關(guān)系：

(10)

(11)

其中，λ1,λ2為控制參數(shù)，0

因?yàn)樵肼晿颖竞腿哂鄬傩詴?huì)增加系數(shù)矩陣的秩，所以假設(shè)rank(Z)=r≤min(n,d),低秩限制的Z可以表示為Z=AB，其中A∈Rn×r,B∈Rr×c。綜上所述，最后可以得到如下目標(biāo)函數(shù)：

s.t.rank(AB)≤min(n,d)

(12)

其中,K(i)∈Rn×n,Y∈Rn×c,AB∈Rn×c,α∈Rd×1，AB為重構(gòu)系數(shù)矩陣，α為屬性選擇向量。

本文提出的KSFS算法具有以下優(yōu)點(diǎn)：

(1)KSFS算法采用有監(jiān)督方式建立模型，在目標(biāo)函數(shù)中充分利用類標(biāo)簽信息，將類標(biāo)簽作為目標(biāo)函數(shù)的響應(yīng)矩陣，從而很好地考慮了類標(biāo)簽和屬性之間的相關(guān)性；其次，在線性回歸模型下引入低秩約束方法來(lái)去除一些噪聲和冗余數(shù)據(jù)，從而實(shí)現(xiàn)了子空間學(xué)習(xí)的效果；同時(shí)提高了模型對(duì)高維數(shù)據(jù)分類的準(zhǔn)確率。所以，KSFS算法相對(duì)于單一子空間學(xué)習(xí)方法具有更好的效果。

(2)KSFS算法在稀疏學(xué)習(xí)模型的基礎(chǔ)之上引入了核函數(shù)，通過(guò)核函數(shù)將原始數(shù)據(jù)映射到高維核空間，使得原始數(shù)據(jù)在高維核空間具有更高的可分性，在高維核空間上充分考慮了屬性與類標(biāo)簽之間的非線性關(guān)系，屬性選擇效果比在低維空間要好很多。

(3)KSFS算法在目標(biāo)函數(shù)中引入了向量α的L1范數(shù)，利用L1范數(shù)對(duì)模型具有很好的稀疏效果，從而使得稀疏向量α元素取值為0或非0，分別對(duì)應(yīng)著數(shù)據(jù)屬性的取舍(0代表不選此屬性)。所以，在模型中把L1范數(shù)作為屬性選擇評(píng)分機(jī)制會(huì)起到良好的屬性選擇作用。

本文算法的偽代碼如下所示：

算法1KSFS算法

輸入：訓(xùn)練集X∈Rn×d,Y∈Rn×c;正則化參數(shù)λ1,λ2;SVM分類器中參數(shù)(c,g)∈[-10:2:10]，分類器選擇非線性模式。

輸出：樣本分類準(zhǔn)確率。

步驟1根據(jù)目標(biāo)函數(shù)式(12)，調(diào)用算法2，求解目標(biāo)函數(shù)全局最優(yōu)解屬性選擇向量α；

步驟2根據(jù)最優(yōu)解向量α，對(duì)原始數(shù)據(jù)集X∈Rn×d進(jìn)行屬性選擇后得到的數(shù)據(jù)集，作為新的樣本數(shù)據(jù)集；

步驟3對(duì)新的樣本數(shù)據(jù)集樣本采用SVM分類。

3.2 算法優(yōu)化

目標(biāo)函數(shù)式(12)中需要優(yōu)化的3個(gè)參數(shù)分別是A,B,α。由于目標(biāo)函數(shù)中有L1范數(shù)的存在，且目標(biāo)函數(shù)是非凸的，所以需要去分步迭代求解最優(yōu)的參數(shù)A,B,α。

s.t.rank(AB)≤min(n,d)

(13)

根據(jù)矩陣論知識(shí)[11]，可以將目標(biāo)函數(shù)的每1項(xiàng)表示為如下形式:

(14)

λ1‖AB‖2,p=λ1tr(BTATDAB)

(15)

(16)

式(15)中的D∈Rm×m是一個(gè)對(duì)角矩陣，且D中的對(duì)角元素根據(jù)參考文獻(xiàn)[11,12]可知為如下形式：

dii=1/(2/p)(‖gi‖2)2-p

s.t.i=1,2,…,m;0

(17)

其中,gi表示矩陣AB的第i行。

那么我們的目標(biāo)函數(shù)可以進(jìn)一步表示為如下形式：

(18)

(1)固定α，優(yōu)化A,B。

由于優(yōu)化B的過(guò)程實(shí)質(zhì)是1個(gè)求導(dǎo)的過(guò)程，所以可以將目標(biāo)函數(shù)中不包含B的項(xiàng)視為常數(shù)項(xiàng)，即在求導(dǎo)時(shí)此項(xiàng)為零，且令目標(biāo)函數(shù)式(18)為J(A,B,α)，那么可以得到：

(19)

對(duì)B求偏導(dǎo)，并令其所得偏導(dǎo)數(shù)等于零：

ATDTA)B-2ATPTY=0

(20)

從式(20)可以求解得到B：

B=(AT(PTP+λ1D)A)-1ATPTY

(21)

然后,把求解得到的矩陣B代入目標(biāo)函數(shù)式(18)中可得到：

λ1‖A(AT(PTP+λ1D)A)-1ATPTY‖2,p+λ2‖α‖1

(22)

最后通過(guò)一系列的化簡(jiǎn)可以得到：

(23)

在固定α的同時(shí)，式(23)要達(dá)到最小值，那么需要：

(24)

從式(24)中注意到：

St=PTP+λ1D,Sb=PTYYTP

(25)

其中,St和Sb分別表示線性判別分析LDA(Linear Discriminant Analysis)中的類內(nèi)離散矩陣和類間離散矩陣，所以可以將式(25)代入式(24)求解得到A：

(26)

(2)固定A,B，優(yōu)化α。

因?yàn)橹皇莾?yōu)化α，所以可以將目標(biāo)函數(shù)式(12)進(jìn)一步化簡(jiǎn)展開為：

(27)

我們可以進(jìn)一步令K(i)AB=Q(i)∈Rn×c，那么式(27)可以表示為：

(28)

αTS(i)(S(i))Tα)+λ2‖α‖1?

(29)

式(29)中f(α)定義如下：

(30)

進(jìn)一步定義F(α)：

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

(31)

很明顯，f(α)是可導(dǎo)的，而且▽f(α)滿足L-Lipschitz條件，那么就存在1個(gè)常數(shù)L>0，使得：

(32)

則在第t次迭代的向量αt附近可將f(α)通過(guò)二階泰勒展開式近似為如下：

(33)

很顯然，式(33)的最小值在式(34)中取得：

(34)

通過(guò)梯度下降法[8]對(duì)f(α)進(jìn)行最小化，同時(shí)在每1步對(duì)f(α)進(jìn)行梯度下降迭代考慮α的L1范數(shù)最小化，最終可以得到使F(α)最小化的向量α，即可得到如下表達(dá)式：

αt+1=

(35)

定義Ut：

(36)

然后將其代入式(35)得：

(37)

(38)

根據(jù)以上目標(biāo)函數(shù)優(yōu)化過(guò)程，優(yōu)化算法能夠確保目標(biāo)函數(shù)值在每1次迭代過(guò)程中逐步收斂，最終獲取全局最優(yōu)解。

算法2優(yōu)化求解表達(dá)式(12)的偽代碼

輸入：訓(xùn)練集X∈Rn×d,Y∈Rn×c；屬性關(guān)聯(lián)結(jié)構(gòu)度參數(shù)p；正則化參數(shù)λ1,λ2；梯度下降參數(shù)L。

輸出：矩陣AB，屬性選擇向量α。

1.初始化t=0；

2.初始化矩陣A,D，α為單位向量；

3.計(jì)算屬性核矩陣K(i)∈Rn×n；

4.repeat

4.1.根據(jù)式(21)，更新B(t+1);/*表示第t+1次迭代的B*/

4.2.根據(jù)式(26)，更新A(t+1);/*表示第t+1次迭代的A*/

4.3.更新對(duì)角矩陣D(t+1);/*表示第t+1次迭代的D*/

4.4.根據(jù)式(37)和式(38)，更新α(t+1);

4.5.更新t=t+1;

4.6.Until目標(biāo)函數(shù)式(12)收斂；

5.end

4 算法收斂性證明

因?yàn)閺哪繕?biāo)函數(shù)式(12)中可以很清楚地看到它是非平滑的，它不僅有3個(gè)變量A,B,α需要優(yōu)化求解，而且它的正則化項(xiàng)也是非平滑的，所以在目標(biāo)函數(shù)收斂性證明上還是存在一定的難度。但是，本文提出了一種有效的方法，下面是目標(biāo)函數(shù)收斂性證明的具體過(guò)程。

從算法2中4.1到4.6迭代到第t次產(chǎn)生的結(jié)果：

〈A(t+1),B(t+1),α(t+1)〉=

λ1tr(BTATD(t)AB)+λ2‖α‖1

(39)

從而可以得到：

(40)

其中，令G(t)=A(t)B(t),G(t+1)=A(t+1)B(t+1)，由式(17)構(gòu)成的對(duì)角矩陣D，代入式(40)可以得到：

(41)

(42)

然后，結(jié)合式(42)就可以得到：

(43)

綜合以上所述，可以得到如下結(jié)果：

(44)

接下來(lái)，證明α優(yōu)化的收斂性。

定理1假設(shè){αt}是由算法1產(chǎn)生的序列，那么對(duì)于任意t≥1時(shí)，就有以下式子成立：

(45)

定理1的證明可以參考文獻(xiàn)[13]，該定理表明了近端梯度下降算法收斂計(jì)算復(fù)雜度為O(1/t2)，其中t表示的迭代次數(shù)，同時(shí)也表明了式(31)是收斂的。

結(jié)合以上不等式和定理1就能證明目標(biāo)函數(shù)是單調(diào)遞減的，所以目標(biāo)函數(shù)是收斂的。

5 相關(guān)理論實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)數(shù)據(jù)集和對(duì)比算法

本文采用了10個(gè)常用的做屬性選擇的數(shù)據(jù)集，并且在數(shù)據(jù)集上測(cè)試本文提出的KSFS算法和近幾年比較優(yōu)秀的屬性選擇對(duì)比算法，通過(guò)實(shí)驗(yàn)結(jié)果比較算法的性能和效果。實(shí)驗(yàn)數(shù)據(jù)集的具體相關(guān)信息如表1所示。

Table 1 Data set information statistics表1 數(shù)據(jù)集信息統(tǒng)計(jì)

本文所有實(shí)驗(yàn)都在Windows 7系統(tǒng)環(huán)境下運(yùn)行的，使用Matlab 2014a編譯器編寫實(shí)驗(yàn)算法和測(cè)試實(shí)驗(yàn)效果性能。對(duì)比實(shí)驗(yàn)選取了5種對(duì)比算法，將其實(shí)驗(yàn)所得的結(jié)果與本文提出的KSFS算法所的結(jié)果進(jìn)行比較。本文所有算法都采用10折交叉驗(yàn)證方法和選擇不同的參數(shù)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估，實(shí)驗(yàn)所選擇的分類器為Matlab工具箱中的SVM分類器，且分類器中參數(shù)(c,g)∈[-10:2:10]，分類器類型都選擇非線性模式。

以下分別介紹5種對(duì)比算法：

(1)FSPG(Feature Selection for linear SVM with Provable Guarantees)算法[14]：是一種改進(jìn)的SVM的屬性選擇算法。它可以用來(lái)做有監(jiān)督的學(xué)習(xí)算法，也可以用來(lái)做無(wú)監(jiān)督的學(xué)習(xí)算法，通過(guò)調(diào)節(jié)參數(shù)來(lái)選擇屬性選擇模型，從而確定它是有監(jiān)督的還是無(wú)監(jiān)督的，本文選擇有監(jiān)督學(xué)習(xí)模型作為對(duì)比算法。它是基于支持向量來(lái)提取特征的，在最壞的情況，保證了局部特征空間的邊緣距離在全局特征空間的邊緣距離誤差范圍之內(nèi)，從而達(dá)到屬性選擇的目的。

(2)Lasso(high-dimensional feature selection by feature-wise kernelized Lasso)算法[15]：是一個(gè)有監(jiān)督學(xué)習(xí)屬性選擇算法，是在輸入特征和輸出值之間建立一種非線性依賴關(guān)系來(lái)進(jìn)行高效的屬性選擇，其目的是通過(guò)引入核函數(shù)挖掘輸入特征數(shù)據(jù)與輸出值之間的非線性關(guān)系。通過(guò)求解非負(fù)約束的Lasso優(yōu)化問(wèn)題、對(duì)偶增廣拉格朗日方法有效地求解問(wèn)題，最終得到全局最優(yōu)解。

(3)FSSL(joint Feature Selection and Subspace Learning for cross-modal retrieval)算法[16]：是一種有監(jiān)督學(xué)習(xí)模型的算法。它是在跨模態(tài)檢索領(lǐng)域?yàn)榱私鉀Q數(shù)據(jù)相關(guān)性度量和特征選擇問(wèn)題所提出的一種屬性選擇算法，通過(guò)投影矩陣將數(shù)據(jù)投影到一個(gè)公共的子空間上，并在投影過(guò)程中同時(shí)選擇不同空間的相關(guān)性特征和判別特征，保證了數(shù)據(jù)間和數(shù)據(jù)內(nèi)的結(jié)構(gòu)相似性，此外在映射時(shí)引入L2,1范數(shù)正則項(xiàng)實(shí)現(xiàn)稀疏化，達(dá)到屬性選擇的效果。

(4)ERFS(Efficient and Robust Feature Selection via jointL2,1-norm minimization)算法[17]：是一種具有高效和魯棒性的有監(jiān)督屬性選擇算法。它的損失函數(shù)是基于L2,1范數(shù)回歸的損失函數(shù)，在數(shù)據(jù)特征提取和消除噪聲特征方面有很大作用。正則項(xiàng)部分也是基于L2,1范數(shù)，能夠?qū)λ袛?shù)據(jù)點(diǎn)特征進(jìn)行關(guān)聯(lián)性稀疏，從而實(shí)現(xiàn)特征選擇的效果。

(5)CSFS(a Convex formulation for Semi-supervised multi-label Feature Selection)算法[18]：是一種利用半監(jiān)督學(xué)習(xí)方式結(jié)合了稀疏學(xué)習(xí)模型，并引入L2,1范數(shù)的正則化項(xiàng)來(lái)進(jìn)行屬性選擇的算法。但是，并沒(méi)有考慮數(shù)據(jù)的全局結(jié)構(gòu)和屬性之間的關(guān)系，所以屬性選擇效果也不是很理想。

5.2 實(shí)驗(yàn)結(jié)果和分析

本文中對(duì)比算法的實(shí)驗(yàn)參數(shù)按照參考文獻(xiàn)設(shè)置，本文的KSFS算法實(shí)驗(yàn)相關(guān)參數(shù)分別有r，λ1∈{108,109,1010,1011},λ2∈{0.05,0.06,0.07,0.08,0.09}，L2,p范數(shù)中參數(shù)p取值為0

在進(jìn)行分類任務(wù)之前，在10個(gè)數(shù)據(jù)集上測(cè)試本文算法，同時(shí)也證明了本文 KSFS算法的目標(biāo)函數(shù)是收斂的。從圖1～圖10我們可以看出，本文提出的屬性選擇模型可以很好地?cái)M合屬性和類標(biāo)簽之間的關(guān)系，通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)梯度下降的參數(shù)在可控的范圍之內(nèi)，L選取最大值時(shí)，目標(biāo)函數(shù)的收斂速度越快，梯度下降參數(shù)L為10時(shí)，目標(biāo)函數(shù)的收斂速度是最快的，圖1～圖10是L為10時(shí)目標(biāo)函數(shù)在每個(gè)數(shù)據(jù)集上的收斂圖。

Figure 1 Convergence plot of the target function on Colon圖1 目標(biāo)函數(shù)在Colon上的收斂圖

Figure 2 Convergence plot of the target function on Ecoli圖2 目標(biāo)函數(shù)在Ecoli上的收斂圖

Figure 3 Convergence plot of the target function on Yale圖3 目標(biāo)函數(shù)在Yale上的收斂圖

Figure 4 Convergence plot of the target function on Isolets圖4 目標(biāo)函數(shù)在Isolets上的收斂圖

Figure 5 Convergence plot of the target function on PCMAC圖5 目標(biāo)函數(shù)在PCMAC上的收斂圖

Figure 6 Convergence plot of the target function on Madelon圖6 目標(biāo)函數(shù)在Madelon上的收斂圖

Figure 7 Convergence plot of the target function on Multiple圖7 目標(biāo)函數(shù)在Multiple上的收斂圖

Figure 8 Convergence plot of the target function on SECOM圖8 目標(biāo)函數(shù)在SECOM上的收斂圖

Figure 9 Convergence plot of the target function on CNAE圖9 目標(biāo)函數(shù)在CNAE上的收斂圖

Figure 10 Convergence plot of the target function on CCUDS圖10 目標(biāo)函數(shù)在CCUDS 上的收斂圖

實(shí)驗(yàn)采用樣本分類準(zhǔn)確率作為屬性選擇效果好壞評(píng)價(jià)的指標(biāo)，樣本分類準(zhǔn)確率越高，表明屬性選擇算法性能越好，反之屬性選擇算法性能越差。本文所有實(shí)驗(yàn)采用10折交叉驗(yàn)證方法，來(lái)驗(yàn)證KSFS算法和對(duì)比算法的性能，把數(shù)據(jù)集按照10折交叉驗(yàn)證方法分為10折，其中9折作為訓(xùn)練集，1折作為測(cè)試集，并且選用SVM分類器進(jìn)行分類，就可以得到不同屬性選擇算法的分類準(zhǔn)確率。為了確保實(shí)驗(yàn)的公平性和準(zhǔn)確性，本文所有算法都在同一實(shí)驗(yàn)環(huán)境下進(jìn)行。最終把實(shí)驗(yàn)10次運(yùn)行結(jié)果的平均值和均方誤差作為屬性選擇算法性能評(píng)價(jià)的指標(biāo)。最后把每個(gè)算法的實(shí)驗(yàn)結(jié)果在10個(gè)公開數(shù)據(jù)集上繪制成對(duì)比圖，如圖11～圖20所示，相關(guān)算法具體實(shí)驗(yàn)數(shù)據(jù)結(jié)果，如表2所示。

Figure 11 Accuracy of algorithms on Colon圖11 各算法在Colon上的準(zhǔn)確率

通過(guò)圖11～圖20和表2所示的實(shí)驗(yàn)結(jié)果可以看出，本文所有算法在10個(gè)公開數(shù)據(jù)集上的分類準(zhǔn)確率，因?yàn)?0折交叉驗(yàn)證的隨機(jī)性，所以并不能確保KSFS算法每次的實(shí)驗(yàn)結(jié)果都高于其他算法。但是，KSFS算法在每個(gè)數(shù)據(jù)集上的10次實(shí)驗(yàn)結(jié)果大部分比對(duì)比算法要好，而且最終的平均準(zhǔn)確率也是最高的。通過(guò)表2分析得出，KSFS算法與其他5種對(duì)比算法相比，其平均分類準(zhǔn)確率均高于其他算法，同時(shí)通過(guò)表3可知，KSFS算法在10個(gè)數(shù)據(jù)集上運(yùn)行所用的時(shí)間比對(duì)比算法所用的時(shí)間要少很多。與半監(jiān)督屬性選擇CSFS算法相比較，平均分類準(zhǔn)確率提高了近7%，說(shuō)明充分利用好數(shù)據(jù)的類標(biāo)簽，對(duì)提高分類準(zhǔn)確率是非常重要的；與經(jīng)典的FSSL算法相比較，平均分類準(zhǔn)確率提高了2%，從而更好地證明了本文KSFS算法比單純的子空間學(xué)習(xí)算法性能要好很多，同時(shí)運(yùn)用了低秩約束的方法，去除冗余的屬性和噪聲樣本，充分考慮數(shù)據(jù)之間的全局結(jié)構(gòu)，不斷調(diào)整屬性選擇的結(jié)果，從而使之達(dá)到最優(yōu)。在龐大樣本數(shù)量的Isolets和PCMAC等數(shù)據(jù)集上低秩約束的方法效果比較顯著，分類準(zhǔn)確率提高了2%～3%；其次與近幾年比較優(yōu)秀的屬性選擇算法FSPG和Lasso、ERFS相比都有比較好的效果。通過(guò)引入核函數(shù)進(jìn)行屬性選擇充分挖掘了屬性與類標(biāo)簽之間的非線性關(guān)系，采用低秩約束的方法充分考慮了數(shù)據(jù)之間的全局結(jié)構(gòu)，所以本文提出的算法有比較好的效果。

Table 2 Statistical results of classification accuracy表2 分類準(zhǔn)確率(±均值方差)統(tǒng)計(jì)結(jié)果

Table 3 Running time statistics of the algorithm on data sets 表3 算法在數(shù)據(jù)集上的運(yùn)行時(shí)間統(tǒng)計(jì)結(jié)果 s

Figure 12 Accuracy of algorithms on Ecoli圖12 各算法在Ecoli上的準(zhǔn)確率

Figure 13 Accuracy of algorithms on Yale圖13 各算法在Yale上的準(zhǔn)確率

Figure 14 Accuracy of algorithms on Isolets圖14 各算法在Isolets上的準(zhǔn)確率

Figure 15 Accuracy of algorithms on PCMAC圖15 各算法在PCMAC上的準(zhǔn)確率

Figure 16 Accuracy of algorithms on Madelon圖16 各算法在Madelon上的準(zhǔn)確率

Figure 17 Accuracy of algorithms on Multiple圖17 各算法在Multiple上的準(zhǔn)確率

Figure 18 Accuracy of algorithms on SECOM圖18 各算法在SECOM上的準(zhǔn)確率

Figure 19 Accuracy of algorithms on CNAE圖19 各算法在CNAE上的準(zhǔn)確率

Figure 20 Accuracy of algorithms on CCUDS圖20 各算法在CCUDS 上的準(zhǔn)確率

6 結(jié)束語(yǔ)

本文結(jié)合核函數(shù)和稀疏學(xué)習(xí)提出了一種新穎的有監(jiān)督屬性選擇算法—KSFS算法。該算法將核函數(shù)嵌入到稀疏學(xué)習(xí)模型中，將原始數(shù)據(jù)集投影到高維核空間，使得原始數(shù)據(jù)集在高維核空間中具有更高的可分性，進(jìn)一步在核空間上進(jìn)行屬性選擇；在此基礎(chǔ)上利用L1范數(shù)正則化懲罰模型，避免模型過(guò)擬合，減小了計(jì)算誤差；同時(shí)，利用L1范數(shù)作為屬性選擇評(píng)分機(jī)制，選出重要的樣本屬性。該算法在回歸模型的基礎(chǔ)上，結(jié)合低秩約束的方法彌補(bǔ)了數(shù)據(jù)幾何結(jié)構(gòu)方面的不足之處。實(shí)驗(yàn)結(jié)果顯示，本文算法在分類準(zhǔn)確率和穩(wěn)定性上都有了較大的提升，所以KSFS算法可以得到比較好的屬性選擇效果。在接下來(lái)的工作中，將嘗試用半監(jiān)督學(xué)習(xí)的屬性選擇方法擴(kuò)展本文所提出的算法，并嘗試使用更好的方法來(lái)降低算法的計(jì)算復(fù)雜度和提高算法的穩(wěn)定性。