白圣子，降愛蓮

(太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 晉中 030600)

0 引 言

在原始高維數(shù)據(jù)集中，冗余特征的存在會(huì)影響學(xué)習(xí)算法的性能，降低學(xué)習(xí)算法的效率，甚至遭遇“維數(shù)災(zāi)難”。因此，需要通過特征選擇，從原始數(shù)據(jù)中剔除無關(guān)、冗余等特征，選出具有代表性的特征構(gòu)成最優(yōu)特征子集，從而降低數(shù)據(jù)維度、簡化學(xué)習(xí)模型、提高學(xué)習(xí)效率。由于數(shù)據(jù)規(guī)模較大以及獲取數(shù)據(jù)標(biāo)簽十分耗時(shí)等原因，無監(jiān)督特征選擇在實(shí)際處理中更實(shí)用，研究其方法更具有挑戰(zhàn)性[1]。

無監(jiān)督特征選擇方法根據(jù)評價(jià)準(zhǔn)則主要分為過濾式方法、封裝式方法和嵌入式方法[2]。過濾式方法獨(dú)立于具體的學(xué)習(xí)算法，逐一對特征進(jìn)行評分，如方差選擇法[3]和拉普拉斯得分[4]選擇法。封裝式方法是根據(jù)后續(xù)使用的算法每次排除若干特征，直到特征數(shù)滿足算法的要求，如遞歸消除特征法[5]。這兩類方法評價(jià)標(biāo)準(zhǔn)單一，忽略特征之間的相關(guān)性，造成特征的冗余。嵌入式方法是將特征選擇和訓(xùn)練模型的過程相結(jié)合，模型優(yōu)化的同時(shí)直接計(jì)算出每個(gè)特征的權(quán)重，特征權(quán)重越大表明該特征越重要。如文獻(xiàn)[6]將特征選擇轉(zhuǎn)化為矩陣分解問題，利用正則化矩陣分解方法選擇出具有代表性的低維特征子集，但計(jì)算復(fù)雜度較高且正交約束條件很難應(yīng)用到實(shí)際中。文獻(xiàn)[7]提出特征級自表示選擇方法，將特征選擇問題轉(zhuǎn)化為損失函數(shù)模型。該方法提出了數(shù)據(jù)集中的每個(gè)特征都可以被所有特征線性近似表示的性質(zhì)，通過優(yōu)化損失函數(shù)可以有效批量地評估每個(gè)特征的重要性。但在計(jì)算過程中，由于每個(gè)特征參與其自身的重構(gòu)[8]，導(dǎo)致權(quán)重易向自身傾斜，無法合理地為每個(gè)特征分配權(quán)重。

針對上述問題，提出基于特征正則稀疏關(guān)聯(lián)的無監(jiān)督特征選擇方法(feature regularized sparse association，F(xiàn)RSA)。該方法利用特征稀疏關(guān)聯(lián)性質(zhì)，能夠合理分配特征權(quán)重，剔除冗余無關(guān)特征，降低數(shù)據(jù)維度，有效提升數(shù)據(jù)聚類準(zhǔn)確率。

1 FRSA模型建立

1.1 最小二乘法線性回歸

給定一個(gè)數(shù)據(jù)矩陣X∈Rn×m與響應(yīng)矩陣Y=[y1,y2,…,yc]∈Rn×c，我們通常用如下公式來構(gòu)建X與Y之間的線性關(guān)系

(1)

其中，W∈Rm×c是特征權(quán)重矩陣，l(Y-XW)是損失項(xiàng)，D(W)是對W施加的正則約束項(xiàng)，λ是一個(gè)正常數(shù)。式(1)的目標(biāo)是得到一個(gè)合適的W，使得實(shí)際的響應(yīng)矩陣Y與預(yù)測的XW之間的差值最小[9]。

1.2 特征稀疏關(guān)聯(lián)

本文將數(shù)據(jù)矩陣X作為最小二乘回歸模型中的響應(yīng)矩陣Y來測量誤差，學(xué)習(xí)特征權(quán)重矩陣W，揭示原始數(shù)據(jù)中特征之間的稀疏關(guān)聯(lián)關(guān)系，即某一個(gè)特征可以被其它特征(不包含自身)稀疏近似表示。具體地說，給定m個(gè)特征，我們所運(yùn)用的特征稀疏關(guān)聯(lián)是學(xué)習(xí)每個(gè)特征與其它所有特征之間的線性近似關(guān)系。當(dāng)i=j時(shí)，令wji=0，第i個(gè)特征不參與自身重構(gòu)表示

f1≈f10+f1w21+…fiwi1+…+fmwm1

f2≈f1w12+f20+…fiwi2+…+fmwm2

?

fm≈f1w1m+f1w2m+…fiwim+…+fm0

(2)

因此，數(shù)據(jù)矩陣X中的每一個(gè)特征fi可形式近似表示為

(3)

其中，ei是誤差項(xiàng)，wji是表示系數(shù)，fi是數(shù)據(jù)矩陣X的一個(gè)特征。對于所有的特征，式(3)可以寫成

X=XW+E

(4)

其中，W∈Rm×m與E∈Rn×m分別是特征權(quán)重矩陣和殘余誤差項(xiàng)。W有效地表示了不同特征之間的關(guān)聯(lián)關(guān)系，并且使得殘余誤差項(xiàng)E(E=X-XW)盡可能得小。

1.3 目標(biāo)函數(shù)

本文利用Forbenius范數(shù)來度量誤差大小，期望得到一個(gè)合適的W，使得重構(gòu)后的矩陣XW能夠很好地近似表示原始數(shù)據(jù)矩陣X。如果X是一個(gè)單位矩陣使得誤差項(xiàng)E≡0，則W為平凡解。因此，必須添加正則化項(xiàng)D(W)對特征權(quán)重矩陣的解空間進(jìn)行約束，防止過擬合，降低模型復(fù)雜度，得到穩(wěn)定可行的最優(yōu)解[10]，進(jìn)而得到了如下最小化問題

(5)

(6)

2 優(yōu)化算法

因此，原目標(biāo)函數(shù)展開得到如下m個(gè)子問題

(7)

根據(jù)特征稀疏關(guān)聯(lián)關(guān)系，第j個(gè)特征不參與自身的線性近似表示，因此wj的第j個(gè)元素為0。在實(shí)際計(jì)算過程中，需要?jiǎng)h除數(shù)據(jù)矩陣X的第j列與wj的第j個(gè)元素

(8)

?j∈R(m-1)×1是wj刪除第j個(gè)元素0后得到的特征向量，Xj-∈Rn×(m-1)是數(shù)據(jù)矩陣X刪除第j列得到的數(shù)據(jù)矩陣，這樣保證了第j個(gè)特征不參與自身的線性近似表示。針對式(8)的正則化回歸問題，將利用一種收縮閾值迭代算法求其最優(yōu)解。

首先考慮式(8)無正則化約束下的連續(xù)可微函數(shù)最小化問題

(9)

s.t.??,y∈Rn

(10)

(11)

對于g(?)最小的常數(shù)K稱為李普希茨常數(shù)L。同時(shí)，在?k附近可將g(?)通過二階泰勒式展開

(12)

式(11)得出李普希茨常數(shù)L形式與二階導(dǎo)數(shù)形式相似。基于此，在?k附近可以把函數(shù)值近似為

其中，后兩項(xiàng)是與?無關(guān)的常量。顯然，式(12)的最小值在如下?k+1獲得

(13)

(14)

即在每一步對g(?)進(jìn)行梯度下降迭代的同時(shí)考慮1-范數(shù)最小化。

(15)

其中，不存在?i?j(i≠j)這樣的項(xiàng)，即?的各分量互不影響且1-范數(shù)是可拆分函數(shù)，可得最優(yōu)閉式解[15]。

對于式(15)中的每一個(gè)分量，都可以通過偏導(dǎo)求其最小值

(16)

(17)

其中，sign(x)為符號函數(shù)，如果x大于0，則為1；如果x小于0，則為-1；如果x等于0，則為0?？紤]到式(15)兩邊都有?i，利用收縮閾值迭代[16]進(jìn)行求解

(18)

綜上所述，得出式(8)的優(yōu)化迭代公式

計(jì)算g(?)在?k處的偏導(dǎo)，最終得到收縮閾值迭代式

?k+1=Γλ/L(?k-2/L(Xj-)T(Xj-?k-fj))

(19)

文獻(xiàn)[16]已驗(yàn)證，若X為數(shù)據(jù)矩陣，當(dāng)李普希茨常數(shù)L=2βmax(XTX)(βmax(·)表示矩陣的最大特征值)，式(19)得以快速求解。該式每次使用前一步迭代求得的近似函數(shù)最小值點(diǎn)?k作為下一步迭代的起始點(diǎn)，收斂速度為O(1/k)。為了加快其收斂速度，將引入梯度加速策略Nestrerow加速技術(shù)[17]

(20)

(21)

其中，Nestrerow加速使用前兩步迭代過程的結(jié)果xk-1，xk，對其進(jìn)行線性組合生成下一步迭代的近似函數(shù)起始點(diǎn)yk+1。經(jīng)驗(yàn)證[17]，該加速技術(shù)適用于式(19)的收縮閾值迭代算法，以極少的額外計(jì)算量提高了算法的收斂速度。因此，引入Nestrerow加速后，式(19)為如下迭代形式

(22)

算法1：

輸入：數(shù)據(jù)矩陣X∈Rn×m，特征選擇個(gè)數(shù)d，正則項(xiàng)參數(shù)λ；

輸出：特征子集D∈Rn×d；

(1)數(shù)據(jù)矩陣X→{f1,f2,…,fm}；

(2)將式(6)劃分為m個(gè)子問題：

(3)計(jì)算L=2βmax((Xj-)TXj-)，初始化y1=?0，t1=1；

(4)重復(fù)(k≥1)：

?k=Γλ/L(yk-2/L(Xj-)T(Xj-yk-fj))

(5)直到收斂；

在引入Nestrerov加速后，收斂速度從O(1/k)提高到O(1/k2)。式(17)求偏導(dǎo)時(shí)(Xj-)TXj-的計(jì)算復(fù)雜度為O(nm2)，所以每個(gè)子問題的計(jì)算復(fù)雜度為O(nm3/k2)。因?yàn)镕RSA模型的最優(yōu)解是由m個(gè)子問題的最優(yōu)解整合得到，所以該算法的整體計(jì)算復(fù)雜度為O(nm3/k2)。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

為驗(yàn)證本文方法的性能，在機(jī)器學(xué)習(xí)數(shù)據(jù)庫中選取了6個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行對比測試，各數(shù)據(jù)集的詳細(xì)參數(shù)見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)匯總

3.2 實(shí)驗(yàn)對比方法

為了驗(yàn)證本文提出的FRSA方法的有效性，實(shí)驗(yàn)中將其與以下4種常用的無監(jiān)督特征選擇方法進(jìn)行比較：

(1)拉普拉斯得分特征選擇方法[18](Laplacian score feature selection，LS)；

(2)無監(jiān)督判別特征選擇方法[19](unsupervised discriminative feature selection，UDFS)；

(3)矩陣分解特征選擇方法[20](matrix factorization feature selection，MFFS)；

(4)自表示特征選擇方法[7](self-representation feature selection，SR-FS)。

3.3 實(shí)驗(yàn)設(shè)置

在本實(shí)驗(yàn)中，采取3種被普遍應(yīng)用的評價(jià)指標(biāo)，即聚類準(zhǔn)確率(accuracy，ACC)、歸一化互信息(normalize mutual information，NMI)和冗余率(redundancy rate，RED)來評價(jià)不同無監(jiān)督特征選擇方法的性能。對于一個(gè)輸入樣本xi，qi和pi表示它的聚類結(jié)果和真實(shí)標(biāo)簽，那么ACC的定義如下

(23)

其中，函數(shù)δ(x,y)用于判斷x與y是否相等，若相等則函數(shù)值為1，否則函數(shù)值為0。map(qi)是一個(gè)最佳映射函數(shù)，它的功能是通過Kuhn-Munkre算法把實(shí)驗(yàn)得到的聚類標(biāo)簽與樣本的真實(shí)標(biāo)簽進(jìn)行匹配[21]。ACC的值越大說明聚類性能越好，表明獲得的聚類標(biāo)簽更加接近樣本真實(shí)的標(biāo)簽。

歸一化互信息是評價(jià)聚類結(jié)果好壞的常用指標(biāo)之一，給定任意兩個(gè)變量P和Q，NMI可以被定義為

(24)

其中，H(P)和H(Q)分別表示P和Q的熵，I(P,Q)是P和Q兩者之間的互信息。P是聚類結(jié)果，Q是實(shí)際標(biāo)簽。類似于ACC，NMI的值越大意味著聚類性能越好。

冗余率[22]是用來度量數(shù)據(jù)的特征之間是否具有較強(qiáng)的相關(guān)性。假設(shè)fs是所選擇的特征集，冗余率計(jì)算公式如下

(25)

其中，ρij是特征fi與特征fj之間的相關(guān)系數(shù)。RED(fs)的值越大意味著選擇后的許多特征仍然是顯著相關(guān)，冗余程度高。因此計(jì)算所得的冗余率越小越好。

在實(shí)驗(yàn)中將對每個(gè)無監(jiān)督特征選擇方法的參數(shù)進(jìn)行設(shè)置。對于所有方法，每個(gè)數(shù)據(jù)集選擇特征的個(gè)數(shù)范圍設(shè)置為 {20，30，40，50，60，70，80，90，100}。對于LS、UDFS算法，將它們的近鄰參數(shù)k設(shè)置為5。對于有正則項(xiàng)參數(shù)的算法，采用交替網(wǎng)格搜索的方式確定它們的值，其網(wǎng)格搜索范圍設(shè)置為 {0.001，0.01，0.1，1，10，100，1000}[6]，并記錄其中最優(yōu)參數(shù)所對應(yīng)的最好結(jié)果。然后將9個(gè)不同維數(shù)的特征子集的聚類準(zhǔn)確率、歸一化互信息以及冗余率分別取平均值，作為評價(jià)各方法性能的指標(biāo)。

當(dāng)利用K-means算法對每種方法選擇的低維特征進(jìn)行聚類時(shí)，考慮到K-means聚類的性能會(huì)受到初始質(zhì)心選取的影響，為提升結(jié)果準(zhǔn)確度，將重復(fù)執(zhí)行150次不同的隨機(jī)初始化實(shí)驗(yàn)，然后記錄平均結(jié)果。

3.4 實(shí)驗(yàn)結(jié)果與分析

利用合成數(shù)據(jù)集IRIS-20測試本文提出的FRSA方法是否能找到具有代表性的特征。該數(shù)據(jù)集包含150個(gè)樣本和20個(gè)特征，后16個(gè)特征是由前4個(gè)特征線性組合得到(組合系數(shù)隨機(jī)生成并且和為1)，并加入了一定的高斯白噪聲。

圖1 特征權(quán)重直方圖

從表2和圖2(e)的實(shí)驗(yàn)結(jié)果可知，F(xiàn)RSA方法在Lung_discrete、Pronstate_GE、lymphoma、ORL和Urban這5個(gè)在數(shù)據(jù)集中所選擇的特征子集獲得最高的聚類準(zhǔn)確率(ACC)，在數(shù)據(jù)集COIL20上的聚類準(zhǔn)確率僅次于MFFS方法。從表3和圖2(c)的實(shí)驗(yàn)結(jié)果可知，F(xiàn)RSA方法在Lung_discrete、Pronstate_GE、ORL、COIL20和Urban這5個(gè)在數(shù)據(jù)集中所選擇的特征子集獲得最高的歸一化互信息(NMI)，在數(shù)據(jù)集lymphoma上的歸一化互信息僅次于SR-FS方法。聚類準(zhǔn)確率和歸一化互信息都是評價(jià)聚類結(jié)果好壞的常用指標(biāo)，因此得出結(jié)論，F(xiàn)RSA方法選擇出的特征更具有代表性，可以有效地提高聚類準(zhǔn)確率。從表4和圖2(c)、圖2(d)的實(shí)驗(yàn)結(jié)果可知，F(xiàn)RSA方法在Lung_discrete、Prostate_GE、COIL20和Urban數(shù)據(jù)集上選出的特征子集的冗余率(RED)最低，在數(shù)據(jù)集lymphoma上的冗余率僅次于SR-FS方法，在數(shù)據(jù)集ORL上的冗余率僅次于MFFS方法。冗余率越低，冗余程度越低。表明FRSA方法選出的特征之間冗余程度較低，特征子集冗余率較低，更具有代表性。

表2 不同特征選擇算法的聚類準(zhǔn)確率ACC/%

表3 不同特征選擇算法的歸一化互信息NMI/%

表4 不同特征選擇算法的冗余率RED/%

圖2 5種無監(jiān)督特征選擇方法在6種不同數(shù)據(jù)集上的ACC、NMI、RED對比

通過以上分析可以得出，由于LS方法是對特征逐一進(jìn)行評分選擇，并且沒有考慮特征之間的相關(guān)性，因此在其3個(gè)評價(jià)指標(biāo)上明顯弱于其它方法。UDFS、MFFS、SR-FS方法都是基于正則化選擇，并且都是對特征進(jìn)行批量選擇，因此在特征選擇時(shí)，批量選擇的效果優(yōu)于單個(gè)選擇。但是，UDFS方法更多地是考慮樣本之間的相似，容易忽略特征之間潛在的相關(guān)系。MFSS方法是從子空間學(xué)習(xí)角度進(jìn)行特征選擇，也沒有考慮特征之間的相關(guān)性。而SR-FS方法雖然利用特征級自表示性質(zhì)選擇特征，考慮特征之間的相關(guān)性，但不足之處是特征參與自身重構(gòu)時(shí)容易使特征權(quán)重向自身傾斜，導(dǎo)致權(quán)重分配不合理。因此，本文在特征級自表示的損失函數(shù)模型框架下，利用特征互表示的性質(zhì)[8]，學(xué)習(xí)每個(gè)特征之間的關(guān)聯(lián)關(guān)系，提出了基于特征正則稀疏關(guān)聯(lián)的無監(jiān)督特征選擇方法(FRSA)。該方法不僅利用稀疏正則化約束對特征進(jìn)行批量選擇，而且考慮到每個(gè)特征與其它特征(不包括自身)的關(guān)聯(lián)性。實(shí)驗(yàn)結(jié)果表明,該方法所選出的特征子集具有較好的聚類效果和較低的冗余度，性能優(yōu)于其它4種常用的無監(jiān)督特征選擇方法。在計(jì)算復(fù)雜度方面，UDFS方法、MFSS方法和SR-FS方法采用矩陣直接迭代逼近最優(yōu)解，計(jì)算時(shí)間與空間復(fù)雜度較高[23]。而分治-收縮閾值迭代算法將矩陣整體優(yōu)化問題拆分為多個(gè)性質(zhì)相同的向量優(yōu)化問題，然后再進(jìn)行迭代求解，占用內(nèi)存較小且計(jì)算效率高。因此，F(xiàn)RSA方法有較低的計(jì)算復(fù)雜度。

4 結(jié)束語

在本文中，利用無標(biāo)簽數(shù)據(jù)特征之間潛在的關(guān)聯(lián)性，提出了一種基于特征正則稀疏關(guān)聯(lián)的無監(jiān)督特征選擇方法(FRSA)。利用L1-稀疏規(guī)則算子在特征選擇時(shí)對權(quán)重矩陣施加正則化約束，最小化其非零行數(shù)，加強(qiáng)了特征權(quán)重矩陣的行稀疏性，提升了所選特征子集的魯棒性。通過稀疏關(guān)聯(lián)性質(zhì)克服了特征權(quán)重易向自身傾斜的不足，合理地為每個(gè)特征分陪權(quán)重。實(shí)驗(yàn)結(jié)果表明，F(xiàn)RSA方法可以有效地評估每個(gè)特征的重要性，選擇出重要特征，剔除冗余特征，降低原始高維數(shù)據(jù)的冗余率，提高聚類準(zhǔn)確率，并且具有較低的計(jì)算負(fù)責(zé)度。在實(shí)際應(yīng)用中，獲取的數(shù)據(jù)不夠完善不具有多樣性[24]，后續(xù)工作可以進(jìn)一步擴(kuò)展方法適用于不完整數(shù)據(jù)。另外，正則化約束項(xiàng)[25]對權(quán)重矩陣的作用直接影響到FRSA方法的性能，如何構(gòu)建更有效的正則化約束項(xiàng)也是下一步研究重點(diǎn)。