开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 人工智能 -> t-SNE -> 正文阅读

[人工智能]t-SNE

t-SNE

文章目录

t-SNE

t-SNE是一种可视化高维数据的工具。它将数据点之间的相似性转换为联合概率，并尝试最小化低维嵌入和高维数据的联合概率之间的Kullback-Leibler散度。t-SNE有一个非凸的代价函数，即通过不同的初始化，我们可以得到不同的结果。

原理

SNE(Stochastic Neighbor Embedding)

随机领域嵌入（SNE）首先将数据点之间的高维欧几里得距离转换为表示相似性的条件概率。数据点 $x_i$ 选择数据点 $x_j$ 作为邻居的条件概率为 $P_{j|i}$ 。如果在以 $x_{i}$ 为中心的高斯分布下，按照概率密度的比例选择邻居，对于相近的点， $P_{j|i}$ 会相对比较高；对于广泛分离的数据点， $P_{j|i}$ 会无穷小。 $p_{j|i}$ 的数学定义如下：
$p_{j|i} = \frac{exp \left( - \left \| x_{i} - x_{j} \right \|^{2} / 2 \sigma_{i}^{2} \right)}{\sum_{k \neq i } exp \left( - \left \| x_{i} - x_{k} \right \|^{2} / 2 \sigma_{i}^{2} \right)}$

$\sigma_{i}$ 是以数据点 $x_{i}$ 为中心的方差。因为我们对模型成对相似性感兴趣，设置 $p_{i|i}=0$ 。

高维空间数据点 $x_i$ 和 $x_j$ 在低维空间相对应的是 $y_i$ 和 $y_{j}$ ，也需要计算相似的条件概率 $q_{j|i}$ 。设置应用在条件概率 $q_{j|i}$ 中的高斯方差为 $\frac{1}{\sqrt(2)}$ ， $q_{j|i}$ 公式表示如下：
$q_{j|i} = \frac{exp\left( - \left \| y_{i} - y_{j} \right \| ^{2} \right)}{\sum_{k \neq i } exp\left( - \left \| y_{i} - y_{k} \right \| ^{2} \right)}$
同样地，我们仅仅对模型成对相似性感兴趣，设置 $q_{i|i}=0$ 。

如果数据点 $y_i$ 和 $y_{j}$ 能够正确地模拟高维空间数据点 $x_i$ 和 $x_j$ 的相似性，那么 $p_{j|i}=q_{j|i}$ 。受到此观察的启示，SNE的目的是找到一种低维数据表示法，最大限度地减少 $q_{j|i}$ 和 $P_{j|i}$ 之间的不匹配。为了实现这一目的，采用KL散度计算 $p_{ij}$ 和 $q_{ij}$ 的相似性。SNE使用梯度下降方法最小化所有数据点上的KL散度之和。损失函数定义如下：

$\sum_{i} \sum_{j} p_{j|i} log \; \frac{p_{j|i}}{q_{j|i}} = \sum_{i} KL \left( P_{i} || Q_{i}\right)$

$Q_{i}$ 表示给定数据点 $x_{i}$ 的所有其他数据点上的条件概率分布； $P_{i}$ 表示映射数据点 $y_{i}$ 的所有其他数据点上的条件概率分布。

由于KL散度是非对称的，因此低维映射中成对距离中不同类型的误差加权不相等。特别是，使用广泛分离的映射点来表示附近的数据点的成本很大（比如，使用小的 $q_{j|i}$ 建模大的 $p_{j|i}$ ），但是使用附近的映射点来表示广泛分离的数据点的成本很小。这个小成本来自于在相关 $Q$ 分布中浪费一些概率质量。换句话说，SNE成本函数侧重于保留地图中数据的局部结构。

要选择的参数是以高维数据点 $x_{i}$ 为中心的方差 $\sigma_{i}$ 。对于数据集中的所有数据点，不可能有一个单一的 $\sigma_{i}$ 值是最优的，因为数据的密度可能会有变化。在密集区域，一个较小的 $\sigma_{i}$ 通常比稀疏区域更合适。 $\sigma_{i}$ 的任何特定值都会在所有其他数据点上产生概率分布 $P_{i}$ 。该分布的熵随 $\sigma_{i}$ 的增加而增加。SNE对 $\sigma_{i}$ 的值执行二进制搜索，该值产生一个 $P_{i}$ ，该 $P_{i}$ 具有用户指定的固定复杂度。复杂度定义为 $Perp\left( P_{i} \right) = 2^{H\left( P_{i} \right)}$ ，其中 $H\left( P_{i}\right)$ 是 $P_{i}$ 的香农熵，定义为 $H\left( P_{i}\right) = -\sum_{j}p_{j|i}log_{2}p_{j|i}$ 。复杂度可以解释为有效邻域数的平滑度量。SNE的性能对复杂度的变化相当稳健，典型值在5到50之间。

最小化成本函数，使用梯度下降方法执行。梯度有一个简单的形式如下：
$\frac{\delta C}{\delta y_{i}} = 2 \sum_{j} \left( y_{i} - y_{j }\right) \left( p_{ij} - q_{ij} + p_{ji} - q_{ji} \right)$

从物理上讲，梯度可以解释为映射点 $y_i$ 和所有其他映射点 $y_{j}$ 之间的一组弹簧产生的合力。所有弹簧沿着 $y_{i} - y_{j}$ 的方向施加力。 $y_{i}$ 和 $y_{j}$ 之间的弹簧排斥或吸引映射点，这取决于映射点之间的距离是否太小或者太大，以表示两个高维数据点之间的相似性。 $y_{i}$ 和 $y_{j}$ 之间弹簧施加的力于其长度成正比，也与其刚度成正比，与数据点和映射点的成对相似性 $\left( p_{ij} - q_{ij} + p_{ji} - q_{ji} \right)$ 不匹配。
梯度下降是通过从以原点为中心的具有小方差的各向同性高斯随机采样映射点来初始化的，使用moneutum优化。
$\Upsilon^{\left( t \right)} = \Upsilon^{\left( t - 1 \right)} + \eta \frac{\partial C }{\partial \Upsilon} + \alpha\left( t \right)\left( \Upsilon^{\left( t - 1 \right)} - \Upsilon^{\left( t - 2 \right)} \right)$
其中 $\Upsilon^{\left( t \right)}$ 表示在 $t$ 步的解， $\eta$ 表示学习率， $\alpha\left( t \right)$ 表示在 $t$ 步的动量。

t-SNE

尽管SNE具有相当好的可视化效果，但它受到难以优化的成本函数的阻碍，我们称之为“拥挤问题”。t-SNE与SNE不同的地方在两个方面：

t-SNE使用了SNE成本函数的对称版本，具有更简单的梯度。
在低维空间中，t-SNE使用student-t分布而不是高斯分布计算相似性。

t-SNE 采用低维空间中的重尾分布（a heavy-tailed distribution）来缓解拥挤问题和优化问题。

对称SNE

作为最小化条件概率 $P_{j|i}$ 和 $q_{j|i}$ 之间的KL散度之和的替代方法，也可以最小化在高维空间中的**联合概率分布 $P$ 和在低维空间中的联合概率分布 $Q$ **之间的单个KL散度。
$\left( P || Q \right) = \sum_{i} \sum_{j} p_{ij} log \; \frac{p_{ij}}{q_{ij}}$

同样，设置 $p_{ii}=0$ 和 $q_{ii}=0$ ，因为 $p_{ij}=p_{ji}$ 和 $q_{ij}=q_{ji}$ 的性质，我们将这种类型的SNE看做对称SNE。在低维空间映射 $q_{ij}$ 公式定义如下：

$q_{ij} = \frac{exp\left( - \left \| y_{i} - y_{j} \right \| ^{2} \right)}{\sum_{k \neq l } exp \left( - \left \| y_{k} - y_{l} \right \| ^{2} \right)}$
高维空间的成对相似性 $p_{ij}$ 定义如下：
$p_{ij} = \frac{exp \left( - \left \| x_{i} - x_{j} \right \|^{2} / 2 \sigma^{2} \right)}{\sum_{k \neq l } exp \left( - \left \| x_{k} - x_{l} \right \|^{2} / 2 \sigma^{2} \right)}$

当一个高维数据点 $x_{i}$ 是一个异常点会出现问题。对于这样的一个异常点， $p_{ij}$ 的值对所有的 $j$ 会很小，那么低维映射点 $y_{i}$ 上的位置将对成本函数影响甚小。因此，映射点的位置不能很好地由其他映射点的位置确定。我们通过将高维空间中的联合概率 $p_{ij}$ 定义为对称的条件概率来避免这个问题。于是，设置 $p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}$ ，这样能够保证对所有的数据点 $x_{i}$ 来说， $\sum_{j} p_{ij} > \frac{1}{2n}$ ，每一个数据点 $x_{i}$ 对成本函数将会有重大的贡献。在低维空间中，对称SNE简单地使用 $q_{ij}$ 。对称SNE的最大优点在于它梯度的简单形式，有助于快速计算。对称SNE梯度的定义如下：

$\frac{\delta C }{\delta y_{i}} = 4 \sum_{j} \left( p_{ij} - q_{ij} \right) \left( y_{i} - y_{j} \right)$

拥挤问题

考虑一组位于二维曲线流形上的数据点，它在小尺度上近似线性，并且嵌入在高维空间中。可以在二维地图中很好地模拟数据点之间的小成对距离，这通常在玩具示例（如“Swiss roll ”数据集）上显示。现在假设流形有十个内在维度，并且嵌入到一个更高维度的空间中。二维地图中的成对距离不能准确地模拟十维流形上点之间的距离，原因有几个。例如，在十个维度中，可能有11个相互等距的数据点，并且无法在二维地图中忠实地建模。一个相关的问题是两个空间中成对距离的分布非常不同。以数据点 $i$ 为中心的球体体积按 $r^{m}$ 缩放，其中 $r$ 是球体的半径， $m$ 是球体的维数。因此，如果数据点在十维流形上近似均匀地分布在 $i$ 周围的区域，我们尝试在二维地图上模拟 $i$ 到其他数据点的距离，我们得到以下**“拥挤问题”：与可容纳附近数据点的区域相比，可容纳适中距离数据点的二维地图区域几乎不够大**。因此，如果我们想在地图上精确地模拟小距离，大多数与数据点 $i$ 距离适中的点必须在二维地图中放置得太远。在SNE中，将数据点 $i$ 连接到每个距离过远的地图点的弹簧将因此产生非常小的吸引力。虽然这些吸引力非常小，但大量的吸引力将地图中心的点挤压在一起，从而防止在自然集群之间形成间隙。

Cook等人（2007年）提出了一项通过在所有弹簧上增加一个轻微的斥力来解决拥挤问题的尝试。通过引入具有小混合比例 $\rho$ 的均匀背景模型来产生轻微的排斥。因此，无论两个地图点之间的距离有多远， $q_{ij}$ 永远不会低于 $\frac{2\rho}{n\left(n-1\right)}$ （因为均匀的背景分布超过 $\frac{n\left( n - 1 \right)}{2}$ 对）。因此，对于在高维空间中相距很远的数据点， $q_{ij}$ 将始终大于 $p_{ij}$ ，从而导致轻微的排斥。这种技术被称为UNI-SNE，尽管它通常优于标准SNE，但UNI-SNE成本函数的优化非常繁琐。

不匹配的尾部可以补偿不匹配的维度

既然对称SNE能够匹配高维和低维空间中数据点对的联合概率，而不是它们的距离，我们有一种很自然的方法缓解拥挤问题。在高维空间，我们使用高斯分布将距离转换成概率。在低维空间中，我们可以使用比高斯分布有更重尾巴的概率分布来将距离转换成概率。这使得高维空间中的适中距离可以通过在地图中更大的距离忠实地建模。因此，它消除了表示适中不同数据点的映射数据点之间的不必要的吸引力。

在t-SNE中，我们应用自由度为1的student t-分布作为在低维图中的重尾分布，使用这个分布，联合概率 $q_{ij}$ 如下定义：

$q_{ij} = \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的student t-分布，是因为它具有特别好的特性， $\left( 1 + \left \| y_{i} - y_{j} \right \|^{2} \right)^{-1}$ 对在低维图中大的成对距离 $\left \| y_{i} - y_{j} \right \|$ ，接近平方反比定律（inverse square law）。

我们选择Student t分布的一个理论理由是，它与高斯分布密切相关，因为Student t分布是高斯分布的无限混合。计算方便的特性是，在Student t分布下计算点的密度要比在Gaussian分布下快得多，因为它不涉及指数，即使Student t分布相当于具有不同方差的Gaussian的无限混合。

在 $P$ 和基于Student t分布的联合概率分布 $Q$ 的KL散度的梯度如下：

$\frac{\delta C }{\delta y_{i}} = 4 \sum_{j} \left( p_{ij} - q_{ij} \right) \left( y_{i} - y_{j} \right) \left( 1 + \left \| y_{i} - y_{j} \right \|^{2} \right)^{-1}$

t-SNE的两大优点：

首先，t-SNE梯度强烈排斥在低维表示中由小的成对距离建模的不同数据点。
第二，尽管t-SNE在不同的数据点之间引入了强大的排斥力，这些数据点由小的成对距离建模，但这些排斥力不会无限大。

t-SNE强调（1）通过大成对距离对不同数据点进行建模，（2）通过小成对距离对相似数据点进行建模。具体而言，t-SNE在低维地图中引入远程力，可以将两个在优化早期分离的相似点（簇）拉回到一起。

在这里插入图片描述

sklearn.manifold.TSNE

class sklearn.manifold.TSNE(n_components=2, *, perplexity=30.0, early_exaggeration=12.0, learning_rate=200.0, n_iter=1000, n_iter_without_progress=300, min_grad_norm=1e-07, metric=‘euclidean’, init=‘random’, verbose=0, random_state=None, method=‘barnes_hut’, angle=0.5, n_jobs=None, square_distances=‘legacy’)

参数

n_components: int, default=2 嵌入空间的维度
perplexity: float, default=30.0 perplexity与用在其他学习算法中的最近邻数有关。更大的数据集通常需要更大的perplexity。在5到50之间取值，不同的值会导致不同的结果。
early_exaggeration: float, default=12.0 控制原始空间中的自然簇在嵌入空间中的紧密程度以及它们之间的空间大小。对于较大的值，自然簇之间的空间在嵌入空间会较大。同样，这个参数的选择不是很关键。如果在初始优化过程中，成本函数增加，早期的夸大因子或者学习率可能过高。
learning_rate: float, default=200.0 t-SNE的学习率的取值区间通常是 $[10.0, 1000.0]$ 。如果学习率太高，数据可能看起来像一个球，任何点与它最相近的邻居的距离大致相等。如果学习率太低，大多数点可能会在密集的云中被压缩，只有很少的异常值。如果成本函数嵌入局部最小值，提高学习率可能会有所帮助。
n_iter: int, default=1000 优化迭代的最大数，至少最低250
n_iter_without_progress: int, default=300 在我们中止优化之前没有进展的最大迭代次数，在第250次初始迭代之后使用。请注意，每50次迭代只坚持一次进度，因此，该值将四舍五入到下一个50的倍数。
min_grad_norm: float, default=1e-7 如果梯度范数小于这个阈值，优化器将会停止。
metric: str or callable, default=’euclidean’ 计算特征阵列中实例之间的距离时使用的度量。如果度量是字符串，则它必须是scipy.spatial.distance.pdist为其度量参数所允许的选项之一或者是在pairwise.PAIRWISE_DISTANCE_FUNCTIONS中列出的度量。如果度量是”预计算的“，假设X是一个距离矩阵。或者，如果度量是一个可调用函数，则在每对实例（行）上调用它，并记录结果值。可调用函数应该从X中获取两个数组作为输入，并返回一个指示它们之间距离的值。默认值为“欧几里德”，它被解释为平方欧几里德距离。
init{‘random’, ‘pca’} or ndarray of shape (n_samples, n_components), default=’random’ 嵌入的初始化。可能的选项有“随机”、“pca”和形状为（n_samples, n_components）的numpy数组。PCA初始化不能用于预计算距离，通常比随机初始化更全局稳定。
verbose: int, default=0
andom_state: int, RandomState instance or None, default=None 确定随机数生成器。在多个函数调用之间传递可再现结果的int。请注意，不同的初始化可能会导致代价函数的不同局部极小值。
method: str, default=’barnes_hut’ 默认情况下，采用Barnes-Hut的梯度计算算法近似在O（NlogN）时间内运行。method='exact’将在O（N^2）时间内运行，较慢但精确。当最近邻误差需要大于3%时，应使用精确算法。然而，精确的方法无法扩展到数百万个示例。
angle: float, default=0.5 仅在method='barnes_hut’下使用。这是Barnes-Hut T-SNE在速度和精度之间的trade-off。
n_jobs: int, default=None 运行邻居搜索的并行作业数。当 metric=“precomputed” 或者 (metric=“euclidean” and method=“exact”)时，该参数没有影响。
square_distances: True or ‘legacy’, default=’legacy’ TSNE是否应将距离值平方。“legacy”表示距离值仅在metric=“euclidean”时才平方。True表示距离值为所有度量的平方。

返回对象的属性

embedding_: array-like of shape (n_samples, n_components) 存放嵌入向量
kl_divergence_: float 优化后的Kullback-Leibler散度
n_iter_: int运行时迭代的数量

Methods

fit(X[y]) 将X放入一个嵌入空间
fit_transform(X[, y]) 将X放入一个嵌入空间和返回转换输出
get_params([deep]) 获取此估计器的参数
**set_params(params) 设置此估计器的参数

参数：
X ndarray of shape (n_samples, n_features) or (n_samples, n_samples)
如果metric=‘precomputed’，X必须是一个平方距离矩阵。否则，它每行包含一个示例。如果method=‘exact’，X可能是‘csr’, 'csc’或‘coo’类型的稀疏矩阵。如果method='barnes_hut’和metric=‘precomputed’, X可能是预计算的稀疏图。

TSNE代码可视化的代码示例如下：

from sklearn.manifold import TSNE
from matplotlib.pyplot import plt
X_tsne = TSNE(n_components=2, init='pca').fit_transform(X)
X_min, X_max = X_tsne.min(0), X_tsne.max(0)
X_norm = (X_tsne - x_min) / (x_max - x_min)
for i in range(X_norm.shape[0]):
    plt.scatter(X_norm[i, 0], X_norm[i, 1])

附录

Kullback-Leibler divergences

KL散度是用来衡量两个概率分布之间的相似性的一个度量指标。KL散度，从信息论中演化而来。信息熵用来度量信息的不确定性，熵越大，信息量越大。假设有随机变量 $X$ , 有 $N$ 种状态，每种状态的发生概率为 $p_{i}, i = [1, 2, \cdots, N]$ ，那么信息熵的公式定义为： $H\left(X\right)=-\sum_{i=1}^{N}p\left( x_{i}\right)log \; p\left( x_{i}\right)$ 。

在信息熵的基础上，假设有概率 $q$ 和概率 $p$ , 定义表示概率 $q$ 和概率 $p$ ,之间差异性的KL散度 $D_{KL} \left( p || q \right)$ 为：
$\begin{matrix} D_{KL} \left( p || q \right) &= \sum_{i=1}^{N} p\left( x_{i}\right) \cdot \left( log \; p\left( x_{i}\right) - log \; q \left( x_{i}\right)\right) \\ &= \sum_{i=1}^{N} p\left( x_{i}\right) \cdot \frac{log \; p\left( x_{i}\right)}{log \; q \left( x_{i}\right)} \qquad \qquad \quad \; \; \end{matrix}$

$D_{KL} \left( p || q \right)$ 散度值越小，表示概率 $q$ 和概率 $p$ 之间越接近。

t-distribution

在概率论和统计学中，t-分布用于根据小样本来估计呈正态分布且方差未知的总体的均值。如果总体方差已知（样本数量足够多时），则应该用正态分布来估计总体均值。

假设 $X$ 服从标准正态分布， $Y$ 服从 $\chi^{2}\left( n \right)$ 分布，那么 $\frac{X}{\sqrt{Y/n}}$ 的分布称为自由度为 $n$ 的 $t$ 分布，记为 $\sim t \left( n \right)$

分布密度函数为:
$F_{Z}\left( x \right) = \frac{Gam\left( \frac{n+1}{2} \right)}{\sqrt{n \pi}Gam\left( \frac{n}{2} \right)}\left( 1 + \frac{x^{2}}{n}\right)^{-\frac{n+1}{2}}$

其中Gam为伽玛函数$\Gamma \left( x \right) = \int_{0}^{\infty } t^{x-1} e ^{-t} dt $

t分布曲线形态与 $n$ （自由度 $d f$ ）大小有关，与标准正态分布曲线相比，自由度 $d f$ 越小，t分布曲线越平坦，曲线中间越低，曲线双侧尾部翘得越高；自由度 $d f$ 越大，t分布曲线越接近正态分布曲线，当自由度 $\infty$ 时，t分布曲线为标准正态分布曲线。

在这里插入图片描述

manifold learning（流形学习）

流形（manifold）是几何中的一个概念，它是高维空间中的集合结构，即空间中的点构成的集合。比如，二维空间中的曲线，三维空间中的曲面等等。二维空间中的曲线可以看作二维空间中的一维流形，三维空间中的曲面可以看作三维空间中的二维流形。 $n$ 维空间中的 $\left( m < n \right)$ 维流形就是具有 $m$ 维集合形状的一个子集。

流形学习假设数据在高维空间的分布位于某一更低维的流形上，基于这个假设来进行数据的分析。假设有一个 $N$ 维空间中的流形 $M$ ，即 $M$ 是 $N$ 维欧氏空间中的一个真子集 $\subset \mathbb{R}^{N}$ ，流形学习降维算法要实现的映射维 $\rightarrow \mathbb{R}^{n}$ ，其中 $n < < N$ ，即将 $N$ 维空间中流形 $M$ 上的点映射维 $n$ 维空间中的点。j降维后应该要保证 $n$ 维空间中同样满足与高维空间流形有关的几何约束。