半監督類保持局部線性嵌入方法

鄧廷權，王強

（哈爾濱工程大學 數學科學學院，黑龍江 哈爾濱 150001）

隨著信息科技的迅速發展，數據規模的爆炸式增長成為了大數據時代的主要特征之一。在此時代背景下，數據通常具有維數高和稀疏性等特點，為數據挖掘帶來了空前的挑戰。特征提取作為處理高維數據的有效手段，通過提取數據的低維特性，可以將高維特征空間映射到低維特征空間中進行數據的分析和處理，通常分為線性特征提取和非線性特征提取2種方式。非線性特征提取不依賴于線性假設，對于處理非線性結構的數據效果較好，成為當前數據挖掘的熱門方向之一。流形學習[1-6]作為一種非線性特征提取方法，應用了流形在局部結構上與歐氏空間同胚的性質。通過對高維數據樣本的分析來挖掘隱藏的本質結構，從而提取有效的低維特征。然而，流形學習方法仍然存在一些不足，例如：流形學習方法忽略了數據的類別標記信息，提取的特征并不是分類上的最優特征。因此，忽略標記信息而提取到的特征在進行數據聚類或分類時，結果往往與實際存在較大差異。所以希望可以使用半監督[7-14]的方法進行學習，即少量標記信息來指導特征提取，同時又使用大量無標記信息的數據點來刻畫并保持樣本的局部或全局幾何、線性等結構。

局部線性嵌入(LLE)[15]是一種無監督[16]的流形學習方法，直接用它提取的特征進行數據挖掘如聚類或分類得到的結果并不是很理想。因此我們希望將數據集的標記信息引入到LLE方法中用以提高特征提取效果。而已有的一些半監督方法，例如半監督局部線性嵌入方法(semi-supervised locally linear embedding, SSLLE)雖然利用了標記信息對特征提取進行一定的改進，但它只考慮了近鄰點的標記信息做局部調整，因此當整體標記信息較低時每個近鄰中將有可能出現沒有標記點的情況。這時SSLLE將失去作用并且由于它只考慮近鄰的這種調整，當標記信息很多時它們整體的區分度也不大。本文在LLE的基礎上利用近鄰偽標簽賦予得到的標記信息作局部調整，同時從全局[17]角度對同類數據點和異類數據點進行全局調整，使得重構數據低維特征空間時，既保持局部線性結構，又能使提取后的數據在低維特征空間中可以實現具有相同標記信息的數據點互相靠近，而標記不同的數據點彼此分離，從而達到更好的特征提取結果。最后通過聚類分析及可視化證明本文方法的有效性。

1 局部線性嵌入

由Roweis等提出的LLE是一個經典的保持局部線性特性的流形學習方法，可以有效提取高維數據的低維特征。其基本原理為：假設數據是分布在一個流形上的，任一點均可用它的近鄰點經由線性重構而得到。基于局部線性表示系數，構造優化問題使得數據在高維原始空間到低維特征空間的過程中局部線性重構權值不發生變化，獲得高維數據的低維特征。

假設數據集X={x1,x2,···,xn} 中有n個樣本點為特征提取后獲得的n個低維特征矩陣，

對于每個數據點，計算每一個數據點xi到其它點的歐氏距離，找到最近的k個點作為該數據樣本的近鄰，確定數據的k近鄰域。也可采用ε鄰域方法確定數據的近鄰點。

假設任一點xi都可用它的k近鄰通過線性權值加權來得到，由以下優化問題求解線性重構的權矩陣為

容易獲得優化問題式(1)的最優解：

基于局部線性重構矩陣式(2)，構造優化問題：

獲得高維數據X的低維嵌入

根據樣本的鄰域點分布將k維行向量wi擴充成n維行向量則優化問題式(3)的目標函數可化簡為

采用拉格朗日乘子法求解優化問題式(3)，可得MY=λY。即式(3)可轉化為求特征值問題。實對稱半正定矩陣M的最小d個非0特征值對應的特征向量按列排列時，每行做成的向量的就是對應數據的低維特征yi。

2 半監督類保持局部線性嵌入方法

在數據挖掘任務中，監督信息為用戶提供強有力的數據分析基礎。然而，眾多實際問題只能獲得少量樣本的監督標記。半監督機器學習方法應運而生。

LLE是一種經典的無監督高維數據特征提取方法。本文在LLE基礎上提出一種半監督類保持局部線性嵌入方法(SSCLLE)。該方法不僅利用近鄰偽標簽賦予得到的標記信息調整近鄰數據間的距離，而且從全局角度加入了同類數據點和異類數據點的全局約束，使提取后的數據在低維特征空間中可以實現具有相同標記信息的數據點互相靠近，而標號不同的數據點彼此分離，達到更好的特征提取效果。

假設X是一個半監督數據集，其中少部分數據樣本帶有標記(類別標簽)。記Xc是有標簽的數據組成的集合，l(x)∈{1,2,···,f} 是Xc中各數據點所對應的標簽，L={l(x1),l(x2),···,l(xs)}，f是數據集的類數。

一般情況下，Xc中的樣本量較少。在流形學習中，少量監督樣本不能全面描述和刻畫數據的局部和全局流形結構，致使學習到的特征不能準確反映數據的內在特性。本文給出一種近鄰偽標簽賦予的方法，給部分未標記樣本賦予偽標簽，增大標記樣本量。

將所有標記樣本Xc的各自近鄰中的未標記點設置與標記點相同的初標簽，然后對這些初標簽點進行篩選。如果這個未標記點只賦予了一個標簽，則將此標簽設定為這個點的偽標簽。如果這個未標記點有2個以上的偽標簽，把這個點的所有初標簽都去掉，該點依然設定為未標記點，如圖1所示。

圖1 近鄰偽標簽賦值方法示意Fig. 1 Schematic diagram of nearest neighbor pseudo label assignment method

在圖1的左圖中，紅色和綠色的點分別代表標記點(2類)，藍色是無標簽的點。經過上述近鄰偽標簽賦值方法后，只有一類標記信息的近鄰點保留賦予的標簽(右圖新增加的紅色點和綠色點)，而有2種(或多種)標記的近鄰點則依舊標為無標記點，保持其藍色不變(右圖大圓中的2個藍色點)。得到的新標簽數據為Xw，則有標簽的數據組成的集合為Xz=[Xc,Xw],對應的新標簽集合為

新增加的偽標簽雖然不是真實的標簽，但由于其與被標注樣本具有很好的近鄰關系，通過這樣的擴充可增加標記信息的量，有利于更好地描述數據的內在結構，發現樣本中隱藏的鑒別能力。

為了構造出利用全局信息進行調整的優化問題，首先定義同類數據點對集合：

和異類數據點對集合：

分別構造同類樣本項偏差和異類樣本項偏差：

本文的目的是要求同類樣本項偏差盡量小，同時確保異類樣本項偏差盡可能的大。

構造半監督數據集X中每一個數據樣本點的線性重構權值。利用數據中已有的標記信息以及新標記的標記信息來重新調整距離矩陣，從而使得構造的數據點的鄰域更加有利于提取優質的特征。

式中0＜r＜1。

從式(4)可以看出，如果2個樣本有相同的類標，則將其距離縮小。如果2個樣本有不同的類標，則將其距離擴大。在其他情況下，樣本點間的距離保持不變。

再由(2)計算樣本點的鄰域局部線性重構權矩陣由此利用標記信息得到改進后的新重構權矩陣

基于以上分析，構造如下優化問題：

該優化問題式(5)的目標函數由3部分組成。第1項形式上雖然和LLE相同，但其中的重構權矩陣包含了樣本點的半監督信息，能夠確保提取出的特征既保持數據的局部線性結構不變，又能在局部上使類內(同類)數據更緊密，并對類間(異類)數據進行分離的效果。第2項和第3項分別是全局同類樣本偏差和全局異類樣本偏差，目的是確保同類樣本偏差最小，同時確保全局異類樣本偏差最大，參數 α ∈(0,1) 是2個偏差項的平衡系數，權衡同類樣本項和異類樣本項對目標函數的影響。β也是一個平衡參數，用于調節局部線性重構對于目標函數的影響。

式(5)的約束條件與LLE相同，確保提取出的特征在低維空間中旋轉平移伸縮都具有平移和縮放不變性，其中I為d階單位矩陣。

簡記式(5)的目標函數為

這樣，式(6)的第1部分形式上與LLE相同，仍可表示為

式中的M由式(2)、(4)確定。

為了簡化第2部分和第3部分，給定矩陣[10]則對任意均有：

其中 矩陣，則

令

則有：

和

因此，優化問題(5)的矩陣表示形式為

式中：H=βM+αVML?(1?α)VCL； 1 =(1,1,···,1)T是一個n×1 的全1矩陣。采用拉格朗日乘子法求解，優化問題(7)的解轉化為求解HY=λY的特征值問題。

計算矩陣H的前d個最小非零特征值(0≠λ1≤λ2≤···≤λd) 所對應的特征向量(列向量)vp,p=1,2,···,d，將其構成矩陣Y=[v1v2···vp]，則矩陣Y的第i行向量即為高維數據xi的低維特征yi。

3 實驗及結果分析

為了證明本文提出的SSCLLE的性能，在加州大學歐文分校(university of california irvine,UCI)數據集、實物數據集coil_20和手寫數字MNIST數據集上進行實驗。實驗結果分別與經典的無監督流形學習方法LLE、半監督SSLLE[18]方法，半監督拉普拉斯特征映射(semi-supervised laplacian eigenmap, SSLE)[19]和分類約束降維方法(classification constrained dimensionality reduction,CCDR)[20]進行實驗對比。從聚類精度和數據可視化角度對它們進行實驗比較和分析。

在這里簡單介紹3種半監督方法。基于LLE提出的SSLLE，它的思想是結合數據擁有的部分標記信息調整近鄰樣本點之間的距離，再利用調整后的距離來重構權值矩陣。雖然SSLLE可以利用部分標簽信息使得近鄰中同類數據點距離更近，異類數據點更遠從而實現更好的分類以及聚類效果。但由于 SSLLE 方法僅對近鄰點之間的距離做調整，缺乏對全局同類異類點的考慮。當標記點較少時近鄰中可能出現沒有同類或異類的點的情況，這時 SSLLE 將失去作用。而且由于它只考慮近鄰的調整，當標記信息很多時它們整體的區分度也不大。

SSLE和CCDR都是在拉普拉斯特征映射（laplacian eigenmap，LE）的基礎上提出的半監督方法。在這里SSLE也是一種利用信息在局部做調整的方法，缺點和SSLLE類似。而CCDR是一種全局的調整，相較于SSLE有較好的提取效果。

本文SSCLLE方法在保持局部線性結構的同時，不僅利用標記信息對局部做調整，同時利用全局項對全局做調整。使類內數據更緊密，而對類間數據進行分離。從而達到更好的特征提取效果，以下是相關的實驗驗證。

統一對各方法設定參數，進行特征提取。這里用聚類精度作為評判方法有效性的指標之一，利用模糊C均值（fuzzy c-means，FCM）聚類方法進行聚類分析。關于樣本標簽個數做以下設置：從數據集的每類樣本中隨機抽取S(S=5%,10%,···,50%)比例的數據作為已知標簽樣本。取20次實驗的平均值作為最終的聚類精度。參數表示：近鄰個數為k，低維特征維度為d，SSLLE方法調節參數用r表示，SSLE方法中的參數用v表示，CCDR方法中的參數用u表示，本文SSCLLE方法中 α 和 β 分別用a和b表示，r與SSLLE中設置相同。

3.1 UCI中幾個數據集

實驗中從UCI數據庫里選3個數據集，分別為Wine數據集、Seeds數據集和WDBC(wisconsin diagnostic breast cancer)。

然后，分別用5種方法進行實驗比較和分析。根據特征提取的維數d做3組實驗，分別設置d的值為2、3和4。每類數據隨機標記5%，每組實驗進行20次，求聚類精度的平均值來評判5種方法的特征提取效果。表1～3分別是d值為2、3和4時，各方法對3個數據集進行特征提取后得到的平均聚類精度。實驗中，將參數設置為：

表1 數據集信息Table 1 Data set information

表2d=2 時5種方法的平均聚類精度Table 2 Average clustering accuracy of the five methods when d=2 %

表3d=3 時5種方法的平均聚類精度Table 3 Average clustering accuracy of the five methods when d =3 %

由表2～4數據可知：當特征空間的維數d為3和4時，在3個數據集上SSCLLE方法的聚類精度都比其他4種方法高，其他方法在不同數據集之間聚類精度各有高低。而當d為2時，雖然SSCLLE方法在Seeds數據集的實驗中的聚類精度并不是全部保持最高，當標記比例為5%時SSLLE方法僅僅略高于本文方法，在標記比例為15%以及另外2個數據集時SSCLLE的聚類精度最高。總體實驗分析可知，本文提出的半監督流形學習方法SSCLLE相比無監督方法LLE與其他3種半監督方法聚類精度最高，體現出本文方法的優勢。

表4d=4 時5種方法的平均聚類精度Table 4 Average clustering accuracy of the five methods when d=4 %

對于半監督方法來說標記信息的多少會影響聚類的結果。這里把3組UCI數據中的每一個類標記信息比例設置為5%、20%和40%，提取特征維數d=2。圖2為3個數據集在4種半監督方法下的實驗結果。

由圖2的實驗結果可以看出：3個數據集的柱狀分析圖，隨著數據的標記比例的增加，各個半監督方法的聚類精度也在增加，符合半監督方法利用越多標記信息就會提高聚類精度的設想。但明顯可以看出2種基于局部標記信息進行調整的方法SSLLE和SSLE，隨著標記信息的增加聚類精度提升，相對考慮全局信息的SSCLLE與CCDR不明顯。而SSCLLE方法的聚類精度已經達到了一個很高的值，明顯高于CCDR，所以相對沒有CCDR提升比率那么高。總體實驗分析中可以看到，在每組實驗里SSCLLE方法的聚類精度基本都能保持最高，證明了本方法在UCI數據上的優勢。

圖2 標記樣本的比例對聚類精度的影響，d=2Fig. 2 Influence of proportion of labeled samples on clustering accuracy, d=2

3.2 實物數據集COIL _20

這里采用哥倫比亞大學(COIL-20) 數據集中第2種(背景被丟棄，圖像由包含物體的最小正方形組成)，數據集共有20種不同的物體，每種有72張圖片。每個圖片都是50×50的灰度圖像，在實驗中將每張圖片以行拉成一個2 500的向量。最后以向量集的形式進行處理與分析。

從數據集中按順序選取6組數據，每組3類不同的物體。分組分別是{1,2,3}，{4,5,6}，{7,8,9}，{10,11,12},{13,14,15}和{16,17,18}，然后再隨機選取3組不同的數據{9,7,10}，{7,3,5}，{4,10,1}，每組運行20次計算聚類精度。其中Group1～Group9分別對應以上9組數據，用不同方法做實驗得到聚類精度。參數設置為：k=8,d=8,r=0.5,a=1,b=10,u=1,v=0.5，標記比例為15%，實驗結果如表5所示。

由表5實驗結果可以看到，在這9組數據中由于SSLLE和本文方法SSCLLE都是在LLE方法上進行的一種改進，所以它們的聚類精度都高于LLE。且本方法利用了全局標記信息進行調整，聚類精度明顯高于SSLLE。SSLE與CCDR都是一種在LE基礎上做的改進，分析數據可以看出整體上它們略低于LLE的改進。且由于CCDR也是一種基于全局考慮標記信息的方法，基本上聚類精度都高于SSLE。由此體現出基于全局角度考慮標記信息的方法較局部效果要好，充分說明SSCLLE方法基于全局考慮的正確性。除在第6組數據中SSLLE方法的聚類精度最高外，其它組中都是本文中提出的SSCLLE方法精度最高。

表5 COIL_20數據集在不同方法下的平均聚類精度Table 5 Average clustering accuracy of COIL_20 dataset under different methods %

接下來隨機選出一組數據為{7，3，9}，來做在不同標簽比例下不同方法聚類精度的折線圖，參數設置為

圖3 不同標記比例COIL_20數據集聚類精度Fig. 3 The clustering accuracy of COIL_20 dataset under different labeling ratios

由圖3可看出在這組數據中隨著標記比例的增加無監督LLE方法精度保持不變，而SSLLE與SSLE方法的聚類精度隨著標記比例的增加只發生了波動，基本沒有體現出上升趨勢，說明這2種利用類信息只調節近鄰關系的方法對一些數據提取到的特征不能很好地提高可分性。而SSCLLE和CCDR方法都是考慮全局的調整，可看到聚類精度呈上升趨勢，且高于其他方法，除在5%的情況下略低于CCDR方法外，其余比例下均高于其他方法。體現出SSCLLE方法對近鄰及全局做調整的優勢。

3.3 數據可視化

數據可視化作為一種重要的數據分析方式，相對于單純的數據表格等，可更加直觀、形象地感知或理解高維數據集的結構分布。為驗證SSCLLE方法在可視化上的優勢，下面隨機選取MNIST數據集中的3個手寫數字做可視化實驗。分別用LLE方法、半監督：SSLLE、SSLE和CCDR方法，將選取的手寫數據集中3個數字提取至2維特征空間中，利用MATLAB畫圖工具進行畫圖，同類數據點的顏色和形狀一樣，分別觀察5種不同的方法提取數據點的低維特征分布情況。手寫數字選取的是{5,6,8}每類500個點分別將標記比例設為15%，參數設置為：k=8,d=2,

圖4 手寫數字可視化Fig. 4 Visualization of Handwritten digital

在圖4中手寫數字的5個可視化圖可以看到，無監督的LLE中有2類數據重合部分較大區分度小，因而不利于數據的聚類分析。而基于標記信息局部調整的SSLLE和SSLE的方法相對LLE的分離度明顯有所提升，不過依然存在重疊區域。而基于標記信息全局調整的CCDR和本文方法SSCLLE明顯3類區分開了，SSCLLE相比CCDR的區分度更高重疊區域最小，可明顯區分出3類數據的分布。通過實驗可視化的分析，半監督方法在數據可視化方面較無監督方法優勢明顯，而本文方法的可視化效果相對其他半監督方法效果最好，證明了本文方法的優勢。

4 參數影響分析

本方法中參數k、d、 α 、 β 和r對特征提取都有影響。k、d參數的選取很多學者都做過討論，這里不再贅述。本文主要討論參數 α 、β 和r對特征提取的影響。 α 和r取 [ 0,1] 的實數，α 用來權衡同類樣本項和異類樣本項對目標函數的影響；β 取大于0的值，用于調節局部線性結構對于目標函數的影響；r的作用是為了調整標記信息在局部所起到的影響。圖5展示了隨著 α,β 和r參數值變化，SSCLLE方法對于COIL_20中的{7,3,9}和UCI中WCBC數據集特征提取后聚類精度的結果。圖5中分別用a、b表示 α、 β。標記比例為15%，參數設置為：在COIL_20數據中設定 α=1,b=10 ,r=0.8；在WCBC數據集中α=0.99,b=10 ,r=0.7。同時固定其中2個參數調整另一個參數，記錄聚類精度的變化。

從圖5可以看出，同類數據樣本項比異類樣本項對聚類精度起到的作用更大。標記比例越高，異類標記的作用會逐漸增加。在一定的標記比例下，α 一般需要取一個較大的值。在COIL_20數據集中當 α 值為1時特征提取效果最好，而在WDBC中取值為0.99附近時效果最好。β 的取值在2個數據集中基本都為10時，得到的聚類精度最高、特征提取效果最好。作為局部調整參數的r，相對低于另2個參數，對特征提取的效果也有很大的影響。在COIL_20數據集中r的取值為0.8時效果最好，在WDBC數據集中取0.9時效果最好。

圖5 參數 α、β 和 r 對聚類精度的影響Fig. 5 The influence of parametersα、β and ron clustering accuracy

5t檢驗

從手寫數字中選取30組不同的數據，每組由3個不同的數字組成。對這30組數據分別用5種方法進行特征提取得到相應的聚類精度。

為了對比SSCLLE與其他方法的優劣，利用SPSS工具對SSCLLE方法得到的聚類精度與其他方法得到的聚類精度做成對t檢驗，得到以下結果如表6～8所示。

表6 配對樣本統計Table 6 Paired sample statistics

表7 配對樣本相關性Table 7 Correlation of paired samples

通過表8可以看到SSCLLE與其他4種方法的顯著性均小于0.05，說明各對比組聚類精度有顯著差異。再對比均值，可見本文SSCLLE方法相對其他方法能夠有效地提高特征提取的效果。

表8 配對樣本檢驗Table 8 Paired sample test

6 結束語

本文在LLE基礎上，提出了一種半監督類保持局部線性嵌入方法(SSCLLE)。方法中不單考慮了利用近鄰偽標簽賦予的標記信息對局部近鄰做調整，還對樣本的全局距離做進一步約束，使其達到既能保持數據的局部線性結構又能使類內數據更緊密，類間數據進行分離，得到很好的特征提取效果。在UCI數據集、實物數據集COIL_20和手寫數據集MNIST上對各方法進行實驗對比，得到SSCLLE方法在聚類精度以及可視化上的結果均高于無監督學習LLE方法和半監督學習SSLLE、SSLE、CCDR方法。