数据降维

Posted on

数据降维

在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”（curse of dimensionality）。
缓解维数灾难的一个重要途径就是降维（dimension reduction），也成为“维数约简”，即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”（subspace），在这个子空间中样本密度大幅提高，距离计算也变得更为容易。
数据降维的原因：很多时候，人们观测或收集到的数据样本虽然是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入”（embedding），原始高维空间中的样本点，在这个低维嵌入子空间中更容易学习。

1. MDS算法

若要求原始空间中样本之间的距离在低维空间中得以保持，即得到“多维缩放”（Multiple Dimensional Scaling，MDS）这种经典的降维方法。
假设\(m\)个样本在原始空间中的距离矩阵为\(\mathbf{D} \in \mathbf{R}^{m \times m}\)，其第\(i\)行\(j\)列的元素\(dist_{ij}\)为样本\(\pmb{x}_i\)到\(\pmb{x}_j\)的距离，我们的目标是获得样本在\(d'\)维空间的表示\(\mathbf{Z} \in \mathbf{R}^{d' \times m},d' < d\)，且任意两个样本在\(d'\)维空间中的欧氏距离等于原始空间中的距离，即\(||\pmb{z}_i - \pmb{z}_j|| = dist_{ij}\)。
令\(\mathbf{B} = \mathbf{Z}^T \mathbf{Z} \in \mathbf{R}^{m \times m}\)，其中\(\mathbf{B}\)为降维后样本的内积矩阵，\(b_{ij} = \pmb{z}_i^T \pmb{z}_j\)，有 \[\begin{align} dist_{ij}^2 &= ||\pmb{z}_i||^2 + ||\pmb{z}_j||^2 - 2 \pmb{z}_i^T \pmb{z}_j \nonumber \\ &= b_{ii} + b_{jj} - 2 b_{ij} \tag{10.3} \end{align}\] 为了便于讨论，令降维后的样本\(\pmb{z}\)被中心化，即\(\sum_{i=1}^m \pmb{z}_i = 0\)。显然，矩阵\(\mathbf{B}\)的行与列之和均为0，即\(\sum_{i=1}^m b_{ij} = \sum_{j=1}^m b_{ij} = 0\)，易知 \[\begin{equation} \sum_{i=1}^m dist_{ij}^2 = tr(\mathbf{B}) + mb_{jj} \nonumber \\ \sum_{j=1}^m dist_{ij}^2 = tr(\mathbf{B}) + mb_{ii} \nonumber \\ \sum_{i=1}^m \sum_{j=1}^m dist_{ij}^2 = 2m \times tr(\mathbf{B}) \nonumber \end{equation}\] 其中\(tr(·)\)表示矩阵的迹，\(tr(\mathbf{B}) = \sum_{i=1}^m ||\pmb{z}_i||^2\)，令 \[\begin{align} dist_{i·}^2 &= \frac{1}{m} \sum_{j=1}^m dist_{ij}^2 \nonumber \\ dist_{·j}^2 &= \frac{1}{m} \sum_{i=1}^m dist_{ij}^2 \nonumber \\ dist_{··}^2 &= \frac{1}{m^2} \sum_{i=1}^m \sum_{j=1}^m dist_{ij}^2 \nonumber \end{align}\] 由上述公式可推得 \[b_{ij} = - \frac{1}{2} (dist_{ij}^2 - dist_{i·}^2 - dist_{·j}^2 + dist_{··}^2)\] 由此即可通过降维前后保持不变的距离矩阵\(\mathbf{D}\)求取内积矩阵\(\mathbf{B}\)。
对矩阵\(\mathbf{B}\)做特征分解（eigenvalue decomposition），\(\mathbf{B} = \mathbf{V} \mathbf{\Lambda} \mathbf{V}^T\)，其中\(\mathbf{\Lambda} = diag(\lambda_1, \lambda_2, \cdots, \lambda_d)\)为特征值构成的对角矩阵，\(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_d\)，\(\mathbf{V}\)为特征向量矩阵，假定其中有\(d^*\)个非零特征值，它们构成对角矩阵\(\mathbf{\Lambda}_{*} = diag(\lambda_1, \lambda_2, \cdots, \lambda_{d^*})\)，令\(\mathbf{V}_*\)表示相应的特征向量矩阵，则\(\mathbf{Z}\)可表达为 \[\mathbf{Z} = \mathbf{\Lambda}_*^{1/2} \mathbf{V}_*^T \in \mathbf{R}^{d^* \times m}\] 在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可取\(d' \ll d\)个最大特征值构成对角矩阵\(\tilde{\mathbf{\Lambda}} = diag(\lambda_1, \lambda_2, \cdots, \lambda_{d'})\)，令\(\tilde{\mathbf{V}}\)表示相应的特征向量矩阵，则\(\mathbf{Z}\)可表达为 \[\mathbf{Z} = \tilde{\mathbf{\Lambda}}^{1/2} \tilde{\mathbf{V}}^T \in \mathbf{R}^{d' \times m}\]

MDS算法描述如下：

一般来说，想要获得低维子空间，最简单的是对原始高维空间进行线性变换。
给定\(d\)维空间中的样本\(\mathbf{X} = (\pmb{x}_1, \pmb{x}_2, \cdots, \pmb{x}_m) \in \mathbf{R}^{d \times m}\)，变换之后得到\(d' \leq d\)维空间中的样本 \[\mathbf{Z} = \mathbf{W}^T \mathbf{X} \tag{10.13} \] 其中\(\mathbf{W} \in \mathbf{R}^{d \times d'}\)是变换矩阵，\(\mathbf{Z} \in \mathbf{R}^{d' \times m}\)是样本在新空间中的表达。
变换矩阵\(\mathbf{W}\)可视为\(d'\)个\(d\)维基向量，\(\pmb{z}_i = \mathbf{W}^T \pmb{x}_i\)是第\(i\)个样本与这\(d'\)个基向量分别做内积而得到的\(d'\)维属性向量。换言之，\(\pmb{z}_i\)是原属性向量\(\pmb{x}_i\)在新坐标系\(\{\pmb{w}_1, \pmb{w}_2, \cdots, \pmb{w}_{d'}\}\)中的坐标向量，若\(\pmb{w}_i\)与\(\pmb{w}_j ( i \neq j)\)正交，则新坐标系是一个正交坐标系，此时\(\mathbf{W}\)为正交变换。显然，新空间中的属性是原空间中属性的线性组合。
基于线性变换来进行降维的方法称为线性降维方法，它们都符合式（10.13）的基本形式，不同之处是对低维子空间的性质有不同的要求，相当于对\(\mathbf{W}\)施加了不同的约束，若要求低维子空间对样本具有最大可分性，则将得到一种极为常用的线性降维方法。
对降维效果的评估，通常是比较降维前后学习器的性能，若性能有所提高则认为降维起到了作用，若将维数降至二维或三维，则可通过可视化技术来直观地判断降维效果。

2. PCA

主成分分析（Principal Component Analysis，PCA）是最常用的一种降维方法。降维是希望在损失尽量少的信息的情况下降低样本的维度，降维后的样本应尽可能的还原原数据样本的分布特征。
首先思考这样一个问题：对于正交属性空间中的样本点，如何用一个超平面（直线的高维推广）对所有样本进行恰当的表达？
若存在这样的超平面，那么它大概应具有这样的性质：

  • 最近重构性：样本点到这个超平面的距离都足够近；
  • 最大可分性：样本点在这个超平面上的投影能尽可能分开。

基于最近重构性和最大可分性，能分别得到PCA的两种等价推导。

（1）最近重构性推导
假设数据样本进行了中心化，即\(\sum_{i} \pmb{x}_i = 0\)；再假定投影变换后得到的新坐标系为\(\{\pmb{w}_1, \pmb{w}_2, \cdots, \pmb{w}_d\}\)，其中\(\pmb{w}_i\)是标准正交基向量，\(||\pmb{w}_i||_2 = 1\)，\(\pmb{w}_i^T \pmb{w}_j = 0 (i \neq j)\)。若丢弃新坐标系中的部分坐标，即将维度降低到\(d' < d\)，则样本点\(\pmb{x}_i\)在低维坐标系中的投影是\(\pmb{z}_i = (z_{i1}, z_{i2}, \cdots, z_{id'})\)，其中\(z_{ij} = \pmb{w}_j^T \pmb{w}_i\)是\(\pmb{x}_i\)在低维坐标系下第\(j\)维的坐标。若基于\(\pmb{z}_i\)来重构\(\pmb{x}_i\)，则会得到\(\hat{\pmb{x}}_i = \sum_{j=1}^{d'} z_{ij} \pmb{w}_j\)。
考虑整个训练集，原样本点\(\pmb{x}_i\)与基于投影重构的样本点\(\hat{\pmb{x}}_i\)之间的距离为 \[\begin{align} \sum_{i=1}^m ||\sum_{j=1}^{d'} x_{ij} \pmb{w}_j - \pmb{x}_i||_2^2 &= \sum_{i=1}^m \pmb{z}_i^T \pmb{z}_i - 2\sum_{i=1}^m \pmb{z}_i^T \mathbf{W}^T \pmb{x}_i + const \nonumber \\ & \propto -tr(\mathbf{W}^T (\sum_{i=1}^m \pmb{x}_i \pmb{x}_i^T) \mathbf{W}) \nonumber \end{align}\] 其中\(\mathbf{W} = (\pmb{w}_1,\pmb{w}_2,\cdots,\pmb{w}_d)\)。根据最近重构性，上式应该被最小化，考虑到\(\pmb{w}_j\)是标准正交基，\(\sum_{i} \pmb{x}_i \pmb{x}_i^T\)是协方差矩阵，有 \[\begin{align} & \min_{\mathbf{W}} \quad - tr(\mathbf{W}^T \mathbf{X} \mathbf{X}^T \mathbf{W}) \nonumber \\ & s.t. \qquad \mathbf{W}^T \mathbf{W} = 1 \nonumber \end{align}\] 这是主成分分析从最近重构性角度思考需要优化的目标。

（2）最大可分性推导
样本点\(\pmb{x}_i\)在新空间超平面上的投影是\(\mathbf{W}^T \pmb{x}_i\)，若所有样本点的投影能尽可能分开，则应该使投影后样本点的方差最大化。在PCA中，我们可以认为数据的方差越大，包含的信息量越多（这句话其实并不严谨，因为根据信息论的知识，信息量的多少和数据的分布有关，而和数据量级没有关系），也就是在降维过程中损失的信息量越少。

上图中，在对图中数据进行降维时，\(u_1\)是投影的最佳方向，数据越分散，越有可能发现数据分布的潜在规律，而\(u_2\)方向可能只是因为数据中存在噪声而表现出的同一性。

首先需要对数据进行标准化：

  1. 计算\(\pmb{\mu} = \frac{1}{m} \sum_{i=1}^m \pmb{x}^{(i)}\)；
  2. 将每个\(\pmb{x}^{(i)}\)替换为\(\pmb{x}^{(i)} - \pmb{\mu}\)；
  3. 计算\(\sigma_j^2 = \frac{1}{m} \sum_i (x_j^{(i)})^2\)；
  4. 将每个\(x_j^{(i)}\)替换为\(\frac{x_j^{(i)}}{\sigma_j}\)。

如果令投影方向的向量\(\pmb{u}\)的模\(||\pmb{u}|| = 1\)，那么样本点\(\pmb{x}^{(i)}\)在\(\pmb{u}\)的投影为\(\pmb{x}^{(i)^T} \pmb{u}\)。
目标函数为： \[\begin{align} & \max_{\pmb{u}} \quad \frac{1}{m} \sum_{i=1}^m (\pmb{x}^{(i)^T} \pmb{u})^2 \nonumber \\ & s.t. \qquad ||\pmb{u}|| \nonumber \end{align}\]

其中目标公式可推导为： \[\begin{align} \frac{1}{m} \sum_{i=1}^m (\pmb{x}^{(i)^T} \pmb{u})^2 &= \frac{1}{m} \sum_{i=1}^m (\pmb{u}^T \pmb{x}^{(i)})(\pmb{x}^{(i)^T} \pmb{u}) \nonumber \\ & = \pmb{u}^T [\frac{1}{m} \sum_{i=1}^m \pmb{x}^{(i)} \pmb{x}^{(i)^T}] \pmb{u} \nonumber \\ & = \pmb{u}^T \pmb{\Sigma} \pmb{u} \nonumber \end{align}\]

其中\(\pmb{\Sigma}\)为样本数据的协方差矩阵。
构造拉格朗日函数： \[L(\pmb{u}, \lambda) = \pmb{u}^T \pmb{\Sigma} \pmb{u} - \lambda (\pmb{u}^T \pmb{u} - 1)\] 对\(\pmb{u}\)求偏导并令其为零得到 \[\begin{equation} \nabla_{\pmb{u}} L = \pmb{\Sigma} \pmb{u} - \lambda \pmb{u} = 0 \nonumber \\ \pmb{\Sigma} \pmb{u} = \lambda \pmb{u} \end{equation}\] 有上式可以看出，\(\lambda\)为协方差矩阵\(\pmb{\Sigma}\)的特征值，\(\pmb{u}\)为\(\pmb{\Sigma}\)的特征向量。
如果要将数据投影到\(k\)维子空间，应选取前\(k\)大的特征值对应的特征向量构成\(\pmb{u}\)。

实际上，从最近重构性和最大可分性两种角度得到的目标函数相同。

实际应用中常常通过对\(\mathbf{X}\)进行奇异值分解来代替协方差矩阵的特征值分解。

降维后低维空间的维度\(d'\)通常需要事先指定，或者通过在\(d'\)值不同的低维空间中对k近邻分类器（或者其他开销较小的学习器）进行交叉验证来选取较好的\(d'\)值。对PCA，还可以从重构的角度设置一个重构阈值，例如\(t = 95\%\)，然后选取使下式成立的最小\(d'\)值： \[\frac{\sum_{i=1}^{d'} \lambda_i}{\sum_{i=1}^d \lambda} \geq t\]

3. 核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，但是在实际应用中，可能需要非线性映射才能找到恰当的低维嵌入。
下图中，样本点从二维空间中的矩形区域采样后以S曲面嵌入到三维空间，若直接使用线性降维方法对三维空间观察到的样本点进行降维，则会丢失原本的低维结构，为了对“原本采样的”低维空间与降维后的低维空间加以区别，称前者为“本真”低维空间。

非线性降维的一种常用方法，是基于核技巧对线性降维方法进行“核化”，下面将以核主成分分析（Kernelized PCA，KPCA）进行说明。

假设将在高维特征数据中把数据投影到由\(\mathbf{W} = (\pmb{w}_1, \pmb{w}_2, \cdots, \pmb{w}_d)\)确定的超平面上，则对于\(\pmb{w}_j\)，有 \[(\sum_{i=1}^m \pmb{z}_i \pmb{z}_i^T) \pmb{w}_j = \lambda_j \pmb{w}_j\] 其中\(\pmb{z}_i\)是样本点\(\pmb{x}_i\)在高维特征空间中的像，所以有 \[\pmb{w}_j = \frac{1}{\lambda_j} (\sum_{i=1}^m \pmb{z}_i \pmb{z}_i^T) \pmb{w}_j = \sum_{i=1}^m \pmb{z}_i \frac{\pmb{z}_i^T \pmb{w}_j}{\lambda_j} = \sum_{i=1}^m \pmb{z}_i \alpha_i^j\] 其中\(\alpha_i^j = \frac{\pmb{z}_i^T \pmb{w}_j}{\lambda_j}\)是\(\pmb{\alpha}_i\)的第\(j\)个分量，假定\(\pmb{z}_i\)是由原始属性空间中的样本点\(\pmb{x}_i\)通过映射\(\phi\)产生，即\(\pmb{z}_i = \phi(\pmb{x}_i),i=1,2,\cdots,m\)。若\(\phi\)能被显式表达出来，则通过它将样本映射到高维特征空间，再在特征空间中实施PCA即可。公式变换为 \[(\sum_{i=1}^m \phi(\pmb{x}_i) \phi(\pmb{x}_i)^T) \pmb{w}_j = \lambda_j \pmb{w}_j \tag{1}\] 同时有 \[\pmb{w}_j = \sum_{i=1}^m \phi(\pmb{x}_i) \alpha_i^j \tag{2}\] 一般情况下，不清楚\(\phi\)的具体形式，于是引入核函数 \[\kappa(\pmb{x}_i, \pmb{x}_j) = \phi(\pmb{x}_i)^T \phi(\pmb{x}_j) \tag{3}\] 将上述式（2）、（3）带入式（1）中化简，令\(\mathbf{Z} = (\phi(\pmb{x}_1),\phi(\pmb{x}_2),\cdots,\phi(\pmb{x}_m))\)，得到 \[\begin{equation} (\sum_{i=1}^m \phi(\pmb{x}_i) \phi(\pmb{x}_i)^T) \pmb{w}_j = \lambda_j \pmb{w}_j \nonumber \\ (\sum_{i=1}^m \phi(\pmb{x}_i) \phi(\pmb{x}_i)^T) \sum_{i=1}^m \phi(\pmb{x}_i) \alpha_i^j = \lambda_j \sum_{i=1}^m \phi(\pmb{x}_i) \alpha_i^j \nonumber \\ \mathbf{Z} \mathbf{Z}^T (\mathbf{Z}· \pmb{\alpha}^j) = \lambda_j (\mathbf{Z}· \pmb{\alpha}^j) \nonumber \\ \mathbf{Z} \mathbf{K} \pmb{\alpha}^j = \mathbf{Z} (\lambda_j · \pmb{\alpha}^j) \nonumber \\ \mathbf{K} \pmb{\alpha}^j = \lambda_j · \pmb{\alpha}^j \end{equation}\]

其中\(\mathbf{K}\)为\(\kappa\)对应的核矩阵，\((\mathbf{K})_{ij} = \kappa(\pmb{x}_i, \pmb{x}_j), \pmb{\alpha}^j = (\alpha_1^j, \alpha_2^j, \cdots, \alpha_m^j)\)。显然，上式是特征值分解问题，取\(\mathbf{K}\)最大的\(d'\)个特征值对应的特征向量即可。
对新样本\(\pmb{x}\)，其投影后的第\(j(j=1,2,\cdots,d')\)维坐标为 \[z_j = \pmb{w}_j^T \phi(\pmb{x}) = \sum_{i=1}^m \alpha_i^j \phi(\pmb{x}_i)^T \phi(\pmb{x}) = \sum_{i=1}^m \alpha_i^j \kappa(\pmb{x}_i, \pmb{x})\] 其中\(\pmb{\alpha}_i\)经过规范化。从上式可以看出，为了获得投影后的坐标，KPCA需对所有样本进行求和，因此它的计算开销较大。

4. 流形学习

流形学习（manifold learning）是一类借鉴拓扑流形概念的降维方法。“流形”是在局部与欧氏空间同胚的空间，即在局部具有欧氏空间的性质，能用欧氏距离来进行距离的计算。
对于降维方法的启发：若低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧氏空间的性质。因此，可以容易地在局部建立降维映射关系，然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示，因此流形学习也可被用于可视化。
下面将介绍两种著名的流形学习方法。

4.1. 等度量映射

等度量映射（Isometric Mapping，Isomap）的基本出发点：低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上式不可达的。
如下图所示，低维嵌入流形上的两点间的距离是“测地线”（geodesic）距离：如图10.7（a）中的红色曲线是距离最短的路径，即S曲面上的测地线，测地线距离是两点之间的本真距离。显然，直接在高维空间中计算直线距离是不恰当的。

此时可以利用流形在局部上与欧氏空间同胚的性质，对每个点基于欧氏距离找出其近邻点，然后建立一个近邻连接图，图中近邻点之间存在连接，而非近邻点之间不存在连接。于是，计算两点之间测地线距离的问题就转变为计算近邻连接图上两点之间的最短路径问题。从图10.7（b）中可以看出，基于近邻距离逼近能获得低维流形上测地线距离很好的近似。

在紧邻连接图上计算两点间的最短路径，可采用Dijkstra算法或Floyd算法，在得到任意两点的距离之后，可通过之前介绍的MDS算法来获得样本点在低维空间中的坐标。

Isomap算法如下：

需要注意的是，Isomap算法仅是得到训练样本在低维空间的坐标，对于新样本，将其映射到低维空间中的常用方法是将训练样本的高维坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。

对近邻图的构建通常有两种做法：

  1. 一种是指定近邻点个数，例如欧氏距离最近的k个点作为近邻点，这样得到的近邻图称为k近邻图；
  2. 另一种是指定距离阈值\(\epsilon\),距离小于\(\epsilon\)的点被认为是近邻点，这样得到的近邻图称为\(\epsilon\)近邻图。

两种方式均有不足：

  • 若紧邻范围指定的较大，则距离很远的点可能被误认为近邻，这样就会出现“短路”的问题；
  • 近邻范围指定的较小，则图中有些区域可能与其他区域不存在连接，这样就会出现“断路”问题。

短路与断路都会给后续的最短路径计算造成误导。

4.2. 局部线性嵌入

与Isomap试图保持近邻样本之间的距离不同，局部线性嵌入（Locally Linear Embedding，LLE）试图保持邻域内样本之间的线性关系。

如上图所示，假定样本点\(\pmb{x}_i\)的坐标能通过它的邻域样本\(\pmb{x}_j,\pmb{x}_k, \pmb{x}_l\)的坐标通过线性组合而重构出来，即 \[\pmb{x}_i = w_{ij} \pmb{x}_j + w_{ik} \pmb{x}_k + w_{il} \pmb{x}_l\]

LLE希望上式的关系在低维空间中得以保持。

LLE先为每个样本\(\pmb{x}_i\)找到其近邻下标集合\(Q_i\)，然后计算出基于\(Q_i\)中的样本点对\(\pmb{x}_i\)进行线性重构的系数\(\pmb{w}_i\)： \[\begin{align} & \min_{\pmb{w}_1, \pmb{w}_2, \cdots, \pmb{w}_m} \quad \sum_{i=1}^m ||\pmb{x}_i - \sum_{j \in Q_i} w_{ij} \pmb{x}_j||_2^2 \nonumber \\ & \quad s.t. \qquad \sum_{j \in Q_i} w_{ij} = 1 \nonumber \end{align} \tag{4}\]

其中\(\pmb{x}_i\)和\(\pmb{x}_j\)均已知，令\(C_{jk} = (\pmb{x}_i - \pmb{x}_j)^T (\pmb{x}_i - \pmb{x}_k)\)，\(w_{ij}\)有闭式解： \[w_{ij} = \frac{\sum_{k \in Q_i} C_{jk}^{-1}}{\sum_{l,s \in Q_i} C_{ls}^{-1}}\]

推导：
为了表示方便，对于每个样本点\(\pmb{x}\)，其邻近点集为\(\{\pmb{Z}_{i1},\pmb{Z}_{i2},\cdots,\pmb{Z}_{iK}\}\)。
接下来计算每个样本点的局部线性重构矩阵\(W_{ij}\)，目标函数可写为 \[\begin{align} & \arg \min_{\pmb{W}} \quad \sum_{i=1}^m ||\pmb{x}_i - \sum_{j=1}^K W_{ij} \pmb{Z}_{ij}||^2 \nonumber \\ & s.t. \qquad \quad \sum_{j=1}^K W_{ij} = 1, \quad i=1,2,\cdots,m \nonumber \end{align}\] \(W_{ij}\)为样本点\(\pmb{x}_i\)对应的第\(j\)个重构系数。
观察单个样本点的目标函数： \[\begin{align} \varepsilon &= ||\pmb{x}_i - \sum_{j=1}^K W_{ij} \pmb{Z}_{ij}||^2 = ||\sum_{j=1}^K (W_{ij} \pmb{x}_i - W_{ij} \pmb{Z}_{ij})||^2 \nonumber \\ &= ||\sum_{j=1}^K W_{ij} (\pmb{x}_i - \pmb{Z}_{ij})||^2 = ||\pmb{Q}_i \pmb{W}_i||^2 \nonumber \end{align}\] 上式中\(\pmb{Q}_i = [\pmb{x}_i - \pmb{Z}_{i1}, \pmb{x}_i - \pmb{Z}_{i2}, \cdots, \pmb{x}_i - \pmb{Z}_{iK}]\)，重构系数向量\(\pmb{W}_i = [W_{i1},W_{i2},\cdots,W_{iK}]\)，为使\(\varepsilon\)最小，可以用拉格朗日乘数法求解\(\pmb{W}_i\)的值： \[\begin{align} \mathscr{L}_i &= ||\pmb{x}_i - \sum_{j=1}^K W_{ij} \pmb{Z}_{ij}||^2 - \lambda_i (\sum_{j=1}^K W_{ij} - 1) \nonumber \\ &= ||\pmb{Q}_i \pmb{W}_i||^2 - \lambda_i(\pmb{1}^T \pmb{W}_i - 1) \nonumber \\ &= \pmb{W}_i^T \pmb{Q}_i^T \pmb{Q}_i \pmb{W}_i - \lambda_i(\pmb{1}^T \pmb{W}_i - 1) \nonumber \end{align}\] 其中\(\pmb{1} = [1,1,\cdots,1]\)，长度为\(K\)。
将\(\mathscr{L}_i\)对\(\pmb{W}_i\)求偏导： \[\frac{\partial \mathscr{L}_i}{\partial \pmb{W}_i} = \pmb{Q}_i^T \pmb{Q}_i \pmb{W}_i - \lambda_i \pmb{1} = 0\] 可推出 \[\pmb{W}_i = \lambda_i \pmb{C}_i^{-1} \pmb{1}\] 式中\(\pmb{C}_i = \pmb{Q}_i^T \pmb{Q}_i\)，另外有\(\sum_{j=1}^K W_{ij} = \pmb{1}^T \pmb{W}_i = 1\)，则有 \[\pmb{1}^T \lambda_i \pmb{C}_i^{-1} \pmb{1} = 1 \Rightarrow \lambda_i = (\pmb{1}^T \pmb{C}_i^{-1} \pmb{1})^{-1}\] 最终 \[\begin{align} \pmb{W}_i &= \lambda_i \pmb{C}_i^{-1} \pmb{1} = (\pmb{1}^T \pmb{C}_i^{-1} \pmb{1})^{-1} \pmb{C}_i^{-1} \pmb{1} \nonumber \\ &= \frac{\pmb{C}_i^{-1} \pmb{1}}{\pmb{1}^T \pmb{C}_i^{-1} \pmb{1}} \nonumber \end{align}\] 若令\(C_{jk} = (\pmb{x}_i - \pmb{x}_j)^T (\pmb{x}_i - \pmb{x}_k)\)，有 \[\frac{\pmb{C}_i^{-1} \pmb{1}}{\pmb{1}^T \pmb{C}_i^{-1} \pmb{1}} = \frac{\sum_{k \in Q_i} C_{jk}^{-1}}{\sum_{l,s \in Q_i} C_{ls}^{-1}} \]

LLE在低维空间中保持\(\pmb{w}_i\)不变，于是\(\pmb{x}_i\)对应的低维空间坐标\(\pmb{z}_i\)可通过下式求解： \[\min_{\pmb{z}_1,\pmb{z}_2,\cdots,\pmb{z}_m} \quad \sum_{i=1}^m ||\pmb{z}_i - \sum_{j \in Q_i} w_{ij} \pmb{z}_j||_2^2\] 上式需要确定\(\pmb{x}_i\)对应的低维空间坐标\(\pmb{z}_i\)。

令\(\pmb{Z} = (\pmb{z}_1, \pmb{z}_2, \cdots, \pmb{z}_m) \in \mathbf{R}^{d' \times m},\quad (\mathbf{W})_{ij} = w_{ij}\)，并且令\(\mathbf{M} = (\mathbf{I} - \mathbf{W})^T(\mathbf{I} - \mathbf{W})\)，则目标公式可写为： \[\begin{align} & \min_{\mathbf{Z}} \quad tr(\mathbf{Z} \mathbf{M} \mathbf{Z}^T) \nonumber \\ & s.t. \qquad \mathbf{Z} \mathbf{Z}^T = \mathbf{I} \nonumber \end{align}\] 可通过特征值分解求解：\(\mathbf{M}\)最小的\(d'\)个特征值对应的特征向量组成的矩阵即为\(\mathbf{Z}^T\)。

详细推导

LLE算法如下：