降维算法之t-SNE (t-Distributed Stochastic Neighbor Embedding)-点头深度学习网站

t-SNE是一种用于探索高维数据结构的非线性降维技术。它特别适用于高维数据的可视化，因为它能够在低维空间中保留原始高维数据的局部结构。由于这个特性，t-SNE在机器学习和数据分析领域越来越受到重视。

1 算法解读：

t-SNE的核心思想是在高维空间中为数据点之间定义一种概率分布，表示点与点之间的相似性，然后在低维空间中创建一个相似的概率分布。通过最小化这两个分布之间的差异（使用KL散度），算法将高维数据映射到低维空间，以便我们可以可视化。

2 步骤和细节：

Step 1. 计算高维空间中的相似度

我们使用高斯分布（正态分布）来计算点之间的相似性。高斯分布是一种常见的概率分布，其形状呈钟型，由均值和方差（标准差的平方）决定。高斯分布有一个很好的性质：它的形状由均值（中心点）和方差（分布的宽度）决定。当我们围绕一个数据点 x 画一个高斯分布时，这个分布会给予附近的点较高的概率值，而离得远的点则会有较低的概率值。这与我们直觉上对“相似性”的理解相一致：靠近的点更相似，远离的点不相似。

对于每个数据点 $x_i$ ，我们计算所有其他点 $x_j$ 与其的条件概率 $p_{j j i}$ 。这个概率反映了点 $x_j$ 是点 $x_i$ 的近邻的可能性。计算公式为:

$$p_{j \mid i}=\frac{\exp \left(-\left\|x_i-x_j\right\|^2 / 2 \sigma_i^2\right)}{\sum_{k \neq i} \exp \left(-|| x_i-x_k \|^2 / 2 \sigma_i^2\right)}$$

这里，分子部分计算了 $x_i$ 和 $x_j$ 之间的欧氏距离的平方（即 $-\left\|x_i-x_j\right\|^2$ ），然后通过高斯分布转换成概率。分母部分是一个归一化因子，确保所有 $p_{j \mid i}$ 的和为1。

$\sigma_i$ 是高斯分布的方差，决定了近邻的范围。不同的点可能有不同的密度，因此 $\sigma_i$ 对于每个点 $x_i$ 可能是不同的，需要通过一种叫做“困惑度”的量来确定。

最后，为了得到一个对称的相似度矩阵，我们取 $p_{j \mid i}$ 和 $p_{i \mid j}$ 的平均值得到 $p_{i j}$ :

$$p_{i j}=\frac{p_{j \mid i}+p_{i \mid j}}{2 n}$$

这样，我们就得到了一个对称的相似度矩阵，其中的每个元素 $p_{i j}$ 都反映了数据点 $x_i$ 和 $x_j$ 在高维空间中的相似性。

通过这一步，我们成功地量化了高维空间中数据点之间的相似性，为后续的低维空间嵌入奠定了基础。

Step 2. 初始化低维空间的点

这一步可以是随机初始化，只需保证初始化点的数量和原数据相同，维度更低即可。

Step 3. 计算低维空间的点的相似度

在t-SNE算法中，高维空间的相似度是通过高斯（正态）分布计算的，而低维空间的相似度是通过t分布（具体来说是自由度为1的t分布，也叫做柯西分布）计算的。这种设计的目的是为了解决“拥挤问题”。

当我们将高维空间中的数据点降维到低维空间时，数据点之间的距离会发生变化。特别是在低维空间中，点与点之间可用的空间更少，容易出现拥挤的情况。如果直接使用高斯分布来计算低维空间的相似度，那么低维空间中远离的点之间的相似度可能会被过高地估计，导致降维结果的可视化效果不佳。

t分布（自由度为1）有一个重要的特性：它的尾部比高斯分布更“厚”（heavy-tailed）。这意味着，在低维空间中，即使两个点距离较远，它们之间的相似度（通过t分布计算）也不会迅速减小到0。这有助于缓解拥挤问题，因为低维空间中远离的点之间的相似度会被较低地估计。对t分布不了解的同学详见数学专栏的博文或视频。

在低维空间中，我们计算点 $y_i$ 和 $y_j$ 之间的相似度 $q_{i j}$ 如下:

$$q_{i j}=\frac{\left(1+\left\|y_i-y_j\right\|^2\right)^{-1}}{\sum_{k \neq l}\left(1+\left\|y_k-y_l\right\|^2\right)^{-1}}$$

这个公式来源于自由度为 1 的t分布。分子部分计算了 $y_i$ 和 $y_j$ 之间的欧氏距离的平方，并转换成了概率。分母部分是一个归一化因子，确保所有的 $q_{i j}$ 之和为1。

通过这种方式，我们得到了低维空间中点之间的相似度矩阵 $\left\{q_{i j}\right\}$ 。接下来，t-SNE算法会试图使高维空间的相似度矩阵 $\left\{p_{i j}\right\}$ 和低维空间的相似度矩阵 $\left\{q_{i j}\right\}$ 尽可能地一致，从而得到合适的低维空间表示。

Step 4. 优化低维空间的点的位置

– 通过最小化 Kullback-Leibler 散度 (KL散度) 来优化低维空间中的点的位置。KL散度用于衡量高维空间和低维空间中的相似度分布之间的差异。

$$C=\sum_{i \neq j} p_{i j} \log \frac{p_{i j}}{q_{i j}}$$

– 使用梯度下降方法来最小化 KL散度，更新低维空间中的点的位置。

$$\frac{\delta C}{\delta y_i}=4 \sum_j\left(p_{i j}-q_{i j}\right)\left(y_i-y_j\right)\left(1+\left\|y_i-y_j\right\|^2\right)^{-1}$$

在梯度下降的计算中，输入是低维空间中每个点的坐标 $\left\{y_i\right\}$ 。这些坐标是我们要优化的参数。输出是低维空间中点与点之间的相似度 $\left\{q_{i j}\right\}$ 。这些相似度是由当前的低维坐标 $\left\{y_i\right\}$ 计算出来的。标签是高维空间中点与点之间的相似度 $\left\{p_{i j}\right\}$ 。这些相似度是已知的，因为它们是由原始高维数据计算得出的。

我们的目标是通过调整低维空间中的点的坐标 $\left\{y_i\right\}$ （即输入），使得由这些坐标计算出的相似度 $\left\{q_{i j}\right\}$ （即输出）尽可能接近已知的高维空间的相似度 $\left\{p_{i j}\right\}$ （即标签）。

为了实现这个目标，我们计算损失函数（即 KL 散度）相对于每个低维坐标的梯度，并使用这个梯度来更新低维坐标。这个过程会重复进行，直到达到预定的迭代次数，或者低维坐标的变化小于某个阈值。

3 举例：

我们可以考虑一个更复杂的例子。假设我们有四个四维的数据点，我们想将它们降维到二维空间：

$$X=\left\{\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{array}\right\}$$

3.1 计算高维空间中的相似度

计算两点间的欧氏距离的平方:

\begin{gathered} d_{12}^2=(1-5)^2+(2-6)^2+(3-7)^2+(4-8)^2=64 \\ d_{13}^2=(1-9)^2+(2-10)^2+(3-11)^2+(4-12)^2=256 \\ d_{14}^2=(1-13)^2+(2-14)^2+(3-15)^2+(4-16)^2=576 \\ d_{23}^2=(5-9)^2+(6-10)^2+(7-11)^2+(8-12)^2=64 \\ d_{24}^2=(5-13)^2+(6-14)^2+(7-15)^2+(8-16)^2=256 \\ d_{34}^2=(9-13)^2+(10-14)^2+(11-15)^2+(12-16)^2=64 \end{gathered}

计算条件概率

由于 $\sigma=1$ ，我们有:

\begin{gathered} p_{12}=\frac{e^{-\frac{64}{2}}}{e^{-\frac{64}{2}}+e^{-\frac{256}{2}}+e^{-\frac{576}{2}}} \approx 0.9933 \\ p_{13}=\frac{e^{-\frac{256}{2}}}{e^{-\frac{64}{2}}+e^{-\frac{256}{2}}+e^{-\frac{576}{2}}} \approx 0.0067 \\ p_{14}=\frac{e^{-\frac{576}{2}}}{e^{-\frac{64}{2}}+e^{-\frac{256}{2}}+e^{-\frac{576}{2}}} \approx 0 \end{gathered}

类似地，我们可以计算其他的 $p_{i j}$ 。

对称化

我们得到对称的相似度矩阵 $P$ ，其形式为:

$$P=\frac{1}{8}\left[\begin{array}{cccc} 0 & 0.9933 & 0.0067 & 0 \\ 0.9933 & 0 & 0.9933 & 0.0067 \\ 0.0067 & 0.9933 & 0 & 0.9933 \\ 0 & 0.0067 & 0.9933 & 0 \end{array}\right]$$

3.2 计算低维空间中的相似度

我们随机初始化低维空间中的点，例如:

$$Y=\left[\begin{array}{ll} 0.1 & 0.2 \\ 0.3 & 0.4 \\ 0.5 & 0.6 \\ 0.7 & 0.8 \end{array}\right]$$

计算低维空间中的相似度

计算低维空间中两点间的距离:

$$\begin{aligned} & d_{12}^{\text {low }}=(0.1-0.3)^2+(0.2-0.4)^2=0.04+0.04=0.08 \\ & d_{13}^{\text {low }}=(0.1-0.5)^2+(0.2-0.6)^2=0.16+0.16=0.32 \\ & d_{14}^{\text {low }}=(0.1-0.7)^2+(0.2-0.8)^2=0.36+0.36=0.72 \\ & d_{23}^{\text {low }}=(0.3-0.5)^2+(0.4-0.6)^2=0.04+0.04=0.08 \\ & d_{24}^{\text {low }}=(0.3-0.7)^2+(0.4-0.8)^2=0.16+0.16=0.32 \\ & d_{34}^{\text {low }}=(0.5-0.7)^2+(0.6-0.8)^2=0.04+0.04=0.08 \end{aligned}$$

计算低维空间中的相似度:

\begin{aligned} & q_{12}=\frac{\left(1+d_{12}^{\text {low }}\right)^{-1}}{\sum_{k \neq 1}\left(1+d_{1 k}^{\text {low }}\right)^{-1}}=\frac{(1+0.08)^{-1}}{(1+0.08)^{-1}+(1+0.32)^{-1}+(1+0.72)^{-1}} \approx 0.620 \\ & q_{13}=\frac{\left(1+d_{13}^{\text {low }}\right)^{-1}}{\sum_{k \neq 1}\left(1+d_{1 k}^{\text {low }}\right)^{-1}}=\frac{(1+0.32)^{-1}}{(1+0.08)^{-1}+(1+0.32)^{-1}+(1+0.72)^{-1}} \approx 0.238 \\ & q_{14}=\frac{\left(1+d_{14}^{\text {low }}\right)^{-1}}{\sum_{k \neq 1}\left(1+d_{1 k}^{\text {low }}\right)^{-1}}=\frac{(1+0.72)^{-1}}{(1+0.08)^{-1}+(1+0.32)^{-1}+(1+0.72)^{-1}} \approx 0.142 \end{aligned}

类似地，我们可以计算其他的 $q_{i j}$ ，然后对称化得到矩阵 $Q$:

$$Q=\frac{1}{8}\left[\begin{array}{cccc} 0 & 0.620 & 0.238 & 0.142 \\ 0.620 & 0 & 0.620 & 0.238 \\ 0.238 & 0.620 & 0 & 0.620 \\ 0.142 & 0.238 & 0.620 & 0 \end{array}\right]$$

优化低维空间的点位置

我们使用梯度下降来优化低维空间中的点的位置。其中，

– 输入：这里的输入是低维空间中的点的坐标（初始通常是随机的），我们通过梯度下降来更新这些坐标，使得低维空间中的相似度矩阵$Q$接近高维空间的相似度矩阵$P$。

– 输出: 经过优化后，低维空间中的点的坐标就是我们的输出。

– 标签: 在这个优化问题中，我们可以将高维空间中的点的相似度 $P$ 视作是“标签”，因为我们的目标是使低维空间中的点的相似度 $Q$ 尽可能地接近 $P$ 。

在这个意义上，我们是以低维空间的相似度为输入，以高维空间的相似度为标签，通过梯度下降来调整低维空间中的点的坐标，使得两者尽可能一致。

4. 代码实现

import numpy as np
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt
# 定义高维数据点
X = np.array([
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
])
# 初始化 t-SNE
tsne = TSNE(n_components=2, random_state=42, perplexity=3)
# 进行 t-SNE 降维
X_tsne = tsne.fit_transform(X)
# 可视化结果
plt.scatter(X_tsne[:, 0], X_tsne[:, 1])
for i, txt in enumerate(['Point 1', 'Point 2', 'Point 3', 'Point 4']):
    plt.annotate(txt, (X_tsne[i, 0], X_tsne[i, 1]))
plt.title('t-SNE Visualization')
plt.xlabel('Dimension 1')
plt.ylabel('Dimension 2')
plt.show()

图片[1]-降维算法之t-SNE (t-Distributed Stochastic Neighbor Embedding)-点头深度学习网站

import numpy as np
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.cm as cm
# 生成一个三维数据集
np.random.seed(0)
X_3D = np.random.rand(50, 3)
# 创建一个颜色映射
colors = cm.rainbow(np.linspace(0, 1, len(X_3D)))
# 可视化三维数据
fig = plt.figure(figsize=(10, 5))
ax = fig.add_subplot(121, projection='3d')
ax.scatter(X_3D[:, 0], X_3D[:, 1], X_3D[:, 2], c=colors, marker='o')
ax.set_title('Original 3D Data')
# 使用t-SNE降维到2维
tsne = TSNE(n_components=2, random_state=42)
X_2D = tsne.fit_transform(X_3D)
# 可视化降维后的2D数据
ax2 = fig.add_subplot(122)
ax2.scatter(X_2D[:, 0], X_2D[:, 1], c=colors, marker='o')
ax2.set_title('2D Data after t-SNE')
plt.tight_layout()
plt.show()