周婉瑩 馬盈倉

（西安工程大學(xué)理學(xué)院 西安 710048）

1 引言

由于存在大量高維數(shù)據(jù)，特征選擇作為許多任務(wù)的預(yù)處理步驟占據(jù)關(guān)鍵位置，如聚類［1～2］，分類［3～4］，人臉識(shí)別［5～6］等。關(guān)于是否使用標(biāo)簽，特征選擇分為三類：監(jiān)督、半監(jiān)督和無監(jiān)督。由于獲取數(shù)據(jù)標(biāo)簽十分費(fèi)力，因此無監(jiān)督特征選擇在現(xiàn)實(shí)中更實(shí)用，更富有挑戰(zhàn)。

無監(jiān)督特征選擇方法主要包括過濾式方法［7～9］，包裝式方法［10］，嵌入式方法［11～15］。其中，嵌入式方法最常用，文獻(xiàn)［16］概述結(jié)構(gòu)化稀疏特征選擇，這是一種嵌入式方法。嵌入式方法將特征選擇和訓(xùn)練模型結(jié)合，模型優(yōu)化期間直接評(píng)估特征重要性。為利用數(shù)據(jù)幾何結(jié)構(gòu)，現(xiàn)有的無監(jiān)督特征選擇大多采用譜分析方法，大量文獻(xiàn)證實(shí)該方法具有良好性能［17］。

傳統(tǒng)基于譜分析的特征選擇方法［18～19］包括兩個(gè)步驟。首先，通過圖拉普拉斯算子或非負(fù)矩陣分解探索數(shù)據(jù)結(jié)構(gòu)。然后，利用稀疏正則化學(xué)習(xí)特征權(quán)重矩陣進(jìn)行特征選擇。這些方法至少存在兩個(gè)問題：1）獨(dú)立構(gòu)造相似矩陣和選擇特征，導(dǎo)致相似矩陣只能從原始數(shù)據(jù)導(dǎo)出，在后續(xù)過程中保持不變；2）僅側(cè)重選擇在聚類或分類任務(wù)中起決定作用的判別特征，忽略了特征冗余。如人臉圖像中有眼睛、鼻子、嘴巴等特征，選擇冗余高的特征會(huì)使數(shù)據(jù)失去多樣性且降低其在聚類或分類任務(wù)中的性能。因此，我們考慮建立基于譜分析和稀疏回歸的無監(jiān)督特征選擇算法。

2 模型建立

其中，F(xiàn)={ f1，f2，…，fn} ∈?n×m是數(shù)據(jù)的指示矩陣，fi是低維流形中第i個(gè)樣本的指示向量。通過對(duì)特征權(quán)重矩陣W施加正交約束WTW=I，使模型在優(yōu)化過程中保持?jǐn)?shù)據(jù)結(jié)構(gòu)，避免奇異解。同時(shí)對(duì)F施加正交約束FTF=I，來減少維數(shù)和避免奇異解。

模型（1）利用最小二乘回歸探索數(shù)據(jù)低維結(jié)構(gòu)，未能發(fā)現(xiàn)局部幾何結(jié)構(gòu)。譜分析表明，數(shù)據(jù)的局部幾何結(jié)構(gòu)可通過最近鄰有效建模?？紤]模型（1）中指示矩陣F也是低維空間中的數(shù)據(jù)結(jié)構(gòu)。自然想到，如果兩個(gè)數(shù)據(jù)點(diǎn)xi和xj鄰近，它們的指示向量 fi和 fj也應(yīng)該鄰近?；诖耍瑯?gòu)造圖正則項(xiàng)，表示為用譜分析中一個(gè)基本但重要的等式：將模型（1）優(yōu)化為

S第i個(gè)對(duì)角元素為

為了自適應(yīng)的構(gòu)造相似矩陣S，定義樣本點(diǎn)xi可被所有其他樣本連接的概率為sij( j =1，2，…，n )，sij是相似矩陣S的元素。兩數(shù)據(jù)相鄰的概率可視為它們的相似性。根據(jù)常識(shí)，較近的樣本具有較大的連接概率，因此sij與xi和xj之間的距離成反比。采用歐氏距離的平方，即確定概率s的方法是解決下面問題：

其中sij是向量si∈?n×1的第 j個(gè)元素。為避免S某些行全部為零，為S添加約束siT1=1，使S行和為1。問題（4）只有最近數(shù)據(jù)點(diǎn)可以使xi鄰域的概率為1，且其他數(shù)據(jù)點(diǎn)不是xi的鄰域。所以在不涉及數(shù)據(jù)點(diǎn)任何距離信息的情況下，解決下面問題：

該問題的最優(yōu)解使所有數(shù)據(jù)點(diǎn)都可以是xi的鄰域，且具有相同概率結(jié)合問題（4）和問題（5），解決下面問題：

其中第二項(xiàng)是正則項(xiàng)，γ是正則化參數(shù)。根據(jù)流形學(xué)習(xí)理論，總會(huì)存在一個(gè)低維流形可以表達(dá)高維數(shù)據(jù)的結(jié)構(gòu)。參考文獻(xiàn)［20］，使用線性組合XW將原始特征映射到低維流形中。應(yīng)用到問題（6），得到

通過以上分析，將問題（7）與模型（3）結(jié)合，給出無監(jiān)督特征選擇的優(yōu)化目標(biāo)如下：

其中β是參數(shù)。為保證更好的結(jié)果，使用W 的?2，1范數(shù)對(duì)W正則化，確保用于選擇特征的W行稀疏，減少特征冗余。得到自適應(yīng)的基于稀疏回歸和譜分析的無監(jiān)督特征選擇（SSUF）的模型如下：

其中λ是正則化參數(shù)，可確定W的稀疏程度，λ越大，W越稀疏，‖‖W2，1越小。W的?2，1范數(shù)定表示向量wi的?2范數(shù)，‖‖wi2越大，表示第i個(gè)特征越重要。

已經(jīng)全面介紹了SSUF模型，如何解模型（9）成為當(dāng)務(wù)之急。

3 模型求解

模型（9）的優(yōu)化涉及四個(gè)變量：W ，F(xiàn)，S和b。顯然，b不受任何約束。根據(jù)KKT定理［21］，變量b可通過模型（9）的拉格朗日函數(shù)的一階導(dǎo)數(shù)確定。模型（9）關(guān)于b的拉格朗日函數(shù)為

模型（10）僅涉及三個(gè)變量：W ，F(xiàn)和S。下面采用交替迭代優(yōu)化方法，即交替固定兩個(gè)變量?jī)?yōu)化另一個(gè)變量。

3.1 固定W和F，更新S

當(dāng)W 和F固定時(shí)，模型（10）轉(zhuǎn)化為

根據(jù)等式（2），得到

下面，推導(dǎo)問題（12）的封閉解。拉格朗日函數(shù)為

其中，θ和φi≥0是拉格朗日乘子。等式（13）關(guān)于si求導(dǎo)并令其等于0：

事實(shí)上，關(guān)注數(shù)據(jù)局部結(jié)構(gòu)可獲得更好的性能。因此，我們學(xué)習(xí)一個(gè)稀疏的si，即只有xi的k個(gè)最近鄰才能連接到xi。學(xué)習(xí)稀疏相似矩陣S的另一個(gè)好處是可以大大減輕實(shí)驗(yàn)的計(jì)算負(fù)擔(dān)。

假設(shè)di1≤di2≤…≤din。如果最優(yōu)的si只有k個(gè)非零元素，根據(jù)等式（15），知道 sik＞0且si，k+1=0 。因此，有

由等式（15）和約束條件siT1=1，可以得到

因此，根據(jù)問題（16）和（17），得到關(guān)于 γi的不等式：

為了獲得恰好具有k個(gè)非零元素的si的最優(yōu)解，將γ設(shè)置為

因?yàn)閗是一個(gè)整數(shù)且具有明確含義，所以鄰域數(shù)k比正則化參數(shù)γ容易確定。

3.2 固定W和S，更新F

固定模型（10）W 和S，優(yōu)化F等于求解：

根據(jù)矩陣性質(zhì)，模型（18）滿足下面推導(dǎo)：

由于W 固定，經(jīng)上述推導(dǎo)，模型（18）等價(jià)于求解：

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

因?yàn)閱栴}（20）與Stiefel流形二次問題標(biāo)準(zhǔn)形式一致，它可通過文獻(xiàn)［22］提出的廣義冪迭代算法有效解決。算法1給出詳細(xì)過程。

算法1：解決問題（20）

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

初始化：隨機(jī)矩陣 F∈?n×m滿足 FTF=I，正定矩陣A?=υI-A∈?n×m，υ為任意常數(shù)

Repeat：

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

2）通過M 的緊致奇異值分解計(jì)算USVT=M，其中U∈?n×m，S∈?m×m，V∈?m×m

3）更新 F←UVT

Until收斂

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

3.3 固定F和S，更新W

當(dāng)F和S固定時(shí)，模型（10）變?yōu)?/p>

其中，S是相似矩陣。

又根據(jù)文獻(xiàn)［24］，當(dāng) wi≠0( )i=1，2，…，d ，關(guān)于W的導(dǎo)數(shù)為

問題（23）同樣用廣義冪迭代方法求解，詳細(xì)算法在算法2給出。算法3總結(jié)了SSUF算法。

算法2：解決問題（23）

輸入：矩陣C∈?d×d和 E∈?d×m

初始化：隨機(jī)矩陣W∈?d×m滿足WTW=I，正定矩陣C?=υI-C∈?d×d，υ為任意常數(shù)

Repeat：

1）更新 N←2C?W+2E

2）通過 N的緊致奇異值分解計(jì)算USVT=N，其中U∈?d×m，S∈?m×m，V∈?m×m

3）更新W←UVT

Until收斂

輸出：特征權(quán)重矩陣W∈?d×m

算法3：SSUF

輸入：數(shù)據(jù)矩陣 X∈?d×n，中心矩陣 H∈?n×n，參數(shù)α，β，λ和k

初始化：相似矩陣 S∈?n×n，隨機(jī)矩陣 F∈?n×m滿足FTF=I，隨機(jī)矩陣W∈?d×m滿足WTW=I

Repeat：

1）通過等式（15）更新 S

3）通過算法1更新F

4）通過算法2更新W

Until收斂

輸出：將 ‖wi‖2(i=1，2，…，d )按降序排列，選出前 l個(gè)特征作為特征子集I

4 收斂性分析

本節(jié)將證明算法SSUF收斂。令

由不等式（26）可知，不等式（24）成立，算法SSUF收斂。

5 實(shí)驗(yàn)

本節(jié)進(jìn)行特征選擇實(shí)驗(yàn)，驗(yàn)證SSUF算法的有效性和優(yōu)越性，在展示實(shí)驗(yàn)結(jié)果之前，先詳細(xì)介紹一些實(shí)驗(yàn)方案。

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

提出的SSUF算法在四個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行評(píng)估，包括兩個(gè)面部圖像數(shù)據(jù)集，UMIST［13］和 ORL［11］；一個(gè)物體圖像數(shù)據(jù)集，COIL20［25］；一個(gè)生物數(shù)據(jù)集，LUNG［26］。表1總結(jié)了這些數(shù)據(jù)集的細(xì)節(jié)。

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

1）對(duì)比算法

為驗(yàn)證SSUF的有效性，將其與五種常用的無監(jiān)督特征選擇方法比較，包括拉普拉斯評(píng)分法［7］（LS）、多聚類特征選擇［11］（MCFS）、無監(jiān)督判別特征選擇［27］（UDFS）、魯棒無監(jiān)督特征選擇［9］（RUFS）、魯棒圖正則化無監(jiān)督特征選擇［20］（SOGFS）。下面詳細(xì)描述這些方法。

LS：通過構(gòu)建樣本拉普拉斯近鄰圖，以特征局部保持能力為準(zhǔn)則對(duì)樣本特征權(quán)重排序，采用啟發(fā)式策略逐個(gè)選取最優(yōu)特征構(gòu)成特征子集。

MCFS：通過譜分析捕獲局部流形結(jié)構(gòu)，對(duì)特征權(quán)重施加?1范數(shù)正則化使特征稀疏，選擇最能保持聚類結(jié)構(gòu)的特征，提高特征局部保持能力。

UDFS：采用局部類間散度最大化與類內(nèi)散度最小化策略獲取最優(yōu)特征子集，將判別分析和?2，1范數(shù)結(jié)合到無監(jiān)督特征選擇中。

RUFS：使用靈活流形嵌入、非負(fù)矩陣分解和?2，1范數(shù)同時(shí)執(zhí)行聚類和特征選擇。

SOGFS：自適應(yīng)確定相似矩陣，同時(shí)進(jìn)行局部結(jié)構(gòu)學(xué)習(xí)和特征選擇。

2）參數(shù)設(shè)置

在相同策略中設(shè)置所有方法的參數(shù)使實(shí)驗(yàn)公平，即搜索網(wǎng)格 {10-4，10-3，10-2，10-1，1，101，102，103，104}，并記錄最優(yōu)結(jié)果。為消除K-means聚類方法引起的隨機(jī)效應(yīng)，執(zhí)行20次隨機(jī)起點(diǎn)的K-means，且最終報(bào)告平均值。所選的特征數(shù)量在{50，100，150，200，250，300} 中變化。還使用所有特征執(zhí)行K-means作為基線。

3）評(píng)價(jià)指標(biāo)

使用兩種廣泛使用的評(píng)價(jià)指標(biāo)評(píng)估所選特征的性能，精確度（ACC）和歸一化互信息（NMI）。ACC和NMI的值越大，代表特征選擇的效果越好。

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

使用不同數(shù)量所選特征的ACC和NMI評(píng)估每種方法的性能。圖1和圖2清晰展示了幾種不同特征選擇算法在四個(gè)數(shù)據(jù)集上的效果。圖中橫坐標(biāo)表示選擇特征的個(gè)數(shù)，縱坐標(biāo)分別表示以ACC和NMI作評(píng)價(jià)指標(biāo)時(shí)的值。從圖中可明顯看出，本文提出的SSUF算法在大多數(shù)實(shí)驗(yàn)中優(yōu)于其他5種方法，甚至優(yōu)于Baseline。

具體來說，以ACC作評(píng)價(jià)指標(biāo)時(shí)，在UMIST數(shù)據(jù)集上，選擇特征數(shù)50，100，150，200，250時(shí)，都是最佳結(jié)果，且與次佳結(jié)果相比，有大約3%改進(jìn)；在ORL數(shù)據(jù)集上，與次優(yōu)方法RUFS相比，有3%改進(jìn)；在COIL20數(shù)據(jù)集上，選擇特征數(shù)50，100，150，250，300時(shí)，達(dá)到最佳效果，與次佳結(jié)果相比，有大約8%改進(jìn)；在LUNG數(shù)據(jù)集上，選擇特征數(shù)100，150，200，250，300時(shí)，都是最佳結(jié)果，與次佳結(jié)果相比，有大約4%改進(jìn)。以NMI作評(píng)價(jià)指標(biāo)時(shí)，在UMIST數(shù)據(jù)集上，選擇特征數(shù)50，100，150，200時(shí)，達(dá)到最佳結(jié)果；在ORL數(shù)據(jù)集上，與次優(yōu)方法RUFS相比，有2%改進(jìn)；在COIL20數(shù)據(jù)集上，與次佳結(jié)果相比，有大約3%改進(jìn)；在LUNG數(shù)據(jù)集上，選擇特征數(shù)100，150，200，250，300時(shí)，達(dá)到最佳結(jié)果，與次佳結(jié)果相比，有大約7%改進(jìn)。

圖2 選擇不同特征數(shù)的4個(gè)數(shù)據(jù)集歸一化互信息

通過特征選擇，獲得更有價(jià)值的精確數(shù)據(jù)。與使用所有特征執(zhí)行K-means的基線Baseline相比，使用SSUF算法進(jìn)行特征選擇的結(jié)果更好。這直接說明特征選擇可以提高數(shù)據(jù)質(zhì)量。

5.4 參數(shù)靈敏度

為研究SSUF的參數(shù)靈敏度，使用ACC評(píng)估參數(shù)α，β和λ。通過兩個(gè)數(shù)據(jù)集ORL和COIL20展示結(jié)果。圖3中，（a）和（b）分別表示在數(shù)據(jù)集ORL和COIL20上選擇不同特征數(shù)時(shí)，固定 β=10和λ=0.0001，隨參數(shù) α 變化ACC的變化情況；（c）和（d）分別表示在數(shù)據(jù)集ORL和COIL20上選擇不同特征數(shù)時(shí)，固定α=10和λ=0.0001，隨參數(shù) β變化ACC的變化情況；（e）和（f）分別表示在數(shù)據(jù)集ORL和COIL20上選擇不同特征數(shù)時(shí)，固定α=10和β=0.0001，隨參數(shù)λ變化ACC的變化情況?？梢钥闯觯琒SUF對(duì)α和 β不敏感，對(duì) λ敏感。作為‖‖W2，1正則項(xiàng)的系數(shù)，λ影響W的稀疏性。當(dāng)λ較大時(shí)，得到的W有更多的行是稀疏的，在某種程度上可獲得更精確的特征序列。

圖3 算法的參數(shù)靈敏度

6 結(jié)語

本文利用最小二乘回歸模型結(jié)合譜分析和稀疏正則化提出一個(gè)無監(jiān)督特征選擇算法。該算法能夠選擇更稀疏的特征，使特征之間相互競(jìng)爭(zhēng)，消除冗余。此外，還設(shè)計(jì)了交替迭代算法解決提出的SSUF，并且在4個(gè)真實(shí)數(shù)據(jù)集上與幾種常用方法的對(duì)比實(shí)驗(yàn)證實(shí)了SSUF的有效性和優(yōu)越性。我們未來的工作之一是用?2，0范數(shù)‖‖W2，0替換稀疏正則項(xiàng)‖‖W2，1，研究對(duì)特征選擇的影響。