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

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