t-SNE是一种降维方法,PCA主成分分析、LDA等属于线性降维,t-SNE属于非线性降维,是一种流形学习方法(Manifold Learning)。
如图所示的曲面上,两点之间的欧式距离为红色虚线所示,蓝色实线为两点之间的测地线距离,第二张图为KNN图,展开后如第三张图所示。两点之间的最短距离为蓝色实线所示,但实际应用中,真实最短距离较难获得,一般通过构造KNN图寻找最短路径作为近似。
构建二维空间k-d树后,寻找k近邻就不用计算某个点与其他所有点之间的距离了。例如寻找图中红点的k近邻,只需要搜索当前子空间,同时不断回溯搜索父节点的其他子空间,即可找到k近邻点。
SNE(stochastic neighbor embedding)根本原理是:在高维空间相似的数据点,映射到低维空间距离也是相似的。通常使用欧式距离来描述这种相似性,而SNE把这种距离关系转换为一种条件概率来表示相似性。高维空间中