盛 超 宋 鵬 鄭文明 趙 力

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

1 引言

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

目前,特征提取和特征選擇是兩種重要的數(shù)據(jù)降維技術(shù)。特征提取方法并不考慮特征是否有用,只是單純的將原始數(shù)據(jù)轉(zhuǎn)換成一種容易識別的特定形式[5]。特征選擇方法是從原始高維數(shù)據(jù)中選擇一部分最能夠表示數(shù)據(jù)信息的特征,以生成新的特征子集,它并不會改變原始的數(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]。也正因為高維數(shù)據(jù)通常不含有標(biāo)簽信息,所以近些年來無監(jiān)督特征選擇引起了廣泛的關(guān)注。

無監(jiān)督特征選擇方法分為過濾式[12]、包裹式[13]和嵌入式[14-15]三類。過濾式方法的特征選擇過程是完全獨立于學(xué)習(xí)算法的,通常是對特征進(jìn)行打分排序,然后選擇分?jǐn)?shù)較高的特征,經(jīng)典方法如Laplacian score[16]。獨立于學(xué)習(xí)算法選擇出來的特征可能并不適合特定的學(xué)習(xí)算法,為了解決這一問題,許多包裹式方法被提出。包裹式方法基于學(xué)習(xí)算法來選擇特征。常見的包裹式方法包括greedy search[17]、floating search[18]和random search[19]等。但是包裹式方法對學(xué)習(xí)算法的依賴性過強,這在一定程度上限制了特征選擇的性能。嵌入式方法是將特征選擇的過程和學(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)算法選擇具有判別力的特征。對于處理高維數(shù)據(jù),子空間學(xué)習(xí)作為降維的重要方法,也被應(yīng)用到了特征選擇中。如Shang等人提出的基于子空間學(xué)習(xí)的圖正則化特征選擇(Subspace learning based graph regularized feature selection,SGFS)[23],將子空間學(xué)習(xí)和圖正則化結(jié)合到特征選擇中,能夠在處理高維數(shù)據(jù)的同時較好地保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu)。在[24]中,Shang等人提出了基于局部判別的稀疏子空間學(xué)習(xí)特征選擇(Local discriminative based sparse subspace learning for feature selection,LDSSL),通過將局部判別引入到子空間學(xué)習(xí)的特征選擇中,可以很好地選擇更有判別力的特征。

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

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

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

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

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

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

(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]。充分挖掘這些局部信息可以提高算法的性能。這里我們引入兩個圖拉普拉斯分別保持樣本空間和特征空間的局部結(jié)構(gòu)。

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

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

(4)

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

(5)

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

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

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

(6)

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

(7)

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

最后,將子空間學(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)化求解

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

(9)

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

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

(10)

(11)

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

(12)

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

(13)

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

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

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

5 實驗與分析

5.1 實驗準(zhǔn)備

為了驗證提出方法的有效性,本文在六個公開數(shù)據(jù)集上與幾種經(jīng)典及新穎的特征選擇算法進(jìn)行了對比實驗,在下文給出了數(shù)據(jù)集和對比方法的詳細(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位志愿者的人臉圖像組成,這些圖像是在時間不同、燈光不同和面部表情不同的條件下拍攝的;Isolet是字母語音信號數(shù)據(jù)集,共包含1560個訓(xùn)練樣本;Yale64是關(guān)于人臉表情的數(shù)據(jù)集,共包含15個不同的個體,165張人臉圖像;JAFFE數(shù)據(jù)集是由來自日本的10位女性的人臉表情圖像構(gòu)成的,共包含213幅人臉圖像。為了保證與對比方法之間的一致性,以上所使用的數(shù)據(jù)集均為原始矩陣格式,未進(jìn)行進(jìn)一步的特征提取。

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

5.2 實驗參數(shù)設(shè)置

首先,對于需要構(gòu)建局部圖的方法,將k近鄰的個數(shù)設(shè)置為5,計算相似度的高斯函數(shù)參數(shù)設(shè)置為10。對于本文提出的方法,為了保證特征選擇矩陣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)整。對于所有方法,選擇特征的數(shù)量為{20, 30, 40, 50, 60, 70, 80, 90, 100}。在選擇特定數(shù)量的特征后,使用K-means進(jìn)行聚類。總共進(jìn)行40次聚類實驗,選擇最優(yōu)結(jié)果和其他對比方法的最優(yōu)結(jié)果進(jìn)行比較。算法迭代求解的最大次數(shù)設(shè)置為30。

5.3 實驗結(jié)果分析

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

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

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

為了進(jìn)一步驗證本文方法的優(yōu)越性,圖2給出了在六種不同數(shù)據(jù)集上對于聚類精確率的參數(shù)敏感性分析。在本文提出的方法中,主要的平衡參數(shù)為控制偽標(biāo)簽回歸系數(shù)α和圖正則約束系數(shù)β。因此,這里主要對這兩個參數(shù)進(jìn)行參數(shù)敏感性實驗。從圖2可以看出,隨著參數(shù)值的改變,大部分?jǐn)?shù)據(jù)集上的聚類精確率在相對穩(wěn)定的范圍內(nèi)變化。對于部分存在波動的數(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 有效性實驗

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

圖3給出了聚類精確率在兩種消融方法和完整方法之間的對比結(jié)果。從圖中可以看出,在六個數(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ù)和特征選擇矩陣,保證算法的魯棒性和特征的稀疏性。實驗結(jié)果表明,相比其他對比方法,本文提出的方法能夠選擇出更具代表性的特征。本文提出的無監(jiān)督特征選擇算法主要適用于小樣本高維數(shù)據(jù),未來算法優(yōu)化的方向則是如何處理大規(guī)模高維數(shù)據(jù)?？稍O(shè)計并行算法將時間復(fù)雜度降低,使之能夠在較短的時間內(nèi)完成對大規(guī)模數(shù)據(jù)的特征選擇。