白圣子，降愛蓮

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

0 引 言

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

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

1 FRSA模型建立

1.1 最小二乘法線性回歸

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

(1)

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

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

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

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

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

?

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

(2)

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

(3)

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

X=XW+E

(4)

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

1.3 目標函數(shù)

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

(5)

(6)

2 優(yōu)化算法

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

(7)

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

(8)

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

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

(9)

s.t.??,y∈Rn

(10)

(11)

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

(12)

式(11)得出李普希茨常數(shù)L形式與二階導數(shù)形式相似?；诖?，在?k附近可以把函數(shù)值近似為

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

(13)

(14)

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

(15)

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

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

(16)

(17)

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

(18)

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

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

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

(19)

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

(20)

(21)

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

(22)

算法1：

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

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

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

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

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

(4)重復(k≥1)：

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

(5)直到收斂；

在引入Nestrerov加速后，收斂速度從O(1/k)提高到O(1/k2)。式(17)求偏導時(Xj-)TXj-的計算復雜度為O(nm2)，所以每個子問題的計算復雜度為O(nm3/k2)。因為FRSA模型的最優(yōu)解是由m個子問題的最優(yōu)解整合得到，所以該算法的整體計算復雜度為O(nm3/k2)。

3 實驗分析

3.1 實驗數(shù)據(jù)

為驗證本文方法的性能，在機器學習數(shù)據(jù)庫中選取了6個標準數(shù)據(jù)集進行對比測試，各數(shù)據(jù)集的詳細參數(shù)見表1。

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

3.2 實驗對比方法

為了驗證本文提出的FRSA方法的有效性，實驗中將其與以下4種常用的無監(jiā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 實驗設置

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

(23)

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

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

(24)

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

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

(25)

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

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

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

3.4 實驗結(jié)果與分析

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

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

從表2和圖2(e)的實驗結(jié)果可知，F(xiàn)RSA方法在Lung_discrete、Pronstate_GE、lymphoma、ORL和Urban這5個在數(shù)據(jù)集中所選擇的特征子集獲得最高的聚類準確率(ACC)，在數(shù)據(jù)集COIL20上的聚類準確率僅次于MFFS方法。從表3和圖2(c)的實驗結(jié)果可知，F(xiàn)RSA方法在Lung_discrete、Pronstate_GE、ORL、COIL20和Urban這5個在數(shù)據(jù)集中所選擇的特征子集獲得最高的歸一化互信息(NMI)，在數(shù)據(jù)集lymphoma上的歸一化互信息僅次于SR-FS方法。聚類準確率和歸一化互信息都是評價聚類結(jié)果好壞的常用指標，因此得出結(jié)論，F(xiàn)RSA方法選擇出的特征更具有代表性，可以有效地提高聚類準確率。從表4和圖2(c)、圖2(d)的實驗結(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 不同特征選擇算法的聚類準確率ACC/%

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

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

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

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

4 結(jié)束語

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