李德玉，高翠珍，翟巖慧

（1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006）

＊基于流形彎曲度的有序自適應(yīng)鄰域選擇算法

李德玉1，2，高翠珍1，翟巖慧1

（1.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006；

2.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006）

針對(duì)傳統(tǒng)鄰域選擇方法不能根據(jù)流形樣本密度和彎曲度合理選擇鄰域的缺點(diǎn)，提出了一種有序自適應(yīng)的鄰域選擇算法.該算法從流形上曲率最小的點(diǎn)開(kāi)始，以寬度優(yōu)先的次序不斷地處理每個(gè)點(diǎn).對(duì)搜索到的數(shù)據(jù)點(diǎn)，基于流形結(jié)構(gòu)的局部線(xiàn)性特性，利用已有的鄰域信息估算其局部切空間，然后通過(guò)其鄰域邊在切空間的投影自適應(yīng)地選擇合適的鄰域.實(shí)驗(yàn)結(jié)果表明：該算法應(yīng)用于Isomap后，對(duì)不同結(jié)構(gòu)的數(shù)據(jù)集嵌入結(jié)果更準(zhǔn)確.

流形學(xué)習(xí)；鄰域選擇；切空間

0 引言

隨著信息技術(shù)的快速發(fā)展，真實(shí)世界中數(shù)據(jù)的規(guī)模也在以幾何級(jí)的速度增長(zhǎng)，出現(xiàn)了大量的高維數(shù)據(jù)，這些數(shù)據(jù)具有高維稀疏性，某些特性也發(fā)生了很大變化，同時(shí)數(shù)據(jù)的計(jì)算量也迅速上升，使得傳統(tǒng)的線(xiàn)性數(shù)據(jù)降維方法不能滿(mǎn)足需求，因此需要找到新的降低數(shù)據(jù)維數(shù)的方法.流形學(xué)習(xí)就是一種新的非線(xiàn)性降維技術(shù)，即從數(shù)據(jù)集中尋找內(nèi)在規(guī)律性，通過(guò)分析提取于研究對(duì)象的數(shù)據(jù)集的外在幾何現(xiàn)象來(lái)認(rèn)識(shí)其本質(zhì)，已經(jīng)成為機(jī)器學(xué)習(xí)、模式識(shí)別、數(shù)據(jù)挖掘等領(lǐng)域的研究熱點(diǎn)之一.

近年來(lái)，流形學(xué)習(xí)領(lǐng)域產(chǎn)生了大量的研究成果，如等度規(guī)映射ISOMAP［1］、局部線(xiàn)性嵌入LLE［2］、局部切空間排列LTSA［3］等算法是具有代表性的流形學(xué)習(xí)算法，這些算法有一個(gè)統(tǒng)一的框架，主要由三步組成：

（1）計(jì)算原始空間中每個(gè)點(diǎn)的鄰域，根據(jù)鄰域信息來(lái)重構(gòu)流形的結(jié)構(gòu)，形成一個(gè)鄰域圖；

（2）基于上一步構(gòu)建的鄰域圖創(chuàng)建一個(gè)矩陣；

（3）通過(guò)矩陣的特征分解計(jì)算低維嵌入.

流形學(xué)習(xí)算法成功的關(guān)鍵是第一步，選擇合適的鄰域.目前常用的鄰域選擇方法是K－NN和ε－NN，這兩種方法中的參數(shù)K和ε都是人為給定的，然而不同結(jié)構(gòu)的流形對(duì)參數(shù)的選擇是敏感的，參數(shù)太大和太小均不能得到合理的鄰域，影響流形結(jié)構(gòu)的正確恢復(fù)，甚至使得一些流形學(xué)習(xí)算法無(wú)法運(yùn)行.此外，以上兩種方法只適應(yīng)于數(shù)據(jù)點(diǎn)分布均勻的流形，不能根據(jù)流形的不同結(jié)構(gòu)、密度和彎曲度選擇合適的鄰域參數(shù).鑒于此，Kouropteva等人在2002年提出了LLE的最優(yōu)鄰域參數(shù)選擇算法［4］，Samko等人借鑒Kouropteva的思想也為Isomap提出了最優(yōu)鄰域參數(shù)選擇算法［5］，該類(lèi)算法在給定一定鄰域參數(shù)范圍之內(nèi)迭代運(yùn)行LLE和Isomap算法，將得到的低維嵌入用殘差值來(lái)度量，將殘差值最小時(shí)對(duì)應(yīng)的鄰域參數(shù)作為最優(yōu)鄰域值，然而這樣得到的參數(shù)仍然是固定值，顯然不能滿(mǎn)足分布不均勻且曲率不斷變化的流形，同時(shí)算法效率低；Karina、Nathan，M.等人依據(jù)流形的局部線(xiàn)性特性提出了基于估計(jì)切空間并動(dòng)態(tài)自適應(yīng)選擇鄰域的算法［6］；Li Yang使用所有數(shù)據(jù)點(diǎn)完全圖的K邊連通子圖和K連通最小生成子圖為流形構(gòu)建連通的鄰域圖［7－8］，得到鄰域參數(shù)，該算法保證了鄰域圖的連通性，但參數(shù)仍然是固定值.Wen等人分別用局部測(cè)地距離和局部空間轉(zhuǎn)化來(lái)優(yōu)化鄰域［9－10］；Gao Xiaofang等人提出了一種基于采樣密度的動(dòng)態(tài)鄰域選擇算法［11］等.通過(guò)以上分析不難發(fā)現(xiàn)，已有算法雖然能為流形學(xué)習(xí)的鄰域選擇提供一定的方便，但仍存在一些問(wèn)題，因此，本文針對(duì)鄰域選擇問(wèn)題提出了一種基于流形彎曲度的有序自適應(yīng)鄰域選擇算法，該算法基于鄰域的局部線(xiàn)性特性，利用鄰域邊在切空間的投影對(duì)不同結(jié)構(gòu)的流形自適應(yīng)地選擇合適的鄰域，該方法應(yīng)用于Isomap算法后得到了更準(zhǔn)確的低維嵌入.

1 自適應(yīng)鄰域選擇

圖1 寬度優(yōu)先順序依次處理各個(gè)點(diǎn)Fig.1 Processing all points with breadth－first order

圖2 去掉不合理邊的方法圖Fig.2 Method of removing the unreasonable edge

通過(guò)圖1和圖2來(lái)說(shuō)明本文提出算法的主要思想.圖1用曲線(xiàn)的例子說(shuō)明自適應(yīng)鄰域構(gòu)建的過(guò)程：選擇流形彎曲度最小且沒(méi)有重疊的點(diǎn)S作為起始點(diǎn)，用寬度優(yōu)先的方法依次搜索點(diǎn)，并計(jì)算其鄰域.

觀(guān)察圖2，可以看出圖中點(diǎn)是取自一條曲線(xiàn)構(gòu)成的流形，該流形的內(nèi)在維數(shù)是一維，應(yīng)對(duì)其進(jìn)行一維重建，圖中pc邊和pd邊形成的二維重建均會(huì)破壞原流形的結(jié)構(gòu)，pc邊使流形發(fā)生“短路”現(xiàn)象，稱(chēng)為“短路邊”，pd邊被點(diǎn)a孤立，偏離了原流形的結(jié)構(gòu)，稱(chēng)為“孤立邊”，因此正確的恢復(fù)流形的結(jié)構(gòu)需去掉這些不合理的邊，我們將去掉“孤立邊”和“短路邊”的鄰域稱(chēng)為“合理鄰域”.此外，從圖2明顯可以看出不管是“短路邊”還是“孤立邊”，一個(gè)共同的特點(diǎn)就是鄰域邊和鄰域切空間的夾角較大，因此可以通過(guò)與切空間的夾角來(lái)去除“孤立邊”和“短路邊”得到合理的鄰域.

目前計(jì)算切空間的方法大多是用點(diǎn)的最近鄰來(lái)逼近，近鄰點(diǎn)選取的合理與否就決定了切空間逼近的準(zhǔn)確性，當(dāng)流形的曲率較大，或者是重疊度很高時(shí)，很容易將短路點(diǎn)和孤立點(diǎn)作為近鄰，這樣會(huì)導(dǎo)致切空間出現(xiàn)嚴(yán)重的錯(cuò)誤，鄰域選取不合理.鑒于這種情況，本算法使用了自適應(yīng)方法來(lái)決定點(diǎn)的鄰域，首先選取彎曲度小并且沒(méi)有重疊的點(diǎn)作為起始點(diǎn)，用已經(jīng)構(gòu)建好的合理鄰域作為新點(diǎn)的鄰域，然后通過(guò)保證流形的局部線(xiàn)性特性來(lái)逼近切空間，按寬度優(yōu)先的次序逐步擴(kuò)展，最終確定每一個(gè)點(diǎn)的合理鄰域.

如圖1中當(dāng)搜索到點(diǎn)a時(shí)，點(diǎn)c的合理鄰域RN（c）＝｛a，d｝已經(jīng)確定，此時(shí)a，c互為鄰域，SN（a）＝｛c｝，用來(lái)逼近點(diǎn)a切空間的點(diǎn)集明顯為｛c｝∪｛b｝，因?yàn)檫卆c和邊ab構(gòu)成的子空間的線(xiàn)性度高于邊ac和邊ag或af構(gòu)成的子空間的線(xiàn)性度，并且邊ab的長(zhǎng)度小于邊ag或af的長(zhǎng)度，因此用點(diǎn)b能更準(zhǔn)確地逼近a點(diǎn)的切空間.確定切空間的點(diǎn)集后，用圖2中的方法更新鄰域.如圖2中當(dāng)前點(diǎn)為p，用K－N N法選擇的鄰域KNN＝｛a，b，c，d，e，f，g｝，通過(guò)KNN中的各點(diǎn)在局部切空間的投影判斷其夾角去“短路邊”和“孤立邊”，得到合理鄰域RN＝｛a，b｝.

具體算法如下：

Step 1 確定KNN.

用K最近鄰法確定每個(gè)樣本點(diǎn)x i的K鄰域，并按邊的長(zhǎng)度排序，表示為KNN（x i），K足夠大.然后將x i與其K NN（x i）中的每個(gè)點(diǎn)相連，構(gòu)成鄰域圖G.

Step 2 選擇起始點(diǎn).

Step 3 擴(kuò)展.

以Step 2中得到的點(diǎn)S為起始點(diǎn)，用寬度優(yōu)先的方法依次搜索鄰域圖G中未被處理的點(diǎn)，設(shè)每次找到的點(diǎn)為x i，用Step 4中的方法計(jì)算x i的切空間并更新其鄰域，由此更新整個(gè)鄰域圖，直到所有的點(diǎn)都處理完.

Step 4 計(jì)算新點(diǎn)x i的鄰域的方法.

Step 4.1 初始化x i的合理鄰域?yàn)镽N（x i）＝｛｝，切空間點(diǎn)集為SN（x i）＝｛｝，δ1＝1.對(duì)?x ij∈K N N（x i），1≤j≤K，如果x i∈RN（x ij），RN（x i）＝RN（x i）∪x ij，SN（x i）＝RN（x i）.

對(duì)于切空間選擇中η的取值在很多實(shí)驗(yàn)中都有了較好的結(jié)果，可以直接使用.此外，隨著流形曲率的增加切空間和原空間比值逐漸減小，為了更好地適應(yīng)此變化，我們加入了ε，將閾值減小到上一次計(jì)算結(jié)果的ε倍.上述算法中的參數(shù)η和ε，本文分別?。?.90，0.95］和0.96.通過(guò)實(shí)驗(yàn)得出對(duì)于大多數(shù)結(jié)構(gòu)的流形，ε的值基本上是穩(wěn)定的，這樣就能根據(jù)流形的結(jié)構(gòu)自動(dòng)的得到較合理的閾值，保證了算法的靈活性和合理性.

2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)選取Swissroll、highly folded Swissroll和Swiss roll with hole三個(gè)數(shù)據(jù)集，分別用K－NN和本文的算法構(gòu)建鄰域圖.圖3、圖4（P222）、圖5（P222）和圖6（P222）給出了不同數(shù)據(jù)集上用兩種方法構(gòu)建的鄰域圖以及應(yīng)用于Isomap后對(duì)應(yīng)的低維嵌入結(jié)果.表1統(tǒng)計(jì)了用兩種算法應(yīng)用于Isomap后嵌入結(jié)果的殘差.

表1 K－NN和本算法的鄰域選擇方法對(duì)應(yīng)的殘差Table 1 Neighborhood selection method residuals of K－NN and the algorithm

圖3 Swissroll數(shù)據(jù)（n＝800）的對(duì)比結(jié)果Fig.3 Swissroll data（n＝800）comparison results

圖5 Highly folded Swissroll數(shù)據(jù)的對(duì)比結(jié)果Fig.5 Highly folded Swissroll data comparison results

圖6 Swissroll with hole數(shù)據(jù)的對(duì)比結(jié)果Fig.6 Swissroll with hole data comparison results

對(duì)比圖3、圖4、圖5、圖6可以直觀(guān)的看出本算法在不同密度、不同彎曲度結(jié)構(gòu)的流形上得到了較好的鄰域關(guān)系圖，避免了K－NN方法中存在的短路和空洞現(xiàn)象，同時(shí)通過(guò)對(duì)應(yīng)的低維嵌入結(jié)構(gòu)及表1中的殘差再次證明了本文中算法的合理性，該算法應(yīng)用于Isomap后，嵌入結(jié)果更加準(zhǔn)確.

3 算法的復(fù)雜度分析

本算法中關(guān)鍵的問(wèn)題是流形局部線(xiàn)性度的度量以及局部切空間的估計(jì)，其中都需要矩陣的分解來(lái)完成，因此我們將算法復(fù)雜度表示為樣本數(shù)N、原始空間維度D、本征維數(shù)d等相關(guān)參數(shù)的函數(shù)，通過(guò)函數(shù)來(lái)度量其性能.

（1）自適應(yīng)鄰域的選擇.首先，對(duì)每個(gè)點(diǎn)x，計(jì)算距離需要代價(jià)O（ND），通過(guò)排序得到KNN需要代價(jià)O（KN）.對(duì)于所有的點(diǎn)，找KNN的代價(jià)是O（N2（D＋K））.接著就是通過(guò)寬度優(yōu)先的方法依次確定要處理的點(diǎn)，該方法的代價(jià)約為O（N）.對(duì)每個(gè)給定的點(diǎn)x，利用其鄰域值構(gòu)成的協(xié)方差矩陣的特征分解來(lái)估算切空間，復(fù)雜度為O（2k3／3＋30k2），由于k?N，計(jì)算可以忽略.因此，本方法總的代價(jià)約為O（N2（D＋K）），和K－NN在同一個(gè)量級(jí).

（2）Isomap的投影.需要計(jì)算每個(gè)點(diǎn)的最短路徑，給定一個(gè)圖G＝（V，E），復(fù)雜度為O（V（V2＋E）），其中V是頂點(diǎn)，E是邊.在我們的算法中，基于鄰域矩陣G，則對(duì)應(yīng)的復(fù)雜度為O（N（N2＋k N））.對(duì)于用MDS進(jìn)行奇異值分解代價(jià)同上O（2k3／3＋30k2），可以忽略.

通過(guò)以上分析，不難發(fā)現(xiàn)算法整體的復(fù)雜度小于O（N3），和常見(jiàn)的K－NN在同樣的量級(jí).因此，本算法是在增加少量時(shí)間的前提下獲取了有效的鄰域信息，使嵌入結(jié)果更準(zhǔn)確，取得了較好的效果.

4 結(jié)束語(yǔ)

本文提出了一種基于流形彎曲度的有序自適應(yīng)鄰域選擇算法，該算法基于流形的局部線(xiàn)性特性，利用已有的合理鄰域點(diǎn)來(lái)增量地確定流形上數(shù)據(jù)點(diǎn)的鄰域，按寬度優(yōu)先的順序不斷擴(kuò)展，直到流形被完全重構(gòu).在不同結(jié)構(gòu)Swissroll數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：該算法可以根據(jù)采樣密度和流形彎曲度自適應(yīng)的確定鄰域，獲得更準(zhǔn)確的鄰域關(guān)系.

［1］ Tenenbaum J B，V.de Silva，Langford J C.A Global Geometric Framework for Nonlinear Dimensionality Reduction［J］.Science，2000，290：2319－2323.

［2］ Roweis S T，Saul L K.Nonlinear Dimensionality Reduction by Locally Linear Embedding［J］.Science，2000，290：2323－2326.

［3］ Zhang Z，Zha H.Principal Manifolds and Nonlinear Dimension Reduction Via Local Tangent Space Alignment［J］.SIAM JoumalonScientificComputing，2004，26（1）：313－338.

［4］ Kouropteva O，Okun O，Pietikainen M.Selection of the Optimal Parameter Value for the Locally Linear Embedding Algorithm［C］／／Proc.of the 1st International Conference on Fuzzy Systems and Knowledge Discovery（FSKD’02），2002：359－363.

［5］ Samko O，Marshall A D，Rosin P L.Selection of the Optimal Parameter Value for the Lsomap Algorithm［J］.PatternRecognitionLetters，2006，27（9）：968－979.

［6］ Nathan M，John K T.Parameterless Isomap with Adaptive Neighborhood Selection［C］／／Proceedings of the 28th DAGM Symposium，Berlin Heidelberg：Springer－Verlag，2006.

［7］ Li Y.Building k－edge－connected Neighborhood Graph for Distance－based Data Projection［J］.PatternRecognitionLetter，2005，26：2015－2021.

［8］ Li Y.Building k－connected Neighborhood Graphs for Isometric Data Embedding［J］.IEEETransactionsonPatternAnalysisandMachineIntelligence，2006，28（5）：827－831.

［9］ Wen G，Jiang L，Wen J.Using Locally Estimated Geodesic Distance to Optimize Neighborhood Graph for Isometric Data Embedding［J］.PatternRecognition，2008，41：2226－2236.

［10］ Wen G，Jiang L，Wen J.Local Relative Transformation with Application to Isometric Embedding［J］.PatternRecognition Letters，2009，30：203－211.

［11］ Gao X，Liang J.The Dynamical Neighborhood Selection Based on the Sampling Density and Manifold Curvature for Isometric Data Embedding［J］.PatternRecognitionLetters，2011，32（2）：101－402.

An Orderly Adaptive Neighborhood Selection Algorithm Based on Manifold Curvature

LI De－yu1，2，GAO Cui－zhen1，ZHAI Yan－h(huán)ui1
（1.SchoolofComputer＆InformationTechnology，ShanxiUniversity，Taiyuan030006，China；2.KeyLaboratoryofComputationalIntelligenceandChineseInformation ProcessingofMinistryofEducation，ShanxiUniversity，Taiyuan030006，China）

An orderly adaptive neighborhood selection algorithm is introduced because the traditional neighborhood selection algorithm has a defect that can not select neighbors adaptively based on the sample density and curvature.In this algorithm，data points start with the smallest curvature point in the manifold，and breadth－first searching algorithm was used to expand manifold data.For each point，we estimate the local tangent space based on the local linearity of manifold structure with existing neighborhood and then choose the right neighborhood adaptively through mapping of the neighborhood edge in the tangent space.This method is applied to Isomap，and experimental results validate the accurate of the embedding results for different data sets.

manifold learning；neighborhood selection；tangent space

TP391.4

A

0253－2395（2012）02－0219－05＊

2012－03－09；

2012－03－19

國(guó)家自然科學(xué)基金（60970014；61175067；60875040）；教育部高等學(xué)校博士點(diǎn)基金（200801080006）；山西省自然科學(xué)基金（2010011021－1）；山西省科技攻關(guān)項(xiàng)目（20110321027－02）

李德玉（1965－），山西曲沃人，博士，教授，主要研究方向?yàn)榇植诩碚摗⒛Ｊ阶R(shí)別、機(jī)器學(xué)習(xí)等.E－mail：lidy＠sxu.edu.cn