页面树结构

2017-11-09 ApacheCN 开源组织,第二期邀请成员活动,一起走的更远 : http://www.apachecn.org/member/209.html


MachineLearning 优酷地址 : http://i.youku.com/apachecn

转至元数据结尾
转至元数据起始
寻找裸露的必需品
简单的裸露必需品
忘记你的烦恼和你的冲突
我的意思是裸露的必需品
老母亲大自然的食谱
这带来了生活的必需品
- 巴勒的歌[丛林书]

流行学习是非线性降维的一种方法。这个任务的算法是基于许多数据集的维数只是人为的高。

 

介绍

高维数据集可能非常难以可视化。虽然可以绘制两维或三维数据来显示数据的固有结构,但是等效的高维图不太直观。为了帮助可视化数据集的结构,必须以某种方式减小维度。

通过对数据进行随机投影,实现降维的最简单方法就是。虽然这允许数据结构的一定程度的可视化,但是选择的随机性是非常需要的。在随机投影中,数据中更有趣的结构很可能会丢失。

 

为了解决这一问题,设计了一些监督和无监督的线性维数降低框架,如主成分分析(PCA),独立成分分析,线性判别分析等。这些算法定义了特定的标题来选择数据的“有趣”线性投影。这些方法可以是强大的,但是经常会错过数据中重要的非线性结构。

 

歧管学习可以被认为是将线性框架(如PCA)推广到对数据中的非线性结构敏感的尝试。虽然存在监督变量,但是典型的歧管学习问题是无监督的:它从数据本身学习数据的高维度结构,而不使用预定的分类。

例子:

以下概述了scikit-learn中可用的多元学习实现。

 

ISOMAP 

多边形学习的最早方法之一是Isomap算法,等距映射的缩写。Isomap可以被视为多维缩放(MDS)或内核PCA的扩展。Isomap寻求一个维度较低的嵌入,它保持所有点之间的测地距离。Isomap可以与对象一起执行 Isomap

复杂性

Isomap算法包括三个阶段:

  1. 最邻居搜索。 Isomap sklearn.neighbors.BallTree用于高效的邻居搜索。对于尺寸点的ķ最近邻居,成本近似。ñð
  2. 最短路径图搜索。 对此最有效的已知算法是Dijkstra的算法,这是大约 Floyd-Warshall算法,这是。该算法可以由用户选择path_method关键字Isomap。如果未指定,则代码尝试为输入数据选择最佳算法。
  3. 部分特征值分解。 嵌入在ðisomap内核的最大特征值 对应的特征向量中进行编码。对于一个密集的求解器,成本约为。通常使用ARPACK求解器可以提高成本。用户可以使用path_method关键字指定特征Isomap。如果未指定,则代码尝试为输入数据选择最佳算法。

Isomap的整体复杂性是 

  • ñ :训练数据点数
  • ð :输入尺寸
  • ķ :最近邻居数
  • ð :输出尺寸

参考文献:

 

局部线性嵌入

局部线性嵌入(LLE)寻求保留本地邻域内距离的数据的低维投影。它可以被认为是一系列局部主成分分析,全球相比,找到最好的非线性嵌入。

本地线性嵌入可以用函数 locally_linear_embedding或其面向对象进行 LocallyLinearEmbedding

复杂性

标准LLE算法包括三个阶段:

  1. 最近的邻居搜索。请参阅上述Isomap上的讨论。
  2. 重量矩阵构造。LLE权重矩阵的构造涉及每个ñ局部邻域的 线性方程的解
  3. 部分特征值分解。请参阅上述Isomap上的讨论。

标准LLE的整体复杂度是 

  • ñ :训练数据点数
  • ð :输入尺寸
  • ķ :最近邻居数
  • ð :输出尺寸

参考文献:

 

修改本地线性嵌入

LLE的一个众所周知的问题是正则化问题。当邻居数量大于输入维数时,定义每个本地邻域的矩阵是秩缺陷的。为了解决这个问题,标准LLE应用了一个任意的正则化参数,它相对于局部权重矩阵的轨迹来选择。虽然可以正式显示,因为,解决方案收敛到期望的嵌入,不能保证找到最佳解决方案。这个问题表现在使得歧管的基本几何形状变形的嵌入。

解决正则化问题的一种方法是在每个邻域中使用多个权重向量。这是修改局部线性嵌入(MLLE)的本质。MLLE可以用功能进行 locally_linear_embedding或它的面向对象的对应 LocallyLinearEmbedding,与关键字。它需要。method = 'modified'n_neighbors > n_components

复杂性

MLLE算法包括三个阶段:

  1. 最近的邻居搜索。与标准LLE相同
  2. 重量矩阵构造。约 。第一个术语与标准的LLE完全相同。第二个术语与从多个权重构成权重矩阵有关。在实践中,与步骤1和3的成本相比,构建MLLE权重矩阵的附加成本相对较小。
  3. 部分特征值分解。与标准LLE相同

MLLE的整体复杂性是 

  • ñ :训练数据点数
  • ð :输入尺寸
  • ķ :最近邻居数
  • ð :输出尺寸

Hessian特征映射

Hessian特征映射(也称为基于Hessian的LLE:HLLE)是解决LLE正则化问题的另一种方法。 它围绕每个邻域的基于一个基于粗体的二次形式,用于恢复局部线性结构。 虽然其他实现注意到其数据大小缩小,但是sklearn实现了一些算法改进,使其成本与其他LLE变体的成本相当,用于小的输出维度。 可以使用函数locally_linear_embedding或其面向对象的LocallyLinearEmbedding执行HLLE,并使用关键字method ='hessian'。 它需要n_neighbors> n_components *(n_components + 3)/ 2。

复杂性

HLLE算法包括三个阶段:

  1. 最近的邻居搜索。与标准LLE相同
  2. 重量矩阵构造。约 。第一个术语反映出与标准LLE类似的成本。第二个术语来自本地粗糙估计的QR分解。
  3. 部分特征值分解。与标准LLE相同

标准HLLE的整体复杂度是 

  • ñ :训练数据点数
  • ð :输入尺寸
  • ķ :最近邻居数
  • ð :输出尺寸

参考文献:

 

光谱嵌入 

光谱嵌入(也称为拉普拉斯特征图)是计算非线性嵌入的一种方法。它使用图拉普拉斯算子的频谱分解找到数据的低维度表示。生成的图可以被认为是高维空间中低维歧管的离散近似。基于图形的成本函数的最小化确保了在歧管上彼此靠近的点在低维空间中彼此靠近,保留了局部距离。光谱嵌入可以用函数spectral_embedding或其面向对象的对象进行SpectralEmbedding

2.2.6.1。复杂性

光谱嵌入算法包括三个阶段:

  1. 加权图构造。使用亲和度(邻接)矩阵表示将原始输入数据转换为图形表示。
  2. 图拉普拉斯建设。非规范化的拉普拉斯算子被构造为和归一化 
  3. 部分特征值分解。特征值分解在图拉普拉斯算子上进行

光谱嵌入的整体复杂度是 

  • ñ :训练数据点数
  • ð :输入尺寸
  • ķ :最近邻居数
  • ð :输出尺寸

参考文献:

 

局部切线空间对齐

虽然在技术上不是LLE的变体,但是本地切线空间对齐(LTSA)在算术上与LLE相似,可以放在该类别中。LTSA不是像LLE那样专注于保留邻域距离,而是通过其切线空间来表征每个邻域的局部几何,并执行全局优化来对齐这些局部切线空间以学习嵌入。LTSA可以使用功能 locally_linear_embedding或其面向对象 LocallyLinearEmbedding的关键字执行。method = 'ltsa'

复杂性

LTSA算法包括三个阶段:

  1. 最近的邻居搜索。与标准LLE相同
  2. 重量矩阵构造。约 。第一个术语反映出与标准LLE类似的成本。
  3. 部分特征值分解。与标准LLE相同

标准LTSA的整体复杂度是 

  • ñ :训练数据点数
  • ð :输入尺寸
  • ķ :最近邻居数
  • ð :输出尺寸

参考文献:

 

多维缩放(MDS)

多维缩放 (MDS)寻找数据的低维表示,其中距离很好地与原始高维空间中的距离相当。

一般来说,是用于分析相似性或不相似性数据的技术。MDS尝试将相似性或不相似性数据建模为几何空间中的距离。数据可以是对象之间的相似度,分子的相互作用频率或国家之间的交易指数。

存在两种类型的MDS算法:度量和非度量。在scikit学习中,该类MDS实现了两者。在度量MDS中,输入相似性矩阵由度量(因此涉及三角不等式)产生,然后将输出两点之间的距离设置为尽可能接近相似性或不相似性数据。在非度量版本中,算法将尝试保留距离的顺序,因此寻求嵌入空间中的距离与相似/不相似之间的单调关系。

小号相似度矩阵,以及输入点X的坐标 ñ。差异是以某种最佳方式选择的相似性的转变。称为压力的目标由此定义

公制

MDS称为绝对MDS的最简单的度量模型是由...定义的 。使用绝对MDS,该值 应该完全对应于点一世和 Ĵ嵌入点之间的距离。

最常见的是差异

非度量MDS 

非度量MDS重点是数据的排列。如果 ,则嵌入应该执行。一种简单的算法来执行该方法是使用的单调回归,得到的差异 在相同的顺序

这个问题的一个简单的解决方案是将所有要点放在原点上。为了避免这种情况,差异正常化。

参考文献:

 

t分布随机邻域嵌入(t-SNE)

t-SNE(TSNE)将数据点的亲和度转换为概率。原始空间的亲和度由高斯联合概率表示,嵌入空间的亲和度由学生的t分布表示。这使得t-SNE对局部结构特别敏感,并且与现有技术相比具有一些其他优点:

  • 在单个地图上显示多个尺度的结构
  • 显示位于多个,不同,歧管或集群中的数据
  • 减少在中心聚集点的倾向

虽然Isomap,LLE和变体最适合展开单个连续低维歧管,但是t-SNE将集中在数据的局部结构上,并且将倾向于提取S曲线示例上突出显示的样本集群本地组。根据本地结构对这些样本进行分组的能力可能对数字数据集中的情况一次视觉解密包含多个歧管的数据集可能是有益的。

原始空间和嵌入空间的联合概率的Kullback-Leibler(KL)分歧将通过梯度下降最小化。注意,KL分歧不是凸的,即具有不同初始化的多个重启将最终在KL分歧的局部最小值中。因此,有时候尝试不同的种子并选择具有最低KL分歧的嵌入是有用的。

使用t-SNE的缺点大概是:

  • t-SNE在计算上是昂贵的,并且在数百万个样本数据集中可能需要几个小时,PCA将在几秒钟或几分钟内完成
  • Barnes-Hut t-SNE方法限于二维或三维嵌入。
  • 算法是随机的,具有不同种子的多次重启可以产生不同的嵌入。但是,使用最小错误来选择嵌入是完全合法的。
  • 全局结构未明确保留。这是通过使用PCA初始化点(使用init ='pca')减轻的问题。

优化T-SNE 

t-SNE的主要目的是高维数据的可视化。因此,当数据嵌入二维或三维时,效果最好。

有时候优化KL分歧可能有点棘手。有五个参数控制t-SNE的优化,因此可能导致嵌入的质量:

  • 困惑
  • 早期夸张因素
  • 学习率
  • 最大迭代次数
  • 角度(精确方法不使用)

困惑被定义为条件概率分布的香农熵在哪里小号。一个ķ芯片的困惑 是ķ,因此,ķ在产生条件概率时,t-SNE的最近邻居的数量是有效的。更大的困惑导致更近的邻居,对小结构的敏感性较低。较大的数据集往往需要更大的困惑。最大迭代次数通常足够高,不需要任何调整。优化包括两个阶段:早期夸张阶段和最终优化。在早期夸张的情况下,原始空间的联合概率将通过乘以给定因子人为增加。更大的因素导致数据中自然聚类之间的差距较大。如果因素太高,在这个阶段,KL分歧可能会增加。通常不需要调整。关键参数是学习率。如果太低的梯度下降将被困在局部最小的地方。如果太高,则优化过程中KL分歧将会增加。更多提示可以在Laurens van der Maaten的FAQ中找到(参见参考资料)。最后一个参数角度是性能和精度之间的折衷。较大的角度意味着我们可以通过单个点近似较大的区域,导致更好的速度,但不太准确的结果。如果太低的梯度下降将被困在局部最小的地方。如果太高,则优化过程中KL分歧将会增加。更多提示可以在Laurens van der Maaten的FAQ中找到(参见参考资料)。最后一个参数角度是性能和精度之间的折衷。较大的角度意味着我们可以通过单个点近似较大的区域,导致更好的速度,但不太准确的结果。如果太低的梯度下降将被困在局部最小的地方。如果太高,则优化过程中KL分歧将会增加。更多提示可以在Laurens van der Maaten的FAQ中找到(参见参考资料)。最后一个参数角度是性能和精度之间的折衷。较大的角度意味着我们可以通过单个点近似较大的区域,导致更好的速度,但不太准确的结果。

Barnes-Hut t-SNE

在这里实施的Barnes-Hut t-SNE通常比其他流形学习算法慢得多。优化是非常困难的,梯度的计算是,这里ð是输出的维数和ñ是样本的数目。Barnes-Hut方法改进了t-SNE复杂度的确切方法 ,但具有其他几个显着差异:

  • Barnes-Hut实现仅在目标维度为3或更小时才起作用。构建可视化时,2D案例是典型的。
  • Barnes-Hut仅适用于密集输入数据。稀疏数据矩阵只能用精确的方法嵌入,或者可以通过例如使用的密集低等级投影近似sklearn.decomposition.TruncatedSVD
  • Barnes-Hut是精确方法的近似值。使用角度参数对近似值进行参数化,因此当方法=“精确”时角度参数未使用
  • Barnes-Hut具有更大的可扩展性。Barnes-Hut可用于嵌入数十万个数据点,而精确的方法可以在成为计算难度之前处理数千个样本

为了可视化的目的(这是t-SNE的主要用例),强烈建议使用Barnes-Hut方法。精确的t-SNE方法对于检查可能在较高维空间中的嵌入的理论属性是有用的,但由于计算约束而限制于小数据集。

还要注意,数字标签大致与t-SNE发现的自然分组匹配,而PCA模型的线性2D投影产生标签区域大大重叠的表示。这是一个很强的线索,这个数据可以通过专注于局部结构的非线性方法(例如具有高斯RBF内核的SVM)来很好地分离。然而,未能在2D中用t-SNE显现良好分离的均匀标记的组不一定意味着数据不能被监督模型正确分类。可能的情况是,2维不足以准确地表示数据的内部结构。

参考文献:

 

实用窍门

  • 确保在所有功能上使用相同的刻度。因为歧管学习方法是基于最近邻搜索,否则算法可能表现不佳。有关 扩展异构数据的方便方法,请参阅StandardScaler
  • 每个程序计算出的重建误差可用于选择最优输出维数。对于ð嵌入在一ð维参数空间中的维度歧管,重建误差将随着n_components增加而减小。n_components == d
  • 请注意,噪声数据可能会使歧管“短路”,实质上作为歧管部分之间的桥梁,否则其将被很好地分离。歧管和/或不完整的数据学习是一个积极的研究领域。
  • 某些输入配置可以导致单数加权矩阵,例如当数据集中的两个以上点相同时,或者当数据被分割成不相交的组时。在这种情况下,solver='arpack' 将无法找到空值空间。解决这个问题的最简单的方法是使用solver='dense'哪种方法可以在单个矩阵上工作,尽管它可能非常慢,这取决于输入点的数量。或者,可以尝试了解奇点的来源:如果是由于不相交集,增加n_neighbors可能有所帮助。如果是由于数据集中的相同点,删除这些点可能有所帮助。

 

也可以看看:完全随机树嵌入也可用于导出特征空间的非线性表示,也不会降低维数。

  • 无标签