周志华机器学习西瓜书全书16章Chap10降维和度量学习PPT课件.ppt
《周志华机器学习西瓜书全书16章Chap10降维和度量学习PPT课件.ppt》由会员分享,可在线阅读,更多相关《周志华机器学习西瓜书全书16章Chap10降维和度量学习PPT课件.ppt(45页珍藏版)》请在三一文库上搜索。
1、丁尧相第十章:降维与度量学习第十章:降维与度量学习大纲大纲pk近邻学习p多维缩放p主成分分析p流形学习p度量学习k近邻学习近邻学习k近邻学习的工作机制pk近邻(k-Nearest Neighbor,kNN)学习是一种常用的监督学习方法:l确定训练样本,以及某种距离度量。l对于某个给定的测试样本,找到训练集中距离最近的k个样本,对于分类问题使用“投票法”获得预测结果,对于回归问题使用“平均法”获得预测结果。还可基于距离远近进行加权平均或加权投票,距离越近的样本权重越大。l投票法:选择这k个样本中出现最多的类别标记作为预测结果。l平均法:将这k个样本的实值输出标记的平均值作为预测结果。“懒惰学习懒
2、惰学习”与与“急切学习急切学习”p“懒惰学习”(lazy learning):此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为零,待收到测试样本后再进行处理。p“急切学习”(eager learning):在训练阶段就对样本进行学习处理的方法。K近邻学习没有显式的训练过程,属于“懒惰学习”k近邻分类示意图近邻分类示意图pk近邻分类器中的k是一个重要参数,当k取不同值时,分类结果会有显著不同。另一方面,若采用不同的距离计算方式,则找出的“近邻”可能有显著差别,从而也会导致分类结果有显著不同。k近邻学习近邻学习分析最近邻分类器(1NN)二分类错误率p暂且假设距离计算是“恰当”的,即能够恰
3、当地找出k个近邻,我们来对“最近邻分类器”(1NN,即k=1)在二分类问题上的性能做一个简单的讨论。给定测试样本 ,若其最近邻样本为 ,则最近邻出错的概率就是 与 类别标记不同的概率,即k近邻学习近邻学习分析1NN二分类错误率令 表示贝叶斯最优分类器的结果,有 最近邻分类虽简单,但它的泛化错误率不超过贝叶斯最优分类器错误率的两倍!低维嵌入低维嵌入维数灾难(curse of dimensionality)p上述讨论基于一个重要的假设:任意测试样本 附近的任意小的 距离范围内总能找到一个训练样本,即训练样本的采样密度足够大,或称为“密采样”。然而,这个假设在现实任务中通常很难满足:l若属性维数为1
4、当 =0.001,仅考虑单个属性,则仅需1000个样本点平均分布在归一化后的属性取值范围内,即可使得任意测试样本在其附近0.001距离范围内总能找到一个训练样本,此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。若属性维数为20,若样本满足密采样条件,则至少需要 个样本。l现实应用中属性维数经常成千上万,要满足密采样条件所需的样本数目是无法达到的天文数字。许多学习方法都涉及距离计算,而高维空间会给距离计算带来很大的麻烦,例如当维数很高时甚至连计算内积都不再容易。l在高维情形下出现的数据样本稀疏、距离计算困难等问题,是所有机器学习方法共同面临的严重障碍,被称为“维数灾难”。低维嵌入
5、低维嵌入p缓解维数灾难的一个重要途径是降维(dimension reduction)l即通过某种数学变换,将原始高维属性空间转变为一个低维“子空间”(subspace),在这个子空间中样本密度大幅度提高,距离计算也变得更为容易。p为什么能进行降维?l数据样本虽然是高维的,但与学习任务 密切相关的也许仅是某个低维分布,即高维空间中的一个低维“嵌入”(embedding),因而可以对数据进行有效的降维。多维缩放多维缩放p若要求原始空间中样本之间的距离在低维空间中得以保持,即得到“多维缩放”(Multiple Dimensional Scaling,MDS):p假定有m个样本,在原始空间中的距离矩阵
6、为 ,其第i行j列的元素 为样本 到 的距离。p目标是获得样本在 维空间中的欧氏距离等于原始空间中的距离,即 p令 ,其中 为降维后的内积矩阵,有多维缩放多维缩放p为便于讨论,令降维后的样本 被中心化,即 。显然,矩阵 的行与列之和均为零,即 易知其中 表示矩阵的迹(trace),。令由此即可通过降维前后保持不变的距离矩阵 求取内积矩阵 :多维缩放多维缩放p对矩阵 做特征值分解(eigenvalue decomposition),其中 为特征值构成的对角矩阵,为特征向量矩阵,假定其中有 个非零正特征值,它们构成对角矩阵 ,为特征向量矩阵。令 表示相应的特征矩阵,则 可表达为 。多维缩放多维缩放
7、p对矩阵 做特征值分解(eigenvalue decomposition),其中 为特征值构成的对角矩阵,p在现实应用中为了有效降维,往往仅需降维后的距离与原始空间中的距离尽可能接近,而不必严格相等。此时可取 个最大特征值构成对角矩阵 ,令 表示相应的特征向量矩阵,则 可表达为 为特征向量矩阵,假定其中有 个非零正特征值,它们构成对角矩阵 ,为特征向量矩阵。令 表示相应的特征矩阵,则 可表达为 。多维缩放多维缩放MDS算法的描述线性降维方法线性降维方法p一般来说,欲获得低维子空间,最简单的是对原始高维空间进行线性变换。给定 维空间中的样本 ,变换之后得到 维空间中的样本p变换矩阵 可视为 个
8、维属性向量。换言之,是原属性向量 在新坐标系 中的坐标轴向量。若 与 正交,则新坐标系是一个正交坐标系,此时 为正交变换。显然,新空间中的属性是原空间中的属性的线性组合。p基于线性变换来进行降维的方法称为线性降维方法,对低维子空间性质的不同要求可通过对 施加不同的约束来实现。其中 是变换矩阵,是样本在新空间中的表达。主成分分析主成分分析主成分分析(Principal Component Analysis,简称PCA)p对于正交属性空间中的样本点,如何用一个超平面对所有样本进行恰当的表达?p容易想到,若存在这样的超平面,那么它大概应具有这样的性质:l最近重构性:样本点到这个超平面的距离都足够近;
9、l最大可分性:样本点在这个超平面上的投影能尽可能分开。p基于最近重构性和最大可分性,能分别得到主成分分析的两种等价推导。主成分分析主成分分析最近重构性p对样本进行中心化,再假定投影变换后得到的新坐标系为 ,其中 是标准正交基向量,p若丢弃新坐标系中的部分坐标,即将维度降低到 ,则样本点在低维坐标系中的投影是 ,是 在低维坐标下第 维的坐标,若基于 来重构 ,则会得到主成分分析主成分分析最近重构性p考虑整个训练集,原样本点 与基于投影重构的样本点 之间的距离为p根据最近重构性应最小化上式。考虑到 是标准正交基,是协方差矩阵,有这就是主成分分析的优化目标。主成分分析主成分分析最大可分性p样本点 在
10、新空间中超平面上的投影是 ,若所有样本点的投影能尽可能分开,则应该使得投影后样本点的方差最大化。若投影后样本点的方差是 ,于是优化目标可写为 显然与 等价。主成分分析主成分分析PCA的求解p对优化式使用拉格朗日乘子法可得 只需对协方差矩阵 进行特征值分解,并将求得的特征值排序:,再取前 个特征值对应的特征向量构成 ,这就是主成分分析的解。主成分分析主成分分析PCA算法主成分分析主成分分析p降维后低维空间的维数 通常是由用户事先指定,或通过在 值不同的低维空间中对k近邻分类器(或其它开销较小的学习器)进行交叉验证来选取较好的 值。对PCA,还可从重构的角度设置一个重构阈值,例如 ,然后选取使下式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 周志华 机器 学习 西瓜 全书 16 Chap10 维和 度量 PPT 课件
