工具类服务
编辑部专用服务
作者专用服务
基于局部线性嵌入的降维算法研究
随着科学的进步，信息技术得到了快速发展及广泛应用，高维数据应运而生，如医学图像处理、计算生物学、全球气候模型等，高维数据难以被现有的机器学习和数据挖掘算法进行有效地处理。数据降维算法是处理这些高维数据的一个非常重要的工具和方法。而流形学习作为一种高维数据降维的技术手段，在非线性降维方面取得了广泛的应用。　　
其中局部线性嵌入(LLE)是一种假设局部能够线性化表示而提出的流形学习算法，它有参数少、计算快、易求全局最优解等优点。但是，LLE算法使得降维后的数据损失了原有数据的密度信息，从而导致降维效果产生扭曲，无法获得正确的低维嵌入。另外，多流形数据不满足局部线性嵌入算法要求流形连续的特点，所以也难以有效降维。这两个问题成为了局部线性嵌入的瓶颈。　　
本文主要对基于流形学习的局部线性嵌入(LLE)算法进行了深入的研究与改进，对LLE的缺点进行了详细地分析：　　
(1)在源数据集分布不均匀、密度变化大的情况下，分析了LLE算法降维的基本思想，得出权值矩阵在降维过程中起到了连接枢纽的重要作用，而近邻的选取对权值矩阵的获得具有直接的影响。因此，一方面从局部近邻的几何性质入手，对近邻选取情况进行改进，另一方面对LLE权向量的性质进行了详细的分析，得知降维后的数据不能反映原来高维数据的密度信息。在以上基础上提出了一种基于密度刻画的降维方法。　　
(2)对多流形问题进行了研究，发现多流形数据存在局域线性化差的问题，从局部线性嵌入算法的两个独立的优化问题入手，对LLE算法进行改进，提出了一种基于局部线性嵌入的多流形学习算法。
学科专业：
授予学位：
学位授予单位：
导师姓名：
学位年度：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社苹果/安卓/wp
积分 78, 距离下一级还需 7 积分
道具: 彩虹炫, 涂鸦板, 雷达卡, 热点灯, 金钱卡, 显身卡下一级可获得
权限: 自定义头衔
购买后可立即获得
权限: 隐身
道具: 金钱卡, 彩虹炫, 雷达卡, 热点灯, 涂鸦板
开心签到天数: 4 天连续签到: 1 天[LV.2]偶尔看看I
本帖最后由 xboy5 于
17:24 编辑
最近看到这个，有点被搞糊涂了0.0
我的混沌逻辑是这样的：
之前做回归的时候，会通过方差分析来筛选出对回归影响不显著的变量如y~x1+x2+x3+x4,假设x4方差分析下不显著，那就剔除他。方差分析的应用应该是逐步回归，是吧，这样算不算是一种降维思想？
然后最近了解了主成分分析和因子分析，这两就是用来专门降维的，其实也就是对变量进行操作，如主成分对变量进行线性变换，重新组合出新的第一主成分，第二主成分，是吧
那我的问题是，主成分分析跟方差分析之间到底是什么关系？这两是互补的吗，可以用完主成分再用逐步回归？？或者什么时候用主成分，什么时候用方差分析？两个最终都降维了不是，搞晕了搞晕了，求大神解答！
支持楼主：、
购买后，论坛将把您花费的资金全部奖励给楼主，以表示您对TA发好贴的支持
载入中......
xboy5 发表于
最近看到这个，有点被搞糊涂了0.0
我的混沌逻辑是这样的：
方差分析和主成份分析是两种不同的分析方法，两者没多大关联。因子分析和逐步回归是解决自变量严重多重共线性问题的两种不同方法。
pca旨在通过构建新指标简化原先指标
一级伯乐勋章
一级伯乐勋章
初级学术勋章
初级学术勋章
初级热心勋章
初级热心勋章
初级信用勋章
初级信用勋章
中级热心勋章
中级热心勋章
中级学术勋章
中级学术勋章
中级信用勋章
中级信用勋章
高级热心勋章
高级热心勋章
高级学术勋章
高级学术勋章
高级信用勋章
高级信用勋章
特级热心勋章
高级热心勋章
特级学术勋章
特级学术勋章
特级信用勋章
高级信用勋章
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
如有投资本站或合作意向，请联系（010-）；
邮箱：service@pinggu.org
投诉或不良信息处理：（010-）
论坛法律顾问：王进律师PCA 降维算法详解 以及代码示例
我的图书馆
PCA 降维算法详解 以及代码示例
PCA ：&principal component analysis ( 主成分分析)
最近发现我的一篇关于PCA算法总结以及个人理解的博客的访问量比较高， 刚好目前又重新学习了一下PCA （主成分分析） 降维算法， 所以打算把目前掌握的做个全面的整理总结， 能够对有需要的人有帮助。 自己再看自己写的那个关于PCA的博客， 发现还是比较混乱的， 希望这里能过做好整理。 本文的所有总结参考了Andrew Ng的PCA教程， 有兴趣的可以自己学习。
上一篇关于PCA 的博客：&， 在这篇博客中，有关于我最初在读研的时候关于PCA的认识， 但是不是很系统， 然后里面却给出了很多我总结的网络上的资料，
以及根据我个人使用的经验总结的感悟， 所以还是收到了很多的好评， o(∩∩)o...哈哈， 谢谢各位的支持。
2. PCA的应用范围
PCA的应用范围有：
1. 数据压缩
1.1 数据压缩或者数据降维首先能够减少内存或者硬盘的使用， 如果内存不足或者计算的时候出现内存溢出等问题， 就需要使用PCA获取低维度的样本特征。
1.2 其次， 数据降维能够加快的速度。&
2. 数据可视化
在很多情况下， 可能我们需要查看样本特征， 但是高维度的特征根本无法观察， 这个时候我们可以将样本的特征降维到2D或者3D， 也就是将样本的特征维数降到2个特征或者3个特征， 这样我们就可以采用可视化观察数据。
3. PCA原理简介
3.1 基础入门
这里我只给出在需要使用PCA的时候需要了解的最基本的PCA的原理， 了解这些原理后对于正常的使用没有问题， 如果想要深入了解PCA， 需要学习一些矩阵分析的知识， 更加详细的PCA算法请见wikipedia。
首先， 我们定义样本和特征， 假定有 m 个样本， 每个样本有 n 个特征， 可以如下表示：
由简到难， 先看一下从2D 降维到1D的比较直观的表示：
在上图中， 假设只有两个特征x1, x2, 然后需要降维到1D， 这个时候我们可以观察途中X所表示的样本点基本上分布在一条直线上， 那么就可以将所有的用(x1, x2)平面表示的坐标映射到图像画出的直线z上， 上图中的黑色铅笔线表示样本点映射的过程。&
映射到直线Z后， 如果只用直线Z表示样本的空间分布， 就可以用1个坐标表示每个样本了， 这样就将2D的特征降维到1D的特征。 同样的道理， 如果将3D的特征降维到2D， 就是将具有3D特征的样本从一个三维空间中映射到二维空间。
在上图中， 将所有的二维特征的样本点映射到了一维直线上， &这样， 从上图中可以看出在映射的过程中存在映射误差。
在上图中， 用圆圈表示了样本映射后的坐标位置。这些位置可以叫做近似位置， 以后还要用到这些位置计算映射误差。
&因为在降维映射的过程中， 存在映射误差， 所有在对高维特征降维之前， 需要做特征归一化（feature normalization）, 这个归一化操作包括： （1） feature scaling (让所有的特征拥有相似的尺度， 要不然一个特征特别小， 一个特征特别大会影响降维的效果) （2） zero mean normalization (零均值归一化)。&
在上图中， 也可以把降维的过程看作找到一个或者多个向量u1, u2, ...., un， 使得这些向量构成一个新的向量空间（需要学习矩阵分析哦）， 然后把需要降维的样本映射到这个新的样本空间上。
对于2D -& 1D 的降维过程， 可以理解为找到一个向量u1, &u1表示了一个方向， 然后将所有的样本映射到这个方向上， 其实， 一个向量也可以表示一个样本空间。
对于3D -& 2D 的降维过程， 可以理解为找到两个向量u1, u2, (u1, u2) 这两个向量定义了一个新的特征空间， 然后将原样本空间的样本映射到新的样本空间。
对于n-D -& k-D 的降维过程， 可以理解为找到 k 个向量 u1, u2, ..., uk, 这k个向量定义了新的向量空间， 然后进行样本映射。
3.2 &Cost Function
既然样本映射存在误差， 就需要计算每次映射的误差大小。 采用以下公式计算误差大小：
X-approx表示的是样本映射以后的新的坐标， 这个坐标如果位置如果用当前的样本空间表示， 维度和 样本X是一致的。
要特别注意， PCA降维和linear regression是不一样的， 虽然看上去很一致， 但是linear regression的cost function的计算是样本上线垂直的到拟合线的距离， 而PCA的cost function 是样本点到拟合线的垂直距离。 差别如下图所示：
3.3 PCA 计算过程
（A） Feature Normalization
首先要对训练样本的特征进行归一化， 特别强调的是， 归一化操作只能在训练样本中进行， 不能才CV集合或者测试集合中进行， 也就是说归一化操作计算的各个参数只能由训练样本得到， 然后测试样本根据这里得到的参数进行归一化， 而不能直接和训练样本放在一起进行归一化。&
另外， 在训练PCA降维矩阵的过程中，也不能使用CV样本或者测试样本， 这样做是不对的。 有很多人在使用PCA训练降维矩阵的时候， 直接使用所有的样本进行训练， 这样实际上相当于作弊的， 这样的话降维矩阵是在包含训练样本和测试样本以及CV样本的情况下训练得到的， 在进行测试的时候， 测试样本会存在很大的优越性， 因为它已经知道了要降维到的空间情况。
特征归一化直接给出代码参考：
function&[X_norm,&mu,&sigma]&=&featureNormalize(X)&&%FEATURENORMALIZE&Normalizes&the&features&in&X&&&%&&&FEATURENORMALIZE(X)&returns&a&normalized&version&of&X&where&&%&&&the&mean&value&of&each&feature&is&0&and&the&standard&deviation&&%&&&is&1.&This&is&often&a&good&preprocessing&step&to&do&when&&%&&&working&with&learning&algorithms.&&&&mu&=&mean(X);&&X_norm&=&bsxfun(@minus,&X,&mu);&&&&sigma&=&std(X_norm);&&X_norm&=&bsxfun(@rdivide,&X_norm,&sigma);&&&&&&%&============================================================&&&&end&&
注意： 这里的X是一个m * n 的矩阵， 有 m 个样本， 每个样本包含 n 个特征， 每一行表示一个样本。 X_norm是最终得到的特征， 首先计算了所有训练样本每个特征的均值， 然后减去均值， 然后除以标准差。&
（B） 计算降维矩阵
B1. 首先计算样本特征的协方差矩阵
如下图所示， 如果是每个样本单独计算， 则采用图中横线上的公式， 如果是采用矩阵化的计算， 则采用横线下的公式。
B2. 计算协方差矩阵的特征值和特征向量
采用奇异值分解的算法计算协方差矩阵的特征值和特征向量， &奇异值分解是个比较复杂的概念， 如果有兴趣可以查看wikipedia， 也可以直接使用matlab或者octave已经提供的奇异值分解的接口。
在上图中， U 则是计算得到的协方差矩阵的所有特征向量， 每一列都是一个特征向量， 并且特征向量是根据特征大小由大到小进行排序的， U 的维度为 n * n 。 U 也被称为降维矩阵。 利用U 可以将样本进行降维。 默认的U 是包含协方差矩阵的所有特征向量， 如果想要将样本降维到 k 维， 那么就可以选取 U 的前 k 列， Uk 则可以用来对样本降维到 &k 维。 这样 Uk 的维度为 n * k
（C） 降维计算
获得降维矩阵后， 即可通过降维矩阵将样本映射到低维空间上。 降维公式如下图所示：
如果是对于矩阵X 进行降维， X 是 m * n的， 那么降维后就变为 m * k 的维度， 每一行表示一个样本的特征。
3.4 &贡献率 （降维的k的值的选择）
在&&这篇文章中， 很多人问了关于贡献率的问题， 这就是相当于选择k的值的大小。 也就是选择降维矩阵 U 中的特征向量的个数。&
k 越大， 也就是使用的U 中的特征向量越多， 那么导致的降维误差越小， 也就是更多的保留的原来的特征的特性。 反之亦然。
从信息论的角度来看， 如果选择的 k 越大， 也就是系统的熵越大， 那么就可以认为保留的原来样本特征的不确定性也就越大， 就更加接近真实的样本数据。 如果 k 比较小， 那么系统的熵较小， 保留的原来的样本特征的不确定性就越少， 导致降维后的数据不够真实。 （完全是我个人的观点）
关于 k 的选择， 可以参考如下公式：&
上面这个公式 要求 &= 0.01， 也就是说保留了系统的99%的不确定性。&
需要计算的就是， 找到一个最小的 k 使得上面的公式成立， 但是如果计算上面公式， 计算量太大， 并且对于每一个 &k &取值都需要重新计算降维矩阵。&
可以采用下面的公式计算 k 的取值， 因为在 对协方差矩阵进行奇异值分解的时候返回了 S , S 为协方差矩阵的特征值， 并且 S 是对角矩阵， 维度为 &n * n， 计算 k 的取值如下：
3.5 &重构 （reconstruction， 根据降维后数据重构原数据）， 数据还原
获得降维后的数据， 可以根据降维后的数据还原原始数据。
还原原始数据的过程也就是获得样本点映射以后在原空间中的估计位置的过程， 即计算 X-approx的过程。
使用降维用的降维矩阵 Uk， 然后将 降维后的样本 z 还原回原始特征， 就可以用上图所示的公式。
4. PCA的应用示例
貌似本页已经写的太多了， 所以这里示例另外给出。&
由于篇幅问题， 这里只给出代码， 关于代码的解释和插图， 请访问上面链接
%%&Initialization&&clear&;&close&&clc&&&&fprintf('this&code&will&load&12&images&and&do&PCA&for&each&face.\n');&&fprintf('10&images&are&used&to&train&PCA&and&the&other&2&images&are&used&to&test&PCA.\n');&&&&m&=&4000;&%&number&of&samples&&trainset&=&zeros(m,&32&*&32);&%&image&size&is&:&32&*&32&&&&for&i&=&1&:&m&&&&&&img&=&imread(strcat('./img/',&int2str(i),&'.bmp'));&&&&&&img&=&double(img);&&&&&&trainset(i,&:)&=&img(:);&&end&&&&&&%%&before&training&PCA,&do&feature&normalization&&mu&=&mean(trainset);&&trainset_norm&=&bsxfun(@minus,&trainset,&mu);&&&&sigma&=&std(trainset_norm);&&trainset_norm&=&bsxfun(@rdivide,&trainset_norm,&sigma);&&&&%%&we&could&save&the&mean&face&mu&to&take&a&look&the&mean&face&&imwrite(uint8(reshape(mu,&32,&32)),&'meanface.bmp');&&fprintf('mean&face&saved.&paused\n');&&&&&&%%&compute&reduce&matrix&&X&=&trainset_&%&just&for&convience&&[m,&n]&=&size(X);&&&&U&=&zeros(n);&&S&=&zeros(n);&&&&Cov&=&1&/&m&*&X'&*&X;&&[U,&S,&V]&=&svd(Cov);&&fprintf('compute&cov&done.\n');&&&&%%&save&eigen&face&&for&i&=&1:10&&&&&&ef&=&U(:,&i)';&&&&&&img&=&&&&&&&minVal&=&min(img);&&&&&&img&=&img&-&minV&&&&&&max_val&=&max(abs(img));&&&&&&img&=&img&/&max_&&&&&&img&=&reshape(img,&32,&32);&&&&&&imwrite(img,&strcat('eigenface',&int2str(i),&'.bmp'));&&end&&&&fprintf('eigen&face&saved,&paused.\n');&&&&&&%%&dimension&reduction&&k&=&100;&%&reduce&to&100&dimension&&test&=&zeros(10,&32&*&32);&&for&i&=&&&&&&&img&=&imread(strcat('./img/',&int2str(i),&'.bmp'));&&&&&&img&=&double(img);&&&&&&test(i&-&4000,&:)&=&img(:);&&end&&&&%&test&set&need&to&do&normalization&&test&=&bsxfun(@minus,&test,&mu);&&&&%&reduction&&Uk&=&U(:,&1:k);&&Z&=&test&*&Uk;&&fprintf('reduce&done.\n');&&&&%%&reconstruction&&%%&for&the&test&set&images,&we&only&minus&the&mean&face,&&%&so&in&the&reconstruct&process,&we&need&add&the&mean&face&back&&Xp&=&Z&*&Uk';&&%&show&reconstructed&face&&for&i&=&1:5&&&&&&face&=&Xp(i,&:)&+&&&&&&&face&=&reshape((face),&32,&32);&&&&&&imwrite(uint8(face),&strcat('./reconstruct/',&int2str(4000&+&i),&'.bmp'));&&end&&&&%%&for&the&train&set&reconstruction,&we&minus&the&mean&face&and&divide&by&standard&deviation&during&the&train&&%&so&in&the&reconstruction&process,&we&need&to&multiby&standard&deviation&first,&&&%&and&then&add&the&mean&face&back&&trainset_re&=&trainset_norm&*&Uk;&%&reduction&&trainset_re&=&trainset_re&*&Uk';&%&reconstruction&&for&i&=&1:5&&&&&&train&=&trainset_re(i,&:);&&&&&&train&=&train&.*&&&&&&&train&=&train&+&&&&&&&train&=&reshape(train,&32,&32);&&&&&&imwrite(uint8(train),&strcat('./reconstruct/',&int2str(i),&'train.bmp'));&&end&&&&fprintf('job&done.\n');&&
TA的最新馆藏
喜欢该文的人也喜欢}