01 数据降维

数据降维是指通过线性的或非线性的映射关系将高维数据转换成低维数据的过程。一般情况下，该低维数据代表了原始高维数据的主要成分（如下图所示），并描述了原始高维数据的空间分布结构。由于经过降维后的数据更易于被分类、识别、可视化以及存储等，故数据降维技术在诸多科研领域受到了越来越多地关注。

从数据本身的的性质特征来看，数据降维可以大致分为线性降维和非线性降维两种技术方法。其中，线性降维技术仅对于数据维数相对较低、且具有全局线性结构的数据有着很好的降维效果。然而，在实际的科学研究中，科研工作者却需要面对海量的非线性高维数据。因此，能够有效处理高维非线性数据的方法亟待被提出，本文将介绍一种用于处理高维非线性数据的降维方法。

02 局部线性嵌入

02-01 全局重建矩阵的求解

局部线性嵌入（Locally linear embedding, LLE）是一种非线性的降维方法，该算法由 Sam T.Roweis等人于2000年提出并发表在《Science》杂志上。LLE试图保留原始高维数据的局部性质，通过假设局部原始数据近似位于一张超平面上，从而使得该局部的某一个数据可以由其邻域数据线性表示，如下图所示：

基于上述思想，原始数据集中任意一个数据都可以看作被表示的点，这相当于将局部的线性表示一步一步转换成了全局的非线性表示。该过程的数学描述为：

其中，xi（i为下标，下同）表示原始数据集中的第i个数据，xik表示数据xi的第k个邻域数据，wik表示xik对应的权重。当xi已知时，邻域数据xik可以通过KNN等算法求出。因此，可以将上式转化成对wik的优化问题，误差函数如下所示：

其中，wi=[wi1,wi2,...wik]T（T表示转置，下同），表示xi的重建系数。为了方便求解，不妨对wi添加约束条件：

于是有：

进一步化简得到：

其中有：

应用拉格朗日数乘法求解上述的优化问题，得到：

其中，one=[1,1,...,1]且尺寸为1xk.因此，对拉格朗日函数求wi的偏导数，得到：

为简便起见，此处进一步化简为：

由于Ai不一定可逆，所以对Ai添加一定的扰动项，如下所示：

其中，small_num表示一个极小的常数值，trace()表示矩阵求迹，eye(k,k)表示kxk的单位对角矩阵。因此解得xi的重建系数为：

最后再对求得的wi做归一化即可。

综上所述，虽然以上分析过程只是针对高维数据xi，但是其他数据xj(j不等于i)也可以按照此方法计算出相应的局部重建矩阵，从而最终得到整个数据集的全局重建矩阵。

02-02 低维数据的求解

在上一节中求得的wi实际为kx1的向量。因此，若原始数据集中共含有n个数据，那么最终求得的w可以组成一个kxn的矩阵，如下所示：

由于局部线性嵌入会保留原始数据的拓扑结构，故降维得到的低维数据具有同高维数据一样的局部线性结构，即：

其中，yi表示低维数据集中的第i个数据，yik表示yi的第k个邻域数据，wik表示与yik对应的重建系数（即上节中求得的重建系数）。故，本节的优化函数为：

将该式化简为：

其中，mi为nxn的权值矩阵，表示从低纬数据集y中取出用于表示yi的邻域数据以及从mi中取出相应的权值系数，Ii表示从低维数据集y中取出第i个数据。mi实际上就是由w组成的稀疏矩阵。例如，当w1=[2,5,7,3,9]时,则m1只在表示第2、5、7、3、9列数据的坐标上不为0，而其他位置均用0表示。进一步化简得到：

令R=(Ii-mi)，于是有：

为了定解，对l(y)添加如下两个约束条件：

其中Id表示d维的单位矩阵。又因为：

同理可得：

故第一个约束条件可以改为：

其中y=[y1,y2,...,yn].

对该优化函数应用拉格朗日数乘法，得到：

对y求偏导数，得：

令该偏导数为0，则有：

因此，yT实际为由矩阵R*RT特征向量组成的矩阵。

03 实验再现

根据LLE的算法原理，笔者编写并执行了LLE程序，原始数据及得到的实验结果分别如下图所示。

04 思考与总结

局部线性嵌入算法以局部线性、全局非线性的策略对待原始高维数据，从而在保持原始数据拓扑结构的基础上进行数据降维。该算法充分利用了矩阵理论的相关知识，将第一、二次优化问题分别转换成了二次型、特征值求解问题，具有较强的启发性和科学论证的严谨性。

求低维数据时添加的两个约束条件，其一表示低维数据的协方差矩阵之和等于单位矩阵的n倍，其二表示所有低维数据的均值为0。另外，由于该协方差约束可以进行如下展开：

注：假设y1=[y11,y12]T.

因此，y中的行向量均位于半径为sqrt(n)的n维单位球上，且两两正交。

05 参考文献

[1] Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embed- ding. Science, 290(5500), 2323-6.

[2] WOJCIECHCHOJNACKI, & Brooks, M. J. (2009). A note on the locally linear embedding algorith- m. International Journal of Pattern Recognition & Artificial Intelligence, 23(8), 1739-1752.

[3] Saul, L. K., & Roweis, S. T. (2001). An introduction to locally linear embedding. Journal of Machine Learning Research, 7.

[4] 吴晓婷, 闫德勤. 数据降维方法分析与研究[J]. 计算机应用研究, 2009, 26(8):2832-2835.

[5] 王靖. 流形学习的理论与方法研究[D]. 浙江大学, 2006.

[6] 马宇. 基于高维空间的非线性降维的局部线性嵌入LLE方法[D]. 西南交通大学, 2017.