张晓宇，孙海霞，黄天民

(西南交通大学 数学学院，四川 成都 611756)



基于模糊聚类和测地距离的LLE算法

张晓宇，孙海霞，黄天民

(西南交通大学 数学学院，四川 成都 611756)

局部线性嵌入算法(LLE)是一种解决降维问题的方法，针对权值矩阵的计算及近邻点个数选取，提出了基于模糊聚类和测地距离的LLE算法，模糊C均值聚类可以减少计算权值矩阵的计算量，缩减计算时间；使用测地距离的LLE算法可以在选取近邻点个数较小的情况下获得良好的效果。实验结果表明，基于模糊C均值聚类和测地距离的LLE算法大大缩减了计算M矩阵和近邻点的计算量，具有一定的优越性。

降维；局部线性嵌入法(LLE)；测地距离；模糊C均值聚类

1　局部线性嵌入法(LLE)

高维数据通常含有大量的冗余数据，维数缩减是模式识别的一项重要内容，通过对高维数据降维可以消除冗余性，提高图像的识别速度。传统的降维方法一般指线性降维方法，例如主元分析法(PCA)[1]、Fisher判别法[2]局部线性嵌入法(LLE)[3]、多维尺度法(MDS)[4]和等距离映射法(ISOMAP)[5]等，是非线性降维方法，介绍类似方法的文献也有很多[6-11]。其中LLE算法具有待定参数少、几何意义直观和有整体解析最优解等众多优点，因此受到很多学者的关注。

LLE是由Saul和Roweis在2000年提出的一种非线性降维方法，其主要思想是用局部线性逼近全局的非线性[3]，即通过彼此互相重叠的局部邻域提供整体信息，来保持整体的几何性质。

LLE算法将高维数据X=(x1,x2,…,xn)xi∈Rd映射到低维数据Y=(y1,y2,…,yn)，yi∈Rm(m

第一步，计算每个样本点xi与其它n-1个样本点之间的距离dij=|xi-xj|，(其中i,j=1,2,…,n)，选择与xi最近的前k个点作为其近邻点。……