基于最小连通邻域图的ISOMAP算法

噪音的干扰和邻域大小的不合适会在ISOMAP算法的邻域图中引入“短路”边,使其不能正确表达数据的邻域结构,从而使该算法具有较差的鲁棒性和拓扑稳定性。为此,根据最小连通邻域图能有效避免“短路”边的特点,提出了一种能有效删除“短路”边因而更具鲁棒性和拓扑稳定性的ISOMAP算法——基于最小连通邻域图的ISOMAP（MCNG-ISOMAP）算法。该算法能在一定程度上避免邻域大小难以有效选取的问题,同时还能在不依赖于邻域大小的情况下发现数据真正的固有维数。     

ISOMAP算法参数的递增式选取

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

一种新的基于ISOMAP的数据可视化算法

作为古典MDS算法的一个非线性扩展,ISOMAP算法能较好地对嵌入在高维欧氏空间中的低维非线性流形进行可视化.然而,ISOMAP算法不但要求数据具有良好抽样且位于单一流形之上,而且还依赖于难以有效选取的邻域大小,这极大地限制了该算法的实际应用.为此提出了一种改进算法--GISOMAP,它采用MDS算法的一个变种来减弱长测地距离和"短路"边对距离保持的影响,不但能更好地对具有多聚类结构的数据进行可视化,而且对邻域大小也不再敏感,从而能更容易地得到实际应用.     

基于随机游走的流形学习与可视化

现有的全局流形学习算法都敏感于邻域大小这一难以高效选取的参数,它们都采用了基于欧氏距离的邻域图创建方法,从而使邻域图容易产生“短路”边。本文提出了一种基于随机游走模型的全局 流形学习算法(Random walk-based isometric mapping,RW-ISOMAP)。和欧氏距离相比,由随机游走模型得到的通勤时间距离是由给定两点间的所有通路以概率为权组合而成的,不但鲁棒性更高,而且还能在一定程度上度量具有非线性几何结构的数据之间的相似性。因此采用通勤时间距离来创建邻域图的RW-ISOMAP算法将不再敏感于邻域大小参数,从而可以更容易地选取邻域大小参数,同时还具有更高的鲁棒性。最后的实验结果证实了该算法的有效性。     

基于邻域距离ISOMAP算法的高光谱遥感降维算法

提出一种以邻域距离改进ISOMAP的算法(Neighborhood Distance ISOMAP,ND\|ISOMAP),该方法采用邻域距离逐步逼近流形距离来表达高维数据的流形结构。同时针对ISOMAP算法的计算复杂度高、运算时间长的特点,提出了一种基于矩阵分块和自动调图的ISOMAP算法(Block\|matrix and Auto\|color ISOMAP,BA\|ISOMAP)以提高运算速率。通过对高光谱遥感影像进行分类比较算法优劣性,基于邻域距离的ISOMAP算法较原始的ISOMAP算法降维效果有了较大的提升,最高分类精度达到97.36%,而原始的ISOMAP算法仅能达到75.01%的分类精度,而基于矩阵分块与自动调图ISOMAP与邻域距离相结合降维后精度达到89.61%,但是其计算速率得到了较大提升,为原始ISOMAP算法的近40倍。     

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

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

基于P-ISOMAP特征脸谱的人脸识别

针对等距映射(Isometric Projection)算法计算量大且易受噪声影响的缺点,根据主成分分析(PCA)兼具降维和除噪的特性,提出一种基于ISOMAP算法的P-ISOMAP特征脸谱(PCA-ISOMAP)人脸识别技术。该算法首先通过主成分分析把人脸图映射到一个人脸图像子空间,然后在人脸图像子空间中进行等距映射降维。P-ISOMAP特征脸谱算法在保持人脸图像的全局几何特性和低维人脸流形的同时,提高了算法效率,能够有效抑制人脸图像中噪声。通过在人脸库中的实验表明,改进后的算法在识别率以及运行效率方面都优于等距映射算法。     

流形学习算法中邻域大小参数的递增式选取

流形学习算法能否成功应用依赖于邻域大小参数的选取是否合适,但该参数在实际中通常难以高效选取。为此,提出一种邻域大小参数的递增式选取方法。按照流形的局部欧氏性,邻域图上的所有邻域都呈线性或近似线性,邻域大小参数若合适,此时所有邻域的线性度量可聚成一类;而邻域大小参数若不合适,邻域图上就会有部分邻域不再线性,其线性度量也不能聚成一类。对邻域图上的每一个邻域执行加权主成分分析,用重建误差对其线性程度进行度量,并计算相应的贝叶斯信息准则,以探测其聚类个数,从而实现对邻域大小参数的递增式选取。实验结果表明,该方法无需任何额外参数,具有较高的运行效率。     

一种改进的有间隔流形ISOMAP算法

ISOMAP算法成功应用的潜在条件是要求数据集均匀抽样于单个的内在流形。如果数据集均匀采样于某个内在流形,但内部出现了一个间隔,ISOMAP算法可能失效。提出了G-ISOMAP(ISOMAP with a Gap)算法,该算法充分利用了数据集中的间隔特性。首先检测被间隔的子流形间最短欧氏距离对应的数据点,然后将这些数据点互相设置为邻域点,最后用ISOMAP算法找到低维嵌入结果。对G-ISOMAP与ISOMAP算法的区别与联系进行了详细的理论说明,得出ISOMAP算法是G-ISOMAP算法的一个特例,G-ISOMAP算法是ISOMAP算法扩充的结论。实验结果验证了该算法比其他常用的流形学习算法在有间隔的数据集上更有效。     

基于改进邻域空间的高维混合数据特征选择算法

作为数据挖掘领域中一项重要的数据预处理技术,特征选择算法能够有效应对高维数据带来的“维数灾难”问题.然而,如何对高维的混合数据进行特征选取仍然是当前研究的重点和难点之一.基于邻域关系的邻域粗糙集模型因其能够处理名词型属性与数值型属性并存的混合数据,已成功应用于混合数据的特征选择.但是,现有邻域粗糙集对混合数据邻域关系的度量,仍然是基于等价关系的名词型数据划分与基于相似关系的数值型数据划分的简单融合,在利用模型划分的邻域空间和预定义的评价函数对高维混合数据进行特征选取时,适应性较差.为此,在邻域粗糙集模型的基础上,提出一种改进的邻域空间构造方法,并设计相应的邻域空间度量公式作为判别指标,自适应地调节邻域空间下邻域粒的大小;为了准确地表征高维混合数据邻域空间的判别能力,设计一种考虑边界数据和邻域空间大小的评价函数;在此基础上,提出一种启发式的高维混合数据特征选择算法.通过UCI标准数据集验证所提出算法的有效性.