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

丁尧相第十章：降维与度量学习大纲k近邻学习多维缩放主成分分析流形学习度量学习k近邻学习k近邻学习的工作机制k近邻(k-NearestNeighbor,kNN)学习是一种常用的监督学习方法:确定训练样本，以及某种距离度量。对于某个给定的测试样本，找到训练集中距离最近的k个样本，对于分类问题使用“投票法”获得预测结果，对于回归问题使用“平均法”获得预测结果。还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。投票法：选择这k个样本中出现最多的类别标记作为预测结果。平均法：将这k个样本的实值输出标记的平均值作为预测结果。“懒惰学习”与“急切学习”“懒惰学习”(lazylearning):此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。“急切学习”(eagerlearning):在训练阶段就对样本进行学习处理的方法。K近邻学习没有显式的训练过程，属于“懒惰学习”k近邻分类示意图k近邻分类器中的k是一个重要参数，当k取不同值时，分类结果会有显著不同。另一方面，若采用不同的距离计算方式，则找出的“近邻”可能有显著差别，从而也会导致分类结果有显著不同。k近邻学习分析最近邻分类器（1NN）二分类错误率暂且假设距离计算是“恰当”的，即能够恰当地找出k个近邻，我们来对“最近邻分类器”（1NN，即k=1）在二分类问题上的性能做一个简单的讨论。给定测试样本，若其最近邻样本为，则最近邻出错的概率就是与类别标记不同的概率，即k近邻学习分析1NN二分类错误率令表示贝叶斯最优分类器的结果，有最近邻分类虽简单，但它的泛化错误率不超过贝叶斯最优分类器错误率的两倍！低维嵌入维数灾难(curseofdimensionality)上述讨论基于一个重要的假设：任意测试样本附近的任意小的距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”。然而，这个假设在现实任务中通常很难满足：若属性维数为1，当=0.001，仅考虑单个属性，则仅需1000个样本点平均分布在归一化后的属性取值范围内，即可使得任意测试样本在其附近0.001距离范围内总能找到一个训练样本，此时最近邻分类器的错误率不超过贝叶斯最优分类器的错误率的两倍。若属性维数为20，若样本满足密采样条件，则至少需要个样本。现实应用中属性维数经常成千上万，要满足密采样条件所需的样本数目是无法达到的天文数字。许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易。在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”。低维嵌入缓解维数灾难的一个重要途径是降维(dimensionreduction)即通过某种数学变换，将原始高维属性空间转变为一个低维“子空间”(subspace)，在这个子空间中样本密度大幅度提高，距离计算也变得更为容易。为什么能进行降维？数据样本虽然是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入”(embedding)，因而可以对数据进行有效的降维。多维缩放若要求原始空间中样本之间的距离在低维空间中得以保持，即得到“多维缩放”(MultipleDimensionalScaling,MDS)：假定有m个样本，在原始空间中的距离矩阵为，其第i行j列的元素为样本到的距离。目标是获得样本在维空间中的欧氏距离等于原始空间中的距离，即令，其中为降维后的内积矩阵，，有多维缩放为便于讨论，令降维后的样本被中心化，即。显然，矩阵的行与列之和均为零，即易知其中表示矩阵的迹(trace)，。令由此即可通过降维前后保持不变的距离矩阵求取内积矩阵:21111111,,iijjijijjimmmmijdistdistdistdistdistdistmmm多维缩放对矩阵做特征值分解(eigenvaluedecomposition)，其中为特征值构成的对角矩阵，为特征向量矩阵，假定其中有个非零正特征值，它们构成对角矩阵，为特征向量矩阵。令表示相应的特征矩阵，则可表达为。111B000000nnnZVVVV多维缩放对矩阵做特征值分解(eigenvaluedecomposition)，其中为特征值构成的对角矩阵，在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可取个最大特征值构成对角矩阵，令表示相应的特征向量矩阵，则可表达为为特征向量矩阵，假定其中有个非零正特征值，它们构成对角矩阵，为特征向量矩阵。令表示相应的特征矩阵，则可表达为。多维缩放MDS算法的描述线性降维方法一般来说，欲获得低维子空间，最简单的是对原始高维空间进行线性变换。给定维空间中的样本，变换之后得到维空间中的样本变换矩阵可视为个维属性向量。换言之，是原属性向量在新坐标系中的坐标轴向量。若与正交，则新坐标系是一个正交坐标系，此时为正交变换。显然，新空间中的属性是原空间中的属性的线性组合。基于线性变换来进行降维的方法称为线性降维方法，对低维子空间性质的不同要求可通过对施加不同的约束来实现。其中是变换矩阵，是样本在新空间中的表达。主成分分析主成分分析(PrincipalComponentAnalysis,简称PCA)对于正交属性空间中的样本点，如何用一个超平面对所有样本进行恰当的表达？容易想到，若存在这样的超平面，那么它大概应具有这样的性质：最近重构性：样本点到这个超平面的距离都足够近；最大可分性：样本点在这个超平面上的投影能尽可能分开。基于最近重构性和最大可分性，能分别得到主成分分析的两种等价推导。主成分分析最近重构性对样本进行中心化，，再假定投影变换后得到的新坐标系为，其中是标准正交基向量，若丢弃新坐标系中的部分坐标，即将维度降低到，则样本点在低维坐标系中的投影是，是在低维坐标下第维的坐标，若基于来重构，则会得到主成分分析最近重构性考虑整个训练集，原样本点与基于投影重构的样本点之间的距离为根据最近重构性应最小化上式。考虑到是标准正交基，是协方差矩阵，有这就是主成分分析的优化目标。主成分分析最大可分性样本点在新空间中超平面上的投影是，若所有样本点的投影能尽可能分开，则应该使得投影后样本点的方差最大化。若投影后样本点的方差是，于是优化目标可写为显然与等价。主成分分析PCA的求解对优化式使用拉格朗日乘子法可得只需对协方差矩阵进行特征值分解，并将求得的特征值排序：，再取前个特征值对应的特征向量构成，这就是主成分分析的解。主成分分析PCA算法主成分分析降维后低维空间的维数通常是由用户事先指定，或通过在值不同的低维空间中对k近邻分类器（或其它开销较小的学习器）进行交叉验证来选取较好的值。对PCA，还可从重构的角度设置一个重构阈值，例如，然后选取使下式成立的最小值：PCA仅需保留与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中。降维虽然会导致信息的损失，但一方面舍弃这些信息后能使得样本的采样密度增大，另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，舍弃可以起到去噪效果。核化线性降维线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而，在不少现实任务中，可能需要非线性映射才能找到恰当的低维嵌入：核化线性降维核化主成分分析(KernelizedPCA,简称KPCA)非线性降维的一种常用方法，是基于核技巧对线性降维方法进行“核化”(kernelized)。假定我们将在高维特征空间中把数据投影到由确定的超平面上，即PCA欲求解其中是样本点在高维特征空间中的像。令，核化线性降维核化主成分分析(KernelizedPCA,简称KPCA)假定是由原始属性空间中的样本点通过映射产生，即若能被显式表达出来，则通过它将样本映射至高维空间，再在特征空间中实施PCA即可，即有并且核化线性降维一般情形下，我们不清楚的具体形式，于是引入核函数又由代入优化式，有上式为特征值分解问题，取最大的个特征值对应的特征向量得到解。核化主成分分析(KernelizedPCA,简称KPCA)其中为对应的核矩阵，核化线性降维对新样本，其投影后的第维坐标为核化主成分分析(KernelizedPCA,简称KPCA)其中已经过规范化，是的第个分量。由该式可知，为获得投影后的坐标，KPCA需对所有样本求和，因此它的计算开销较大。流形学习流形学习(manifoldlearning)是一类借鉴了拓扑流形概念的降维方法。“流形”是在局部与欧氏空间同胚的空间，换言之，它在局部具有欧氏空间的性质，能用欧氏距离来进行距离计算。若低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧氏空间的性质，因此，可以容易地在局部建立降维映射关系，然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示，因此流形学习也可被用于可视化。流形学习等度量映射(IsometricMapping，Isomap)低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上不可达。而低维嵌入流形上两点间的本真距离是“测地线”(geodesic)距离。流形学习等度量映射(IsometricMapping，Isomap)测地线距离的计算：利用流形在局部上与欧氏空间同胚这个性质，对每个点基于欧氏距离找出其近邻点，然后就能建立一个近邻连接图，图种近邻点之间存在连接，而非近邻点之间不存在连接，于是，计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间的最短路径问题。最短路径的计算可通过Dijkstra算法或Floyd算法实现。得到距离后可通过多维缩放方法获得样本点在低维空间中的坐标。流形学习等度量映射(IsometricMapping，Isomap)流形学习局部线性嵌入(LocallyLinearEmbedding，LLE)局部线性嵌入试图保持邻域内的线性关系，并使得该线性关系在降维后的空间中继续保持。流形学习局部线性嵌入(LocallyLinearEmbedding，LLE)LLE先为每个样本找到其近邻下标集合，然后计算出基于的中的样本点对进行线性重构的系数：其中和均为已知，令，有闭式解流形学习局部线性嵌入(LocallyLinearEmbedding，LLE)LLE在低维空间中保持不变，于是对应的低维空间坐标可通过下式求解：令则优化式可重写为右式，并通过特征值分解求解。流形学习局部线性嵌入(LocallyLinearEmbedding，LLE)度量学习研究动机在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。那么，为何不直接尝试“学习”出一个合适的距离度量呢？度量学习欲对距离度量进行学习，必须有一个便于学习的距离度量表达形式。对两个维样本和，它们之间的平方欧氏距离可写为其中表示与在第维上的距离。若假定不同属性的重要性不同，则可引入属性权重，得到其中是一个对角矩阵，，可通过学习确定。度量学习的非对角元素均为零，这意味着坐标轴是正交的，即属性之间无关；但现实问题中往往不是这样，例如考虑西瓜的“重量”和“体积”这两个属性，它们显然是正相关的，其对应的坐标轴不再正交。为此将替换为一个普通的半正定对称矩阵，于是就得到了马氏距离(Mahalanobisdistance)。其中亦称“度量矩阵”，而度量学习则是对进行学习。注意到为了保持距离非负且对称，必须是（半）正定对称矩阵，即必有正交基使得能写为。对进行学习当然要设置一个目标。假定我