数据科学中的几何观点

• 赋予拓扑结构（数据集是一个拓扑空间）：数据集合 的子集构成的新的集合 , 称为数据集 上的拓扑 (topology
  )，需要满足以下条件：

  (1) ,;

  (2) 中有限个集合的交集和任意（有限、可数、不可数）个集合的并集还属于 。简单来说就是 中的集合对于有限交和任意并运算封闭。
• 赋予流形结构：数据集 上可以赋予很多拓扑结构，并不是唯一的。我们进一步增加约束条件：令 是一个Hausdorff
  空间。若对任一点 , 都存在 在 中的一个邻域 ,使得 同胚于 维欧氏空间 , 则 就称为是一个 维流形。
• 赋予微分流形结构：为了能在数据流形上有微分运算（类似欧式空间），我们需要数据流形是可微的：一个 维微分流形 就是一个赋予了微分结构的 维流形，即存在一组坐标卡 （即流形定义中的局部同胚映射），使得：（i） 为 的一个开覆盖；（ii）任意两个不相交的坐标卡；（iii） 和 满足 皆为 函数为 极大的（该条件可由前两条唯一生成）。

• 微分流形局部同胚与欧式空间（每个点都存在一个邻域同胚于欧氏空间中的开集）；
• 微分流形可以嵌入至欧式空间；

第二部分 流行学习

有了Whitney
嵌入定理的理论保证，高维数据集可以先验为嵌入高维欧式空间的低维流形。基于这个先验就有了一个研究分支：流形学习（manifold learning
）。

对于地球位置的数据集，在 3 维欧式空间可以用 3 维数据坐标 来表示，实际上又可以用 2 维经纬度坐标（内蕴坐标）表示，地球位置数据实际是一个二维球面子流形嵌入在 3 维欧式空间中。当数据集是 3 维欧式空间表示时，我们可以降维到二维流形。

上面的分析前提是我们开启了上帝视角。实际应用中，对于任意给定的数据集，很难判断或假设合理的内蕴流形结构。

2.1 数据降维

数据科学中对于线性空间中数据，有较多成熟的降维技术：例如主成分分析（PCA
）、独立分量分析（ICA
）、Fish
判别法（FDA
）、多尺度分析（MDS
）等。那么在降维的时候，寻找恰当的降维映射是算法的目的。降维映射空间同样是庞大的，需要定义相关的性能度量来度量映射的优劣。

然而对于非线性数据流形，空间上是没有距离（欧氏距离）概念的。这时候我们需要利用微分流形另一个重要特性：微分流形局部同胚与欧式空间。

宇宙是一个微分流形，我们人类所处的局部是一个三维欧式空间。

2.1.1 保持局部线性关系

映射需要保持流形上每个很小的局部欧式线性。代表算法有：局部改线嵌入（local Linear Embedding
，LLE
）。算法大体分成三个部分：寻找近邻、线性重构、低维嵌入。

• 寻找近邻。对于每个数据点，需要定义邻域。邻域有两种方式：(1)最近的K
  个点;(2)邻域距离阀值限定局部大小。LLE
  算法使用前者，其中K
  是一个预先给定值（超参数），使用欧式距离度量。
• 线性重构。每个数据点由 K 个近邻线性表达；
• 低维嵌入。每个点在低维空间中的降维映射值在项空间同样有近似的线性表达。

具体算法过程，参考论文：《Nonlinear Dimensionality Reduction by Locally Linear Embedding
》。LEE
算法对于闭合流形、稀疏数据集效果有限，另外结果对于 K 值选取较为敏感。

2.1.2 保持点之间测地线距离

微分流形中整体是没有距离概念的，但是有推广的测地线距离（geodesic
）。代表算法有Isomap
(Isometric Feature Mapping
)算法。算法步骤大体分成三个部分：构造近邻图、计算最短路径、低维嵌入。

• 构造近邻图。和LLE
  算法相同，基于欧式距离找出邻近点，建立整体集合的近邻连接图（图论理论中图概念）。

• 计算最短路径。近邻连接图中近邻点之间存在连接关系，而非近邻点之间不存在连接关系。这样计算两点之间测地线距离的问题就转变为计算近邻连接图上两点之间的最短路径问题。最短路径上逐点距离和近似代替几何意义上的测地线。最短路径计算，采用图论中Dikstra
  算法或Floyd
  算法。

• 低维嵌入。在得到任意两点的距离之后，结果就可以直接应用 MDS(Multidimensional Scaling)
  算法了。

上图瑞士卷数据集是常用的验证数据集。A 图中蓝色线表示流形上两点之间的实际测地线距离，B 图中红色是Dijkstra
算法在近邻图上找到的最短距离，C 图显示了降维后三维数据集在二维平面中的嵌入效果，结果较为近似。但是当流形的曲率较大、数据稀疏时或者流形上有孔洞的话，算法效果较差。而对于空间中的数据点稠密时，近似效果较好。

2.1.3 保持图的局部邻接关系

Isomap
算法使用点与点之间欧式距离构建了整体数据集合的近邻图。在这个图中，点与点之间关系为欧式距离。而这个关系可以使用高斯核(Gaussian Kernel
)来定义。

对于连通的两个点 ,令图关系值为: 。而其它点关系值为: 0。这样所有点之间的关系值可以得到图的邻接矩阵W，第i行的第i'个值对应权重：。

如果记在降维映射后的值为 ,那么就是在假设空间中寻找函数使得下面的性能度量最小：

其中

这个目标函数形式是不是和PCA
十分的相似。目标函数的求解是一个广义特征值分解问题：

计算L
的特征值，将特征值从小到大排序，取前k
个特征值，并计算前k
个特征值 。这样就得到了键数据映射到特征空间中。

这个算法过程和谱聚类(Spectral Clustering
)算法技术是相同的。

这就是Laplacian Eigenmaps
算法，具体算法过程，参考论文：《Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
》。LEE 算法对于闭合流形、稀疏数据集效果有限，另外结果对于 K 值选取较为敏感。

LE 算法是非线性的，另外还有推广的线性版本：保持投影LPP
（Locality Preserving Projections
）算法，参考论文：《Locality Preserving Projections
》。

2.1.4 保持概率分布

对于数据流形中，Isomap
算法使用近似测地线来度量近邻点之间的距离（相似性）。2002 年 Hinton
提出一个奇妙的思路，使用概率密度来度量这个相似性。这就是SNE
（Stochastic Neighbor Embedding
）算法。

对于数据流形 中两个数据点 和 ，考虑 为中心的高斯分布（ 为分布的方差），定义一个条件概率 （数据点 选择 为近邻点的概率）：

当映射将流形数据映射到低维空间 后，需要保持数据点的相似性。记在低维空间中数据点 和 的值分别为 和 ，同样赋予条件概率度量，特别的将高斯分布的方差固定为 。

我们定义了数据流形中点 和值空间中点 条件概率。如果遍历所有点，就定义了一个关于 和 的概率分布：

映射保持概率分布，这时候概率分布的度量KL
（Kullback-Leibler Divergence
）散度就用上了,最后得到假设空间的性能度量指标：

最后算法根据这个目标函数寻找最优解。

我们知道KL
散度是非对称的，SNE
算法更关注于局部，容易忽视全局结构。后续Hinton
将低维空间的分布由高斯分布换成t
分布（利用t
分布的长尾性特征），就是降维可视化中最常用的算法t-SNE
算法。

下图为mnist
在t-SNE
算法下降维至 2 维空间的可视化效果。

对于t-SNE
算法，实际工程实现时需要计算大量的概率值，计算量较大。实际上，对于相距较远的点成为邻域点的概率会很小，所以只需要考虑一定范围邻域的点集即可，提前构建近邻图。

2.2 可视化

数据降维的一个衍生功能就是可视化化。将数据映射到二维或者三维欧式空间中（映射保持指定的信息结构），便于三维生物体更容易感知到数据之间的结构关系。但是原始数据蕴含的流形并不一定是恰好的三维或二维，强行降维会破坏数据的真实结构信息。

2.3 半监督学习

在实际数据处理中，标签数据是珍贵而稀缺的。更多的应用场景是：有少量已经标记的标签数据和大量的无标签数据。在流形学习假设前提下，相似数据应该在流形的同一个局部邻域中（或者说局部领域中数据标签相似）。基于这个假设，大量的非标签数据就可以通过少量标签获取到标签。

2.4 工程实现

对于工程实现，Python
中scikit-learn
包提供相关流形学习的算法实现包。主要有：

• Isomap Embedding，封装类：manifold.Isomap()

• Locally Linear Embedding，封装类：manifold.LocallyLinearEmbedding()

• Spectral embedding，封装类：manifold.SpectralEmbedding()

• t-SNE，封装类：manifold.TSNE()

第三部分 总结

3.1 谱图理论

Isomap
算法和LE
算法在构建数据近邻图的过程使用的思想其实是谱图理论(spectral graph theory)。其本质是利用数据相似度的关系矩阵，然后计算矩阵的特征值和特征向量，最后选择合适的特征向量投影得到的数据的低维嵌入。图谱理论的技术要求数据流形的数据采样是稠密的、流形曲率不能太大，否则对噪声是敏感的。

图谱理论的技术使得数据流形学习由理论落地为实践。近几年在图神经网络方向仍然是重要技术。

3.2 流形学习中问题

  3.2.1 基本问题 1

由于笔者水平有限，不能保证全部内容均正确无误，欢迎大家留言指教一起探讨。

参考文献