tSNE—高维数据降维可视化(理论部分)

t-SNE是一种降维方法,PCA主成分分析、LDA等属于线性降维,t-SNE属于非线性降维,是一种流形学习方法(Manifold Learning)。

tSNE—高维数据降维可视化(理论部分)

如图所示的曲面上,两点之间的欧式距离为红色虚线所示,蓝色实线为两点之间的测地线距离,第二张图为KNN图,展开后如第三张图所示。两点之间的最短距离为蓝色实线所示,但实际应用中,真实最短距离较难获得,一般通过构造KNN图寻找最短路径作为近似。

tSNE—高维数据降维可视化(理论部分)

构建二维空间k-d树后,寻找k近邻就不用计算某个点与其他所有点之间的距离了。例如寻找图中红点的k近邻,只需要搜索当前子空间,同时不断回溯搜索父节点的其他子空间,即可找到k近邻点。

SNE(stochastic neighbor embedding)根本原理是:在高维空间相似的数据点,映射到低维空间距离也是相似的。通常使用欧式距离来描述这种相似性,而SNE把这种距离关系转换为一种条件概率来表示相似性。高维空间中的两个数据点xi和xj,xi以条件概率Pj|i选择xj作为它的邻近点。考虑以xi为中心点的高斯分布,若xj越靠近xi,则Pj|i越大。反之若两者相距较远,则Pj|i极小。因此我们可以这样定义Pj|i。

tSNE—高维数据降维可视化(理论部分)

其中σi表示以xi为中心点的高斯分布的方差。由于我们只关心不同点对之间的相似度,所以设定Pi|i=0。

当我们把数据映射到低维空间后,高维数据点之间的相似性也应该在低维空间的数据点上体现出来。这里同样用条件概率的形式描述,假设高维数据点xi和xj在低维空间的映射点分别为yi和yj。类似的,低维空间中的条件概率用qj|i表示,并将所有高斯分布的方差均设定为1/sqrt(2),所以有:

tSNE—高维数据降维可视化(理论部分)

若yi和yj真实反映了高维数据点xi和xj之间的关系,那么条件概率pj|i与qj|i应该完全相等。这里我们只考虑了xi与xj之间的条件概率,若考虑xi与其他所有点之间的条件概率,则可构成一个条件概率分布Pi,同理在低维空间存在一个条件概率分布Qi且应该与Pi一致。如何衡量两个分布之间的相似性?当然是用经典的KL距离(Kullback-Leibler Divergence),SNE最终目标就是对所有数据点最小化这个KL距离,我们可以使用梯度下降算法最小化如下代价函数:

tSNE—高维数据降维可视化(理论部分)


http://bindog.github.io/blog/2016/06/04/from-sne-to-tsne-to-largevis/#top