提示：
拓扑“流形”是指局部与欧氏空间同胚的空间，简言之，形象地理解为： 流畅地“拼接”局部超平面（每一个“局部”都能都能视为欧氏空间）。
等度量映射策略：将空间中视为一个紧挨一个的“局部”拼接而成，而“局部”视为欧氏空间（定义了欧氏距离）
局部线性嵌入策略：它的局部是指$k$近邻，在局部可以用一个超平面替换（低维流形嵌入高维中），且这种嵌入具有“线性关系”不变的特点

流形学习

拓扑“流形”是指局部与欧氏空间同胚的空间，简言之，形象地理解为： 流畅地“拼接”局部超平面（每一个“局部”都能都能视为欧氏空间）。 这样就易于处理，如，欧氏空间中的曲面可用超平面近似。

等度量映射

策略：将空间中视为一个紧挨一个的“局部”拼接而成，而“局部”视为欧氏空间（定义了欧氏距离），在全局中使用“测地线”作为距离，即若干“局部”线段串起来的最短折线。 涉及两个问题：

（1）如何定义“局部”？有两种方案：

• 邻域：得到$\epsilon$- 邻近图。
• 近邻：得到$k$近邻图。
  这里通常取$k$近邻，因为它本身的确定并不需要欧氏距离，再在其上定义欧氏距离。

（2）求最短折线，有Dijkstra算法或Floyd算法。

综合（1）（2）得到等度量映射的Isomap算法【西瓜书图10.8】。

局部线性嵌入

局部线性嵌入LLE算法是一种“流形学习”：它的局部是指$k$近邻，在局部可以用一个超平面替换（低维流形嵌入高维中），且这种嵌入具有“线性关系”不变的特点，即： 高维中存在的线性关系在低维中仍保持不变，反之亦然。

$\mathcal{X}$空间（$d$维）中样本集 { x i } i = 1 m \{\boldsymbol{x}_i\}_{i=1}^m {xi​}i=1m​中每个样本已编号（下标指示），即样本集对应的下标集为： { 1 , 2 , ⋯   , m } \{1,2,\cdots,m\} {1,2,⋯,m}。 每个样本点${\mathbf{x}}_i$的全部$k$近邻点${\mathbf{x}}_j$的下标集记为$Q_i$，则$Q_i$为 { 1 , 2 , ⋯   , m } \{1,2,\cdots,m\} {1,2,⋯,m}的子集。 又任意点的近邻点个数是一个常数（超参数），不妨设为$Q$，即子集的大小为常数：$|Q_i|=Q$。
设$\mathcal{X}$空间（$d$维）中的样本点${\mathbf{x}}_i$降维成$\mathcal{Z}$空间（$d^{\prime }$维）中点${\mathbf{z}}_i$，对应的邻域（近邻集）${\mathcal{X}}_i$，变成了${\mathcal{Z}}_i$（为行文方便，不妨称它为${\mathbf{z}}_i$的邻域）。

LLE算法的原理是高、低维两对应邻域内的线性关系一致，即同时有
$$\begin{array}{r}{\mathbf{x}}_i=\sum _{j\in Q_i}{w}_{ij}{\mathbf{x}}_j\end{array}\text{\hspace{1em}(10.77)}$$
$$\begin{array}{r}{\mathbf{z}}_i=\sum _{j\in Q_i}{w}_{ij}{\mathbf{z}}_j\end{array}\text{\hspace{1em}(10.78)}$$
其中，${\mathbf{x}}_i$为任一样本点，$Q_i$为点${\mathbf{x}}_i$的近邻点集对应的下标集。

当然，这是理想情况，一般情况下有二个问题：一是线性关系本身是“近似”成立，二是不变性也是“近似”成立，因此，我们退而求其次：尽最大可能使其“近似”，这就转化成了优化问题。

（1）在低维邻域${\mathcal{Z}}_i$中，设点${\mathbf{z}}_i$的“近似”点${\hat{\mathbf{z}}}_i$满足式(10.78)，即
$$\begin{array}{r}{\hat{\mathbf{z}}}_i=\sum _{j\in Q_i}{w}_{ij}{\mathbf{z}}_j\end{array}\text{\hspace{1em}(10.79)}$$
并对系数作“概率化（亦称规范化、归一化）”（使其和为1）处理，即式(10.78)中，${\sum }_{j\in Q_i}{w}_{ij}=1$。

（2）在高维邻域${\mathcal{X}}_i$中依式(10.79)的线性关系重构出一个新点${\hat{\mathbf{x}}}_i$。
$$\begin{array}{r}{\hat{\mathbf{x}}}_i=\sum _{j\in Q_i}{w}_{ij}{\mathbf{x}}_j\end{array}\text{\hspace{1em}(10.80)}$$
其中，${\sum }_{j\in Q_i}{w}_{ij}=1$。

（3）在高维邻域${\mathcal{X}}_i$中，新点${\hat{\mathbf{x}}}_i$为原样本点${\mathbf{x}}_i$的“近似”点，它们之间的误差为${\mathbf{x}}_i-{\hat{\mathbf{x}}}_i$。 将数据集的“均方误差最小化”作为优化目标，即【西瓜书式(10.27)】。 这是已知数据集中点的坐标求解$w_{ij}$，它能求出闭式解（闭式解是指能用式子表达的解），即解为【西瓜书式(10.28)】。

（4）在低维邻域${\mathcal{Z}}_i$中，新点${\hat{\mathbf{z}}}_i$为原样本点${\mathbf{z}}_i$的“近似”点，它们之间的误差为$||{\mathbf{z}}_i-{\hat{\mathbf{z}}}_i|{|}^2$。 在低维空间中优化目标也为均方误差最小化，即【西瓜书式(10.29)】。 但它是已知$w_{ij}$（【西瓜书式(10.28)】），求点的坐标。 该问题转化为【西瓜书式(10.31)】，即为矩阵的特征分解问题：通过对$\mathbf{M}$进行特征分解，特征值排序后，取$d^{\prime }$个最小特征值对应的特征向量，组成矩阵${\mathbf{Z}}^{\mathrm{T}}$即为所求（参考式(10.17)），该矩阵有$d^{\prime }$列（即选取的特征向量），但有$m$行，每行对应一个点${\mathbf{z}}_i$，且点${\mathbf{x}}_i$与点${\mathbf{z}}_i$对应。

综上，得到局部线性嵌入LLE算法【西瓜书图10.10】。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：10.7 核化线性降维（线性降维+“核技巧”）
下一篇：10.9 局部线性嵌入公式推导（更正书中的公式）