李德玉，高翠珍，翟巖慧

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

2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006）

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

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

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

2.山西大學(xué) 計算智能與中文信息處理教育部重點實驗室，山西 太原 030006）

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

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

0 引言

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

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

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

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

（3）通過矩陣的特征分解計算低維嵌入.

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

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

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

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

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

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

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

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

具體算法如下：

Step 1 確定KNN.

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

Step 2 選擇起始點.

Step 3 擴展.

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

Step 4 計算新點x i的鄰域的方法.

Step 4.1 初始化x i的合理鄰域為RN（x i）＝｛｝，切空間點集為SN（x i）＝｛｝，δ1＝1.對?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）.

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

2 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

本文提出了一種基于流形彎曲度的有序自適應(yīng)鄰域選擇算法，該算法基于流形的局部線性特性，利用已有的合理鄰域點來增量地確定流形上數(shù)據(jù)點的鄰域，按寬度優(yōu)先的順序不斷擴展，直到流形被完全重構(gòu).在不同結(jié)構(gòu)Swissroll數(shù)據(jù)集上的實驗結(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

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

李德玉（1965－），山西曲沃人，博士，教授，主要研究方向為粗糙集理論、模式識別、機器學(xué)習(xí)等.E－mail：lidy＠sxu.edu.cn