数据降维

写在前面

• 态度决定高度！让优秀成为一种习惯！
• 世界上没有什么事儿是加一次班解决不了的，如果有，就加两次！（- - -茂强）

综述

面对着大数据时代的发展，数据成为目前一切科学的基础，拥有数据，就代表着拥有商机，拥有决定权，每个公司或者科研项目，想要用实际说话，就必须有一个良好的数据基础，所以数据清晰，数据结构化，标准化，数据降维，数据可视化是目前大数据或者数据科学重中之重。

目前的数据降维技术

我们可以用一张图来说明一下目前的数据降维技术

目前数据降维技术

• 主成分分析算法（PCA）
  Principal Component Analysis(PCA)是最常用的线性降维方法，它的目标是通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。
  通俗的理解，如果把所有的点都映射到一起，那么几乎所有的信息（如点和点之间的距离关系）都丢失了，而如果映射后方差尽可能的大，那么数据点则会分散开来，以此来保留更多的信息。可以证明，PCA是丢失原始数据信息最少的一种线性降维方式。（实际上就是最接近原始数据，但是PCA并不试图去探索数据内在结构）
  设n维向量w为目标子空间的一个坐标轴方向（称为映射向量），最大化数据映射后的方差，有：

  
  主成分目标
  

  其中m是数据实例的个数， xi是数据实例i的向量表达， x拔是所有数据实例的平均向量。定义W为包含所有映射向量为列向量的矩阵，经过线性代数变换，可以得到如下优化目标函数：

  
  优化目标函数
  其中tr表示矩阵的迹
  A
  A是数据协方差矩阵。
  容易得到最优的W是由数据协方差矩阵前k个最大的特征值对应的特征向量作为列向量构成的。这些特征向量形成一组正交基并且最好地保留了数据中的信息。
  PCA的输出就是Y = W‘X，由X的原始维度降低到了k维。
  

  PCA追求的是在降维之后能够最大化保持数据的内在信息，并通过衡量在投影方向上的数据方差的大小来衡量该方向的重要性。但是这样投影以后对数据的区分作用并不大，反而可能使得数据点揉杂在一起无法区分。这也是PCA存在的最大一个问题，这导致使用PCA在很多情况下的分类效果并不好。具体可以看下图所示，若使用PCA将数据点投影至一维空间上时，PCA会选择2轴，这使得原本很容易区分的两簇点被揉杂在一起变得无法区分；而这时若选择1轴将会得到很好的区分结果。

  
  PCA
• Linear Discriminant Analysis（LDA）线性判别分析
  Linear Discriminant Analysis (也有叫做Fisher Linear Discriminant)是一种有监督的（supervised）线性降维算法。与PCA保持数据信息不同，LDA是为了使得降维后的数据点尽可能地容易被区分！
  了解详情可参考LDA线性判别

• 基于重建权值 （LLE）
  Locally linear embedding（LLE）是一种非线性降维算法，它能够使降维后的数据较好地保持原有流形结构。LLE可以说是流形学习方法最经典的工作之一。很多后续的流形学习、降维方法都与LLE有密切联系。
  见图1，使用LLE将三维数据（b）映射到二维（c）之后，映射后的数据仍能保持原有的数据流形（红色的点互相接近，蓝色的也互相接近），说明LLE有效地保持了数据原有的流行结构。
  但是LLE在有些情况下也并不适用，如果数据分布在整个封闭的球面上，LLE则不能将它映射到二维空间，且不能保持原有的数据流形。那么我们在处理数据中，首先假设数据不是分布在闭合的球面或者椭球面上。

  
  LLE
  

  LLE算法认为每一个数据点都可以由其近邻点的线性加权组合构造得到。算法的主要步骤分为三步：(1)寻找每个样本点的k个近邻点；（2）由每个样本点的近邻点计算出该样本点的局部重建权值矩阵；（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值。具体的算法流程如图2所示：

  
  流程
• Laplacian Eigenmaps 拉普拉斯特征映射
  继续写一点经典的降维算法，前面介绍了PCA,LDA，LLE，这里讲一讲Laplacian Eigenmaps。其实不是说每一个算法都比前面的好，而是每一个算法都是从不同角度去看问题，因此解决问题的思路是不一样的。这些降维算法的思想都很简单，却在有些方面很有效。这些方法事实上是后面一些新的算法的思路来源。
  Laplacian Eigenmaps看问题的角度和LLE有些相似，也是用局部的角度去构建数据之间的关系。详情可参考：拉普拉斯特征映射
  其他的就不一一介绍了，下面就切入正题，本文将介绍一种新的降维方式

T-SNE降维

TSNE是由SNE衍生出的一种算法，SNE最早出现在2002年，它改变了MDS和ISOMAP中基于距离不变的思想，将高维映射到低维的同时，尽量保证相互之间的分布概率不变，SNE将高维和低维中的样本分布都看作高斯分布，而Tsne将低维中的坐标当做T分布，这样做的好处是为了让距离大的簇之间距离拉大，从而解决了拥挤问题。从SNE到TSNE之间，还有一个对称SNE，其对SNE有部分改进作用。
可以参考TSNE

• 首先介绍一下SNE
  高维数据用X表示，Xi表示第i个样本，低维数据用Y表示，则高维中的分布概率矩阵P定义如下：

  
  X
  

  P(i,j)表示第i个样本分布在样本j周围的概率。delta是依据最大熵原理来决定，entropy=sum(pi*log(pi))，以每个样本点作为中心的delta都需要使得最后分布的熵较小，通常以log(k)为上限，k为你所决定的邻域点的个数。
  低维中的分布概率矩阵计算如下：

  
  Y
  这里我们把低维中的分布看作是均衡的，每个delta都是0.5，由此可以基本判断最后降维之后生成的分布也是一个相对均匀的分布。
  随机给定一个初始化的Y，进行优化，使得Y的分布矩阵逼近X的分布矩阵。我们给定目的函数，用KL散度来定义两个不同分布之间的差距：
  KL
  

  则可以计算梯度为：

  
  SGD
  每次梯度下降的步长可设定固定或者自适应、随机等，也可以加上一个动量的梯度，初始值一般设为1e-4的随机正态分布。
  STEP
  这样通过不断的迭代，就可以达到X,Y分布的逼近

• 对称SNE
  顾名思义，就是让高维和低维中的概率分布矩阵是对称的，能方便运算，但是对拥挤问题无改进。
  低维的分布为：

  
  Y
  

  高维的分布为：

  
  X
  同样采用KL散度作为两个分布之间的差异标准，只是梯度有一些改变：
  梯度

• TSNE
  TSNE对高维中的分布采用对称SNE中的做法，低维中的分布则采用更一般的T分布，也是对称的，我们可以发现sum(P)=sum(Q)=1。
  高维分布：

  
  X
  

  低维一版的T分布

  
  Y
  则梯度为：
  梯度
  TSNE算法流程如下：
  TSNE算法流程
• 最后不得不说一下LargeVis
  这个是最新的流形学数据降维方式，主要也是采用了tnse的思想，LargeVis在t-SNE改进算法的基础上，参考了近年来较为新颖的优化技巧，如随机投影树、负采样、边采样(实质也是负采样)等，直接将训练的时间复杂度降至线性级。
  怎么用可以参考LargeVis

数据降维的实现

推荐大家参考一下数据降维
tsne可以参考TSNE

• 看个tsne的python例子
  import numpy as np
  from sklearn.manifold import TSNE
  X = np.array([[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 1]])
  model = TSNE(n_components=2, random_state=0)
  np.set_printoptions(suppress=True)
  model.fit_transform(X)
  array([[ 0.00017599, 0.00003993],
  [ 0.00009891, 0.00021913],
  [ 0.00018554, -0.00009357],
  [ 0.00009528, -0.00001407]])
  如果数据量比较大，我们可以采用spark来跑tnse
  可以参考： spark-tsne
  在spark这个项目上有个很好的例子，就是MINIST
  MINIST可视化
  如果想更深层次的了解sne -> tsne -> largvis可以参考：
  from-sne-to-tsne-to-largevis