基于小世界模型的流形学习算法

等距特征映射(ISOMAP)不仅计算复杂度很高,而且缺乏对新样本的学习能力。基于标志点的ISOMAP(L-ISOMAP)通过只保持一些标志点之间的测地线距离有效地降低了复杂度,然而标志点集的随机选择常常会导致较差的嵌入结果。为此,提出了一种基于小世界模型的流形学习算法。根据小世界模型的原理,该算法仅仅保持每个样本点与其k个最近邻和一些随机选择的远点之间的测地线距离,采用最速梯度下降法优化来得到数据的低维表示。理论分析表明,该算法的计算复杂度远远低于ISOMAP的复杂度。利用应力函数和剩余方差对3个算法进行了比较。实验结果表明,从该算法得到的结果与从ISOMAP得到的结果相近,且优于从L-ISOMAP得到的结果。同时,该算法可以实现对新样本的学习,对噪声也不太敏感。     

流形学习中基于局部线性结构的自适应邻域选择

近年来,流形学习成为包括机器学习、模式识别和计算机视觉等相关领域的研究热点.流形学习算法中,邻域选择直接关系到算法的性能,而传统的邻域选择算法如k近邻和ε邻域算法存在参数难以确定,所构建邻域不能反映流形学习算法对邻域要求等缺点.提出了一种基于流形局部线性结构的自适应邻域选择算法(ANSLL).首先通过分析现有流形学习算法,总结出构建邻域的两个基本原则:1)同一邻域的所有点都近似地位于某一d维线性子空间内(d为流形维数);2)每个邻域包含尽可能多的点.基于这两个基本原则,ANSLL 算法采用主成分分析技术(PCA)度量有限点集的线性程度,通过邻域压缩或扩张方式自适应地构建邻域.针对邻域线性结构的特点,还提出了一种改进的邻域图构建方法,以提高等度映射(Isomap)算法中测地线距离估计的准确性.最后大量系统的实验表明,ANSLL算法能够依据流形的局部曲率自适应地构建邻域,从而提高大多数流形学习算法(如Isomap和LLE)的性能.     

基于近邻元分析的半监督流形学习算法*

现有的大多数流形学习算法偏重保持流形的几何结构,并未考虑到样本点的标签信息,这在一定程度上限制了流形学习算法在数据分类中的应用.因此文中提出一种基于近邻元分析的半监督流形学习算法,采用近邻元分析学习距离度量矩阵,在距离度量方式下选择样本点的局部邻域点.基于距离度量方式构造样本点和邻域点的局部几何结构,并在样本点的低维嵌入坐标中保持这种局部几何结构不变.3个不同数据集上的分类实验验证了文中算法的有效性.     

一种选择标注分层流形学习算法

流形数据的查询需要使用流形的嵌入表示,因此查询流形数据需要访问大量的样本数据.提出一种选择标注分层流形学习算法,选择出的标注点集用来帮助查找流形数据.首先采用自适应近邻算法求出每个数据的最优近邻,然后构造测地线矩阵,最后逐步迭代随机选择标注点,求出每个标注点的极大单元子集,直到流形数据集变成空集,形成初始标注点集.此外...     

基于邻域保持嵌入和标准距离K近邻的多模态过程故障检测

提出一种基于邻域保持嵌和标准距离K近邻(neighborhood preserving embedding-standard distance k nearest neighbor rule, NPE-SDKNN)的故障检测方法来解决非线性和多模态问题。首先,使用邻域保持嵌入方法提取数据中的流形结构,对数据进行降维;其次,在低维空间计算每个样本的标准距离,将各模态间的数据调整到同一尺度;最后使用标准距离的统计量对故障进行检测。邻域保持嵌入能够解决非线性问题和降低计算复杂度,标准距离K近邻通过用标准距离替代原始距离,消除了数据的多模态特征,使用NPE-SDKNN方法进行故障检测,能够提高多模态数据的故障检测率。在田纳西伊斯曼过程运用NPE-SDKNN方法,结果表明,相对于K近邻、主元分析、邻域保持嵌入、标准距离K近邻方法,NPE-SDKNN具有更高的故障检测率。     

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

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

基于二维测地线距离保持映射的人脸识别

人脸空间是嵌套在高维观测空间中的低维流形,为了更好地描述人脸空间的凸起和凹进等细微结构,提出了一种基于二维测地线距离保持映射的人脸识别算法。算法采用矩阵的模式表示人脸空间中的样本图像;基于图像的矩阵表示模型,采用二维测地线距离保持映射算法计算人脸空间的低维嵌套流形;以人脸样本在低维流形空间中的投影为特征进行人脸识别。在CMU PIE人脸数据库上的实验结果验证了算法的合理性和有效性。     

基于流形的概念空间形式化研究

概念是人们对事物本质的认识、逻辑思维的最基本单元和形式,是人类思维的基础,是反映事物本质属性的思维产物。Grdenfors教授于2000年发表的著作中提出的,简单来说Grdenfors教授建立的概念空间是基于域以及其上的几何特性的属性来建立和计算概念、属性、相似性的模型。基于流形的LLE算法的主要思想是在嵌套空间每个采样点可以用它的近邻点线性表示,在低维空间中保持每个邻域中的权值不变,重构原数据点,使重构误差最小。它可以学习任意维数的低维流形,每个点的近邻权值在平移,旋转,伸缩变换下是保持不变的。该文文通过把概念空间中的各个域当成一个流形,把各域中的维看成是流形的n维数据,实验中先后通过没有使用流形和通过基于流形的LLE算法进行降维后的进行比较,得出的实验结果是使用流形的方法对于某些不能细分的域能起到很好的作用,体现了该算法对于概念空间研究的准确性和优越性。     

基于自适应邻域选择的局部判别投影算法

在多模数据分类中,使用局部Fisher判别分析和边界Fisher分析方法构建邻域不能充分反映流形学习对邻域的要求.为此,提出一种基于自适应邻域选择的局部判别投影算法.采用自适应方法扩大或者缩小近邻系数k,以构建邻域,从而保持局部线性结构,揭示流形的内在几何结构,利用局部化方法使得投影空间中同类近邻样本尽量紧凑、异类近邻样本尽量分开.在ORL和YALE入脸数据库中进行实验,结果表明,在不同训练样本个数下,该算法均能获得较高的识别率.     

基于最优密度方向的等距映射降维算法

等距映射算法(ISOMAP)是一种典型的非线性流形降维算法,该算法可在尽量保持高维数据测地距离与低维数据空间距离对等关系的基础上实现降维.但ISOMAP容易受噪声的影响,导致数据降维后不能保持高维拓扑结构.针对这一问题,提出了一种基于最优密度方向的等距映射(ODD–ISOMAP)算法.该算法通过筛选数据的自然邻居确定每个数据沿流形方向的最优密度方向,之后基于与各近邻数据组成的向量相对最优密度方向投影的角度、方向和长度合理缩放局部邻域距离,引导数据沿流形方向计算测地距离,从而降低算法对噪声的敏感度.为验证算法有效性,选取了2类人工合成数据和5类实测数据作为测试数据集,分别使用ISOMAP,LLE,HLLE,LTSA,LEIGS,PCA和ODD–ISOMAP算法对数据集降维,并对降维数据进行K-mediods聚类分析.通过比对聚类正确率以及不同幅度噪声对此正确率的影响程度评价各算法降维效果优劣.结果表明,ODD–ISOMAP算法较其他6种常见算法降维效果提升显著,且对噪声干扰有更强的抵抗能力.     

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.     

Using locally estimated geodesic distance to optimize neighborhood graph for isometric data embedding

To deal with the highly twisted and folded manifold, this paper propose a geodesic distance-based approach to build the neighborhood graph for isometric embedding. This approach assumes that the neighborhood of a point located at the highly twisted place of the manifold may not be linear so that its neighbors should be determined by geodesic distance. This approach firstly determines the neighborhood for each point using Euclidean distance and then applies the locally estimated geodesic distances to optimize the neighborhood. It increases only linear time complexity. Furthermore the optimized neighborhood can speed up the subsequent embedding process. The proposed approach is simple, general and easy to deal with a wider range of data. The conducted experiments on both synthetic and real data sets validate the approach.     

ISOMAP算法参数的递增式选取

ISOMAP算法能否被成功应用依赖于其唯一参数——邻域大小的选取是否合适,然而,如何高效地选取一个合适的邻域大小目前还是一个难题。当邻域大小变得不合适时,短路边将会出现在邻域图中,从而严重破坏与之相关的最短路径距离对测地距离的逼近能力。和非短路边不同,短路边的两个端点虽然在欧氏空间中相距较近,但在流形上却相距甚远。基于短路边的这一特点,采用序来近似度量一条边的两个端点在流形上的远近程度,因而能够递增式地对邻域大小进行合适的选取。和基于残差的参数选取方法不同,该方法只需递增式地运行广度优先搜索算法,而无需就每一个可能的邻域大小分别运行整个ISOMAP算法,从而具有比较高的运行效率。最终的实验结果证实了该方法的可行性。     

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

目的 局部线性嵌入（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算法,不仅将流形距离信息引入到重构权值中,而且还将结构信息加入其中,有效减少了噪声和流形外数据点的干扰,所以对于噪声数据具有更强的鲁棒性,能够更好地处理稀疏采样数据和大曲率数据,在人脸识别率上也有较大提升。     

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

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

流形学习中邻域大小参数的合适性判定

流形学习算法能否成功应用严重依赖于其邻域大小参数的选择是否合适,为此,提出了一种高效的邻域大小参数的合适性判定方法。基于流形的局部欧氏性,该方法用PCA（Principal Component Analysis,主成分分析）重建误差对邻域图上每一个邻域的线性程度进行衡量,然后根据邻域图上所有PCA重建误差的聚类个数来判定相应邻域大小的合适性。该方法无需象残差那样运行相对耗时的流形学习算法,从而具有较高的运行效率,其有效性可通过实验结果得以证实。     

Unsupervised manifold learning based on multiple feature spaces

Manifold learning is a well-known dimensionality reduction scheme which can detect intrinsic low-dimensional structures in non-linear high-dimensional data. It has been recently widely employed in data analysis, pattern recognition, and machine learning applications. Isomap is one of the most promising manifold learning algorithms, which extends metric multi-dimensional scaling by using approximate geodesic distance. However, when Isomap is conducted on real-world applications, it may have some difficulties in dealing with noisy data. Although many applications represent a special sample by multiple feature vectors in different spaces, Isomap employs samples in unique observation space. In this paper, two extended versions of Isomap to multiple feature spaces problem, namely fusion of dissimilarities and fusion of geodesic distances, are presented. We have employed the advantages of several spaces and depicted the Euclidean distance on learned manifold that is more compatible to the semantic distance. To show the effectiveness and validity of the proposed method, some experiments have been carried out on the application of shape analysis on MPEG7 CE Part B and Fish data sets.     

统计流形扩散核的文本分类方法

提出Dirichlet混合多项式(DCM)流形,并利用DCM流形可与正半球流形建立同胚和等距关系的性质,通过拉回映射将正半球流形的测地距离映射为DCM流形的测地距离,从而在DCM流形上建立距离度量,构建统计流形上的Dirichlet混合多项式扩散核和Dirichlet混合多项式倒排文档频率(DCMIDF)扩散核。利用WebKBTop4和20Newsgroups语料库上进行实验,DCM流形能比欧氏空间更能准确地描述文本。与多项式核支持向量机算法、,负测地距离核支持向量机算法相比,实验结果显示文中基于DCM扩散核和DCMIDF扩散核的支持向量机算法可取得良好的文本分类效果。     

基于边界检测的多流形学习算法*

已知流形学习算法都假设数据分布于一个单流形,而现实中大部分数据都分布在多流形上,因此限制算法的实际应用.基于此种情况,文中提出基于边界检测的多流形学习算法,通过检测流形的边界处理分布于多流形的数据,并且可以较好地保持流形内、流形间的测地距离.算法首先检测流形边界,再分别降维处理各流形,最后将各低维坐标重置于一个全局坐标系中.在人工数据集和真实数据集上的对比实验表明文中算法的可行性和有效性.