1 前言

将高维数据点以可视化的方式呈现出来是探索式数据分析的一个重要研究课题,例如对于多张64*64的像素图，将每张图转化为行向量后可以表示为4096维空间中的数据点，如果能将这些数据点可视化到平面视图中, 并在某种程度上保留数据点间的分布规律，就能以人类可感知的方式探索原始图像集背后隐藏的规律。各个学科领域采集的数据如全球气候数据、人类基因分布、金融统计等经常呈现出高维的特征,所以研究高维数据的可视化方法具有极大的现实意义。
由于人类肉眼仅限于感知二/三维空间中的几何图形，所以高维数据点只有以二/三维的视觉元素表达后才能使人直观的观测数据分布的规律。在二维平面上可视化超过两个维度的方法有很多，比如散点图矩阵,平行坐标,Andrew曲线,星形图等，这些方法面对高维数据时也会产生视觉混淆的问题。降维算法是利用线性或者非线性变换将高维观测空间中的数据投影到一个有意义的低维空间中，同时尽量保持数据的内在结构不被改变，进而获取数据集内在特征的低维表示。

图1.1(a)5维的平行坐标图	图1.1(b)高维的平行坐标图

2 降维方法

针对不同目的所使用的降维方法有所不同，比如特征工程是利用专家的知识和经验进行特征抽取和组合以达到降低运算复杂度的目的，而针对可视化呈现效果我们对不同的降维技术又有不同的评估标准。
通常针对可视化的降维问题的形式化表述如下：

令观测数据集 $X = \{ x_{1},x_{2},...,x_{N} \}$ , 由 $N$ 个 $D$ 维数据 $x_{i} = \{ x_{i_{1}},x_{i_{2}},...,x_{i_{D}} \}\in R^{D}$ 构成。
令 $\delta _{D}:R_{D} \times R_{D} \to R$ 和 $\delta _{d}:R_{d} \times R_{d} \to R$ 分别为高维空间 $R^{D}$ 和低维嵌入空间 $R^{d}$ 的相似度度量函数。
数据降维可以定义为 $D$ 维数据 $x_{i}$ 到 $d$ 维数据 $y_{i}$ 的映射：
$\Phi: R_{D} \to R_{d} ,d \ll D\\ x_{i} \mapsto y_{i}, i = 1,2,...,N\\ x_{i} \in X,y_{i} \in Y$
使得 $\delta _{D}(x_{i},x_{j}) \approx \delta _{D}(y_{i},y_{j}), i,j = 1,2,...,N$

该映射要使在高维空间中相距较近的点在低维空间中也应较近，在高维空间中相距较远的点在低维空间中也应较远。使高维数据点集嵌入到低维空间后尽量还原其整体和局部的拓扑结构。根据映射 $\Phi$ 的性质，降维可分为线性的和非线性的。

2.1 线性降维

线性降维方法将高维数据集通过线性映射到低维空间，最常见的线性降维算法有PCA(Principal Component Analysis)，MDS(Classical Multidimensional Scaling),等。
以PCA为例，通过寻找一组线性向量基，将数据映射到其均方误差失真最小的低维线性空间中并尽量保持高维数据集对方差贡献最大的特征。具地地，对于高维数据集 $X$ ，PCA通过将 $cov(X)$ (数据集 $X$ 的方差矩阵)进行特征值分解，取前几个较大的特征值对应的特征向量组成的线性映射矩阵 $M$ ，也就是最大化 $M^{T}Cov(X)M$ 的线性映射矩阵 $M$ ， $M$ 的行数就是最终低维空间的维度，通过这种映射方法，低维空间中的数据集将尽量保留最大的信息量(方差),从而达到压缩原始数据的维度的目的。
与PCA相似，MDS(Classical)方法求取的映射也是线性的,不同的是MDS(Classical)算法是从数据点对之间的相似性矩阵出发来构造合适的低维空间中的点集，使得数据的内在线性结构在低维空间中得以保持，相似度一般用欧氏距离来衡量。
上述方法，由于映射方法是线性的，将高维空间中局部存在的线性结构可视化后还能还原其结构，但对相距较远的点之间非线性的关系映射到低维空间后则会失真。比如我们将PCA方法应用到两类不同的三维数据集。

图2.1(a)Corner-Plane数据集	图2.1(b)Corner-Plane的PCA降维结果
图2.1(c)Swiss-roll数据集	图2.1(d)Swiss-roll的PCA降维结果

图2.1(c)和2.1(d)揭示了对于高维空间中的低维流形，更重要的是将那些高维空间中紧密靠近的点集在低维空间中形成聚类效果，比如图c三维空间中所有蓝色的点，而对于蓝色和黄色的点在二维平面中则应该更加的分散。PCA方法显然将蓝色点与黄色点混淆在一起了，所有基于线性映射的方法都存在这样的缺陷。

2.2 非线性降维

为了克服线性降维算法的缺陷，涌现了一批非线性降维算法。在探讨这些算法之前，有必要引入讨论下流形学习的背景知识。

2.2.1 流形学习与knn图

三维空间中的地球，我们只用两个维度（经度和纬度）就可以维一的定位地面上任意一点。如图3.1c所示三维空间中的面包卷结构上，我们将它锤平后可以近似看作几个二维平面拼接在一起,我们可以确认它的本征维度为2。现实生活中的高维数据其实大量存在低维流形结构。2000年，Seung等人在《Science》上发表的论文【8】首次从流形的角度解释了人类的视觉认知形式，提出了流形是人类认知的基础的观点，这种认知形式可以抽象成维数与神经元数目相当的抽象空间中的点。例如,虽然人脸的图像是由 $N\times N$ 像素点组成的高维数据点，但是图2.2中只有头像的角度变化，理论上可以只用一个自由度去描述这几个头像图的变化，也就是 $R^{N\times N}$ 高维空间中的一维流形,而人类认知这个复杂人脸的变化可能只需要一个感知角度的神经元。现实中，一个图像中的人脸可能还加入明暗度，大小，表情变化等自由度，但其本征维度远低于 $N\times N$ 像素点的维度。更重要的是，随着分辨率的提高，维度急剧增加，流形的本征维度却没有变化。

图2.2 视觉认知中的流形

上文提到线性降维方法对面包卷流形可视化效果不好的原因，就是在流形中并非任意两点的距离都适合用欧氏距离去衡量。比如对于地球，当测地的范围较小时近似于二维平面。从百米跑道的起点走到终点，我们可以直接用欧氏距离来度量，但是对于一艘做环球航行的船来说，再用欧氏距离去测量出来的距离就是0,这显然是不合适的。目前主流方法计算高维空间中的流形上的两点距离进而得出相似度矩阵都是使用knn图,对于A点到B点的距离，我们测量A点与最近邻点的欧氏距离，然后从A点出发找到一条到B点的路径，用路径上所有点对的距离之和近似A与B的距离。

图2.3(a)	图2.3(b)	图2.3(c)

图2.3(a)中的红色虚线表示两点间的欧氏距离，蓝线表示实际距离。图2.3(c)中的红色实线表示knn路径对实际距离的近似。
有了计算流形中两点相似度的方法后，在这之上就有了将高维空间中的低维流形嵌入低维空间中以表征其结构的降维方法，这被称为流形学习。 ISOMAP和LLE降维算法是流形学习的奠基之作,它们从算法层面印证了高维非线性数据确实存在低维流形结果，分别从全局特征构造和局部特征构造两个角度对高维非线性数据进行低维流形结构的还原。

2.2.2 ISOMAP算法

ISOMAP算法是一种基于全局特征保持的流形学习算法。其算法的思路基本与MDS方法一致，也是根据点对相似度距阵不断迭代寻找各数据点在低维空间中放置的位置。不同的是ISOMAP通过knn计算点对相似度距阵，用测地距离替代MDS中的欧氏距离。最终代价函数为高维空间点距离与低维空间点距离差之和，这里可以看出优化目标是全局特征，然后对这个目标函数用梯度下降迭代求最优。
ISOMAP算法在可视化流形时主要存在两个问题：(1) “短路边”的存在会严重破坏低维空间中的可视化效果，在构建knn图时如果为每个数据点选择的领域过大或者输入样本中存在异常点，可能会导致流形上不相关的两个点间产生过近的距离。(2)对于非凸的高维数据集（有孔洞）,如图2.4(b), ISOMAP不能很好的处理。(3)邻域选取过小会导致图非连通

2.2.3 LLE算法

ISOMAP试图在低维空间从全局上还原所有点对间测地距离，而LLE则试图在低维空间还原点与邻近点的局部线性关系。具体来说，LLE根据相似度矩阵构造每个点与周围几个邻近点人线性关系，然后对这个线性系数矩阵做特征分解，求出在低位空间中的坐标。LLE算法在可视化流形时主要存在两个问题：(1)邻域选取过大有时会导致很大一部分非近邻点映射为近邻点。(2)不能处理首尾相接的闭环流形。(3)邻域选取过小又可能导致找不到点的局部线性关系。

图2.4(a)	图2.4(b)	图2.4(c)

3 确定本征维度的方法和拥挤问题

前面提到过高维空间中的流形具有远低于所在空间的本征维度，而如何估计低维流形的本征维度也是流形学习中的一个重要问题。而且这也是可视化的重要问题。如果低维流形的本征维度远大于2度，那利用降维算法将这些数据点可视化到二维散点图中就会比较困难。一个比较明显的问题就是拥挤问题【11】, 对于10维空间中的一个点A，其以R为半径的邻域为 $R^{10}$ 空间中的球形, 我们假设这个邻域中均匀分布着一系列点，现在我们将点A和所有邻域中的点映射到二维平面中，将会近似一个圆。在10维空间中邻域内离A较远的点远多于A附近的点，而这些较远点的象在二维平面上将集中在圆周附近，随着原始维度的上升，这些圆周附近的点将会变得更加拥挤，从而导致原始拓扑结构的失真。在10维空间中我们至少能同时找到10个彼此距离相等的点，而在2维空间中我们只能找到3个。如果不能解决拥挤问题，那么以低于流形本征维度的方式可视化就有很大可能失真。
本征维度被定义为在不损失信息的前提下，用来描述数据的自由变量的最小数量。局部本征维度估计方法可以分为全局本征维度估计法和局部本征维度估计法【6】。

4 t-SNE可视化

t-SNE算法是SNE算法的改进，SNE将点对间的相似度用条件概率表述，这样任一点周围的点分布可以用高斯分布表示，然后用KL散度衡量低维空间中的分布于高维空间分布间的近视度,SNE的最终目标就是对所有点最小化这个KL散度。
t-SNE作出的改进就是用在低维空间中用t分布替代高斯分布，如图1所示，高斯分布对应高维空间，t-分布对应低维空间。对于高维空间中相距较近的点，为了满足 $p_{ij} = q_{ij}$ ，低维空间中的距离需要稍小一点；而对于高维空间中相距较远的点，为了满足 $p_{ij} = q_{ij}$ ，低维空间中的距离需要更远。这就使最终的可视化效果有更好的聚类表现。t-分布的长尾效应某种程度上缓解了拥挤问题。t-SNE作者还在论文【11】中提到，t-分布只适合二维可视化，其他维度的可视化需要其他分布。
t-SNE相较于ISOMAP和LLE来说有更好的可视化效果，因为它同时兼顾了全局特征和局部特征。

图4.1(a)t-SNE在MINIST数据上的可视化效果	图4.2(b)ISOMAP可视化效果	图4.2(c)LLE可视化效果

图4.1是t-SNE,ISOMAP,LLE在MINIST数据(手写体数字)上的可视化效果，可以看出t-SNE在不同的类簇间形成清晰的间隔，而ISOMAP和LLE不同类间存在重叠。

5 总结

本文简述了从线性降维到非线性降维的发展历史，列举了几种经典的流行学习的算法在可视化方面的效果，包括当前最流行的t-SNE算法。当前的大量降维算法均是对这几种算法的改进或是基于类似的思想。本文所有讨论都只涉及了可视化效果这一角度，而没有分析各算法的时间空间复杂度。实际上，由于“维数灾难“问题和高维数据通常伴随大尺度的特征，降维算法的运算复杂度也是一个不容忽视的问题。
最后指出一点，这些可视化的方法只能用于理论的探索和猜测，而不能做为验证理论正确性的工具，t-SNE的作者曾指出，相当一部分学术论文使用t-SNE方法时犯了这样的错误。

6 引用

[1]陈为,沈则潜,陶煜波.数据可视化[M].北京:电子工业出版社,2013
[2]詹宇斌.流形学习理论与方法及其应用研究[D].长沙:国防科学技术大学,2011
[3]石浩.基于等距特征映射的非线性降维及其应用研究[D].合服:中国科学技术大学,2017.
[4]Jolliffe I T.Principal Component Analysis[M].New York:Springer-Verlag,1986
[5]从SNE到t-SNE再到LargeVis
[6]Camastra F.Data dimensionality estimation methods:a survey[J].Pattern recognition,2003,36(12):2945-2954.
[7]Pettis K W,Bailey T A,Jain A K, et al.An intrinsic dimensionality estimator from near-neighbor information[J].IEEE Transactions on pattern analysis and machine intelligence,1979,PAMI-1(1):25-37
[8]Seung,HS,Lee D D.The manifold ways of perception[J].science,2000,290(5500):2268-2269.
[9]Tenenbaum J B,De Silva V,Langford J C. A global geometric framework for nonlinear dimensionality reduction[J].science, 2000,290(5500):2319-2323.
[10]Roweis S T,Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J].science,2000,290(5500):2323-2326.
[11]Laurens V D,Geoffrey Hinton. Visualizing Data using t-SNE[J].Machine Learning Research 9(2008):2579-2605.

降维与可视化