最大熵和?2,0 范數約束的無監督特征選擇算法

周婉瑩，馬盈倉，續秋霞，鄭 毅

西安工程大學 理學院，西安710600

1 引言

特征選擇作為數據挖掘和機器學習的重要組成部分[1-2]，受到越來越多的關注[3-4]。特征選擇的目的是選擇最能代表原始特征空間的最優特征子集[5-6]，減小特征維數，緩和維數災難，縮短模型訓練時間，提高性能，增強模型的泛化能力[7-8]。根據類標簽信息的可用性，特征選擇方法可分為有監督方法和無監督方法。監督特征選擇是在類標簽信息的指導下，搜索最具鑒別性的特征子集[9-10]。這類特征選擇方法具有清晰的充分的信息，能夠有效地找到學習任務的最優特征子集[11]。然而，多數情況，標記所有樣本往往是費時且昂貴的，這要求以無監督的方式學習算法，選擇最相關的特征子集。由于缺少類標簽信息，無監督特征選擇旨在探索數據的內在結構，學習到的特定結構作為偽監督信息，尋找最優特征子集[12-13]。由于學習到的結構信息往往是不確定的、不充分的、模糊的，因此無監督特征選擇是一個具有挑戰性的任務[14-15]。

根據搜索策略，特征選擇方法可分為過濾式方法、包裝式方法、嵌入式方法[16-17]。其中，嵌入式方法最常用，它將特征選擇和模型訓練結合，模型優化期間直接評估特征重要性。近年來，隨著稀疏性研究的發展，理論和實證都表明稀疏性是真實數據的內在屬性，稀疏正則化也應用到特征選擇模型中[18]。根據范數結構，稀疏性可以從以下兩種特征選擇正則項中獲得：平滑稀疏性通過?1范數或?0范數正則化選擇單個特征；結構稀疏性通過?2,1范數、?2,∞范數或?2,0范數選擇組特征。

將結構化稀疏正則項嵌入到無監督特征選擇中，它可以在所有具有稀疏性的類中選擇特征。從稀疏性角度看，雖然?2,0范數更理想，但由于其非凸性和非光滑性會在優化中產生很大困難，學者們更喜歡凸的?2,1范數作正則項[19-20]。而?2,1范數的正則化參數沒有明確含義，對于不同的數據，可能會發生顯著變化，需要研究者仔細調整其值[21]。本文提出了一種高效、魯棒、實用的特征選擇模型，直接用?2,0范數約束解決原始稀疏問題，而不采用它的松弛或近似方法，且令?2,0范數約束的值等于選擇特征的數量，賦予其實際意義。并提出一種有效的算法解決本文提出的無監督特征選擇模型，在四個真實數據集上的實驗表明，該算法優于其他幾種常用的無監督特征選擇算法。

2 模型建立

給定輸入數據集X={ x1,x2,…,xn} ∈?d×n，其中xi∈?d×1表示第i 個樣本，且這些數據點屬于c 類。使用經典最小二乘回歸模型，優化以下函數：

其中，W={w1;w2;…;xd} ∈?d×c是特征權重矩陣，表示對X 的特征加權，wi是W 的第i 行，d 是數據維數。1=(1 ,1,…,1)T∈?n×1是全1 列向量。b ∈?c×1是偏差，Y ∈?n×c是標簽矩陣或已知類結構。是Frobenius 范數，定義為，其中Tr(· )是跡。第二項是正則化項，λ 是正則化參數。為了獲得更精確的模型，使用?2,0范數約束且不將它作為正則項[22]。使用以下目標函數來選擇多類問題的特征：

其中，k 是選擇特征的數量，當W 的?2,0范數等于選擇特征的數量時，意味著特征權重矩陣W 只有k個非零行，該k 個非零行的索引序列即可確定數據集中要選擇的特征。M ∈?m×n。

遺憾的是，這種回歸模型很難直接應用到無監督特征選擇中。Y 作為未知變量，需要在模型（1）中進行優化，且當W=0，b=(1 ,0,…,0)T，Y=(1 ,0,…,0 )時，可能會引發平凡解。為避免上述情況并特別利用最小二乘回歸模型進行無監督特征選擇，故采用下面優化模型：

其中，F={ f1,f2,…,fn} ∈?n×c是輸入數據的指示矩陣，fi是c 維流形中第i 個樣本的指示向量。通過對F 施加正交約束FTF=I ，使模型在優化過程中保持數據結構，避免奇異解。

模型（2）執行流形學習并利用最小二乘回歸探索數據低維結構。然而，這種流形學習只在歐氏空間中進行，不能發現數據的局部幾何結構[23]。譜分析表明，局部幾何結構可通過數據點的最近鄰圖有效地建模。考慮模型（2）中的指示矩陣F 在低維空間的數據結構。很自然地想到，如果兩個數據點xi和xj鄰近，它們的指示向量fi和fj也應該鄰近。基于此，構造圖正則項，將數據的局部幾何結構嵌入到流形學習中。采用譜分析中一個基本但重要的等式：將模型（2）優化為：

為了自適應地構造相似矩陣，采用一種相似矩陣信息熵最大化的思想。信息熵也稱香農熵表示某種特定信息的出現概率，定義如下：

通過上述分析。給出基于最大熵和?2,0范數約束的無監督特征選擇算法（ENUF）的模型如下：

其中，β 是正則項參數。

3 模型求解及算法

3.1 模型重構

模型（6）的優化涉及四個變量：W，F，S 和b。顯然，b 不受任何約束。根據KKT 定理[24]，變量b 的最優解可通過模型（6）的拉格朗日函數的一階導數確定。模型（6）關于b 的拉格朗日函數表示如下：

其中，R(W,F,S)表示拉格朗日函數中與b 無關的項。

b 的最優解推導如下：

將b 的最優解代入模型（6），模型簡化為：

模型（7）的優化涉及三個變量：W，F 和S。根據文獻[25]，采用增廣拉格朗日函數法（ALM）求解模型（7），引入一個松弛變量V ，令V=W ，則模型（7）可重新表示為：

化簡得：

其中，Y 是拉格朗日乘子，μ ＞0 是懲罰參數。下面介紹一種基于ALM的交替迭代優化算法求解模型（8）。

3.2 模型求解

（1）固定W ，F 和V ，更新S

當W ，F 和V 固定時，模型（8）變為：

結合譜分析中的重要等式（3），問題（9）的拉格朗日函數可以表示如下：

其 中，Φ={φi|i=1,2,…,n} 和Π={πij|i,j=1,2,…,n} 是拉格朗日乘子。根據優化理論，問題（9）的拉格朗日函數必須滿足以下KKT條件：

通過求解（10），可以得到：

其中，ri是r( )φi的縮寫，表示依賴φi的變量。

由于fi是第i 個樣本的指示向量，因此當兩個樣本鄰近時，由等式（12）計算出的樣本間的相似性更高。

（2）固定W ，S 和V ，更新F

當模型（8）的W 和S 固定時，F 的優化等于解決以下問題：

根據矩陣的性質，問題（13）滿足下面推導：

由于W 是固定的，經上述推導，問題（13）等價于求解：

其中，A=H+αLS，B=HXTW 。

因為問題（14）與Stiefel 流形的二次問題的標準形式一致，所以它可以通過文獻[26]中提出的一種有效算法解決，該算法稱為廣義冪迭代算法。詳細算法在算法1中給出。

算法1 解決問題（14）

輸入：矩陣A ∈?n×n和B ∈?n×c

初始化：隨機矩陣F ∈?n×c滿足FTF=I ，正定矩陣A?=υI-A ∈?n×c，υ 為任意常數

Repeat：

1.更新M ←2A?F+2B

2.通過M 的緊致奇異值分解計算USVT=M ，其中

U ∈?n×c，S ∈?c×c，V ∈?c×c

3.更新F ←UVT

Until 收斂

輸出：指示矩陣F ∈?n×c

（3）固定F，S 和V ，更新W

當F，S 和V 固定時，模型（8）變為：

求W 的導數并將其設置為0，得：

則：

其中，I ∈?d×d是單位矩陣。

（4）固定W ，F 和S，更新V

當模型（8）的W ，F 和S 固定時，V 的優化等價于求解下面問題：

其求解過程在算法2中總結。

算法2 解決問題（17）

輸入：矩陣W ∈?d×c，Y ∈?d×c；參數μ；選擇特征的個數k

Process：

2.計算向量p ∈?d×1，其中每個元素定義為?i=1,2,…,d

3.對p 排序，找出前k 個項對應的索引q=( q1,q2,…,qk)T

4.如果i ∈q，則把W 的第i 行賦給V

如果i ?q，則把零向量0T∈?1×c賦給V輸出：松弛變量矩陣V ∈?d×c

根據上述分析，在算法3中總結了算法ENUF。

算法3 ENUF

輸入：數據矩陣X ∈?d×n；中心矩陣H ∈?n×n；參數α，β 和k

初始化：相似矩陣S ∈?n×n，隨機矩陣F ∈?n×c滿足FTF=I ，隨機矩陣W ∈?d×c

Repeat：

1.通過等式（12）更新S

3.通過算法1更新F

4.通過等式（16）更新W

5.通過算法2更新V

Until 收斂

征作為特征子集

3.3 算法分析

盡管模型（8）不是凸問題，但本文算法是有效的，在每次迭代中，給定Y 和μ，算法3 都能找到其局部解。ALM算法的收斂性在文獻[25]中得到證明和討論。

在ENUF算法中模型（8）的優化分為交替迭代解決問題（9）、問題（14）、問題（15）和問題（16）。通過求解問題（12）進一步解決子問題（9），計算復雜度為O( n2)；子問題（14）的計算復雜度為O( n2d )；通過求解（16）解決子問題（15），計算復雜度為O( d3)；子問題（17）的計算復雜度為O( n )。因此，NSUF的計算復雜度為O(d3+n2d+n2+n )，其中，n 和d 分別是樣本數和特征數。

4 實驗

為了驗證本文提出的無監督特征選擇算法的有效性和優越性，使用四個常用的真實數據集進行綜合實驗。本章重點評估ENUF 算法在SRBCT、JAFFE、ORL和COIL20 數據集上的實驗效果，并與幾種常用的無監督特征選擇算法在相同數據集上的結果進行比較，統一使用K-means 聚類算法對所選擇的特征進行精確度（ACC）和歸一化互信息（NMI）評價。

4.1 數據集

本文在生物數據集SRBCT、表情數據集JAFFE[27]、人臉圖像數據集ORL[28]和物體圖像數據集COIL20[29]上進行實驗。表1總結了這些數據集的細節。

表1 數據集描述

SRBCT：由83 個樣本組成，共分為4 類，分別為29個、11個、18個和25個。每個樣本都包含2 308個基因。

JAFFE：共有213張圖像組成。選取了10名日本女學生，每個人做出7 種表情。7 種表情包括憤怒、厭惡、恐懼、高興、悲傷、驚訝、中性。

ORL：由40個不同年齡、不同性別和不同種族的人的人臉圖像組成。每個人10幅圖像，共計400幅灰度圖像，圖像尺寸是92×112，圖像背景為黑色。其中人臉部分表情和細節均有變化，例如笑或不笑、眼睛睜著或閉著，戴或不戴眼鏡等，人臉姿態也有變化，其深度旋轉和平面旋轉可達20°，人臉尺寸也有最多10%的變化。該庫是目前使用最廣泛的標準人臉數據庫。

COIL20：哥倫比亞物體圖像庫是一種多類圖像分類數據集，由20個物體的1 440幅灰度圖像組成。包含對20個物體從不同角度的拍攝，每隔5°拍攝一幅圖像，每個物體72張圖像。

4.2 實驗設置

4.2.1 對比算法

為了驗證ENUF的有效性，將其與五種常用的無監督特征選擇方法進行比較，包括拉普拉斯評分法（LS）[30]、多聚類特征選擇（MCFS）[31]、無監督判別特征選擇（UDFS）[32]、魯棒無監督特征選擇（RUFS）[33]、魯棒圖正則化無監督特征選擇（SOGFS）[34]。下面對這些方法進行詳細描述。

LS：通過構建樣本拉普拉斯近鄰圖，以特征局部保持能力為準則對樣本特征權重進行排序，采用啟發式策略逐個選取最優特征構成特征子集。

MCFS：通過譜分析捕獲局部流形結構，對特征權重施加?1范數正則化使得特征呈現有效的稀疏化特性，然后選擇最能保持聚類結構的特征，提高特征局部保持能力。

UDFS：采用局部類間散度最大化與類內散度最小化的策略以獲取最優特征子集，將判別分析和?2,1范數結合到無監督特征選擇中。

RUFS：使用靈活流形嵌入，非負矩陣分解和?2,1范數同時執行魯棒聚類和魯棒特征選擇。

SOGFS：自適應地確定相似矩陣，同時進行局部結構學習和特征選擇。

4.2.2 參數設置

在相同策略中設置所有方法的參數以使實驗足夠公平，即搜索網格{10-4，10-3，10-2，10-1，1，101，102，103，104}，并記錄最優結果，為消除K-means聚類方法引起的隨機效應，執行25 次隨機起點的K-means 聚類，并且最終報告平均值。使用數據集的類數作為K-means 聚類中的參數K 。所選的特征數量在{50，100，150，200，250，300}中變化。還使用所有特征執行K-means作為基線。

4.2.3 評價指標

為了評估所選特征的性能，本文使用兩種廣泛使用的評價指標，即精確度（ACC）和歸一化互信息（NMI）來評估特征選擇的性能。ACC 和NMI 的值越大，代表特征選擇的效果越好。

ACC的定義如下：

其中，N 是數據集的類別數；yi和ci分別是數據點xi的真實類別標簽和預測類別標簽；δ( )yi,c 是一個函數，如果y=c，則等于1，反之等于0；map()?是最優映射函數，將每個類別標簽映射到Hungarian算法[35]的類別中。給定兩個變量P 和Q，NMI定義為：

其中，H( P )和H( Q )分別是P 和Q 的熵，I( P,Q )是P 和Q 之間的互信息。對于本文算法，P 和Q 分別是K-means聚類結果和真實標簽。NMI反映了K-means聚類結果和真實標簽之間的一致性。

4.3 實驗結果

把使用聚類算法得到的類別標簽與數據集提供的類別標簽比較后進行算法評估。表2～表9 分別展示了不同數據集上幾種無監督特征選擇算法在選取最優參數的情況下選擇不同特征數的最佳結果，表中加粗項表示在選擇特征數相同時該算法的效果最優，下劃線項表示該算法的效果排第二位。為驗證所提出的算法在數據降維上的有效性，與選擇所有特征（Baseline）作為實驗特征數進行實驗對比。

表2 不同算法在SRBCT數據集上的精確度%

表3 不同算法在JAFFE數據集上的精確度%

表4 不同算法在ORL數據集上的精確度%

表5 不同算法在COIL20數據集上的精確度%

表6 不同算法在SRBCT數據集上的歸一化互信息

表7 不同算法在JAFFE數據集上的歸一化互信息

表8 不同算法在ORL數據集上的歸一化互信息

表9 不同算法在COIL20數據集上的歸一化互信息

從表1對數據集的介紹和表2～表9的結果分析，得出以下結論：一般來說，隨著選擇特征數的增加，特征選擇方法的性能并不總是增加，而是呈現先增加后減小的趨勢。真實數據集總是包含許多冗余特征，因此必要的信息只包含在小部分特征集中。如果過度增加特征子集的大小，很多噪聲特征將進入最終結果，這肯定會降低算法性能。該趨勢間接驗證了特征選擇方法的有效性。

通過特征選擇，獲得包含更有價值的精確數據。與使用所有特征執行K-means的基線相比，在大多數情況下使用所選特征的結果會變得更好。特別是本文提出的ENUF方法，平均有超過13%的改進。驗證了所提算法降維的有效性，直接說明特征選擇提高了數據質量。

具體來說，以精確度作為評價指標時，本文提出的ENUF方法的性能超過其他方法。在SRBCT數據集中，與第二種最優方法相比，有大約4%的改進。在JAFFE數據集中，與第二種最優方法SOGFS相比，有大約2.4%的改進。在ORL 數據集中，當所選特征數為100、150、200和300時，都達到了最優效果，與第二種最優方法相比，有大約1.3%的改進。在COIL20 數據集中，與第二種最優方法RUFS相比，有大約3.8%的改進。以歸一化互信息作為評價指標時，所提出的NSUF方法的性能也超過其他方法。在SRBCT 數據集中，與第二種最優方法相比，有大約2.8%的改進。在JAFFE數據集中，當所選特征數為100、150、200、250 和300 時，達到了最優效果，與第二種最優方法相比，有大約1.7%的改進。在ORL 數據集中，當所選特征數為100、150、200、250 和300時，NSUF方法達到了最優效果。在COIL20數據集中，與第二種最優方法相比，有大約2%的改進。平均來說ENUF實現了相當好的性能。

圖1 選擇不同特征數的4個數據集的精確度

圖2 選擇不同特征數的4個數據集的歸一化互信息

圖3 算法的收斂曲線

綜合上述實驗結果，圖1 和圖2 分別展示了幾種不同的特征選擇算法在不同數據集上的效果。圖1和圖2更明確地展示了上述結論。

4.4 收斂性

現用實驗驗證算法收斂。通過兩個數據集ORL和COIL20顯示結果。目標值的收斂曲線如圖3所示。參數α 取0.01，β 取0.001，選擇特征的數量k 取150。可以看到，隨著迭代次數不斷增加，目標函數值逐漸減小，最后趨于平穩，表明該算法是收斂的。

5 結語

本文提出了一種無監督特征選擇算法，用于解決?2,0范數約束的優化問題，通過譜分析獲得最優的局部結構，并結合最大熵原理自適應地構造相似矩陣。因?2,0范數約束具有唯一確定的含義，即選擇特征的數量，不涉及參數的選取，所以避免了一部分正則化參數的調整工作。未來的工作之一是，考察相似矩陣對特征選擇的影響，提出更優的構造相似矩陣的方法，實現更好的特征選擇效果。