基于子空間學(xué)習(xí)和偽標(biāo)簽回歸的無監(jiān)督特征選擇

盛 超 宋 鵬 鄭文明 趙 力

(1. 煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院, 山東煙臺(tái) 264005; 2. 東南大學(xué)兒童發(fā)展與學(xué)習(xí)科學(xué)教育部 重點(diǎn)實(shí)驗(yàn)室, 江蘇南京 210096; 3. 東南大學(xué)信息科學(xué)與工程學(xué)院, 江蘇南京 210096)

1 引言

隨著信息技術(shù)的迅速發(fā)展,在機(jī)器學(xué)習(xí)、模式識(shí)別等領(lǐng)域產(chǎn)生了大量的無標(biāo)簽高維數(shù)據(jù)。這些高維數(shù)據(jù)存在著大量的噪音和冗余數(shù)據(jù),不僅會(huì)增加計(jì)算機(jī)的存儲(chǔ)負(fù)擔(dān)和處理時(shí)間,而且會(huì)降低算法的性能[1-2]。因此,如何更高效便捷的處理和使用這些高維數(shù)據(jù)已經(jīng)成為一個(gè)非常重要的研究方向。處理高維數(shù)據(jù)的非常關(guān)鍵的一點(diǎn)則是去除無關(guān)的冗余特征,將有效的特征提取出來生成一個(gè)最優(yōu)特征子集[3- 4]。在完成了對(duì)高維數(shù)據(jù)的處理后,后續(xù)對(duì)數(shù)據(jù)的使用將會(huì)變得更加高效和方便。

目前,特征提取和特征選擇是兩種重要的數(shù)據(jù)降維技術(shù)。特征提取方法并不考慮特征是否有用,只是單純的將原始數(shù)據(jù)轉(zhuǎn)換成一種容易識(shí)別的特定形式[5]。特征選擇方法是從原始高維數(shù)據(jù)中選擇一部分最能夠表示數(shù)據(jù)信息的特征,以生成新的特征子集,它并不會(huì)改變?cè)嫉臄?shù)據(jù)表示。根據(jù)是否包含標(biāo)簽信息,可以將特征選擇方法大致分為有監(jiān)督特征選擇、半監(jiān)督特征選擇和無監(jiān)督特征選擇。有監(jiān)督特征選擇方法是指在進(jìn)行特征選擇之前數(shù)據(jù)的標(biāo)簽信息是已知的[6];半監(jiān)督特征選擇方法是只有一部分?jǐn)?shù)據(jù)標(biāo)簽信息是已知的,這樣可以通過已知的標(biāo)簽信息來提升方法的性能[7];與有監(jiān)督和半監(jiān)督特征選擇方法相比,由于缺少數(shù)據(jù)的標(biāo)簽信息,無監(jiān)督特征選擇方法更加具有挑戰(zhàn)性[8-11]。也正因?yàn)楦呔S數(shù)據(jù)通常不含有標(biāo)簽信息,所以近些年來無監(jiān)督特征選擇引起了廣泛的關(guān)注。

無監(jiān)督特征選擇方法分為過濾式[12]、包裹式[13]和嵌入式[14-15]三類。過濾式方法的特征選擇過程是完全獨(dú)立于學(xué)習(xí)算法的,通常是對(duì)特征進(jìn)行打分排序,然后選擇分?jǐn)?shù)較高的特征,經(jīng)典方法如Laplacian score[16]。獨(dú)立于學(xué)習(xí)算法選擇出來的特征可能并不適合特定的學(xué)習(xí)算法,為了解決這一問題,許多包裹式方法被提出。包裹式方法基于學(xué)習(xí)算法來選擇特征。常見的包裹式方法包括greedy search[17]、floating search[18]和random search[19]等。但是包裹式方法對(duì)學(xué)習(xí)算法的依賴性過強(qiáng),這在一定程度上限制了特征選擇的性能。嵌入式方法是將特征選擇的過程和學(xué)習(xí)算法結(jié)合起來。許多研究發(fā)現(xiàn)數(shù)據(jù)的局部流形結(jié)構(gòu)中包含許多重要的信息,因此一些保持?jǐn)?shù)據(jù)局部結(jié)構(gòu)的特征選擇方法被提出。如Cai等人提出了一種多聚類的特征選擇方法(Multi-cluster feature selection,MCFS)[20],利用譜分析的理論來保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu),選擇出來的特征可以很好的保持?jǐn)?shù)據(jù)的譜聚類結(jié)構(gòu)。Yang等人提出了一種L2,1范數(shù)正則化的判別特征選擇(L2,1-norm regularized discriminative feature selection for unsupervised learning,UDFS)[21]?；诰€性判別分析(Linear discriminant analysis,LDA)方法[22],UDFS利用線性分類器去預(yù)測數(shù)據(jù)的標(biāo)簽并標(biāo)簽來指導(dǎo)算法選擇具有判別力的特征。對(duì)于處理高維數(shù)據(jù),子空間學(xué)習(xí)作為降維的重要方法,也被應(yīng)用到了特征選擇中。如Shang等人提出的基于子空間學(xué)習(xí)的圖正則化特征選擇(Subspace learning based graph regularized feature selection,SGFS)[23],將子空間學(xué)習(xí)和圖正則化結(jié)合到特征選擇中,能夠在處理高維數(shù)據(jù)的同時(shí)較好地保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu)。在[24]中,Shang等人提出了基于局部判別的稀疏子空間學(xué)習(xí)特征選擇(Local discriminative based sparse subspace learning for feature selection,LDSSL),通過將局部判別引入到子空間學(xué)習(xí)的特征選擇中,可以很好地選擇更有判別力的特征。

通過對(duì)近幾年無監(jiān)督特征選擇算法的研究和分析,本文提出了一種基于子空間學(xué)習(xí)和偽標(biāo)簽回歸的無監(jiān)督特征選擇方法。首先,為了更好地處理高維數(shù)據(jù),我們將子空間學(xué)習(xí)和特征選擇融合在統(tǒng)一框架中,并且對(duì)特征選擇矩陣進(jìn)行了L2,1范數(shù)的稀疏約束;其次,我們利用回歸函數(shù)來學(xué)習(xí)特征子空間和偽標(biāo)簽之間的映射關(guān)系,從而選擇出更具有判別力的特征;最后,在樣本和特征空間分別加入圖正則化來保持局部結(jié)構(gòu)。因此,該方法能夠有效地將包含數(shù)據(jù)有效信息的特征選擇出來,完成對(duì)高維數(shù)據(jù)的處理。

2 基于子空間學(xué)習(xí)和偽標(biāo)簽回歸的特征選擇

為了能夠更直觀地描述本文提出的算法，圖1給出了算法的框架圖。

圖1 提出方法的框架圖Fig.1 The framework of proposed method

2.1 基于子空間學(xué)習(xí)的特征選擇

對(duì)于高維數(shù)據(jù),首先利用子空間學(xué)習(xí)找到一個(gè)較低維度的低維子空間,實(shí)現(xiàn)對(duì)原始數(shù)據(jù)的降維。假定X∈Rn×d為原始高維數(shù)據(jù),n表示數(shù)據(jù)的數(shù)量,d表示特征的維度。可以通過以下?lián)p失函數(shù)來學(xué)習(xí)一個(gè)子空間:

(1)

其中H∈Rl×d是重構(gòu)系數(shù)矩陣,用來映射學(xué)習(xí)到的子空間和原始數(shù)據(jù)空間之間的關(guān)系。XI∈Rn×l是學(xué)習(xí)到的子空間,|I|是子空間的維度。利用矩陣分解的原理,可以將子空間學(xué)習(xí)和特征選擇結(jié)合起來,得到子空間學(xué)習(xí)特征選擇的目標(biāo)函數(shù)如下:

(2)

2.2 偽標(biāo)簽回歸

缺乏標(biāo)簽信息是無監(jiān)督特征選擇存在的挑戰(zhàn)之一。由于無法有效利用標(biāo)簽信息,很難選擇出具有判別力的特征。為了解決這一問題,本文利用回歸函數(shù)學(xué)習(xí)到的偽標(biāo)簽來指導(dǎo)特征選擇,從而使得選擇出來的特征更具有判別力。學(xué)習(xí)到的特征子空間和偽標(biāo)簽空間之間通常存在一種線性關(guān)系[25],通過回歸函數(shù)來學(xué)習(xí)這種映射關(guān)系,得到的目標(biāo)函數(shù)如下:

(3)

其中F∈Rn×c表示偽標(biāo)簽矩陣,c為數(shù)據(jù)類別的數(shù)量,P∈Rl×c為系數(shù)矩陣,用來映射特征子空間和偽標(biāo)簽空間之間的關(guān)系。這里采用L2,1范數(shù)來約束回歸函數(shù),提高模型的魯棒性。

2.3 雙圖正則化

在高維空間中,數(shù)據(jù)的局部幾何結(jié)構(gòu)中通常包含著許多重要的信息[20]。充分挖掘這些局部信息可以提高算法的性能。這里我們引入兩個(gè)圖拉普拉斯分別保持樣本空間和特征空間的局部結(jié)構(gòu)。

2.3.1樣本空間的局部結(jié)構(gòu)保持

假定兩個(gè)樣本是相互接近的,那么它們各自的相關(guān)重構(gòu)也應(yīng)該接近。為了保持?jǐn)?shù)據(jù)空間的局部幾何結(jié)構(gòu),引入一個(gè)相似度矩陣Sd來表示數(shù)據(jù)之間的相似度。這里利用高斯熱核函數(shù)計(jì)算樣本之間的相似度,公式如下:

(4)

其中Nk(xi,:)表示xi,:的k個(gè)近鄰。最終我們得到樣本空間的局部結(jié)構(gòu)保持目標(biāo)函數(shù)如下:

(5)

式中Ld=Dd-Sd為拉普拉斯矩陣,[Dd]ii=∑j[Sd]ij為對(duì)角矩陣,Tr(·)表示矩陣的跡。

2.3.2特征空間的局部結(jié)構(gòu)保持

同樣地,把矩陣的每一列看成一個(gè)特征,尋找特征空間的局部幾何結(jié)構(gòu)。利用高斯熱核函數(shù)求得不同特征之間的相似度矩陣Sf,公式如下:

(6)

其中Nk(x:,i)表示x:,i的k個(gè)近鄰。最終我們得到特征空間的局部結(jié)構(gòu)保持公式如下:

(7)

式中Lf=Df-Sf為拉普拉斯矩陣,[Df]ii=∑j[Sf]ij為對(duì)角矩陣。

最后,將子空間學(xué)習(xí)特征選擇(2)、偽標(biāo)簽回歸(3)、樣本空間的局部結(jié)構(gòu)保持(5)和特征空間的局部結(jié)構(gòu)保持(7)結(jié)合到統(tǒng)一的框架中,得到最終的目標(biāo)函數(shù)。如下:

s.t.W,H,F,P≥0,WTW=Il,FTF=Ic

(8)

其中α、β和λ為平衡參數(shù)。

3 優(yōu)化求解

對(duì)于提出的目標(biāo)函數(shù)(8),其包含L2,1范數(shù),是非光滑的,很難直接對(duì)其進(jìn)行優(yōu)化求解。因此,本文提出了一種迭代更新的方法來進(jìn)行優(yōu)化求解,即在求解一個(gè)變量時(shí)保持其他變量不變。下面給出了具體的優(yōu)化求解過程:

(9)

其中γ和γ1是平衡參數(shù)。

(1)對(duì)W進(jìn)行求解,固定H,F,P,U和Q。使用KKT條件(Karush-Kuhn-Tucker)[25],令δijWij=0,得到W的更新公式:

(10)

(11)

(3)對(duì)F進(jìn)行求解,固定W,H,P,U和Q。使用KKT條件,令θijFij=0,得到F的更新公式:

(12)

(4)對(duì)P進(jìn)行求解,固定W,H,F,U和Q。使用KKT條件,令ηijPij=0,得到P的更新公式:

(13)

最終,我們得到四個(gè)變量的求解公式,對(duì)它們進(jìn)行迭代更新求解,直到滿足迭代次數(shù)或收斂條件。

4 時(shí)間復(fù)雜度分析

本節(jié)給出算法的時(shí)間復(fù)雜度分析,以證明算法的可行性。通過對(duì)公式(8)進(jìn)行分析,算法主要包括子空間學(xué)習(xí)、偽標(biāo)簽回歸、圖約束和L2,1范數(shù)約束。d為數(shù)據(jù)的維度,n為數(shù)據(jù)的樣本數(shù),c為樣本的類別數(shù),l為子空間的維度。樣本空間構(gòu)圖和特征空間構(gòu)圖的時(shí)間復(fù)雜度分別為O(dn2)和O(d2n)。得到計(jì)算W,H,F和P的時(shí)間復(fù)雜度分別為O(nd+nc+dn2+dl),O(nd+d2n),O(nc)和O(cl)。由于子空間的維度和數(shù)據(jù)的樣本數(shù)都小于數(shù)據(jù)的維度,所以得到算法的時(shí)間復(fù)雜度為O(T(dn2+nd2))。

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)準(zhǔn)備

為了驗(yàn)證提出方法的有效性,本文在六個(gè)公開數(shù)據(jù)集上與幾種經(jīng)典及新穎的特征選擇算法進(jìn)行了對(duì)比實(shí)驗(yàn),在下文給出了數(shù)據(jù)集和對(duì)比方法的詳細(xì)介紹。

使用的數(shù)據(jù)集包括Lung_dis數(shù)據(jù)集[27]、COIL20數(shù)據(jù)集[28]、ORL數(shù)據(jù)集[20]、Isolet數(shù)據(jù)集[29]、Yale64數(shù)據(jù)集[20]和JAFFE數(shù)據(jù)集[30]。其中Lung_dis是關(guān)于人類肺部疾病的生物數(shù)據(jù)集,包含7種不同類別的疾病;COIL20數(shù)據(jù)集共有1440張灰度圖像,這些圖像是20種不同物體從不同角度拍攝得來的;ORL是一種人臉數(shù)據(jù)集,由40位志愿者的人臉圖像組成,這些圖像是在時(shí)間不同、燈光不同和面部表情不同的條件下拍攝的;Isolet是字母語音信號(hào)數(shù)據(jù)集,共包含1560個(gè)訓(xùn)練樣本;Yale64是關(guān)于人臉表情的數(shù)據(jù)集,共包含15個(gè)不同的個(gè)體,165張人臉圖像;JAFFE數(shù)據(jù)集是由來自日本的10位女性的人臉表情圖像構(gòu)成的,共包含213幅人臉圖像。為了保證與對(duì)比方法之間的一致性,以上所使用的數(shù)據(jù)集均為原始矩陣格式,未進(jìn)行進(jìn)一步的特征提取。

對(duì)比的特征選擇算法包括Baseline、LS[16]、MCFS[20]、UDFS[21]、SGFS[23]和LDSSL[24]。其中Baseline是使用所有特征進(jìn)行實(shí)驗(yàn)的基準(zhǔn)方法;LS是一種經(jīng)典過濾式的方法;MCFS將流形學(xué)習(xí)的思想引入到特征選擇的算法中;UDFS考慮局部判別信息,可以選擇出具有判別力的特征;SGFS在子空間學(xué)習(xí)特征選擇中加入了圖正則化,保持了特征空間的局部結(jié)構(gòu);LDSSL則在子空間學(xué)習(xí)特征選擇的基礎(chǔ)上加入了局部判別模型。

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

首先,對(duì)于需要構(gòu)建局部圖的方法,將k近鄰的個(gè)數(shù)設(shè)置為5,計(jì)算相似度的高斯函數(shù)參數(shù)設(shè)置為10。對(duì)于本文提出的方法,為了保證特征選擇矩陣W和偽標(biāo)簽矩陣F的正交性,正交約束的平衡參數(shù)γ和γ1調(diào)節(jié)的范圍為105～108。目標(biāo)函數(shù)中的其他平衡參數(shù)α、β和λ調(diào)整的范圍為{10-3, 10-2, 10-1, 1, 10, 102, 103}。理論上子空間的維度應(yīng)該遠(yuǎn)小于原始數(shù)據(jù)的維度,所以子空間的維度在{100, 200, 300, 400, 500}內(nèi)調(diào)整。對(duì)于所有方法,選擇特征的數(shù)量為{20, 30, 40, 50, 60, 70, 80, 90, 100}。在選擇特定數(shù)量的特征后,使用K-means進(jìn)行聚類?？偣策M(jìn)行40次聚類實(shí)驗(yàn),選擇最優(yōu)結(jié)果和其他對(duì)比方法的最優(yōu)結(jié)果進(jìn)行比較。算法迭代求解的最大次數(shù)設(shè)置為30。

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

本文對(duì)比了不同方法在不同數(shù)據(jù)集上的聚類精確率(ACC)和互信息率(NMI),結(jié)果如表1和表2所示。從表中可以看出,與對(duì)比方法進(jìn)行比較,本文提出的方法在所有數(shù)據(jù)集上都可以取得更好的結(jié)果。這表明利用本文提出的方法選擇出的特征可以更好地表示原始數(shù)據(jù)的信息,在學(xué)習(xí)算法上也有更好的表現(xiàn)。對(duì)比SGFS,本文提出的方法在考慮了雙圖正則化和偽標(biāo)簽回歸后,結(jié)果有了顯著的提升。這表明雙圖正則化約束可以充分地利用隱藏在原始數(shù)據(jù)里的局部結(jié)構(gòu)信息,同時(shí)偽標(biāo)簽回歸可以彌補(bǔ)無監(jiān)督特征選擇缺乏標(biāo)簽信息這一缺點(diǎn);LDSSL將判別分析和子空間學(xué)習(xí)結(jié)合在一起,但并沒有考慮到偽標(biāo)簽空間和子空間之間的關(guān)系。本文提出的方法利用回歸函數(shù)映射特征子空間和偽標(biāo)簽空間之間的線性關(guān)系,從而使得選擇出的特征更具有判別力。

表1 不同數(shù)據(jù)集上不同方法的聚類精確率

表2 不同數(shù)據(jù)集上不同方法的互信息率

為了進(jìn)一步驗(yàn)證本文方法的優(yōu)越性,圖2給出了在六種不同數(shù)據(jù)集上對(duì)于聚類精確率的參數(shù)敏感性分析。在本文提出的方法中,主要的平衡參數(shù)為控制偽標(biāo)簽回歸系數(shù)α和圖正則約束系數(shù)β。因此,這里主要對(duì)這兩個(gè)參數(shù)進(jìn)行參數(shù)敏感性實(shí)驗(yàn)。從圖2可以看出,隨著參數(shù)值的改變,大部分?jǐn)?shù)據(jù)集上的聚類精確率在相對(duì)穩(wěn)定的范圍內(nèi)變化。對(duì)于部分存在波動(dòng)的數(shù)據(jù)集如JAFFE,本文的方法仍可以在特定的參數(shù)組合下得到良好的聚類結(jié)果。通過以上分析,可以證明本文提出方法的優(yōu)越性和穩(wěn)定性。

圖2 不同數(shù)據(jù)集上的聚類精確率參數(shù)敏感性分析Fig.2 Sensitivity analysis of cluster accuracy parameters on different datasets

5.4 有效性實(shí)驗(yàn)

本節(jié)對(duì)提出的方法進(jìn)行了有效性實(shí)驗(yàn),通過設(shè)置偽標(biāo)簽回歸和圖正則化的參數(shù)來驗(yàn)證方法的有效性。將控制偽標(biāo)簽回歸的平衡參數(shù)α設(shè)置為0,可以得到不包含偽標(biāo)簽回歸的方法,簡稱為Ours1;將圖正則約束系數(shù)β設(shè)置為0,則可以得到?jīng)]有圖約束的方法,簡稱為Ours2。

圖3給出了聚類精確率在兩種消融方法和完整方法之間的對(duì)比結(jié)果。從圖中可以看出,在六個(gè)數(shù)據(jù)集上,Ours的效果都要優(yōu)于Ours1和Ours2。這表明偽標(biāo)簽回歸和圖正則約束都可以提高方法的效果,也證明了本文提出方法的有效性。

圖3 不同數(shù)據(jù)集上關(guān)于聚類精確率的有效性分析Fig.3 Effectiveness analysis of cluster accuracy on different datasets

6 結(jié)論

本文提出了一種基于子空間學(xué)習(xí)和偽標(biāo)簽回歸的無監(jiān)督特征選擇算法。該方法將子空間學(xué)習(xí)的特征選擇作為基礎(chǔ)框架;在此基礎(chǔ)之上引入了偽標(biāo)簽回歸,可以利用數(shù)據(jù)的偽標(biāo)簽信息指導(dǎo)特征選擇;進(jìn)一步還通過雙圖正則化分別在數(shù)據(jù)空間和特征空間進(jìn)行局部結(jié)構(gòu)保持;最后,利用L2,1范數(shù)約束回歸函數(shù)和特征選擇矩陣,保證算法的魯棒性和特征的稀疏性。實(shí)驗(yàn)結(jié)果表明,相比其他對(duì)比方法,本文提出的方法能夠選擇出更具代表性的特征。本文提出的無監(jiān)督特征選擇算法主要適用于小樣本高維數(shù)據(jù),未來算法優(yōu)化的方向則是如何處理大規(guī)模高維數(shù)據(jù)。可設(shè)計(jì)并行算法將時(shí)間復(fù)雜度降低,使之能夠在較短的時(shí)間內(nèi)完成對(duì)大規(guī)模數(shù)據(jù)的特征選擇。