降维（DimensionalityReduction）基础知识1

一、维度与数据空间

  数据空间的维度可能非常大。我们可以通过一些例子来理解高维数据的概念。

1、高维的数据

  下图展示了不同类型的高维数据：

1. 三维散点图：图中展示了一个三维空间中的数据分布。可以看到，数据点在空间中形成了不同的簇，这有助于我们理解数据的结构和模式。
   

2. 人脸图像：这组图像展示了不同人脸的高维特征。每个图像都可以看作是一个高维向量，包含了像素值等信息。
   

3. 文档：文档也可以表示为高维向量，其中每个维度可能代表一个特定的词汇或特征。
   

4. 基因表达数据：这类数据通常包含成千上万的基因表达水平，基因每个可以看作是一个维度。
   

5. MEG（脑磁图）读数：这些读数反映了大脑不同区域的磁场活动，每个区域可以看作是一个维度。
   

  这些例子展示了高维数据在不同领域的应用。高维数据的处理和分析是现代数据科学中的一个重要课题，它涉及到降维、聚类、分类等多种技术。

  在处理高维数据时，我们通常需要找到合适的方法来减少数据的维度，以便更好地理解和分析数据。这可以通过主成分分析（PCA）、t-SNE等降维技术来实现。通过这些技术，我们可以将高维数据投影到较低维度的空间中，同时尽可能保留数据的主要特征和结构。

  总之，高维数据的处理是一个复杂但充满挑战的领域，它需要我们不断探索和创新，以应对日益增长的数据量和复杂性。

二、降维的基本概念

  降维或嵌入是指将原始的高维数据映射到低维空间。本质上的想法是：高度冗余的数据通常是可以被压缩的，即高维复杂数据的本质维度可能比较小，或者和任务相关的维度较小。

  下图展示了降维的效果：

• 左图：展示了原始的3D数据，可以看到数据点分布在一个三维空间中。
• 右图：展示了降维后的本质维度为2D的数据，可以看到数据点被映射到了一个二维平面上，保留了原始数据的主要结构和特征。

  降维技术在数据科学中非常重要，它可以帮助我们减少数据的复杂性，提高计算效率，同时保留数据的主要信息。常见的降维方法包括主成分分析（PCA）、t-SNE、自编码器等。

  通过降维，我们可以将高维数据投影到较低维度的空间中，使得数据更易于可视化和分析。例如，我们可以将高维的人脸图像数据降维到二维空间，从而在二维平面上展示人脸的主要特征。

  总之，降维是处理高维数据的重要工具，它可以帮助我们更好地理解和利用数据。

三、基于重构的降维

1、主成分分析（PCA）

  主成分分析（PCA）是一种常用的降维技术，它通过将数据投影到一个新的坐标系中，来减少数据的维度，同时尽可能保留数据的方差信息。

（1）PCA的基本假设

  假设向量$\Vert w_i\Vert =1$，且$w_i^T{w}_j=0(i\ne j)$，这些向量构成了新的坐标系。坐标原点被设定为数据中心。

（2）PCA的两个关键函数

  在PCA中，$W$用于两个函数：

1. 编码：$z_i=f(x_i;W)=W^T{x}_i$，其中$z_{i,j}=w_j^T{x}_i$。这一步将原始数据$x_i$转换为新坐标系中的表示$z_i$。

2. 解码：${\hat{x}}_i=g(z_i;W)=W{z}_i={\sum }_{j=1}^{D^{\prime }}{z}_{i,j}{w}_j$。这一步将新坐标系中的表示$z_i$转换回原始空间中的近似表示${\hat{x}}_i$。

（3）PCA的目标

  PCA的目标是最小化重建误差$\Vert x_i-{\hat{x}}_i\Vert$，同时最大化投影方差。数学上，这可以表示为：

$$\underset{W\in {\mathbb{R}}^{D\times D^{\prime }}}{\min }\sum _{i=1}^N\Vert x_i-W{z}_i{\Vert }^2=\underset{W}{\max }\sum _{i=1}^N{z}_i^T{z}_i=\underset{W}{\max }\sum _{i=1}^N\text{tr}(W^{T}X{X}^{T}W)$$

其中，$X=(x_1,x_2,...,x_N)$表示原始数据集。

  通过这种方式，PCA找到了一组新的基向量$W$，这些基向量不仅能够最大程度地保留原始数据的方差信息，还能有效地降低数据的维度，从而简化后续的数据分析和处理工作。

（4）PCA优化求解

  PCA（主成分分析）的目标是找到一个矩阵$W\in {\mathbb{R}}^{D\times D^{\prime }}$，使得${\max }_W\text{tr}(W^{T}SW)$，同时满足约束条件$W^{T}W=I$。这里的$S$是数据的协方差矩阵，$I$是单位矩阵。

1、求解步骤

  求解$W$的步骤如下：

1. 计算数据均值：
   $$\bar{x}=\frac{1}{N}\sum _{j=1}^N{x}_j$$

2. 数据中心化：
   $$x_i=x_i-\bar{x}$$
   其中，$X=[x_1{x}_2\cdots x_N]$。

3. 计算协方差矩阵：
   $$S=X{X}^T$$

4. 对$S$做特征分解：
   找到$S$的$D^{\prime }$个最大特征值对应的特征向量。

5. 选择$D^{\prime }$个最大特征值对应的特征向量：
   $$W=(w_1,w_2,\dots ,w_{D^{\prime }})$$

2、输出

  最终输出的$W$矩阵包含了$D^{\prime }$个最大特征值对应的特征向量，这些特征向量构成了新的坐标系，用于将原始数据投影到低维空间。

  通过这些步骤，PCA能够有效地降低数据的维度，同时保留数据的主要信息。这种方法在数据压缩、特征提取和可视化等领域有着广泛的应用。

（5）PCA优化求解(2)

  在PCA（主成分分析）中，我们的目标是将高维数据投影到低维空间，同时尽可能保留数据的变异性。以下是PCA优化求解的详细步骤：

1、输入

• 数据集 X = { x 1 , x 2 , … , x N } X = \{x_1, x_2, \ldots, x_N\} X={x1​,x2​,…,xN​}
• 低维空间的维数 $D^{\prime }$

2、算法过程

1. 数据中心化：
   $$x_i=x_i-\frac{1}{N}\sum _{j=1}^N{x}_j$$
   这一步确保每个数据点都减去数据的均值，使得数据中心位于原点。

2. 奇异值分解（SVD）：
   $$X=U_{D\times D}{\Sigma }_{D\times N}{V}_{N\times N}^T$$
   其中，$U$和$V$是正交矩阵，$\Sigma$是对角矩阵，包含了数据的奇异值。

3. 选择$D^{\prime }$个最大奇异值对应的左奇异向量：
   这些向量构成了新的坐标系，用于将原始数据投影到低维空间。

3、输出

• 矩阵 $U=(u_1,u_2,\dots ,u_{D^{\prime }})$
  这些向量是原始数据在低维空间中的表示。

  通过这些步骤，PCA能够有效地降低数据的维度，同时保留数据的主要信息。这种方法在数据压缩、特征提取和可视化等领域有着广泛的应用。PCA通过奇异值分解找到数据的主要方向，这些方向对应于数据中最大的变异性。

（6）超越线性：简单的解决方案

  在某些情况下，数据的分布可能不是线性的，这意味着传统的线性方法如PCA可能无法有效地捕捉数据的结构。为了解决这个问题，我们可以考虑使用非线性方法。

1、图示说明

• 左图（PCA有效）：展示了PCA在数据分布接近线性时的有效性。红色直线表示主成分，它捕捉了数据的主要变异性。
• 中图（PCA无效）：展示了当数据分布非线性时，PCA可能无法有效捕捉数据结构的情况。
• 右图（预期的解）：展示了通过非线性映射后，数据分布变得更加线性，从而可以通过线性方法进行有效分析。

2、非线性映射与降维

  对$x$进行非线性映射，然后再降维： S = { ϕ ( x ) = W z } S = \{\phi(x) = Wz\} S={ϕ(x)=Wz}

• $\varphi (x)$空间的线性降维   $⟷$    $x$空间的非线性降维

3、如何选择$\varphi (x)$

  选择合适的非线性映射函数$\varphi (x)$是一个关键问题，需要考虑以下几点：

1. 启发式的解决方案（可能性太多）：有许多可能的非线性映射函数可供选择，需要根据具体问题进行选择。
2. $\varphi (x)$维度高，计算开销大：非线性映射可能会增加数据的维度，从而增加计算的复杂性和资源需求。

  通过非线性映射，我们可以将原本非线性分布的数据转换为更接近线性分布的形式，从而使得线性方法如PCA能够有效地应用于数据降维和特征提取。

2、核化PCA

（1）表示理论

  在PCA中，投影向量/主成分方向$w_d$可以表示为$x_i$的线性组合。具体来说，PCA可以转换成特征值问题：

$$X{X}^T{w}_d=\lambda w_d$$

  进一步展开，可以得到：

$$w_d=\frac{1}{\lambda }X{X}^T{w}_d=\frac{1}{\lambda }\sum _{i=1}^N{x}_i{x}_i^T{w}_d=\sum _{i=1}^N\frac{1}{\lambda }{x}_i^T{w}_d\cdot {\alpha }_{d,i}{x}_i$$

  这与支持向量机（SVMs）中的权重向量$w$的计算方式相似：

$$w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$$

（2）核化PCA推导

  PCA的特征值问题可以表示为：

$$X{X}^T{w}_d=\lambda w_d\Rightarrow w_d=X{\alpha }_d$$

  将$w_d=X{\alpha }_d$代入$X{X}^T{w}_d=\lambda w_d$，得到：

$$X{X}^{T}X{\alpha }_d={\lambda }_{d}X{\alpha }_d$$

  两边同乘以$X^T$，得到：

$$(X^{T}X)(X^{T}X){\alpha }_d={\lambda }_d(X^{T}X){\alpha }_d$$

  两边同乘以$(X^{T}X{)}^{-1}$，得到：

$$(X^{T}X){\alpha }_d={\lambda }_d{\alpha }_d$$

  将内积矩阵$(X^{T}X)$用核矩阵$K$表示，得到核PCA的目标：

$$K{\alpha }_d={\lambda }_d{\alpha }_d$$

  其中核矩阵元素$k_{ij}=x_i^T{x}_j=k(x_i,x_j)$，即对核矩阵$K$进行特征值分解，${\alpha }_d$为特征值${\lambda }_d$对应的特征向量。

  将${\alpha }_d$代入$w_d=X{\alpha }_d$，可得到第$d$个投影方向$w_d$，$d=1,2,\dots ,D^{\prime }$。

（3）投影矩阵和低维表示

  得到投影向量$w_d=X{\alpha }_d$后，将$D^{\prime }$个$w_d$组合，得到投影矩阵：

$$W=XA$$

  其中，

$$W=\left(\begin{array}{cccc}{x}_{1,1}& x_{2,2}& \cdots & x_{N,1}\\ x_{1,2}& x_{2,2}& \cdots & x_{N,2}\\ ⋮& ⋮& \ddots & ⋮\\ x_{1,D}& x_{2,D}& \cdots & x_{N,D}\end{array}\right),A=\left(\begin{array}{cccc}{\alpha }_{1,1}& {\alpha }_{1,2}& \cdots & {\alpha }_{1,D^{\prime }}\\ {\alpha }_{2,1}& {\alpha }_{2,2}& \cdots & {\alpha }_{2,D^{\prime }}\\ ⋮& ⋮& \ddots & ⋮\\ {\alpha }_{N,1}& {\alpha }_{N,2}& \cdots & {\alpha }_{N,D^{\prime }}\end{array}\right)$$

  对任意样本$x$，可得到其低维表示$z$为：

$$z=W^{T}x=(XA{)}^{T}x=A^T{X}^{T}x=A^T\left(\begin{array}{c}k(x_1,x)\\ k(x_2,x)\\ ⋮\\ k(x_N,x)\end{array}\right)=\left(\begin{array}{c}{\sum }_{i=1}^N{\alpha }_{i,1}k(x_i,x)\\ {\sum }_{i=1}^N{\alpha }_{i,2}k(x_i,x)\\ ⋮\\ {\sum }_{i=1}^N{\alpha }_{i,D^{\prime }}k(x_i,x)\end{array}\right),k(x_i,x_j)=x_i^T{x}_j$$

（4）KPCA 算法

  KPCA（核主成分分析）是一种非线性降维技术，它通过将数据映射到高维空间来实现线性不可分数据的线性化。以下是KPCA算法的步骤：

1. 计算核矩阵 $K$：
   $$k_{ij}=k(x_i,x_j)$$
   其中，$k(x_i,x_j)$是任意核函数，用于计算数据点$x_i$和$x_j$之间的相似度。

2. 中心化核矩阵：对核矩阵$K$进行中心化处理，得到$\bar{K}$。

3. 特征分解：对中心化的核矩阵$\bar{K}$进行特征分解。

4. 选择特征向量：选择$D^{\prime }$个最大的特征值对应的特征向量${\alpha }_1,...,{\alpha }_{D^{\prime }}$（$\alpha$为$N$维向量，通常对$\alpha$进行归一化，模长为1）。

5. 低维表示：对于新样本$x$，可以得到其低维表示$z$为：
   $$z=\left(\begin{array}{c}{\sum }_{i=1}^N{\alpha }_{i,1}k(x_i,x)\\ {\sum }_{i=1}^N{\alpha }_{i,2}k(x_i,x)\\ ⋮\\ {\sum }_{i=1}^N{\alpha }_{i,D^{\prime }}k(x_i,x)\end{array}\right)$$
   其中，$k(x_i,x_j)=x_i^T{x}_j$表示样本间的内积。

（5）示例

  输入1000幅28*28图像，分别采用KPCA、PCA和ICA降维，得到的基向量/投影方向如下：

• 训练图像：展示了原始的28*28图像。
• KPCA：先全局变化后局部变化。
• PCA：全局变化。
• ICA：局部变化。

  这些图像展示了不同降维方法在处理图像数据时的效果差异。KPCA通过非线性映射能够捕捉到数据的非线性结构，而PCA和ICA则主要关注数据的全局和局部变化。

图片来源：Kernel PCA vs PCA vs ICA in TensorFlow-Sklearn

3、自编码器（神经网络部分讲解）

四、基于全局结构保持的降维

1、多维缩放（MDS）

（1）问题形式化

在多维缩放（MDS）中，我们面临的问题是：

  - 给定空间中任意两个点的距离。
  - 距离保持：我们希望将这些点嵌入到一个低维空间中，使得新的空间中点对之间的距离和原始空间中的距离尽可能接近。显然，投影到低维空间的形式不是唯一的，原因是低维空间的点经过平移、旋转和镜像后，点对之间的距离不变。

示例：绘制地图（城市嵌入）

在平面坐标上根据标出这10个城市之间的相对位置，使之尽可能接近表中的距离数据。

（2）MDS的形式化

  - 令矩阵 $Z\in {\mathbb{R}}^{D^{\prime }\times N}$ 表示所有样本点在 $D^{\prime }$ 维（低维）空间中的表示。
  - 基本思想：$D^{\prime }$ 空间的欧式距离等于原始空间的欧式距离，例如
$$\Vert z_i-z_j\Vert =d_{i,j}$$
  - 如何计算 $z_i$？

高维空间点两两之间的距离矩阵尽可能地接近低维空间的距离矩阵。问题看起来也有点像矩阵近似问题？如果是矩阵近似问题，就可以用我们的老朋友：特征值分解。

（3）$B$ 的推导

1、假设与推导

  不失一般性，我们假设低维空间中的样本是中心化的，即 ${\sum }_{i=1}^N{z}_i=0$。

  $d_{i,j}=\Vert z_i-z_j\Vert$，所以：$d_{i,j}^2=\Vert z_i-z_j{\Vert }^2=\Vert z_i{\Vert }^2+\Vert z_j{\Vert }^2-2z_i^T{z}_j$。

  看起来和 $z_i^T{z}_j$ 相关，所以考虑内积矩阵 $B=Z^{T}Z$，即 $b_{ij}=z_i^T{z}_j$，用已知的 $d_{i,j}$ 表示 $B$，再将 $B$ 进行分解，得到 $Z$。

2、求和与简化

  对上述等式两边求和（每列距离和）：
$$\sum _{i=1}^N{d}_{i,j}^2=\sum _{i=1}^N\left(\Vert z_i{\Vert }^2+\Vert z_j{\Vert }^2-2z_i^T{z}_j\right)$$
$$=\sum _{i=1}^N\Vert z_i{\Vert }^2+N\Vert z_j{\Vert }^2-2z_j\sum _{i=1}^N{z}_i\text{（因为 ∑i=1Nzi=0）}$$
$$=\sum _{i=1}^N\Vert z_i{\Vert }^2+N\Vert z_j{\Vert }^2$$

3、所有点对的距离和

  类似的，得到：
$$\sum _{i=1}^N{d}_{i,j}^2=\sum _{i=1}^N\Vert z_i{\Vert }^2+N\Vert z_j{\Vert }^2\text{（每行的距离和）}$$
$$\sum _{i=1}^N\sum _{j=1}^N{d}_{i,j}^2=\sum _{i=1}^N\left(\sum _{j=1}^N\Vert z_j{\Vert }^2+N\Vert z_i{\Vert }^2\right)\text{（所有点对的距离和）}$$
$$=N\sum _{j=1}^N\Vert z_j{\Vert }^2+N\sum _{i=1}^N\Vert z_i{\Vert }^2$$
$$=2N\sum _{i=1}^N\Vert z_i{\Vert }^2$$

4、平均距离

  （每列的平均距离）
$$\frac{1}{N}\sum _{i=1}^N{d}_{i,j}^2=\frac{1}{N}\sum _{i=1}^N\Vert z_i{\Vert }^2+\Vert z_j{\Vert }^2$$
（每行的平均距离）
$$\frac{1}{N}\sum _{j=1}^N{d}_{i,j}^2=\frac{1}{N}\sum _{j=1}^N\Vert z_j{\Vert }^2+\Vert z_i{\Vert }^2$$
（总的平均距离）
$$\frac{1}{N^2}\sum _{i=1}^N\sum _{j=1}^N{d}_{i,j}^2=\frac{2}{N}\sum _{i=1}^N\Vert z_i{\Vert }^2$$

5、进一步推导

  $\frac{1}{N}{\sum }_{i=1}^N{d}_{i,j}^2=\frac{1}{N}{\sum }_{i=1}^N\Vert z_i{\Vert }^2+\Vert z_j{\Vert }^2$
$$\frac{1}{N}\sum _{j=1}^N{d}_{i,j}^2=\frac{1}{N}\sum _{j=1}^N\Vert z_j{\Vert }^2+\Vert z_i{\Vert }^2$$
$$\frac{1}{N^2}\sum _{i=1}^N\sum _{j=1}^N{d}_{i,j}^2=\frac{2}{N}\sum _{i=1}^N\Vert z_i{\Vert }^2$$

  $\Vert z_j{\Vert }^2=\frac{1}{N}{\sum }_{i=1}^N(d_{i,j}^2-\Vert z_i{\Vert }^2)$
$$\Vert z_i{\Vert }^2=\frac{1}{N}\sum _{j=1}^N(d_{i,j}^2-\Vert z_j{\Vert }^2)$$
$$2\sum _{i=1}^N\Vert z_i{\Vert }^2=\frac{1}{N^2}\sum _{i=1}^N\sum _{j=1}^N{d}_{i,j}^2$$

6、用 $D$ 表示 $B$

  $d_{i,j}^2=\Vert z_i-z_j{\Vert }^2=\Vert z_i{\Vert }^2+\Vert z_j{\Vert }^2-2z_i^T{z}_j=b_{i,i}+b_{j,j}-2b_{i,j}$

  用 $D$ 表示 $B$
$$b_{i,j}=-\frac{1}{2}(d_{i,j}^2-b_{i,i}-b_{j,j})$$
$$=-\frac{1}{2}\left(d_{i,j}^2-\frac{1}{N}\sum _{j=1}^N{d}_{i,j}^2-\frac{1}{N}\sum _{i=1}^N{d}_{i,j}^2+\frac{1}{N^2}\sum _{i=1}^N\sum _{j=1}^N{d}_{i,j}^2\right)$$
$$=-\frac{1}{2}\left(d_{i,j}^2-\frac{1}{N}\sum _{j=1}^N{d}_{i,j}^2-\frac{1}{N}\sum _{i=1}^N{d}_{i,j}^2+\frac{2}{N}\sum _{i=1}^N\Vert z_i{\Vert }^2\right)$$
$$=\frac{1}{2}\left(d_{i,j}^2-\frac{1}{N}\sum _{j=1}^N{d}_{i,j}^2-\frac{1}{N}\sum _{i=1}^N{d}_{i,j}^2+\frac{1}{N^2}\sum _{i=1}^N\sum _{j=1}^N{d}_{i,j}^2\right)$$

7、矩阵表示

  用矩阵表示：$B=-\frac{1}{2}JDJ$，其中 $J=I_N-\frac{1}{N}11^T$ 为中心化矩阵，$1=(1,1,\dots ,1{)}^T$

  $DJ$ 为从 $D$ 中的每个元素里减去列均值，$JDJ$ 的作用就是在此基础上再减去行均值，因此中心化矩阵的作用就是把元素的中心平移到坐标原点。

  中心化过程相当于平移，并不会改变低维度点之间的距离。

8、补充：中心化矩阵

（1）中心化矩阵的定义

  对于矩阵 $A$，我们可以通过以下方式进行中心化处理：

$$\frac{1}{N}A11^T=\frac{1}{N}\left[\begin{array}{cccc}{a}_{1,1}& a_{1,2}& \cdots & a_{1,N}\\ a_{2,1}& a_{2,2}& \cdots & a_{2,N}\\ ⋮& ⋮& \ddots & ⋮\\ a_{N,1}& a_{N,2}& \cdots & a_{N,N}\end{array}\right]\left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]=\frac{1}{N}\left[\begin{array}{cccc}{\sum }_{i=1}^N{a}_{1,i}& {\sum }_{i=1}^N{a}_{1,i}& \cdots & {\sum }_{i=1}^N{a}_{1,i}\\ {\sum }_{i=1}^N{a}_{2,i}& {\sum }_{i=1}^N{a}_{2,i}& \cdots & {\sum }_{i=1}^N{a}_{2,i}\\ ⋮& ⋮& \ddots & ⋮\\ {\sum }_{i=1}^N{a}_{N,i}& {\sum }_{i=1}^N{a}_{N,i}& \cdots & {\sum }_{i=1}^N{a}_{N,i}\end{array}\right]$$

  第 $i$ 行的每个元素都是 $A$ 中第 $i$ 行的均值。

（2）列均值的处理

  类似的，$\frac{1}{N}11^{T}A$ 的第 $j$ 列的每个元素都是 $A$ 中第 $j$ 列的均值。

（3）中心化矩阵的定义

  因此定义中心化矩阵：$J=I_N-\frac{1}{N}11^T$

（4）中心化矩阵的作用

  $DJ$ 为从 $D$ 中的每个元素里减去列均值，$JDJ$ 的作用就是在此基础上再减去行均值，因此中心化矩阵的作用就是把元素分布的中心平移到坐标原点。

  中心化过程相当于平移，并不会改变低维度点之间的距离。

（4）MDS（多维缩放）应用实例

1、MDS 特征值分解

  对 $B=Z^{T}Z$ 做特征值分解：
$$B=V\Lambda V^T$$
其中 $\Lambda =\text{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_D)$，${\lambda }_1>{\lambda }_2>\cdots >{\lambda }_D>0$，$V$ 是对应的特征向量组成的矩阵，则：
$$Z={\Lambda }^{1/2}{V}^T\in {\mathbb{R}}^{D\times N}$$
  实际上，我们使用 $D^{\prime }\ll D$ 特征值矩阵 $\tilde{\Lambda }=\text{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_{D^{\prime }})$
$$Z={\tilde{\Lambda }}^{1/2}{\tilde{V}}^T\in {\mathbb{R}}^{D^{\prime }\times N}$$

2、例子：MDS

  假设我们有5种水果：苹果、香蕉、橙子、葡萄和菠萝。我们对这些水果进行了甜度（Sweetness）、酸度（Sourness）和多汁程度（Juiciness）的评分。评分数据如下：

水果	甜度	酸度	多汁程度
苹果	6	4	5
香蕉	8	1	3
橙子	5	7	6
葡萄	7	3	4
菠萝	4	6	8

计算距离矩阵 $d_{ij}$

  根据水果的评分数据，我们计算出距离矩阵 $d_{ij}$，表示每种水果之间的距离：

	苹果	香蕉	橙子	葡萄	菠萝
苹果	0	4.69	3.74	2.45	3.32
香蕉	4.69	0	6.56	3.32	6.56
橙子	3.74	6.56	0	5.29	2.45
葡萄	2.45	3.32	5.29	0	5.29
菠萝	3.32	6.56	2.45	5.29	0

  通过计算距离矩阵 $d_{ij}$，我们可以更直观地了解不同水果之间的相似性。距离越小，表示两种水果在甜度、酸度和多汁程度上的评分越接近。

1. 计算中心化矩阵
   $$J=I_N-\frac{1}{N}11^T=\left(\begin{array}{cccc}0.8& -0.2& -0.2& -0.2\\ -0.2& 0.8& -0.2& -0.2\\ -0.2& -0.2& 0.8& -0.2\\ -0.2& -0.2& -0.2& 0.8\end{array}\right)$$

2. 计算距离平方矩阵 $d_{ij}^2$
   $$D=\left(\begin{array}{ccccc}0.00& 21.98& 13.99& 6.00& 11.02\\ 21.98& 0.00& 43.03& 11.02& 43.03\\ 13.99& 43.03& 0.00& 28.00& 6.00\\ 6.00& 11.02& 28.00& 0.00& 28.00\\ 11.02& 43.03& 6.00& 28.00& 0.00\end{array}\right)$$

3. 用中心化矩阵 $J$ 和距离平方矩阵 $D$ 计算内积矩阵 $B$
   $$B=-\frac{1}{2}JDJ=\left(\begin{array}{ccccc}2.12& -2.27& -1.07& 1.12& 0.11\\ -2.27& 15.33& -8.99& 5.21& -9.29\\ -1.07& -8.99& 9.72& -6.07& 6.42\\ 1.12& 5.21& -6.07& 6.12& -6.37\\ 0.11& -9.29& 6.42& -6.37& 9.13\end{array}\right)$$

4. 计算 $B$ 的特征值和特征向量
   $${\lambda }_1\approx 32.32,v_1\approx (-0.02,0.63,-0.48,0.36,-0.49)$$
   $${\lambda }_2\approx 6.39,v_2\approx (-0.53,0.59,0.33,-0.10,0.10)$$

5. 计算降维后的新坐标
   $$\tilde{V}=\left(\begin{array}{cc}-0.02& -0.53\\ 0.63& 0.59\\ -0.48& 0.33\\ 0.36& -0.50\\ -0.49& 0.10\end{array}\right)$$
   $${\tilde{\Lambda }}^{1/2}=\left(\begin{array}{cc}\sqrt{32.32}& 0\\ 0& \sqrt{6.39}\end{array}\right)$$
   降维后的新坐标：
   $$Z={\tilde{\Lambda }}^{1/2}{\tilde{V}}^T=\left(\begin{array}{cc}-0.11& -1.33\\ 3.60& 1.50\\ -2.76& 0.84\\ 2.02& -1.26\\ -2.76& 0.25\end{array}\right)$$
   
   

3、如何在不丢失重要信息的情况下最大限度地降低维度？

  肘部法：计算不同维度（$n\_components$）对应的拟合优度统计量（stress）
$$\text{stress}:\sum _{i<j}{d}_{ij}-{\hat{d}}_{ij}$$

4、实例：MNIST

  PCA 保持大部分全局结构

  MDS 虽然目标函数看起来很合理但没有得到有意义的结果

  维数灾难：高维空间中，最短距离也很远

2、Isomap

（1）流形（Manifold）学习

  在高维空间中，欧氏距离不能准确地反映数据内在的相似性。如图所示，数据在高维空间中可能呈现出复杂的几何结构，如线性结构、S形结构和瑞士卷结构。这些结构在欧氏空间中可能被扭曲或拉伸，导致相似的数据点之间的距离被错误地表示。

  流形是指局部具有欧氏距离性质的拓扑空间。通过流形学习，我们可以更好地理解和表示高维数据的内在结构。

（2）测地线距离（Geodesic Distance）

  在高维空间中如何度量距离？如图所示，直接使用欧氏距离可能无法准确反映数据点之间的真实距离。因此，我们应该使用测地距离，而不是直接使用欧氏距离。

  测地距离的定义如下：

• 对于邻近的点：输入空间中的欧氏距离提供一个测地线距离的近似。
• 对于较远的点：测地距离能够通过一系列邻域点之间的欧氏距离的累加近似。

（3）IsoMAP算法

  IsoMAP是一种非线性降维方法，基于度量多维尺度分析（MDS），试图保留数据内在的由测地距离蕴含的几何结构。IsoMAP算法的三个步骤如下：

1. 构建邻接图
2. 计算最短路径（测地距离）
3. 构建低维嵌入：保持点对之间的测地距离（采用MDS）

通过这些步骤，IsoMAP能够将高维数据映射到低维空间中，同时尽可能地保留数据的内在几何结构。

（4）构建邻接图

  所有数据点构成相似图：带权无向图 $G(\mathcal{V},\mathcal{E})$

• 结点集合 V = { v 1 , v 2 , . . . , v N } \mathcal{V} = \{v_1, v_2, ..., v_N\} V={v1​,v2​,...,vN​}，$N$ 表示节点数目，$v_i$ 表示数据点 $x_i$
• 结点之间可以用边连接：边的集合 E = { e i j , i , j = 1 , . . . , N } \mathcal{E} = \{e_{ij}, i, j = 1, ..., N\} E={eij​,i,j=1,...,N}
• $e_{ij}$ 表示结点 $v_i$ 和 $v_j$ 之间边，其权重 $w_{ij}$：结点 $v_i$ 和 $v_j$ 的相似性/距离
  

  全连接图对大多数场合来说不现实（图太大），所以一般建立局部连接图：如果 $x_i$ 和 $x_j$ 距离 $d_{ij}$ 较近，则结点 $v_i$ 和 $v_j$ 连一条边。

  边创建的两个准则：

• $\epsilon$ 邻域（$\epsilon$-neighborhood）：如果 $d_{ij}<\epsilon (\epsilon \in {\mathbb{R}}^{+})$，结点 $v_i$ 和 $v_j$ 之间连一条边；
• $K$ 近邻：如果 $x_i$ 是 $x_j$ 的 $K$ 个最近邻之一且/或 $x_j$ 是 $x_i$ 的 $K$ 个最近邻之一，则结点 $v_i$ 和 $v_j$ 之间连一条边。
  

（5）计算最短路径

  数据集 $X$ 中任意两个点的距离为 $d_{i,j}$
  计算最短路径：

• 如果 $i$ 和 $j$ 相连接，初始化 $d_G(i,j)=d_{ij}$；否则 $d_G(i,j)=\infty$。
• 对于每一个 $k=1,2,...,N$，替换所有的 $d_G(i,j)$ 为 $\min (d_G(i,j),d_G(i,k)+d_G(k,j))$，则 $D_G=[d_G(i,j)]$ 包含 $G$ 中所有点对的最短路径。

（6）ISOMAP算法

  ISOMAP算法中有两个瓶颈：

• 最短路径的计算

  • Floyd算法: $O(N^3)$
  • Dijkstra算法（利用Fibonacci堆）: $O(K{N}^2\log N)$，其中$K$为近邻数

• 特征分解: $O(N^3)$

Dijkstra是荷兰的计算机科学大师，发音是/ˈdɑːɪkstrə/，/k/音不发。

（7）例：数字“2”图像

  下图展示了数字“2”的图像示例，图中通过底部环状结构（Bottom loop articulation）和顶部拱形结构（Top arch articulation）展示了数字“2”的形状特征。