＊ 基于流形弯曲度的有序自适应邻域选择算法

李德玉，高翠珍，翟岩慧

（1.山西大学 计算机与信息技术学院，山西 太原 030006；

2.山西大学 计算智能与中文信息处理教育部重点实验室，山西 太原 030006）

＊基于流形弯曲度的有序自适应邻域选择算法

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

（1.山西大学 计算机与信息技术学院，山西 太原 030006；

2.山西大学 计算智能与中文信息处理教育部重点实验室，山西 太原 030006）

针对传统邻域选择方法不能根据流形样本密度和弯曲度合理选择邻域的缺点，提出了一种有序自适应的邻域选择算法.该算法从流形上曲率最小的点开始，以宽度优先的次序不断地处理每个点.对搜索到的数据点，基于流形结构的局部线性特性，利用已有的邻域信息估算其局部切空间，然后通过其邻域边在切空间的投影自适应地选择合适的邻域.实验结果表明：该算法应用于Isomap后，对不同结构的数据集嵌入结果更准确.

流形学习；邻域选择；切空间

0 引言

随着信息技术的快速发展，真实世界中数据的规模也在以几何级的速度增长，出现了大量的高维数据，这些数据具有高维稀疏性，某些特性也发生了很大变化，同时数据的计算量也迅速上升，使得传统的线性数据降维方法不能满足需求，因此需要找到新的降低数据维数的方法.流形学习就是一种新的非线性降维技术，即从数据集中寻找内在规律性，通过分析提取于研究对象的数据集的外在几何现象来认识其本质，已经成为机器学习、模式识别、数据挖掘等领域的研究热点之一.

近年来，流形学习领域产生了大量的研究成果，如等度规映射ISOMAP［1］、局部线性嵌入LLE［2］、局部切空间排列LTSA［3］等算法是具有代表性的流形学习算法，这些算法有一个统一的框架，主要由三步组成：

（1）计算原始空间中每个点的邻域，根据邻域信息来重构流形的结构，形成一个邻域图；

（2）基于上一步构建的邻域图创建一个矩阵；

（3）通过矩阵的特征分解计算低维嵌入.

流形学习算法成功的关键是第一步，选择合适的邻域.目前常用的邻域选择方法是K－NN和ε－NN，这两种方法中的参数K和ε都是人为给定的，然而不同结构的流形对参数的选择是敏感的，参数太大和太小均不能得到合理的邻域，影响流形结构的正确恢复，甚至使得一些流形学习算法无法运行.此外，以上两种方法只适应于数据点分布均匀的流形，不能根据流形的不同结构、密度和弯曲度选择合适的邻域参数.鉴于此，Kouropteva等人在2002年提出了LLE的最优邻域参数选择算法［4］，Samko等人借鉴Kouropteva的思想也为Isomap提出了最优邻域参数选择算法［5］，该类算法在给定一定邻域参数范围之内迭代运行LLE和Isomap算法，将得到的低维嵌入用残差值来度量，将残差值最小时对应的邻域参数作为最优邻域值，然而这样得到的参数仍然是固定值，显然不能满足分布不均匀且曲率不断变化的流形，同时算法效率低；Karina、Nathan，M.等人依据流形的局部线性特性提出了基于估计切空间并动态自适应选择邻域的算法［6］；Li Yang使用所有数据点完全图的K边连通子图和K连通最小生成子图为流形构建连通的邻域图［7－8］，得到邻域参数，该算法保证了邻域图的连通性，但参数仍然是固定值.Wen等人分别用局部测地距离和局部空间转化来优化邻域［9－10］；Gao Xiaofang等人提出了一种基于采样密度的动态邻域选择算法［11］等.通过以上分析不难发现，已有算法虽然能为流形学习的邻域选择提供一定的方便，但仍存在一些问题，因此，本文针对邻域选择问题提出了一种基于流形弯曲度的有序自适应邻域选择算法，该算法基于邻域的局部线性特性，利用邻域边在切空间的投影对不同结构的流形自适应地选择合适的邻域，该方法应用于Isomap算法后得到了更准确的低维嵌入.

1 自适应邻域选择

图1 宽度优先顺序依次处理各个点Fig.1 Processing all points with breadth－first order

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

通过图1和图2来说明本文提出算法的主要思想.图1用曲线的例子说明自适应邻域构建的过程：选择流形弯曲度最小且没有重叠的点S作为起始点，用宽度优先的方法依次搜索点，并计算其邻域.

观察图2，可以看出图中点是取自一条曲线构成的流形，该流形的内在维数是一维，应对其进行一维重建，图中pc边和pd边形成的二维重建均会破坏原流形的结构，pc边使流形发生“短路”现象，称为“短路边”，pd边被点a孤立，偏离了原流形的结构，称为“孤立边”，因此正确的恢复流形的结构需去掉这些不合理的边，我们将去掉“孤立边”和“短路边”的邻域称为“合理邻域”.此外，从图2明显可以看出不管是“短路边”还是“孤立边”，一个共同的特点就是邻域边和邻域切空间的夹角较大，因此可以通过与切空间的夹角来去除“孤立边”和“短路边”得到合理的邻域.

目前计算切空间的方法大多是用点的最近邻来逼近，近邻点选取的合理与否就决定了切空间逼近的准确性，当流形的曲率较大，或者是重叠度很高时，很容易将短路点和孤立点作为近邻，这样会导致切空间出现严重的错误，邻域选取不合理.鉴于这种情况，本算法使用了自适应方法来决定点的邻域，首先选取弯曲度小并且没有重叠的点作为起始点，用已经构建好的合理邻域作为新点的邻域，然后通过保证流形的局部线性特性来逼近切空间，按宽度优先的次序逐步扩展，最终确定每一个点的合理邻域.

如图1中当搜索到点a时，点c的合理邻域RN（c）＝｛a，d｝已经确定，此时a，c互为邻域，SN（a）＝｛c｝，用来逼近点a切空间的点集明显为｛c｝∪｛b｝，因为边ac和边ab构成的子空间的线性度高于边ac和边ag或af构成的子空间的线性度，并且边ab的长度小于边ag或af的长度，因此用点b能更准确地逼近a点的切空间.确定切空间的点集后，用图2中的方法更新邻域.如图2中当前点为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.

Step 2 选择起始点.

Step 3 扩展.

以Step 2中得到的点S为起始点，用宽度优先的方法依次搜索邻域图G中未被处理的点，设每次找到的点为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）.

对于切空间选择中η的取值在很多实验中都有了较好的结果，可以直接使用.此外，随着流形曲率的增加切空间和原空间比值逐渐减小，为了更好地适应此变化，我们加入了ε，将阈值减小到上一次计算结果的ε倍.上述算法中的参数η和ε，本文分别取［0.90，0.95］和0.96.通过实验得出对于大多数结构的流形，ε的值基本上是稳定的，这样就能根据流形的结构自动的得到较合理的阈值，保证了算法的灵活性和合理性.

2 实验结果及分析

实验选取Swissroll、highly folded Swissroll和Swiss roll with hole三个数据集，分别用K－NN和本文的算法构建邻域图.图3、图4（P222）、图5（P222）和图6（P222）给出了不同数据集上用两种方法构建的邻域图以及应用于Isomap后对应的低维嵌入结果.表1统计了用两种算法应用于Isomap后嵌入结果的残差.

表1 K－NN和本算法的邻域选择方法对应的残差Table 1 Neighborhood selection method residuals of K－NN and the algorithm

图3 Swissroll数据（n＝800）的对比结果Fig.3 Swissroll data（n＝800）comparison results

图5 Highly folded Swissroll数据的对比结果Fig.5 Highly folded Swissroll data comparison results

图6 Swissroll with hole数据的对比结果Fig.6 Swissroll with hole data comparison results

对比图3、图4、图5、图6可以直观的看出本算法在不同密度、不同弯曲度结构的流形上得到了较好的邻域关系图，避免了K－NN方法中存在的短路和空洞现象，同时通过对应的低维嵌入结构及表1中的残差再次证明了本文中算法的合理性，该算法应用于Isomap后，嵌入结果更加准确.

3 算法的复杂度分析

本算法中关键的问题是流形局部线性度的度量以及局部切空间的估计，其中都需要矩阵的分解来完成，因此我们将算法复杂度表示为样本数N、原始空间维度D、本征维数d等相关参数的函数，通过函数来度量其性能.

（1）自适应邻域的选择.首先，对每个点x，计算距离需要代价O（ND），通过排序得到KNN需要代价O（KN）.对于所有的点，找KNN的代价是O（N2（D＋K））.接着就是通过宽度优先的方法依次确定要处理的点，该方法的代价约为O（N）.对每个给定的点x，利用其邻域值构成的协方差矩阵的特征分解来估算切空间，复杂度为O（2k3／3＋30k2），由于k≪N，计算可以忽略.因此，本方法总的代价约为O（N2（D＋K）），和K－NN在同一个量级.

（2）Isomap的投影.需要计算每个点的最短路径，给定一个图G＝（V，E），复杂度为O（V（V2＋E）），其中V是顶点，E是边.在我们的算法中，基于邻域矩阵G，则对应的复杂度为O（N（N2＋k N））.对于用MDS进行奇异值分解代价同上O（2k3／3＋30k2），可以忽略.

通过以上分析，不难发现算法整体的复杂度小于O（N3），和常见的K－NN在同样的量级.因此，本算法是在增加少量时间的前提下获取了有效的邻域信息，使嵌入结果更准确，取得了较好的效果.

4 结束语

本文提出了一种基于流形弯曲度的有序自适应邻域选择算法，该算法基于流形的局部线性特性，利用已有的合理邻域点来增量地确定流形上数据点的邻域，按宽度优先的顺序不断扩展，直到流形被完全重构.在不同结构Swissroll数据集上的实验结果表明：该算法可以根据采样密度和流形弯曲度自适应的确定邻域，获得更准确的邻域关系.

［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－hui1
（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

国家自然科学基金（60970014；61175067；60875040）；教育部高等学校博士点基金（200801080006）；山西省自然科学基金（2010011021－1）；山西省科技攻关项目（20110321027－02）

李德玉（1965－），山西曲沃人，博士，教授，主要研究方向为粗糙集理论、模式识别、机器学习等.E－mail：lidy＠sxu.edu.cn