Manifold Learning

2020-03-01 129浏览

1.流形学习 Manifold Learn ing 小组成员学号： 51174500083 姓名：丁雨琦学号： 51174500052 姓名：吴盈娇学号： 51174500125 姓名：孙阳学号： 51174500100 姓名：李衡学号： 51174500053 姓名：闫倩倩 Date ： 2018-04-11
2.Introduction 闫倩倩 51174500053
3.降维数据降维、参数降维、特征降维数据降维，一般说的是维数约简（ Dimensionality reduction ）。它的思路是：将原始高维特征空间里的点向一个低维空间投影，新的空间维度低于原特征空间，所以维数减少了。在这个这这程中，特征这这这这这这这生了根本性的这这这这这这这化，原始的特征这这这这这这消失了（虽然新的特征也保持了原特征的一些性质）。什么叫高维数据呢？给定一个数据 x ，我们可以把这个数据看作一个向量，这个向量的每个分量都表示这个向量的某一个属性。
4.降维机器学习领域中所谓的降维就是指采用某种映射方法，将高维空间中的数据点映射到低维度的空间中。降维的本质是学习一个映射函数f:x->y ，其中 x 是原始数据点的表达，目前最多使用向量表达形式。 Y 是数据点映射后的低维向量表达，通常 y 的维度小于 x 的维度。 F 可能是显式的或隐式的、线性的或非线性的。
5.为什么需要降维？ 1. 数据集太大，加速后续计算速度。 2. 不相这数据、这这这这这这信息、噪音数据（高这这这这这这这这这这空这这有冗余，低这这这这这这空间没冗余），提高识别的精度。 3. 将高维数据映射回低维空间中，揭示其本质。 4. 实现数据可视化。
6.降维方法分为线性降维和非线性降维，非线性降维又分为基于核函数和基于特征值的方法（流形学习）。
7.线性降维方法主成分分析算法 PCA ： Principal Component Analysis(PCA) 是最常用的线性降维方法，它的目标是通过某种线性投影，将高维的数据映射到低维的空间中表示，并期望在所投影的维度上数据的方差最大，以此使用较少的数据维度，同时保留住较多的原数据点的特性。
8.线性降维方法例如天气”，它由很多子属性构成——温度、湿度、降水量、能见度、风力、阳光强度、舒适度等等，于是这样一个简单的天气数据向量就包含了以上七个分量，是一个七维数据！就算是不了解数据分析的读者也可以看出，这个天气数据的七个分量之间存在着暧昧不清的关系，比如湿度”必然和降水量”有关，舒适度”和前面几个分量都有关。那么能不能把湿度”和降水量”结合成一个新的分量？能不能把舒适度”用其他分量表示？这就是数据的降维，也是主成分分析的基本思想，形成的新分量就是所谓的主成分。
9.线性降维方法 Linear Discriminant Analysis(LDA) 是一种有监督的（ supervised ）线性降维算法。与 PCA 保持数据信息不同， LDA 是为了使得降维后的数据点尽可能地容易被区分！ 1 、同类的数据点尽可能的接近（ within class ） 2 、不同类的数据点尽可能的分开（ between class ） MDA 多重判别分析（ MDA ） LDA 往多类情况的推广
10.
11.
12.
13.流形学习流形学习在 2000 年在著名的科学杂志《 Science 》被首次提出。流形学习是一种流形的非线性降维方法。降维过程要保留原来高维空间中的拓扑关系。它的主要思想是将高维的数据映射到低维，使该低维的数据能够反映原高维数据的某些本质结构特征。流形学习的前提是有一种假设，即某些高维数据，实际是一种低维的流形结构嵌入在高维空间中。直观上讲是一个流形在 d 维的空间，在一个 m 维的空间被扭曲后的结果。
14.基本术语（流形）输入： x1, x2… xn 输出： y1, y2… yn 输入数据数量： n 输入维度： D 输出维度： d 邻居数量： k 邻居集： Ni 表示 k 个最邻近邻居 xi 的集合。特征向量，特征值 (v i ,λ i )
15.基本术语（流形）流形是局部具有欧氏空间性质的空间。流形并不是一个“形状” ，而是一个“空间”。欧氏空间是带有内积的线性空间，是平坦的，非欧空间是弯曲的。
16.基本术语（流形）定义 1 ：同胚是一个连续函数，其反函数也是一个连续函数。在拓扑学中，两个流形，如果可以通这这弯曲、延展、剪切这这这这这这这 ( 只要最终完全沿着当初剪开的这隙再重新粘这这这这这这这起来这 ) 等操作把其中一个变为另一个，则认为两者是同胚的。如：圆和正方形是同胚的，而球面和环面就不是同胚的。如果两个空间之间存在同胚，那么这两个空间就称为同胚的，从拓扑学的观点来看，两个空间是相同的。
17.基本术语（流形）定义 2 ：一个 d 维的流形集 M 与 Rd （欧氏空间）是局部同胚的。也就是说，对每个 x 属于 M ，在 x,Nx 周围都存在一个开放邻域和一个同胚f:Nx-> Rd, 这些邻域称为坐标块，坐标块组成坐标图，坐标图中的图像被称为参数空间。简单的说就是正逆映射都是光滑的一一映射。
18.基本术语（流形）定义 3 ：每个坐标图是微分同胚的。微分同胚是从微分流形之间的可逆映射，使得此映射及其逆映射均为光滑（即无穷可微）的。这这度小于 3 的流形，可证明同胚的流形必为微分同胚；换言之，此时流形上的拓扑结构确定了微分结构。
19.基本术语（流形学习）假设流形M 由单个坐标图给出。
20.尽管“现实世界”数据集表现出低维流形结构的程度仍在探索之中，但已这这这这了一些这这这这极的例子。这这这这
21.主成分分析 PCA Principal Component Analy sis 李衡 51174500100
22.为什么要用主成分分析？ • 在进行统计学习多变量的任务时，变量越多越复杂 • 减少变量个数 • 往往变量之间会存在一定的相关性（重复） • 删除重复部分，建立新两两不相关的变量
23.• 下表 1 是某些学生的语文、数学、物理、化学成绩统计： • 对总成绩的比较起主要作用的是？
24.如果数据量增大：
25.降维： • 假设从三维降到二维：
26.1. 主成分分析 (PCA) • 是一种统计方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。 • 是一种无监督降维算法，可以很好地解决因变量太多而复杂性、计算量增大的弊端。
27.一些知识点： • 1 ：协方差原理样本 X 和样本 Y 的协方差 (Covariance) ：协方差为正时说明 X 和 Y 是正相关关系，协方差为负时 X 和 Y 是负相关关系，协方差为 0 时 X 和 Y 相互独立。
28.2： • SVD 分解原理： • • 若 AX=λX ，则称 λ 是 A 的特征值， X 是对应的特征向量。
29.主成分分析原理： • 在 PCA 中，最终的目的是找到从原来的 d 维输入空间中找到新的 k 维空间的具有最小信息损失的映射。（ k30.为什么引入投影？ • 以二维数据为例： w 2 w 131.投影的计算方法： • • ❑ � � (�❑ , � …) � � w =32.最大方差定理 : • 投影后得到的点尽可能的分开。33.目标函数： • 投影后的方差： • • 根据前述最大方差定理： • Objectivefunction:•34.•对上式使用拉格朗日乘子法可得：所以，可以看出只要对协方差矩阵进行特征值分解，将求得的特征值排序：提取前 k 个特征值对应的特征向量构成就是主成分的解了。35.PCA 算法流程36.举个例子： • 这在假这这有一这这这数据如下这这：这行代表了样例，列代表特征，这里有 10 个样例，每个样例两个特征。可以认为，有 10 篇文档， x 是 10 篇文档中“ learn” 出现的 TFIDF ， y 是 10 篇文档中 “ study” 出现的 TFIDF 。37.步骤一：中心化 • 分别求 x 和 y 的平均值，然后这于所有的这这这这这这例，都减去对应的均值。这里 x 的均值是 1.81 ， y 的均值是 1.91 ，那么一个样例减去均这后即这这这（ 0.69,0.49 ），得到：38.步骤二：求特征协方差矩阵 • 1. 特征协方差矩阵： • 对角线上分别是 x 和 y 的方差，非对角线上是协方差。39.步骤三：做特征值分解 • 1. 对协方差矩阵做特征值分解，求出其特征值和特征向量：40.步骤四：取特征向量： • 1 ：将特征值按照从大到小的顺序排序，选择其中最大的 k 个，然后将其对应的 k 个特征向量分别作为列向量组成特征向量矩阵 • 这里特征这这只有两个，我这这这这这这这这这其中最大的那个，这这这这这这这 1.28402771 这这里是这，对应的特征向量是 • (-0.677873399, -0.735178656)T41.• • 特征向量求出来，按照前面所这这的公式：这这这 • • 就可以求出投影之后的数据：42.PCA 后续： • • 实践中，即使所有的特征值都大于 0 ，但是某些特征值对方差的影响很小，并且可以丢失，因此，提出一个概念： • 贡献率：第 i 个主成分的反差在全部方差中所占比重 • 累积贡献率：前 k 个主成分共有多大的综合能力，用 k 个主成分的方差和在全部方差中所占的比重： •43.PCA 总结：44.自动编码器 AE Auto-Encoder 李衡 5117450010045.自编码器简介： • 自编码器是一种无监督的神经网络模型，核心作用是能够学习到输入数据的深层表示。 • 自编码器的应用主要有两个方面： • 1 ：特征提取 2 ：非线性降维自动编码器就是一种尽可能复现输入信号的神经网络。为了实现这种复现，自动编码器就必须捕捉可以代表输入数据的最重要的因素，像 PCA ，找到可以代表原信息的主要成分。46.自编码器简介：由编码器（ Encoder ）和解码器（ Decoder ）两部分组成，本质上都是对输入信号做某种变换47.Question ：当 g=f ? • 1: 如果 f 和 g 都是恒等映射，就有 ~x=x •But:• 这样的变化实际中应用价值不大。 • 我们经常对中间信号 y （也叫作 “编码 ”）做一定的约束48.自编码器与神经网络：49.自编码器试图复现其原始输入！ W W* y=x=x~50.自编码器的公式： • 编码过程： • • F 是激活函数， W 是参数 • 解码过程： • • 损失函数： •51.隐层的约束： • 1 ：当隐层维度小于输入数据维度。也就是说从输入层→隐含层的变换是一种降维的操作。实际上，当每两层之间的变换均为线性，且监督训练的误差是二次型误差时，该网络等价于 PCA ！ • 2 ：当隐层维度大于输入数据维度。约束 h 的表达尽量稀疏（有大量维度为 0 ，未被激活），此时的编码器便是 “稀疏自编码器” 。52.降噪自编码器 (Denoising Autoencoder, DAE) ： • 当采用无监督的方法分层预训练深度网络的权值时，为了学习到较鲁棒的特征，可以在网络的可视层（即数据的输入层）引入随机噪声，这种方法称为 Denoise Autoencoder( 简称 DAE) ，由 Bengio 在 08 年提出。 • 使用 DAE 时，可以用被破坏的输入数据重构出原始的数据（指没被破坏的数据），所以它训练出来的特征会更鲁棒。53.DAE 的系统结构如下图（摘自 Vincent 论文）所示：文章： Extracting and composing robust features with denoising autoencoders54.DAE 结构图： �¿1 ¿ ¿ �2 ¿ … ¿ �� ¿ W* h1 … h2 W 1 � 2… �� 1 �2 … �� 55.对 DAE 的直观解释： • 1.dAE 有点类似人体的感官系统 • 2. 多模态信息输入人体时（比如声音，图像等），少了其中某些模态的信息有时影响也不大。 • 3. 普通的 autoencoder 的本质是学习一个相等函数，即输入和重构后的输出相等56.数学上的解释： • 1. 流形学习的观点。一般情况下，高维的数据都处于一个较低维的流形曲面上，而使用 dAE 得到的特征就基本处于这个曲面上。57.堆栈自编码器： • 单个自编码器通过虚构 x→h→x 的三层网络，能够学习出一种特征变化 h=fθ(x) （这里用 θ 表示变换的参数，包括 W,b 和激活函数） • 考虑将 h 作为下一级自编码器的输入。58.堆栈自编码器的结构： • h 再当做原始信息，训练一个新的自编码器，得到新的特征表达 • （论文） Iearning multiple levels of representation and abstraction(Hinton, Bengio, LeC un, 2015)59.稀疏自编码器： • 这种模型背后的思想是，高维而稀疏的表达是好的。 • 一般而言，不会指定隐层表达 h 中哪些节点是被抑制的（对于 s igmoid 单元即输出为 0 ），而是指定一个稀疏性参数 ρ ，代表隐藏神经元的平均活跃程度（在训练集上取平均）。 • 考虑如何从数学模型上进行表达？60.思路： • 既然要求平均激活度为 ρ ，那么只要引入一个度量，来衡量神经元 i 的实际激活度 ρ^i 与期望激活度 ρ 之间的差异即可，然后将这个度量添加到目标函数作为正则，训练整个网络。 • 什么这这的度量合适？这这这这这 • 相对熵，也就是 KL 散度（ KL divergence ）。在信息论中， KL(P Q) 表示当用概率分布 Q 来这这合真这这这分布这 P 时，产生的信息损耗，其中 P 表示真实分布， Q 表示 P 的拟合分布。61.简述 KL 散度： • 这一惩罚因子有如下性质，当时 =0 ，并且随着与之间的差异增大而单调递增。62.• 如果在 AutoEncoder 的基础上加上 L1 的 Regul arity 限制（ L1 主要是约束每一层中的节点中大部分都要为 0 ，只有少数不为 0 ，这就是 Sparse 名字的来源），就可以得到 Sparse AutoEncod er 法。63.稀疏自编码器的两个原则： • 1 ：隐藏层向量是稀疏的，则向量 ht 有尽可能多的零元素； • 2 ：输出层的数据能够尽可能的还原输入层数据64.稀疏编码器的应用： • （论文）KATE:K-Competitive Autoencoder for Text （一种改进的自动编码器应用，得到文本的向量表示 KDD2017 ）65.思想： • 1 ： Encoder 得到中间向量 code 的过程中，神经元之间的权重是不一样的，有些神经元重要，有些神经元不重要。 • 2 ：选择经过激活函数得到 z 中最具竞争力的 k 个神经元 ( 神经元的取值绝对值最大的 k 个 ) 作为胜利者，其余的作为失败者66.• 这样就对神经元的能量进行了再分配，使得重要的神经元得到了加强，不重要的神经元失活67.关于预训练和深度学习： • 对于一个深度网络，这种逐层预训练的方法，正是前面介绍的这种 Stacked Auto-Encoder 。对于常见的分类任务，一般分为以下两个阶段： • layer-wise pre-training （逐层预训练） • fune-tuning （微调）68.多维缩放 -MDS Multiple Dimension Scaling 吴盈娇 5117450005269.Conten ts 目录 01 - K 近邻学习及降维思想 02 - MDS 主要思想及公式 03 - 特征值分解和奇异值分解 04 - MDS 算法描述及实例 05 - 算法总结70.K 近邻学习 • K 近邻是常用的监督学习方法，其工作机制为：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 K 个训练样本，然后基于这 k 个“邻居”的信息进行预测，在分类任务中使用“投票法”进行预测；在回归任务中使用“平均法”作为预测结果。 • 基于一个重要假设：任意测试样本 x 附近任意小的 δ 距离范围内总能找到一个训练样本。71.K 近邻学习 K 近邻分类器示意图，虚线显示等距线；测试样本在 k = 1 或 k = 5 时被判别为正例， k = 3 时被判别为负例。72.低维嵌入 • K 近邻中若距离 δ 为 0.001 ，仅考虑单个属性，需 1000 个样本点平均分布在归一化后的属性取值范围内，才能使任意测试样本在该范围内总能找到一个训练样本，若有更多的属性会造成以下问题：（ 1 ）样本数目难以达到密采样条件（ 2 ）高维空间距离计算复杂高维情景下出现数据样本稀疏、距离计算困难问题，在机器学习中被称为 “维数灾难”。73.低维嵌入缓解“维数灾难” 的重要途径就是“降维”，即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”。即高维空间的低维 “嵌入”。74.多维缩放 - Multiple Dimension Scaling （ MDS ） •主要思想：原始空间中样本点的距离在低维空间中保持不变算法简介：假定 m 个样本在原始空间的距离矩阵为，矩阵 i 行 j 列的元素为样本的距离，我们的目标是获得样本在空间的表示，，且任意两个样本在维空间中的欧氏距离等于原始空间中的距离，即 =75.多维缩放 - Multiple Dimension Scaling （ MDS ） •令， B 这降这这后这这本的内这这这这= 矩这这，则： =+-2 = 表示令降维后的样本 Z 被中心化，即 = 0 则矩阵 B 的行与列之和均为零： = = 0 ( = )76.为什么要样本中心化？ • 机器学习中通常对数据进行中心化（ Zero-centered 或者 Mea n-subtraction ）处理和标准化（ Standardization 或 Normali zation ）处理。中心化的目的是更好的描述数据的方向；标准化的目的是消除特征之间的差异性。77.多维缩放 - Multiple Dimension Scaling （ MDS ） •由：公式 = = =0 = 易知： = (2) 公式 (3) (4) tr(·) 表示矩阵的迹， = = =m+m =78.令：（5 ）（6 ）（7 ）由以及公式 (2)~(7) 可得：（8）79.(2) (3) 公式 (8) 推导： (5) (6) (7) (4) (1) (9) • 由 (5)+(6)-(7) 得： = • 上式带入 (9) 得：80.因此，可通过降维前后保持不变的距离矩阵 D ，求取内积矩阵 B 。对矩阵 B 做特征值分解，，其中为特征值构成的对角矩阵，， V 为特征向量矩阵为，取前个非零特征值，又因为，则 Z 可表示为：81.特征值分解 -Eigen Decomposition •特征值分解（ Eigen decomposition ），又称谱分解（ Spectral decomp osition ）是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。只有可对角化矩阵才能进行特征分解。可对角化矩阵 A 满足， D 为对角矩阵特征值与特征向量的定义：其中 A 是一个的方阵，是 n 维向量，为 A 的一个特征值，而 x 是特征值对应的特征向量。如果我们求出矩阵 A 的 n 个特征值，以及对应的特征向量，那么方阵 A 可用特征分解表示：82.特征值分解 -Eigen Decomposition • 为这 n 个特征值为主对角线的维矩阵，除主对角线以外全为 0 ，如果将 W 的 n 个特征向量标准化，即满足，此时 W 的 n 个特征向量为标准正交基，即满足 , = ，此时 W 为酉矩阵，我们的特征分解表达式可以写这：这83.奇异值分解 -Singular Value Decomposit ion •如果 A 不是方阵，即行与列不相同时，定义矩阵 A 的奇异值分解为：，，矩阵 A 的 SVD 这解如下：84.奇异值分解 -Singular Value Decomposit ion • = , 为左奇异向量 = V ，为右奇异向量可以看出 SVD 奇异这与特征这这这这这这足如下这这这这系：这85.•Eg ：定义矩阵 A 为：（ 1 ）先求出和86.•（ 2 ）进而求出特征值与特征向量：接着求特征值与特征向量：87.•（ 3 ）利用求出奇异值和 1 最终得到的 A 的 SVD 为：88.因此，可通过降维前后保持不变的距离矩阵 D ，求取内积矩阵 B 。对矩阵 B 做特征值分解，，其中为特征值构成的对角矩阵，， V 为特征向量矩阵为，取前个非零特征值，又因为，则 Z 可表示为：89.奇异值分解 -Singular Value Decomposit ion 一般前 10% 甚至 1% 的奇异值的和就占了全部的奇异值之和的 99% 以上的比例，所以在实际运用中，仅需降维后的距离与原始空间中的距离尽可能接近，可取因此，可取个最大特征值构成对角矩阵，，，为特征向量矩阵，则 Z 可表示为：90.MDS 算法描述91.MDS 算法实例有如下表格所示四维数据集（每一项数据有 4 个相关的值）一个待缩放的 4 这表格：矩阵：（ 1 ）数据项两两之间的距离欧式距离 A B C D A 0.0 0.2 0.9 0.8 0.8 B 0.2 0.0 0.9 0.7 0.0 C 0.9 0.9 0.0 1.1 D 0.8 0.7 1.1 0.0 A 0.5 0.0 0.3 0.1 B 0.4 0.15 0.2 0.1 C 0.2 0.4 0.7 D 1.0 0.3 0.692.MDS 算法实例（ 2 ）将数据项随机放置在二维图上。所有数据项两两之间的当前距离是随机放置在二维图后的实际测量距离。（即当前随机距离）（ 3 ）针对每两两构成的一对数据项，将它们的实际距离与当前在二维图上的距离进行比较，求出一个误差值（ 4 ）根据误差的情况，按照比例将每个数据项的所在位置移近或移远少许量。每一个节点的移动，都是所有其它节点施加在该节点上的推或拉的结合效应。节点每移动一次，其当前距离和目标距离之间的差距就会减少一些。93.MDS 算法实例（ 5 ）不断重复第三步、第四步，直到无法再通过移动节点来减少总体误差为止。实现此功能的 python 代码： def scaledown(data,distance=euclidean,rate=0.01)94.MDS 算法优缺点优点 • 可建立非线性关系模型 • 可以从个体获得维度“解决方案”；可深入了解个体与聚合数据的区别 • 无需定义属性情况下发掘维度 • 从 MDS 中产生的维度可合并到回归分析中，去评估他们和其他变量之间的关系缺点 • 只提供了相似 / 不相似的全局测量，而没有提供更细节的信息 • 难以表示和减少对数据的直觉理解。因此，数据的模型就像数据本身一样复杂。 • 维度的意义是主观的95.局部线性嵌入 LLE Locally Linear Embedding 孙阳 5117450012596.LLE • 局部线性嵌入 (Locally Linear Embedding ，简称 LLE) 是非常重要的降维方法。 • 和传统的 PCA ， LDA 等关注样本方差的降维方法相比， LLE 关注于降维时保持样本局部的线性特征，由于 LLE 在降维时保持了样本的局部特征，它广泛的用于图像识别，高维数据可视化等领域。97.LLE 引入 : • 等距映射算法有一个问题就是它要找所有样本全局的最优解，当数据量很大，样本维度很高时，计算起来非常的耗时。 • 鉴于这个问题， LLE 通过放弃所有样本全局最优的降维，只是通过保证局部最优来降维，同时假设样本集在局部是满足线性关系的，进一步减少降维的计算量。98.LLE 思想 : • LLE 首先假设数据在较小的局部是线性的，也就是说，某一个数据可以由它邻域中的几个样本来线性表示。如我们有一个样本 X1 ， X2,X3,X4 为它在原始高维空间中用 K- 近邻思想找到的三个近邻。其中 W12,W13,W14 为权重系数。99.LLE 思想 : • 在我们通过 LLE 降维后，我们希望 X1 在低维空间对应的投影 X1’ 和 X2 ， X3 ， X4 对应的投影 X2’ ， X3’ ， X4’ 也尽量保持同样的线性关系，即也就是说，投影前后线性关系的权重系数 W12,W13,W14 是尽量不变或者最小改变。100.LLE 算法推导 : • 对于 LLE 算法，我们首先要确定邻域大小的选择，即我们需要多少个邻域样本来线性表示某个样本。假设这个值为 k 。 • 寻找到某个样本 Xi 的 k 个最近邻之后我们就需要找到 Xi 和这 k 个最近邻之间的线性关系，即要找到线性关系的权重系数。假设我们有 m 个 n 维的样本，可用均方误差作为损失函数，即：101.LLE 算法推导 : • 一般会对权重系数 Wij 做归一化限制，即满足： • 对于不在样本 Xi 邻域内的样本 Xj ，我们令对应的 Wij=0 。102.LLE 算法推导 : • 矩阵化：其中103.LLE 算法推导 : • 令矩阵，对矩阵化为：其中 1k 为 k 维全 1 向量。用拉格朗日乘子法合为一个优化目标：104.LLE 算法推导 : • 对 W 求偏导并令其为 0 ，得到：即我们的利用对 Wi 归一化，最终权重系数为：105.LLE 算法推导 • 得到了高维的权重系数，我们希望这些权重系数对应的线性关系在降维后的低维一样得到保持。 • 于是， Xi 对应的低维空间坐标 Zi 可通过下式求解：106.LLE 算法推导则可重写为：可通过特征值分解求解： M 最小的 d’ 个特征值对应的特征向量组成的矩阵为107.LLE 算法流程108.LLE 算法流程109.LLE 总结 • 主要优点： 1 ）可以学习任意维的局部线性的低维流形。 2 ）算法归结为稀疏矩阵特征分解，计算复杂度相对较小，实现容易。 • 主要缺点：。 1 ）算法所学习的流形只能是不闭合的，且样本集是稠密均匀的 2 ）算法对最近邻样本数的选择敏感，不同的最近邻数对最后的降维结果有很大影响。110.LLE 的改进算法 • 1 ） Modified Locally Linear Embedding(MLLE) 。 • 2 ） Hessian Based LLE(HLLE) • 3 ） Local tangent space alignment(LTSA)111.Semidefinite Embeddi ng （ SDE ）孙阳 51174500125112.SDE • SDE 基于一种物理的直觉。 • 想象每一个点都跟它的最近邻居用刚性杆相连，取这个结构并且将这个结构拉的尽可能越远越好。113.Example • 假设在二维空间中从 sin 函数抽取一些点。正弦曲线是嵌入到二维空间中的一个一维流形。应用 SDE 的思想去寻找一个一维表示过程如图：114.Example115.SDE • SDE 背后的主要思想被描述为最大方差展开（maximum varian ce unfolding ）。保持原高维空间点对距离与降维后低维空间的点对距离相等最大化方差。 • 算法的第一步是计算每个输入的 k- 近邻，定义邻居的矩阵，若 X i 与 Xj 是 k 近邻，则 ŋij=1 ，否则 ŋij=0 。对所有的 ŋij=1 ，有如下约束：116.SDE • 低维数据中心化 • 最大化方差 • 令 B 表示降维后的 gram matrix ，其中117.SDE 算法流程118.SDE 算法 • SDE 算法主要有三个步骤： 1 ）用 k- 近邻算法找出邻居。 2 ）用半定规划计算 kernel matrix B 。 3 ）计算其最大的几个特征值及相应特征向量。119.等度量映射 Isomap Isometric Feature Mapping 丁雨琦 51174500083120.Isomap 基本概念 • 测地线 (geodesic) 距离 : 空这这中两这 A 点的最长或者最短路径，即两点之间的本真距离 B 图：测地线距离与高维直线距离121.Isomap 基本概念 A • 近邻距离: 基于欧氏距离建立近邻矩阵，计算两点之间的最短路径即为近邻 B 距离图：测地线距离与近邻距离122.Isomap 出发点 • 提出 : Tenenbaum et al. (Science 2000) • 前提 : 在高维空间中分布的数据，实际上是由低维的流形结构嵌入到高维空间中的 • 出发点 : 直接在高维空间中计算直线距离具有误导性，怎么样在高维空间中测出低维空间中两点之间的实际距离呢？123.Isomap 算法 • 基本原理：通过计算邻近距离近似得到测地线距离，在低维嵌入空间中尽量保持任意两点的欧氏距离等于测地线距离，即 = • 所要解决的问题（ 1 ）如何测量流形空间中的测地线距离？（ 2 ）如何将高维空间映射到低维空间？124.Isomap 计算这这地这这距离这 • Step 1 建立邻接矩阵（ 1 ）基于 k- 邻域：对其 k- 邻域包含样本集 D 中与的距离最小的 k 个点，记作（ 2 ）基于 ε- 邻域：对其 ε- 邻域包含样本集 D 中与的距离不大于 ε 的样本，即125.Isomap 计算测地线距离 • Step 2 最短路径计算（ 1 ） Dijkstra 算法：以起始点为中心向外层层扩展，直到扩展到终点为止，使用了广度优先搜索解决赋权有向图的单源最短路径（ 2 ） Floyd 算法：基于动态规划的思想126.Isomap 低维映射 • Step 3 MDS 算法（ 1 ）输入：距离矩阵 G ，其中之间的测地线距离（ 2 ）计算出 B 矩阵，其中 B = （ 3 ）对 B 进行特征值分解，取特征值构成的对角矩阵和相应的特征向量矩阵（ 4 ）输出：矩阵127.Isomap 算法流程 • 输入：样本集 D={} ，近邻参数 • 步骤： 1. 循环 m 个样本，找到每个样本的 k 近邻，并将与 k 近邻的距离设置为欧氏距离，其他距离设为无穷大 2. 调用最短路径算法计算点 3. 以为输入调用 MDS 算法 • 输出：样本集 D 在低维空间中的投影 Y={}128.Isomap 新这这本这这 • 问题： Isomap 算法只得到了 dataset 在低维空间中的坐标，那么如果有新的样本，该如何映射到低维空间呢？ • 解决方案：以 D={} 作为输入， Y={} 作为输出，训练一个回归学习器，对高维空间的新样本直接用回归器对其低维空间坐标进行预测129.Isomap 改进 • 保角映射：基于 Isomap 算法基本思想，但是强调维度空间变换前后保持角度不变，而不是距离。 • 大数据处理：选取 l 个标记点 landmark points ，满足 l>d 且 l <130.Isomap 优点 • 适用于非线形问题 • 不需要进行迭代 • 保持全局最优性 • 保证收敛的渐进性131.Isomap 缺点 • 不稳定，依赖于数据的拓扑结构 • 由于图的离散度过高的估计了测地线距离132.Isomap 例子 • 瑞士卷 Swiss Roll ：选取 1000 个样本点，图中两点的欧氏距离不能反映这两点真正的相似度133.Isomap 例子 • 计算测地线距离：选取 k=7 ， N=1000 ，得到 1000*1000 的距离矩阵134.Isomap 例子 • MDS 算法：保持高维空间和低维空间中的距离相等，得到一个的欧氏空间135.拉普拉斯特征映射 LE Laplacian Eigenmaps 丁雨琦 51174500083136.LE 基本概念 • 拉普拉斯矩阵 Laplacian Matrix ：给定边权重矩阵 • 性质：半正定矩阵最小特征值为 0137.LE 基本原理 • 提出 : Belkin et al. (2002) • 基本原理 : 从局部的角度去构建数据之间的关系。拉普拉斯特征映射是一种基于图的降维算法，它希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近，从而在降维后仍能保持原有的数据结构138.LE 目标函数 • 主要思想：两个数据实例和很相似，那么在降维后目标子空间中应该尽量接近，实例在目标低维空间中的表示，点之间的相似度139.LE 目标函数变换目标函数推导最后确保优化问题有解140.LE 算法流程 • Step1 ：构建邻接矩阵 • Step2 ：确定权重（ 1 ）近邻点则设置为 1 ，否为 0 （ 2 ）使用高斯热核函数 Gaussian Heat Kernel ，近邻点设置为 0141.LE 算法流程 • Step3 ：计算拉普拉斯矩阵 L 的特征向量与特征值，即 • Step4 ：使用最小的 m 个非零特征值对应的特征向量作为降维后的结果输出 • 问题：为什么用最小的 m 个非零特征值对应的特征向量？142.LE 算法例子参数： N 是选取的近邻点的个数， t 是热核函数的参数， t= 即权重为 1143.LE 算法例子 • 瑞士卷 Swiss Roll ：取原始三维空间中的 2000 个数据样例点144.LE 优缺点 • 优点：不会产生“短路”问题计算量小，执行快 • 缺点：对流形上距离远的点不加约束，没办法恢复流形等距的低维坐标热核函数的超参数调节需要经验指导145.流形学这算法这这这这 • 嵌入方式： • Isometric map ：试图找到参数空间到高维空间的坐标图，且保持点于点之间的距离。 • Conformal map ：保持局部角度，而不一定是保持距离146.流形学习算法总结局部 / 全局方法揭示了流形学这算法法这这这区别性特征，局部方法倾向于准确地描述流形的局部几何形状，但在全局层面上无法描述。 • Local ：嵌入中点对于其邻居点的位置较准确 • Global ： Isomap 相反，嵌入中点对于其邻居点的距离不精确，而大部分点与点之间的距离是精确的147.主要参考文献 • 《机器学习》周志华 • 《 Algorithms for manifold learning 》 Lawrence Cayton • 《 A Global Geometric Framework for Nonlinear Dimensionality Reducti on 》 Joshua B. Tenenbaum, 1 ， Vin de Silva, 2 ， John C. Langford 3 • 《 Nonlinear Dimensionality Reduction by Locally Linear Embedding 》 Sam T. Roweis 1 and Lawrence K. Saul 2 • 《集体智慧编程》莫映，王开福（译）148.Thank you ！
30.为什么引入投影？ • 以二维数据为例： w 2 w 1
31.投影的计算方法： • • ❑ � � (�❑ , � …) � � w =
32.最大方差定理 : • 投影后得到的点尽可能的分开。
33.目标函数： • 投影后的方差： • • 根据前述最大方差定理： • Objectivefunction:•
34.•对上式使用拉格朗日乘子法可得：所以，可以看出只要对协方差矩阵进行特征值分解，将求得的特征值排序：提取前 k 个特征值对应的特征向量构成就是主成分的解了。
35.PCA 算法流程
36.举个例子： • 这在假这这有一这这这数据如下这这：这行代表了样例，列代表特征，这里有 10 个样例，每个样例两个特征。可以认为，有 10 篇文档， x 是 10 篇文档中“ learn” 出现的 TFIDF ， y 是 10 篇文档中 “ study” 出现的 TFIDF 。
37.步骤一：中心化 • 分别求 x 和 y 的平均值，然后这于所有的这这这这这这例，都减去对应的均值。这里 x 的均值是 1.81 ， y 的均值是 1.91 ，那么一个样例减去均这后即这这这（ 0.69,0.49 ），得到：
38.步骤二：求特征协方差矩阵 • 1. 特征协方差矩阵： • 对角线上分别是 x 和 y 的方差，非对角线上是协方差。
39.步骤三：做特征值分解 • 1. 对协方差矩阵做特征值分解，求出其特征值和特征向量：
40.步骤四：取特征向量： • 1 ：将特征值按照从大到小的顺序排序，选择其中最大的 k 个，然后将其对应的 k 个特征向量分别作为列向量组成特征向量矩阵 • 这里特征这这只有两个，我这这这这这这这这这其中最大的那个，这这这这这这这 1.28402771 这这里是这，对应的特征向量是 • (-0.677873399, -0.735178656)T
41.• • 特征向量求出来，按照前面所这这的公式：这这这 • • 就可以求出投影之后的数据：
42.PCA 后续： • • 实践中，即使所有的特征值都大于 0 ，但是某些特征值对方差的影响很小，并且可以丢失，因此，提出一个概念： • 贡献率：第 i 个主成分的反差在全部方差中所占比重 • 累积贡献率：前 k 个主成分共有多大的综合能力，用 k 个主成分的方差和在全部方差中所占的比重： •
43.PCA 总结：
44.自动编码器 AE Auto-Encoder 李衡 51174500100
45.自编码器简介： • 自编码器是一种无监督的神经网络模型，核心作用是能够学习到输入数据的深层表示。 • 自编码器的应用主要有两个方面： • 1 ：特征提取 2 ：非线性降维自动编码器就是一种尽可能复现输入信号的神经网络。为了实现这种复现，自动编码器就必须捕捉可以代表输入数据的最重要的因素，像 PCA ，找到可以代表原信息的主要成分。
46.自编码器简介：由编码器（ Encoder ）和解码器（ Decoder ）两部分组成，本质上都是对输入信号做某种变换
47.Question ：当 g=f ? • 1: 如果 f 和 g 都是恒等映射，就有 ~x=x •But:• 这样的变化实际中应用价值不大。 • 我们经常对中间信号 y （也叫作 “编码 ”）做一定的约束
48.自编码器与神经网络：
49.自编码器试图复现其原始输入！ W W* y=x=x~
50.自编码器的公式： • 编码过程： • • F 是激活函数， W 是参数 • 解码过程： • • 损失函数： •
51.隐层的约束： • 1 ：当隐层维度小于输入数据维度。也就是说从输入层→隐含层的变换是一种降维的操作。实际上，当每两层之间的变换均为线性，且监督训练的误差是二次型误差时，该网络等价于 PCA ！ • 2 ：当隐层维度大于输入数据维度。约束 h 的表达尽量稀疏（有大量维度为 0 ，未被激活），此时的编码器便是 “稀疏自编码器” 。
52.降噪自编码器 (Denoising Autoencoder, DAE) ： • 当采用无监督的方法分层预训练深度网络的权值时，为了学习到较鲁棒的特征，可以在网络的可视层（即数据的输入层）引入随机噪声，这种方法称为 Denoise Autoencoder( 简称 DAE) ，由 Bengio 在 08 年提出。 • 使用 DAE 时，可以用被破坏的输入数据重构出原始的数据（指没被破坏的数据），所以它训练出来的特征会更鲁棒。
53.DAE 的系统结构如下图（摘自 Vincent 论文）所示：文章： Extracting and composing robust features with denoising autoencoders
54.DAE 结构图： �¿1 ¿ ¿ �2 ¿ … ¿ �� ¿ W* h1 … h2 W 1 � 2… �� 1 �2 … ��
55.对 DAE 的直观解释： • 1.dAE 有点类似人体的感官系统 • 2. 多模态信息输入人体时（比如声音，图像等），少了其中某些模态的信息有时影响也不大。 • 3. 普通的 autoencoder 的本质是学习一个相等函数，即输入和重构后的输出相等
56.数学上的解释： • 1. 流形学习的观点。一般情况下，高维的数据都处于一个较低维的流形曲面上，而使用 dAE 得到的特征就基本处于这个曲面上。
57.堆栈自编码器： • 单个自编码器通过虚构 x→h→x 的三层网络，能够学习出一种特征变化 h=fθ(x) （这里用 θ 表示变换的参数，包括 W,b 和激活函数） • 考虑将 h 作为下一级自编码器的输入。
58.堆栈自编码器的结构： • h 再当做原始信息，训练一个新的自编码器，得到新的特征表达 • （论文） Iearning multiple levels of representation and abstraction(Hinton, Bengio, LeC un, 2015)
59.稀疏自编码器： • 这种模型背后的思想是，高维而稀疏的表达是好的。 • 一般而言，不会指定隐层表达 h 中哪些节点是被抑制的（对于 s igmoid 单元即输出为 0 ），而是指定一个稀疏性参数 ρ ，代表隐藏神经元的平均活跃程度（在训练集上取平均）。 • 考虑如何从数学模型上进行表达？
60.思路： • 既然要求平均激活度为 ρ ，那么只要引入一个度量，来衡量神经元 i 的实际激活度 ρ^i 与期望激活度 ρ 之间的差异即可，然后将这个度量添加到目标函数作为正则，训练整个网络。 • 什么这这的度量合适？这这这这这 • 相对熵，也就是 KL 散度（ KL divergence ）。在信息论中， KL(P Q) 表示当用概率分布 Q 来这这合真这这这分布这 P 时，产生的信息损耗，其中 P 表示真实分布， Q 表示 P 的拟合分布。
61.简述 KL 散度： • 这一惩罚因子有如下性质，当时 =0 ，并且随着与之间的差异增大而单调递增。
62.• 如果在 AutoEncoder 的基础上加上 L1 的 Regul arity 限制（ L1 主要是约束每一层中的节点中大部分都要为 0 ，只有少数不为 0 ，这就是 Sparse 名字的来源），就可以得到 Sparse AutoEncod er 法。
63.稀疏自编码器的两个原则： • 1 ：隐藏层向量是稀疏的，则向量 ht 有尽可能多的零元素； • 2 ：输出层的数据能够尽可能的还原输入层数据
64.稀疏编码器的应用： • （论文）KATE:K-Competitive Autoencoder for Text （一种改进的自动编码器应用，得到文本的向量表示 KDD2017 ）
65.思想： • 1 ： Encoder 得到中间向量 code 的过程中，神经元之间的权重是不一样的，有些神经元重要，有些神经元不重要。 • 2 ：选择经过激活函数得到 z 中最具竞争力的 k 个神经元 ( 神经元的取值绝对值最大的 k 个 ) 作为胜利者，其余的作为失败者
66.• 这样就对神经元的能量进行了再分配，使得重要的神经元得到了加强，不重要的神经元失活
67.关于预训练和深度学习： • 对于一个深度网络，这种逐层预训练的方法，正是前面介绍的这种 Stacked Auto-Encoder 。对于常见的分类任务，一般分为以下两个阶段： • layer-wise pre-training （逐层预训练） • fune-tuning （微调）
68.多维缩放 -MDS Multiple Dimension Scaling 吴盈娇 51174500052
69.Conten ts 目录 01 - K 近邻学习及降维思想 02 - MDS 主要思想及公式 03 - 特征值分解和奇异值分解 04 - MDS 算法描述及实例 05 - 算法总结
70.K 近邻学习 • K 近邻是常用的监督学习方法，其工作机制为：给定测试样本，基于某种距离度量找出训练集中与其最靠近的 K 个训练样本，然后基于这 k 个“邻居”的信息进行预测，在分类任务中使用“投票法”进行预测；在回归任务中使用“平均法”作为预测结果。 • 基于一个重要假设：任意测试样本 x 附近任意小的 δ 距离范围内总能找到一个训练样本。
71.K 近邻学习 K 近邻分类器示意图，虚线显示等距线；测试样本在 k = 1 或 k = 5 时被判别为正例， k = 3 时被判别为负例。
72.低维嵌入 • K 近邻中若距离 δ 为 0.001 ，仅考虑单个属性，需 1000 个样本点平均分布在归一化后的属性取值范围内，才能使任意测试样本在该范围内总能找到一个训练样本，若有更多的属性会造成以下问题：（ 1 ）样本数目难以达到密采样条件（ 2 ）高维空间距离计算复杂高维情景下出现数据样本稀疏、距离计算困难问题，在机器学习中被称为 “维数灾难”。
73.低维嵌入缓解“维数灾难” 的重要途径就是“降维”，即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”。即高维空间的低维 “嵌入”。
74.多维缩放 - Multiple Dimension Scaling （ MDS ） •主要思想：原始空间中样本点的距离在低维空间中保持不变算法简介：假定 m 个样本在原始空间的距离矩阵为，矩阵 i 行 j 列的元素为样本的距离，我们的目标是获得样本在空间的表示，，且任意两个样本在维空间中的欧氏距离等于原始空间中的距离，即 =
75.多维缩放 - Multiple Dimension Scaling （ MDS ） •令， B 这降这这后这这本的内这这这这= 矩这这，则： =+-2 = 表示令降维后的样本 Z 被中心化，即 = 0 则矩阵 B 的行与列之和均为零： = = 0 ( = )
76.为什么要样本中心化？ • 机器学习中通常对数据进行中心化（ Zero-centered 或者 Mea n-subtraction ）处理和标准化（ Standardization 或 Normali zation ）处理。中心化的目的是更好的描述数据的方向；标准化的目的是消除特征之间的差异性。
77.多维缩放 - Multiple Dimension Scaling （ MDS ） •由：公式 = = =0 = 易知： = (2) 公式 (3) (4) tr(·) 表示矩阵的迹， = = =m+m =
78.令：（5 ）（6 ）（7 ）由以及公式 (2)~(7) 可得：（8）
79.(2) (3) 公式 (8) 推导： (5) (6) (7) (4) (1) (9) • 由 (5)+(6)-(7) 得： = • 上式带入 (9) 得：
80.因此，可通过降维前后保持不变的距离矩阵 D ，求取内积矩阵 B 。对矩阵 B 做特征值分解，，其中为特征值构成的对角矩阵，， V 为特征向量矩阵为，取前个非零特征值，又因为，则 Z 可表示为：
81.特征值分解 -Eigen Decomposition •特征值分解（ Eigen decomposition ），又称谱分解（ Spectral decomp osition ）是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。只有可对角化矩阵才能进行特征分解。可对角化矩阵 A 满足， D 为对角矩阵特征值与特征向量的定义：其中 A 是一个的方阵，是 n 维向量，为 A 的一个特征值，而 x 是特征值对应的特征向量。如果我们求出矩阵 A 的 n 个特征值，以及对应的特征向量，那么方阵 A 可用特征分解表示：
82.特征值分解 -Eigen Decomposition • 为这 n 个特征值为主对角线的维矩阵，除主对角线以外全为 0 ，如果将 W 的 n 个特征向量标准化，即满足，此时 W 的 n 个特征向量为标准正交基，即满足 , = ，此时 W 为酉矩阵，我们的特征分解表达式可以写这：这
83.奇异值分解 -Singular Value Decomposit ion •如果 A 不是方阵，即行与列不相同时，定义矩阵 A 的奇异值分解为：，，矩阵 A 的 SVD 这解如下：
84.奇异值分解 -Singular Value Decomposit ion • = , 为左奇异向量 = V ，为右奇异向量可以看出 SVD 奇异这与特征这这这这这这足如下这这这这系：这
85.•Eg ：定义矩阵 A 为：（ 1 ）先求出和
86.•（ 2 ）进而求出特征值与特征向量：接着求特征值与特征向量：
87.•（ 3 ）利用求出奇异值和 1 最终得到的 A 的 SVD 为：
88.因此，可通过降维前后保持不变的距离矩阵 D ，求取内积矩阵 B 。对矩阵 B 做特征值分解，，其中为特征值构成的对角矩阵，， V 为特征向量矩阵为，取前个非零特征值，又因为，则 Z 可表示为：
89.奇异值分解 -Singular Value Decomposit ion 一般前 10% 甚至 1% 的奇异值的和就占了全部的奇异值之和的 99% 以上的比例，所以在实际运用中，仅需降维后的距离与原始空间中的距离尽可能接近，可取因此，可取个最大特征值构成对角矩阵，，，为特征向量矩阵，则 Z 可表示为：
90.MDS 算法描述
91.MDS 算法实例有如下表格所示四维数据集（每一项数据有 4 个相关的值）一个待缩放的 4 这表格：矩阵：（ 1 ）数据项两两之间的距离欧式距离 A B C D A 0.0 0.2 0.9 0.8 0.8 B 0.2 0.0 0.9 0.7 0.0 C 0.9 0.9 0.0 1.1 D 0.8 0.7 1.1 0.0 A 0.5 0.0 0.3 0.1 B 0.4 0.15 0.2 0.1 C 0.2 0.4 0.7 D 1.0 0.3 0.6
92.MDS 算法实例（ 2 ）将数据项随机放置在二维图上。所有数据项两两之间的当前距离是随机放置在二维图后的实际测量距离。（即当前随机距离）（ 3 ）针对每两两构成的一对数据项，将它们的实际距离与当前在二维图上的距离进行比较，求出一个误差值（ 4 ）根据误差的情况，按照比例将每个数据项的所在位置移近或移远少许量。每一个节点的移动，都是所有其它节点施加在该节点上的推或拉的结合效应。节点每移动一次，其当前距离和目标距离之间的差距就会减少一些。
93.MDS 算法实例（ 5 ）不断重复第三步、第四步，直到无法再通过移动节点来减少总体误差为止。实现此功能的 python 代码： def scaledown(data,distance=euclidean,rate=0.01)
94.MDS 算法优缺点优点 • 可建立非线性关系模型 • 可以从个体获得维度“解决方案”；可深入了解个体与聚合数据的区别 • 无需定义属性情况下发掘维度 • 从 MDS 中产生的维度可合并到回归分析中，去评估他们和其他变量之间的关系缺点 • 只提供了相似 / 不相似的全局测量，而没有提供更细节的信息 • 难以表示和减少对数据的直觉理解。因此，数据的模型就像数据本身一样复杂。 • 维度的意义是主观的
95.局部线性嵌入 LLE Locally Linear Embedding 孙阳 51174500125
96.LLE • 局部线性嵌入 (Locally Linear Embedding ，简称 LLE) 是非常重要的降维方法。 • 和传统的 PCA ， LDA 等关注样本方差的降维方法相比， LLE 关注于降维时保持样本局部的线性特征，由于 LLE 在降维时保持了样本的局部特征，它广泛的用于图像识别，高维数据可视化等领域。
97.LLE 引入 : • 等距映射算法有一个问题就是它要找所有样本全局的最优解，当数据量很大，样本维度很高时，计算起来非常的耗时。 • 鉴于这个问题， LLE 通过放弃所有样本全局最优的降维，只是通过保证局部最优来降维，同时假设样本集在局部是满足线性关系的，进一步减少降维的计算量。
98.LLE 思想 : • LLE 首先假设数据在较小的局部是线性的，也就是说，某一个数据可以由它邻域中的几个样本来线性表示。如我们有一个样本 X1 ， X2,X3,X4 为它在原始高维空间中用 K- 近邻思想找到的三个近邻。其中 W12,W13,W14 为权重系数。
99.LLE 思想 : • 在我们通过 LLE 降维后，我们希望 X1 在低维空间对应的投影 X1’ 和 X2 ， X3 ， X4 对应的投影 X2’ ， X3’ ， X4’ 也尽量保持同样的线性关系，即也就是说，投影前后线性关系的权重系数 W12,W13,W14 是尽量不变或者最小改变。
100.LLE 算法推导 : • 对于 LLE 算法，我们首先要确定邻域大小的选择，即我们需要多少个邻域样本来线性表示某个样本。假设这个值为 k 。 • 寻找到某个样本 Xi 的 k 个最近邻之后我们就需要找到 Xi 和这 k 个最近邻之间的线性关系，即要找到线性关系的权重系数。假设我们有 m 个 n 维的样本，可用均方误差作为损失函数，即：
101.LLE 算法推导 : • 一般会对权重系数 Wij 做归一化限制，即满足： • 对于不在样本 Xi 邻域内的样本 Xj ，我们令对应的 Wij=0 。
102.LLE 算法推导 : • 矩阵化：其中
103.LLE 算法推导 : • 令矩阵，对矩阵化为：其中 1k 为 k 维全 1 向量。用拉格朗日乘子法合为一个优化目标：
104.LLE 算法推导 : • 对 W 求偏导并令其为 0 ，得到：即我们的利用对 Wi 归一化，最终权重系数为：
105.LLE 算法推导 • 得到了高维的权重系数，我们希望这些权重系数对应的线性关系在降维后的低维一样得到保持。 • 于是， Xi 对应的低维空间坐标 Zi 可通过下式求解：
106.LLE 算法推导则可重写为：可通过特征值分解求解： M 最小的 d’ 个特征值对应的特征向量组成的矩阵为
107.LLE 算法流程
108.LLE 算法流程
109.LLE 总结 • 主要优点： 1 ）可以学习任意维的局部线性的低维流形。 2 ）算法归结为稀疏矩阵特征分解，计算复杂度相对较小，实现容易。 • 主要缺点：。 1 ）算法所学习的流形只能是不闭合的，且样本集是稠密均匀的 2 ）算法对最近邻样本数的选择敏感，不同的最近邻数对最后的降维结果有很大影响。
110.LLE 的改进算法 • 1 ） Modified Locally Linear Embedding(MLLE) 。 • 2 ） Hessian Based LLE(HLLE) • 3 ） Local tangent space alignment(LTSA)
111.Semidefinite Embeddi ng （ SDE ）孙阳 51174500125
112.SDE • SDE 基于一种物理的直觉。 • 想象每一个点都跟它的最近邻居用刚性杆相连，取这个结构并且将这个结构拉的尽可能越远越好。
113.Example • 假设在二维空间中从 sin 函数抽取一些点。正弦曲线是嵌入到二维空间中的一个一维流形。应用 SDE 的思想去寻找一个一维表示过程如图：
114.Example
115.SDE • SDE 背后的主要思想被描述为最大方差展开（maximum varian ce unfolding ）。保持原高维空间点对距离与降维后低维空间的点对距离相等最大化方差。 • 算法的第一步是计算每个输入的 k- 近邻，定义邻居的矩阵，若 X i 与 Xj 是 k 近邻，则 ŋij=1 ，否则 ŋij=0 。对所有的 ŋij=1 ，有如下约束：
116.SDE • 低维数据中心化 • 最大化方差 • 令 B 表示降维后的 gram matrix ，其中
117.SDE 算法流程
118.SDE 算法 • SDE 算法主要有三个步骤： 1 ）用 k- 近邻算法找出邻居。 2 ）用半定规划计算 kernel matrix B 。 3 ）计算其最大的几个特征值及相应特征向量。
119.等度量映射 Isomap Isometric Feature Mapping 丁雨琦 51174500083
120.Isomap 基本概念 • 测地线 (geodesic) 距离 : 空这这中两这 A 点的最长或者最短路径，即两点之间的本真距离 B 图：测地线距离与高维直线距离
121.Isomap 基本概念 A • 近邻距离: 基于欧氏距离建立近邻矩阵，计算两点之间的最短路径即为近邻 B 距离图：测地线距离与近邻距离
122.Isomap 出发点 • 提出 : Tenenbaum et al. (Science 2000) • 前提 : 在高维空间中分布的数据，实际上是由低维的流形结构嵌入到高维空间中的 • 出发点 : 直接在高维空间中计算直线距离具有误导性，怎么样在高维空间中测出低维空间中两点之间的实际距离呢？
123.Isomap 算法 • 基本原理：通过计算邻近距离近似得到测地线距离，在低维嵌入空间中尽量保持任意两点的欧氏距离等于测地线距离，即 = • 所要解决的问题（ 1 ）如何测量流形空间中的测地线距离？（ 2 ）如何将高维空间映射到低维空间？
124.Isomap 计算这这地这这距离这 • Step 1 建立邻接矩阵（ 1 ）基于 k- 邻域：对其 k- 邻域包含样本集 D 中与的距离最小的 k 个点，记作（ 2 ）基于 ε- 邻域：对其 ε- 邻域包含样本集 D 中与的距离不大于 ε 的样本，即
125.Isomap 计算测地线距离 • Step 2 最短路径计算（ 1 ） Dijkstra 算法：以起始点为中心向外层层扩展，直到扩展到终点为止，使用了广度优先搜索解决赋权有向图的单源最短路径（ 2 ） Floyd 算法：基于动态规划的思想
126.Isomap 低维映射 • Step 3 MDS 算法（ 1 ）输入：距离矩阵 G ，其中之间的测地线距离（ 2 ）计算出 B 矩阵，其中 B = （ 3 ）对 B 进行特征值分解，取特征值构成的对角矩阵和相应的特征向量矩阵（ 4 ）输出：矩阵
127.Isomap 算法流程 • 输入：样本集 D={} ，近邻参数 • 步骤： 1. 循环 m 个样本，找到每个样本的 k 近邻，并将与 k 近邻的距离设置为欧氏距离，其他距离设为无穷大 2. 调用最短路径算法计算点 3. 以为输入调用 MDS 算法 • 输出：样本集 D 在低维空间中的投影 Y={}
128.Isomap 新这这本这这 • 问题： Isomap 算法只得到了 dataset 在低维空间中的坐标，那么如果有新的样本，该如何映射到低维空间呢？ • 解决方案：以 D={} 作为输入， Y={} 作为输出，训练一个回归学习器，对高维空间的新样本直接用回归器对其低维空间坐标进行预测
129.Isomap 改进 • 保角映射：基于 Isomap 算法基本思想，但是强调维度空间变换前后保持角度不变，而不是距离。 • 大数据处理：选取 l 个标记点 landmark points ，满足 l>d 且 l <130.Isomap 优点 • 适用于非线形问题 • 不需要进行迭代 • 保持全局最优性 • 保证收敛的渐进性131.Isomap 缺点 • 不稳定，依赖于数据的拓扑结构 • 由于图的离散度过高的估计了测地线距离132.Isomap 例子 • 瑞士卷 Swiss Roll ：选取 1000 个样本点，图中两点的欧氏距离不能反映这两点真正的相似度133.Isomap 例子 • 计算测地线距离：选取 k=7 ， N=1000 ，得到 1000*1000 的距离矩阵134.Isomap 例子 • MDS 算法：保持高维空间和低维空间中的距离相等，得到一个的欧氏空间135.拉普拉斯特征映射 LE Laplacian Eigenmaps 丁雨琦 51174500083136.LE 基本概念 • 拉普拉斯矩阵 Laplacian Matrix ：给定边权重矩阵 • 性质：半正定矩阵最小特征值为 0137.LE 基本原理 • 提出 : Belkin et al. (2002) • 基本原理 : 从局部的角度去构建数据之间的关系。拉普拉斯特征映射是一种基于图的降维算法，它希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近，从而在降维后仍能保持原有的数据结构138.LE 目标函数 • 主要思想：两个数据实例和很相似，那么在降维后目标子空间中应该尽量接近，实例在目标低维空间中的表示，点之间的相似度139.LE 目标函数变换目标函数推导最后确保优化问题有解140.LE 算法流程 • Step1 ：构建邻接矩阵 • Step2 ：确定权重（ 1 ）近邻点则设置为 1 ，否为 0 （ 2 ）使用高斯热核函数 Gaussian Heat Kernel ，近邻点设置为 0141.LE 算法流程 • Step3 ：计算拉普拉斯矩阵 L 的特征向量与特征值，即 • Step4 ：使用最小的 m 个非零特征值对应的特征向量作为降维后的结果输出 • 问题：为什么用最小的 m 个非零特征值对应的特征向量？142.LE 算法例子参数： N 是选取的近邻点的个数， t 是热核函数的参数， t= 即权重为 1143.LE 算法例子 • 瑞士卷 Swiss Roll ：取原始三维空间中的 2000 个数据样例点144.LE 优缺点 • 优点：不会产生“短路”问题计算量小，执行快 • 缺点：对流形上距离远的点不加约束，没办法恢复流形等距的低维坐标热核函数的超参数调节需要经验指导145.流形学这算法这这这这 • 嵌入方式： • Isometric map ：试图找到参数空间到高维空间的坐标图，且保持点于点之间的距离。 • Conformal map ：保持局部角度，而不一定是保持距离146.流形学习算法总结局部 / 全局方法揭示了流形学这算法法这这这区别性特征，局部方法倾向于准确地描述流形的局部几何形状，但在全局层面上无法描述。 • Local ：嵌入中点对于其邻居点的位置较准确 • Global ： Isomap 相反，嵌入中点对于其邻居点的距离不精确，而大部分点与点之间的距离是精确的147.主要参考文献 • 《机器学习》周志华 • 《 Algorithms for manifold learning 》 Lawrence Cayton • 《 A Global Geometric Framework for Nonlinear Dimensionality Reducti on 》 Joshua B. Tenenbaum, 1 ， Vin de Silva, 2 ， John C. Langford 3 • 《 Nonlinear Dimensionality Reduction by Locally Linear Embedding 》 Sam T. Roweis 1 and Lawrence K. Saul 2 • 《集体智慧编程》莫映，王开福（译）148.Thank you ！
130.Isomap 优点 • 适用于非线形问题 • 不需要进行迭代 • 保持全局最优性 • 保证收敛的渐进性
131.Isomap 缺点 • 不稳定，依赖于数据的拓扑结构 • 由于图的离散度过高的估计了测地线距离
132.Isomap 例子 • 瑞士卷 Swiss Roll ：选取 1000 个样本点，图中两点的欧氏距离不能反映这两点真正的相似度
133.Isomap 例子 • 计算测地线距离：选取 k=7 ， N=1000 ，得到 1000*1000 的距离矩阵
134.Isomap 例子 • MDS 算法：保持高维空间和低维空间中的距离相等，得到一个的欧氏空间
135.拉普拉斯特征映射 LE Laplacian Eigenmaps 丁雨琦 51174500083
136.LE 基本概念 • 拉普拉斯矩阵 Laplacian Matrix ：给定边权重矩阵 • 性质：半正定矩阵最小特征值为 0
137.LE 基本原理 • 提出 : Belkin et al. (2002) • 基本原理 : 从局部的角度去构建数据之间的关系。拉普拉斯特征映射是一种基于图的降维算法，它希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近，从而在降维后仍能保持原有的数据结构
138.LE 目标函数 • 主要思想：两个数据实例和很相似，那么在降维后目标子空间中应该尽量接近，实例在目标低维空间中的表示，点之间的相似度
139.LE 目标函数变换目标函数推导最后确保优化问题有解
140.LE 算法流程 • Step1 ：构建邻接矩阵 • Step2 ：确定权重（ 1 ）近邻点则设置为 1 ，否为 0 （ 2 ）使用高斯热核函数 Gaussian Heat Kernel ，近邻点设置为 0
141.LE 算法流程 • Step3 ：计算拉普拉斯矩阵 L 的特征向量与特征值，即 • Step4 ：使用最小的 m 个非零特征值对应的特征向量作为降维后的结果输出 • 问题：为什么用最小的 m 个非零特征值对应的特征向量？
142.LE 算法例子参数： N 是选取的近邻点的个数， t 是热核函数的参数， t= 即权重为 1
143.LE 算法例子 • 瑞士卷 Swiss Roll ：取原始三维空间中的 2000 个数据样例点
144.LE 优缺点 • 优点：不会产生“短路”问题计算量小，执行快 • 缺点：对流形上距离远的点不加约束，没办法恢复流形等距的低维坐标热核函数的超参数调节需要经验指导
145.流形学这算法这这这这 • 嵌入方式： • Isometric map ：试图找到参数空间到高维空间的坐标图，且保持点于点之间的距离。 • Conformal map ：保持局部角度，而不一定是保持距离
146.流形学习算法总结局部 / 全局方法揭示了流形学这算法法这这这区别性特征，局部方法倾向于准确地描述流形的局部几何形状，但在全局层面上无法描述。 • Local ：嵌入中点对于其邻居点的位置较准确 • Global ： Isomap 相反，嵌入中点对于其邻居点的距离不精确，而大部分点与点之间的距离是精确的
147.主要参考文献 • 《机器学习》周志华 • 《 Algorithms for manifold learning 》 Lawrence Cayton • 《 A Global Geometric Framework for Nonlinear Dimensionality Reducti on 》 Joshua B. Tenenbaum, 1 ， Vin de Silva, 2 ， John C. Langford 3 • 《 Nonlinear Dimensionality Reduction by Locally Linear Embedding 》 Sam T. Roweis 1 and Lawrence K. Saul 2 • 《集体智慧编程》莫映，王开福（译）
148.Thank you ！