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

张晓宇，孙海霞，黄天民

(西南交通大学 数学学院，四川 成都 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个点作为其近邻点。

第二步，计算局部权值矩阵W={wij}，对每个样本点用它的k个邻域来近似重构，即计算该点和每个近邻点的权重wij使得构建误差最小，解最小化目标函数

第三步，用局部权值矩阵W计算低维嵌入空间中的Y。由于wij代表着局部信息，低维空间要尽量保持高维空间的局部线性结构，所以固定wij，最小化目标函数

(1)

得到Y，LLE通过两个条件来约束优化问题使f(Y)对旋转、平移、伸缩变化具有不变性：样本点映射后的坐标以原点为中心；嵌入之后的向量有单位协方差，即

记f(Y)=‖Y-YWT‖2，则式(1)写成迹的形式

要解决的优化问题此时成为

这个问题的解为M=(I-WT)(I-W)的最小m个特征值对应的特征向量，即

由于M的最小特征值一般接近于0，因此取2～m+1个特征值所对应的特征向量作为Y，矩阵M=(I-WT)(I-W)通常被称为LLE矩阵。

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

从LLE的计算过程可以看出，当样本点个数比较大时，求近邻点和权重矩阵W的计算量也会随之增大。若样本集不均匀，近邻点个数k的选取对结果的影响比较大，而使用测地距离的LLE算法会降低样本分布对计算结果的影响(证明过程见文献[9])，因此本文在改进距离的LLE的基础上使用模糊C均值聚类的方法来缩减求近邻点及M矩阵的计算量，具体步骤如下：

第一步，采用模糊C均值聚类的方法[12-15]将样本集X={x1,x2,…,xn}分为c类，由于聚类的均值向量包含大量的信息，因此可以用聚类的均值向量(也称聚类中心向量)代表该类，再用所有的聚类中心{v1,v2,…,vc}作为新的样本集。

第二步，对新的样本集中的每个点vi计算它与其它c-1个样本点之间的测地距离G(vi,vj)，通过公式

求得样本点之间的调和距离，其中M(i)，M(j)分别表示vi，vj和其余各点之间距离的平均值，即

第三步，计算局部权值矩阵W={wij}，对每个样本点用它的k个邻域来近似重构，即计算该点和每个近邻点的权重wij使得构建误差最小，解最小化目标函数

(2)

式(2)中的I表示n维单位矩阵，对应的优化问题转化为以下的约束优化问题

令M=(I-WT)(I-W)，取M的第2～m+1个特征值所对应的特征向量当作低维嵌入的坐标。

采用测地距离的LLE算法可以使分布比较密集的区域的样本点距离增大，使得分布比较稀疏的区域的样本点之间的距离缩小，从而使样本点整体的分布均匀化，缓解用欧氏距离重构对流行结构造成的扭曲。其次，采用模糊C均值聚类的方法对样本点进行分类，可以使样本点个数增多时求近邻点及矩阵的计算量大大降低。因此，采用两者相结合的方法理论上较全面的对LLE算法进行了改进，下面用实验结果验证新算法的有效性。

3　实验

采用Matlab R2009a对新算法的有效性进行验证，本实验的数据集采样自Swiss Hole，N=2000，k分别取9,11,13，分别采用测地距离LLE和基于模糊C均值聚类和测地距离的LLE算法将数据降维至二维平面，两种降维方法所需时间如表1所示：

表1　两种方法降维时间的比较

由实验结果可知，利用模糊C均值聚类方法聚类后，重构权值矩阵的阶数与近邻点的个数只是和聚类的个数有关，大大缩减了求M矩阵和近邻点的计算量，因而计算速度较快些。

对LLE和基于模糊C均值聚类和测地距离的LLE算法在样本点个数变化时查准率进行实验，实验结果如图1所示：

图1　样本点个数变化时两种方法的查准率比较

从图1可以看出，随着样本点个数的增多，LLE算法与基于模糊C均值聚类和测地距离的LLE算法的检索精度均有所下降，但是两种算法却保持了一致的查准率，也就是说，随着样本点个数的增多，基于模糊C均值聚类和测地距离的LLE算法几乎不影响原来的检索精度。

针对LLE算法对样本点的计算量问题，提出了一种基于模糊C均值聚类和测地距离的LLE算法，该方法有效的缩减了求M矩阵阶数和近邻点的计算量，实验结果表明，改进的方法具有一定的优越性。

[1]Jolliffe I T. Principle Component Analysis[M]. Berlin: Springer, 1986.

[2]Mika S, Ratsch G, Weston J,etal. Fisher discriminant analysis with kernels[J]. Neural Networks for Signal Processing,1999, 8(9):41-48.

[3]Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Scinece, 2000,290:2323-2326.

[4]Borg I, Groenen P. Mordern Multidimentional Scaling: Theory and Application[M]. New York: Springer Verlag, 1997.

[5]Tenenbaum J B, Silva Vin de, Langford John C. A global geometric framework for nonlinear dimensionality reduction[J]. Science,2000,290:2319-2323.

[6]Orsenigo C, Vercellis C. Kernel ridge regression for out-of sample mapping in supervised manifold learning[J]. Expert System with Application,2012,39(9):7757-7762.

[7]Min R, Stanley D A, Yuan Z,etal. A deep non-linear feature mapping for large-margin kNN classification[C]. The 9th IEEE International Conference on Date Mining.2009:357-366.

[8]Strange H, Zwiggelaar R Z. Parallel projections for manifold learning[C]. The 9th International Conference on Machine Learning and Application, 2010:266-271.

[9]邹艳.高维数据降维方法的研究[D].成都：西南交通大学，2012年.

[10]余肖生，周宁.高维数据降维方法研究[J].情报科学，2007,25(8):1248-1251.

[11]王和勇，郑杰，姚正安,等.基于聚类和改进距离的LLE方法在数据降维中的应用[J]. 计算机研究与发展，2006，43(8)：1485-1490.

[12]张小红，裴道武,代建华.模糊数学与Rough集理论[M]. 北京：清华大学出版社，2013:135-145.

[13]苏锦旗，张文宇.基于模糊聚类的改进LLE算法[J].计算机与现代化，2014，(5):10-13.

[14]鲍正益.模糊聚类算法及其有效性研究[D].厦门，厦门大学，2006年.

[15]许丽利.聚类分析的算法及应用[D].吉林：吉林大学，2010年.

责任编辑王菊平

The LLE algorithm based on fuzzy clustering and geodesic distance

ZHANG Xiao-yu, SUN Hai-xia， HUANG Tian-min

(Department of Mathematics, Southwest Jiaotong University, Chengdu 611756, China)

Locally linear embedding (LLE) algorithm is a method to solve the problem of dimension reduction. To calculate weight matrix and determine the quantity of neighboring points, this paper proposes LLE algorithm which is based on fuzzy clustering and geodesic distance. Fuzzy C means clustering can reduce the amount of calculation of the weight value matrix and computing time. The application of the LLE algorithm works very well when a small number of neighboring points are chosen. Experimental results show certain advantages of the LLE algorithm as it greatly reduces the calculation M matrix and neighboring point calculation.

dimension reduction; locally linear embedding; geodesic distance; fuzzy C means clustering

TP391.9

A

1003-8078(2016)03-0008-04

2016-04-05

10.3969/j.issn.1003-8078.2016.03.03

张晓宇，女，山西霍州人，硕士研究生，主要研究方向为运筹与优化；孙海霞，女，山西吕梁人，硕士研究生，主要研究方向为微分方程；黄天民，男，河北邯郸人，教授，主要研究方向为优化与决策、模糊控制与智能控制。

国家自然科学基金项目(61473239)。