机器学习与人工神经网络作业..doc

流行学习方法 1.1 流形及流形学习的基本概念 1.1.1 流形的概念 青年数学家刘克峰在“物理激发的数学”系列演讲中提到，流形的英文翻译为“manifold”，中文“流形”一词取自于文天祥的著名诗句：“天地有正气，杂然赋流形，下则为河岳，上则为日星”。数学上，流形意指表面局部平坦的物体。流形就是在足够小的邻域是线性的，即分布在高维观测空间中具有低维自由度的嵌入空间。这种描述是基于认为在小邻域中数据的分布都是线性的假设，即在一个小邻域内可以用欧式空间的特性来描述流形。流形是微分几何中的一个基本概念，在 1854 年由德国数学家黎曼的论文《论几何学的基本假设》中提出，其定义为： 设 是一个Hausdorff拓扑空间，若对每一点 都有 的一个开邻域 和 的一个开子集同胚, 则称 为 维拓扑流形, 简称为 维流形. 流形是线性子空间的一种非线性推广； 拓扑学角度：局部区域线性，与低维欧式空间拓扑同胚； 微分几何角度：有重叠chart的光滑过渡； 黎曼流形就是以光滑的方式在每一点的切空间上指定了欧氏内积的微分流形 下图1-1给出了流形在欧式空间的几种形状： 图1-1 流行的几种直观图例 1.1.2 流形学习的定义 Tenenbaum J.B.等人在2002年NIPS会议上的发言，明确提出流形学习的概念，定义为：假设 是一个低维流形， 是一个光滑的嵌入，其中 。流形学习就是对于 上的一个给定被观察数据集合{ }的条件下恢复与 。数据集 { } 是随机地产生的，然后被 f 映射为观察空间的数据{ }。 流形学习就是从高维采样数据中恢复低维流形结构，即找到高维空间中的低维流形，并求出相应的嵌入映射，实现维数约简或者数据可视化。它是从观测到的现象中去寻找事物的本质，找到数据集的内在规律。 1.1.3 流形学习问题的数学描述 一个流形就是一个在局部空间上是欧氏的拓扑空间。流形学习本身是一类无监督学习问题，在降维能力上有着较好的优势，其主要目标是寻找观测数据嵌入在高维空间的低维流形。 问题的数学描述：假设为嵌入在维欧氏空间中的维流形， ，，这里 为上的紧致连接开子集。 对于给定的高维数据集 ={} ，其中，服从某种潜在分布。 这里 ={}，其中，表示独立噪声。 流形学习的目标是根据观测数据集重构未知函数 和，对于任意的，可以用 估计。 在流形学习中，必须在 上加一些限制条件，才能寻找出观察变量 和隐变量 的联系。例如 ISOMAP 算法就是用等距映射来限制的，也有些地方是用保形映射作为 的限制条件。 流形学习的直观图如下图1-2所示： 图1-2 流形学习直观图 2等距特征映射 2.1等距特征映射概念 等距特征映射（Isometric feature mapping,ISOMAP）是 Joshua B. Tenenbaum提出的一种数据处理的新算法，是一种在经典多维尺度变换（MDS）基础之上的全局优化算法。多维尺度分析（MDS）是根据数据间的相异度（可以为距离）寻找数据在低维空间中的近似，并尽可能地保持观测数据之间的相似性关系。但是 MDS 保留的是直线距离，所以只能发现线性结构，Tenenbaum 等提出的ISOMAP 算法用测地线距离取代了 MDS 算法中传统的欧氏距离来表示数据间的距离，再使用 MDS 算法把数据点从高维空间映射到低维空间中，获得保持样本间内在结构不变的低维流形，即各样本的低维嵌入坐标。 ISOMAP有效的前提假设有两个：一是高维数据所在的低维流形与欧氏空间的一个子集是整体等距的，即光滑流形与其参数空间的子集之间存在等距离映射。二是与数据所在的流形等距的欧氏空间的子集是一个凸集。虽然进行了一定的前提假设，但是ISOMAP的有效性在人工合成数据和自然图像的实验中己经得到验证。 ISOMAP算法中需要两个参数：一个是邻域的大小，一个是降维的维数。降维维数的确定通常是在本质维数未知的情况下进行的，经多次实验绘制残差曲线观察得到。 ISOMAP算法的关键是利用样本向量之间的欧氏距离 。首先计算出样本之间的测地距离，真实地再现高维数据内在的非线性几何结构，然后使用经典多维尺度分析算法构造一个新的维空间(是降维后空间的维数)，最大限度地保持样本之间的欧式距离 与 误差最小。进而发现嵌入在高维空间的低维坐标，以达到降维的目的。 2.2 ISOMAP算法流程 计算每个点的近邻点 (用K近邻或 邻域)。 在样本集上定义一个赋权无向图，如果 和 互为近邻点, 则边的权值为。 计算图中两点间的最短距离, 记所得的距离矩阵为。 用MDS求低维嵌入坐标 ， 令 低维嵌入是的第1大到第 d大的特征