分類監督半定嵌入算法

董文明， 孔德庸

（1.新疆農業大學水利與土木工程學院，新疆烏魯木齊 830052；2.烏魯木齊新數元測繪有限公司遙感室，新疆烏魯木齊 830052）

0 引 言

維數約簡方法一直都是模式識別、機器學習、多元統計分析等領域的重要研究課題之一，而傳統的維數約簡方法如：主成分分析（PCA）［1］、多維尺度變換（MDS）［2］及判別分析（MDA）［3］等大多都是線性降維方法，即假設所研究的數據集在統計意義下具有全局線性結構，并且構成數據集的各變量之間是獨立無關的。因此，可以用歐氏空間這種全局線性空間來作為數據集存在的幾何空間，在這樣的空間中歐氏距離可以被用于數據分析，從而使得線性降維方法在歐氏空間中是有效的。但在許多實際問題中所要研究的數據集往往呈現出高度的非線性，這時再采用常規的線性維數約簡方法就不能很好地描述數據的內在結構。目前已涌現出了許多優異的流形學習研究算法，如核主成分分析（kernel PCA）［4－5］、局部線性嵌入算法（Locally Linear Embedding，LLE）［6］、等度規特征映射算法（ISOMAP）［7］、拉普拉斯特征映射（Laplacian Embedding）［8］等；這些算法已經在數據的可視化與可聽化、人臉識別、文本分類以及圖像處理等方面得到了較好的效果。

文中將對2004年Weinberger［9］提出的一種新的流形學習算法——半定嵌入算法進行研究，從新的角度去研究SDE算法的監督形式，給出兩種新的監督型SDE算法。

1 半定嵌入算法（SDE）簡介

SDE算法在本質上是對核主成分分析算法的改進，它與核主成分分析算法的不同點在于：前者通過一個非線性映射φ將原空間中的數據點映射到高維特征空間，然后在特征空間中應用PCA方法，從而達到維數降低的目的；然而非線性映射φ通常是通過定義適當的內積核函數來實現的，所以根據所選擇的核函數不同，降維的結果也會大不相同；SDE算法則是通過考察原數據點與經過非線性映射φ變換后的特征空間中的數據點之間的關系來構造滿足特定條件（保持映射前后相鄰數據點之間的距離不變）的核函數，然后在特定的高維特征空間中應用PCA方法達到降維的目的。

SDE算法的具體步驟如下：

第一步：對于給定的數據集X＝｛xi，i＝1，2，…，n｝，其中xi∈Rd，n為樣本點的個數，計算任意兩點間的歐氏距離，根據計算出的歐氏距離，選出數據集中任意一點xi的K個鄰近點，K＜＜n；然后根據所選出的鄰近點構造二進制矩陣Γn×n，如果xj是xi的近鄰點，則Γij＝1，否則，Γij＝0。

第二步：通過求解如下的半定規劃問題，構造核矩陣K（Kij＝（φ（xi）·φ（xj））），令Gij＝（xi·xj）：

Kii＋Kjj－Kij－Kji＝Gii＋Gjj－Gij－Gji當且僅當Γij＝1。

第三步：求解特征方程Nλα＝Kα；由于求得的各個特征值都是非負的，于是樣本X的第i主成分為：

從上述算法的具體步驟中可以看出，該算法的核心部分就是求解上述半定規劃問題［10］，從而構造滿足條件的核矩陣。下面簡要地分析一下上述半定規劃問題的目標函數和約束條件所對應的具體含義。

由于我們要構造的是核矩陣，所以首先要加入約束K≥0，即要使所求的核矩陣為半正定的；而上述半定規劃問題的第二個約束則是要將映射后特征空間中的數據點中心化，也就是說要使：

這個式子可等價為以下等式：

最后一個約束則是反映了原數據點與經過非線性映射φ變換后的特征空間中的數據點之間的關系，即保持兩鄰近點之間的距離不變：

對于上述半定規劃問題的目標函數，則是要在保持局部幾何結構不變的前提下盡量使兩點之間的距離增大，即要在滿足約束的前提下使：

達到最大，由Kij和Gij的定義可將H化簡如下：

上述半定規劃問題可以用SeDuMi 1.0軟件包進行求解，該軟件包的運行環境是Matlab，具體操作可參見文獻［11］。

SDE算法由于在降維過程中不考慮樣本點的標簽信息，從本質上講是一種非監督的流形學習算法，所以并不適合分類問題的降維，在文獻［12］中基于無監督的SDE算法提出了一種有監督的算法，稱為SSDE，當該算法用于分類問題的降維時，為了提高降維后分類的正確率，使得在低維空間中，同類樣本點盡可能地聚在一起。因此，在求解xi的K個最鄰近點的時候，要求選出的K個最鄰近點與xi具有相同的標簽信息，即在選擇xi的K個最鄰近點的時候，是在與xi類別相同的樣本點中進行選取的，這樣就保證了xi與其K個最鄰近點隸屬于同一類別。SSDE算法的具體實現步驟如下：

第一步：給定數據集X＝｛xi∈Rd，i＝1，2，…，n｝，以及與數據集X相對應的標簽信息ω＝（ω1，ω2，…，ωn），對于數據集中的任意一點xi，首先根據xi的標簽信息選出與xi具有相同標簽信息的樣本點組成集合Δi，然后在Δi中根據歐氏距離的大小選擇K個最鄰近點，K＜＜n；然后根據所選出的鄰近點構造二進制矩陣Γn×n，如果xj是xi的近鄰點，則Γij＝1，否則，Γij＝0。

SSDE算法接下來的步驟與SDE算法的后兩步相同。

從上述SSDE算法的具體實現步驟來看，該算法與原始的SDE算法唯一的不同點就在于鄰近點的選擇上，SSDE算法充分利用了所給樣本點的標簽信息，使得數據集X中的同類樣本點在降維后盡可能地聚在了一起。

2 兩種新的SSDE算法

2.1 基于權重的SSDE算法

由于監督型的流形學習算法目的就是要充分利用樣本點的標簽信息，使得降維后在低維空間中的同類樣本點盡量地聚在一起，結合SDE算法本身的特性（保持樣本點的局部結構不變，即保持降維前后鄰近樣本點之間的距離不變），只要在原空間中利用樣本標簽的信息，使得同類樣本點之間的歐氏距離變小，不同類樣本點之間的歐氏距離變大，即通過改變原空間中樣本點的分布（同類點相互靠近），來達到使降維后低維空間中的同類樣本點盡量聚在一起的目的。

基于上述討論，我們對任意兩點間的歐氏距離定義如下的權重：

式中：Mij——數據集中任意兩點xi與xj之間的歐氏距離；

ωi，ωj——分別代表了點xi與xj的標簽信息；

下面給出基于權重的SSDE算法的具體步驟：

第一步：給定數據集X＝｛xi∈Rd，i＝1，2，…，n｝，以及與數據集X相對應的標簽信息ω＝（ω1，ω2，…，ωn），首先計算任意兩點間的歐氏距離，得到歐氏距離矩陣M，再根據樣本點的標簽信息對兩點間的歐氏距離做如下的改進：

并且用改變后的距離M′ij來代替原來兩點間的歐氏距離，根據改變后任意兩點間距離的大小，選出數據集中任意一點xi的K個鄰近點，K＜＜n；然后根據所選出的鄰近點構造二進制矩陣Γn×n，如果xj是xi的近鄰點，則Γij＝1，否則，Γij＝0。

基于權重的SSDE算法接下來的步驟與SDE算法的后兩步相同。

2.2 基于最佳距離度量的SSDE算法

上述基于權重的SSDE算法雖然可以達到使降維后低維空間中的同類樣本點盡量聚在一起的目的，但是這種算法僅僅是利用已知樣本點的標簽信息機械地增大或縮小兩樣本點之間的歐氏距離。下面引入一種基于另一種距離度量方式的SSDE算法，即基于最佳距離度量的SSDE算法；首先，簡單地介紹一下什么是最佳距離度量［13］。

最佳距離度量是模式識別中最佳距離度量近鄰法所采用的一種距離度量形式，采用這種距離度量可使得用最近鄰法分類時具有較小的錯誤率（相對于其它的距離度量形式而言）。基于這一特點，可以直觀地認為在這樣的距離度量下，同一類別的樣本點能在一定程度上相互靠近；接下來我們將給出最佳距離度量的具體數學表達式。

設數據集X＝｛xi∈Rd，i＝1，2，…，n｝中的樣本點分別屬于C個不同的類別，我們把X中每一類所含有的樣本點個數記為ni，i＝1，2，…，C；對于數據集X中的任意一點x，先根據其到其它各點歐氏距離的大小找出與x距離最近的k個鄰近點xl，l＝l1，l2，…，lk；在選出的k個鄰近點中，每一類所包含的樣本點個數記為Wi，i＝1，2，…，C，然后根據以下表達式：

求得點x到其k個鄰近點xl的最佳距離，其中：

基于最佳距離度量的SSDE算法與SSDE算法的不同點在于，選擇近鄰點時所用的距離度量形式不再是傳統的歐氏距離，而是上述定義的最佳距離度量，下面總結一下這一算法的具體步驟：

第一步：給定數據集X＝｛xi∈Rd，i＝1，2，…，n｝，以及與數據集X相對應的標簽信息ω＝（ω1，ω2，…，ωn），首先計算任意兩點間的歐氏距離，然后根據歐氏距離的大小確定數據集中任意一點x的鄰近區域，在鄰近區域范圍內根據上面定義的最佳距離度量計算點x到區域內任意一點的最佳距離，再根據所算出的最佳距離的大小選擇點x的k個近鄰點，然后根據所選出的鄰近點構造二進制矩陣Γn×n，如果xj是xi的近鄰點，則Γij＝1；否則，Γij＝0。

基于最佳距離度量的SDE算法接下來的步驟與SDE算法的后兩步相同。

3 數值實驗

上面提出了兩種監督型的SDE算法，由于這些算法主要是在分類問題的數據降維階段進行應用，所以接下來將會把這些算法應用到不同的數據集中，并與其它的監督或非監督流形學習算法進行比較，來說明它們在分類問題降維階段的有效性。

在下面的數值實驗中所用到的數據集主要來源于UCI和USPS數據庫，詳細的數據屬性見表1。

表1 數據屬性

數值實驗的具體步驟如下：

1）將原始數據的80%作為訓練集，20%作為測試集，然后用PCA，SDE，MDS，SSDE，基于權重的SSDE及基于最佳距離度量的SSDE對訓練集進行降維處理，所要降到的低維空間維數d用特征值分析法確定。

2）基于訓練集和降維后的低維數據訓練RBF神經網絡，然后用訓練出的神經網絡模型對測試集進行處理，得到與測試集相對應的低維數據。

3）用最近鄰分類方法對降維后的與測試集相對應的低維數據進行分類，統計分類的錯誤率。

以上實驗對每個數據集都做了10次，實驗結果取10次的平均值。實驗結果見表2。

表2 平均分類錯誤率 %

從上述實驗結果可以看出，監督型的SSDE算法對于高維數據集降維效果均要好于線性降維算法（PCA，MDS）以及無監督的SDE算法；但是對于維數較低的數據集來說，監督型的SSDE算法的降維效果就不是很好。

4 結 語

對SDE算法的監督型算法進行了研究，提出了兩種新的監督型SSDE算法：基于權重的SSDE算法和基于最佳距離度量的SSDE算法，這兩種算法都是在SDE算法的基礎上根據樣本點的標簽信息修改距離的度量方式來實現無監督SDE算法到監督型SSDE算法的轉變。

總體來說，監督型的SSDE算法主要是在分類問題的降維階段進行應用，并且在高維數據的分類問題中取得了較好的效果；但是目前，關于監督型的SSDE算法在其它方面的應用研究還比較少，這將成為今后研究的一個主要方向。

［1］ I T Jollie.Principal component analysis［M］.New York：Springer-Verlag，1986.

［2］ T F Cox，M A Cox.Multidimensional scaling［M］. 2nd edition.［S.l.］：Chapman Hill，2001.

［3］ R O Duda，P E Hart，D Stork.Pattern classification［M］.2nd edition.［S.l.］：John Wiley ＆Sons，2001.

［4］ J Ham，D D Lee，D Mika，et al.A kernel view of the dimensionality reduction of manifolds［C］／／Proceedings of the Twenty First International Conference on Machine Learning（ICML-04）.Banff，Canada.2004.

［5］ C K I Williams.On a connection between kernel PCA and metric multidimensional scaling［J］.Machine Learning，2002，46：11-19.

［6］ S T Roweis，L K Saul.Nonliear dimensionality re-duction by locally linear embedding［J］.Science，2000，290：2323-2326.

［7］ J B Tenenbaum，V de Silva，J C Langford.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290（5500）：2319-2323.

［8］ M Belkin，P Niyogi.Laplacian eigenmaps and spectral techniques for embedding and clustering［C］／／Advances in Neural Information Processing Systems.2002.

［9］ K Q Weinberger，F Sha，L K Saul.Learning a kernel matrix for nonlinear dimensionality reduction［C］／／Proceedings of the Twenty First International Conference on Machine Learning（ICML-04），Canada，2004：839-846.

［10］ L Vandenberghe，S P Boyd.Semidefinite programming［J］.SIAM Review，1996，38（1）：49-95.

［11］ J F Sturm.Using SeDuMi 1.02，a MATLAB toolbox for optimization over symmetric cones［C］／／Optimization Methods and Software，1999.

［12］ B Y Zhang，J Yan，N.Liu，et al.Supervised semidefinite embedding for image manifold［C］／／http：www.ieee.org／ieeexplore，2005.

［13］ 邊肇祺，張學工.模式識別［M］.2版.北京：清華大學出版社，1999.