A comment on “Using locally estimated geodesic distance to optimize neighborhood graph for isometric data embedding”

A geodesic distance-based approach to build the neighborhood graph for isometric embedding is proposed to deal with the highly twisted and folded manifold by Wen et al. [Using locally estimated geodesic distance to optimize neighborhood graph for isometric data embedding, Pattern Recognition 41 (2008) 2226-2236]. This comment is to identify the error in their example and the ineffectiveness of their algorithm.     

邻域参数动态变化的局部线性嵌入

局部线性嵌入是最有竞争力的非线性降维方法,有较强的表达能力和计算优势.但它们都采用全局一致的邻城大小,只适用于均匀分布的流形,无法处理现实中大量存在的非均匀分布流形.为此,提出一种邻域大小动态确定的新局部线性嵌入方法.它采用Hessian局部线性嵌入的概念框架,但用每个点的局部邻域估计此邻域内任意点之间的近似测地距离,然后根据近似测地距离与欧氏距离之间的关系动态确定该点的邻域大小,并以此邻域大小构造新的局部邻域.算法几何意义清晰,在观察数据稀疏和数据带噪音等情况下,都比现有算法有更强的鲁棒性.标准数据集上的实验结果验证了所提方法的有效性.     

改进重构权值的局部线性嵌入算法

目的 局部线性嵌入（LLE）算法是机器学习、数据挖掘等领域中的一种经典的流形学习算法。为克服LLE算法难以有效处理噪声、大曲率和稀疏采样数据等问题,提出一种改进重构权值的局部线性嵌入算法（IRWLLE）。方法 采用测地线距离来描述结构,重新构造和定义LLE中的重构权值,即在某样本的邻域内,将测地距离与欧氏距离之比定义为结构权值;将测地距离与中值测地距离之比定义为距离权值,再将结构权值与距离权值的乘积作为重构权值,从而将流形的结构和距离两种信息进行有机的结合。结果 对经典的人工数据Swiss roll、S-curve和Helix进行实验,在数据中加入噪声干扰,同时采用稀疏采样的方式来生成数据集,并与原始LLE算法和Hessian局部线性嵌入（HLLE）算法进行比较。实验结果表明,IRWLLE算法对比于LLE算法和HLLE算法,能够更好地保持流形的近邻关系,对流形的展开更加完好。尤其是对于加入噪声的大曲率数据集Helix,IRWLLE展现出极强的鲁棒性。对ORL和Yale人脸数据库进行人脸识别实验,采用最近邻分类器进行识别,将IRWLLE算法的识别结果与LLE算法进行对比。对于ORL数据集,IRWLLE算法识别率为90%,原LLE算法的识别率为85.5%;对于Yale数据集,IRWLLE算法识别率为88%,原LLE算法的识别率为75%,可见IRWLLE在人脸识别率上也有很大提高。结论 本文提出的IRWLLE算法对比于原LLE算法,不仅将流形距离信息引入到重构权值中,而且还将结构信息加入其中,有效减少了噪声和流形外数据点的干扰,所以对于噪声数据具有更强的鲁棒性,能够更好地处理稀疏采样数据和大曲率数据,在人脸识别率上也有较大提升。     

Building k-connected neighborhood graphs for isometric data embedding

Isometric data embedding using geodesic distance requires the construction of a connected neighborhood graph so that the geodesic distance between every pair of data points can be estimated. This paper proposes an approach for constructing k-connected neighborhood graphs. The approach works by applying a greedy algorithm to add each edge, in a nondecreasing order of edge length, to a neighborhood graph if end vertices of the edge are not yet k-connected on the graph. The k-connectedness between vertices is tested using a network flow technique by assigning every vertex a unit flow capacity. This approach is applicable to a wide range of data. Experiments show that it gives better estimation of geodesic distances than other approaches, especially when the data are undersampled or nonuniformly distributed.     

Building k edge-disjoint spanning trees of minimum total length for isometric data embedding

Isometric data embedding requires construction of a neighborhood graph that spans all data points so that geodesic distance between any pair of data points could be estimated by distance along the shortest path between the pair on the graph. This paper presents an approach for constructing k-edge-connected neighborhood graphs. It works by finding k edge-disjoint spanning trees the sum of whose total lengths is a minimum. Experiments show that it outperforms the nearest neighbor approach for geodesic distance estimation.     

流形距离与压缩感知核稀疏投影的局部线性嵌入算法

流形学习算法的目的是发现嵌入在高维数据空间中的低维表示,现有的流形学习算法对邻域参数k和噪声比较敏感。针对此问题,文中提出一种流形距离与压缩感知核稀疏投影的局部线性嵌入算法,其核心思想是集成局部线性嵌入算法对高维流形结构数据的降维有效性与压缩感知核稀疏投影的强鉴别性,以实现高效有降噪流形学习。首先,在选择各样本点的近邻域时,采用流形距离代替欧氏距离度量数据间相似度的方法,创建能够正确反映流形内部结构的邻域图,解决以欧氏距离作为相似性度量时对邻域参数的敏感。其次,利用压缩感知核稀疏投影作为从高维观测空间到低维嵌入空间的映射,增强算法的鉴别性。最后,利用Matlab工具对实验数据集进行仿真,进一步验证所提算法的有效性。     

仿射不变的自适应局部线性嵌入

目的: 为将流形学习有效应用于图像的降维与识别中,并消除图像的仿射变换对流形结构产生的影响,本文提出一种仿射不变的自适应局部线性嵌入算法。方法: 该算法在局部线性嵌入的基础上,为适应产生各种仿射变换的图像样本,引入切线距离计算各样本之间的相似程度,以此描述样本空间中的距离,并通过图像相似度函数自适应计算样本空间中每一点的邻域数量。结果: 实验结果表明,该算法能够构造出更合理的低维流形结构,并有效提升统计识别的正确率。结论: 本文算法对仿射变换不敏感,表现出更强的稳健性。     

The dynamical neighborhood selection based on the sampling density and manifold curvature for isometric data embedding

The construction of the neighborhood is a critical problem of manifold learning. Most of manifold learning algorithms use a stable neighborhood parameter (such as k-NN), but it may not work well for the entire manifold, since manifold curvature and sampling density may vary over the manifold. Although some dynamical neighborhood algorithms have been proposed, they are limited by either another global parameter or an assumption. This paper proposes a new approach to select the dynamical neighborhood for each point while constructing the tangent subspace based on the sampling density and the manifold curvature. And the parameters of the approach can be automatically determined by computing the correlation coefficient of the matrices of geodesic distances between pairs of points in input and output spaces. When we apply it to ISOMAP, the results of experiments on the synthetic data as well as the real world patterns demonstrate that the proposed approach can efficiently maintain an accurate low dimensional representation of the manifold data with less distortion, and give higher average classification rate compared to others.     

A novel maximum margin neighborhood preserving embedding for face recognition

This paper presents a novel supervised linear dimensionality reduction approach called maximum margin neighborhood preserving embedding (MMNPE). The central idea is to modify the neighborhood preserving embedding by maximizing the maximum margin distance while preserving the geometric structure of the manifold. Experimental results conducted on the ORL database, the Yale database and the VALID face database indicate the effectiveness of the proposed MMNPE.     

Incremental Isometric Embedding of High-Dimensional Data Using Connected Neighborhood Graphs

Most nonlinear data embedding methods use bottom-up approaches for capturing the underlying structure of data distributed on a manifold in high dimensional space. These methods often share the first step which defines neighbor points of every data point by building a connected neighborhood graph so that all data points can be embedded to a single coordinate system. These methods are required to work incrementally for dimensionality reduction in many applications. Because input data stream may be under-sampled or skewed from time to time, building connected neighborhood graph is crucial to the success of incremental data embedding using these methods. This paper presents algorithms for updating $k$-edge-connected and $k$-connected neighborhood graphs after a new data point is added or an old data point is deleted. It further utilizes a simple algorithm for updating all-pair shortest distances on the neighborhood graph. Together with incremental classical multidimensional scaling using iterative subspace approximation, this paper devises an incremental version of Isomap with enhancements to deal with under-sampled or unevenly distributed data. Experiments on both synthetic and real-world data sets show that the algorithm is efficient and maintains low dimensional configurations of high dimensional data under various data distributions.     

基于相对流形的局部线性嵌入

局部线性嵌入算法极大地依赖于邻域是否真实地反映了流形的内在结构,现有方法构造的邻域结构是拓扑不稳定的,对噪音和稀疏数据敏感.根据认知的相对性规律提出了相对变换,并用其构造了相对空间和相对流形.相对变换可以提高数据之间的可区分性,并能抑制噪音和数据稀疏的影响.在构造的相对空间和相对流形上确定数据点的邻域能够更真实地反映流形的内在结构,由此提出了增强的局部线性嵌入算法,明显地提高了性能,特别是基于流形的方法还同时提高了速度.标准数据集上的实验结果验证了该方法的有效性.     

基于局部密度和测地距离的谱聚类

传统根据[K]-近邻图计算测地距离的方法,虽然能够发现流形分布数据间的相似关系,但是当不同类的点存在粘连关系时,依此计算相似度时不能体现样本间的真实关系,从而无法有效聚类。针对传统测地距离计算相似度的方法不能有效处理粘连数据集的问题,提出了基于局部密度和测地距离的谱聚类方法。计算样本的局部密度,寻找每个样本点的最近高密度点,并选择边缘点和非边缘点;在边缘点和其最近高密度点之间构造边、非边缘点之间的[K]个近邻点构造边,依此计算测地距离和相似度并进行聚类。在人工数据集和UCI数据集上的实验表明,该算法在处理粘连数据集时有效提高了聚类准确率。     

基于采样密度和流形弯曲度的动态邻域算法

针对流形学习的邻域优化问题,提出一种动态邻域的算法。基于局部采样密度和流形弯曲度估计切空间,并为所有样本点动态地选择邻域,其参数可通过计算残差自动确定。实验结果表明,将这种算法应用于ISOMAP后,邻域得到进一步优化,嵌入结果也更加准确。     

基于完全二维对称主成分分析的人脸识别

镜像对称性是人脸的一个直观明显的自然特性,结合该特性在完全二维主成分分析的基础上提出完全二维对称主成分分析的人脸识别方法。该方法通过镜像变换得到奇对称样本和偶对称样本,分别对奇偶对称样本进行完全二维主成分分析,通过奇偶加权因子对奇偶对称样本的特征矩阵进行组合,并采用最近邻距离分类器分类。在ORL人脸数据库上的实验表明,该方法有较好的识别效果。     

基于邻域保持的流形学习算法评价模型

应力函数和残差只适合于评价距离严格保持的流形学习算法,dy-dx表示法又是一个定性模型。虽然距离比例方差可以比较和评价大多数的流形学习算法,但其需要计算测地线距离,具有较高的计算复杂度。为此,提出一种基于邻域保持的流形学习算法定量评价模型,该模型仅仅需要确定两个空间中每个对象的k个近邻,并计算出每个点在低维空间中的近邻保持情况,不用计算测地线距离。理论分析表明,邻域保持模型的计算复杂度远远低于距离比例方差的复杂度。在三个数据集上比较了两个模型的性能,实验结果表明,利用邻域保持模型不但可以评价同一算法在不同邻域参数下的嵌入效果,而且可以在不同的流形学习算法之间进行比较,并且其评价流形学习算法的性能优于距离比例方差。     

基于测地线距离的广义高斯型Laplacian 特征映射

传统的Laplacian 特征映射是基于欧氏距离的近邻数据点的保持,近邻的高维数据点映射到内在低维空间后仍为近邻点,高维数据点的近邻选取最终将影响全局低维坐标.将测地线距离和广义高斯函数融合到传统的Laplacian 特征映射算法中,首先提出了一种基于测地线距离的广义高斯型Laplacian 特征映射算法(geodesicdistance-based generalized Gaussian LE,简称GGLE),该算法在用不同的广义高斯函数度量高维数据点间的相似度时,获得的全局低维坐标呈现出不同的聚类特性;然后,利用这种特性进一步提出了它的集成判别算法,该集成判别算法的主要优点是:近邻参数K 固定,邻接图和测地线距离矩阵都只构造一次.在木纹数据集上的识别实验结果表明,这是一种有效的基于流形的集成判别算法.     

核岭回归的邻域保持最大间隔分析的人脸识别

邻域保持嵌入是局部线性嵌入的线性近似,强调保持数据流形的局部结构.改进的最大间隔准则重视数据流形的判别和几何结构,提高了对数据的分类性能.文中提出的核岭回归的邻域保持最大间隔分析既保持流形的局部结构,又使不同类别的数据保持最大间隔,以此构建算法的目标函数.为了解决数据流形高度非线性化的问题,算法采用核岭回归计算特征空间的变换矩阵.先求解数据样本在核子空间中降维映射的结果,再解得核子空间.在标准人脸数据库上的实验表明该算法正确有效,并且识别性能优于普通的流形学习算法.     

扩大局部邻域的疏散嵌入算法

非线性流形学习降维方法已经被广泛应用到人脸识别、入侵检测以及传感器网络等领域。然而,能够有效处理稀疏数据的流形学习算法很少。基于局部线性嵌入（LLE）算法的思想框架,提出一种扩大局部邻域的稀疏嵌入算法,通过对局部区域信息加强,使得在样本较少的情况下,达到丰富重叠信息的目的。在稀疏的人工和人脸数据集上的实验结果表明,所提算法产生了较好的嵌入及分类结果。     

Stochastic neighbor projection on manifold for feature extraction

This paper develops a manifold-oriented stochastic neighbor projection (MSNP) technique for feature extraction. MSNP is designed to find a linear projection for the purpose of capturing the underlying pattern structure of observations that actually lie on a nonlinear manifold. In MSNP, the similarity information of observations is encoded with stochastic neighbor distribution based on geodesic distance metric, then the same distribution is required to be hold in feature space. This learning criterion not only empowers MSNP to extract nonlinear feature through a linear projection, but makes MSNP competitive as well by reason that distribution preservation is more workable and flexible than rigid distance preservation. MSNP is evaluated in three applications: data visualization for faces image, face recognition and palmprint recognition. Experimental results on several benchmark databases suggest that the proposed MSNP provides a unsupervised feature extraction approach with powerful pattern revealing capability for complex manifold data.