Tag Archives: Dimensionality Reduction

SVD Dimension Reduction 奇异值分解 降维

降维的意义:

  1. 找出隐含的相关关系
  2. 去除无意义的特征
  3. 便于理解、可视化、存储

方法一:奇异值分解

可以参见以前的文章
A = USigma V^T

例子:

输入矩阵:

  • A_{[m times n]} 表示m篇文档和n个术语

分解获得:

  1. U_{[mtimes r]}表示m篇文档和r个概念
  2. Sigma_{[rtimes r]}, r的值等于矩阵A的rank
  3. V_{[ntimes r]}表示n个术语和r个概念

沿用之前TF-IDF时候的代码:

矩阵M4times 35的矩阵,表示4篇文章和35个术语

奇异值分解的几个属性:

  1. 实数矩阵A,总是可以进行奇异值分解的
  2. 分解后的U,Sigma ,V都是唯一的
  3. U,V都是列正交的(每一列都是相互垂直的单位向量)
  4. Sigma是一个对角矩阵,对角线上的元素是奇异值,且均为正数,并且从左上往下按照大小排列

测试一下U是否是列正交的

看一下U矩阵的具体内容:

这个矩阵每一行代表一篇文档,每一列代表一个概念。

  • 文档1和概念2,4相关性较高
  • 文档2和概念2,3相关性较高
  • 文档3和概念3相关性较高
  • 文档4和概念1相关性较高

看一下Sigma矩阵:

这个矩阵可以理解为4个概念的强度,揭示的是将数据投影到低维度空间中时,在各个坐标方向数据的方差。

看一下V^T矩阵:

每一行代表一个概念,每一列代表一个术语,每个元素代表的是术语与概念之间的相关关系,是将高位数据进行投影时所依据的坐标系。

验证一下分解的正确性:

奇异值降解SVD提供的是”最佳"低维度坐标系,“最佳”的含义是:将高维度数据投影到该低维度坐标系后损失的信息最少。

这个最佳的坐标系可以通过V^T矩阵获得,记得本例中的V矩阵的含义是:概念与术语之间的关系。

将原本表示“文档-术语"关系的矩阵M投影为"文档-概念",投影方法为:

QQ截图20150309182607

每一行代表一篇文档,每一列代表一个概念。

用SVD进行降维的方法:

  1. 进行SVD分解
  2. 若要降维至k维,用(U矩阵的前k列构成的矩阵)与(Sigma矩阵的前kk列构成的矩阵)进行点积
  3.  如果要将该低维度的数据表现恢复至高维度,则用2中结果与V^T矩阵的前k列所构成的矩阵进行点积

例如,投影到2维:

每一行代表一篇文章,每一列代表降至2维后,每篇文章在各个维度方向的投影。

将有损压缩的该低维度投影,恢复至原本的高维度:

原本数据是35维的,因而无法直接进行可视化。降至2维后,便可以了:

SVD_Plot

 

注意到,之前介绍过计算文档之间的相似程度,不妨用来验证一下,这个低维度的投影中,代表文档的点与点之间的距离,是否直觉上符合他们之间的相似度?

至于选择怎样的k来进行降维,通常会选择k使得,"能量"的损失在20%以内。

frac{sum_{i = 1}^{k}sigma_i^2}{sum_{i = 1}^{r}sigma_i^2} leq 0.8

机器学习笔记 Week8 降维

学习笔记(Machine Learning) Week8

全部笔记PDF版:http://vdisk.weibo.com/s/J4rRX/1373287206

Week8 由两部分内容构成:

  1. 聚类
  2. 降维

2 降维(Dimensionality Reduction)

2.1 动机一:数据压缩(Data Compression)

通过几个例子来介绍降维。

将数据从二维降至一维:

假使我们要采用两种不同的仪器来测量一些东西的尺寸,其中一个仪器测量结果的单位是英寸,另一个仪器测量的结果是厘米,我们希望将测量的结果作为我们机器学习的特征。现在的问题的是,两种仪器对同一个东西测量的结果不完全相等(由于误差、精度等),而将两者都作为特征有些重复,因而,我们希望将这个二维的数据降至一维。

QQ截图20130704143340

具体做法是,我们找出一条合适的直线,然后将所有的数据点都投射到该直线上,然后用z(i)标识,这样我们便完成了二维数据x(i)向一维数据z(i)的映射。这样新的到的特征只是原有特征的近似,但是这样做将我们的存储、内存占用量减半,并且使我们要使用这些数据的算法可以运行得更快。

将数据从三维降至二维:

这个例子中我们要将一个三维的特征向量降至一个二维的特征向量。过程是与上面类似的,我们将三维向量投射到一个二维的平面上,强迫使得所有的数据都在同一个平面上,降至二维的特征向量。

QQ截图20130704144255

这样的处理过程可以被用于把任何维度的数据降到任何想要的维度,例如将1000维的特征降至100维。

2.2动机二:数据可视化(Data Visualization)

在许多及其学习问题中,如果我们能将数据可视化,我们便能寻找到一个更好的解决方案,降维可以帮助我们。

假使我们有有关于许多不同国家的数据,每一个特征向量都有50个特征(如,GDP,人均GDP,平均寿命等)。如果要将这个50维的数据可视化是不可能的。使用降维的方法将其降至2维,我们便可以将其可视化了。

这样做的问题在于,降维的算法只负责减少唯独,新产生的特征的意义就必须由我们自己去发现了。

2.3主要成分分析(Principal Component Analysis)

主要成分分析是最常见的降维算法。

在PCA中,我们要做的是找到一个方向向量(Vector direction),当我们把所有的数据都投射到该向量上时,我们希望投射平均均方误差能尽可能地小。方向向量是一个经过原点的向量,而投射误差是从特征向量向该方向向量作垂线的长度。

Machine Learning

下面给出主要成分分析问题的描述:

  • 问题是要将n维数据降至k维
  • 目标是找到向量u(1),u(2),...,u(k)使得总的投射误差最小

主要成分分析与线性回顾的比较:

主要成分分析与线性回归是两种不同的算法。主要成分分析最小化的是投射误差而线性回归尝试的是最小化预测误差。线性回归的目的是预测结果,而主要成分分析不作任何预测。

QQ截图20130704151555

上图中,左边的是线性回归的误差,右边则是主要成分分析的误差。

2.4主要成分分析算法

第一步是均值归一化。我们需要计算出所有特征的均值,然后令xj=xjj。如果特征是在不同的数量级上,我们还需要将其除以标准差σ2

第二步是计算协方差矩阵(covariance matrix)Σ:

QQ截图20130704152823

第三步是计算协方差矩阵的特征向量(eigenvectors):

在Octave里我们可以利用奇异值分解(singular value decomposition)来求解,[U, S, V] = svd(sigma)。

对于一个n×n维度的矩阵,上式中的U是一个具有与数据之间最小投射误差的方向向量构成的矩阵。如果我们希望将数据从n维降至k维,我们只需要从U真呢个选取前K个向量,获得一个n×k维度的矩阵,我们用Ureduce表示,然后通过如下计算获得要求的新特征向量z(i)

daum_equation_1372923400498

其中x是n×1维的,因此结果为k×1维度。

注,我们不对偏倚特征进行处理。

2.5选择主要成分的数量

主要成分分析是减少投射的平均均方误差:

QQ截图20130704154159

训练集的方差为:

QQ截图20130704154208

我们希望在平均均方误差与训练集方差的比例尽可能小的情况下选择尽可能小的K值。

如果我们希望这个比例小于1%,就意味着原本数据的偏差有99%都保留下来了,如果我们选择保留95%的偏差,便能非常显著地降低模型中特征的维度了。

我们可以先令K=1,然后进行主要成分分析,获得Ureduce和z,然后计算比例是否小于1%。如果不是的话再令K=2,如此类推,直到找到可以使得比例小于1%的最小K值(原因是各个特征之间通常情况存在某种相关性)。

还有一些更好的方式来选择K,当我们在Octave中调用“svd”函数的时候,我们获得三个参数:[U, S, V] = svd(sigma)。

QQ截图20130704220742

其中的S是一个n×n的矩阵,只有对角线上有值,而其它单元都是0,我们可以使用这个矩阵来计算平均均方误差与训练集方差的比例:

图片1

也就是:

QQ截图20130704220913

在压缩过数据后,我们可以采用如下方法来近似地获得原有的特征:

daum_equation_1372947232882

2.6应用主要成分分析

假使我们正在针对一张100×100像素的图片进行某个计算机视觉的机器学习,即总共有10000个特征。

  1. 第一步是运用主要成分分析将数据压缩至1000个特征
  2. 然后对训练集运行学习算法
  3. 在预测时,采用之前学习而来的Ureduce将输入的特征x转换成特征向量z,然后再进行预测

注,如果我们有交叉验证集合测试集,也采用对训练集学习而来的Ureduce。

错误的主要成分分析情况:

一个常见错误使用主要成分分析的情况是,将其用于减少过拟合(减少了特征的数量)。这样做非常不好,不如尝试归一化处理。原因在于主要成分分析只是近似地丢弃掉一些特征,它并不考虑任何与结果变量有关的信息,因此可能会丢失非常重要的特征。然而当我们进行归一化处理时,会考虑到结果变量,不会丢掉重要的数据。

另一个常见的错误是,默认地将主要成分分析作为学习过程中的一部分,这虽然很多时候有效果,最好还是从所有原始特征开始,只在有必要的时候(算法运行太慢或者占用太多内存)才考虑采用主要成分分析。

课程地址:https://class.coursera.org/ml-003/class/index