知名的建站公司,重庆网络seo,什么企业做网站比较方便呢,软件开发流程怎么写机器学习 第10章-降维与度量学习
10.1 k近邻学习
k近邻(k-Nearest Neighbor,简称kNN)学习是一种常用的监督学习方法其工作机制非常简单:给定测试样本#xff0c;基于某种距离度量找出训练集中与其最靠近的k个训练样本#xff0c;然后基于这k个“邻居”的信息来进行预测。通…机器学习 第10章-降维与度量学习
10.1 k近邻学习
k近邻(k-Nearest Neighbor,简称kNN)学习是一种常用的监督学习方法其工作机制非常简单:给定测试样本基于某种距离度量找出训练集中与其最靠近的k个训练样本然后基于这k个“邻居”的信息来进行预测。通常在分类任务中可使用“投票法”即选择这k个样本中出现最多的类别标记作为预测结果在回归任务中可使用“平均法”即将这k个样本的实值输出标记的平均值作为预测结果还可基于距离远近进行加权平均或加权投票距离越近的样本权重越大。
与前面介绍的学习方法相比k近邻学习有一个明显的不同之处:它似乎没有显式的训练过程!事实上它是“懒惰学习”(lazy learning)的著名代表此类学习技术在训练阶段仅仅是把样本保存起来训练时间开销为零待收到测试样本后再进行处理相应的那些在训练阶段就对样本进行学习处理的方法称为“急切学习”(eager learning)。
图10.1给出了k近邻分类器的一个示意图。显然k是一个重要参数当k取不同值时分类结果会有显著不同。另一方面若采用不同的距离计算方式则找出的“近邻”可能有显著差别从而也会导致分类结果有显著不同。 10.2 低维嵌入
事实上在高维情形下出现的数据样本稀疏、距离计算困难等问题是所有机器学习方法共同面临的严重障碍被称为“维数灾难”(curse of dimensionality)。
缓解维数灾难的一个重要途径是降维(dimensionreduction)亦称“维数约简”即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”(subspace)在这个子空间中样本密度大幅提高距离计算也变得更为容易。为什么能进行降维这是因为在很多时候人们观测或收集到的数据样本虽是高维的但与学习任务密切相关的也许仅是某个低维分布即高维空间中的一个低维“嵌入”(embedding)。图10.2给出了一个直观的例子。原始高维空间中的样本点在这个低维嵌入子空间中更容易进行学习。
假定 m m m个样本在原始空间的距离矩阵为 D ∈ R m ∗ m D\in R^{m*m} D∈Rm∗m其中第 i i i行 j j j列的元素 d i s t i j dist_{ij} distij为样本 x i x_i xi到 x j x_j xj的距离目标是要获取样本在 d ′ {d} d′维空间的表示 Z ∈ R d ′ ∗ m d ′ ≤ d Z\in R^{{d}*m}{d}\leq d Z∈Rd′∗md′≤d且任意两个样本在 d ′ {d} d′维空间中的欧氏距离等于原始空间中的距离即 ∥ z i − z j ∥ d i s t i j \left \| z_i-z_j \right \|dist_{ij} ∥zi−zj∥distij。
令 B Z T Z ∈ R m ∗ m BZ^T Z\in R^{m*m} BZTZ∈Rm∗m其中 B B B为降维后样本的内积矩阵 b i j z i T z j b_{ij}z_i^Tz_j bijziTzj则有 d i s t i j 2 ∣ ∣ z i ∣ ∣ 2 ∣ ∣ z j ∣ ∣ 2 − 2 z i T z j b i i b j j − 2 b i j dist_{ij}^2||z_i||^2||z_j||^2-2z_i^Tz_jb_{ii}b_{jj}-2b_{ij} distij2∣∣zi∣∣2∣∣zj∣∣2−2ziTzjbiibjj−2bij 令降维后的样本 Z Z Z中心化即 ∑ i 1 m z i 0 ∑^m_{i1}z_i0 ∑i1mzi0且矩阵B的行列之和都为0可以得到 ∑ i 1 m d i s t i j 2 t r ( B ) m b j j \sum_{i1}^{m}dist_{ij}^2tr(B)mb_{jj} i1∑mdistij2tr(B)mbjj ∑ j 1 m d i s t i j 2 t r ( B ) m b i i \sum_{j1}^{m}dist_{ij}^2tr(B)mb_{ii} j1∑mdistij2tr(B)mbii ∑ i 1 m ∑ i j m d i s t i j 2 2 m t r ( B ) \sum_{i1}^{m}\sum_{ij}^{m}dist_{ij}^22m\: tr(B) i1∑mij∑mdistij22mtr(B) 联立得 b i j − 1 2 ( d i s t i j 2 − d i s t i ⋅ 2 − d i s t ⋅ j 2 d i s t ⋅ ⋅ 2 ) b_{ij}-\frac{1}{2}(dist_{ij}^2-dist_{i\cdot }^2-dist_{\cdot j}^2dist_{\cdot \cdot }^2) bij−21(distij2−disti⋅2−dist⋅j2dist⋅⋅2)
整个算法描述如下图所示 基于线性变换来进行降维的方法称为线性降维方法和MDS方法不同之处是对低维子空间的性质有不同的要求。
10.3 主成分分析
主成分分析(Principal Component Analysis,简称 PCA)是最常用的一种降维方法。
对于正交属性空间中的样本点如何用一个超平面(直线的高维推广)对所有样本进行恰当的表达 容易想到若存在这样的超平面那么它大概应具有这样的性质: 最近重构性:样本点到这个超平面的距离都足够近 最大可分性:样本点在这个超平面上的投影能尽可能分开
根据最近重构性可以得到 KaTeX parse error: Undefined control sequence: \ at position 20: …derset{W}{min} \̲̲ \ -tr(W^TXX^T… 根据最大可分性可以得到 KaTeX parse error: Undefined control sequence: \ at position 19: …nderset{W}{max}\̲̲ \ \ tr(W^TXX… 显然两式等价对其使用拉格朗日乘子法可得 X X T W λ W XX^TW\lambda W XXTWλW 于是只需对协方差矩阵 X X T XX^T XXT进行特征值分解将求得的特征值排序: λ 1 ≥ λ 2 ≥ 。。。 ≥ λ d λ_1≥λ_2≥。。。≥λ_d λ1≥λ2≥。。。≥λd再取前 d ′ d d′个特征值对应的特征向量构成 W ( w 1 , w 2 , . . . , w d ′ ) W(w_1,w_2,...,w_{d}) W(w1,w2,...,wd′)。这就是主成分分析的解。
PCA 算法描述如图 10.5 所示。
PCA 仅需保留W与样本的均值向量即可通过简单的向量减法和矩阵-向量乘法将新样本投影至低维空间中。显然低维空间与原始高维空间必有不同因为对应于最小的d-d个特征值的特征向量被舍弃了这是降维导致的结果但舍弃这部分信息往往是必要的:一方面舍弃这部分信息之后能使样本的采样密度增大这正是降维的重要动机另一方面当数据受到噪声影响时最小的特征值所对应的特征向量往往与噪声有关将它们舍弃能在一定程度上起到去噪的效果。
10.4 核化线性降维
线性降维方法假设从高维空间到低维空间的函数映射是线性的然而在不少现实任务中可能需要非线性映射才能找到恰当的低维嵌入。图10.6给出了一个例子样本点从二维空间中的矩形区域采样后以S形曲面嵌入到三维空间若直接使用线性降维方法对三维空间观察到的样本点进行降维则将丢失原本的低维结构。为了对“原本采样的”低维空间与降维后的低维空间加以区别我们称前者为“本真”(intrinsic)低维空间。
10.5 流形学习
流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法“流形”是在局部与欧氏空间同胚的空间换言之它在局部具有欧氏空间的性质能用欧氏距离来进行距离计算。这给降维方法带来了很大的启发:若低维流形嵌入到高维空间中则数据样本在高维空间的分布虽然看上去非常复杂但在局部上仍具有欧氏空间的性质因此可以容易地在局部建立降维映射关系然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时能对数据进行可视化展示因此流形学习也可被用于可视化。
10.5.1 等度量映射
等度量映射(Isometric Mapping,简称Isomap)的基本出发点是认为低维流形嵌入到高维空间之后直接在高维空间中计算直线距离具有误导性因为高维空间中的直线距离在低维嵌入流形上是不可达的如图 10.7(a)所示低维嵌入流形上两点间的距离是“测地线”(geodesic)距离想象一只虫子从一点爬到另一点如果它不能脱离曲面行走那么图10.7(a)中的红色曲线是距离最短的路径即S曲面上的测地线测地线距离是两点之间的本真距离。显然直接在高维空间中计算直线距离是不恰当的 在近邻连接图上计算两点间的最短路径可采用著名的Diikstra算法或Floyd 算法在得到任意两点的距离之后就可通过 10.2节介绍的 MDS 方法来获得样本点在低维空间中的坐标。图10.8给出了Isomap 算法描述 Isomap仅是得到了训练样本在低维空间的坐标对于新样本如何将其映射到低维空间呢这个问题的常用解决方案是将训练样本的高维空间坐标作为输入、低维空间坐标作为输出训练一个回归学习器来对新样本的低维空间坐标进行预测这显然仅是一个权宜之计但目前似乎并没有更好的办法。
对近邻图的构建通常有两种做法一种是指定近邻点个数例如欧氏距离最近的 k k k个点为近邻点这样得到的近邻图称为 k k k近邻图另一种是指定距离阈值 ϵ \epsilon ϵ距离小于 ϵ \epsilon ϵ的点被认为是近邻点这样得到的近邻图称为 ϵ \epsilon ϵ近邻图。两种方式均有不足例如若近邻范围指定得较大则距离很远的点可能被误认为近邻这样就出现“短路”问题:近邻范围指定得较小则图中有些区域可能与其他区域不存在连接这样就出现“断路”问题。短路与断路都会给后续的最短路径计算造成误导
10.5.2 局部线性嵌入
与Isomap试图保持近邻样本之间的距离不同局部线性嵌入(LocallyLinear Embedding,简称LLE)试图保持邻域内样本之间的线性关系如图10.9所示假定样本点 x i x_i xi的坐标可以通过它的邻域样本 x j x_j xj x k x_k xk x l x_l xl的坐标通过线性组合来表示即 x i w i j x j w i k x k w i l x l x_iw_{ij}x_jw_{ik}x_kw_{il}x_l xiwijxjwikxkwilxl LLE先为每个样本KaTeX parse error: Expected group after _ at position 2: x_̲找到其近邻下标集合 Q i Q_i Qi然后计算出基于 Q i Q_i Qi中的样本点 x i x_i xi对进行线性重构的系数 w i w_i wi: w i j ∑ k ∈ Q i C j k − 1 ∑ l , s ∈ Q i C l s − 1 w_{ij}\frac{\sum_{k\in Q_i}C_{jk}^{-1}}{\sum _{l,s\in Q_i}C_{ls}^{-1}} wij∑l,s∈QiCls−1∑k∈QiCjk−1 然后去求解低维坐标 Z ( z 1 , z 2 , ⋯ , z m ) ∈ R d ′ ∗ m , ( W ) i j w i j Z(z_1,z_2,\cdots,z_m)\in {R}^{{d}*m},(W)_{ij}w_{ij} Z(z1,z2,⋯,zm)∈Rd′∗m,(W)ijwij M ( I − W ) T ( I − W ) M(I-W)^T(I-W) M(I−W)T(I−W) 最后可以得到 KaTeX parse error: Undefined control sequence: \ at position 19: …nderset{z}{min}\̲̲ \ tr(ZMZ^T)\… LLE 的算法描述如图 10.10所示。
10.6 度量学习
在机器学习中对高维数据进行降维的主要目的是希望找到一个合适的低维空间在此空间中进行学习能比原始空间性能更好。事实上每个空间对应了在样本属性上定义的一个距离度量而寻找合适的空间实质上就是在寻找一个合适的距离度量。那么为何不直接尝试“学习”出一个合适的距离度量呢这就是度量学习(metric learning)的基本动机。
对两个 d d d维样本 x i x_i xi和 x j x_j xj它们之间的平方欧氏距离可写为 d i s t e d 2 ( x i x j ) ∣ ∣ x i − x j ∣ ∣ 2 2 d i s t i j , 1 2 d i s t i j , 2 2 ⋯ d i s t i j , d 2 dist_{ed}^{2}(x_{i}x_{j})||x_{i}-x_{j}||_{2}^{2}dist_{ij,1}^{2}dist_{ij,2}^{2}\cdotsdist_{ij,d}^{2} disted2(xixj)∣∣xi−xj∣∣22distij,12distij,22⋯distij,d2
其中 d i s t i j , k dist_{ij,k} distij,k表示 x i x_i xi与 x j x_j xj在第k维上的距离。若假定不同属性的重要性不同则可引入属性权重 w w w得到: d i s t w e d 2 ( x i x j ) ∣ ∣ x i − x j ∣ ∣ 2 2 w 1 ⋅ d i s t i j , 1 2 w 2 ⋅ d i s t i j , 2 2 ⋯ w d ⋅ d i s t i j , d 2 ( x i − x j ) T W ( x i − x j ) dist_{wed}^{2}(x_{i}x_{j})||x_{i}-x_{j}||_{2}^{2}w_{1}\cdot dist_{ij,1}^{2}w_{2}\cdot dist_{ij,2}^{2}\cdotsw_{d}\cdot dist_{ij,d}^{2} (x_{i}-x_{j})^{T}W(x_{i}-x_{j}) distwed2(xixj)∣∣xi−xj∣∣22w1⋅distij,12w2⋅distij,22⋯wd⋅distij,d2(xi−xj)TW(xi−xj) 其中 w i ≥ 0 w_i≥0 wi≥0 W d i a g ( w ) Wdiag(w) Wdiag(w)是一个对角矩阵 ( W ) i i w i (W)iiw_i (W)iiwi。
式(1033)中的 W W W可通过学习确定但我们还能再往前走一步: W W W的非对角元素均为零这意味着坐标轴是正交的即属性之间无关但现实问题中往往不是这样例如考虑西瓜的“重量”和“体积”这两个属性它们显然是正相关的其对应的坐标轴不再正交。为此将式(1033)中的 W W W替换为一个普通的半正定对称矩阵 M M M于是就得到了马氏距离(Mahalanobis distance) d i s t m a h 2 ( x i x j ) ( x i − x j ) T M ( x i − x j ) ∣ ∣ x i − x j ∣ ∣ M 2 dist_{mah}^{2}(x_{i}x_{j})(x_{i}-x_{j})^{T}M(x_{i}-x_{j})||x_{i}-x_{j}||_{M}^{2} distmah2(xixj)(xi−xj)TM(xi−xj)∣∣xi−xj∣∣M2 其中 M M M亦称“度量矩阵”而度量学习则是对 M M M进行学习。注意到为了保持距离非负且对称 M M M必须是(半)正定对称矩阵即必有正交基 P P P使得 M M M能写为 M P P T MPP^T MPPT
对M进行学习当然要设置一个目标。假定我们是希望提高近邻分类器的性能则可将M直接嵌入到近邻分类器的评价指标中去通过优化该性能指标相应地求得M。
