machine learning and data mining 2006 主成分分析( pca ) - read.pptVIP

机器学习研究第六讲：流形学习 杨 剑 维数约简 局部线性嵌入(LLE) 前提假设：采样数据所在的低维流形在局部是线性的，即每个采样点可以用它的近邻点线性表示. 学习目标：在低维空间中保持每个邻域中的权值不变，即假设嵌入映射在局部是线性的条件下, 最小化重构误差. 求解方法：特征值分解. LLE算法 1 计算每一个点 的近邻点, 一般采用K 近邻或者 邻域. 2 计算权值 使得把 用它的K个近邻点线性表示 的误差最小, 即通过最小化 来求出 . 3 保持权值 不变, 求 在低维空间的象 , 使 得低维重构误差最小. LLE算法示意图 LLE算法的求解 1计算每一个点 的近邻点. 2 对于点 和它的近邻点的权值 , 3 令 , 低维嵌入 是 M 的最小的第 2到第 d＋1 个特征值对应的特征向量. LLE算法的例子(1) LLE算法的例子(2) LLE算法的优点 LLE算法可以学习任意维数的低维流形. LLE算法中的待定参数很少, K 和 d. LLE算法中每个点的近邻权值在平移, 旋转,伸缩变换下是保持不变的. LLE算法有解析的整体最优解,不需迭代. LLE算法归结为稀疏矩阵特征值计算, 计算复杂度相对较小, 容易执行. LLE算法的缺点 LLE算法要求所学习的流形只能是不闭合的且在局部是线性的. LLE算法要求样本在流形上是稠密采样的. LLE算法中的参数 K, d 有过多的选择. LLE算法对样本中的噪音比较敏感. R 多维标度 (MDS) MDS 是一种非监督的维数约简方法. MDS的基本思想: 约简后低维空间中任意两点间的距离 应该与它们在原高维空间中的距离相同. MDS的求解: 通过适当定义准则函数来体现在低维空间 中对高维距离的重建误差, 对准则函数用梯度下降法求解, 对于某些特殊的距离可以推导出解析解法. MDS的准则函数 MDS的示意图 MDS的失效 建立在多维尺度变换(MDS)的基础上, 力求保持 数据点的内在几何性质, 即保持两点间的测地距离. 等距映射(Isomap)的基本思想 Isomap的前提假设 高维数据所在的低维流形与欧氏空间的一个子 集是整体等距的. 与数据所在的流形等距的欧氏空间的子集是一 个凸集. 估计两点间的测地距离: 1 离得很近的点间的测地距离用欧氏距离代替. 2 离得较远的点间的测地距离用最短路径来逼近. Isomap算法的核心 中国科学院自动化研究所 Machine Learning and Data Mining 2006 中国科学院自动化研究所 Machine Learning and Data Mining 2006 中国科学院研究生院 2006年6月 维数约简 增加特征数 增加信息量 提高准确性 增加训练分类器的难度 维数灾难 解决办法：选取尽可能多的, 可能有用的特征, 然后根据需要进行特征约简. 特征选择 维数约简 依据某一标准选择性质最突出的特征 经已有特征的某种变换获取约简特征 试验数据分析，数据可视化（通常为2维或3维）等都需要维数约简 特征抽取 线性维数约简方法: PCA, MDA. 流形和维数约简. 流形学习的一些数学基础. 几种流形学习算法简介：LLE, Isomap, LSTA. 流形学习问题的简单探讨. Outline 线性约简方法 通过特征的线性组合来降维. 本质上是把数据投影到低维线性子空间. 线性方法相对比较简单且容易计算. 两种经典的寻找有效的线性变换的方法: 主成分分析 (PCA); 多重判别分析 (MDA). 主成分分析 ( PCA ) 目的：寻找能够表示采样数据的最好的投影子空间. 求解：对样本的散布矩阵进行特征值分解, 所求子空间为过样本均值, 以最大特征值所对应的特征向量为方向的子空间. Principal component 主成分分析 PCA对于椭球状分布的样本集有很好的效果, 学习所得的主方向就是椭球的主轴方向. PCA 是一种非监督的算法, 能找到很好地代表所有样本的方向, 但这个方向对于分类未必是最有利的. 线性判别分析(LDA)1 LDA是一种监督的维数约简方法. 思想: 寻找最能把两类样本分开的投影直线. 目标: 使投影后两类样本的均值之差与投影样本的总类散布的比值最