本文主要介绍各种与降维任务有关的算法。

0 降维与嵌入概述

样本的特征数称为维数（Dimensionality）。高维情形下常发生称为维数灾难（Curse of Dimensionality）的严重问题，具体表现在：①由于难以维持训练样本的采样密度足够大的密采样（Dense Sample），数据样本变得非常稀疏；②训练样本的稀疏使得其代表总体分布的能力大大减弱，从而削减了学习器的泛化能力；③计算距离变得十分复杂，甚至连计算内积都不再容易（因此SVM必须引入核函数实现“低维计算，高维表现”）。

缓解维数灾难的一个重要途径就是降维（Dimension Reduction，维度约简），即通过某种数学变换将原始高维空间转变到一个低维的子空间（Subspace）。在这个子空间中，样本密度将大幅提高，同时距离计算也变得容易。

降维这种做法的合理性解释：在很多任务中，尽管获取到的数据样本是高维的，但与学习任务密切相关的可能仅是某个低维分布，即高维空间中的一个低维嵌入（Embedding）。例如，很多时候数据属性中存在噪声属性、相似属性或冗余属性等，对高维数据进行降维能在一定程度上实现提炼低维优质属性或降噪的效果。

---

1 k-近邻

k-近邻（k-Nearest Neighbor，kNN）学习是一种经典的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其距离最近的k个训练样本，然后给基于这k个近邻点的信息（真实类标记或实值）来进行预测。通常在分类任务采用投票法，在回归任务中采用平均法（见前述“结合策略”一节），亦可基于距离远近进行加权平均或加权投票，距离越近权重越大。

与前述的所有算法不同，kNN没有显式的训练过程，是一种典型的懒惰学习（Lazy Learning）算法。在训练阶段仅将样本保存起来，训练时间开销为0；当有新样本需要预测时才进行处理。相应地，前述的那些在训练阶段就对样本进行学习处理的方法属于急切学习（Eager Learning）。

kNN分类器示意图如下所示：

可见，kNN算法的核心在于参数k的取值与距离度量方式的选择。k值太小，模型容易受到噪声数据的干扰，从而过拟合；k值太大，模型的预测能力会大大减弱，即欠拟合。可通过交叉验证法来选取一个适当的k值。

一般根据样本的特性来选择合适的距离度量函数，同时应对数据进行去量纲/归一化处理来消除大量纲属性的影响。

---

2 多维缩放

无论是用核函数升维还是对数据降维，通常都希望原始空间样本点之间的距离在新空间中基本保持不变，从而不会使得原始空间样本之间的关系及总体分布发生较大的改变。由此可得多维缩放（Multiple Dimensional Scaling，MDS）这种经典的降维算法。MDS要求原始空间样本之间的距离在降维后的低维空间中得以保持。

假定m个样本在d维原始空间的距离矩阵为\mathbf{D}\in \mathbb{R}^{m\times m}，其第i行j列的元素dist_{ij}为样本\mathbf{x}_i到\mathbf{x}_j的距离。目标是获得样本在d'维空间的表示\mathbf{Z}\in \mathbb{R}^{d'\times m},\ d'\le d，且任意两个样本在d'维空间中的欧氏距离等于原始空间中的距离，即\left\| \mathbf{z}_i -\mathbf{z}_j\right\|=dist_{ij}。

令降维后样本的内积矩阵\mathbf{B}=\mathbf{Z}^\top \mathbf{Z}\in \mathbb{R}^{m\times m},\ b_{ij}=\mathbf{z}_i^\top \mathbf{z}_j，则可推得以下等式

\begin{aligned}
dist_{ij}^2 &= \left\| \mathbf{z}_i \right\|^2 + \left\| \mathbf{z}_j \right\|^2 - 2\mathbf{z}_i^\top \mathbf{z}_j\\
 &= b_{ii}+b_{jj} -2b_{ij}
\end{aligned}

令降维后的样本坐标矩阵\mathbf{Z}被中心化（将每个样本向量减去整个样本集的均值向量），即\sum\limits_{i=1}^m \mathbf{z}_i=\mathbf{0}。显然，矩阵\mathbf{B}的行与列之和均为0（因为提取公因子后都有一项为所有样本向量的和向量），即\sum\limits_{i=1}^m b_{ij}=\sum\limits_{j=1}^m b_{ij}=0。易知

\begin{aligned}
\sum\limits_{i=1}^m dist_{ij}^2 &=\text{tr}(\mathbf{B})+m\cdot b_{jj}\\
\sum\limits_{j=1}^m dist_{ij}^2 &= \text{tr}(\mathbf{B}) + m\cdot b_{ii}\\
\sum\limits_{i=1}^m\sum\limits_{j=1}^m dist_{ij}^2 &=2m \text{tr}(\mathbf{B})
\end{aligned}

其中\text{tr}(\cdot)是矩阵的迹（Trace），易知\text{tr}(\mathbf{B})=\sum\limits_{i=1}^m \left\| \mathbf{z}_i \right\|^2。据此，令

\begin{aligned}
dist_{i\cdot}^2 &=\dfrac{1}{m}\sum\limits_{j=1}^m dist_{ij}^2\\
dist_{\cdot j}^2 &=\dfrac{1}{m}\sum\limits_{i=1}^m dist_{ij}^2\\
dist_{\cdot \cdot}^2 &=\dfrac{1}{m^2}\sum\limits_{i=1}^m \sum\limits_{j=1}^m dist_{ij}^2
\end{aligned}

将上述全部式子代入最初推得的等式并整理，即可实现通过降维前后保持不变的距离矩阵\mathbf{D}求取内积矩阵\mathbf{B}，元素计算式如下

\begin{aligned}
b_{ij}=-\frac{1}{2}(dist_{ij}^2-dist_{i\cdot}^2-dist_{\cdot j}^2+dist_{\cdot \cdot}^2)
\end{aligned}

对\mathbf{B}做特征值分解（Eigenvalue Decomposition），\mathbf{B}=\mathbf{V}\mathbf{\Lambda}\mathbf{V}^\top,\ \mathbf{\Lambda}=\text{diag}(\lambda_1,\lambda_2,\dots,\lambda_d),\ \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_d，\mathbf{V}为特征向量矩阵。假定共有d^*个非零特征值，其构成\mathbf{\Lambda}_{*}=\text{diag}(\lambda_1,\lambda_2,\dots,\lambda_{d^*})，令\mathbf{V}_{*}为相应的特征向量矩阵，则可得\mathbf{Z}的表示

\begin{aligned}
\mathbf{Z}=\mathbf{\Lambda}_{*}^{1/2}\mathbf{V}_{*}^\top \in \mathbb{R}^{d'\times m}
\end{aligned}

在实际应用中，为了有效降维，往往无需降维后的距离与原始空间中的距离严格相等，此时可取d' \ll d个最大特征值构成\tilde \mathbf{\Lambda}=\text{diag}(\lambda_1,\lambda_2,\dots,\lambda_{d'})，令\tilde \mathbf{V}为相应的特征向量矩阵，则可得\mathbf{Z}的最终表示

\begin{aligned}
\mathbf{Z}=\tilde \mathbf{\Lambda}^{1/2} \tilde \mathbf{V}^\top \in \mathbb{R}^{d'\times m}
\end{aligned}

MDS算法流程如下所示：

• 输入：距离矩阵\mathbf{D}\in \mathbb{R}^{m\times m}，其元素dist_{ij}为样本\mathbf{x}_i到\mathbf{x}_j的距离；低维空间维数d'
• 过程：
  • 计算dist_{i\cdot}^2,dist_{\cdot j}^2,dist_{\cdot \cdot}^2
  • 计算矩阵\mathbf{B}
  • 对矩阵\mathbf{B}做特征值分解
  • 取\tilde \mathbf{\Lambda}为d'个最大特征值所构成的对角矩阵，\tilde \mathbf{V}为相应的特征向量矩阵
• 输出：矩阵\tilde \mathbf{V} \tilde \mathbf{\Lambda}^{1/2} \in \mathbb{R}^{m\times d'}，每行为1个样本的低维坐标

---

3 主成分分析

一般情况下，要获得低维子空间，只需对原始高维空间进行线性变换。给定d维空间中的样本\mathbf{X}=(\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m)\in \mathbb{R}^{d\times m}，变换矩阵\mathbf{W}=(\mathbf{w}_1,\mathbf{w}_2,\dots,\mathbf{w}_{d'})\in \mathbb{R}^{d\times d'}包含d'个d维基向量，则变换之后可得到d' \ll d维空间中的样本表达通式为\mathbf{Z}=\mathbf{W}^\top \mathbf{X} \in \mathbb{R}^{d'\times m}。这类基于线性变换的降维方法统称为线性降维。

主成分分析（Principal Component Analysis，PCA）是最常用的一种线性降维方法，通过一个线性变换将原始空间中的样本投影到新的低维空间中。PCA采用一组新的基来表示样本点，其中每个基向量都是原来基向量的线性组合，通过使用尽可能少的新基向量来表出样本，从而达到降维的目的。

对于正交属性空间中的样本点，若想用一个超平面对所有样本进行恰当的表达，则该超平面应具有以下两种性质：

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

巧合的是，尽管可以基于最近重构性或最大可分性从不同的出发点来定义优化问题中的目标函数，但最终这两种特性得到了完全相同的优化问题。

首先从最近重构性开始推导：假定数据样本进行了中心化，即\sum\limits_{i}\mathbf{x}_i=\mathbf{0}；假定投影变换后得到的新坐标系为\{\mathbf{w}_1,\mathbf{w}_2,\dots,\mathbf{w}_d\}，其中\mathbf{w}_i是标准正交基向量，\left\| \mathbf{w}_i \right\|_2=1,\ \mathbf{w}_i^\top \mathbf{w}_j=0\ (i \ne j)。若丢弃新坐标系中的部分坐标，即将维度降低到d' \lt d，则样本点\mathbf{x}_i在低维坐标系中的投影为\mathbf{z}_i=(z_{i1};z_{i2};\dots;z_{id'})，其中z_{ij}=\mathbf{w}_j^\top \mathbf{x}_i是\mathbf{x}_i在低维坐标系下第j维的坐标。若基于\mathbf{z}_i来重构\mathbf{x}_i，则可得\hat \mathbf{x}_i=\sum\limits_{j=1}^{d'}z_{ij} \mathbf{w}_j。

考虑整个训练集，原样本点\mathbf{x}_i与基于投影重构的样本点\hat \mathbf{x}_i之间的距离如下，其中\text{const}为常数：

\begin{aligned}
\sum\limits_{i=1}^m \left\| \sum\limits_{j=1}^{d'} z_{ij}\mathbf{w}_{j}-\mathbf{x}_i \right\|_2^2 &= \sum\limits_{i=1}^m \mathbf{z}_i^\top \mathbf{z}_i - 2\sum\limits_{i=1}^m \mathbf{z}_i^\top \mathbf{W}^\top \mathbf{x}_i + \text{const} \\
 & \propto -\text{tr}\left( \mathbf{W}^\top \left(\sum\limits_{i=1}^m \mathbf{x}_i\mathbf{x}_i^\top \right) \mathbf{W} \right)
\end{aligned}

根据最近重构性，上式应被最小化，考虑到\mathbf{w}_j是标准正交基，\sum\limits_{i}\mathbf{x}_i\mathbf{x}_i^\top是协方差矩阵，则可得PCA优化目标的一种写法：

\begin{aligned}
\min\limits_{\mathbf{W}} & -\text{tr}(\mathbf{W}^\top \mathbf{X}\mathbf{X}^\top \mathbf{W})\\
\text{s.t. } & \mathbf{W}^\top \mathbf{W}=\mathbf{I}
\end{aligned}

从最大可分性出发：若所有样本点\mathbf{x}_i的投影\mathbf{W}^\top \mathbf{x}_i都尽可能分开，则应使投影后样本点的方差\sum\limits_{i}\mathbf{W}^\top \mathbf{x}_i\mathbf{x}_i^\top \mathbf{W}最大化，如下图所示：

由此可得PCA优化目标的另一种写法：

\begin{aligned}
\max\limits_{\mathbf{W}} &\ \text{tr}(\mathbf{W}^\top \mathbf{X}\mathbf{X}^\top \mathbf{W})\\
\text{s.t. } & \mathbf{W}^\top \mathbf{W}=\mathbf{I}
\end{aligned}

显然，上述两式完全等价！对任意一式使用拉格朗日乘子法可得\mathbf{X}\mathbf{X}^\top \mathbf{W}=\lambda \mathbf{W}，于是与前一节类似，只需对协方差矩阵\mathbf{X}\mathbf{X}^\top进行特征值分解（实践中常改为对\mathbf{X}进行奇异值分解），将求得的特征值由大到小排序，取前d'个最大特征值对应的特征向量即可构成投影矩阵\mathbf{W}=(\mathbf{w}_1,\mathbf{w}_2,\dots,\mathbf{w}_{d'})，这就是PCA的解。

PCA的基本算法描述如下所示：

• 输入：样本集D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}；低维空间维数d'
• 过程：
  • 中心化所有样本\mathbf{x}_i \gets \mathbf{x}_i-\dfrac1m \sum\limits_{j=1}^m \mathbf{x}_j
  • 计算样本的协方差矩阵\mathbf{X}\mathbf{X}^\top
  • 对协方差矩阵\mathbf{X}\mathbf{X}^\top做特征值分解
  • 取最大的d'个特征值所对应的特征向量\mathbf{w}_1,\mathbf{w}_2,\dots,\mathbf{w}_{d'}
• 输出：投影矩阵\mathbf{W}=(\mathbf{w}_1,\mathbf{w}_2,\dots,\mathbf{w}_{d'})

PCA亦可看做是逐一选取方差最大方向，即先对协方差矩阵\sum\limits_{i}\mathbf{x}_i\mathbf{x}_i^\top做特征值分解，取最大特征值\lambda_1对应的特征向量\mathbf{w}_1；再对\sum\limits_{i}\mathbf{x}_i\mathbf{x}_i^\top-\lambda_1做特征值分解，取最大特征值\lambda_2对应的特征向量\mathbf{w}_2……由\mathbf{W}各分量正交及\sum\limits_{i=1}^m \mathbf{x}_i\mathbf{x}_i^\top=\sum\limits_{j=1}^d \lambda_j \mathbf{w}_j \mathbf{w}_j^\top可知，上述逐一选取方差最大方向的做法与直接选取最大d'个特征值等价。

对于低维空间维数d'的选取，通常直接事先指定，或通过在d'值不同的低维空间中对k-近邻分类器（或其他开销较小的学习器）进行交叉验证来选取较好的d'值。对于PCA，还可从重构的角度设置一个重构阈值t（例如95%），然后选取使得不等式\dfrac{\sum\limits_{i=1}^{d'}\lambda_i}{\sum\limits_{i=1}^{d}\lambda_i}\ge t成立的最小d'值。

---

4 核化线性降维

在不少现实任务中，可能需要非线性映射才能找到恰当的低维嵌入。如下图所示，三维空间里的样本点是从二维空间里采样后以S型曲面嵌入，常称原本采样的低维空间本真（Intrinsic）低维空间，可见PCA的线性降维结果丢失了原有结构。

非线性降维的一种常用方法，是基于核技巧对线性降维方法进行核化（Kernelized），例如核主成分分析（Kernelized PCA，KPCA）：假定将在高位特征空间中把数据投影到由\mathbf{W}确定的超平面上，即PCA欲求解

\begin{aligned}
\left(\sum\limits_{i=1}^m \mathbf{z}_i \mathbf{z}_i^\top \right)\mathbf{W}=\lambda \mathbf{W}
\end{aligned}

其中\mathbf{z}_i是样本点\mathbf{x}_i在高维特征空间中的像。对等式变形，可得

\begin{aligned}
\mathbf{W} &=\frac{1}{\lambda}\left(\sum\limits_{i=1}^m \mathbf{z}_i \mathbf{z}_i^\top \right)\mathbf{W}=\sum\limits_{i=1}^m \mathbf{z}_i\frac{\mathbf{z}_i^\top \mathbf{W}}{\lambda}\\
&= \sum\limits_{i=1}^m \mathbf{z}_i \mathbf{\alpha}_i
\end{aligned}

其中\mathbf{\alpha}_i=\dfrac{1}{\lambda}\mathbf{z}_i^\top \mathbf{W}。假定\mathbf{z}_i是由原始属性空间中的样本点\mathbf{x}_i通过映射\phi产生，即\mathbf{z}_i=\phi(\mathbf{x}_i),\ i=1,2,\dots,m。若\phi能被显式地表达出来，则通过它可将样本映射到高维特征空间，再在特征空间中实施PCA即可。据此，可将欲求解式和基向量组的表达分别变换为

\begin{aligned}
\left(\sum\limits_{i=1}^m \phi(\mathbf{x}_i) \phi(\mathbf{x}_i)^\top \right)\mathbf{W}=\lambda \mathbf{W}\\
\mathbf{W}=\sum\limits_{i=1}^m \phi(\mathbf{x}_i) \mathbf{\alpha}_i
\end{aligned}

由于不清楚\phi的具体形式，故引入核函数（更多内容见前述）：

\begin{aligned}
\kappa(\mathbf{x}_i,\mathbf{x}_j)=\phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)
\end{aligned}

将所得全部代入欲求解式，可得KPCA最终的欲求解式：

\begin{aligned}
\mathbf{K}\mathbf{A}=\lambda \mathbf{A}
\end{aligned}

其中\mathbf{K}为\kappa对应的核矩阵，(\mathbf{K})_{ij}=\kappa(\mathbf{x}_i,\mathbf{x}_j)，\mathbf{A}=(\mathbf{\alpha}_1;\mathbf{\alpha}_2;\dots;\mathbf{\alpha}_m)。显然，与上两节情况同理，对于该特征值分解问题，取\mathbf{K}最大的d'个特征值对应的特征向量即可。

对新样本\mathbf{x}，其投影后的第j\ (j=1,2,\dots,d')维坐标如下，其中\mathbf{\alpha}_i已经过规范化，\alpha_i^j是\mathbf{\alpha}_i^j是\mathbf{\alpha}_i的第j个分量：

\begin{aligned}
z_j &= \mathbf{w}_j^\top \phi(\mathbf{x}) = \sum\limits_{i=1}^m \mathbf{\alpha}_i^j \phi(\mathbf{x}_i)^\top \phi(\mathbf{x})\\
&= \sum\limits_{i=1}^m \alpha_i^j \kappa(\mathbf{x}_i,\mathbf{x})
\end{aligned}

由上式可见，为获得投影后的坐标，KPCA需对所有样本求和，因此其计算开销较大。

---

5 流形学习

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

本节介绍两种著名的流形学习方法——

5.1 等度量映射

等度量映射（Isometric Mapping，Isomap）的基本出发点是：高维空间中的直线距离具有误导性，因为有时高维空间中的直线距离在低维嵌入流形上是不可达的。低维嵌入流形上的两点间距离是测地线（Geodesic）距离，如下图(a)中红色曲线所示，是两点之间的本真距离。直接在高维空间中计算直线距离是不恰当的，因此利用流形在局部上与欧式空间同胚的性质，可以使用近邻距离来逼近测地线距离，即对每个点基于欧氏距离找出其近邻点，建立一个近邻链接图（图中近邻点之间存在连接，非近邻点之间不存在连接），于是高维空间中两个样本之间的距离就转变为计算近邻连接图上两点之间的最短路径，如下图(b)中所示。

对于近邻图的构建常有两种方法：一种是指定近邻点个数k，采用kNN的思想，选取最近的k个点为近邻点，这样得到的近邻图称为k-近邻图；另一种是指定距离阈值\varepsilon，距离小于\varepsilon的点被认为是近邻点，这样得到的近邻图称为ε-近邻图。注意近邻范围的选取：若近邻范围指定过大，则距离很远的点可能被误认为近邻，出现“短路”问题；若近邻范围指定过小，则部分样本点可能会不可达，出现“断路”问题。应科学选取近邻范围（另见“k-近邻”一节），避免给后续的最短路径计算造成误导。

对于图的最短路径问题，可采用Dijkstra算法或Floyd算法等进行求解。在得到高维空间中任意两点之间的距离后，便可使用MDS算法来其计算低维空间中的坐标。

Isomap的算法流程如下所示：

• 输入：样本集D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}；近邻参数k；低维空间维数d'
• 过程：
  • for i=1,2,\dots,m do
    • 确定\mathbf{x}_i的k近邻
    • \mathbf{x}_i与k近邻点之间的距离设置为欧氏距离，与其他点的距离设置为无穷大
  • end for
  • 调用最短路径算法计算任意两样本点之间的距离\text{dist}(\mathbf{x}_i,\mathbf{x}_j)
  • 将\text{dist}(\mathbf{x}_i,\mathbf{x}_j)作为MDS算法的输入
  • return MDS算法的输出
• 输出：样本集D在低维空间的投影\mathbf{Z}=\{\mathbf{z}_1,\mathbf{z}_2,\dots,\mathbf{z}_m\}

注意Isomap仅是得到了训练样本在低维空间的坐标，无法给出通用的投影向量组。对于新样本的映射，权且以训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。目前并没有发现特别好的办法。

5.2 局部线性嵌入

不同于Isomap算法去保持邻域距离，局部线性嵌入（Locally Linear Embedding，LLE）算法试图保持邻域内样本之间的线性关系。如下图所示，假定样本点\mathbf{x}_i的坐标可通过其邻域样本\mathbf{x}_j,\mathbf{x}_k,\mathbf{x}_l的坐标通过线性组合而重构出来（线性表出），即如下式所示，则LLE希望该关系在低维空间中得以保持：

\begin{aligned}
\mathbf{x}_i=w_{ij}\mathbf{x}_j+w_{ik}\mathbf{x}_k+w_{il}\mathbf{x}_l
\end{aligned}

首先，LLE为每个样本\mathbf{x}_i找到其近邻下标集合Q_i，然后计算出基于Q_i中的样本点对\mathbf{x}_i进行线性重构的系数\mathbf{w}_i：

\begin{aligned}
\min\limits_{\mathbf{w}_1,\mathbf{w}_2,\dots,\mathbf{w}_m} & \sum\limits_{i=1}^m \left\| \mathbf{x}_i - \sum\limits_{j\in Q_i} w_{ij} \mathbf{x}_j \right\|_2^2\\
\text{s.t. } & \sum\limits_{j\in Q_i} w_{ij}=1
\end{aligned}

其中各样本点\mathbf{x}_i,\mathbf{x}_j均为已知，令C_{jk}=(\mathbf{x}_i-\mathbf{x}_j)^\top (\mathbf{x}_i-\mathbf{x}_k)，可直接求得w_{ij}的闭式解：

\begin{aligned}
w_{ij}=\frac{\sum\limits_{k\in Q_i} C_{jk}^{-1}}{\sum\limits_{l,s\in Q_i}C_{ls}^{-1}}
\end{aligned}

接着，LLE在低维空间中保持\mathbf{w}_i不变，故\mathbf{x}_i对应的低维空间坐标\mathbf{z}_i可通过下式求解：

\begin{aligned}
\min\limits_{\mathbf{z}_1,\mathbf{z}_2,\dots,\mathbf{z}_m} \sum\limits_{i=1}^m \left\| \mathbf{z}_i - \sum\limits_{j\in Q_i} w_{ij} \mathbf{z}_j \right\|_2^2
\end{aligned}

上式与求重构系数的优化目标同型。令\mathbf{Z}=(\mathbf{z}_1,\mathbf{z}_2,\dots,\mathbf{z}_m)\in \mathbb{R}^{d'\times m},\ (\mathbf{W})_{ij}=w_{ij},\ \mathbf{M}=(\mathbf{I}-\mathbf{W})^\top (\mathbf{I}-\mathbf{W})，则上式可重写为

\begin{aligned}
\min\limits_{\mathbf{Z}} &\ \text{tr}(\mathbf{Z}\mathbf{M}\mathbf{Z}^\top)\\
\text{s.t. } & \mathbf{Z}\mathbf{Z}^\top = \mathbf{I}
\end{aligned}

与前几节同理，可通过特征值分解求解，\mathbf{M}最小的d'个特征值对应的特征向量组成的矩阵即为\mathbf{Z}^\top。

LLE的算法描述如下所示：

• 输入：样本集D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}；近邻参数k；低维空间参数d'
• 过程：
  • for i=1,2,\dots,m do
    • 确定\mathbf{x}_i的k近邻
    • 求得w_{ij}=\dfrac{\sum\limits_{k\in Q_i} C_{jk}^{-1}}{\sum\limits_{l,s\in Q_i}C_{ls}^{-1}},\ j\in Q_i
    • 对于j\notin Q_i，令w_{ij}=0
  • end for
  • 求得\mathbf{M}=(\mathbf{I}-\mathbf{W})^\top (\mathbf{I}-\mathbf{W})
  • 对\mathbf{M}进行特征值分解
  • return \mathbf{M}的最小d'个特征值对应的特征向量
• 输出：样本集D在低维空间的投影\mathbf{Z}=\{\mathbf{z}_1,\mathbf{z}_2,\dots,\mathbf{z}_m\}

---

6 度量学习

在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。那么，何不尝试直接学习出一个合适的距离度量？由此引入了度量学习（Metric Learning），亦称距离度量学习（Distance Metric Learning）。

欲对距离度量进行学习，必须有一个便于学习的距离度量形式。此前“距离度量”一节给出的距离度量表达式都是固定的、无可调节的参数，故在此先进行一个推广：对于两个d维样本\mathbf{x}_i,\mathbf{x}_j，它们之间的平方欧氏距离为

\begin{aligned}
\text{dist}_{\text{ed}}^2(\mathbf{x}_i,\mathbf{x}_j)=\left\|\mathbf{x}_i - \mathbf{x}_j \right\|_2^2=dist_{ij,1}^2+dist_{ij,2}^2+\cdots+dist_{ij,d}^2
\end{aligned}

其中dist_{ij,k}表示\mathbf{x}_i与\mathbf{x}_j在第k维上的距离。若假定不同属性的重要性不同，则引入属性权重\mathbf{w}后的加权平方欧氏距离为

\begin{aligned}
\text{dist}_{\text{wed}}^2(\mathbf{x}_i,\mathbf{x}_j)= &\left\|\mathbf{x}_i - \mathbf{x}_j \right\|_2^2=w_1\cdot dist_{ij,1}^2+w_2\cdot dist_{ij,2}^2+\cdots+w_d\cdot dist_{ij,d}^2\\
&= (\mathbf{x}_i-\mathbf{x}_j)^\top \mathbf{W}(\mathbf{x}_i-\mathbf{x}_j)
\end{aligned}

其中w_i \ge 0，对角矩阵\mathbf{W}=\text{diag}(\mathbf{w}),\ (\mathbf{W})_{ii}=w_i，可通过学习确定。然而，尽管由于\mathbf{W}非对角元素均为0，坐标轴是正交的，即属性之间无关，但现实中往往存在属性互相关联的情况（例如西瓜的“重量”和“体积”）。为此，将上式中的\mathbf{W}替换为一个普通的半正定对称矩阵\mathbf{M}（常称为度量矩阵），由此引入了经典的马氏距离（Mahalanobis Distance）：

\begin{aligned}
\text{dist}_{\text{mah}}^2(\mathbf{x}_i,\mathbf{x}_j)= (\mathbf{x}_i-\mathbf{x}_j)^\top \mathbf{M}(\mathbf{x}_i-\mathbf{x}_j)=\left\|\mathbf{x}_i - \mathbf{x}_j \right\|_{\mathbf{M}}^2
\end{aligned}

度量学习对度量矩阵\mathbf{M}进行学习。注意为了保持距离非负且对称，度量矩阵必须是（半）正定对称矩阵，即必有正交基\mathbf{P}使得\mathbf{M}=\mathbf{P}\mathbf{P}^\top。

对于度量学习的优化目标，可以设置为错误率或相似性等。常用的近邻分类器有近邻成分分析）Neighbourhood Component Analysis，NCA）等，此处略。