盛 超 宋 鵬 鄭文明 趙 力
(1. 煙臺大學計算機與控制工程學院, 山東煙臺 264005; 2. 東南大學兒童發(fā)展與學習科學教育部 重點實驗室, 江蘇南京 210096; 3. 東南大學信息科學與工程學院, 江蘇南京 210096)
隨著信息技術的迅速發(fā)展,在機器學習、模式識別等領域產生了大量的無標簽高維數據。這些高維數據存在著大量的噪音和冗余數據,不僅會增加計算機的存儲負擔和處理時間,而且會降低算法的性能[1-2]。因此,如何更高效便捷的處理和使用這些高維數據已經成為一個非常重要的研究方向。處理高維數據的非常關鍵的一點則是去除無關的冗余特征,將有效的特征提取出來生成一個最優(yōu)特征子集[3- 4]。在完成了對高維數據的處理后,后續(xù)對數據的使用將會變得更加高效和方便。
目前,特征提取和特征選擇是兩種重要的數據降維技術。特征提取方法并不考慮特征是否有用,只是單純的將原始數據轉換成一種容易識別的特定形式[5]。特征選擇方法是從原始高維數據中選擇一部分最能夠表示數據信息的特征,以生成新的特征子集,它并不會改變原始的數據表示。根據是否包含標簽信息,可以將特征選擇方法大致分為有監(jiān)督特征選擇、半監(jiān)督特征選擇和無監(jiān)督特征選擇。有監(jiān)督特征選擇方法是指在進行特征選擇之前數據的標簽信息是已知的[6];半監(jiān)督特征選擇方法是只有一部分數據標簽信息是已知的,這樣可以通過已知的標簽信息來提升方法的性能[7];與有監(jiān)督和半監(jiān)督特征選擇方法相比,由于缺少數據的標簽信息,無監(jiān)督特征選擇方法更加具有挑戰(zhàn)性[8-11]。也正因為高維數據通常不含有標簽信息,所以近些年來無監(jiān)督特征選擇引起了廣泛的關注。
無監(jiān)督特征選擇方法分為過濾式[12]、包裹式[13]和嵌入式[14-15]三類。過濾式方法的特征選擇過程是完全獨立于學習算法的,通常是對特征進行打分排序,然后選擇分數較高的特征,經典方法如Laplacian score[16]。獨立于學習算法選擇出來的特征可能并不適合特定的學習算法,為了解決這一問題,許多包裹式方法被提出。包裹式方法基于學習算法來選擇特征。常見的包裹式方法包括greedy search[17]、floating search[18]和random search[19]等。但是包裹式方法對學習算法的依賴性過強,這在一定程度上限制了特征選擇的性能。嵌入式方法是將特征選擇的過程和學習算法結合起來。許多研究發(fā)現數據的局部流形結構中包含許多重要的信息,因此一些保持數據局部結構的特征選擇方法被提出。如Cai等人提出了一種多聚類的特征選擇方法(Multi-cluster feature selection,MCFS)[20],利用譜分析的理論來保持數據的局部結構,選擇出來的特征可以很好的保持數據的譜聚類結構。Yang等人提出了一種L2,1范數正則化的判別特征選擇(L2,1-norm regularized discriminative feature selection for unsupervised learning,UDFS)[21]?;诰€性判別分析(Linear discriminant analysis,LDA)方法[22],UDFS利用線性分類器去預測數據的標簽并標簽來指導算法選擇具有判別力的特征。對于處理高維數據,子空間學習作為降維的重要方法,也被應用到了特征選擇中。如Shang等人提出的基于子空間學習的圖正則化特征選擇(Subspace learning based graph regularized feature selection,SGFS)[23],將子空間學習和圖正則化結合到特征選擇中,能夠在處理高維數據的同時較好地保持數據的局部結構。在[24]中,Shang等人提出了基于局部判別的稀疏子空間學習特征選擇(Local discriminative based sparse subspace learning for feature selection,LDSSL),通過將局部判別引入到子空間學習的特征選擇中,可以很好地選擇更有判別力的特征。
通過對近幾年無監(jiān)督特征選擇算法的研究和分析,本文提出了一種基于子空間學習和偽標簽回歸的無監(jiān)督特征選擇方法。首先,為了更好地處理高維數據,我們將子空間學習和特征選擇融合在統(tǒng)一框架中,并且對特征選擇矩陣進行了L2,1范數的稀疏約束;其次,我們利用回歸函數來學習特征子空間和偽標簽之間的映射關系,從而選擇出更具有判別力的特征;最后,在樣本和特征空間分別加入圖正則化來保持局部結構。因此,該方法能夠有效地將包含數據有效信息的特征選擇出來,完成對高維數據的處理。
為了能夠更直觀地描述本文提出的算法,圖1給出了算法的框架圖。
圖1 提出方法的框架圖Fig.1 The framework of proposed method
對于高維數據,首先利用子空間學習找到一個較低維度的低維子空間,實現對原始數據的降維。假定X∈Rn×d為原始高維數據,n表示數據的數量,d表示特征的維度??梢酝ㄟ^以下?lián)p失函數來學習一個子空間:
(1)
其中H∈Rl×d是重構系數矩陣,用來映射學習到的子空間和原始數據空間之間的關系。XI∈Rn×l是學習到的子空間,|I|是子空間的維度。利用矩陣分解的原理,可以將子空間學習和特征選擇結合起來,得到子空間學習特征選擇的目標函數如下:
(2)
缺乏標簽信息是無監(jiān)督特征選擇存在的挑戰(zhàn)之一。由于無法有效利用標簽信息,很難選擇出具有判別力的特征。為了解決這一問題,本文利用回歸函數學習到的偽標簽來指導特征選擇,從而使得選擇出來的特征更具有判別力。學習到的特征子空間和偽標簽空間之間通常存在一種線性關系[25],通過回歸函數來學習這種映射關系,得到的目標函數如下:
(3)
其中F∈Rn×c表示偽標簽矩陣,c為數據類別的數量,P∈Rl×c為系數矩陣,用來映射特征子空間和偽標簽空間之間的關系。這里采用L2,1范數來約束回歸函數,提高模型的魯棒性。
在高維空間中,數據的局部幾何結構中通常包含著許多重要的信息[20]。充分挖掘這些局部信息可以提高算法的性能。這里我們引入兩個圖拉普拉斯分別保持樣本空間和特征空間的局部結構。
2.3.1樣本空間的局部結構保持
假定兩個樣本是相互接近的,那么它們各自的相關重構也應該接近。為了保持數據空間的局部幾何結構,引入一個相似度矩陣Sd來表示數據之間的相似度。這里利用高斯熱核函數計算樣本之間的相似度,公式如下:
(4)
其中Nk(xi,:)表示xi,:的k個近鄰。最終我們得到樣本空間的局部結構保持目標函數如下:
(5)
式中Ld=Dd-Sd為拉普拉斯矩陣,[Dd]ii=∑j[Sd]ij為對角矩陣,Tr(·)表示矩陣的跡。
2.3.2特征空間的局部結構保持
同樣地,把矩陣的每一列看成一個特征,尋找特征空間的局部幾何結構。利用高斯熱核函數求得不同特征之間的相似度矩陣Sf,公式如下:
(6)
其中Nk(x:,i)表示x:,i的k個近鄰。最終我們得到特征空間的局部結構保持公式如下:
(7)
式中Lf=Df-Sf為拉普拉斯矩陣,[Df]ii=∑j[Sf]ij為對角矩陣。
最后,將子空間學習特征選擇(2)、偽標簽回歸(3)、樣本空間的局部結構保持(5)和特征空間的局部結構保持(7)結合到統(tǒng)一的框架中,得到最終的目標函數。如下:
s.t.W,H,F,P≥0,WTW=Il,FTF=Ic
(8)
其中α、β和λ為平衡參數。
對于提出的目標函數(8),其包含L2,1范數,是非光滑的,很難直接對其進行優(yōu)化求解。因此,本文提出了一種迭代更新的方法來進行優(yōu)化求解,即在求解一個變量時保持其他變量不變。下面給出了具體的優(yōu)化求解過程:
(9)
其中γ和γ1是平衡參數。
(1)對W進行求解,固定H,F,P,U和Q。使用KKT條件(Karush-Kuhn-Tucker)[25],令δijWij=0,得到W的更新公式:
(10)
(11)
(3)對F進行求解,固定W,H,P,U和Q。使用KKT條件,令θijFij=0,得到F的更新公式:
(12)
(4)對P進行求解,固定W,H,F,U和Q。使用KKT條件,令ηijPij=0,得到P的更新公式:
(13)
最終,我們得到四個變量的求解公式,對它們進行迭代更新求解,直到滿足迭代次數或收斂條件。
本節(jié)給出算法的時間復雜度分析,以證明算法的可行性。通過對公式(8)進行分析,算法主要包括子空間學習、偽標簽回歸、圖約束和L2,1范數約束。d為數據的維度,n為數據的樣本數,c為樣本的類別數,l為子空間的維度。樣本空間構圖和特征空間構圖的時間復雜度分別為O(dn2)和O(d2n)。得到計算W,H,F和P的時間復雜度分別為O(nd+nc+dn2+dl),O(nd+d2n),O(nc)和O(cl)。由于子空間的維度和數據的樣本數都小于數據的維度,所以得到算法的時間復雜度為O(T(dn2+nd2))。
為了驗證提出方法的有效性,本文在六個公開數據集上與幾種經典及新穎的特征選擇算法進行了對比實驗,在下文給出了數據集和對比方法的詳細介紹。
使用的數據集包括Lung_dis數據集[27]、COIL20數據集[28]、ORL數據集[20]、Isolet數據集[29]、Yale64數據集[20]和JAFFE數據集[30]。其中Lung_dis是關于人類肺部疾病的生物數據集,包含7種不同類別的疾病;COIL20數據集共有1440張灰度圖像,這些圖像是20種不同物體從不同角度拍攝得來的;ORL是一種人臉數據集,由40位志愿者的人臉圖像組成,這些圖像是在時間不同、燈光不同和面部表情不同的條件下拍攝的;Isolet是字母語音信號數據集,共包含1560個訓練樣本;Yale64是關于人臉表情的數據集,共包含15個不同的個體,165張人臉圖像;JAFFE數據集是由來自日本的10位女性的人臉表情圖像構成的,共包含213幅人臉圖像。為了保證與對比方法之間的一致性,以上所使用的數據集均為原始矩陣格式,未進行進一步的特征提取。
對比的特征選擇算法包括Baseline、LS[16]、MCFS[20]、UDFS[21]、SGFS[23]和LDSSL[24]。其中Baseline是使用所有特征進行實驗的基準方法;LS是一種經典過濾式的方法;MCFS將流形學習的思想引入到特征選擇的算法中;UDFS考慮局部判別信息,可以選擇出具有判別力的特征;SGFS在子空間學習特征選擇中加入了圖正則化,保持了特征空間的局部結構;LDSSL則在子空間學習特征選擇的基礎上加入了局部判別模型。
首先,對于需要構建局部圖的方法,將k近鄰的個數設置為5,計算相似度的高斯函數參數設置為10。對于本文提出的方法,為了保證特征選擇矩陣W和偽標簽矩陣F的正交性,正交約束的平衡參數γ和γ1調節(jié)的范圍為105~108。目標函數中的其他平衡參數α、β和λ調整的范圍為{10-3, 10-2, 10-1, 1, 10, 102, 103}。理論上子空間的維度應該遠小于原始數據的維度,所以子空間的維度在{100, 200, 300, 400, 500}內調整。對于所有方法,選擇特征的數量為{20, 30, 40, 50, 60, 70, 80, 90, 100}。在選擇特定數量的特征后,使用K-means進行聚類??偣策M行40次聚類實驗,選擇最優(yōu)結果和其他對比方法的最優(yōu)結果進行比較。算法迭代求解的最大次數設置為30。
本文對比了不同方法在不同數據集上的聚類精確率(ACC)和互信息率(NMI),結果如表1和表2所示。從表中可以看出,與對比方法進行比較,本文提出的方法在所有數據集上都可以取得更好的結果。這表明利用本文提出的方法選擇出的特征可以更好地表示原始數據的信息,在學習算法上也有更好的表現。對比SGFS,本文提出的方法在考慮了雙圖正則化和偽標簽回歸后,結果有了顯著的提升。這表明雙圖正則化約束可以充分地利用隱藏在原始數據里的局部結構信息,同時偽標簽回歸可以彌補無監(jiān)督特征選擇缺乏標簽信息這一缺點;LDSSL將判別分析和子空間學習結合在一起,但并沒有考慮到偽標簽空間和子空間之間的關系。本文提出的方法利用回歸函數映射特征子空間和偽標簽空間之間的線性關系,從而使得選擇出的特征更具有判別力。
表1 不同數據集上不同方法的聚類精確率
表2 不同數據集上不同方法的互信息率
為了進一步驗證本文方法的優(yōu)越性,圖2給出了在六種不同數據集上對于聚類精確率的參數敏感性分析。在本文提出的方法中,主要的平衡參數為控制偽標簽回歸系數α和圖正則約束系數β。因此,這里主要對這兩個參數進行參數敏感性實驗。從圖2可以看出,隨著參數值的改變,大部分數據集上的聚類精確率在相對穩(wěn)定的范圍內變化。對于部分存在波動的數據集如JAFFE,本文的方法仍可以在特定的參數組合下得到良好的聚類結果。通過以上分析,可以證明本文提出方法的優(yōu)越性和穩(wěn)定性。
圖2 不同數據集上的聚類精確率參數敏感性分析Fig.2 Sensitivity analysis of cluster accuracy parameters on different datasets
本節(jié)對提出的方法進行了有效性實驗,通過設置偽標簽回歸和圖正則化的參數來驗證方法的有效性。將控制偽標簽回歸的平衡參數α設置為0,可以得到不包含偽標簽回歸的方法,簡稱為Ours1;將圖正則約束系數β設置為0,則可以得到沒有圖約束的方法,簡稱為Ours2。
圖3給出了聚類精確率在兩種消融方法和完整方法之間的對比結果。從圖中可以看出,在六個數據集上,Ours的效果都要優(yōu)于Ours1和Ours2。這表明偽標簽回歸和圖正則約束都可以提高方法的效果,也證明了本文提出方法的有效性。
圖3 不同數據集上關于聚類精確率的有效性分析Fig.3 Effectiveness analysis of cluster accuracy on different datasets
本文提出了一種基于子空間學習和偽標簽回歸的無監(jiān)督特征選擇算法。該方法將子空間學習的特征選擇作為基礎框架;在此基礎之上引入了偽標簽回歸,可以利用數據的偽標簽信息指導特征選擇;進一步還通過雙圖正則化分別在數據空間和特征空間進行局部結構保持;最后,利用L2,1范數約束回歸函數和特征選擇矩陣,保證算法的魯棒性和特征的稀疏性。實驗結果表明,相比其他對比方法,本文提出的方法能夠選擇出更具代表性的特征。本文提出的無監(jiān)督特征選擇算法主要適用于小樣本高維數據,未來算法優(yōu)化的方向則是如何處理大規(guī)模高維數據。可設計并行算法將時間復雜度降低,使之能夠在較短的時間內完成對大規(guī)模數據的特征選擇。