精华内容
下载资源
问答
  • 信息降维
    2020-09-30 02:53:27

    主成分分析之基本概念—降维技术

    假设一下场景:

    1. 一百多个自变量做聚类分析
    2. 两个变量做线性回归存在多重共线性,去掉其中一个又损失了回归的精度

    这种情况下,最优的解法就是将多个变量融合为一个新的变量,使得变量的个数大大降低(降维),并且能够将有相关关系的几个指标合并为一个,消除变量之间的多重共线性, 这种 设法将原先众多的具有一定相关性的指标,重新组合为一组新的互相独立的综合指标,并代替原先的指标的技术,称为主成分技术。

    例子:

    	y1	x1	x2	x3
    	3	6	0	100
    	5	9	0	100
    	7	15	0	100
    	4	9	0	100
    	8	15	0	100
    	9	7	0	100
    	10	19	0	100
    	2	3	0	100
    	6	13	0	100
    
    1、回归就是通过自变量的变化来解释因变量的变化!!!
    
    2、Y和x做回归时,x2和x3本身不发生任何变化(本身无方差),无法用来及时y的回
    
    归(因为用一个不变的量来解释变的量是不可能的),主成分分析就是 用有方差且
    
    方差够大的变量来做组合。
    
    3、	主成分分析-降维:以尽可能小的牺牲精度为代价来去因子,用更少的变量来解释事实;
    
    4、	主成分分析的数据概念---方差最大
    
    a)	自变量的方差足够大,才有可能解释因变量的方差足够大;
    

    案例: 身高x1,体重x2,胸围x3,坐高x4 分析

    ####用数据框形式输入数据:
    X1=c(148,139,160,……148)
    X2=c(41,34,45,….,66)
    X3=c(72,71,77,,70)
    X4=c(78,76,86,..)
    
     #做主成分分析,显示分析效果
    Student.pr<-princomp(student,cor=TRUE)
    Summary(student.pr,loadings=TRUE)
    
    ## 做预测
    Predict(student.pr)
    
    ##做碎石图
    Screeplot(student.pr,type=”lines”)
    
    更多相关内容
  • 人工智能-基于互信息降维神经网络模型的个人信用评估.pdf
  • 带有互信息保留映射的文本降维
  • 高维信息降维可视化常用算法比较

    千次阅读 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
    展开全文
  • 与主成分分析(PCA)算法相比,实验结果表明用该算法对数据集降维后,得到的属性约简集合的属性个数较多,K-means算法根据属性集合进行聚类的精度较高。实验结果证明该算法能有效地应用于信息表的属性约简方面。
  • 数据降维可以降低模型的计算量并减少模型运行时间、降低噪音对于模型结果的影响、便于通过可视化方式展示归约后的维度信息并减少数据存储空间。因此,大多数情况下,当我们面临高维数据时,都需要对数据做降维处理。...

    目录

    数据降维的应用场景

    基于特征选择的降维

    基于维度转换的降维

    参考资料:

    1.《Python数据分析与数据化运营》宋天龙

    2.主成分分析(PCA)原理详解 - 知乎

    3.机器学习中SVD总结

    数据降维的应用场景

    数据降维可以降低模型的计算量并减少模型运行时间、降低噪音对于模型结果的影响、便于通过可视化方式展示归约后的维度信息并减少数据存储空间。因此,大多数情况下,当我们面临高维数据时,都需要对数据做降维处理。是否进行降维主要考虑以下方面:

    • 维度数量。高维的数据大部分情况下是需要降维的,同时需要考虑维度本身的重要性、共线性以及其他排除关系。
    • 建模输出是否必须保留原始维度。某些场景下,我们需要完整保留参与建模的原始维度并在最终建模输出时能够得以分析、解释和应用,这种情况下不能选择基于维度转换的降维,只能选择基于特征选择的降维。
    • 是否要保留完整数据特征。数据降维的基本出发点是在最大化保留原始数据特征的前提下,降低参与建模的维度。在降维过程中,无论未被表示出来的特征是噪音还是正常分布,这部分信息都无法参与建模过程。如果某些场景下需要所有数据集的完整特征,那么通常不选择降维。
    • 对模型的计算效率与建模时效性要求。当面临高维数据建模时,数据模型消耗的资源将呈几何倍数增长,这种增长带来的结果便是运算效率慢、耗时长。如果对建模时间和时效性有要求,那么降维几乎是必要步骤。

    数据降维只是处理高维数据的思路之一,除此之外还有其他高维数据建模的方法。以高维数据聚类为例,除了降维方法外,其他方法还包括:基于超图的聚类、基于子空间的聚类、联合聚类等。

    基于特征选择的降维

    基于特征选择的降维是根据一定规则和经验,直接选取原有维度的一部分参与到后续的计算和建模过程。整个过程不产生新的维度。

    这种降维方法的好处是,既能满足后续数据处理和建模需求,又能保留维度原本的业务含义,以便于业务理解和应用。

    基于特征选择的降维方法有4种:

    • 经验法:通过业务专家、数据专家的以往经验、实际数据情况、业务理解程度等综合考虑选择。从众多维度特征中选择对结果影响较大的特征,或从对后期数据处理和建模的影响来选择维度。
    • 测算法:通过不断测试多种维度选择参与计算,通过结果来反复验证和调整并最终找到最佳特征方案。
    • 基于统计分析的方法:通过计算不同维度间的相关性分析,找到具有较高线性相关性的维度,然后筛选;或者通过计算不同维度间的互信息量,找到具有较高互信息量的维度,然后筛选。
    • 机器学习算法:通过机器学习算法得到不同特征的重要程度,然后再根据权重来选择较大的特征。

    基于维度转换的降维

    基于维度转换的降维是按照一定的数学变换方法,把给定的一组相关变量通过数学模型将高维空间的数据点映射到低维度空间中,然后利用映射后变量的特征来表示原有变量的总体特征。整个过程会产生新的维度。

    维度变换是非常重要的降维方法,这种降维方法分为线性降维和非线性降维两种,其中常用的代表算法包括独立成分分析(ICA)、主成分分析(PCA)、因子分析(Factor Analysis,FA)、线性判别分析(LDA)、局部线性嵌入(LLE)、核主成分分析(Kernel PCA)等。

    Q:在机器学习中,经常会把数据分为训练集和测试集,也有可能包括应用集,多份数据需要单独降维还是整体降维?

    A:对于线性方法(例如PCA)而言,它旨在寻找一个高维空间到低维空间的映射矩阵,当映射矩阵找到后便可直接将其应用到其他数据集进行降维,因此这种降维方式下可以单独降维;而非线性方法(例如LLE)则需要在保持某种局部结构的条件下实现数据的整体降维,因此这种降维方式下需要整体降维。

    以下介绍PCA主要适用的场景:

    • 非监督式的降维方法,适用于不带有标签的数据集。而对于带有标签的数据集则可以采用LDA。
    • 根据方差自主控制特征数量。最大的主成分的数量会小于等于原始特征的数量。
    • 更少的正则化处理。选择较多的主成分将导致较少的平滑,因为我们将能够保留更多的数据特征,从而减少正则化。
    • 数据量较大的数据集。PCA对大型数据集的处理效率较高。
    • 数据分布是位于相同平面上,数据中存在线性结构。

    代码如下:

    # 导入库
    import numpy as np
    from sklearn.tree import DecisionTreeClassifier
    from sklearn.decomposition import PCA
    
    # 读取数据文件
    data = np.loadtxt('data1.txt')  
    x = data[:, :-1]  
    y = data[:, -1]  
    print(x[0], y[0])  
    
    # 使用sklearn的DecisionTreeClassifier判断变量重要性
    # 变量重要性的总得分为1,值越大重要性越高。一般情况下,如果选择的变量重要性总得分接近80%,基本上已经解释大部分的特征变化了。
    model_tree = DecisionTreeClassifier(random_state=0)  # 建立分类决策树模型对象
    model_tree.fit(x, y)                                 # 将数据集的维度和目标变量输入模型
    print(model_tree.feature_importances_)               # 获得所有变量的重要性得分
    
    # 使用sklearn的PCA进行维度转换
    # 各主成分方差越大重要性越高。一般情况下,如果选择的主成分方差占比接近80%,基本上已经解释大部分的特征变化了。
    model_pca = PCA()                   # 建立PCA模型对象
    model_pca.fit(x)                    # 将数据集输入模型,仅输入x进行PCA训练
    model_pca.transform(x)              # 对数据集进行转换映射,可作用于其他数据集上
    components = model_pca.components_  # 获得转换后的所有主成分
    components_var = model_pca.explained_variance_              # 获得各主成分的方差
    components_var_ratio = model_pca.explained_variance_ratio_  # 获得各主成分的方差占比
    print(components[:2])  
    print(components_var[:2])  
    print(components_var_ratio) 
    展开全文
  • pca针对二阶统计量的分析,主要处理服从高斯分布的信号信息
  • 基于信息降维的混合属性数据流聚类算法.pdf
  • 为了提高降维的效果, 根据近邻点的选取对diffusion maps的降维效果影响, 利用数据近邻点分布的不同, 挖掘该数据点局部的密度信息, 能够更好地保持数据的流形结构。利用样本点聚类后的类别信息构造密度信息指数, 提出...
  • 深度学习降维过程中的信息损失度量研究.pdf
  • 数据降维:主成分分析法

    千次阅读 2021-01-19 00:39:16
    什么叫做主成分分析法,我们先看一张图椭圆的图,如果让你找一条线,使得椭圆上所有点在该线上映射的点最分散,保留下来的信息最多,你会怎么选择这条线?若是下图,会选择水平线,这是用一维的方式去尽可能多的表示...

    前言

    什么叫做主成分分析法,我们先看一张图椭圆的图,如果让你找一条线,使得椭圆上所有点在该线上映射的点最分散,保留下来的信息最多,你会怎么选择这条线?若是下图,会选择水平线,这是用一维的方式去尽可能多的表示二维的数据,那么多维的数据呢,是否可以用较低维的数据尽可能表示。

    m17

    如何用二维的平面去尽可能表示一个椭球面呢?

    m17

    思想

    主成分分析法是一种统计方式,简化数据的方式,是一种线性变换,把数据变换到新的坐标系中,使得任意投影的第一大方差映射到第一主成分上,第二大方差映射到第二主成分上。如果舍弃高维的主成分,一般可以达到保留对方差贡献最大的特征,在一些方面上,可以保留数据的主要特征,当然,为了数据更好看,我们会把坐标轴的中心移到数据的中心,这可以让数据处理起来更方便。

    高斯分布

    在数学上

    在数学上,我们用 L 2 L^2 L2 范数的平方( L 2 L^2 L2范数的平方与其本身在相同位置取得最小值,单调递增,性质更好)来计算,x 为输入, c ∗ c^* c 为最优编码:

    c ∗ = ( L 2 ) 2 = a r g m i n c ∣ ∣ x − g ( c ) ∣ ∣ 2 2 = ( x − g ( c ) ) T ( x − g ( c ) ) = x T x − 2 x T g ( c ) + g ( c ) T g ( c ) = a r g m i n c − 2 x T D c + c T I l c ( 其 中 c = f ( x ) , g ( c ) = D c ) ∴ ∇ c ( − 2 x T D c + c T c ) = 0 c = f ( x ) = D T x c^*=(L^2)^2=argmin_c||x-g(c)||_2^2 \\\\ =(x-g(c))^T(x-g(c)) \\\\ =x^Tx-2x^Tg(c)+g(c)^Tg(c) \\\\ =argmin_c-2x^TDc+c^TI_lc \\\\ (其中c=f(x),g(c)=Dc) \\\\ \therefore\nabla_c(-2x^TDc+c^Tc)=0 \\\\ c=f(x)=D^Tx c=(L2)2=argmincxg(c)22=(xg(c))T(xg(c))=xTx2xTg(c)+g(c)Tg(c)=argminc2xTDc+cTIlcc=f(x)g(c)=Dcc(2xTDc+cTc)=0c=f(x)=DTx

    由上可知,若要得到c只需要一个矩阵乘法。定义重构操作:

    r ( x ) = g ( f ( x ) ) = D D T x D ∗ = a r g m i n D ∑ i , j ( x j ( i ) − r ( x ( i ) ) j ) 2 其 中 D T D = I l r(x)=g(f(x))=DD^Tx \\\\ D^*=argmin_D\sqrt{\sum_{i,j}(x_j^{(i)}-r(x^{(i)})_j)^2} \\\\ 其中D^TD=I_l r(x)=g(f(x))=DDTxD=argminDi,j(xj(i)r(x(i))j)2 DTD=Il

    经过复杂的 推导,用数学归纳法可以证明,矩阵 D 可以由前 X T X X^TX XTX 的前 l l l 个最大的特征值对应的特征向量组成。

    总结

    主成分分析法主要用于数据降维,目标为尽量减少原数据的损失的情况下,尽可能减少数据量。

    展开全文
  • 基于信息熵的高维稀疏大数据降维算法研究
  • 数据降维可以降低模型的计算量并减少模型运行时间、降低噪音变量信息对于模型结果的影响、便于通过可视化方式展示归约后的维度信息并减少数据存储空间。因此,大多数情况下,当我们面临高维数据时,都需要对数据做...
  • 2. 降维可以在压缩数据的同时让信息损失最小化; 3. 理解几百个维度的数据结构很困难,两三个维度的数据通过可视化更容易理解。 PCA简介 在理解特征提取与处理时,涉及高维特征向量的问题往往容易陷入维度灾难。随着...
  • 关节点时空信息融合降维的人体动作识别方法.docx
  • #资源达人分享计划#
  • 针对属性权重信息完全未知的情况,采用实际数据信息构造犹豫模糊指数熵,并利用信息熵最小化原则计算得到属性权重.最后利用指数熵加权的降维犹豫模糊兰氏距离测度,结合实际的医疗诊断数据进行实例分析.结果表明,所提出...
  • 针对文本分类中信息增益降维方法的不足,提出了一种基于相对文档频的平衡信息增益(RDFBIG)降维方法。实验结果表明,RDFBIG能有效消除不同类别之间语料规模对分类精度的影响,取得了较好的分类效果。
  • 基于偏最小二乘法的信息降维及聚类研究.pdf
  • 文章目录前言一、用到的降维算法1.PCA2.T-SNE3.SVD奇异值分解![在这里插入图片描述](https://img-blog.csdnimg.cn/3697ec93c8bb4b45b7ecc4582535e4d5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow...
  • 通过对栈式自编码器深度学习算法进行研究,提出一种深度学习降维信息损失度量方法,将香农信息理论运用到降维信息损失度量中,计算深度学习降维过程中信息损失量,并研究其与算法性能的关系,为深度学习算法的改进提供...
  • 深度学习是当前人工智能领域广泛使用的一种机器学习方法.深度学习对数据的高度依赖性使得数据需要...实验证明:当提取VGG-16神经网络fc3层的4096维特征后,使用PCA法将数据维度降至64维,依然能够保持较高的特征信息.
  • 降维: – 主成分分析PCA降维处理 聚类: – K-means(k均值聚类) 2、主成分分析 应用PCA实现特征的降维 ·定义:高维数据转化为低维数据的过程,在此过程中可能会舍弃原有数据、创造新的变量 ·作用:是数据维散...
  • PCA数据降维python程序

    2021-05-04 10:06:15
    可直接使用,读取excel表格信息降维后输出表格信息~
  • 主要是将数据从高维数据转到低维数据,并在低维空间里也保持其在高维空间里所携带的信息(比如高维空间里有的清晰的分布特征,转到低维度时也依然存在)。 TSNE目的:将高维数据降维并进行可视化,输入的数据为N个...
  • 局部线性嵌入(LLE)和等距映射(ISOMAP)在降维过程中都只单一地保留数据集的某一种特性结构,从而使降维后的数据集往往存在顾此失彼的情况。针对这种情况,借助流形学习的核框架,提出融合LLE和ISOMAP的非线性降维...
  • 每个神经元能自动观察每一维度的信息,然后自动调整,组合学习,形成比较好的效果。这里采用神经网络。 2、为什么要转化为分类问题 机器学习问题归纳下来就是解决regression和classification问题,也就是回归...
  • 最早起源于当我们仅能获得物体之间的相似性矩阵时,如何由此来重构它们的欧几里得坐标,如对一个国家的许多城市而言,假如我们不知道它们的经纬度信息,却知道所有城市两两之间的距离,就可以通过MDS方法重现它们的...
  • 新手教程,含搜集资料加代码。高光谱图像分类是高光谱遥感对地观测技术的一项重要内容,在军事及民用领域都有着重要的应用。然而,高光谱图像的高维...一方面高光谱图像相邻波段之间相关性较大,存在较高的信息冗余。
  • 利用信息熵理论,将高光谱遥感影像的各波段抽象为具有相关性的独立个体,设计了高光谱遥感影像的决策表矩阵,进而计算各波段的信息熵,量化各波段的信息量,从而将各波段根据信息增益进行排序。用户可根据高光谱遥感...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 52,567
精华内容 21,026
关键字:

信息降维