李 繁，严 星，张晓宇

(1.新疆财经大学 网络与实验教学中心，新疆 乌鲁木齐 830012；2.新疆财经大学 信息管理学院，新疆 乌鲁木齐 830012)

0 引 言

LLE数据降维算法是利用局部的信息计算相关权重，从而产生一个大型稀疏矩阵，通过解大型稀疏矩阵的特征值来解决非线性数据降维的问题。在LLE算法提出后又有一些改进的LLE算法提出：如HLLE算法结合了LLE和拉普拉斯特征映射来修改LLE的第二个步骤，并采用Hessain来评估测量权重，从而避免LLE算法存在的一些out-of-sample问题[1]。MLLE算法也是修改LLE的重建权重部分，通过引进对每一个邻点计算多个独立的线性权重来修改LLE的第二个步骤[2]，这个方法一样是在改进LLE计算权重时的正确性或可能会发生的一些问题。所以上面两个算法都是修改LLE的第二个步骤，来提高LLE算法的准确性。

在探讨LLE算法的准确性问题时，更改的通常都只有在重建权重的那个部分[3]，由于在任何LLE变种算法中都要计算KNN和解决稀疏矩阵特征值这两个问题，所以在整体的计算效率上，LLE已经通过KNN的这个步骤来选择与数据点接近的K个点来保持局部的信息，并将不在邻近的数据点权重设为0，这样一来通过重建权重的时候就可以产生一个大型的稀疏矩阵，产生大型的稀疏矩阵可降低后面特征值的计算量，所以通过KNN的这个步骤可以大量减少后面特征值的计算量，这也就是为何LLE的数据降维技术比其它的方法计算速度还快，不过就算KNN这步降低了特征值的计算量，其大型稀疏矩阵求特征值也存在效率上的问题，所以要加快整体的LLE计算效率就要先从KNN及稀疏矩阵这两部分来加速。……