当前位置: 首页 > > 天 方 夜 “谈” 第1期 | 高维数据可视化之t-SNE算法

天 方 夜 “谈” 第1期 | 高维数据可视化之t-SNE算法

发表于:2020-03-18 20:48 作者: 方滨兴班 阅读数(11122人)

假设你有一个包含数百个特征的数据集,却对该数据所属领域几乎没有什么了解,并且你需要去探索数据中存在的隐模式,那可谓是数无形时少直觉,根本无从下手。当数据各特征间存在高度的线性相关,这时你可能首先会想到使用 PCA 对数据进行降维处理,但是 PCA 是一种线性算法,它不能解释特征之间的复杂多项式关系,而 t-SNE (t distributed stochastic neighbor embedding)是一种用于挖掘高维数据的非线性降维算法,它能够将多维数据映射到二维或三维空间中,因此 t-SNE 非常适用于高维数据的可视化操作 t-SNE  是由 SNE 发展而来,因此本文将先介绍 SNE  的基本原理,之后再扩展到 t-SNE 

1SNE 基本原理

SNE 是通过仿射变换将数据点映射到相应概率分布上,主要包括下面两个步骤:

1. 通过在高维空间中构建数据点之间的概率分布P,使得相似的数据点有更高的概率被选择,而不相似的数据点有较低的概率被选择;

2. 然后在低维空间里重构这些点的概率分布Q,使得这两个概率分布尽可能相似。


令输入空间是 图片.png,输出空间为 图片.png 。

不妨假设含有图片.png个样本数据 图片.png,其中图片.png,降维后的数据为 图片.png ,图片.png图片.png 是先将欧几里得距离转化为条件概率来表达点与点之间的相似度,即首先是计算条件概率 图片.png其正比于 图片.png  图片.png之间的相似度,图片.png的计算公式为:

图片.png

在这里引入了一个参数 图片.png ,对于不同的数据点 图片.png取值亦不相同,因为我们关注的是不同数据点两两之间的相似度,故可设置 图片.png。对于低维度下的数据点 图片.png,通过条件概率 图片.png 来刻画 图片.png与 图片.png之间的相似度,图片.png的计算公式为:

图片.png

同理,设置 图片.png


如果降维的效果比较好,局部特征保留完整,那么有  成立,因此通过优化两个分布之间的 KL 散度构造出的损失函数为:

图片.png

这里的 图片.png 表示在给定高维数据点 图片.png 时,其他所有数据点的条件概率分布; 图片.png 则表示在给定低维数据点 图片.png 时,其他所有数据点的条件概率分布。从损失函数可以看出,当 图片.png 较大 图片.png 较小时,惩罚较高;而 图片.png 较小 图片.png 较大时,惩罚较低。换句话说就是高维空间中两个数据点距离较近时,若映射到低维空间后距离较远,那么将得到一个很高的惩罚;反之,高维空间中两个数据点距离较远时,若映射到低维空间距离较近,将得到一个很低的惩罚值。也就是说,SNE 的损失函数更关注于局部特征,而忽视了全局结构。


SNE 对应目标函数的求解


首先不同的数据点对应着不同的 图片.png ,图片.png 的熵会随着 图片.png  的增加而增加。

 图片.png引入困惑度的概念,通过二分搜索的方式来寻找一个最佳 图片.png其中困惑度指: 

图片.png

这里的 图片.png 是 图片.png  的香农熵,即:

 图片.png

困惑度可以理解为某个数据点附近有效近邻点的个数 SNE 对困惑度的调整具有鲁棒性,通常选择 5~50 之,给定之后通过二分搜索的方式即可寻找到合适的 图片.png 。通过对 SNE 的损失函数求梯度可得:

图片.png

在迭代初始化阶段,可以使用较小的 图片.png 对高斯分布进行初始化。为了加速优化过程和避免陷入局部最优解,梯度中需要使用一个相对较大的动量,即参数更新过程中除了使用当前梯度,还要引入之前梯度累加的指数衰减项,迭代更新过程如下: 

图片.png

这里的 图片.png 表示迭代 次的解,图片.png 表示学习率,图片.png 表示迭代 次的动量。

3 对称SNE


优化 图片.png 的一种替换思路是使用联合概率分布来替换条件概率分布,即 P 是高维空间里数据点的联合概率分布,是低维空间里数据点的联合概率分布,此时的损失函数为:

图片.png

同样的 图片.png ,这种改进下的 SNE 称为对称 SNE ,因为它的先验假设为对 图片.png有 图片.png 成立,故概率分布可以改写成:

图片.png

这种改进方法使得表达式简洁很多,但是容易受到异常点数据的影响,为了解决这个问题通过对联合概率分布定义修正为: 图片.png ,这保证了 图片.png,使得每个点对于损失函数都会有贡献。对称 SNE 最大的优点是简化了梯度计算,梯度公式改写为:

图片.png

研究表明,对称 SNE  SNE 的效果差不多,有时甚至更好一点。


4  t-SNE


t-SNE 在对称 SNE 的改进是,首先通过在高维空间中使用高斯分布将距离转换为概率分布,然后在低维空间中,使用更加偏重长尾分布的方式来将距离转换为概率分布,使得高维度空间中的中低等距离在映射后能够有一个较大的距离。

图片.png


从图中可以看到,在没有异常点时,分布与高斯分布的拟合结果基本一致。而在第二张图中,出现了部分异常点,由于高斯分布的尾部较低,对异常点比较敏感,为了照顾这些异常点,高斯分布的拟合结果偏离了大多数样本所在位置,方差也较大。相比之下,分布的尾部较高,对异常点不敏感,保证了其鲁棒性,因此拟合结果更为合理,较好的捕获了数据的全局特征。

使用 分布替换高斯分布之后 图片.png 的变化如下:

图片.png

此外,随着自由度的逐渐增大,分布的密度函数逐渐接近标准正态分布,因此在计算梯度方面会简单很多,优化后的梯度公式如下:

图片.png

 总的来说,t-SNE 的梯度更新具有以下两个优势:

  • 对于低维空间中不相似的数据点,用一个较小的距离会产生较大的梯度让这些数据点排斥开来;

  • 这种排斥又不会无限大,因此避免了不相似的数据点距离太远。

5 与 PCA 降维效果对比

在 MNIST 数据集上,该数据集的每张数字图片大小为 28 28,也就是说特征维度为728 ,通过使用sklearn 算法库中的 t-SNE  PCA 算法进行降维可视化测试,测试结果如下图所示:


from sklearn.manifold import TSNEfrom sklearn.datasets import load_iris,load_digitsfrom sklearn.decomposition import PCAimport matplotlib.pyplot as pltimport numpy as np%config InlineBackend.figure_format = "svg"
digits = load_digits()X_tsne = TSNE(n_components=2, random_state=33).fit_transform(digits.data)X_pca = PCA(n_components=2).fit_transform(digits.data)
font = {"color": "darkred", "size": 13, "family" : "serif"}
plt.style.use("dark_background")plt.figure(figsize=(8.5, 4))plt.subplot(1, 2, 1) plt.scatter(X_tsne[:, 0], X_tsne[:, 1], c=digits.target, alpha=0.6, cmap=plt.cm.get_cmap('rainbow', 10))plt.title("t-SNE", fontdict=font)cbar = plt.colorbar(ticks=range(10)) cbar.set_label(label='digit value', fontdict=font)plt.clim(-0.5, 9.5)plt.subplot(1, 2, 2)plt.scatter(X_pca[:, 0], X_pca[:, 1], c=digits.target, alpha=0.6, cmap=plt.cm.get_cmap('rainbow', 10))plt.title("PCA", fontdict=font)cbar = plt.colorbar(ticks=range(10)) cbar.set_label(label='digit value', fontdict=font)plt.clim(-0.5, 9.5)plt.tight_layout()


从实验结果可以看出t-SNE 法降维后的可视化效果要远远好于 PCA 算法

图片.png

6 总结

t-SNE  算法详细过程如下:

1. 数据准备:图片.png,其中 图片.png 

2. 初始化困惑度参数用于求解 图片.png ,迭代次数 图片.png 、学习率 图片.png 和动量 图片.png ;

3. 开始优化

  • 计算高维空间中的条件概率 图片.png ;

  •   图片.png 

  • 使用正态分布 图片.png 随机初始化 图片.png 矩阵;

  • 从 图片.png 进行迭代 

    • 计算低维空间中的条件概率 图片.png 

    • 计算损失函数 图片.png 对 图片.png 的梯度;

    • 更新  图片.png

  • 输出 图片.png 

4. 算法结束。


t-SNE 算法其实就是在 SNE 算法的基础上增加了两个改进:

  • 把 SNE 修正为对称 SNE ,提高了计算效率,效果稍有提升;

  • 在低维空间中采用了 t 分布替换原来的高斯分布,解决了高维空间映射到低维空间所产生的拥挤问题,优化了 SNE  过于关注局部特征而忽略全局特征的问题 。