t-SNE:可视化降维算法

Posted on Edited on In

t-SNE介绍

  • t-SNE是由t-分布和随机近邻嵌入(Stochastic neighbor Embedding)组成
  • 其重要用途是 可视化和探索高维数据。它的主要目标是将高维数据集转换为低维数据集，并且可视化效果更好。采用非线性降维技术，可以捕获复杂的流行数据。

t-SNE工作原理

SNE算法

在介绍t-SNE之前，我们先介绍SNE算法

​ 核心思想：

数据降维时，要保证： 在高维空间相似的数据点，映射到低维空间也是相似的。常规做法是使用欧式距离来表示这种相似性，而SNE把距离关系转换成一种条件概率来表示相似性

把距离映射到某一概率分布上：

对于高维空间中的两个点$x_i$​​​​,$x_j$​​​​， $x_i$​​​​以条件概率$p_{j|i}$​​​​选择$x_j$​​​​作为它的临近点。 考虑以$x_i$​​​​为中心点的高斯分布，如果$x_j$​​​​​越靠近$x_i$​​，则条件概率$p_{j|i}$​​​越高，相似性越高。

在SNE中，在高维空间中，条件概率$p_{j|i}$定义为
$$
p_{j|i} = \frac{exp(-||x_i-x_j||^2/{2\sigma_i^2})}{\sum_{k \neq i} exp(-||x_i - x_k||^2 /{2\sigma^2_i)}}
$$
考虑其它所有点与$x_i$的条件概率分布，可以构成一个条件概率分布$P_i$.

同样的，当数据映射到低维空间之后，我们也用类似上面条件概率的形式，定义低维空间中两点​的相似性.

这里我们假设高维数据点$x_i,x_j$在低维空间中的映射点分别是$y_i,y_j$。类似的，低维空间中的条件概率用$q_{j|i}$表示，这里$\sigma$均固定为$1/\sqrt{2}$
$$
q_{j|i} = \frac{exp(-||y_i-y_j||^2/{2\sigma_i^2})}{\sum_{k \neq i} exp(-||y_i - y_k||^2 /{2\sigma^2_i)}}
$$
考虑其它所有点与$y_i$​的条件概率分布，可以构成一个条件概率分布$Q_i$​.

高维空间的条件概率分布$P_i$应该和低维空间中的概率分布$ Q_i$相同,我们可以用KL散度来衡量两个分布之间差异。

SNE的最终目标就是对所有数据点最小化KL距离，其代价函数可以定义为
$$
C = \sum_{i} KL(P_i || Q_i) = \sum_{i} \sum_{j} p_{j|i} log \frac{p_{j|i}}{q_{j|i}}
$$
不过目前的SNE存在两个问题：不对称 和 拥挤问题

  • 不对称：$p_{j|i}$​ 和 $q_{j|i}$​不相等
  • 拥挤：不同类别的簇挤在一起，没有办法分开。因为高维空间距离分布和低维空间存在差异。简单来说，更高维的空间距离相等的点的数据量更多。在10维流行性，存在11个点两两数据相等，而在2维空间，最多能使3个点之间两两数据相等。所以将高维空间中的距离关系完全保留到低维空间中是不可能的.

t-SNE算法

针对上述提到的SNE算法中的两点不足，t-SNE提出了相应的解决方法。

不对称

对于不对称问题，我们用更加简答直观的方式重新定义了概率分布
$$
p_{ij} = \frac{p_{i|j} + p_{j|i}}{2n}
$$
相应的损失函数可以定义为
$$
C = KL(P||Q) = \sum_{i} \sum_{j} p_{ij} log\frac{p_{ij}}{q_{ij}}
$$
相应的梯度变为：
$$
\frac{\grad C }{ \grad{y_i}} = 4 \sum_{j}(p_{ij} - q_{ij})(y_i-y_j)
$$

拥挤

随着维度的增加，大部分数据点与$x_i$​之间的距离分布极其不均衡，很多点与$x_i$之间的距离接近，如果直接把高维距离关系保留到低维空间。很容易出现拥挤问题。我们用t-分布的方法，解决该问题。

t-分布

​ t-分布:从正态总体中抽取容量为N的随机样本，如果该正态总体的均值为$\mu$,方差为$\sigma^2$.随机样本均值为$\hat x$,方差为$s^2 = \frac{1}{N-1} \sum_{i=1}^{N} (x_i - \hat x)^2$,

随机变量t可以表示为
$$
t = \frac{\hat x - \mu}{ s / \sqrt{N} }
$$
我们称t服从自由度为n-1的t分布。

t-分布是长尾分布。相比于高斯分布，他尾部更宽一些，处理小样本和异常点时，鲁棒性较高

如上图所示，要是$p_{ij}$ 和$q_{ij}$相等，在高维空间中比较接近的点(对应正态分布)，在低维空间中要更接近(对应t-分布)；而对与高维空间中较远的点，在低维空间中需要更远。

所以在t-SNE中，用t-分布，重新定义了低维空间中的概率分布，如下所示
$$
q_{ij} = \frac{(1+||y_i - y_j||^2)^{-1}}{ \sum_{k\neq l}(1+||y_k - y_l||^2)^{-1}}
$$

代码实现

“封装成一个函数”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
import matplotlib.pyplot as plt
from sklearn import manifold 
'''
    tSNE对数据进行t-sne可视化
    @para：
    X：shape（num,dim) num为数据点的个数，dim是每个数据点的特征的维度  eg：（100，3）表示一共有100个数据点，每个数据点是3维向量
    label：shape(num,1) 对应每个数据点的类别标签
    colorlist: dict:{"red":red}每个类别对应的颜色
    n_components:数据点降维之后的维度，默认是2
    init:和库函数的含义一样，可以选择"pca: "random"
    perplexity:建议5-50，数据量越大，该值应该设置的越大
'''
def tSNE(X,label,colorlist,n_components=2,init="pca", perplexity=10):
    #降维
    tsne = manifold.TSNE(n_components=n_components,init=init,random_state=0, perplexity=10)
    X_tsne = tsne.fit_transform(X)#(187500, 2)
    #可视化
    for color in colorlist.keys():
        plt.scatter(X_tsne[colorlist[color][:,0]][:,0], X_tsne[colorlist[color][:,0]][:,1],s=0.01, c=color)
    plt.show()

“应用实例”

使用时，需要自己计算colorlis

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from PIL import Image
import numpy as np
#加载图片和标签
X= np.asarray(Image.open("D:/Users/July/Desktop/image1.jpg")) #(366, 500,3)
label = np.asarray(Image.open("D:/Users/July/Desktop/label1.png")) #(366,500)

#调整尺寸
label = label.reshape(-1,1)
X=X.reshape(-1,3)

#计算colorlist
red= label==0
green= label ==5
blue = label ==255
yellow = label ==11
colorlist={}
colorlist['red']=red
colorlist['green']=green
colorlist['blue']=blue
colorlist['yellow']=yellow
#调用函数
tSNE(X,label,colorlist)

运行结果