##可视化与降维

可视化是降维的一种，但其与降维有本质的区别。可视化要求我们将数据转化至两位或三维，使人能够直观地感受数据分布的特征，而降维只是数据预处理的一部分，将高维的数据，转化至我们的模型方法能够处理的成都即可。因此可视化的要求要远远高于降维。下面，除了原题目要求的SOM，PCA和MDS方法，我还将对比几个更新的方法如tsne，LLE等。

PCA

PCA的想法很简单，希望通过正交变换，获得方差更大的特征，从而将信息集中在少数几个特征上。这一方法要求最后获得的特征的总方差占到总方差的百分之九十或九十五以上。

但实际上，当数据维数较高，信息分布较分散时，前两三个主成分所占据的方差往往很小，自然也就不能很好地反应数据的真实分布。

\[\hat{X}_{n\times p}=(I-\frac{1}{n}11^T)X_{n \times p}\] \[\hat{X}_{n\times p}=U\Sigma V^T\] \[Y=XV[,1:k]\]

MDS

给定距离矩阵 \((\delta_{ij})_{n\times n}\)，我们希望从距离矩阵复现出坐标矩阵。

优化角度

第一种角度是从优化的角度来看问题，希望找到k维空间中的一系列点，其距离矩阵与真实距离矩阵相似。

find \(x_1,...x_n \in R^k\),

s.t. \[||x_i-x_j||\approx \delta_{ij}\]

\[\min_{x_1,...x_n} \sum_{i,j}^{n} (||x_i-x_j||^2-\delta_{ij}^2)^2\]

但这个优化在实际中不是很理想，因此我们更多地使用矩阵分解的角度来看这个问题。

矩阵分解角度

首先我们将距离矩阵转化为内积矩阵，而内积矩阵是一个负定的矩阵，我们就自然可以对其进行svd分解，从而其前几个最大的特征值对应的特征向量就自然是其在低维空间中的投影。

suppose \(A=(||x_i-x_j||^2)\), \(P=I-\frac{1}{n}11^T\)

then \(\hat{A}=-\frac{1}{2}PAP=PX(PX)^T\)

from distance matrix to inner product matrix (semi-positive definite)

另外我们还可以证明每一个特定的距离矩阵是和一组低维空间坐标一一对应的，这就为这个方法提供来理论保障:

###Lemma

if A is a distance amtrix and the rank of \(-\frac{1}{2}PAP\) is k,

then \(\exists y_1,...y_n \in R^k\), s.t. \(A_{ij}=||y_i-y_j||^2\)

分析与拓展

值得一提的是，在距离取二范数的时候，MDS就是PCA的另一种形式。另外，我们还可以取各种\(L_n\)范数作为距离。还有一种常用的选择是径向基核函数，我们可以选定一些基准点，构造新的径向基核函数矩阵，然后再计算距离矩阵进行可视化。

##SOM

SOM的想法非常巧妙，通过神经元之间的互相竞争来确定聚类：

对于每一次输入，输出层某神经元得到最大的值而获胜，与此同时，该神经元周围的神经元也收到神经元间的互相刺激，改变与输入神经元的连接参数。这就保证来在每一次更新之时，神经元（降维后结果）之间依然保持所代表的数据（降维前）的邻接关系。

具体的权值修正可以是简单的梯度下降法，与神经网络有很大的相似性，只不过为了聚类的效果，另外增加了神经元之间的互相作用。

##t-sne, t-distribution stochastic neighbor embindding ### Algorithm

t-sne是现在被广泛使用的一个很有效的可视化降维手段，因此我也将其列在这里进行分析比较。

t-sne的想法是，先根据高维空间中点之间的距离，计算出相互的转移概率，或者说相似度。然后，我们希望降维后的点保持这个相似度不变。具体的来说，就是使得两者的信息熵最小化。

\[P(x^j|x^i)=\frac{S(x^i,x^j)}{\sum_{k\not = i}S(x^i,x^k)},\ \ S(x^i,x^j)=exp(-\frac{||x^i-x^j||^2}{\sigma^2})\] \[Q(z^j|z^i)=\frac{S'(z^i,z^j)}{\sum_{k\not = i}S'(z^i,z^k)},\ \ S'(z^i,z^j)=(1+||z^i-z^j||^2)^{-1}\] \[L=\sum_{i}KL\left( P(*|x^i)||Q(*|z^i) \right) =\sum_{i}\sum_{j}P(x^j|x^i)log\frac{P(x^j|x^i)}{Q(z^j|z^i)}\]

随后我们可以使用梯度下降法进行最优化，由于t分布跟正态分布的关系很紧密，因此求导之后依然有简洁的形式。

\[\frac{dL}{dz_i}=4\sum_{j}(p_{ij}-q_{ij}](z_i-z_j)(1+||z^i-z^j||^2)^{-1}\]

Advantage of Long Tail(t distribution)

t分布由于是重尾，因此对于离群点更佳稳健，参数不会轻易改变。而相对比的，正态分布易受离群点对影响，在有离群点的情况下，参数估计会出现较大的偏差。

至于tsne为什么在两步转化分别使用正态分布和t分布，我们可以由高维的初始数据和低维的降维后的数据性质来分析。

对于高维的初始数据，数据的分布往往是非常稀疏的；可以想象一个n维的球内的均匀分布，随着n的增大，绝大多数点会聚集在球的边缘。因此，我们希望从距离转化为相似度时，使更远的点，相似度更低；而更近的点，相似度更高。

对于低维的降维后的数据，由于样本往往很多，而维度较低，可视化之后的效果往往会是点与点之间很拥挤。这就要求我们将相似度转化为距离时，让相似度高的点凑得更近，而相似度低的点离得更远，从而解决拥挤的问题。

##LLE

\(X_{n \times p}\) is the data

1, 对于每个点，找到它的最近邻

\[\forall x_i, KNN: x^i_1,x^i_2,...,x^i_k\]

2, 通过最近邻，找到最近邻到这一点的线性表出

\[\min_w ||x_i-\sum_{j=1}^{k}w_jx^i_j||\]

3,我们希望在全局坐标上，依然保持这一线性表出大致不变 \[\min_{Y\in R^q} \sum_{i=1}^{n}||y_i-\sum_{j=1}^{n}\hat{w}_{ij}y_j||\]

LLE的缺点

当降维的lower dimension比k近邻个数少时，表出方法不唯一，这是这个方法的一个重大缺陷。比如当我们想要做到可视化，降至二维，那么我们就只能使用2个近邻，这是远远不够的，我们希望能有更稳定的，能容许我们采用更多近邻的方法。下面我采用的是LTSA。

Local Tagent Space Alignment

\(X_{n \times p}\) is the data

1, 找到k个最近邻 \[\forall x_i, KNN: x_{i_1},...,x_{i_k}\] \[X_i=(x_{i_1},...,x_{i_k})\] 2, 找到局部流形 \[\min_{x,\Theta,Q}\sum_{j=1}^{k}||x_{i_j}-(x+Q\theta_j)||^2_2= \min_{x,\Theta,Q} ||X_i-(xe^T+Q\Theta)||^2_2\] \[\Theta=(\theta_1,...\theta_k) , Q\in R^{p\times d}\]
3, 根据局部流形（local manifold）上的坐标 \(x_{i_j}=\bar{x}_i+Q_i\theta_j^i+\epsilon^i_j\) 确定全局坐标 （global coordinate）$_{i_j}={}_i+L_i_ji+i_j $

\[T_i=(\tau_{i_1},...,\tau_{i_k})\] \[T_i=T_i \frac{ee^T}{k} + L_i\Theta_i+E_i \] \[\min_{T,L_i} \sum_{i=1}^{n}||E_i||^2_2\]

Details

1, Find KNN

2,\[X_i(I-\frac{11^T}{k})=U\Sigma V^T, Q=U[,1:d]\] \[\Theta_i=Q_i^TX_i(I-\frac{11^T}{k})=(\theta^i_1,...\theta^i_k) _{d \times k}\] 3, \[E_i=T_i(I-\frac{11^T}{k})(I-\Theta^+_i\Theta_i)=T_iW_i=TS_iW_i\] \[T=(\tau_1,...\tau_n)\in R^{d \times n}, S_i \in R^{n \times k}\] \[\min_{T} \sum_{i=1}^{n}||E_i||^2_2=\min_{T} tr(T \sum_{i=1}^{n}S_iW_iW_i^TS_i^T T^T) \]

LLE一类的算法（以LTSA为例），更佳注重局部流形的结构，因此在数据分散过于稀疏的情况下并不适用。但当数据结构稠密时，能很好地在降维时保持数据结构。另外，其它的算法不包括对于离群点的处理，因此在可视化时，往往会有几个点很分散，而其他多数点聚在一起，这时候就需要手动排除离群点来观看可视化效果。

##可视化效果分析 ###数据介绍 我采用的混合高斯模型，共有200个样本（往往样本越少，聚类难度越大），分为三类，数据的维数为60维，其中仅有10维含有信息，其余是noise。

###L2范数的MDS(也即是PCA)

L1范数的MDS

径向基核函数

我这里选用的是一个效果较好的例子：\(\Phi(r)=\frac{1}{\sqrt{1+r^2}}\),\(r=||x-x_i||\),\(x_i\)为基准。

我先采用k-means，得到k个聚类中心后，将其作为基准点。

我们可以看到，对于MDS，不同的距离矩阵的选择会有不同的效果：L1和L2范数的分布更接近于原分布，正态分布；而我们选择逆二次函数作为径向基核函数时，降维后的分布更像是分散状的。我们在实际运用中可以尝试多种核函数，来帮助我们分析数据。

t-sne

tsne是近年来被认为最好的可视化方法之一，右图中也可见其效果要明显好于其他方法。且类与类之间保持来可见的距离，易于我们探查聚类的模式。

SOM

SOM可以将数据分布到不同神经节点上，且降维后的相邻节点依然保持降维前的临近关系。R包的结果并不是很显而易见，这里我用每个节点的众数来表示这个节点，从而观察聚类效果。总的来看，som的效果还是不错的。但其缺点是我们无法进一步利用它降维后的结果，而其他方法如MDS，tsne，在降维之后，我们可以使用它们的结果进行聚类。这也是为什么som只能作为分析的辅助手段，而无法作为降维的方法的原因。

##      [,1] [,2] [,3] [,4] [,5] [,6]
## [1,]    3    3    3    3    3    3
## [2,]    0    0    0    0    0    3
## [3,]    2    0    0    0    0    1
## [4,]    2    0    0    0    1    0
## [5,]    2    2    0    0    0    1
## [6,]    2    2    2    1    1    1

LLE (LTSA)

LLE作为降维方法可以很好的保持局部性质，也往往会有线性的特征，但对于一般来说比较稀疏的聚类问题来说，可视化效果并不是很显著。