特征自表達和圖正則化的魯棒無監(jiān)督特征選擇

陳彤，陳秀宏

（江南大學 人工智能與計算機學院，江蘇 無錫 214122）

隨著互聯(lián)網(wǎng)的迅猛發(fā)展，產(chǎn)生了大量的高維數(shù)據(jù)，高維數(shù)據(jù)通常含有大量的冗余、噪聲，會降低學習算法的性能。基于這一問題，特征選擇和特征提取成為了降維的重要手段。特征提取通過將高維數(shù)據(jù)投影到低維子空間來減少數(shù)據(jù)的維度，特征選擇是直接選擇原始數(shù)據(jù)的特征子集作為降維后的特征。本文，從特征選擇的角度展開研究。

特征選擇方法包括有監(jiān)督特征選擇[1]、半監(jiān)督特征選擇[2]、無監(jiān)督特征選擇[3-4]。有監(jiān)督特征選擇和半監(jiān)督特征選擇依賴于數(shù)據(jù)的標簽信息，然而在實際應用中，類別標注的成本過高。因此，這就要求應用無監(jiān)督特征選擇方法選擇更具價值的特征。常見的無監(jiān)督特征選擇方法可以分為了三類：過濾法[3]、包裹法[5]和嵌入法[6]。過濾式特征選擇方法獨立于具體的學習算法，運算效率較高。它的主要思想是對每一維特征賦予權重，所得到的權重就代表著該特征的重要性，然后依據(jù)權重進行排序，把重要性相對較小的特征過濾掉，將重要性較大的特征作為原始數(shù)據(jù)的表示。例如，最大方差法[7]以數(shù)據(jù)方差作為評價標準，將特征按重要性排序進行選擇。除此之外，拉普拉斯評分法[3](LapScore)也是常見的無監(jiān)督的過濾式特征選擇方法。包裹式特征選擇方法從初始特征集合中不斷地選擇特征子集，訓練學習器，根據(jù)學習器的性能進行評價，直到選擇出最佳的子集。LVW(Las Vegas Wrapper)[8]是一個典型的包裹式特征選擇方法，它在拉斯維加斯(Las Vegas method)框架下使用隨機策略來進行子集搜索，并以最終分類器的誤差作為特征子集評級準則。嵌入式特征選擇在學習器訓練過程中自動地進行特征選擇，其分類效果通常較好，同時該類方法可以實現(xiàn)對多個特征的選擇。嵌入式選擇最常用的是L1正則化和L2正則化[6]，當正則化項增大到一定程度時，所有的特征系數(shù)都會趨于0，在這個過程中，會有一部分特征的系數(shù)先變?yōu)?，也就實現(xiàn)了特征選擇過程。除此之外，近年來又研究出了更加有效且高效的無監(jiān)督特征選擇方法，例如Li 等[9]將局部幾何一致性和冗余最小化結合到同一框架中，利用局部幾何結構的一致性來提高聚類精度，并在此過程中進行特征選擇。Liu 等[10]提出了一種嵌入式無監(jiān)督特征選擇方法，該方法通過局部線性嵌入(locally linear embedding,LLE)算法得到特征權重矩陣，并使用L1-范數(shù)來描述重構誤差最下化。大量的實驗結果證明，以上這些方法均是有效的。

對于特征選擇來說，保持局部幾何數(shù)據(jù)結構顯然比保持全局結構更為重要[11]。最常用的局部幾何結構保持方法有以下3 種：基于L2范數(shù)的局部線性嵌入(LLE)[12]、局部保留投影(locality preserving projections,LPP)[13]以及局部切空間對齊(local tangent space alignment,LTSA)[14]。而傳統(tǒng)的局部保留方法是基于L2范數(shù)，很容易受到噪聲和冗余數(shù)據(jù)的影響，其次，L2范數(shù)已經(jīng)被應用于許多正則化項中，這使得傳統(tǒng)方法對離群值十分敏感，導致特征選擇效果不理想。

基于以上提出的問題，本文通過特征自表達、圖正則化以及低秩約束，提出了一個魯棒無監(jiān)督特征選擇模型，同時保留了數(shù)據(jù)的局部幾何結構和全局結構。并在6個公開數(shù)據(jù)集上進行實驗，且與5個對比算法進行對比，證明了該模型的有效性。

1 相關工作

1.1符號元素定義

對于任意矩陣X∈Rm×n，xij表示的是該矩陣第i行第j列的元素。tr(X)表示矩陣X的跡，X?1表示矩陣X的逆。矩陣X的L2,1范數(shù)被定義為

矩陣X的F范數(shù)被定義為

1.2 特征自表達

特征自表達已經(jīng)被廣泛地應用于無監(jiān)督特征選擇之中。例如Zhu 等[15]提出了一種用于無監(jiān)督特征選擇的正則化自表達(regularized self-representation,RSR) 模型。在RSR 中，X=[x1x2···xn]=[x1x2···xd]∈Rn×d表示特征矩陣，其中樣本數(shù)和特征數(shù)分別是n和d，X的每一行代表一個樣本，每一列代表一個特征維度。樣本的特征自表達定義為

式中：權重矩陣W∈Rd×d的元素wji表示第i個特征xi和第j個特征xj之間的權重。在式(1)中，每一個特征的特征表示項都是由其余重要的特征組成的，而不重要的特征應該從特征表示項中移除。

特征表示系數(shù)可通過以下模型來求解

式中：λ 為一個平衡參數(shù)，基于L2,1范數(shù)的正則化項可得到行稀疏的權重矩陣W，從而實現(xiàn)特征選擇。

從式(1)、(2)可以看出，所有訓練樣本的每一個特征(即式(1)左側(cè)的xi)都是由其他特征的線性組合所表示的，相應的權重向量是式(2)中W的第i列wi。顯然，wi中的值越大，其對應的特征在xi的表示中所占的比重越多。除此之外，如果W的某一行的元素全為0，則相應的特征不出現(xiàn)在特征自表達中，即所有參與特征自表達的特征應該是重要的，而那些不重要的特征將通過 ‖W‖2,1來去除。

1.3 局部保留投影(LPP)

局部保留投影(LPP)[13]通過獲得線性投影來最優(yōu)地保持數(shù)據(jù)的鄰域結構，即樣本之間的某種非線性關系在降維后仍然保留著這種關系。假設W是將樣本數(shù)據(jù)投影到子空間的投影矩陣，則可以通過優(yōu)化以下目標函數(shù)得到W的最優(yōu)解：

式中：W是投影矩陣；s是相似矩陣，關于s的元素定義如下：

Nk(xj)xiσ

是 的k個近鄰的集合， 是寬度參數(shù)。

2 基于特征自表達和圖正則化模型

2.1 模型建立

為了給出基于特征自表達的魯棒聯(lián)合圖正則化無監(jiān)督特征選擇(feature self-representation and graph regularization,FSRGR)模型，首先引入以下圖正則化特征自表達無監(jiān)督特征選擇一般模型：

式中：φ(W)是圖正則化項，用于保留數(shù)據(jù)的局部幾何結構。λ和β是用于平衡L2,1范數(shù)和正則化項的兩個參數(shù)。

2.1.1 基于L2范數(shù)圖正則化項的無監(jiān)督特征選擇

局部線性嵌入(LLE)[12]、局部保留投影(LPP)[13]和局部切線空間對齊(LTSA)[14]等均是基于L2范數(shù)的圖正則化方法。將LPP 思想應用于模型(5)中，則可得到以下模型：

式(6)也可以表示為

2.1.2 基 于L2,1范數(shù)圖正則化項的無監(jiān)督特征選擇

在式(7)中，最后一項圖正則化項用于保留數(shù)據(jù)的局部幾何結構，然而，基于L2范數(shù)的正則化函數(shù)容易受到噪聲數(shù)據(jù)的影響。為減少噪聲的影響，下面介紹一種基于L2,1范數(shù)的圖正則化方法，使得模型對噪聲數(shù)據(jù)更加魯棒。

由于拉普拉斯矩陣L是實對稱的，故設矩陣L特征分解為

于是，式(7)中的圖正則化項可以改寫為

于是式(7)可改寫為

2.1.3 目標函數(shù)

式(11)通過特征自表達和圖正則化來保留數(shù)據(jù)的局部幾何結構，但該模型卻缺少了全局結構信息，無法準確地捕捉特征的全局結構信息。因此本文采用低秩約束來保留數(shù)據(jù)的全局結構。區(qū)別于傳統(tǒng)的特征自表達，此處將特征自表達以及圖正則化項與低秩約束相結合，分別考慮了局部特征相關性和全局特征相關性，從而得到局部特征自表達和全局特征自表達。具體來說，就是對W施加一個低秩假設，即W=AB，所得目標函數(shù)為

式中：A∈Rd×k為投影矩陣；B∈Rk×d為恢復矩陣。λ和β 均是平衡參數(shù)。

該模型利用特征自表達保留了特征的局部結構，并采用了低秩約束(即用A和B代替W)來保留樣本以及特征的全局結構。此外，對傳統(tǒng)LPP模型中的拉普拉斯矩陣進行特征分解，建立基于L2,1范數(shù)的圖正則化項，增強其魯棒性和稀疏性，并保留了數(shù)據(jù)的局部幾何結構。

2.2 優(yōu)化算法

雖然式(12)中的目標函數(shù)是凸的，但很難聯(lián)合地求解所有變量。這里使用交替迭代優(yōu)化策略去優(yōu)化它，即交替地迭代每一個變量，直至算法收斂。

首先，式(12)可以改寫為

式中：P為對角矩陣，將其第i個對角元素定義為

D為對角矩陣，其第i個對角元素定義為

式中：(AB)i是矩陣AB的第i行；(GAB)i是矩陣GAB的第i行。

對式(13)中目標函數(shù)關于B求導數(shù)并設令其等于0，可以得到：

其中，S1=XTX+λP+βGTDG。

將式(16)代入到式(13)中，式(13)可以變?yōu)橐韵滦问剑?/p>

它等價于以下問題：

其中S2=XTXXTX。

對式(18)關于A求導并令其等于零可得：

如設廣義特征方程S2a=λS1a的前k個最大特征值分別為 λ1,λ2,···,λk，對應的特征向量分別為a1,a2,···,ak，并令A=[a1a2···ak]，則有

此時，式(18)中 t r((ATS1A)?1ATS2A)達到最大。

這樣，通過求解式(18)得到A，再式(16)得到B。此過程可迭代進行，直到終止條件滿足。算法給出了更新A和B的具體步驟。

算法FSRGR

2.3 復雜度分析

在每次迭代中，F(xiàn)SRGR 算法的時間主要花費在式(10)中XTX+λP+βGTDG和(ATS1A)?1ATXTX以及特征分解的計算上，相應的復雜度為max{O(n2d),O(nd2)}，O(nd2)及O(n3)，其中n和d代表樣本數(shù)及特征數(shù)。在本次實驗中，所提出的算法一般在10 次迭代內(nèi)收斂，所以算法的時間復雜度為max{O(n2d),O(nd2),O(n3)}。

3 實驗與分析

將在6個公開數(shù)據(jù)集上對FSRGR 算法進行評估，并且與5個特征選擇算法進行比較。以驗證該算法的有效性。

3.1 數(shù)據(jù)集

實驗中使用的6個公開數(shù)據(jù)集中，包括4個人臉數(shù)據(jù)集YALE[16]、ORL[17]、MSRA[18]以及AR[19]，2個手寫數(shù)字數(shù)據(jù)集USPS[20]和LEAVES[21]。這些數(shù)據(jù)集的具體信息如表1 所示，數(shù)據(jù)集的部分圖像如圖1 所示。并且對于每一個數(shù)據(jù)集，均從每類中隨機選取10個樣本組成訓練集，剩余的樣本組成測試集進行實驗。

表1 數(shù)據(jù)集具體信息Table1 Specific information of data sets

圖1 部分數(shù)據(jù)集的圖片F(xiàn)ig.1 Visualization of some data sets with different noise

3.2 對比算法

為了驗證所研究算法的有效性，考慮以下對比方法：

1)NDFS[22]：聯(lián)合學習數(shù)據(jù)的局部幾何結構和基于L2,1范數(shù)正則化項的稀疏線性回歸。

2)JELSR[4]：同時考慮了拉普拉斯正則化器和權重矩陣對特征的得分進行了排序。

3)SOGFS[23]：從低維空間中學習樣本的全局結構來選擇重要特征。

4)L1-UFS[24]：將特征自表達以及基于L1范數(shù)的圖拉普拉斯正則化融入到同一框架中。

5)LRLMR[25]：在低維子空間中進行學習，使得對噪聲更加魯棒；通過圖的流形正則化項來保持原始數(shù)據(jù)的局部結構。

3.3 重構圖像

圖2 展示了6 種不同的算法(NDFS、JELSR、SOGFS、L1-UFS、LRLMR、FSRGR)關于AR 數(shù)據(jù)集得到的部分重構圖像。以圖2(g)為例，共展示了7 張圖像，從左至右分別選取了200、250、300、350、400、450、500個特征進行圖像的重構。從圖2 中可以看出，同其他5個對比算法相比，F(xiàn)SRGR 算法對于圖像的重構效果更好。而在6 種算法中，JELSR 算法的重構效果最差，可以明顯看出，隨著所選特征數(shù)量的增加，該算法所選擇的特征均為不重要的面部特征，而重要的人臉的五官特征并沒有被選擇。

圖2 不同算法對部分AR 數(shù)據(jù)集的重構圖像Fig.2 Reconstructed images of partial AR data sets by different algorithms

3.4 分類精度和聚類精度

將在不同數(shù)據(jù)集上比較FSRGR 算法同其他5 種對比算法，分別評估它們的聚類及分類性能。具體的結果見圖3 和圖4。其中圖3 展示了所有算法在6個數(shù)據(jù)集上關于分類精度的對比結果。如圖3 所示，其橫軸表示所選擇的特征數(shù)，縱軸代表不同的特征數(shù)所對應的分類精度(ACC)。由于不同數(shù)據(jù)集的特征數(shù)通常是不相同的，因此對于YALE、ORL、AR 和LEAVES 數(shù)據(jù)集，我們所選擇的特征數(shù)的范圍為 {50,100,150,200,250,300}，而對于MSRA 及USPS 數(shù)據(jù)集，將所選擇的特征數(shù)的范圍設置為 {20,40,60,80,100,120}。并且對于每一個算法，為了呈現(xiàn)出最真實的比較結果，均將其參數(shù)調(diào)至為最佳參數(shù)，即所呈現(xiàn)出的實驗結果均為其最好的結果。首先從圖3 可以看出，在大多數(shù)情況下，本文所提出的FSRGR 算法均優(yōu)于其他對比算法。尤其在AR 數(shù)據(jù)集上，相比其他5 種對比算法，F(xiàn)SRGR 所取得的分類效果明顯更加優(yōu)越。還可以看出，在5 種對比算法中，分類性能最好的是LRLMR 算法，分類效果最差的是NDFS 算法。其次，圖4 比較了FSRGR 算法同其他對比算法在不同數(shù)據(jù)集上的聚類性能。從圖中可以看出，隨著所選特征數(shù)的增加，通過FSRGR 算法所得到的聚類效果可以穩(wěn)定地優(yōu)于其他對比算法。這是因為本文所提出的方法既保留了數(shù)據(jù)的局部幾何結構，又保留了數(shù)據(jù)的全局結構，并且通過對權重矩陣施加低秩約束，使得所學習到的投影向量的數(shù)量不受限制，從而可以得到足夠多的投影向量。

圖3 6 種算法在6 種數(shù)據(jù)集上的分類精度Fig.3 Classification accuracies of six methods on six data sets

圖4 6 種算法在6 種數(shù)據(jù)集上的聚類精度Fig.4 Clustering accuracies of six methods on six data sets

.5 運行時間

為了比較不同算法的運行時間，在YALE、MSRA、ORL 和USPS 數(shù)據(jù)集上進行了聚類實驗，所有算法均在MATLAB 中實現(xiàn)。具體的實驗結果位于表2 中。

從表2 可以看出，在所有方法中運行時間最短的是LRLMR 算法，本文所提出的FSRGR 算法同L1-UFS,LRLMR 及NDFS 算法相比，運行時間較長。而JELSR 與SOGFS 算法對于不同的數(shù)據(jù)集，運行時間并不穩(wěn)定。

表2 不同方法的運行時間Table2 Running time of different methods s

3.6 收斂性分析

通過計算不同迭代次數(shù)對應的目標函數(shù)值來觀察FSRGR 算法的收斂曲線。并且最大迭代次數(shù)設置為10。由于FSRGR 算法在不同的數(shù)據(jù)集上有相似的收斂性，因此在收斂性分析的部分只展示了在YALE 數(shù)據(jù)集上的實驗結果。從圖5 中可以發(fā)現(xiàn)：1)所提出的算法優(yōu)化了式(12)所提出的目標函數(shù)，單調(diào)地減少了目標函數(shù)值直至算法收斂。2)所提出的算法需要經(jīng)過數(shù)次迭代來有效地達到收斂。

圖5 FSRGR 在YALE 數(shù)據(jù)集上的收斂性Fig.5 Convergence of FSRGR on YALE data sets

3.7 參數(shù)設置

重點研究參數(shù) β和λ 的取值對于聚類精度的影響。首先參數(shù) β 是用于平衡，其次是參數(shù) λ，用于控制AB的稀疏性。并且這兩個參數(shù)的取值范圍均被設置為 {10?6,10?4,10?2,1,102,104,106}。實驗采用了K-means 算法，呈現(xiàn)出了不同的參數(shù)組合在不同的數(shù)據(jù)集上對于聚類精度的影響。具體的實驗結果見圖6。

從圖6 可以看出，本文所提出的方法對參數(shù)的設置較為敏感，不同的參數(shù)組合具有不同的聚類結果。舉例說明，對于人臉數(shù)據(jù)集YALE,當λ=10?2,β=10?6時，F(xiàn)SRGR 的聚類精度達到了36.89%的最好效果；而對于手寫字數(shù)據(jù)集USPS，當 λ=104,β=10?4時，F(xiàn)SRGR 的聚類精度達到了57.70%的最好效果。

圖6 不同 β和λ 組合下的FSRGR 聚類精度Fig.6 Clustering accuracy of FSRGR algorithm with different combination of β and λ

3.8 低秩約束的影響

式(12)中不同秩(k∈{3，6，9，12，15})在數(shù)據(jù)集AR、ISOLET、PIE、LUNG、USPS、YALE 上對聚類精度的影響。圖7 中給出了FSRGR 在不同數(shù)據(jù)集上滿秩和低秩下的聚類精度。其中橫軸代表所選定的秩的范圍，縱軸代表不同的秩所對應的分類精度。

從圖7 中可以觀察到，低秩約束下的聚類性能在大多數(shù)情況下都優(yōu)于滿秩。例如，在數(shù)據(jù)集AR 和USPS 上，同全秩的情況下相比，低秩約束下所得到的平均分類精度分別高出了12.43%和17.88%。這說明在特征選擇中，對高維數(shù)據(jù)進行低秩約束是有效的。

圖7 FSRGR 在不同秩上的ACC 結果Fig.7 ACC results of FSRGR at different number of ranks

4 結束語

本文提出了一種新的魯棒無監(jiān)督特征選擇模型，它將特征自表達、低秩約束、圖正則化以及L2,1范數(shù)正則化項統(tǒng)一在同一框架中,將傳統(tǒng)的基于L2范數(shù)的圖正則化項通過特征分解改為基于L2,1范數(shù)的正則化項，并對權重矩陣施加了一個低秩約束。該方法能夠降低噪聲數(shù)據(jù)對特征選擇的影響，并且在保留了數(shù)據(jù)局部幾何結構的同時又很好地保留了數(shù)據(jù)的全局結構。理論分析和實驗結果均表明，與現(xiàn)有的特征選擇方法相比，所給出的方法具有更好的效果。

在未來的研究中，將對所提出的框架進行擴展，以對不完整的高維數(shù)據(jù)進行特征選擇，因為在許多實際應用中經(jīng)常會發(fā)現(xiàn)不完整的數(shù)據(jù)集。