《机器学习》流形学习 流形 局部线性嵌入 等距映射（Isomap： 测地线MDS降维

流形学习

流形学习（Manifold Learning）是一种降维技术，它基于这样的假设：高维数据实际上位于一个低维的流形上，这个低维流形嵌入在更高维的空间中。流形是一种几何结构，它在局部看起来像欧几里得空间，这意味着在足够小的尺度上，流形上的点可以由欧几里得距离来描述。

流形

流形（Manifold）是数学中的一个基本概念，特别是在拓扑学和微分几何学中。简单来说，流形是一个局部类似于欧几里得空间的拓扑空间。更正式地，一个流形可以定义如下：

一个拓扑空间M称为n维流形，如果它满足以下两个条件：

1. 豪斯多夫空间（Hausdorff Space）：对于M中的任意两个不同的点，都存在不相交的开集，分别包含这两个点。A∩B=∅，x∈A，y∈B。这意味着流形中的每对点都可以被分开。

2. 局部欧几里得性：M中的每一个点都有一个邻域，这个邻域与n维欧几里得空间R^n的某个开集同胚（homeomorphic）。同胚是一种连续的双向映射，它保持拓扑结构不变。这意味着在足够小的尺度上，流形的局部区域看起来和普通的欧几里得空间一样。

以下是一些流形的例子：

这样，球面上的点(λ, φ)就被映射到了平面上的点(x, y)。在这个映射下，球面上的邻域U被映射成了平面上的一个开集V。

举例：

假设我们在地球表面上的北极点(0°N, 0°E)。我们可以取一个以北极点为中心，半径为r的圆形邻域。这个邻域内的所有点都可以用它们的经度λ和相对于北极点的角度θ来描述，这里纬度φ固定为90°N。

映射过程如下：

这样，球面上的点(λ, 90°N)就被映射到了平面上的点(x, y)，其中x = λ，y = 90°。实际上，由于我们是在北极点，这个映射可以简化为只考虑经度λ，因为纬度是固定的。

在更一般的情况下，如果我们不是在极点，那么映射会涉及纬度和经度的变化，但基本思想是相同的：将球面上的邻域通过经纬度映射到平面上的一个开集，保持邻域内的拓扑结构不变。这个映射是连续的，并且可以在局部区域内逆转，从而证明了球面在局部是平面R^2的同胚。

• 直线：一维流形，每个点都有一个邻域同胚于实数线R。
• 平面：二维流形，每个点都有一个邻域同胚于平面R^2。
• 球面：二维流形，尽管它嵌入在三维空间中，但每个点都有一个邻域同胚于平面R^2。（还记得复分析的球极映射嘛，たぶん、（）多分）

  在球面上，一个点到其邻域到平面开集的具体映射可以通过以下步骤来描述，这里我们以地球表面的经纬度系统为例：

• 选择球面上的一个点：假设我们选择球面上的一个点P，我们可以用经纬度(λ, φ)来表示这个点，其中λ是经度，φ是纬度。

• 定义邻域：在点P附近取一个足够小的邻域U，这个邻域是球面上的一部分，可以想象成一个微小的圆盘。

• 映射到平面：我们可以将这个邻域U映射到平面R^2上的一个开集V。这个映射可以定义为：

  • 将纬度φ映射到平面上的y坐标，即y = φ。
  • 将经度λ映射到平面上的x坐标，即x = λ。
• 对于邻域内的任意一点(λ, 90°N)，我们将纬度90°N映射到平面上的y坐标，即y = 90°。
• 将经度λ映射到平面上的x坐标，即x = λ。
• 由于我们是在北极点附近，我们可以将角度θ映射到平面上的另一个坐标，比如z = θ。
• 圆环面（Torus）：二维流形，常见于甜甜圈形状，每个点都有一个邻域同胚于平面R^2。

流形的概念在物理学和工程学中也非常重要，特别是在描述物理空间的几何性质时。例如，在广义相对论中，宇宙的时空被认为是四维流形。

在数据科学和机器学习中，流形的假设被用于流形学习算法，这些算法试图发现高维数据中的低维结构。在这种情况下，数据点被认为是在一个低维流形上分布，这个流形嵌入在一个更高维的空间中。通过理解这种低维结构，可以更容易地进行数据分析和可视化。

流形的数学定义

在数学中，流形的正式定义涉及拓扑和微分几何的概念。以下是n维流形的数学定义：

一个拓扑空间M称为一个n维拓扑流形，如果它满足以下条件：

1. 豪斯多夫空间：M是一个豪斯多夫空间，即对于M中的任意两个不同的点p和q，都存在不相交的开集U和V，使得p ∈ U且q ∈ V。

2. 第二可数性：M有一个可数的基，即存在一个可数集合{U_i}，它是M的开覆盖，并且对于M中的任意开集V，V都可以表示为这些U_i的并集。

3. 局部欧几里得性：对于M中的每一个点p，都存在一个开集U包含p，使得U同胚于n维欧几里得空间R^n。这意味着在U上存在一个同胚映射ϕ: U → ϕ(U) ⊆ R^n，其中ϕ(U)是R^n中的一个开集。

如果M不仅是一个拓扑流形，而且在其上还可以定义一个光滑结构，使得光滑函数可以在M上连续地微分，那么M被称为一个光滑流形。以下是光滑流形的额外条件：

1. 光滑结构：M有一个光滑结构，即存在一个图册（atlas），这是一个由M上的开集组成的集合{ϕ_i: U_i → V_i}，其中每个ϕ_i是从开集U_i到R^n的同胚，并且V_i是R^n中的开集，满足以下条件：
   • {U_i}是M的开覆盖。
   • 对于任意两个图册中的映射ϕ_i和ϕ_j，它们的重叠部分ϕ_i(U_i ∩ U_j)和ϕ_j(U_i ∩ U_j)是光滑兼容的，即ϕ_j ∘ ϕ_i^(-1)和ϕ_i ∘ ϕ_j^(-1)是从R^n到R^n的光滑映射。

流形的定义可以进一步扩展到包括微分流形、复流形、黎曼流形等，每种类型的流形都有其特定的附加结构和性质。例如，黎曼流形是带有黎曼度量的光滑流形，这个度量允许我们定义距离和角度，从而进行积分和曲率分析。

以下是两种著名的流形学习方法：

1. 局部线性嵌入（Locally Linear Embedding, LLE）：

   • LLE的基本思想是每个数据点都可以通过其近邻点的线性组合来近似重建。这种方法首先为每个数据点找到其近邻点，然后计算这些近邻点的权重，这些权重可以用来重建原始点。在保持这些局部重建关系的同时，LLE寻找一个低维空间，在这个空间中，数据点可以保持相似的重建权重。LLE不显式地使用数据的全局结构，因此它特别适合于非线性的流形结构。
   • LLE的步骤通常包括：
     • 确定每个点的近邻点。
     • 计算权重矩阵，用于重建每个点。
     • 利用权重矩阵求解低维空间中的坐标。

2. 等距映射（Isomap）：

   • Isomap是一种基于几何学的降维方法，它试图保持数据点之间的全局几何结构。Isomap首先使用近邻图来估计数据点之间的距离，即计算每个点与其近邻点之间的最短路径距离（通常使用Dijkstra算法或Floyd-Warshall算法）。然后，它将这些距离视为在低维空间中保持不变的距离，并使用多维尺度分析（Multidimensional Scaling, MDS）来找到数据点在低维空间中的表示。
   • Isomap的步骤通常包括：
     • 确定每个点的近邻点并构建近邻图。
     • 计算图中所有点对之间的最短路径距离。
     • 使用MDS或其他技术来找到保持这些距离的低维表示。

这两种方法都可以有效地将高维数据降至低维，使得数据可以在二维或三维空间中可视化，从而帮助我们发现数据中的结构和模式。然而，它们也都有局限性，例如对噪声敏感、计算复杂度高以及难以处理新数据点的嵌入问题。

测地线

测地线是流形上的一种曲线，它具有以下性质：在曲线上的每一点处，测地线都是该点切空间中曲线的最短路径。换句话说，测地线是流形上两点之间局部距离最短的曲线。这个概念是欧几里得空间中直线的推广，因为在欧几里得空间中，两点之间的最短路径就是直线。

以下是测地线的数学定义：

设(M, g)是一个带有度量g的黎曼流形，γ: [a, b] → M是一个参数化的曲线。如果对于任意ε > 0，都存在δ > 0，使得对于所有满足|t - s| < δ的t, s ∈ [a, b]，都有：

存疑

d(γ(t),γ(s))=∣t−s∣⋅gγ(s)​(γ′(s),γ′(s))​

其中d是流形上的距离函数，γ’(s)是曲线在点γ(s)的切向量，那么曲线γ称为测地线。

测地线距离是指在黎曼流形上，沿着测地线计算的两点之间的距离。它是流形上两点之间最短路径的长度。测地线距离的数学表达式如下：

设p和q是黎曼流形M上的两点，存在一条参数化的测地线γ: [a, b] → M，使得γ(a) = p和γ(b) = q，那么p和q之间的测地线距离定义为：

dM​(p,q)=∫a b ​gγ(t)​(γ′(t),γ′(t))​dt

这里的积分是在测地线γ上进行的，g_{γ(t)}是流形在点γ(t)的度量张量，γ’(t)是测地线在点γ(t)的切向量。

在日常生活中，测地线距离的一个直观例子是在地球表面计算两个城市之间的最短距离。由于地球是一个近似球体，因此两点之间的最短路径通常不是在平面上连接这两点的直线，而是在球面上的大圆弧，这条大圆弧就是地球表面上的测地线。

不过流形学习似乎没什么前途，数学还贼复杂。

MDS降维

多维尺度分析（MDS）是一种统计学方法，主要用于将高维数据转换到低维空间，同时保持数据点间的距离关系。这一方法最早由Torgerson于1952年提出，广泛应用于社会科学、心理学、生物学、地理信息系统、信息检索、数据挖掘等领域2。

MDS的核心思想是将高维空间中的数据点映射到低维空间，例如二维或三维，以保持这些点之间的距离关系。这种方法特别适用于数据可视化和分析，使得复杂数据集的结构和模式更加直观14。

MDS算法的主要步骤包括：

1. 构建距离矩阵：计算原始空间中数据点之间的距离。
2. 中心化距离矩阵：对距离矩阵进行中心化处理。
3. 计算内积矩阵：通过中心化矩阵和距离矩阵的平方形式计算内积矩阵。
4. 计算特征值和特征向量：求内积矩阵的特征值和特征向量。
5. 计算降维后的坐标：将原始数据投影到选定的基上，得到降维后的坐标                       。

在Python中实现MDS算法时，通常会使用诸如NumPy、Matplotlib和SciPy等库来处理数据和可视化结果。这些库提供了计算距离矩阵、特征值和特征向量以及数据可视化的工具。

MDS算法在数据降维技术中占有重要地位，尤其是在处理高维数据集时，它可以帮助简化数据结构，提高计算效率，同时保留关键信息。例如，在生物信息学中，MDS可以用于基因表达数据的可视化；在社会科学中，可以用于分析个体之间的相似性和差异性 

PCA降维

多维尺度分析（MDS）和主成分分析（PCA）都是用于数据降维的技术，它们在某些方面有相似之处，但也存在一些关键的区别。

相似之处：

1. 目的：MDS和PCA的主要目的是减少数据的维度，使得数据更容易理解和可视化，同时尽量保留原始数据中的重要信息。
2. 距离保留：两者都试图在降维过程中保持数据点之间的相对距离。PCA通过最大化数据方差来实现这一点，而MDS直接基于距离矩阵进行降维。

区别：

1. 理论基础：

   • PCA是一种线性降维技术，它通过寻找数据方差最大的方向（即主成分）来进行降维。PCA假设这些主成分能够捕捉到数据中的大部分变异性。
   • MDS是一种非线性降维技术，它不假设数据遵循线性结构。MDS的目标是保持原始数据中点对之间的距离关系，因此它可以更好地处理非线性结构。

2. 计算方法：

   • PCA通过计算数据协方差矩阵的特征值和特征向量来找到主成分。
   • MDS通过优化一个目标函数来最小化原始高维空间中点对之间的距离与低维空间中对应点对之间距离的误差。

3. 适用范围：

   • PCA适用于数据具有线性结构的情况，当数据中存在线性关系时，PCA非常有效。
   • MDS适用于数据可能具有非线性结构的情况，它不依赖于数据的线性假设。

4. 距离度量：

   • PCA使用的是欧几里得距离，它基于数据点的坐标来计算距离。
   • MDS可以采用多种距离度量，包括欧几里得距离，也可以是其他类型的距离，如曼哈顿距离或非度量距离。

5. 输出：

   • PCA的输出是主成分，它们是原始变量的线性组合。
   • MDS的输出是低维空间中的点坐标，这些坐标旨在保持原始数据点之间的相对距离。

尽管MDS和PCA有这些区别，它们在某些情况下可以产生相似的结果，尤其是在数据近似线性时。然而，当数据结构更加复杂和非线性时，MDS可能比PCA更能够保持数据的结构。

———— 

さよなら 实习的日子……