周志华-机器学习-西瓜书-全书16章-ppt-Chap10降维和度量学习课件.ppt

《周志华-机器学习-西瓜书-全书16章-ppt-Chap10降维和度量学习课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、丁尧相第十章：降维与度量学习大纲k近邻学习多维缩放主成分分析流形学习度量学习k近邻学习k近邻学习的工作机制k近邻(k-NearestNeighbor,kNN)学习是一种常用的监督学习方法:确定训练样本，以及某种距离度量。对于某个给定的测试样本，找到训练集中距离最近的k个样本，对于分类问题使用“投票法”获得预测结果，对于回归问题使用“平均法”获得预测结果。还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。投票法：选择这k个样本中出现最多的类别标记作为预测结果。平均法：将这k个样本的实值输出标记的平均值作为预测结果。“懒惰学习”与“急切

2、学习”“懒惰学习”(lazylearning):此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。“急切学习”(eagerlearning):在训练阶段就对样本进行学习处理的方法。K近邻学习没有显式的训练过程，属于“懒惰学习”k近邻分类示意图k近邻分类器中的k是一个重要参数，当k取不同值时，分类结果会有显著不同。另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。k近邻学习分析最近邻分类器（1NN）二分类错误率暂且假设距离计算是“恰当”的，即能够恰当地找出k个

3、近邻，我们来对“最近邻分类器”（1NN，即k=1）在二分类问题上的性能做一个简单的讨论。给定测试样本，若其最近邻样本为，则最近邻出错的概率就是与类别标记不同的概率，即k近邻学习分析1NN二分类错误率令表示贝叶斯最优分类器的结果，有最近邻分类虽简单，但它的泛化错误率不超过贝叶斯最优分类器错误率的两倍！低维嵌入维数灾难(curseofdimensionality)上述讨论基于一个重要的假设：任意测试样本附近的任意小的距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”。然而，这个假设在现实任务中通常很难满足：若属性维数为1，当

4、=0.001，仅考虑单个属性，则仅需1000个样本点平均分布在归一化后的属性取值范围内，即可使得任意测试样本在其附近0.001距离范围内总能找到一个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。若属性维数为20，若样本满足密采样条件，则至少需要个样本。现实应用中属性维数经常成千上万，要满足密采样条件所需的样本数目是无法达到的天文数字。许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易。在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严

5、重障碍，被称为“维数灾难”。低维嵌入缓解维数灾难的一个重要途径是降维(dimensionreduction)即通过某种数学变换，将原始高维属性空间转变为一个低维“子空间”(subspace)，在这个子空间中样本密度大幅度提高，距离计算也变得更为容易。为什么能进行降维？数据样本虽然是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入”(embedding)，因而可以对数据进行有效的降维。多维缩放若要求原始空间中样本之间的距离在低维空间中得以保持，即得到“多维缩放”(MultipleDimensionalScaling,

6、MDS)：假定有m个样本，在原始空间中的距离矩阵为，其第i行j列的元素为样本到的距离。目标是获得样本在维空间中的欧氏距离等于原始空间中的距离，即令，其中为降维后的内积矩阵，，有多维缩放为便于讨论，令降维后的样本被中心化，即。显然，矩阵的行与列之和均为零，即易知其中表示矩阵的迹(trace)，。令由此即可通过降维前后保持不变的距离矩阵求取内积矩阵:多维缩放对矩阵做特征值分解(eigenvaluedecomposition)，其中为特征值构成的对角矩阵，为特征向量矩阵，假定其中有个非零正特征值，它们构成对角矩阵，为特征向量矩阵。令表示相应的特征矩阵，

7、则可表达为。多维缩放对矩阵做特征值分解(eigenvaluedecomposition)，其中为特征值构成的对角矩阵，在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可取个最大特征值构成对角矩阵，令表示相应的特征向量矩阵，则可表达为为特征向量矩阵，假定其中有个非零正特征值，它们构成对角矩阵，为特征向量矩阵。令表示相应的特征矩阵，则可表达为。多维缩放MDS算法的描述线性降维方法一般来说，欲获得低维子空间，最简单的是对原始高维空间进行线性变换。给定维空间中的样本，变换之后得到维空间中的样本变换矩阵可视为

8、个维属性向量。换言之，是原属性向量在新坐标系中的坐标轴向量。若与正交，则新坐标系是一个正交坐标系，此时为正交变换。显然，新空间中的属性是