降维与度量学习
螺杆启闭机
样本的特征数称为维数（dimensionality），当维数⾮常⼤时，也就是现在所说的“维数灾难”，具体表现在：在⾼维情形下，数据样本将变得⼗分稀疏，因为此时要满⾜训练样本为“密采样”的总体样本数⽬是⼀个触不可及的天⽂数字，谓可远观⽽不可亵玩焉…训练样本的稀疏使得其代表总体分布的能⼒⼤⼤减弱，从⽽消减了学习器的泛化能⼒；同时当维数很⾼时，计算距离也变得⼗分复杂，甚⾄连计算内积都不再容易，这也是为什么⽀持向量机（SVM）使⽤核函数“低维计算，⾼维表现”的原因。缓解维数灾难的⼀个重要途径就是降维，即通过某种数学变换将原始⾼维空间转变到⼀个低维的⼦空间。在这个⼦空间中，样本的密度将⼤幅提⾼，同时距离计算也变得容易。这时也许会有疑问，这样降维之后不是会丢失原始数据的⼀部分信息吗？这是因为在很多实际的问题中，虽然训练数据是⾼维的，但是与学习任务相关也许仅仅是其中的⼀个低维⼦空间，也称为⼀个低维嵌⼊，例如：数据属性中存在噪声属性、相似属性或冗余属性等，对⾼维数据进⾏降维能在⼀定程度上达到提炼低维优质属性或降噪的效果。 K近邻学习
k近邻算法简称kNN（k-Nearest Neighbor），是⼀种经典的监督学习⽅法，同时也实⼒担当⼊选数据挖掘⼗⼤算法。其⼯作机制⼗分简单粗暴：给定某个测试样本，kNN基于某种距离度量在训练集中出与其距离最近的k个带有真实标记的训练样本，然后给基于这k个邻居的真实标记来进⾏预测，类似于前⾯集成学习中所讲到的基学习器结合策略：分类任务采⽤投票法，回归任务则采⽤平均法。接下来本篇主要就kNN分类进⾏讨论。
从上图【来⾃Wiki】中我们可以看到，图中有两种类型的样本，⼀类是蓝⾊正⽅形，另⼀类是红⾊三⾓形。⽽那个绿⾊圆形是我们待分类的样本。基于kNN算法的思路，我们很容易得到以下结论：
如果K=3，那么离绿⾊点最近的有2个红⾊三⾓形和1个蓝⾊的正⽅形，这3个点投票，于是绿⾊的这个待分类点属于红⾊的三⾓形。
如果K=5，那么离绿⾊点最近的有2个红⾊三⾓形和3个蓝⾊的正⽅形，这5个点投票，于是绿⾊的这个待分类点属于蓝⾊的正⽅形。
awc可以发现：kNN虽然是⼀种监督学习⽅法，但是它却没有显式的训练过程，⽽是当有新样本需要预测时，才来计算出最近的k个邻居，因此kNN是⼀种典型的懒惰学习⽅法，再来回想⼀下朴素贝叶斯的流程，训练的过程就是参数估计，因此朴素贝叶斯也可以懒惰式学习，此类技术在训练阶段开销为零，待收到测试样本后再进⾏计算。相应地我们称那些⼀有训练数据⽴马开⼯的算法为“急切学习”，可见
前⾯我们学习的⼤部分算法都归属于急切学习。
很容易看出：kNN算法的核⼼在于k值的选取以及距离的度量。k值选取太⼩，模型很容易受到噪声数据的⼲扰，例如：极端地取k=1，若待分类样本正好与⼀个噪声数据距离最近，就导致了分类错误；若k值太⼤， 则在更⼤的邻域内进⾏投票，此时模型的预测能⼒⼤⼤减弱，例如：极端取k=训练样本数，就相当于模型根本没有学习，所有测试样本的预测结果都是⼀样的。⼀般地我们都通过交叉验证法来选取⼀个适当的k值。
对于距离度量，不同的度量⽅法得到的k个近邻不尽相同，从⽽对最终的投票结果产⽣了影响，因此选
悬臂梁挠度计算公式择⼀个合适的距离度量⽅法也⼗分重要。在上⼀篇聚类算法中，在度量样本相似性时介绍了常⽤的⼏种距离计算⽅法，包括闵可夫斯基距离，曼哈顿距离，VDM等。在实际应⽤中，kNN的距离度量函数⼀般根据样本的特性来选择合适的距离度量，同时应对数据进⾏去量纲/归⼀化处理来消除⼤量纲属性的强权政治影响。
MDS 算法
不管是使⽤核函数升维还是对数据降维，我们都希望原始空间样本点之间的距离在新空间中基本保持不变，这样才不会使得原始空间样本之间的关系及总体分布发⽣较⼤的改变。**“多维缩放”（MDS）**正是基于这样的思想，MDS要求原始空间样本之间的距离在降维后的低维空间中得以保持。
假定m个样本在原始空间中任意两两样本之间的距离矩阵为，我们的⽬标便是获得样本在低维空间中的表⽰，且任意两个样本在低维空间中的欧式距离等于原始空间中的距离，即。因此接下来我们要做的就是根据
已有的距离矩阵D来求解出降维后的坐标矩阵Z。
令降维后的样本坐标矩阵Z被中⼼化，中⼼化是指将每个样本向量减去整个样本集的均值向量，故所有样本向量求和得到⼀个零向量。这样
易知：矩阵B的每⼀列以及每⼀列求和均为0，因为提取公因⼦后都有⼀项为所有样本向量的和向量。
第三方物流方案设计
根据上⾯矩阵B的特征，我们很容易得到下⾯等式：
D ∈R (m ∗m )Z ∈R (d ’∗m ,d ’<d )∣∣z −i z ∣∣=j Dist (ij )
由此可通过降维前后保持不变的距离矩阵求取内积矩阵 ，即，再逐⼀地计算每个，就得到了降维后低维空间中的内积矩阵，只需对进⾏特征值分解便可以得到
。MDS的算法流程如下图所⽰：主成分分析（PCA ）
D B b =ij −(dist −21ij 2dist −i ⋅2dist −⋅j 2dist )⋅⋅2
b (ij )B (B =Z ’∗Z )B Z
不同于MDS采⽤距离保持的⽅法，主成分分析（PCA）直接通过⼀个线性变换，将原始空间中的样本
投影到新的低维空间中。简单来理解这⼀过程便是：PCA采⽤⼀组新的基来表⽰样本点，其中每⼀个基向量都是原来基向量的线性组合，通过使⽤尽可能少的新基向量来表出样本，从⽽达到降维的⽬的。
d’d’
假设使⽤个新基向量来表⽰原来样本，实质上是将样本投影到⼀个由个基向量确定的⼀个超平⾯上（即舍弃了⼀些维度），要⽤⼀个超平⾯对空间中所有⾼维样本进⾏恰当的表达，最理想的情形是：若这些样本点都能在超平⾯上表出且这些表出在超平⾯上都能够很好地分散开来。但是⼀般使⽤较原空间低⼀些维度的超平⾯来做到这两点⼗分不容易，因此我们退⼀步海阔天空，要求这个超平⾯应具有如下两个性质：
最近重构性：样本点到超平⾯的距离⾜够近，即尽可能在超平⾯附近；
最⼤可分性：样本点在超平⾯上的投影尽可能地分散开来，即投影后的坐标具有区分性。
这⾥⼗分神奇的是：最近重构性与最⼤可分性虽然从不同的出发点来定义优化问题中的⽬标函数，但最终这两种特性得到了完全相同的优化
问题：
接着使⽤拉格朗⽇乘⼦法求解上⾯的优化问题，得到：
钢制压力容器因此只需对协⽅差矩阵进⾏特征值分解即可求解出W，PCA算法的整个流程如下图所⽰：
另⼀篇博客给出更通俗更详细的理解：主成分分析解析
核化线性降维
说起机器学习你中有我/我中有你/⽔乳相融…在这⾥能够得到很好的体现。正如SVM在处理⾮线性可分时，通过引⼊核函数将样本投影到⾼维特征空间，接着在⾼维空间再对样本点使⽤超平⾯划分。这⾥也是相同的问题：若我们的样本数据点本⾝就不是线性分布，那还如何使⽤⼀个超平⾯去近似表出呢？因此也就引⼊了核函数，即先将样本映射到⾼维空间，再在⾼维空间中使⽤线性降维的⽅法。下⾯主要介绍核化主成分分析（KPCA) 的思想。
sis 6326若核函数的形式已知，即我们知道如何将低维的坐标变换为⾼维坐标，这时我们只需先将数据映射到⾼维特征空间，再在⾼维空间中运⽤PCA即可。但是⼀般情况下，我们并不知道核函数具体的映射规则，例如：Sigmoid、⾼斯核等，我们只知道如何计算⾼维空间中的样本内
积，这时就引出了KPCA的⼀个重要创新之处：即空间中的任⼀向量，都可以由该空间中的所有样本线性表⽰。证明过程也⼗分简单：这样我们便可以将⾼维特征空间中的投影向量
使⽤所有⾼维样本点线性表出，接着代⼊PCA的求解问题，得到：
化简到最后⼀步，发现结果⼗分的美妙，只需对核矩阵K进⾏特征分解，便可以得出投影向量对应的系数向量α，因此选取特征值前⼤对应的特征向量便是个系数向量。这时对于需要降维的样本点，只需按照以下步骤便可以求出其降维后的坐标。可以看出：KPCA在计算
降维后的坐标表⽰时，需要与所有样本点计算核函数值并求和，因此该算法的计算开销⼗分⼤。流形学习
流形学习（manifold learning）是⼀种借助拓扑流形概念的降维⽅法，流形是指在局部与欧式空间同胚的空间，即在局部与欧式空间具有相同的性质，能⽤欧⽒距离计算样本之间的距离。这样即使⾼维空间的分布⼗分复杂，但是在局部上依然满⾜欧式空间的性质，基于流形学习的降维正是这种“邻域保持”的思想。其中等度量映射（Isomap）试图在降维前后保持邻域内样本之间的距离，⽽局部线性嵌⼊（LLE）则是保持邻域内样本之间的线性关系，下⾯将分别对这两种著名的流⾏学习⽅法进⾏介绍。
等度量映射（Isomap）w i w i d ′
d ′
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议