成都建站,wordpress修改前缀,网站主页设计优点,一般做外单的有哪些网站1. 维数灾难
样本的特征数称为维数#xff08;dimensionality#xff09;#xff0c;当维数非常大时#xff0c;也就是现在所说的维数灾难。 维数灾难具体表现在#xff1a;在高维情形下#xff0c;数据样本将变得十分稀疏#xff0c;因为此时要满足训练样本为“密采样…1. 维数灾难
样本的特征数称为维数dimensionality当维数非常大时也就是现在所说的维数灾难。 维数灾难具体表现在在高维情形下数据样本将变得十分稀疏因为此时要满足训练样本为“密采样”的总体样本数目是一个触不可及的天文数字训练样本的稀疏使得其代表总体分布的能力大大减弱从而消减了学习器的泛化能力同时当维数很高时计算距离也变得十分复杂甚至连计算内积都不再容易这也是为什么支持向量机SVM使用核函数低维计算高维表现的原因。
缓解维数灾难的一个重要途径就是降维即通过某种数学变换将原始高维空间转变到一个低维的子空间。 在这个子空间中样本的密度将大幅提高同时距离计算也变得容易。这时也许会有疑问这样降维之后不是会丢失原始数据的一部分信息吗这是因为在很多实际的问题中虽然训练数据是高维的但是与学习任务相关也许仅仅是其中的一个低维子空间也称为一个低维嵌入例如数据属性中存在噪声属性、相似属性或冗余属性等对高维数据进行降维能在一定程度上达到提炼低维优质属性或降噪的效果。
2. K近邻学习kNN
k近邻算法简称kNNk-Nearest Neighbor是一种经典的监督学习方法数据挖掘十大算法之一。
工作机制非常简单:给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测。
通常,在分类任务中可使用“投票法”,即选择这k个样本中出现最多的类别标记作为预测结果;
在回归任务中可使用“平均法”,即将这k个样本的实值输出标记的平均值作为预测结果;还可基于距离远近进行加权平均或加权投票,距离越近的样本权重越大.
2.1 分析 从上图中我们可以看到图中有两种类型的样本一类是蓝色正方形另一类是红色三角形。而那个绿色圆形是我们待分类的样本。基于kNN算法的思路我们很容易得到以下结论 如果K3那么离绿色点最近的有2个红色三角形和1个蓝色的正方形这3个点投票于是绿色的这个待分类点属于红色的三角形。 如果K5那么离绿色点最近的有2个红色三角形和3个蓝色的正方形这5个点投票于是绿色的这个待分类点属于蓝色的正方形。 与前面介绍的学习方法相比, k近邻学习有一个明显的不同之处: 它似乎没有显式的训练过程! 事实上,它是“懒情学习” (lazy learning)的著名代表, 此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为零, 待收到测试样本后再进行处理因此朴素贝叶斯也可以懒惰式学习此类技术在训练阶段开销为零待收到测试样本后再进行计算。; 相应的,那些在训练阶段就对样本进行学习处理的方法, 称为“急切学习” (eager learning).
很容易看出kNN算法的核心在于k值的选取以及距离的度量。k值选取太小模型很容易受到噪声数据的干扰例如极端地取k1若待分类样本正好与一个噪声数据距离最近就导致了分类错误若k值太大 则在更大的邻域内进行投票此时模型的预测能力大大减弱例如极端取k训练样本数就相当于模型根本没有学习所有测试样本的预测结果都是一样的。一般地我们都通过交叉验证法简单来说就是一部分样本做训练集一部分做测试集来选取一个适当的k值。 对于距离度量不同的度量方法得到的k个近邻不尽相同从而对最终的投票结果产生了影响因此选择一个合适的距离度量方法也十分重要。在上一篇聚类算法中在度量样本相似性时介绍了常用的几种距离计算方法包括闵可夫斯基距离曼哈顿距离VDM等距离度量方法总结可参考博客。在实际应用中kNN的距离度量函数一般根据样本的特性来选择合适的距离度量同时应对数据进行去量纲/归一化处理来消除大量纲属性的强权政治影响。
2.2 KNN最近邻分类算法的过程
计算测试样本和训练样本中每个样本点的距离常见的距离度量有欧式距离马氏距离等对上面所有的距离值进行排序选前 k 个最小距离的样本根据这 k 个样本的标签进行投票得到最后的分类类别
3. MDS算法
不管是使用核函数升维还是对数据降维我们都希望原始空间样本点之间的距离在新空间中基本保持不变这样才不会使得原始空间样本之间的关系及总体分布发生较大的改变。**“多维缩放”Multiple Dimensional ScalingMDS**正是基于这样的思想MDS要求原始空间样本之间的距离在降维后的低维空间中得以保持。 令降维后的样本坐标矩阵Z被中心化中心化是指将每个样本向量减去整个样本集的均值向量故所有样本向量求和得到一个零向量即 这样易知矩阵B的每一列以及每一列求和均为0因为提取公因子后都有一项为所有样本向量的和向量。 根据上面矩阵B的特征我们很容易得到以下等式 MDS的算法流程如下图所示
4. 主成分分析PCA
该部分可参考博客。
主成分分析(Principal Component Analysis,简称 PCA)是最常用的一种降维方法。不同于MDS采用距离保持的方法主成分分析PCA直接通过一个线性变换将原始空间中的样本投影到新的低维空间中。简单来理解这一过程便是PCA采用一组新的基来表示样本点其中每一个基向量都是原来基向量的线性组合通过使用尽可能少的新基向量来表出样本从而达到降维的目的。
在介绍PCA之前,不妨先考虑这样一个问题:对于正交属性空间中的样本点,如何用一个超平面(直线的高维推广)对所有样本进行恰当的表达? 容易想到,若存在这样的超平面,那么它大概应具有这样的性质: 最近重构性:样本点到这个超平面的距离都足够近; 最大可分性:样本点在这个超平面上的投影能尽可能分开.
这里十分神奇的是最近重构性与最大可分性虽然从不同的出发点来定义优化问题中的目标函数但最终这两种特性得到了完全相同的优化问题 接着使用拉格朗日乘子法求解上面的优化问题得到 因此只需对协方差矩阵进行特征值分解即可求解出WPCA算法的整个流程如下图所示 5. 核化线性降维
线性降维方法假设从高维空间到低维空间的函数映射是线性的,然而,在不少现实任务中,可能需要非线性映射才能找到恰当的低维嵌入,图10.6给出了一个例子,样本点从二维空间中的矩形区域采样后以S形曲面嵌入到三维空间,若直接使用线性降维方法对三维空间观察到的样本点进行降维,则将丢失原本的低维结构,为了对“原本采样的”低维空间与降维后的低维空间加以区别,我们称前者为“本真”(intrinsic)低维空间。 正如SVM在处理非线性可分时通过引入核函数将样本投影到高维特征空间接着在高维空间再对样本点使用超平面划分。这里也是相同的问题若我们的样本数据点本身就不是线性分布那还如何使用一个超平面去近似表出呢因此也就引入了核函数即先将样本映射到高维空间再在高维空间中使用线性降维的方法。下面主要介绍**核化主成分分KPCA**的思想。
5.1 基本思想
若核函数的形式已知即我们知道如何将低维的坐标变换为高维坐标这时我们只需先将数据映射到高维特征空间再在高维空间中运用PCA即可。但是一般情况下我们并不知道核函数具体的映射规则例如Sigmoid、高斯核等我们只知道如何计算高维空间中的样本内积这时就引出了KPCA的一个重要创新之处即空间中的任一向量都可以由该空间中的所有样本线性表示。 6. 流形学习
流形学习manifold learning是一种借助拓扑流形概念的降维方法流形是指在局部与欧式空间同胚的空间即在局部与欧式空间具有相同的性质能用欧氏距离计算样本之间的距离。这样即使高维空间的分布十分复杂但是在局部上依然满足欧式空间的性质基于流形学习的降维正是这种**“邻域保持”的思想。其中等度量映射Isomap试图在降维前后保持邻域内样本之间的距离而局部线性嵌入LLE则是保持邻域内样本之间的线性关系**下面将分别对这两种著名的流行学习方法进行介绍。
6.1 等度量映射Isomap
等度量映射(Isometric Mapping, 简称 Isomap) 的基本出发点是认为低维流形嵌入到高维空间之后,直接在高维空间中计算直线距离具有误导性,因为高维空间中的直线距离在低维嵌入流形上是不可达的。
如图10.7(a)所示,低维嵌入流形上两点间的距离是“测地线”(geodesic)距离: 想象一只虫子从一点爬到另一点,如果它不能脱离曲面行走,那么图10.7(a)中的红色曲线是距离最短的路径,即S曲面上的测地线,测地线距离是两点之间的本真距离,显然,直接在高维空间中计算直线距离是不恰当的.
利用流形在局部上与欧式空间同胚的性质可以使用近邻距离来逼近测地线距离**即对于一个样本点它与近邻内的样本点之间是可达的且距离使用欧式距离计算这样整个样本空间就形成了一张近邻图高维空间中两个样本之间的距离就转为最短路径问题。可采用著名的Dijkstra算法或Floyd算法计算最短距离得到高维空间中任意两点之间的距离后便可以使用MDS算法来其计算低维空间中的坐标。
从MDS算法的描述中我们可以知道MDS先求出了低维空间的内积矩阵B接着使用特征值分解计算出了样本在低维空间中的坐标但是并没有给出通用的投影向量w因此对于需要降维的新样本无从下手书中给出的权宜之计是是将训练样本的高维空间坐标作为输入、低维空间坐标作为输出,训练一个回归学习器来对新样本的低维空间坐标进行预测。
Isomap算法流程如下图
对近邻图的构建通常有两种做法,一种是指定近邻点个数,例如欧氏距离最近的k个点为近邻点,这样得到的近邻图称为k近邻图另一种是指定距离阈值 ϵ ϵ ϵ距离小于 阈值 ϵ 阈值ϵ 阈值ϵ的点被认为是近邻点,这样得到的近邻图称为 ϵ ϵ ϵϵ ϵϵ近邻图。
两种方式均有不足 若邻域范围指定过大则会造成“短路问题”即本身距离很远却成了近邻将距离近的那些样本扼杀在摇篮。 若邻域范围指定过小则会造成“断路问题”即有些样本点无法可达了整个世界村被划分为互不可达的小部落。 6.2 局部线性嵌入(LLE)
与Isomap试图保持近邻样本之间的距离不同,局部线性嵌入(Locally Linear Embedding, 简称LLE) 试图保持邻域内样本之间的线性关系.如图10.9所示,假定样本点 x j , x k , x l x i x j , x k , x l xi xj,xk,xlxi的坐标能通过它的邻域样本 x j , x k , x l x j , x k , x l x j , x k , x l xj,xk,xl xj,xk,xlxj,xk,xl的坐标通过线性组合而重构出来,即 7. 度量学习
在机器学习中,对高维数据进行降维的主要目的是希望找到一个合适的低维空间,在此空间中进行学习能比原始空间性能更好,事实上,每个空间对应了在样本属性上定义的一个距离度量,而寻找合适的空间,实质上就是在寻找一个合适的距离度量,那么,为何不直接尝试“学习”出一个合适的距离度量呢?这就是度量学习(metric learning)的基本动机.
首先要学习出距离度量必须先定义一个合适的距离度量形式。对两个样本 x i x i xi xi xixi与 x j x j xj xj xjxj它们之间的平方欧式距离为
若各个属性重要程度不一样即都有一个权重则得到加权的平方欧式距离 此时各个属性之间都是相互独立无关的但现实中往往会存在属性之间有关联的情形例如身高和体重一般人越高体重也会重一些他们之间存在较大的相关性。这样计算距离就不能分属性单独计算于是就引入经典的马氏距离(Mahalanobis distance): 标准的马氏距离中M是协方差矩阵的逆马氏距离是一种考虑属性之间相关性且尺度无关即无须去量纲的距离度量。 换句话说度量学习便是对度量矩阵进行学习。
现在来回想一下前面我们接触的机器学习不难发现机器学习算法几乎都是在优化目标函数从而求解目标函数中的参数。同样对于度量学习也需要设置一个优化目标书中简要介绍了错误率和相似性两种优化目标此处不再展开。
降维是将原高维空间嵌入到一个合适的低维子空间中接着在低维空间中进行学习任务
度量学习则是试图去学习出一个距离度量来等效降维的效果两者都是为了解决维数灾难带来的诸多问题。
