精华内容
下载资源
问答
  • 高维信息降维可视化常用算法比较

    千次阅读 2019-07-17 21:08:52
    这里引入了常用降维算法模型原理,对MNIST 784维数据做可视化和结果对比展示,其中的大部分算法可用来减少数据维度,减少特征数,去除噪声干扰信息,压缩数据,降低计算量。公式原理等是引用他人内容,如侵权联系...

    我们人类比较容易理解三维以内的信息,在做数据分析挖掘以前,先要对数据集有个浅显的认识,比如统计分布、可视化、相关性等。这里引入了常用降维算法模型原理,对MNIST 784维数据做可视化和结果对比展示,其中的大部分算法可用来减少数据维度,减少特征数,去除噪声干扰信息,压缩数据,降低计算量。公式原理等是引用他人内容,如侵权联系删除。

    常用算法列举和特点

     算法 特点 MNIST效果
    1. PCA 线性降维、运行时间短(1s/3000条) 极差
    TSNE 非线性降维、运行时间短(1452s/70000条) 一般
    LargeVis 非线性降维、运行时间一般(686s/70000条) 最好
    UMAP 非线性降维、运行时间短(16s/4000条) 较好
    AUTO_ENCODER 非线性降维、运行时间一般(135s/65000条) 一般

     

    1. PCA

    1.1 算法原理

    PCA(Principal Component Analysis),即主成分分析方法,是一种使用最广泛的数据线性降维算法。PCA的主要思想是将n维特征映射到k(其中k<n)维上,这k维是全新的正交特征也被称为主成分,是在原有n维特征的基础上重新构造出来的k维特征。PCA的工作就是从原始的空间中顺序地找一组相互正交的坐标轴,新的坐标轴的选择与数据本身是密切相关的。其中,第一个新坐标轴选择是原始数据中方差最大的方向,第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的,第三个轴是与第1,2个轴正交的平面中方差最大的。依次类推,可以得到n个这样的坐标轴。(这部分操作类似决策树,先找到一个包含信息最多的切分点,在分离后的结果内找另一个最大的切分点。)通过这种方式获得的新的坐标轴,我们发现,大部分方差都包含在前面k个坐标轴中,后面的坐标轴所含的方差几乎为0。于是,我们可以忽略余下的坐标轴,只保留前面k个含有绝大部分方差的坐标轴。事实上,这相当于只保留包含绝大部分方差的维度特征,而忽略包含方差几乎为0的特征维度,实现对数据特征的降维处理。

    这里写图片描述

    1.1.1 协方差

    数学定义协方差 Cov(a,b)=\frac{1}{m-1}\sum_{i=1}^m{(a_i-\overline{a})(b_i-\overline{b})}

    提高计算效率我们先将特征均值化变为0,上面公式简化为Cov(a,b)=\frac{1}{m-1}\sum_{i=1}^m{a_ib_i}

    可以看到,在字段均值为0的情况下,两个字段的协方差简洁的表示为其内积除以元素数m。

    当协方差为0时,表示两个字段完全独立。为了让协方差为0,我们选择第二个基时只能在与第一个基正交的方向上选择。因此最终选择的两个方向一定是正交的。

    至此,我们得到了降维问题的优化目标:将一组N维向量降为K维(K大于0,小于N),其目标是选择K个单位(模为1)正交基,使得原始数据变换到这组基上后,各字段两两间协方差为0,而字段的方差则尽可能大(在正交的约束下,取最大的K个方差)

    矩阵是空间里的线性变换,PCA其实为矩阵分解,矩阵分解其实在原空间的子空间中找出线性变换中的主要变化趋势,减少冗余特征和不显著的特征。各维度相关性和噪声可以通过协方差矩阵表示,特征之间协方差为0去除了线性相关,剔除方差比较小的特征代表的噪声。

    1.1.2 协方差矩阵

    上面我们导出了优化目标,但是这个目标似乎不能直接作为操作指南(或者说算法),因为它只说要什么,但根本没有说怎么做。所以我们要继续在数学上研究计算方案。

    我们看到,最终要达到的目的与字段内方差及字段间协方差有密切关系。因此我们希望能将两者统一表示,仔细观察发现,两者均可以表示为内积的形式,而内积又与矩阵相乘密切相关。于是我们来了灵感:

    假设我们只有a和b两个字段,那么我们将它们按行组成矩阵X:

    X^\mathsf{T}=\begin{pmatrix} a_1 & a_2 & \cdots & a_m \\ b_1 & b_2 & \cdots & b_m \end{pmatrix}

    然后我们用X乘以X的转置,并乘上系数1/m:

    \frac{1}{m-1}X^\mathsf{T}X=\begin{pmatrix} \frac{1}{m-1}\sum_{i=1}^m{a_i^2} & \frac{1}{m-1}\sum_{i=1}^m{a_ib_i} \\ \frac{1}{m-1}\sum_{i=1}^m{a_ib_i} & \frac{1}{m-1}\sum_{i=1}^m{b_i^2} \end{pmatrix}

    奇迹出现了!这个矩阵对角线上的两个元素分别是两个字段的方差,而其它元素是a和b的协方差。两者被统一到了一个矩阵的。

    根据矩阵相乘的运算法则,这个结论很容易被推广到一般情况:

     

    设我们有m个n维数据记录,将其按列排成n乘m的矩阵X,设 C=\frac{1}{m-1}X^\mathsf{T}X,则C是一个对称矩阵,其对角线分别为各个字段的方差,而第i行j列和j行i列元素相同,表示i和j两个字段的协方差

    1.1.3 协方差矩阵对角化

    根据上述推导,我们发现要达到优化目标,等价于将协方差矩阵对角化:即除对角线外的其它元素化为0,并且在对角线上将元素按大小从上到下排列,这样我们就达到了优化目的。这样说可能还不是很明晰,我们进一步看下原矩阵与基变换后矩阵协方差矩阵的关系:

    设原始数据矩阵X对应的协方差矩阵为C,而P是一组基按行组成的矩阵,设Y=XP,则Y为X对P做基变换后的数据。设Y的协方差矩阵为D,我们推导一下D与C的关系:

    \begin{array}{l l l} D & = & \frac{1}{m-1}Y^\mathsf{T}Y \\ & = & \frac{1}{m-1}(XP)^\mathsf{T}(XP) \\ & = & \frac{1}{m-1}P^\mathsf{T}X^\mathsf{T}XP \\ & = & P^\mathsf{T}(\frac{1}{m-1}X^\mathsf{T}X)P \\ & = & P^\mathsf{T}CP \end{array}

    现在事情很明白了!我们要找的P不是别的,而是能让原始协方差矩阵对角化的P。换句话说,优化目标变成了寻找一个矩阵P,满足P^\mathsf{T}CP是一个对角矩阵,并且对角元素按从大到小依次排列,那么P的前K行就是要寻找的基,用P的前K行组成的矩阵乘以X就使得X从N维降到了K维并满足上述优化条件

    至此,我们离“发明”PCA还有仅一步之遥!

    现在所有焦点都聚焦在了协方差矩阵对角化问题上,有时,我们真应该感谢数学家的先行,因为矩阵对角化在线性代数领域已经属于被玩烂了的东西,所以这在数学上根本不是问题。

    由上文知道,协方差矩阵C是一个是对称矩阵,在线性代数上,实对称矩阵有一系列非常好的性质:

    1)实对称矩阵不同特征值对应的特征向量必然正交。

    2)设特征向量λ重数为r,则必然存在r个线性无关的特征向量对应于λ,因此可以将这r个特征向量单位正交化。

    由上面两条可知,一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量,设这n个特征向量为e_1,e_2,\cdots,e_n

    我们将其按列组成矩阵:

    E=\begin{pmatrix} e_1 & e_2 & \cdots & e_n \end{pmatrix}

    则对协方差矩阵C有如下结论:

    E^\mathsf{T}CE=\Lambda=\begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{pmatrix}

    其中Λ为对角矩阵,其对角元素为各特征向量对应的特征值(可能有重复)。

    以上结论不再给出严格的数学证明,对证明感兴趣的朋友可以参考线性代数书籍关于“实对称矩阵对角化”的内容。

    到这里,我们发现我们已经找到了需要的矩阵P:

                                                    P=E

    P是协方差矩阵的特征向量单位化后按行排列出的矩阵,其中每一行都是C的一个特征向量。如果设P按照Λ中特征值的从大到小,将特征向量从上到下排列,则用P的前K行组成的矩阵乘以原始数据矩阵X,就得到了我们需要的降维后的数据矩阵Y。

    至此我们完成了整个PCA的数学原理讨论。在下面的一节,我们将给出PCA的一个实例。

     

    1.2 算法及实例

    为了巩固上面的理论,我们在这一节给出一个具体的PCA实例。

    1.2.1 PCA算法

    总结一下PCA的算法步骤,设有m条n维数据:

    1. 将原始数据按列组成m行n列矩阵X^T = {x_1, ... , x_n}
    2. 目标结果是低维数据表示Y^T = {y_1, ... , y_m}
    3. 将X的每一行(代表一个属性字段)进行零均值化,即减去这一行的均值
    4. 求出协方差矩阵C=\frac{1}{m-1}X^\mathsf{T}X
    5. 求出协方差矩阵的特征值及对应的特征向量
    6. 将特征向量按对应特征值大小从上到下按行排列成矩阵,取前k行组成矩阵P
    7. Y=XP即为降维到k维后的数据

    1.2.2 代码和结果

    import numpy as np
     
    from sklearn.decomposition import PCA
    from sklearn.model_selection import train_test_split
    from keras.datasets import mnist
     
    (x_train, y_train), (x_test, y_test) = mnist.load_data()
    train_data = x_train.reshape((-1, 784))
    test_data = x_test.reshape((-1, 784))
    data = np.concatenate((train_data, test_data), axis=0)
    label = np.concatenate((y_train, y_test), axis=0)
     
    _, x_run, _, y_run = train_test_split(test_data, y_test, test_size = 0.3, random_state=159)
    x_run = x_run.astype('float32') / 255.0
     
    pca = PCA(n_components=2)
    x_run = pca.fit_transform(x_run)

     

    2. TSNE

    2.1 算法原理

    t-SNE是由SNE(Stochastic Neighbor Embedding, SNE; Hinton and Roweis, 2002)发展而来。这里的Hinton就是大名鼎鼎的2018年图灵奖得主和深度学习的领跑者

    t-SNE(t-distributed stochastic neighbor embedding)是用于降维的一种机器学习算法,是由 Laurens van der Maaten 和 Geoffrey Hinton在08年提出来。此外,t-SNE 是一种非线性降维算法,非常适用于高维数据降维到2维或者3维,进行可视化。

    我们先介绍SNE的基本原理,之后再扩展到t-SNE。最后再看一下t-SNE的实现以及一些优化。

    2.1.1 流行学习

    总觉得即使是“浅谈”两个字,还是让这个标题有些过大了,更何况我自己也才刚刚接触这么一个领域。不过懒得想其他标题了,想起来要扯一下这个话题,也是因为和朋友聊起我自己最近在做的方向。Manifold Learning 或者仅仅 Manifold 本身通常就听起来颇有些深奥的感觉,不过如果并不是想要进行严格的理论推导的话,也可以从许多直观的例子得到一些感性的认识,正好我也就借这个机会来简单地谈一下这个话题吧,或者说至少是我到目前为止对这它的认识。

    这两个词,在谈 Manifold 之前,不妨先说说 Learning ,也就是 Machine Learning 。而说道 Machine Learning 而不提一下 Artificial Intelligence 的话似乎又显得有些不厚道。人说 AI 是一门最悲剧的学科,因为每当它的一个子领域发展得像模像样之后,就立马自立门户,从此和 AI “再无瓜葛”了,而 Machine Learning 大概要算是最新的一个典型吧。这就让人有点奇怪,比如说数学,分门别类总算是够多了吧?可以不管怎么分,大家兄弟姐妹也都还承认自己是叫“数学”的。那 AI 呢?我觉得这里有很大一部分是它自身定位的问题。

    反正现在我是不太清楚 AI 是做什么的,不知道其他人到底清楚不清楚。Wikipedia 上说

    Artificial intelligence (AI) is the intelligence of machines and the branch of computer science that aims to create it.

    可是这相当于一个 tautology ,因为到底什么又是 the intelligence of machines 呢?一开始的时候,大牛们都野心勃勃,而且好像也是信心满满,就好像曾经广泛认为“牛顿定理揭示了宇宙真理,科学剩下的事情只要按照公式来做计算就可以了”一样,大家可能觉得,不出几十年,人类就可以不用思考,交给 AI 来做了。不过我这里并不想再多说诸如什么是“思考”,什么是“智能”之类的以及随之而来的“图灵测试”之类的话题。我想说的是,到头来,AI 到底是什么,这还是一个问题,或者说,AI 在一开始定了一个过高的目标,几十年后,发现情况并不像当年那么乐观,却又有些下不了台了。

    这个时候,AI 的一些旁枝或者子领域果断放下面子,丢掉了那个近乎玄幻的目标,逐渐发展成为“正常”的学科,所以也就不再好称为 AI 了。或者说现在的 AI 有两个意思,一个广义的 AI ,包括了所有相关的以及派生的领域,另一个则是狭义的或者经典的 AI ,专门指那些仍然在执着地追求着真正的“智能”的部分,或者说得不好听一点,就是剩下的部分。

    Machine Learning 作为离家出走的典型,虽然名字里带了 Learning 一个词,让人乍一看觉得和 Intelligence 相比不过是换了个说法而已,然而事实上这里的 Learning 的意义要朴素得多。我们来看一看 Machine Learning 的典型的流程就知道了,其实有时候觉得和应用数学或者更通俗的数学建模有些类似,通常我们会有需要分析或者处理的数据,根据一些经验和一些假设,我们可以构建一个模型,这个模型会有一些参数(即使是非参数化方法,也是可以类似地看待的),根据数据来求解模型参数的过程,就叫做 Parameter Estimation ,或者 Model Fitting ,但是搞机器学习的人,通常把它叫做 Learning (或者,换一个角度,叫 Training)——因为根据数据归纳出一个有用的模型,这和我们人类“学习”的过程还是挺类似的吧。不过,如果抛开无聊的抠字眼游戏的话,我们可以看到,Machine Learning 已经抛弃了“智能”的高帽子,它的目的就是要解决具体的问题——而并不关心是否是通过一种“智能”的方式类解决的。

    说到这里,其实我们构造模型就类似于写一个类,数据就是构造函数的参数,Learning 就是构造函数运行的过程,成功构造一个对象之后,我们就完成了学习。一些 Machine Learning 的问题到这一步就结束了,另一些情况还会使用得到的模型(对象)对后来的数据进行一些处理,通常会是 Inferencing 。到这个时候,又有些像统计里的东西了,所谓“统计推断”嘛。其实原本统计和机器学习研究的不少问题就是交叉在一起的,不过两派人从不同的角度来看待同样的问题。而且,也确实有 Statistical Learning 这么一个说法存在的,可以把他看成是 Machine Learning 的一个子领域(或者是一个分子或者甚至就是 Machine Learning 本身)。

    到这里,如果你还没有因为不断地抠字眼而烦躁的话,我已经忍无可忍了。所以,我就假定你已经了解了什么叫 Learning ,或者是已经恶心到懒得去了解了。于是我们转入下一个话题:流形,也就是 Manifold 。不知道你有没有为我在本文开头放上的那个地球的图片感到困惑?这是因为球面是一个很典型的流形的例子,而地球就是一个很典型的“球面”啦(姑且当作球面好啦)。

    有时候经常会在 paper 里看到“嵌入在高维空间中的低维流形”,不过高维的数据对于我们这些可怜的低维生物来说总是很难以想像,所以最直观的例子通常都会是嵌入在三维空间中的二维或者一维流行。比如说一块布,可以把它看成一个二维平面,这是一个二维的欧氏空间,现在我们(在三维)中把它扭一扭,它就变成了一个流形(当然,不扭的时候,它也是一个流形,欧氏空间是流形的一种特殊情况)。

    所以,直观上来讲,一个流形好比是一个 d 维的空间,在一个 m 维的空间中 (m > d) 被扭曲之后的结果。需要注意的是,流形并不是一个“形状”,而是一个“空间”,如果你觉得“扭曲的空间”难以想象,那么请再回忆之前一块布的例子。如果我没弄错的话,广义相对论似乎就是把我们的时空当作一个四维流(空间三维加上时间一维)形来研究的,引力就是这个流形扭曲的结果。当然,这些都是直观上的概念,其实流形并不需要依靠嵌入在一个“外围空间”而存在,稍微正式一点来说,一个 d 维的流形就是一个在任意点处局部同胚于(简单地说,就是正逆映射都是光滑的一一映射)欧氏空间{R}^d。实际上,正是这种局部与欧氏空间的同胚给我们带来了很多好处,这使得我们在日常生活中许许多多的几何问题都可以使用简单的欧氏几何来解决,因为和地球的尺度比起来,我们的日常生活就算是一个很小的局部啦——我突然想起《七龙珠》里的那个界王住的那种私人小星球,走几步就要绕一圈的感觉,看来界王不仅要体力好(那上面重力似乎是地球的十倍),而且脑力也要好,初中学的必须是黎曼几何了!

    那么,除了地球这种简单的例子,实际应用中的数据,怎么知道它是不是一个流形呢?于是不妨又回归直观的感觉。再从球面说起,如果我们事先不知道球面的存在,那么球面上的点,其实就是三维欧氏空间上的点,可以用一个三元组来表示其坐标。但是和空间中的普通点不一样的是,它们允许出现的位置受到了一定的限制,具体到球面,可以可以看一下它的参数方程:

    \begin{aligned} x &= x_0 + r \sin \theta \; \cos \varphi \\ y &= y_0 + r \sin \theta \; \sin \varphi \qquad (0 \leq \varphi \leq 2\pi \mbox{ and } 0 \leq \theta \leq \pi )\\ z &= z_0 + r \cos \theta \end{aligned}

    可以看到,这些三维的坐标实际上是由两个变量\theta\varphi生成的,也可以说成是它的自由度是二,也正好对应了它是一个二维的流形。有了这样的感觉之后,再来看流形学习里经常用到的人脸的例子,就很自然了。下图是 Isomap 论文里的一个结果:

    这里的图片来自同一张人脸(好吧,其实是人脸模型),每张图片是 64×64 的灰度图,如果把位图按照列(或行)拼起来,就可以得到一个 4096 维的向量,这样一来,每一张图片就可以看成是 4096 维欧氏空间中的一个点。很显然,并不是 4096 维空间中任意一个点都可以对应于一张人脸图片的,这就类似于球面的情形,我们可以假定所有可以是人脸的 4096 维向量实际上分布在一个 d 维 (d < 4096) 的子空间中。而特定到 Isomap 的人脸这个例子,实际上我们知道所有的 698 张图片是拍自同一个人脸(模型),不过是在不同的 pose 和光照下拍摄的,如果把 pose (上下和左右)当作两个自由度,而光照当作一个自由度,那么这些图片实际只有三个自由度,换句话说,存在一个类似于球面一样的参数方程(当然,解析式是没法写出来的),给定一组参数(也就是上下、左右的 pose 和光照这三个值),就可以生成出对应的 4096 维的坐标来。换句话说,这是一个嵌入在 4096 维欧氏空间中的一个 3 维流形。 实际上,上面的那张图就是 Isomap 将这个数据集从 4096 维映射到 3 维空间中,并显示了其中 2 维的结果,图中的小点就是每个人脸在这个二维空间中对应的坐标位置,其中一些标红圈的点被选出来,并在旁边画上了该点对应的原始图片,可以很直观地看出这两个维度正好对应了 pose 的两个自由度平滑变化的结果。 就我目前所知,把流形引入到机器学习领域来主要有两种用途:一是将原来在欧氏空间中适用的算法加以改造,使得它工作在流形上,直接或间接地对流形的结构和性质加以利用;二是直接分析流形的结构,并试图将其映射到一个欧氏空间中,再在得到的结果上运用以前适用于欧氏空间的算法来进行学习。 这里 Isomap 正巧是一个非常典型的例子,因为它实际上是通过“改造一种原本适用于欧氏空间的算法”,达到了“将流形映射到一个欧氏空间”的目的。 :) Isomap 所改造的这个方法叫做 Multidimensional Scaling (MDS) ,MDS 是一种降维方法,它的目的就是使得降维之后的点两两之间的距离尽量不变(也就是和在原是空间中对应的两个点之间的距离要差不多)。只是 MDS 是针对欧氏空间设计的,对于距离的计算也是使用欧氏距离来完成的。如果数据分布在一个流形上的话,欧氏距离就不适用了。

    让我们再回到地球——这个在三维空间中的二维流形,假设我们要在三维空间中计算北极点和南极点的距离,这很容易,就是两点相连的线段的长度,可是,如果要在这个流形上算距离就不能这样子算了,我们总不能从北极打个洞钻到南极去吧?要沿着地球表面走才行,当然,如果我随便沿着什么路线走一遍,然后数出总共走了多少步作为距离,这是不成的,因为这样一来如果我沿着不同的路线走,岂不是会得到不同的距离值?总而言之,我们现在需要一个新的定义在地球表面(流形)上的距离度量,理论上来说,任意满足测度的 4 个条件的函数都可以被定义为距离,不过,为了和欧氏空间对应起来,这里选择一个直线距离的推广定义。

    还记得初中学的“两点之间,线段最短”吗?现在,我们反过来说,把线段的概念推广一下,变成“两点之间最短的曲线是线段”,于是流形上的距离定义也就等同于欧氏空间了:流形上两个点之间的距离就是连接两个点的“线段”的长度。虽然只是置换了一个概念,但是现在两者统一起来了,不过,在流形上的线段大概就不一定是“直”的了(于是直线也变成不一定是“直”的了),通常又称作是“测地线”。对于球面这个简单的流形来说,任意一条线段必定是在一个“大圆”上的,于是球面上的直线其实都是一些大圆,也造成了球面这个流形上没有平行线等一系列尴尬的局面(任意两条直线均相交),如果你看过一些数学科普八卦类的书,应该会回忆起不少东西啦!

    回到 Isomap ,它主要做了一件事情,就是把 MDS 中原始空间中距离的计算从欧氏距离换为了流形上的测地距离。当然,如果流形的结构事先不知道的话,这个距离是没法算的,于是 Isomap 通过将数据点连接起来构成一个邻接 Graph 来离散地近似原来的流形,而测地距离也相应地通过 Graph 上的最短路径来近似了。如下图所示:

    这个东西叫做 Swiss Roll ,姑且把它看作一块卷起来的布好了。图中两个标黑圈的点,如果通过外围欧氏空间中的欧氏距离来计算的话,会是挨得很近的点,可是在流形上它们实际上是距离很远的点:红色的线是 Isomap 求出来的流形上的距离。可以想像,如果是原始的 MDS 的话,降维之后肯定会是很暴力地直接把它投影到二维空间中,完全无视流形结构,而 Isomap 则可以成功地将流形“展开”之后再做投影。

    除了 Isomap 之外,Manifold Embedding 的算法还有很多很多,包括 Locally Linear Embedding 、Laplacian Eigenmaps 、Hessian Eigenmaps 、Local Tangent Space Alignment、Semidefinite Embedding (Maximum Variance Unfolding) 等等等等。哪个好哪个坏也不好说,它们都各有特点,而且也各自有不少变种。网上有一个 Matlab 的 demo ,给出了几种流行的 manifold embedding 算法在一些 synthetic manifold 上的结果和对比,可以有一个直观的认识。

    另一方面是改造现有算法使其适合流形结构甚至专门针对流形的特点来设计新的算法,比较典型的是 graph regularized semi-supervised learning 。简单地说,在 supervised learning 中,我们只能利用有 label 的数据,而(通常都会有很多的)没有 label 的数据则白白浪费掉。在流形假设下,虽然这些数据没有 label ,但是仍然是可以有助于 Learn 出流形的结构的,而学出了流形结构之后实际上我们就是对原来的问题又多了一些认识,于是理所当然地期望能得到更好的结果喽。

    当然,所有的这些都是基于同一个假设,那就是数据是分布在一个流形上的(部分算法可能会有稍微宽松一些的假设),然而 real world 的数据,究竟哪些是分别在流形上的呢?这个却是很难说。不过,除了典型的 face 和 hand written digit 之外,大家也有把基于流形的算法直接用在诸如 text 看起来好像也流形没有什么关系的数据上,效果似乎也还不错。

    2.1.2 SNE原理

    SNE是通过仿射(affinitie)变换将数据点映射到概率分布上,主要包括两个步骤:

    • SNE构建一个高维对象之间的概率分布,使得相似的对象有更高的概率被选择,而不相似的对象有较低的概率被选择。
    • SNE在低维空间里在构建这些点的概率分布,使得这两个概率分布之间尽可能的相似。

    我们看到t-SNE模型是非监督的降维,他跟kmeans等不同,他不能通过训练得到一些东西之后再用于其它数据(比如kmeans可以通过训练得到k个点,再用于其它数据集,而t-SNE只能单独的对数据做操作,也就是说他只有fit_transform,而没有fit操作)。

    SNE是先将欧几里得距离转换为条件概率来表达点与点之间的相似度。具体来说,给定一个m个高维的数据x_1, ... , x_m(注意m不是维度), t-SNE首先是计算概率p_{ij},正比于x_ix_j之间的相似度(这种概率是我们自主构建的),即:

    {p_ {j \mid i} = \frac{\exp(- \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i ))} {\sum_{k \neq i} \exp(- \mid \mid x_i - x_k \mid \mid ^2 / (2 \sigma^2_i))}}

     

    这里的有一个参数是\sigma_i,对于不同的点x_i取值不一样,后续会讨论如何设置。此外设置p_{x \mid x}=0,因为我们关注的是两两之间的相似度。

    那对于低维度下的y_i,我们可以指定高斯分布为方差为\frac{1}{\sqrt{2}},因此它们之间的相似度如下:

    {q_ {j \mid i} = \frac{\exp(- \mid \mid x_i -x_j \mid \mid ^2)} {\sum_{k \neq i} \exp(- \mid \mid x_i - x_k \mid \mid ^2)}}

    同样,设定q_{i \mid i} = 0.

    如果降维的效果比较好,局部特征保留完整,那么p_{i \mid j} = q_{i \mid j}, 因此我们优化两个分布之间的距离-KL散度(Kullback-Leibler divergences),那么目标函数(cost function)如下:

    C = \sum_i KL(P_i \mid \mid Q_i) = \sum_i \sum_j p_{j \mid i} \log \frac{p_{j \mid i}}{q_{j \mid i}}

     

    这里的P_i表示了给定点 x_i下,其他所有数据点的条件概率分布。需要注意的是KL散度具有不对称性,在低维映射中不同的距离对应的惩罚权重是不同的,具体来说:距离较远的两个点来表达距离较近的两个点会产生更大的cost,相反,用较近的两个点来表达较远的两个点产生的cost相对较小(注意:类似于回归容易受异常值影响,但效果相反)。即用较小的q_{j \mid i}=0.2来建模较大的p_{j \mid i}=0.8, {\rm cost}=p \log(\frac{p}{q})=1.11,同样用较大的q_{j \mid i}=0.8来建模较大的p_{j \mid i}=0.2, cost=-0.277, 因此,SNE会倾向于保留数据中的局部特征。

    下面我们提供一个参数\sigma_i的合理选择方式,首先不同的点具有不同的\sigma_iP_i的熵(entropy)会随着\sigma_i的增加而增加。SNE使用困惑度(perplexity)的概念,用二分搜索的方式来寻找一个最佳的σ。其中困惑度指:

    Perp(P_i) = 2^{H(P_i)}

     

    这里的 H(P_i)P_i的熵,即:

    H(P_i) = -\sum_j p_{j \mid i} \log_2 p_{j \mid i}

    sum\_exp = \sum_{k \neq i} \exp(- \mid \mid x_i - x_k \mid \mid ^2 / (2 \sigma^2_i))}

    H(P_i) = -\sum_j p_{j \mid i} \log_2 \frac{\exp(- \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i ))} {sum\_exp} \\ = -\sum_j p_{j \mid i} [- \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i ) - \log_2 sum\_exp] \\ = \sum_j p_{j \mid i} [ \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i )] + \sum_j p_{j \mid i}\log_2 sum\_exp \\ = \sum_j \frac{\exp(- \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i ))} {sum\_exp} [ \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i )] + \log_2 sum\_exp \\ = \frac{1} {sum\_exp*(2 \sigma^2_i )} \sum_j ( \mid \mid x_i -x_j \mid \mid ^2 )\exp(- \mid \mid x_i -x_j \mid \mid ^2 / (2 \sigma^2_i )) + \log_2 sum\_exp \\

     

    困惑度可以解释为一个点附近的有效近邻点个数。SNE对困惑度的调整比较有鲁棒性,通常选择5-50之间,给定之后,使用二分搜索的方式寻找合适的σ,那么核心问题是如何求解梯度了,目标函数等价于\sum \sum - p log(q)这个式子与softmax非常的类似,我们知道softmax的目标函数是\sum -y \log p,对应的梯度是y - p(注:这里的softmax中y表示label,p表示预估值)。 同样我们可以推导SNE的目标函数中的i在j下的条件概率情况的梯度是2(p_{i \mid j}-q_{i \mid j})(y_i-y_j), 同样j在i下的条件概率的梯度是2(p_{j \mid i}-q_{j \mid i})(y_i-y_j), 最后得到完整的梯度公式如下:

    \frac{\delta C}{\delta y_i} = 2 \sum_j (p_{j \mid i} - q_{j \mid i} + p_{i \mid j} - q_{i \mid j})(y_i - y_j)

    在初始化中,可以用较小的σσ下的高斯分布来进行初始化。为了加速优化过程和避免陷入局部最优解,梯度中需要使用一个相对较大的动量(momentum)。即参数更新中除了当前的梯度,还要引入之前的梯度累加的指数衰减项,如下:

    Y^{(t)} = Y^{(t-1)} + \eta \frac{\delta C}{\delta Y} + \alpha(t)(Y^{(t-1)} - Y^{(t-2)})

    这里的Y^{(t)}表示迭代t次的解,\eta表示学习速率,\alpha(t)表示迭代t次的动量。

    此外,在初始优化的阶段,每次迭代中可以引入一些高斯噪声,之后像模拟退火一样逐渐减小该噪声,可以用来避免陷入局部最优解。因此,SNE在选择高斯噪声,以及学习速率,什么时候开始衰减,动量选择等等超参数上,需要跑多次优化才可以。

    2.1.3 TSNE原理

    尽管SNE提供了很好的可视化方法,但是他很难优化,而且存在”crowding problem”(拥挤问题)。后续中,Hinton等人又提出了t-SNE的方法。与SNE不同,主要如下:

    • 使用对称版的SNE,简化梯度公式
    • 低维空间下,使用t分布替代高斯分布表达两点之间的相似度

    t-SNE在低维空间下使用更重长尾分布的t分布来避免crowding问题和优化问题。在这里,首先介绍一下对称版的SNE,之后介绍crowding问题,之后再介绍t-SNE。

    优化p_{i \mid j}q_{i \mid j}的KL散度的一种替换思路是,使用联合概率分布来替换条件概率分布,即P是高维空间里各个点的联合概率分布,Q是低维空间下的,目标函数为:

    C = KL(P \mid \mid Q) = \sum_i \sum_j p_{i,j} \log \frac{p_{ij}}{q_{ij}}

    这里的p_{ii},q_{ii}为0,我们将这种SNE称之为symmetric SNE(对称SNE),因为他假设了对于任意i,p_{ij} = p_{ji}, q_{ij} = q_{ji},因此概率分布可以改写为:

    p_{ij} = \frac{\exp(- \mid \mid x_i - x_j \mid \mid ^2 / 2\sigma^2)}{\sum_{k \neq l} \exp(- \mid \mid x_k-x_l \mid \mid ^2 / 2\sigma^2)} \ \ \ \ q_{ij} = \frac{\exp(- \mid \mid y_i - y_j \mid \mid ^2)}{\sum_{k \neq l} \exp(- \mid \mid y_k-y_l \mid \mid ^2)}

    这种表达方式,使得整体简洁了很多。但是会引入异常值的问题。比如x_i是异常值,那么\mid \mid x_i - x_j \mid \mid ^2会很大,对应的所有的j,p_{ij}

    都会很小(之前是仅在x_i下很小),导致低维映射下的y_i对cost影响很小。

     

    为了解决这个问题,我们将联合概率分布定义修正为: p_{ij} = \frac{p_{i \mid j} + p_{j \mid i}}{2}, 这保证了\sum_j p_{ij} > \frac{1}{2n}, 使得每个点对于cost都会有一定的贡献。对称SNE的最大优点是梯度计算变得简单了,如下:

    \frac{\delta C}{\delta y_i} = 4 \sum_j (p_{ij} - q_{ij})(y_i - y_j)

    实验中,发现对称SNE能够产生和SNE一样好的结果,有时甚至略好一点。

    优化后对称SNE降低了计算梯度复杂性,现在处理降维产生的拥挤问题。拥挤问题就是说各个簇聚集在一起,无法区分。比如有一种情况,高维度数据在降维到10维下,可以有很好的表达,但是降维到两维后无法得到可信映射,比如降维如10维中有11个点之间两两等距离的,在二维下就无法得到可信的映射结果(最多3个点)。 进一步的说明,假设一个以数据点x_i为中心,半径为r的m维球(三维空间就是球),其体积是按r^m增长的,假设数据点是在m维球中均匀分布的,我们来看看其他数据点与x_i的距离随维度增大而产生的变化。

    show png

    从上图可以看到,随着维度的增大,大部分数据点都聚集在m维球的表面附近,与点x_i的距离分布极不均衡。如果直接将这种距离关系保留到低维,就会出现拥挤问题。

    两点间的距离公式\mid A - B \mid =\sqrt{\sum_{i=1}^{n}{(a_i-b_i)^2}},当维数增加一维要不原谅在根号内多增加了一项,比如两维\mid A - B \mid =\sqrt{(a_1-b_1)^2+(a_2-b_2)^2},三维\mid A - B \mid =\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+(a_3-b_3)^2},维数上升至后距离变大了,逆操作降维距离变小。原来的高维距离较远的点会降维后距离变小,上图显示的是距离原点情况。

    Cook et al.(2007) 提出一种slight repulsion的方式,在基线概率分布(uniform background)中引入一个较小的混合因子\rho,这样q_{ij}就永远不会小于\frac{2 \rho}{n(n-1)}(因为一共了n(n-1)个pairs),这样在高维空间中比较远的两个点之间的q_{ij}总是会比p_{ij}大一点。这种称之为UNI-SNE,效果通常比标准的SNE要好。优化UNI-SNE的方法是先让\rho为0,使用标准的SNE优化,之后用模拟退火的方法的时候,再慢慢增加\rho。直接优化UNI-SNE是不行的(即一开始\rho不为0),因为距离较远的两个点基本是一样的q_{ij}(等于基线分布), 即使p_{ij}很大,一些距离变化很难在q_{ij}中产生作用。也就是说优化中刚开始距离较远的两个聚类点,后续就无法再把他们拉近了。

    对称SNE实际上在高维度下 另外一种减轻”拥挤问题”的方法:在高维空间下,在高维空间下我们使用高斯分布将距离转换为概率分布,在低维空间下,我们使用更加偏重长尾分布的方式来将距离转换为概率分布,使得高维度下中低等的距离在映射后能够有一个较大的距离。

    show png

    我们对比一下高斯分布和t分布(如上图,code见probability/distribution.md), t分布受异常值影响更小,拟合结果更为合理,较好的捕获了数据的整体特征。

    使用了t分布之后的q变化,如下:

    q_{ij} = \frac{(1 + \mid \mid y_i -y_j \mid \mid ^2)^{-1}}{\sum_{k \neq l} (1 + \mid \mid y_i -y_j \mid \mid ^2)^{-1}}

    此外,t分布是无限多个高斯分布的叠加,计算上不是指数的,会方便很多。优化的梯度如下:

    \frac{\delta C}{\delta y_i} = 4 \sum_j(p_{ij}-q_{ij})(y_i-y_j)(1+ \mid \mid y_i-y_j \mid \mid ^2)^{-1}

    t-sne的有效性,也可以从上图中看到:横轴表示距离,纵轴表示相似度, 可以看到,对于较大相似度的点,t分布在低维空间中的距离需要稍小一点;而对于低相似度的点,t分布在低维空间中的距离需要更远。这恰好满足了我们的需求,即同一簇内的点(距离较近)聚合的更紧密,不同簇之间的点(距离较远)更加疏远。

    总结一下,t-SNE的梯度更新有两大优势:

    • 对于不相似的点,用一个较小的距离会产生较大的梯度来让这些点排斥开来。
    • 这种排斥又不会无限大(梯度中分母),避免不相似的点距离太远。

     

    2.2 算法及实例

    为了巩固上面的理论,我们在这一节给出一个具体的TSNE实例。

    2.2.1 TSNE算法

    总结一下TSNE的算法步骤,设有m条n维数据:

    1. 将原始数据按列组成m行n列矩阵X^T = {x_1, ... , x_n}
    2. 计算cost function的参数:困惑度perplexity
    3. 优化参数: 设置迭代次数T, 学习速率\eta, 动量\alpha(t)
    4. 目标结果是低维数据表示Y^T = {y_1, ... , y_m}
    5. 开始优化
      • 配合高维空间欧氏距离,在给定的perplexity下查找最佳\sigma_i使得{\rm perplexity} = H(P_i),条件概率p_{j \mid i}

      • p_{ij} = \frac{p_{j \mid i} + p_{i \mid j}}{2}

      • N(0, 10^{-4}I)随机初始化 Y

      • 从 t = 1 到 T迭代, 做如下操作:

        • 计算低维空间的q_{ij} = \frac{(1 + \mid \mid y_i -y_j \mid \mid ^2)^{-1}}{\sum_{k \neq l} (1 + \mid \mid y_i -y_j \mid \mid ^2)^{-1}}
        • 计算梯度\frac{\delta C}{\delta y_i} = 4 \sum_j(p_{ij}-q_{ij})(y_i-y_j)(1+ \mid \mid y_i-y_j \mid \mid ^2)^{-1}
        • 更新Y^{t} = Y^{t-1} + \eta \frac{dC}{dY} + \alpha(t)(Y^{t-1} - Y^{t-2})

    优化过程中可以尝试的两个trick:

    • 提前压缩(early compression):开始初始化的时候,各个点要离得近一点。这样小的距离,方便各个聚类中心的移动。可以通过引入L2正则项(距离的平方和)来实现。
    • 提前夸大(early exaggeration):在开始优化阶段,p_{ij}乘以一个大于1的数进行扩大,来避免因为q_{ij}太小导致优化太慢的问题。比如前50次迭代,p_{ij}乘以4

    优化的过程动态图如下:

    2.2.2 代码和结果

    import numpy as np
    
    from sklearn.decomposition import PCA
    from sklearn.manifold import TSNE
    from sklearn.model_selection import train_test_split
    from keras.datasets import mnist
    
    (x_train, y_train), (x_test, y_test) = mnist.load_data()
    train_data = x_train.reshape((-1, 784))
    test_data = x_test.reshape((-1, 784))
    data = np.concatenate((train_data, test_data), axis=0)
    label = np.concatenate((y_train, y_test), axis=0)
    
    _, x_run, _, y_run = train_test_split(test_data, y_test, test_size = 0.3, random_state=159)
    x_run = x_run.astype('float32') / 255.0
    
    pca = PCA(n_components=128)
    x_run = pca.fit_transform(x_run)
    components_list = [64, 2]
    for dim in components_list:
        tsne = TSNE(n_components=dim, perplexity=60, init='pca', verbose=1, random_state=0, method='exact')
        x_run = tsne.fit_transform(x_run)

     

    3. LargeVis

    3.1 算法及实例

    3.1.1 代码和结果

    import numpy as np
    
    from keras.datasets import mnist
    
    (x_train, y_train), (x_test, y_test) = mnist.load_data()
    train_data = x_train.reshape((-1, 784))
    test_data = x_test.reshape((-1, 784))
    data = np.concatenate((train_data, test_data), axis=0)
    label = np.concatenate((y_train, y_test), axis=0)
    
    x_run = data.tolist()
    
    LargeVis.loaddata(x_run)
    x_run = LargeVis.run(2, 8, -1, -1, -1, -1, -1, -1, -1, -1)

     

    4. UMAP

    4.1 算法及实例

    4.1.1 代码和结果

    import numpy as np
    
    from keras.datasets import mnist
    from sklearn.decomposition import PCA
    from sklearn.model_selection import train_test_split
    import umap
    
    (x_train, y_train), (x_test, y_test) = mnist.load_data()
    train_data = x_train.reshape((-1, 784))
    test_data = x_test.reshape((-1, 784))
    data = np.concatenate((train_data, test_data), axis=0)
    label = np.concatenate((y_train, y_test), axis=0)
    
    _, x_run, _, y_run = train_test_split(test_data, y_test, test_size = 0.4, random_state=159)
    x_run = x_run.astype('float32') / 255.0
    
    pca = PCA(n_components=64)
    x_run = pca.fit_transform(x_run)
    x_run = umap.UMAP(n_neighbors=100, min_dist=0.5).fit_transform(x_run)

     

    5. AUTO_ENCODER

    5.1 算法及实例

    5.1.1 代码和结果

    import tensorflow as tf
    import numpy as np
    from tensorflow.examples.tutorials.mnist import input_data
    
    mnist = input_data.read_data_sets("/data01/dataPath/vence/mnist/", one_hot=False)
    x_run = np.concatenate((mnist.train.images, mnist.test.images), axis=0)
    y_run = np.concatenate((mnist.train.labels, mnist.test.labels), axis=0)
    
    learning_rate = 0.01
    training_epochs = 150
    batch_size = 512
    display_step = 1
    num_samps, n_input = x_run.shape
    
    X = tf.placeholder("float", [None, n_input]) 
     
    # 用字典的方式存储各隐藏层的参数 
    n_hidden_1 = 128 # 第一编码层神经元个数 
    n_hidden_2 = 64 # 第二编码层神经元个数 
    n_hidden_3 = 10
    n_hidden_4 = 2
    
    # 权重和偏置的变化在编码层和解码层顺序是相逆的 
    # 权重参数矩阵维度是每层的 输入*输出,偏置参数维度取决于输出层的单元数 
    weights = {
        'encoder_h1': tf.Variable(tf.truncated_normal([n_input, n_hidden_1], )),
        'encoder_h2': tf.Variable(tf.truncated_normal([n_hidden_1, n_hidden_2], )),
        'encoder_h3': tf.Variable(tf.truncated_normal([n_hidden_2, n_hidden_3], )),
        'encoder_h4': tf.Variable(tf.truncated_normal([n_hidden_3, n_hidden_4], )),
        'decoder_h1': tf.Variable(tf.truncated_normal([n_hidden_4, n_hidden_3], )),
        'decoder_h2': tf.Variable(tf.truncated_normal([n_hidden_3, n_hidden_2], )),
        'decoder_h3': tf.Variable(tf.truncated_normal([n_hidden_2, n_hidden_1], )),
        'decoder_h4': tf.Variable(tf.truncated_normal([n_hidden_1, n_input], )),
    }
    biases = {
        'encoder_b1': tf.Variable(tf.random_normal([n_hidden_1])),
        'encoder_b2': tf.Variable(tf.random_normal([n_hidden_2])),
        'encoder_b3': tf.Variable(tf.random_normal([n_hidden_3])),
        'encoder_b4': tf.Variable(tf.random_normal([n_hidden_4])),
        'decoder_b1': tf.Variable(tf.random_normal([n_hidden_3])),
        'decoder_b2': tf.Variable(tf.random_normal([n_hidden_2])),
        'decoder_b3': tf.Variable(tf.random_normal([n_hidden_1])),
        'decoder_b4': tf.Variable(tf.random_normal([n_input])),
    }
    
    # 每一层结构都是 xW + b 
    # 构建编码器 
    def encoder(x):
        layer_1 = tf.nn.sigmoid(tf.add(tf.matmul(x, weights['encoder_h1']),
                                       biases['encoder_b1']))
        layer_2 = tf.nn.sigmoid(tf.add(tf.matmul(layer_1, weights['encoder_h2']),
                                       biases['encoder_b2']))
        layer_3 = tf.nn.sigmoid(tf.add(tf.matmul(layer_2, weights['encoder_h3']),
                                       biases['encoder_b3']))
        # 为了便于编码层的输出,编码层随后一层不使用激活函数
        layer_4 = tf.add(tf.matmul(layer_3, weights['encoder_h4']),
                         biases['encoder_b4'])
        return layer_4
    
    # 构建解码器 
    def decoder(x):
        layer_1 = tf.nn.sigmoid(tf.add(tf.matmul(x, weights['decoder_h1']),
                                       biases['decoder_b1']))
        layer_2 = tf.nn.sigmoid(tf.add(tf.matmul(layer_1, weights['decoder_h2']),
                                       biases['decoder_b2']))
        layer_3 = tf.nn.sigmoid(tf.add(tf.matmul(layer_2, weights['decoder_h3']),
                                       biases['decoder_b3']))
        layer_4 = tf.nn.sigmoid(tf.add(tf.matmul(layer_3, weights['decoder_h4']),
                                       biases['decoder_b4']))
        return layer_4
    
    # 构建模型 
    encoder_op = encoder(X)
    decoder_op = decoder(encoder_op)
    
    # 预测 
    y_pred = decoder_op
    y_true = X
     
    # 定义代价函数和优化器 
    cost = tf.reduce_mean(tf.pow(y_true - y_pred, 2)) #最小二乘法 
    optimizer = tf.train.AdamOptimizer(learning_rate).minimize(cost)
    
    with tf.Session() as sess:
        # tf.initialize_all_variables() no long valid from
        # 2017-03-02 if using tensorflow >= 0.12
        if int((tf.__version__).split('.')[1]) < 12 and int((tf.__version__).split('.')[0]) < 1:
            init = tf.initialize_all_variables()
        else:
            init = tf.global_variables_initializer()
        sess.run(init)
        total_batch = int(mnist.train.num_examples / batch_size)
        for epoch in range(training_epochs):
            for i in range(total_batch):
                batch_xs, batch_ys = mnist.train.next_batch(batch_size)  # max(x) = 1, min(x) = 0
                _, c = sess.run([optimizer, cost], feed_dict={X: batch_xs})
            if epoch % display_step == 0:
                print("Epoch:", '%04d' % (epoch + 1), "cost=", "{:.9f}".format(c))
        print("Optimization Finished!")
    
        encoder_result = sess.run(encoder_op, feed_dict={X: x_run})

     

     

     

    5. 参考文档

    1. PCA的数学原理 http://blog.codinglabs.org/articles/pca-tutorial.html
    2. 浅谈流形学习 http://blog.pluskid.org/?p=533
    3. t-SNE完整笔记 http://www.datakit.cn/blog/2017/02/05/t_sne_full.html
    展开全文
  • 降维

    2019-06-13 20:25:12
    可以发现,虽然是两个变量,但它们传达的信息是一致的,即物体的重量。所以我们只需选用其中的一个就能保留原始意义,把2维数据压缩到1维,这样的好处减少矩阵大小,在集合中就是减少维度,减少计算量,减少共线性。...

    一、为什么要降维?

    举个例子
    两个特征“千克”,“磅”。可以发现,虽然是两个变量,但它们传达的信息是一致的,即物体的重量。所以我们只需选用其中的一个就能保留原始意义,把2维数据压缩到1维,这样的好处减少矩阵大小,在集合中就是减少维度,减少计算量,减少共线性。

    在高维超正方体中,大多数点都分布在边界处: 在二维平面的一个正方形单元(一个 1×1 的正方形)中随机取一个点,那么随机选的点离所有边界大于 0.001(靠近中间位置)的概率为 0.4%( 1 - 0.998^2 )。在一个 1,0000 维的单位超正方体(一个 1×1×…×1 的立方体,有 10,000 个 1),这种可能性超过了 99.999999%。

    高维数据集有很大风险分布的非常稀疏:在一个平方单位中随机选取两个点,那么这两个点之间的距离平均约为0.52,三维空间中这个距离是0.66,在一个 1,000,000 维超立方体中随机抽取两点,他们的距离大概是408.25。大多数训练实例可能彼此远离,训练集的维度越高,过拟合的风险就越大。

    在这里插入图片描述

    二、降维技术

    降低数据维度的方法主要有两种

    • 仅保留原始数据中最相关的变量(特征选择)
    • 寻找一组较小的新变量,其中每个变量都是输入变量的组合,包含与输入变量基本相同的信息(降维)。

    具体方法:
    1、缺失值比率(Missing Value Ratio)
    核心思想:空值率太低,果断舍弃(特征选择)
    code:
    train=pd.read_csv(“Train_UWu5bXk.csv”)
    #用.isnull().sum()检查每个变量中缺失值的占比
    # 保存变量中的缺失值
    a = train.isnull().sum()/len(train)*100

    2、低方差滤波(Low Variance Filter)
    核心思想:如果我们某一列的数值基本一致,也就是他的方差非常非常小,那么这个值没有价值,低方差变量携带的信息量很少,这是可以考虑删除
    放在示例中,我们先估算缺失值:
    train[‘Item_Weight’].fillna(train[‘Item_Weight’].median, inplace=True)

    train[‘Outlet_Size’].fillna(train[‘Outlet_Size’].mode()[0], inplace=True)
    检查缺失值是否已经被填充:
    train.isnull().sum()/len(train)*100

    再计算所有数值变量的方差:
    train.var()
    再设定某个阈值,小于该阈值的全部删除

    3、高相关滤波(High correlation filter)
    核心思想:如果两个变量是高度相关的,它意味着他们具有相似的趋势,我们可以计算独立数值变量之间的相关性。如果相关性超过某个阈值,就删除其中一个变量
    df=train.drop(‘Item_Outlet_Sales’, 1)
    df.corr()
    如上表所示,示例数据集中不存在高相关变量,但通常情况下,如果一对变量之间的相关性大于0.5-0.6,那就应该考虑是否要删除一列了。

    4、随机森林 random forest
    随机森林是一种广泛使用的特征选择算法,他会自动计算各个特征之间的重要性,无需单独编码。(注意:在开始降维前,我们先把数据转换成数字格式,因为随机森林只接受数字)

    5、反向特征消除(backward feature elimination)

    • 先获取数据集n个变量,然后用他们训练一个模型
    • 计算模型性能
    • 在删除每个变量(n次)后计算模型性能,即我们每次都去掉一个变量,用剩余的n-1个变量训练模型。
    • 确定对模型性能影响最小的变量,把他删除
    • 重复此过程,知道不在能删除变量

    lreg = LinearRegression()
    rfe = RFE(lreg, 10)
    rfe = rfe.fit_transform(df, train.Item_Outlet_Sales)

    6、向前特征选择(Forward Feature selection)
    前向特征选择其实就是反向特征消除的相反过程,即找到能改善模型性能的最佳特征,而不是删除弱影响特征。

    • 选择一个特征,用每个特征训练模型n次,得到n个模型。

    • 选择模型性能最佳的变量作为初始变量。

    • 每次添加一个变量继续训练,重复上一过程,最后保留性能提升最大的变量。

    • 一直添加,一直筛选,直到模型性能不再有明显提高。

    7、因子分析(Factor Analysis)
    因子分析是一种常见的统计方法,它能从多个变量中提取共性因子,并得到最优解。假设我们有两个变量:收入和教育。它们可能是高度相关的,因为总体来看,学历高的人一般收入也更高,反之亦然。所以它们可能存在一个潜在的共性因子,比如“能力”。

    8、主成分分析 PCA
    核心思想: 找到接近数据集分布的超平面,然后将所有的数据都投影到这个超平面上。
    如果说因子分析是假设存在一系列潜在因子,能反映变量携带的信息,那PCA就是通过正交变换将原始的n维数据集变到一个新的被称作主成分的数据集中,即从现有的大量变量中提取一组新的变量。

    • 主成分是原始变量的线性组合
    • 第一个主成分具有最大的方差值(选择保持最大方差的轴,因为它比其他投影损失更少的信息。)
    • 第二主成分试图解释数据集中剩余的方差,并且与第一主成分不相关(正交)
    • 第三主成分试图解释前两个主成分等没有解释的方差

    9、独立分量分析(ICA)

    总结:
    缺失值比率:如果数据集的缺失值太多,我们可以用这种方法减少变量数。
    低方差滤波:这个方法可以从数据集中识别和删除常量变量,方差小的变量对目标变量影响不大,所以可以放心删去。
    高相关滤波:具有高相关性的一对变量会增加数据集中的多重共线性,所以用这种方法删去其中一个是有必要的。
    随机森林:这是最常用的降维方法之一,它会明确算出数据集中每个特征的重要性。
    前向特征选择和反向特征消除:这两种方法耗时较久,计算成本也都很高,所以只适用于输入变量较少的数据集。
    因子分析:这种方法适合数据集中存在高度相关的变量集的情况。
    PCA:这是处理线性数据最广泛使用的技术之一。
    ICA:我们可以用ICA将数据转换为独立的分量,使用更少的分量来描述数据。
    ISOMAP:适合非线性数据处理。
    t-SNE:也适合非线性数据处理,相较上一种方法,这种方法的可视化更直接。
    UMAP:适用于高维数据,与t-SNE相比,这种方法速度更快。

    原文地址: www.analyticsvidhya.com/blog/2018/08/dimensionality-reduction-techniques-python/

    展开全文
  • 直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和...

    ==========

    欢迎关注文章首发公众号:早起python

    本文为早起的统计工具箱第二期

    ==========

    前言

    为什么要进行数据降维?直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和预测的时间与效率。

    降维方法分为线性和非线性降维,非线性降维又分为基于核函数和基于特征值的方法(流形学习),代表算法有线性降维方法:PCA ICA LDA LFA

    基于核的非线性降维方法KPCA KFDA

    流形学习:ISOMAP LLE LE LPP

    本文主要对线性降维方法中的PCA、ICA、LDA的Python实现进行讲解。

    请注意本文将不对各种数据降维方法的原理与理论推导过程做过多的讲解,旨在用尽可能少的语言说清楚以及如何用Python实现,先实现再理解,并在读完代码之后自行查阅相关文献理解其不同的思想。但读者应具有一定的统计学、代数学、机器学习的基础。

    主成分分析PCA

    主成分分析(Principal Component Analysis),是一种常用的数据降维方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量,转换后的这组变量就叫主成分。关于主成分分析的思想与理论推导过程在互联网上很容易找到完美的证明,用人话说来就是找到一个轴,将你的数据映射到这个轴上之后所计算的方差最大,再换句人话说就是从原始数据的一堆变量中提取出一部分变量,而这部分变量能完美解释原始数据中包含的信息(或保留原始的数据特性)

    注意:进行主成分分析前需对数据进行归一化处理

    PCA流程:对数据行归一化处理

    计算归一化后的数据集的协方差矩阵与其特征值、特征向量

    对特征值从大到小排序并保留最大的个特征向量

    将数据转换到个特征向量构建的新空间中

    优点:无参数限制

    提取了主要信息并且结果容易理解

    缺点:方差小的主成分可能含有对样本差异的重要信息

    在某些情况下,PCA方法得出的主元可能并不是最优的

    相关Python代码

    sklearn.decomposition.PCA

    Python实现示例(已注释)

    #来看个官网最简单的例子

    >>> import numpy as np

    >>> from sklearn.decomposition import PCA

    #创建数据 矩阵形式

    >>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])

    #设定两个主成分

    >>> pca = PCA(n_components=2)

    #用X训练

    >>> pca.fit(X)

    PCA(n_components=2)

    #查看每个主成分解释程度

    >>> print(pca.explained_variance_ratio_)

    [0.9924... 0.0075...]

    >>> print(pca.singular_values_)

    [6.30061... 0.54980...]

    #降维

    >>> pca = PCA(n_components=1, svd_solver='arpack')

    >>> pca.fit(X)

    PCA(n_components=1, svd_solver='arpack')

    >>> print(pca.explained_variance_ratio_)

    [0.99244...]

    >>> print(pca.singular_values_)

    [6.30061...]

    线性判别分析LDA

    线性判别分析(Linear Discriminant Analysis)是一种有监督的(supervised)线性降维算法。与PCA保持数据信息不同,LDA的核心思想:往线性判别超平面的法向量上投影,使得区分度最大(高内聚,低耦合)。LDA是为了使得降维后的数据点尽可能地容易被区分!

    与PCA比较PCA为无监督降维,LDA为有监督降维

    LDA降维最多降到类别数K-1的维数,PCA没有这个限制。

    PCA希望投影后的数据方差尽可能的大(最大可分性),而LDA则希望投影后相同类别的组内方差小,而组间方差大。

    相关Python代码

    sklearn.discriminant_analysis.LinearDiscriminantAnalysis

    Python实现示例(已注释)

    import numpy as np

    import matplotlib.pyplot as plt

    from mpl_toolkits.mplot3d import Axes3D

    %matplotlib inline

    from sklearn.datasets.samples_generator import make_classification

    #生成数据

    X, y = make_classification(n_samples=1000, n_features=3, n_redundant=0, n_classes=3, n_informative=2,

    n_clusters_per_class=1,class_sep =0.5, random_state =10)

    #LDA降维

    from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

    lda = LinearDiscriminantAnalysis(n_components=2)

    lda.fit(X,y)

    X_new = lda.transform(X)

    plt.scatter(X_new[:, 0], X_new[:, 1],marker='o',c=y)

    plt.show()

    独立成分分析ICA

    独立成分分析(Independent component analysis)是一种利用统计原理进行计算的方法,它是一个线性变换,这个变换把数据或信号分离成统计独立的非高斯的信号源的线性组合。之前介绍的PCA、LDA都是以观测数据点呈高斯分布模型为基本假设前提的,而ICA将适用于非高斯分析数据集,是PCA的一种有效扩展。

    与PCA比较ICA寻找的是最能使数据的相互独立的方向,而PCA仅要求方向是不相关的

    PCA认为主元之间彼此正交,样本呈高斯分布;ICA则不要求样本呈高斯分布

    相关Python代码

    sklearn.decomposition.FastICA

    Python实现示例(已注释)

    import numpy as np

    import matplotlib.pyplot as plt

    from scipy import signal

    from sklearn.decomposition import FastICA, PCA

    # 生成观测模拟数据

    np.random.seed(0)

    n_samples = 2000

    time = np.linspace(0, 8, n_samples)

    s1 = np.sin(2 * time) # 信号源 1 : 正弦信号

    s2 = np.sign(np.sin(3 * time)) # 信号源 2 : 方形信号

    s3 = signal.sawtooth(2 * np.pi * time) # 信号源 3: 锯齿波信号

    S = np.c_[s1, s2, s3]

    S += 0.2 * np.random.normal(size=S.shape) # 增加噪音数据

    S /= S.std(axis=0) # 标准化

    # 混合数据

    A = np.array([[1, 1, 1], [0.5, 2, 1.0], [1.5, 1.0, 2.0]]) # 混合矩阵

    X = np.dot(S, A.T) # 生成观测信号源

    # ICA模型

    ica = FastICA(n_components=3)

    S_ = ica.fit_transform(X) # 重构信号

    A_ = ica.mixing_ # 获得估计混合后的矩阵

    # PCA模型

    pca = PCA(n_components=3)

    H = pca.fit_transform(X) # 基于PCA的成分正交重构信号源

    # 图形展示

    plt.figure()

    models = [X, S, S_, H]

    names = ['Observations (mixed signal)',

    'True Sources',

    'ICA recovered signals',

    'PCA recovered signals']

    colors = ['red', 'steelblue', 'orange']

    for ii, (model, name) in enumerate(zip(models, names), 1):

    plt.subplot(4, 1, ii)

    plt.title(name)

    for sig, color in zip(model.T, colors):

    plt.plot(sig, color=color)

    plt.subplots_adjust(0.09, 0.04, 0.94, 0.94, 0.26, 0.46)

    plt.show()

    以上就是早起的统计工具箱第二期的内容,当然想要完全学会还需要自行查阅更多文献,而更多的数据降维方法、还有上一期未介绍完的python统计检验我们之后再聊。

    我的公众号:早起python

    展开全文
  • 直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和...

    ==========

    欢迎关注文章首发公众号:早起python

    本文为早起的统计工具箱第二期

    ==========

    前言

    为什么要进行数据降维?直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和预测的时间与效率。

    降维方法分为线性和非线性降维,非线性降维又分为基于核函数和基于特征值的方法(流形学习),代表算法有线性降维方法:PCA ICA LDA LFA

    基于核的非线性降维方法KPCA KFDA

    流形学习:ISOMAP LLE LE LPP

    本文主要对线性降维方法中的PCA、ICA、LDA的Python实现进行讲解。

    请注意本文将不对各种数据降维方法的原理与理论推导过程做过多的讲解,旨在用尽可能少的语言说清楚以及如何用Python实现,先实现再理解,并在读完代码之后自行查阅相关文献理解其不同的思想。但读者应具有一定的统计学、代数学、机器学习的基础。

    主成分分析PCA

    主成分分析(Principal Component Analysis),是一种常用的数据降维方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量,转换后的这组变量就叫主成分。关于主成分分析的思想与理论推导过程在互联网上很容易找到完美的证明,用人话说来就是找到一个轴,将你的数据映射到这个轴上之后所计算的方差最大,再换句人话说就是从原始数据的一堆变量中提取出一部分变量,而这部分变量能完美解释原始数据中包含的信息(或保留原始的数据特性)

    注意:进行主成分分析前需对数据进行归一化处理

    PCA流程:对数据行归一化处理

    计算归一化后的数据集的协方差矩阵与其特征值、特征向量

    对特征值从大到小排序并保留最大的个特征向量

    将数据转换到个特征向量构建的新空间中

    优点:无参数限制

    提取了主要信息并且结果容易理解

    缺点:方差小的主成分可能含有对样本差异的重要信息

    在某些情况下,PCA方法得出的主元可能并不是最优的

    相关Python代码

    sklearn.decomposition.PCA

    Python实现示例(已注释)

    #来看个官网最简单的例子

    >>> import numpy as np

    >>> from sklearn.decomposition import PCA

    #创建数据 矩阵形式

    >>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])

    #设定两个主成分

    >>> pca = PCA(n_components=2)

    #用X训练

    >>> pca.fit(X)

    PCA(n_components=2)

    #查看每个主成分解释程度

    >>> print(pca.explained_variance_ratio_)

    [0.9924... 0.0075...]

    >>> print(pca.singular_values_)

    [6.30061... 0.54980...]

    #降维

    >>> pca = PCA(n_components=1, svd_solver='arpack')

    >>> pca.fit(X)

    PCA(n_components=1, svd_solver='arpack')

    >>> print(pca.explained_variance_ratio_)

    [0.99244...]

    >>> print(pca.singular_values_)

    [6.30061...]

    线性判别分析LDA

    线性判别分析(Linear Discriminant Analysis)是一种有监督的(supervised)线性降维算法。与PCA保持数据信息不同,LDA的核心思想:往线性判别超平面的法向量上投影,使得区分度最大(高内聚,低耦合)。LDA是为了使得降维后的数据点尽可能地容易被区分!

    与PCA比较PCA为无监督降维,LDA为有监督降维

    LDA降维最多降到类别数K-1的维数,PCA没有这个限制。

    PCA希望投影后的数据方差尽可能的大(最大可分性),而LDA则希望投影后相同类别的组内方差小,而组间方差大。

    相关Python代码

    sklearn.discriminant_analysis.LinearDiscriminantAnalysis

    Python实现示例(已注释)

    import numpy as np

    import matplotlib.pyplot as plt

    from mpl_toolkits.mplot3d import Axes3D

    %matplotlib inline

    from sklearn.datasets.samples_generator import make_classification

    #生成数据

    X, y = make_classification(n_samples=1000, n_features=3, n_redundant=0, n_classes=3, n_informative=2,

    n_clusters_per_class=1,class_sep =0.5, random_state =10)

    #LDA降维

    from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

    lda = LinearDiscriminantAnalysis(n_components=2)

    lda.fit(X,y)

    X_new = lda.transform(X)

    plt.scatter(X_new[:, 0], X_new[:, 1],marker='o',c=y)

    plt.show()

    独立成分分析ICA

    独立成分分析(Independent component analysis)是一种利用统计原理进行计算的方法,它是一个线性变换,这个变换把数据或信号分离成统计独立的非高斯的信号源的线性组合。之前介绍的PCA、LDA都是以观测数据点呈高斯分布模型为基本假设前提的,而ICA将适用于非高斯分析数据集,是PCA的一种有效扩展。

    与PCA比较ICA寻找的是最能使数据的相互独立的方向,而PCA仅要求方向是不相关的

    PCA认为主元之间彼此正交,样本呈高斯分布;ICA则不要求样本呈高斯分布

    相关Python代码

    sklearn.decomposition.FastICA

    Python实现示例(已注释)

    import numpy as np

    import matplotlib.pyplot as plt

    from scipy import signal

    from sklearn.decomposition import FastICA, PCA

    # 生成观测模拟数据

    np.random.seed(0)

    n_samples = 2000

    time = np.linspace(0, 8, n_samples)

    s1 = np.sin(2 * time) # 信号源 1 : 正弦信号

    s2 = np.sign(np.sin(3 * time)) # 信号源 2 : 方形信号

    s3 = signal.sawtooth(2 * np.pi * time) # 信号源 3: 锯齿波信号

    S = np.c_[s1, s2, s3]

    S += 0.2 * np.random.normal(size=S.shape) # 增加噪音数据

    S /= S.std(axis=0) # 标准化

    # 混合数据

    A = np.array([[1, 1, 1], [0.5, 2, 1.0], [1.5, 1.0, 2.0]]) # 混合矩阵

    X = np.dot(S, A.T) # 生成观测信号源

    # ICA模型

    ica = FastICA(n_components=3)

    S_ = ica.fit_transform(X) # 重构信号

    A_ = ica.mixing_ # 获得估计混合后的矩阵

    # PCA模型

    pca = PCA(n_components=3)

    H = pca.fit_transform(X) # 基于PCA的成分正交重构信号源

    # 图形展示

    plt.figure()

    models = [X, S, S_, H]

    names = ['Observations (mixed signal)',

    'True Sources',

    'ICA recovered signals',

    'PCA recovered signals']

    colors = ['red', 'steelblue', 'orange']

    for ii, (model, name) in enumerate(zip(models, names), 1):

    plt.subplot(4, 1, ii)

    plt.title(name)

    for sig, color in zip(model.T, colors):

    plt.plot(sig, color=color)

    plt.subplots_adjust(0.09, 0.04, 0.94, 0.94, 0.26, 0.46)

    plt.show()

    以上就是早起的统计工具箱第二期的内容,当然想要完全学会还需要自行查阅更多文献,而更多的数据降维方法、还有上一期未介绍完的python统计检验我们之后再聊。

    我的公众号:早起python

    展开全文
  • 通俗理解PCA降维作用

    万次阅读 多人点赞 2017-08-13 16:37:05
    本文主要介绍一种降维方法,PCA(Principal Component Analysis,主成分分析)。...2. 降维可以在压缩数据的同时让信息损失最小化; 3. 理解几百个维度的数据结构很困难,两三个维度的数据通过可视化更容易理解。。
  • PCA降维

    2019-07-22 16:07:06
    降维的时候,我们希望保留主要特征,所以我们想删除不是那么重要的信息【或者说某一个维度的信息】。 这个维度的信息 可以通过其他维度的信息进行生成,所以这个维度自然也就没有保留的含义了。 怎么降维? 将...
  • 直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和...
  • 降维相关

    千次阅读 2017-12-04 22:54:09
    降维相关降维相关 什么是降维 PCA LDA LLE LE 什么是降维一般来说,在ml里面,需要feature。而对于feature,我们又通常使用向量来表示。...直观地说,就是要既能降低维度,又能使得损失的信息尽量少。举个例子,如果
  • 降维算法

    2020-04-07 23:25:10
    我们希望能够找出一种方法来帮助我们衡量特征上所带的信息,让我们在姜维的过程中,即能够减少特征的数量,又能够保留大部分的信息——将那些带有重复信息的特征合并,并删除那些带有无效信息的特征等—...
  • 数据降维

    2018-08-25 21:58:50
    特征的重要性取决于特征变量对数据信息表示的贡献程度,以及决定使用哪种技术。决定使用哪种技术取决于试错和偏好。通常从线性技术开始,当结果表明拟合不足时,就转向非线性技术。 [b]数据集降维的好处可以是:[/...
  • 直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和...
  • 直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和...
  • FDA降维

    千次阅读 2016-03-24 10:53:19
    LPP通过保持数据的局部结构获得很好的降维效果,但他只能用于无监督的情况,不能将样本的标签信息考虑在内。 由于类间散布矩阵不是满秩的,所以FDA只能将数据映射到维数小于类个数的低维空间,这是FDA的局限。
  • 降维方法

    千次阅读 2019-10-04 21:02:47
    在特征选择中往往会选择一些多余的特征,它增加了维数,从而增加了聚类分析的复杂度,但对模式分类却没有提供多少有用的信息。在这种情况下,需要去掉相关程度过高的特征(进行降维处理)。 降维方法 设有N个样本...
  • 基于信息熵的高维稀疏大数据降维算法研究
  • 4 降维

    2018-12-20 09:11:18
    由于它是无监督的, 因此PCA假设方差越大, 信息量越多, 用主成分来表示原始数据可以去除冗余的维度, 达到降维。 02 线性判别分析–LDA LDA选择的是投影后类内方差小、 类间方差大的方 向。 其用到了类别标签...
  • 有利于提取有效信息、摈弃无用信息 降维的主要方法:线性映射和非线性映射 线性映射方法里比较常见的就是: 主成分分析 PCA(Principal Component Analysis) 线性判别分析 LDA(Linear Discriminant Analysis...
  • 直观地好处是维度降低了,便于计算和可视化,其深层次的意义在于有效信息的提取综合及无用信息的摈弃,并且数据降维保留了原始数据的信息,我们就可以用降维的数据进行机器学习模型的训练和预测,但将有效提高训练和...
  • sklearn降维

    2019-05-21 08:26:51
    1.sklearn降维API sklearn. decomposition 2.PCA 本质:PCA是一种分析、简化数据集的技术 目的:是数据维数压缩,尽可能降低原数据的维数(复杂度),损失少量信息。 作用:可以削减回归分析或者聚类分析中特征...
  • 为了提高降维的效果, 根据近邻点的选取对diffusion maps的降维效果影响, 利用数据近邻点分布的不同, 挖掘该数据点局部的密度信息, 能够更好地保持数据的流形结构。利用样本点聚类后的类别信息构造密度信息指数, 提出...
  • AdaBoost特征降维

    2015-08-16 15:49:37
    特征降维是模式识别中重要的一步,从图像中提取的原始特征往往维度较高,...基于AdaBoost的特征降维是具有良好的特征选择能力,其对每一维特征训练若分离器,根据分类效果调整权重,并最终选择具有分类信息的特征组合。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,980
精华内容 792
关键字:

信息降维