讲座 | 利用 t-SNE 降维并可视化数据

2018-11-22 本文已影响1人 Kofe_

作者：Siraj Raval
课堂：The Best Way to Visualize a Dataset Easily | Bilibili | Youtube
源码：llSourcell.Visualize_dataset_demo | Github
转载：出于篇幅原因，若需要更好索引阅读，请参阅原博文

目标：在本次课堂中，将对人类活动识别 ( Human Activity Recognition，HAR ) 数据集进行数据可视化呈现，并进行探索性分析以发现知识。而本课堂具体目标则是人类活动状态识别，活动状态包括：Sitting-down，Standing-up，Standing，Walking，Sitting。

具体地，通过降维方法 t-SNE 实现不同活动状态的数据自动 "分类" ( 更准确地说应该是聚类 )，从而在低维度 ( 二维 ) 下复现数据 ( 的特征 )，以便我们理解数据、统计分析数据。
问题：若我们要将要描述如此复杂的数据，即它们拥有的特征 ( 维度 ) 过多了，相对于人类大脑只能理解二维或三维的层面，如此复杂数据我们是难以从中发现知识的。
解决：通过可视化数据来描述它们的特征，具体措施是使用机器学习中的降维方法 T-SNE ( Distributed Stochastic Neighbor Embedding )，把高维空间中的数据以二维或三维的形式表示。
HAR 数据集的数据来源：参与者绑上健身追踪设备，当它们运动起来时，追踪设备会记录这些身体指标数据。

关于HAR 数据集更详细的描述请参考：HAR Set 介绍 | HAR Set 下载

观察数据

每一行数据代表不同的人。
每一列代表某人的身体指标测量数据，如手臂或者前臂的空间位置 ( x，y，z 坐标 )。
在人类活动识别数据集中，每一行 ( 实体 ) 都有类标签标记。且共有 5 种标签：Sitting-down，Standing-up，Standing，Walking，Sitting。

预处理数据

关于 预处理数据 的详细解释，可参考另外一篇文章：Kofe. 如何轻松有效地预处理数据

数据清洗：缺失值处理、光滑噪声数据、识别和删除离群点。
数据集成：多个数据源的数据合并，存放于同一个数据仓库中。
- 实体识别问题：来自多个信息源，各数据源中的实体之间如何匹配，这涉及实体识别问题。如不同数据来源于不同数据库中，现实意义上它们是同一实体，但它们属性的元数据表达却不同 ( 如主键 )。
- 冗余和相关分析：集成多个数据源，数据中可能有多组属性重复存在。而冗余可被相关分析检测到，如分类 ( 标称 ) 属性的卡方检验、数值属性的相关系数、数值属性的方差和协方差。
- 元组重复：元组级检测重复。
数据归约：在尽可能保持数据原貌前提下，最大限度精简数据量。策略包括：
- 维归约：也称为特征归约，减少所考虑的属性的个数。方法包括：小波变换、主成分分析、属性子集选择等。当然利用冗余和相关分析也是可行的。
- 数量归约：用替代的、较小的数据表示形式替换原数据。方法包括：回归和对数线性模型、聚类、降维等。
  
  在本课堂中则使用了降维方法进行属性数量的归约，其中降维方法有：PCA、t-SNE $^{[4]}$ 、LargeVis $^{[5, 6]}$ 等。
数据变换：主要思想是将数据变换或统一成适合数据挖掘的形式。方法可以是数据归一化、数据离散化、概念分层等。
- 特征构造：由给定的属性构造新的属性并添加至属性集中。
- 聚集分解：对数据进行 汇总 或者 聚集。如聚集季度销售数据。与之相对的是 分解，如常见的 “日期” 属性，不同的需求，我们要解构的粒度是不同的。如预测当日的气温变化，则我们可把年和月份剔除。
- 归一化：针对每一个特征 ( 维度 )，去均值和方差归一化。即把属性数据按比例缩放，让所有特征在统一数量级上运作，如此一来数据指标之间就有了可比性。
- 离散化：数值属性的原始值用区间标签或者概念标签替换，即这些标签可递归地组织成更高层概念，导致数值属性的 概念分层。
  
  例如，我们对年龄进行分层：1 to 17 为 Adolescent；18 to 45 为 Adult；46 以上为 Senior。

数据可视化

降维方法

降维目的

通过降维算法来寻找 数据内部的本质结构特征，如特征选择或特征提取。
- 特征选择：假定数据中包含大量冗余或无关变量 ( 或称特征、属性、指标等 )，旨在从原有变量中找出主要变量。其代表方法为 LASSO。
- 特征提取：是将高维数据转化为低维数据的过程。在此过程中可能舍弃原有数据、创造新的变量。其代表方法为 PCA。
在原始的高维空间中，包含有冗余信息、噪音信息。通过降维方法，减少冗余信息 所造成的误差，以提高模型的精度。

降维本质

机器学习领域中，降维指采用某种映射方法将原高维空间中的数据点映射到低维度的空间中。
降维的本质是学习一个映射函数 $f : x \to y$ ，其中 $x$ 是原始数据点的表达， $y$ 是数据点映射后的低维向量表达 ( 通常 $y$ 的维度小于 $x$ 的维度 )。 $f$ 可能是显式的或隐式的、线性的或非线性的映射函数 ( 例如本例提及的 PCA 或者 t-SNE )。
当我们意识到需要降维时，一般是发现了特征间的高度线性相关，而 t-SNE 主打的是非线性降维；若我们发现了线性相关，则适合使用 PCA 处理 $^{[1]}$ 。

降维算法

PCA

PCA：主成分分析算法 ( Principal Component Analysis，PCA )，是最常用的 线性降维方法。它通过某种线性投影，将高维的数据映射到低维的空间中表示。为使所有样本的投影点尽可能分开，则需要在所投影的维度上数据的方差最大化。以此，使用较少的数据维度，同时保留住较多的原数据点的特性。

SNE

t-SNE 可理解为 SNE 的特殊形式，我们先了解 SNE 的基本原理，再延伸学习 t-SNE ( 本小节可参考多篇博文比对学习，如参考资料中的 [2] - [3] )。
SNE 是通过仿射变换将数据点映射到概率分布上，主要包括两个步骤：
- SNE 构建一个高维对象之间的概率分布，使得相似的对象有更高的概率被选择，而不相似的对象有较低的概率被选择。
- SNE在低维空间里在构建这些点的概率分布，使之与高维度的概率分布之间尽可能相似。
SNE 的实现原理：
- 原始 SNE 先将 欧几里得距离 转换为 条件概率 来表达点与点之间的相似度。具体地，给定一个 $N$ 个高维的数据 $x_1, x_2, ..., x_N$ ， $x_i$ 和 $x_j$ 之间的相似度可表示为 ( $x_i$ 为中心点 )：
  
  $p_{j|i} = \frac{ exp({-||x^{(i)} - x^{(j)}||}^2 / { 2\sigma_i^2}) }{ \sum_{k \neq i} exp({-||x^{(i)} - x^{(k)}||}^2 / { 2\sigma_i^2}) } \tag{1}$
  
  这里的有一个参数是 $\sigma_i$ ，其表示以 $x_i$ 为中心点的高斯分布的方差。且对于不同的点 $x_i$ 取值不一样 $^{[2]}$ ( 具体参详 SNE 的困惑度 ( Perplexity ) )。再者，由于我们只关心不同点两两之间的相似度，所以设定 $p_{i|i} = 0$ 。
- 在把数据映射到低维空间后，高维数据点之间的相似性也应该在低维空间的数据点上体现出来。这里同样用条件概率的形式描述，对于低维度下的 $y_i$ ，我们可以指定高斯分布为方差为 $\frac{1}{\sqrt2}$ 。因此它们之间的相似度为:
$q_{j|i} = \frac{ exp( {-||y^{(i)} - y^{(j)}||}^2 ) }{ \sum_{k \neq i} exp( {-||y^{(i)} - y^{(k)}||}^2 ) } \tag{2}$
- 同理，设定 $q_{i|i} = 0$ 。这样一来，若 $y_i$ 和 $y_j$ 真实反映了高维数据点 $x_i$ 和 $x_j$ 之间的关系，那么条件概率 $p_{j|i}$ 与 $q_{j|i}$ 应该完全相等。
  
  这里我们只考虑 $x_i$ 与 $x_j$ 之间的条件概率，则它们可构成一个条件概率分布函数 $P$ 。同理，只考虑 $y_i$ 与 $y_j$ 之间的条件概率，在低维空间存在一个条件概率分布 $Q$ ，且应该与 $P$ 是一致的。
  
  如何衡量两个分布之间的相似性？则我们可通过优化两分布的距离，即 K-L 散度 ( Kullback-Leibler Divergence )。SNE 最终目标就是对所有数据点最小化这个 K-L 散度，具体地，我们可使用 梯度下降算法 最小化以下代价函数：
  
  $C = D_{KL}(P || Q) = \sum_{i} \sum_{j} p_{j|i} log \frac{p_{j|i}}{q_{j|i}} \tag{3}$
  
  SNE 代价函数对 $y_i$ 求梯度后的形式如下：
  
  $\frac{\delta C}{\delta y_i} = 2 \sum_j ( p_{j|i} - q_{j|i} + p_{i|j} - q_{i|j} )( y_i - y_j ) \tag{4}$
- 似乎到这里问题就解决了，得到代价函数，利用梯度下降算法进行训练了。但事情远没有那么简单，因为 K-L 散度是一个非对称的度量，最小化代价函数的目的是让 $pj|i$ 和 $qj|i$ 的值尽可能的接近，即低维空间中点的相似性应当与高维空间中点的相似性一致。
  - 但从代价函数的形式就可以看出，考虑到离群点的情况，当 $p_{j|i}$ 较大， $q_{j|i}$ 较小时，即高维空间中两个数据点距离较近，而映射到低维空间后距离较远，那么将得到一个很高的惩罚，这没什么问题；
  - 而 $p_{j|i}$ 较小， $q_{j|i}$ 较大时，即高维空间中两个数据点距离较远，而映射到低维空间距离较近，将得到一个很低的惩罚值。然而这就是问题所在，理应得到一个较高的惩罚才对。换句话说，SNE 的代价函数更关注局部结构，而忽视了全局结构。

t-SNE

在原始 SNE 中， $p_{i|j}$ 与 $p_{j|i}$ 是不相等的，低维空间中 $q_{i|j}$ 与 $q_{j|i}$ 也是不相等的。若我们分别在高维和低维空间构造更加通用的联合概率分布 $P$ 和 $Q$ ，使得对任意 i, j，均有 $p_{i|j} = p_{j|i}, \, q_{i|j} = q_{j|i}$ 。而这种 SNE 称之为对称 SNE ( Symmetric SNE )，因此它们的概率分布可改写为 ( 同理，我们只关注不同点两两之间的相似性，故设定 $p_{i||i} = 0, q_{i||i} = 0$ ):

$p_{i, j} = \frac{ exp({-||x^{(i)} - x^{(j)}||}^2 / { 2\sigma_i^2}) }{ \sum_{k \neq l} exp({-||x^{(k)} - x^{(l)}||}^2 / { 2\sigma_i^2}) } \\ q_{i, j} = \frac{ exp( {-||y^{(i)} - y^{(j)}||}^2 ) }{ \sum_{k \neq l} exp( {-||y^{(k)} - y^{(l)}||}^2 ) } \tag{5}$
这样表达方式使得整体简洁了很多。但是会引入异常值的问题。比如， $x_i$ 是异常值，那么 $||x^{(i)} - x^{(j)}||^2$ 会很大，对应的所有的 $j$ , $p_{i, j}$ 都会很小，导致低维映射下的 $y_i$ 无论处在什么位置，对代价函数影响很小。

为了解决这个问题，我们将联合概率分布改写为：

$p_{i,j} = \frac{ p_{j|i} + p_{i|j} }{2N} \tag{6}$
其中 N 为数据点的总数，这样定义即满足了对称性，又保证了 $x_i$ 的惩罚值不会过小。此时可以利用 KL 距离写出如下代价函数：

$C = D_{KL}(P || Q) = \sum_{i} \sum_{j} p_{i, j} log \frac{p_{i, j}}{q_{i, j}} \tag{7}$
对称 SNE 的最大优点，即梯度计算变得简单了：

$\frac{\delta C}{\delta y_i} = 4 \sum_j ( p_{i, j} - q_{i, j})( y_i - y_j ) \tag{8}$

但是Maaten 还指出 $^{[4]}$ ，对称 SNE 的效果只是略微优于原始 SNE 的效果，依然没有从根本上解决问题。我们还需要解决 拥挤问题。

拥挤问题：就是说各个簇聚集在一起，无法区分。这是由于高维空间距离分布和低维空间距离分布的差异造成的。比如，有一高维度数据在降维到 10 维下可以有很好的表达，但是降维到两维后无法得到 "可信" 映射。

进一步说明，假设一个以数据点 $x_i$ 为中心，半径为 $r$ 的 $m$ 维球 ( 三维空间就是球 )，其体积是按 $r^m$ 增长的，假设数据点是在 m 维球中均匀分布的，我们来看看其他数据点与 $x_i$ 的距离随维度增大而产生的变化。具体，我们可参考代码 $^{[3]}$ ：

import numpy as np
from numpy.linalg import norm
import matplotlib.pyplot as plt

npoints = 1000  # 抽取 1000 个 m 维球内均匀分布的点
plt.figure( figsize=(20, 4) )
for i, m in enumerate((2, 3, 5, 8)):
    # 这里模拟 m 维球中的均匀分布用到了拒绝采样
    # 即先生成 m 维立方中的均匀分布，再剔除 m 维球外部的点
    accepts = []
    while len(accepts) < 1000:
        points = np.random.rand(500, m)
        accepts.extend(
            [d for d in norm(points, axis=1) if d <= 1.0]
        ) # 拒绝采样
    accepts = accepts[:npoints]
    ax = plt.subplot(1, 4, i+1)
    ax.set_xlabel('distance') # x 轴表示点到圆心的距离
    if i == 0:
        ax.set_ylabel('count') # y 轴表示点的数量
    ax.hist(accepts, bins=np.linspace(0., 1., 50), color='green')
    ax.set_title('m={0}'.format(str(m)), loc='left')
plt.show()

运行结果如图 2-1 所示。据图示反映，随着维度的增大，大部分数据点都聚集在 m 维球的表面附近，与点 $x_i$ 的距离分布极不均衡。若直接将这种距离关系保留到低维，肯定会出现拥挤问题。如何解决呢？这个时候就需要请出 $\tau$ 分布了。
图 2-1 半径为 r 的 m 维球上的数据分布
减轻 拥挤问题 的方法：在高维空间下我们使用 高斯分布 将距离转换为概率分布；在低维空间下，我们使用更加 偏重长尾分布 的方式来将距离转换为概率分布，使得高维度下中低等的距离在映射后能够有一个较大的距离。使用了自由度为 1 的 $\tau$ 分布之后的 $q$ 变化，如下:

$q_{i,j} = \frac{ (1 + ||y^{(i)} - y^{(j)}||^2)^{-1} }{ \sum_{k \neq l} (1 + ||y^{(k)} - y^{(l)}||^2)^{-1} } \tag{9}$

依然用 K-L 距离衡量两个分布之间的相似性，此时梯度变为：

$\frac{\delta C}{\delta y_i} = 4 \sum_j ( p_{i, j} - q_{i, j})( y_i - y_j )(1 + ||y^{(i)} - y^{(j)}||^2)^{-1} \tag{10}$
总结：综上所述，从不对称的 SNE 算法到 t-SNE 算法，所做的改进工作：
- 把 SNE 变为对称 SNE；
- 在低维空间中采用了 $\tau$ 分布代替原来的高斯分布，高维空间不变。
- 具体算法步骤可参考了文章 [7] 的 t-SNE 图文解释，如图 2-2 所示。
图 2-2 t-SNE的算法步骤

数据展示

参考资料

[1] 微调. t-SNE 数据可视化算法的作用是为了降维还是认识数据. zhihu.com
[2] Chrispher. t-SNE 完整笔记 [OL]. datakit.cn. 2017
[3] Bindog. 从 SNE 到 t-SNE 再到 LargeVis. bindog.github.io. 2016
[4] Maaten L, Hinton G. Visualizing data using t-SNE [J]. Journal of machine learning r/esearch, 2008, 9(Nov): 2579-2605.
[5] Tang J, Liu J, Zhang M, et al. Visualizing large-scale and high-dimensional data[C]. International World Wide Web Conferences Steering Committee, 2016: 287-297.
[6] Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]. International World Wide Web Conferences Steering Committee, 2015: 1067-1077.
[7] 徐小贱民. 降维技术解析：PCA, t-SNE and Auto Encoders. zhihu.com