聯合不相關回歸和非負譜分析的無監督特征選擇

朱星宇，陳秀宏

（1.江南大學 人工智能與計算機學院，江蘇 無錫 214122;2.江南大學 江蘇省媒體設計與軟件技術重點實驗室，江蘇 無錫 214122）

在信息時代背景下產生了海量的高維數據，然而這些數據通常含有大量冗余特征和噪聲，降低了算法的性能。因此，如何從高維數據中選出最有效的特征即特征選擇已成為一項研究熱點，特征選擇旨在通過去除冗余、不相關和有噪聲的特征，找到一組簡潔且具有良好泛化能力的特征，由此產生的方法已在機器學習[1]、數據挖掘[2]和生物信息學[3]等領域得到了廣泛的應用。基于是否使用標簽，特征選擇方法可分為有監督學習[4]和無監督學習[5]。

有監督學習依賴于數據的標簽信息，并利用它直接指導學習過程。然而，從未標記數據中提取最有判別性的信息是一個具有挑戰性的問題，由于無監督特征選擇可以根據原始數據的潛在屬性來確定特征的重要性，因此近年來越來越受到研究人員的關注。本文主要研究無監督特征選擇方法。

基于譜分析的無監督特征選擇因其出色的性能引起了廣泛關注，本節將回顧一些比較經典的譜特征選擇方法。無監督的判別特征選擇(L2,1-norm regularized discriminative feature selection for unsupervised learning)[6]聯合使用判別分析和L2,1范數進行無監督特征選擇，它雖然可以選擇判別性的特征，但卻忽略了數據間的內在結構。Nie 等[7]提出了靈活流形嵌入(flexible manifold embedding:a framework for semi-supervised and unsupervised dimension reduction)作為降維的一般框架，非負判別特征選擇(unsupervised feature selection using nonnegative spectral analysis)[8]則在FME 框架中結合特征選擇和譜聚類學習，它具有魯棒非負矩陣分解、局部學習和魯棒特征學習的優勢。聯合嵌入學習和稀疏回歸(joint embedding learning and sparse regression:a framework for unsupervised feature selection)[9]是基于FME 和L2,1范數的特征選擇方法，它致力于嵌入學習高維樣本的低維表示。最近，Nie 等[10]提出了結構最優圖特征選擇(unsupervised feature selection with structured graph optimization)，該方法同時執行特征選擇和局部結構學習，同時它可以自適應地確定數據間的相似性矩陣，但過于嚴格的正交約束選擇出的特征會丟失一定程度的判別性，從而降低他們在聚類或分類任務中的性能。自適應圖的廣義不相關回歸(generalized uncorrelated regression with adaptive graph for unsupervised feature selection)[11]通過最大熵來自適應地構造相似圖，進而同時進行特征選擇和譜聚類，但它在學習相似圖時采用標簽矩陣學習，沒有考慮原始數據的類簇結構，這顯然不是很合理。

盡管上述無監督特征選擇方法已經在各種應用中取得了良好的性能，但仍有以下不足：1)上述基于譜特征選擇的方法構造的相似圖是從原始數據得到且是靜態的，而現實世界的數據始終包含大量噪聲，這使得靜態相似矩陣很不可靠，進而破壞局部流形結構；2)最優相似矩陣應具有精確的c個連通分量（c是類簇數），它能更準確地揭示數據的局部鄰域結構；3)通過傳統正交約束選擇出的特征雖達到了低冗余的目的，但會丟失一些判別性的特征，這些特征在分類任務中往往能起到關鍵作用。

綜合上述分析，本文聯合廣義不相關回歸、結構化最優圖和非負譜分析，提出一個聯合不相關回歸和非負譜分析的無監督特征選擇模型。模型中對相似矩陣增加包含精確的c個連通分量的約束，可以用來動態學習結構化最優圖，進而更準確地揭示數據之間的局部結構信息；同時通過非負譜聚類可以學習到更真實準確的聚類指標；利用廣義不相關約束的正則回歸方法選擇不相關和判別性的特征，有效避免不相關約束導致的平凡解。在不同數據集上的實驗表明所提出的方法是有效的，且該模型在無監督二維圖像的特征選擇領域，如：醫學圖像分類、人臉識別、模式識別等計算機視覺任務方面有著廣泛的應用價值。

1 相關工作

1.1 廣義不相關回歸模型

無監督特征選擇也可以表示為回歸模型，從而正則化回歸模型也廣泛應用在無監督特征選擇中。但是，已有工作忽略了特征的不相關性。尤其是當只需少量特征時，需要選擇最具判別性的特征。Li 等[11]提出的以下廣義不相關回歸模型(generalized uncorrelated regression model，GURM) 可以獲得具有判別性且不相關的流形結構：

式中：W∈Rd×c是回歸矩陣，b∈Rc×1是偏差項，F∈Rn×c是學習的嵌入聚類結構；正則化項‖W‖2,1可使得W的行是稀疏的，進而選擇重要的特征；β是正則化參數，β越大，W行越稀疏；=St+βG為廣義散度矩陣，G為d×d對角矩陣，其對角元素定義為

這里，ε>0是一個很小的值，可避免因W的行稀疏而導致的分母為0 的情形；St=XHXT是樣本數據的總散度矩陣。一般地，當樣本數量小于數據維度時，St是奇異的，而SG t總是正定的，這樣約束條件可使數據在投影子空間中是統計不相關的，這樣可以很好地保留數據的全局結構。當 β很小時，可使投影后樣本之間高度不相關，因此，約束條件在描述樣本的不相關性時要優于正交約束WTW=I和傳統不相關約束WTStW=I。

1.2 局部結構學習

研究表明，相似性矩陣可用來描述數據間的局部結構。然而，大多數構造相似性矩陣的方法并沒有考慮原始數據中的冗余特征和噪聲，從而導致所學習到的局部結構不夠準確，最終影響特征選擇的結果。本節采用一種自適應確定相似度矩陣的方法[12]，可以同時執行特征選擇和局部結構學習。

兩個數據樣本相鄰的概率可以用來描述它們之間的相似度，記相似度矩陣為S∈Rn×n，其中元素sij表示相似性圖中與樣本xi和xj相對應的結點之間相連的概率。樣本xi和xj越接近，則對應的連接概率sij越大，它與對應結點之間的距離成反比。相似度矩陣S∈Rn×n可通過以下優化問題得到：

1.3 結構化最優圖學習

如果學習得到的相似矩陣恰好包含c個連通分量時（即它僅含有c個對角分塊），則每個樣本的近鄰是最佳的。但是，問題(3)(式(3))的解一般不具備此性質，大多數情況下其解只包含1個連通分量[12]。

受文獻[14]的啟發，對拉普拉斯矩陣LS=DS?的秩進行約束可使得矩陣S具有c個連通分量。這時，問題(3)轉化為

然而，問題(4)(式(4))很難直接求解，因為秩約束是一個復雜的非線性約束。假設半正定矩陣LS的n個非負特征值依次由小到大排列σ1(LS)≤σ2(LS)≤···≤σn(LS)，則問題(4)可轉化為

這里F∈Rn×c是類指標矩陣。故問題(5)(式(5))可重寫為

正交非負約束可使得F的每一行只有一個元素大于0，其他元素都等于0。從而得到的類指標矩陣F更準確，且獲得更具判別性的信息。此外，求解問題(7)(式(7))得到的S包含精確的c個連通分量，能夠捕獲更準確的局部結構信息。

2 聯合不相關回歸和非負譜分析模型(JURNFS)

2.1 模型建立

根據流形學習的理論，希望原始空間中樣本的近鄰關系在低維投影空間中得到保持，為此，本文討論在低維空間內學習最優圖。設W∈Rd×c是投影矩陣，則由(7)可得到以下模型：

將模型(8)(式(8))與稀疏回歸模型(1)相結合，得到本文聯合不相關回歸和非負譜分析模型：

其中，α、β、λ是正則化參數。在式(9) 中,第1 項、第4 項和第5 項刻畫了無監督不相關回歸和非負譜分析，用于學習稀疏投影矩陣和預測標簽矩陣，且L2,1范數可使得W保持行稀疏，從而能夠選擇出更具有價值和判別性的特征；第2 項和第3 項用于學習數據的局部結構，確保原始空間內數據的相似結構在投影子空間內得到保持。這里第2 項未采用L2范數距離的平方，這是考慮到若原始數據中有噪聲，平方會擴大噪聲對模型學習與分類的影響。

令問題(9)(式(9))關于b的 拉格朗日函數為

其中，Γ(W,F,S)表示式(9)中依賴于W、F、S但又獨立于b的項。取Ωb(b)關于b的導數并令其等于0，得

在實際應用中，數據結構總是多模態的，為了在多模態數據上獲得更好的性能，可以研究圖的局部性。假設S的每一行有一個具體的αi[13]，再結合式(11)，問題(9)可重寫為

此時，參數 αi可以控制每個樣本自適應近鄰的數量[12]。

2.2 模型求解

由于式(12)中的目標函數是凸的，故它有全局最優解，但直接求其全局解比較困難。本節給出一種交替優化方法來迭代求解它。

1)固定F和S，更新W

此時，問題(12)(式(12))等價于以下問題：

該問題將不相關性表現為流形結構，且具有閉式解。問題(15)(式(15))可表示為

問題(16)(式(16))可以利用廣義冪迭代方法[16]求解，詳細過程見算法1。

算法1求解問題(14)

此時，問題(12)等價于：

其中，E=H+2λLS，M=HXTW。

此問題可采用乘性更新規則[17]來求解。首先考慮它的松馳問題：

其中，γ為充分大的正數，由KKT 最優性條件得

這里，φij為對應于約束Fij≥0的非負拉格朗日乘子。于是有以下更新規則：

再對F的每一列歸一化使得它滿足條件(FTF)ii=1,i=1,2,···,n。

3)固定W和F，更新S

其中，fi和fj分別為F的第i行和第j行。該問題可分解為以下n個獨立的子問題：

其中，mi=(eil+λfil,···,ein+λfin)。

該問題可利用文獻[18]中的方法求解，并可自適應地確定式(9)中參數α[13]，進而獲得具有精確k個非零分量的最優解si。

以上3 步可迭代地進行，直到目標函數收斂或滿足終止條件，整個過程概括為算法2。

算法2JURNFS

2.3 時間復雜度分析

在以上算法中，主要的計算復雜度為步驟①中的奇異值分解和矩陣求逆，故本算法時間復雜度最高為O(n2d)，假設算法迭代T次，則該部分的時間復雜度為O(Tn2d)，從而整個算法的時間復雜度為O(Tn2d)。

3 實驗及分析

3.1 實驗方案

在本節中，通過進行大量實驗以充分驗證本文所提出方法的有效性和優越性。在展示結果之前，首先提供一些詳細的實驗方案。

1)數據集：實驗中使用了6個公共數據集，包括2個人臉數據集ORL[19]和BIO[20]，1個物體數據集COIL20[21]，1個手寫字數據集BA[22]，1個樹葉數據集LEAVES[23]以及1個生物學數據集LUNG[24]。數據集的詳細信息見表1 及圖1 所示。

圖1 部分數據集的圖片Fig.1 Visualization of some datasets

表1 數據集信息Table1 Detail introduction to datasets

2)對比算法：實驗中將本文所提出的聯合不相關回歸和非負譜分析模型(joint uncorrelated regression and nonnegative spectral analysis for unsupervised feature selection,JURNFS)與5個特征選擇方法進行了比較，分別是：無監督判別特征選擇(L2,1-norm regularized discriminative feature selection for unsupervised learning,UDFS)[6]、非負判別性特征選擇(unsupervised feature selection using nonnegative spectral analysis,NDFS)[8]、聯合嵌入學習和稀疏回歸(joint embedding learning and sparse regression:A framework for unsupervised feature selection,JELSR)[9]、最優結構圖的特征選擇(unsupervised feature selection with structured graph optimization,SOGFS)[10]和用于無監督特征選擇的自適應圖的廣義不相關回歸(generalized uncorrelated regression with adaptive graph for unsupervised feature selection,URAFS)[11]。

3)評價指標：為了驗證所選特征的優劣性，本文利用兩個度量標準來衡量每種算法的性能，一個是識別精度(ACC)[25]，定義：

式中：yi是每一個樣本的真實標簽；是對應的預測標簽；n是測試樣本的數量；函數δ(·,·)衡量兩個輸入參數之間的關系，如果兩個參數相等則等于1，否則等于0，聚類精度越高，說明算法的效果越好；另一個評價指標是標準化互信(NMI)[26]，定義：

式中：C是真實標簽的集合；C′是預測標簽的集合；MI(C,C′)是互信息指標；Γ(C)、Γ(C′)分別是C和C′的熵。NMI 越大，表示算法性能越穩定。

4)參數設置：本文通過網格搜索來確定每個算法的最優參數，所有算法的參數都是從{10?4,10?3,10?2,···,102,103,104}中選取。此外，在聚類實驗中，本文采用流行的K-means 聚類方法，用于對具有選定特征形成的新數據進行聚類，每個數據集的選擇特征數在表1 中列出。為減少Kmeans 中隨機起點觸發的偶然性影響，對每種算法進行10 次聚類，并計算平均值。對于分類實驗，本文使用1-最近鄰(1-NN)分類器對選定特征的測試圖像數據進行分類。為了減少偏差，所有實驗均重復運行10 次以隨機選擇訓練樣本，最后計算平均分類結果。另外，K-means 聚類方法中的K值設置為c，并且將每種方法中子空間的維數也都設置為c，除SOGFS 的子空間維數設置為d/2。在UDFS、NDFS、JELSR、SOGFS 和JURNFS 中，最近鄰k的數量設置為5。

3.2 聚類性能與分析

本節將不同方法的聚類精度進行比較，實驗中將每個數據集的所有樣本都用作訓練集。首先，每個算法在每個數據集上進行學習以選擇重要且具有判別性的特征，不同數據集所選特征數也不一樣，具體細節見表1；然后，本文使用K-means聚類算法對由這些選擇出的特征所形成的新樣本進行聚類實驗。圖2 給出了6個算法在6個數據集上的聚類精度，從圖2 可以看出，在大多數情況下，本文所提出的JURNFS 相比其他算法都取得了比較好的效果，這證明了JURNFS 的優越性。

此外，1)從圖2(a)和(b)可知，JURNFS 在人臉數據集上的效果遠遠領先于其他5個算法，并且JURNFS 在ORL 和BIO 上相對于其他算法分別平均提升了約3.28%和4.75%，這是因為JURNFS 通過學習數據的局部流形結構選擇出了人臉上更具有判別性的特征，這些特征能夠顯著地代表原數據，因而獲得了較高的聚類精度。2)所有算法在COIL20 和BA 數據集上的聚類效果都比較接近，這可能是由于這兩個數據集里的樣本特征區分度信息不是很高，所有算法學習到了近似的局部結構，而JURNFS 中采用的廣義不相關約束在保留低冗余度特征的同時維持了對判別性部分特征的關注（如COIL20 中物體的輪廓商標部分；BA 中文字筆畫拐彎部分），所以JURNFS 的聚類效果仍能夠優于其他算法。3)在LEAVES和LUNG 數據集上，所有算法的聚類效果隨著所選特征數而波動。這也證明并不是選擇的特征數越多，聚類效果越好。因為特征越多，冗余的特征也可能越多，因此有必要進行特征選擇。而JURNFS 采用低維流形結構化最優圖學習和廣義不相關回歸聯合學習的方式保留了判別性局部結構信息（如LEAVES 中葉的根莖部，LUNG 中的病灶部分），因此在處理非人臉數據集時仍能具有較好的性能。此外，可以發現LUNG 數據集的數據量較大，標簽類數只有5，因此每一類標簽的訓練數據集較大，這也可能是JURNFS 優于其他算法的原因，因為在這種情況下JURNFS 可以選擇更準確、更判別性的特征。總之，通過特征選擇獲得的精煉的數據包含更多有價值的信息，而JURNFS 通過廣義不相關回歸以及結構化最優圖，所選擇的特征更具判別性及有效性，因而可以獲得更好的性能。

圖2 6個算法在6個數據集上的聚類精度Fig.2 Clustering accuracies of six methods on six different datasets

為了進一步說明JURNFS 的優越性，表2 給出了在6個不同的數據集上6 種不同算法的標準偏差的最優NMI 值，其中最優值以黑體加粗。一般而言，NMI 值越高，特征選擇的性能越好。顯然，與其他特征選擇算法相比，JURNFS 的NMI 相對較高，這也表明JURNFS 具有更好的算法性能。

表2 不同數據集上不同方法的最佳NMI (標準偏差)Table2 Best NMI with standard deviation of different methods on different data sets %

3.3 分類性能與分析

本節將不同方法的分類精度進行比較，首先從不同數據集上的每個類中隨機選取適當數量的樣本作為訓練樣本，其余的作為測試樣本。對于ORL、LEAVES 和LUNG 數據集，隨機選取5個圖像樣本作為每類的訓練樣本，剩余的作為測試樣本。對于BIO、BA 和COIL20 數據集，隨機選取10個圖像樣本作為每個類的訓練樣本，剩余的作為測試樣本。此外，不同的數據集在實驗中選取的特征數量也不同(見表1)。

圖3 描述了不同特征選擇方法的分類精度隨所選特征數量的增加而變化的情況。由該圖可以發現JURNFS 在所有數據集上都能取得很好的分類效果，這得益于JURNFS 聯合使用廣義不相關回歸和非負譜分析，在保留全局結構的同時自適應進行局部結構學習，很好地保留了特征的判別性信息，這些判別性特征在后續進行分類任務時起到了關鍵作用。

圖3 6個算法在6個數據集上的分類精度Fig.3 Classification accuracies of six methods on six different datasets

此外，圖4 通過重構圖展示了部分算法在ORL 數據集上選擇的特征，不難看出：1)隨著選擇特征數的變化，JURNFS 可以選擇信息量較大的特征（如眼睛、鼻子、嘴巴），并且JURNFS 在選擇特征數較少的情況下會優先選擇具有判別性的特征；2)對于SOGFS，盡管它在聚類任務中表現良好，但它選擇的特征主要分布在皮膚區域，而不是人臉的區分器官特征。這表明邊緣和輪廓上的特征有助于提高這些方法的聚類性能。

圖4 6個算法在ORL 數據集上的重構圖，所選特征個數從左到右依次為{150,250,350,450,550,650,1 024}Fig.4 Reconstruction graph of 6 algorithms on ORL data set,the number of selected features from left to right is {150,250,350,450,550,650,1 024}

3.4 算法參數與性能分析

本節將分析JURNFS 中參數的穩定性。在所提出的模型(9)中，有3個參數：α、β、λ。其中，正則化參數α用于保證在學習相似矩陣S時，每個樣本都有機會成為xi的近鄰；正則化參數β用于調整投影矩陣W的稀疏性；正則化參數λ確保學習到的樣本標簽足夠平滑。因此，參數α、β、λ共同調節回歸與特征選擇之間的效果。在實驗中，可以根據文獻[15]中的方法自適應確定參數α，因此，本節將專注于研究參數β和λ對模型的影響。這里只給出JURNFS 在數據集ORL、BIO 和COIL20 上的不同參數組合變化圖。

觀察圖5 可知，在ORL 和BIO 數據集上，JURNFS 受λ的影響較小，而隨著β的增大，JURNFS的聚類效果顯著提高。這可能是由于在人臉數據集上，JURNFS 經過有限次迭代學習到的標簽矩陣接近于真實標簽，故λ對目標函數的影響不大，而隨著β增大，使得W更加稀疏，因而選擇出的特征更加具有判別性及代表性，故聚類效果得到提升。在COIL20 數據集上，JURNFS 的聚類效果隨著β和λ的變化而波動，這表明此時β和λ同時影響著JURNFS 的聚類效果，并且隨著β的增大，JURNFS 的聚類精度會呈現出一個先增加后減少的趨勢。因此在實驗中，對于不同數據集仍需要找到一組合適的參數。

圖5 JURNFS 在不同數據集上不同參數組合的聚類精度Fig.5 Clustering accuracies of JURNFS with different parameter combinations on different dataset,respectively

為驗證JURNFS 算法的收斂性，本文考慮在數據集ORL 和BA 上驗證式(9)中目標函數隨迭代次數增加的變化情況。從圖6 可見，隨著迭代次數增加，目標函數值單調減少，且在5 次迭代后即可收斂，這也驗證了JURNFS 的高效性。

圖6 JURNFS 在不同數據集上的收斂性Fig.6 Convergence behaviors of JURNFS on different datasets

此外，本文還通過算法的運行時間來評估JURNFS 的性能。本文將所有算法在ORL、BIO、COIL20 和BA 數據集上的聚類時間進行比較。不同算法的運行時間見表3。可以看到，JURNFS 的運行時間與其他算法相比仍具有很好的競爭力。

表3 不同方法的運行時間Table3 Computational time of different methods s

4 結束語

本文提出了一種新穎的無監督特征選擇方法，將廣義不相關回歸、結構化最優圖和非負譜分析結合，通過廣義不相關回歸模型選擇不相關和判別性的特征，利用結構化最優圖自適應學習數據間的局部結構信息，同時結合非負譜聚類來學習局部流形中的標簽矩陣，這使得所學習到的標簽矩陣更真實可靠。文中還提出了一個有效的迭代算法來求解提出的模型，并在真實數據集上進行了大量實驗證明了該方法的有效性和優越性。后續的工作主要集中在以下2個方面： 1)提高算法在不同噪聲（如光照、遮擋等）水平下的魯棒性；2)提高算法處理高維數據的速度。