分類監(jiān)督半定嵌入算法

董文明， 孔德庸

（1.新疆農(nóng)業(yè)大學(xué)水利與土木工程學(xué)院，新疆烏魯木齊 830052；2.烏魯木齊新數(shù)元測繪有限公司遙感室，新疆烏魯木齊 830052）

0 引 言

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

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

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

SDE算法在本質(zhì)上是對核主成分分析算法的改進(jìn)，它與核主成分分析算法的不同點(diǎn)在于：前者通過一個(gè)非線性映射φ將原空間中的數(shù)據(jù)點(diǎn)映射到高維特征空間，然后在特征空間中應(yīng)用PCA方法，從而達(dá)到維數(shù)降低的目的；然而非線性映射φ通常是通過定義適當(dāng)?shù)膬?nèi)積核函數(shù)來實(shí)現(xiàn)的，所以根據(jù)所選擇的核函數(shù)不同，降維的結(jié)果也會(huì)大不相同；SDE算法則是通過考察原數(shù)據(jù)點(diǎn)與經(jīng)過非線性映射φ變換后的特征空間中的數(shù)據(jù)點(diǎn)之間的關(guān)系來構(gòu)造滿足特定條件（保持映射前后相鄰數(shù)據(jù)點(diǎn)之間的距離不變）的核函數(shù)，然后在特定的高維特征空間中應(yīng)用PCA方法達(dá)到降維的目的。

SDE算法的具體步驟如下：

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

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

Kii＋Kjj－Kij－Kji＝Gii＋Gjj－Gij－Gji當(dāng)且僅當(dāng)Γij＝1。

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

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

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

這個(gè)式子可等價(jià)為以下等式：

最后一個(gè)約束則是反映了原數(shù)據(jù)點(diǎn)與經(jīng)過非線性映射φ變換后的特征空間中的數(shù)據(jù)點(diǎn)之間的關(guān)系，即保持兩鄰近點(diǎn)之間的距離不變：

對于上述半定規(guī)劃問題的目標(biāo)函數(shù)，則是要在保持局部幾何結(jié)構(gòu)不變的前提下盡量使兩點(diǎn)之間的距離增大，即要在滿足約束的前提下使：

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

上述半定規(guī)劃問題可以用SeDuMi 1.0軟件包進(jìn)行求解，該軟件包的運(yùn)行環(huán)境是Matlab，具體操作可參見文獻(xiàn)［11］。

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

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

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

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

2 兩種新的SSDE算法

2.1 基于權(quán)重的SSDE算法

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

基于上述討論，我們對任意兩點(diǎn)間的歐氏距離定義如下的權(quán)重：

式中：Mij——數(shù)據(jù)集中任意兩點(diǎn)xi與xj之間的歐氏距離；

ωi，ωj——分別代表了點(diǎn)xi與xj的標(biāo)簽信息；

下面給出基于權(quán)重的SSDE算法的具體步驟：

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

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

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

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

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

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

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

求得點(diǎn)x到其k個(gè)鄰近點(diǎn)xl的最佳距離，其中：

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

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

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

3 數(shù)值實(shí)驗(yàn)

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

在下面的數(shù)值實(shí)驗(yàn)中所用到的數(shù)據(jù)集主要來源于UCI和USPS數(shù)據(jù)庫，詳細(xì)的數(shù)據(jù)屬性見表1。

表1 數(shù)據(jù)屬性

數(shù)值實(shí)驗(yàn)的具體步驟如下：

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

2）基于訓(xùn)練集和降維后的低維數(shù)據(jù)訓(xùn)練RBF神經(jīng)網(wǎng)絡(luò)，然后用訓(xùn)練出的神經(jīng)網(wǎng)絡(luò)模型對測試集進(jìn)行處理，得到與測試集相對應(yīng)的低維數(shù)據(jù)。

3）用最近鄰分類方法對降維后的與測試集相對應(yīng)的低維數(shù)據(jù)進(jìn)行分類，統(tǒng)計(jì)分類的錯(cuò)誤率。

以上實(shí)驗(yàn)對每個(gè)數(shù)據(jù)集都做了10次，實(shí)驗(yàn)結(jié)果取10次的平均值。實(shí)驗(yàn)結(jié)果見表2。

表2 平均分類錯(cuò)誤率 %

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

4 結(jié) 語

對SDE算法的監(jiān)督型算法進(jìn)行了研究，提出了兩種新的監(jiān)督型SSDE算法：基于權(quán)重的SSDE算法和基于最佳距離度量的SSDE算法，這兩種算法都是在SDE算法的基礎(chǔ)上根據(jù)樣本點(diǎn)的標(biāo)簽信息修改距離的度量方式來實(shí)現(xiàn)無監(jiān)督SDE算法到監(jiān)督型SSDE算法的轉(zhuǎn)變。

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

［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(xiàn) 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］ 邊肇祺，張學(xué)工.模式識(shí)別［M］.2版.北京：清華大學(xué)出版社，1999.