一種基于流形學習的PCA-SLPP特征空間降維方法

王培珍，王 慧，劉 曼，王 高，張代林

（安徽工業大學a.電氣與信息工程學院；b.煤的潔凈轉化與綜合利用安徽省重點實驗室；c.冶金減排與資源綜合利用教育部重點實驗室，安徽馬鞍山243002）

關健詞：降維；主成分分析；流形學習；有監督的局部保留投影；煤巖；分類

對于復雜問題的分類與識別，常常會因為特征量過多致使特征空間維數過高而遇到“維數災難”問題。因此，采用適當的方法對特征空間進行降維，即在保留數據信息的同時將高維特征空間嵌入到一個相對低維的空間中，成為提高分類器泛化能力和分類、識別正確率的重要手段之一。主成分分析法(principal component analysis，PCA)[1]和線性判別分析法(linear discriminant analysis，LDA)[2]是兩種常用的降維算法，兩者均通過一定的準則尋找變換矩陣，對特征量進行投影，并通過適當的截取實現降維。PCA的準則是使降維后數據具有最大方差，得到的是最佳描述特征，但非最佳分類特征。LDA方法其投影方向數受到限制，對數據樣本類別數不多、且難以用少量特征量描述的復雜對象分類不適用。

人類主要通過低維流形信息認知事物[3]。Nayar等[4]指出高維的圖像數據中具有低維流形現象，PCA和LDA提取的均為全局特征，難以反映高維數據的非線性流形結構。流形學習算法主要有等距映射算法(isometric mapping，ISOMAP）[5-6]、局部線性嵌入(locally linear embedding，LLE)[7]、拉普拉斯特征映射(Laplacian eigenmap，LE)[8]以及局部保留投影(locality preserving projection，LPP)[9]等。其中，LPP是一種非監督的局部特征提取算法，該算法通過最小化低維投影后樣本與其近鄰點之間距離的加權平方和，使原始空間中相鄰的樣本在降維后的低維空間中也保持相鄰，以保留原始數據的局部結構。該算法沒有考慮樣本類別信息，對于分屬于不同類別但在原特征空間靠得較近的數據點，投影后依然靠得較近甚至發生混淆，不利于特征區域的劃分。為此申中華等[10]提出有監督的局部保留投影算法(supervised locality preserving projects，SLPP)，對于同類別相鄰點與不同類別相鄰點設置不同的懲罰項，以兼顧局部保留性和類間離散性。此類方法均沒有考慮樣本的全局結構。

煤巖在漫長的形成過程中受各種不確定因素的影響，結構較為復雜，采用少量特征量難以對其進行完備描述[11]；其特征量之間存在一定的相關性，若將諸多特征量簡單聯合則特征空間維數過高，且數據間存在大量的冗余，給準確分類帶來困難[12]。鑒于PCA對數據的最佳描述能力和SLPP的局部保留特征，本文在PCA與SLPP的基礎上，同時考慮樣本數據的全局結構和局部保留特性以及樣本類別信息，提出一種基于PCA-SLPP流形學習的特征空間降維方法，并將該方法應用于煤巖惰質組顯微組分的分類，以驗證本文方法對于具有復雜結構圖像分類的有效性。

1 降維方法

1.1 主成分分析

主成分分析(PCA)法依照投影后特征值間方差最大的原則利用矩陣變換將一組相關變量映射為相互獨立的變量，并依照方差大小排序。設有樣本集X=[x1,x2,…,xn]，xi∈Rd,i=1,2,…,n；d為原始特征空間的維數。

先求樣本集均值

再將每個樣本中心化,

得到新樣本集Z=[z1,z2,…,zn]，zi∈Rd。求樣本集Z的協方差矩陣ZZT的特征值λi和對應的特征向量ai，且有

從大到小依此取前r個特征值對應的特征向量構成投影矩陣UPCA=[a1,a2,…,am]xi∈Rd×r，投影后的樣本集。可根據積累貢獻率[12]從大到小截取適合數量的特征量（保持原始數據的絕大部分的信息），則原始樣本集X被映射到一個低維空間中，實現降維。

1.2 有監督的局部保留投影及其改進

局部保留投影(LPP)算法在保留類內局部結構的同時最大化類別之間的分離度。設有樣本集X=[x1,x2,…,xm]，xi∈Rr，i=1,2,…,n；r為特征空間的維數。尋找投影矩陣 A=[a1,a2,…,am]∈ Rr×m，將樣本映射到一個低維空間中，投影后的樣本集為Y=[y1,y2,…,yn]，且Y=ATX，則LPP的目標函數[10]為

其中S為相似度矩陣。LPP中，對于鄰近的樣本點xi和xj，無論其是否屬于同一類別，均按相同的規則進行投影，亦即其在投影后的特征空間中依然鄰近，因而投影后空間樣本的可區分性未能得到加強。為此，在SLPP中，將類內與類間樣本區別對待，分別定義樣本類內相似度矩陣W和樣本類間相似度矩陣B[10]，對于類內結構的保留，采用最小化來實現；對于類間結構，則通過最大化實現。于是，SLPP的優化問題可表示為

其中，LB=diagB-B，LW=diagW-W，是拉普拉斯矩陣，diagB與diagW的元素分別為樣本的類內和類間相似度矩陣B和W的對應行或列上的元素之和(B和W均為實對稱矩陣)。最大化目標函數式(6)可轉化為求下面廣義特征值問題

取解出的前d個最大特征值對應的特征向量構成投影矩陣USLPP。

文獻[10]中，需先構建連接圖，在此基礎上計算相似度矩陣。本文通過核函數，重新定義W和B為

其中：exp(-||xi-xj||2/t)為熱核(heat kernel)函數，參數t為大于零的實數；||x||2為向量的L2范數。

改進后的SLPP，省去了連接圖的構建，使算法可自適應地確定鄰域范圍，且更為高效簡潔。

1.3 基于PCA-SLPP的降維方法

綜合考慮PCA對數據的全局描述能力、SLPP對數據類內局部流形的保留特性及類間數據的可分離性，采用PCA計算降維映射矩陣UPCA，在此基礎上，計算SLPP的投影矩陣USLPP，并生成最終的映射矩陣UPCA-SLPP，通過空間映射，實現最終的降維。具體步驟如下。

1)對樣本進行PCA映射，按照式(3)求投影矩陣UPCA，將d維原始樣本數據X通過投影矩陣投影到一個低維的r(1≤r≤d)維空間中。

2)使用熱核函數建立類內相似度矩陣W和類間相似度矩陣B，計算對應的拉普拉斯矩陣LB，LW，求解式(7)的廣義特征值問題；取特征向量a的前m個最大特征值對應的特征向量構成投影矩陣USLPP，將r維的數據進一步降維到一個更低維的m(1≤m≤r)維空間中。

3)計算最終投影矩陣UPCA-SLPP=UPCAUSLPP，依此計算投影結果Y=UPCA-SLPPTX，實現最終的特征空間及數據降維。

2 分類方案

2.1 煤巖惰質組顯微圖像特點

根據煤巖顯微組分的形態特征和細胞結構等特點，惰質組分為絲質體、半絲質體、真菌體、氧化樹脂體、粗粒體、微粒體、碎屑體等7個顯微組分，其中絲質體又分篩狀絲質體和星狀絲質體2個亞組分[13]。其在油鏡反光下典型顯微圖像如圖1[14]。

圖1 惰質組顯微組分典型圖像Fig.1 Typical microscopic images of inertinite

由圖1可看出，不同顯微組分在亮度（灰度）、形狀、區域大小等方面各有特點，且表現出明顯的紋理特征。但由于其結構復雜，不同組分間特征又有交錯，少量特征難以描述。

2.2 特征量選擇與提取

鑒于以上分析，同時為便于與文獻[12]比較，分別從亮度和紋理的角度構建初始特征量集，對煤巖惰質組顯微組分進行描述。

2.2.1 灰度統計特征量

依據鏡質組不同組分在油鏡反光下呈現的的亮度差異，從灰度統計的角度構建6個特征量。

1)亮度比

其中：c為亮度比，反映亮灰度值像素點在整個區域所占的比重；h(i)為灰度值為i的像素數；L為灰度級；e為設定的閾值。

2)均值

其中：μ為均值，反映圖像的亮暗程度；p(i)為灰度值為i的概率。

3)方差

其中σ為方差，反映灰度對比度的大小。

4)三階矩偏度

其中α為三階矩偏度，反映灰度分布的不對稱程度或者偏斜程度，當α＞0時為正偏斜；當α＜0時為負偏斜。

5)一致性

其中U(i)為一致性，反映紋理的粗糙度，一致性值越小，表明紋理越粗糙。

6)峰度

其中β為峰度，反映灰度分布的集中程度。

2.2.2 基于灰度共生矩陣紋理特征

灰度共生矩陣中的每個元素P(i,j|l,θ)描述的是原始圖像中方向θ上間隔為l的一對像素值分別i和 j的像元出現的頻數，θ通常取0°，45°，90°和135°。在此基礎上定義5個反映紋理特征的參數。

1)能量

反映圖像灰度分布的均勻性和紋理的粗細程度，其中L為灰度級。

2)熵

用于描述紋理的非均勻程度，越復雜紋理對應的熵值越大。

3)慣性矩

紋理越細，慣性矩越大。

4)局部平穩性

度量紋理局部變化平穩性，其值越大，局部越均勻。

5)最大概率

反映紋理出現次數最多的單元比例，其值越大，紋理一致性越強。

初始特征量集由上述11個特征量構成。如果直接采用上述11個特征量對初始特征量集進行分類，則對于顯微組分中的每個樣本，將在由上述11個特征量構建的11維特征空間中進行描述。其特征空間維數過高，且特征量間存在一定的相關性，特征數據存在大量冗余。為此，本文采用1.3描述的基于PCA-SLPP方法對特征空間進行降維，其中PCA主要用于去除特征量間的相關性，改進的SLPP用于在保持特征空間數據局部流形的前提下，對特征空間進一步降維，在降低分類器復雜性的同時，提高分類的正確率。

2.3 分類器構建

焦巖惰質組的分類屬于小樣本非線性分類問題，分類器采用支持向量機，其最終的決策函數可以表示為

其中：ai為拉格朗日乘子；b為閾值；xi是輸入模式；δi為對應于xi的輸出；K(xi,x)為核函數，用于解決分類的非線性問題。

研究表明[12]，當缺少過程的先驗知識時，徑向基核函數(RBF)在參數優化的條件下具有更好的性能。故本文選擇RBF的核函數，形式為

其中σ2為函數的寬度參數，控制函數的徑向作用范圍，其值通過cross validation優化選取。

3 實驗與結果分析

為驗證方法的有效性，以煤巖惰質組顯微組分為對象，分別采用單一的PCA，SLPP及本文方法對其特征空間進行降維，探討不同降維方法及參數選取對分類效果的影響。實驗平臺硬件配置為Windows 764 bit，CPU i7-4700MQ，2.5 GHz，內存6 GB，算法在Microsoft Visual Studio 2013環境下編程實現。

3.1 實驗數據及參數設置

實驗所用的樣本數據為煤巖惰質組顯微組分圖像，采用光度計在油浸反光下，依照GN/T 8899—1998標準采集。訓練數據樣本和測試數據樣本均含8類，分別為篩狀絲質體、星狀絲質體、半絲質體、真菌體、氧化樹脂體、粗粒體、微粒體、碎屑體，每類15個，共120個樣本圖像，大小為120×240。為避免數據量綱不同而導致降維和分類器訓練過程中產生的中心偏移，對實驗數據進行歸一化處理[14]。

3.2 結果與討論

3.2.1 熱核參數t對分類結果的影響

為考察熱核函數 exp(-‖xi-xj‖2/t)中參數t對分類結果的影響，取t=1～6采用本文方法分別進行實驗，結果見圖2，橫坐標為最終維數。從圖2可以看出，參數t對本文方法的分類結果稍有影響，且在降到較低維數時，影響較為明顯，t=2時分類正確率較為穩定，且略高于其他取值。本文后續的比較實驗中，熱核函數參數t取2。

圖2 參數t不同取值時分類正確率Fig.2 Classification accuracy with different parameters t

3.2.2 不同降維環節維數截取對算法性能的影響

為考察不同降維環節截取的降維維數對算法性能的影響，分別選取不同PCA降維維數r、SLPP降維維數m進行實驗。表1是本文PCA-SLPP降維方法在參數r和m取不同值時的分類正確率，其中r和m的范圍均為1～11，且m≤r。圖3是當r分別取7、8、9、10，m取不同值時的分類結果。由圖3可看出，當r一定時，分類正確率隨著m的增大呈上升趨勢，直至平穩，且m從1增大到2時分類正確率提升較大，表明局部結構的保留對分類效果有較大影響。圖4是m分別取2、3、4、5時，分類正確率隨r的變化情況。由圖4可看出：m＝2時（m過低），分類正確率不穩定；m＝3～5時，分類正確率隨著r的減小出現先略微增大后減小的趨勢，如當m＝5，r從11減小到9時，分類正確率從90.83%上升到97.50%；繼續減小r至5，則分類正確率下降到94.17%，表明PCA在逐漸減少主成分個數的過程中，數據間相關冗余逐漸減少，對于分類不利的影響逐漸消除；但減少到一定程度后再次減小，則會使用于分類的有效信息逐步丟失。

圖3 維數r一定時分類正確率隨m的變化Fig.3 Change of classification accuracy with m while r is fixed

表1 維數r、m不同取值時PCA-SLPP的分類正確率，%Tab.1 Classification accuracy of PCA-SLPPwith different values of r and m,%

3.2.3 不同降維方法分類結果比較

PCA-SLPP與PCA、SLPP在不同降維維數下的分類正確率結果見表2。對比結果可以看出：在較高維（維數≥7）空間中3種方法的分類正確率比較接近，維數為11時（與初始特征空間維數一致），PCA投影后分類結果最好，因為此時盡管特征空間維數保持一致，但將特征量投影到彼此正交的空間，減少了對分類產生不利影響的相關性因素；在特征空間維數降到較低（原樣本空間維數的1/2及以下）時，本文方法（PCA-SLPP）分類正確率較PCA和SLPP均明顯提高，高出近10%。

表3為數據樣本降維至2維時各方法在不同處理過程中的耗時，包括求解投影矩陣時間、投影時間和分類時間。由表3可以看出，對于求解投影矩陣的時間，PCA耗時最短，約為其他方法耗時的1/10，因為其算法只需對樣本數據的協方差矩陣進行特征值分解，而其他方法求解過程相對較復雜。3種方法對于投影時間基本相同，投影過程均為樣本數據矩陣和一個具有相同大小的矩陣作乘法運算；分類時間也基本相同，其差別主要與分類器的結構有關。

圖4 維數m一定時分類正確率隨r的變化Fig.4 Change of classification accuracy with r while m is fixed

表2 不同方法的分類正確率，%Tab.2 Classification accuracy with different methods,%

表3 各方法在不同處理階段的耗時，μsTab.3 Time consuming of each method in different processes,μs

4 結 論

結合主成分分析和局部保留投影算法的優點，同時考慮樣本數據的全局結構和局部保留特性及樣本類別信息，提出基于PCA-SLPP的流形學習的降維方法，且將其應用于煤巖惰質組顯微組分分類，得以下結論：

1)PCA可有效去除特征數據間的信息冗余，有助于提高分類正確率；

2)當PCA的維數一定時，隨著SLPP維數的降低，分類正確率相對平穩，但當總維數降到2及以下時，分類正確率迅速下降；

3)對于具有復雜結構圖像的分類問題，在樣本空間維數降到原樣本空間維數的1/2及以下時，本文提出方法的分類正確率明顯高于其他同類算法；

4)本文算法在耗時上與SLPP相近。