页面树结构

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


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

转至元数据结尾
转至元数据起始

Nearest Neighbors ( 最近邻 )

sklearn.neighbors 提供了无监督和监督的 neighbors-based ( 基于邻居 ) 的学习方法的功能。无监督的最近邻是许多其他学习方法的基础,特别是 manifold learning ( 多学科 ) 和 spectral clustering ( 频谱聚类 ) 。受监督的 neighbors-based ( 基于邻居 ) 的学习有两种风格:具有离散标签的数据 分类,以及具有连续标签的数据的 回归
最邻近方法的原理是找到与新点最近的距离最接近的预定数量的训练样本,并从这些中预测标签。样本数可以是用户定义的常数(k-最近邻学习),或者基于点的局部密度(基于半径的邻居学习)而变化。一般来说,距离可以是 metric measure :标准欧氏距离是最常见的选择。基于邻居的方法被称为非泛化机器学习方法,因为它们简单地 “remember” 其所有训练数据(可能被转换成诸如 Ball Tree KD Tree 的快速索引结构)。
尽管它的简单性,最近的邻居已经成功地进行了大量的分类和回归问题,包括手写数字或卫星图像场景。作为非参数方法,在决策边界非常不规则的分类情况下,通常是成功的。
sklearn.neighbors 中的类可以处理 Numpy 数组或 scipy.sparse matrices 作为输入。对于密集矩阵,支持大量可能的距离度量。对于稀疏矩阵,搜索可支持任意的 Minkowski metrics 。
有许多依靠最近的邻居的学习习惯是核心的。density estimation ( 密度估计 ) 部分讨论的 核密度估计 的一个例子。

Unsupervised Nearest Neighbors ( 无监督最近邻 )

NearestNeighbors 实现 unsupervised nearest neighbors learning ( 无监督最近邻学习 ) 。它作为三个不同的最近邻算法的统一接口: BallTree KDTree 和基于 sklearn.metrics.pairwise 中的 brute-force algorithm based on routines ( 例程的强力算法 ) neighbors search algorithm ( 邻域搜索算法 ) 的选择通过关键字algorithm 进行控制,该算法必须是 ['auto','ball_tree','kd_tree','brute'] 之一。当通过默认值 “auto” 时,算法尝试从训练数据确定最佳方法。有关每个选项的优缺点的讨论,请参阅 最近邻算法

警告

关于最近邻算法,如果两个 neighbors ( 邻居 ),neighbor neighbor k 具有相同的距离,但是具有不同的 label ( 标签 ) ,结果取决于训练数据的排序。

Finding the Nearest Neighbors ( 找到最近的邻居 )

为了找到两组数据之间最近邻居的简单任务,可以使用  sklearn.neighbors 内的无监督算法:

>>> from sklearn.neighbors import NearestNeighbors
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
>>> distances, indices = nbrs.kneighbors(X)
>>> indices                                           
array([[0, 1],
       [1, 0],
       [2, 1],
       [3, 4],
       [4, 3],
       [5, 4]]...)
>>> distances
array([[ 0.        ,  1.        ],
       [ 0.        ,  1.        ],
       [ 0.        ,  1.41421356],
       [ 0.        ,  1.        ],
       [ 0.        ,  1.        ],
       [ 0.        ,  1.41421356]])

因为 query set ( 查询集 )匹配 training set ( 训练集 ) ,每个点的最近邻点是点本身,距离是零。

还可以有效地产生一个显示相邻点之间连接的稀疏图:

>>> nbrs.kneighbors_graph(X).toarray()
array([[ 1.,  1.,  0.,  0.,  0.,  0.],
       [ 1.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  1.,  1.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  1.,  1.,  0.],
       [ 0.,  0.,  0.,  1.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  1.,  1.]])

我们的数据集被构造成使得附近的索引顺序的点在参数空间附近,生成近似于 K 个最近邻的块对角矩阵。这种稀疏图在各种情况下都是有用的,他们利用无监督学习的点之间的空间关系:特别是参见 sklearn.manifold.Isomapsklearn.manifold.LocallyLinearEmbedding 和 sklearn.cluster.SpectralClustering

KDTree and BallTree Classes 

或者,可以直接使用 KDTreeBallTree 类来查找最近的邻居。这是上面使用的 NearestNeighbors 类所包含的功能。Ball TreeKD Tree 具有相同的界面 ; 我们将在这里展示一个使用 KD Tree 的例子:

>>> from sklearn.neighbors import KDTree
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> kdt = KDTree(X, leaf_size=30, metric='euclidean')
>>> kdt.query(X, k=2, return_distance=False)          
array([[0, 1],
       [1, 0],
       [2, 1],
       [3, 4],
       [4, 3],
       [5, 4]]...)

有关可用于 neighbors searches ( 邻居搜索 )的选项的更多信息,包括各种距离度量的查询策略的规范等,请参阅 KDTree BallTree 类文档。有关可用度量列表,请参阅 DistanceMetric 类的文档。

Nearest Neighbors Classification ( 最近邻分类 )

Neighbors-based classification ( 基于邻居的分类 ) 是一种 instance-based learning ( 基于实例的学习 ) 或 non-generalizing learning ( 非泛化学习 ) :它不试图构建一般的内部模型,而只是存储训练数据的实例。分类是从每个点的最近邻居的 simple majority vote ( 简单多数投票 ) 中计算出来的:一个查询点被分配在点的最近邻居中具有最多代表的数据类。

scikit-learn 实现两个不同的最近邻居分类器:KNeighborsClassifier 基于每个查询点的 k 个最近邻居实现学习,其中k是用户指定的整数值。 RadiusNeighborsClassifier 实现基于每个训练点的固定半径 r 内的邻居数量的学习,其中 r 是用户指定的浮点值。

KNeighborsClassifier 中的 k 邻居分类是两种技术中更常用的。值 k 的最佳选择是高度依赖于数据的:通常较大的 k 抑制噪声的影响,但是使得分类边界不太明显。

在数据不均匀采样的情况下,RadiusNeighborsClassifier 中基于半径的邻居分类可以是更好的选择。用户指定一个固定的半径 r ,使得稀疏区域中的点对分类使用较少的最近邻居。对于高维参数空间,由于所谓的 “curse of dimensionality ( 维度惩罚 )” ,该方法变得不太有效。

基本最近邻分类使用均匀权重:即,分配给查询点的值是从最近的邻居的简单多数投票计算的。在某些情况下,最好对邻居进行加权,使邻近邻居更有利于拟合。这可以通过 weights ( 权重 )关键字来实现。默认值 weights = 'uniform' 为每个邻居分配均匀权重。 weight ='distance' 分配与查询点距离的倒数成比例的权重。或者,可以提供用于计算权重的用户定义的距离函数。

classification_1

classification_2

示例:

Nearest Neighbors Classification:使用最近邻分类的例子。

Nearest Neighbors Regression ( 最近邻回归 )

data labels ( 数据标签 ) 是 continuous ( 连续 ) 的而不是 discrete ( 离散 ) 的变量的情况下,可以使用 Neighbors-based regression ( 基于邻居的回归 ) 。分配给查询点的标签是根据其最近邻居的标签的平均值计算的。

scikit-learn 实现两个不同的 neighbors  ( 邻居 ) 回归: KNeighborsRegressor 根据每个查询点的 k 个最近邻实现学习,其中 k 是用户指定的整数值。 RadiusNeighborsRegressor 根据查询点的固定半径 r 内的邻居实现学习,其中 r 是用户指定的浮点值。
basic nearest neighbors regression ( 基本最近邻回归 ) 使用 uniform weights ( 均匀权重 ) :即,local neighborhood ( 本地邻域中 ) 的每个点对查询点的分类均一致。在某些情况下,加权点可能是有利的,使得附近点对远程点的贡献更多。这可以通过 weights ( 权重 ) 关键字来实现。默认值 weights = 'uniform' 为所有点分配相等的权重。 weight ='distance' 分配与查询点距离的倒数成比例的权重。或者,可以提供距离的用户定义的函数,其将用于计算权重。

使用 multi-output nearest neighbors ( 多输出最近邻 ) 进行回归,在使用 multi-output estimators ( 多输出估计器 ) 的面部完成中进行了演示。 在该示例中,输入 X 是面部的上半部分的像素,并且输出 Y 是这些面的下半部分的像素。

示例:

Nearest Neighbor Algorithms ( 最近邻算法 )

Brute Force

最近邻的快速计算是机器学习研究的一个活跃领域。最简单的 neighbor search ( 邻居搜索 ) 实现涉及数据集中所有点对之间的距离的强力计算:对于 D 维中的 N 个样本,该方法作为  进行比例。对于小数据样本,有效的 brute-force neighbors searches 可能非常有竞争力。然而,随着样本数量 N 的增长,brute-force 迅速变得不可行。在 sklearn.neighbors 中的类中,使用关键字 algorithm ='brute' 指定 brute-force neighbors searches ,并使用 sklearn.metrics.pairwise 中可用的例程来计算。

K-D Tree

为了解决 brute-force approach ( 强力方法 ) 的计算效率低下,已经发明了各种 tree-based ( 基于树 ) 的数据结构。通常,这些结构试图通过有效地编码样本的总距离信息来减少所需的距离计算数量。基本思想是,如果 A 点距 B 点很远,B 点非常接近 C 点,那么我们知道 A 点和 C 点非常遥远,而不必明确地计算它们的距离。以这种方式,最近邻搜索的计算成本可以减小到  或更好。这是对 brute-force for large N 的显着改善。
利用这种 aggregate information ( 聚合信息 ) 的早期方法是 KD 树数据结构(K 维树的简称),其将二维四叉树和三维十字树概括为任意数量的维度。 KD 树是二进制树结构,它沿着数据轴递归地划分参数空间,将其分割成数据点被归档到的嵌套原点区域。 KD 树的构造非常快:因为仅沿着数据轴执行分割,因此不需要计算 D 维距离。一旦构造,可以仅使用  距离计算来确定查询点的最近邻居。虽然KD树方法对于低维()邻居搜索来说非常快,但随着 D 增长非常大,它变得无效率:这是所谓的curse of dimensionality ( 维度惩罚 ) 的一种表现。在 scikit-learn 中,使用关键字 algorithm ='kd_tree' 指定 KD树 邻居搜索,并使用类 KDTree 计算。

参考:

Ball Tree

为了解决 KD 树在较高维度上的低效率,开发了 Ball Trees 数据结构。其中 KD 树沿 Cartesian axes ( 笛卡尔轴 ) 分割数据,ball tree 在一系列 nesting hyper-spheres ( 嵌套超球体 ) 中分割数据。这使得树构造比 KD 树的成本更高,但是导致数据结构对于高度结构化的数据可以是非常有效的,即使在非常高的维度上。

Ball Tree 将数据递归地划分为由质心 C 和半径 r 定义的节点,使得节点中的每个点位于由 r C 定义的超球体内。通过使用减少邻居搜索的候选点数量的三角不等式:

通过这种设置,测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限。由于ball tree 节点的球形几何,它可以在高维度上执行 KD 树,尽管实际的性能高度依赖于训练数据的结构。在 scikit-learn 中,使用关键字 algorithm ='ball_tree' 指定基于 ball tree 的邻居搜索,并使用类 sklearn.neighbors.BallTree 计算。或者,用户可以直接使用 BallTree 类。

参考:

Choice of Nearest Neighbors Algorithm ( 最近邻算法的选择 )

给定数据集的最优算法是一个复杂的选择,并且取决于多个因素:

  • 样本数 N ( 即 n_samples ) 和维数 D ( 即 n_features )
    • Brute force 查询时间如  增长
    • Ball tree 查询时间大致如  增长
    • KD tree 查询时间随着 D 的改变而难以精确地表征。对于小 D ( 小于 20 左右 ),成本约为  ,并且 KD tree 查询可以非常有效。对于较大的 D ,成本增加到接近  ,并且由于树结构导致的开销可以导致比 brute force 更慢的查询。
    对于小数据集 ( N 小于 30 左右 ), 与 N 相当。而 brute force algorithms 比 tree-based ( 基于树 ) 的方法更有效。 KDTreeBallTree 都通过提供一个 leaf size 参数来解决这个问题:它控制 query 切换到 brute-forcethe number of samples ( 样本数 ) 。这允许两种算法接近小 N 的 brute-force 计算的效率。
  • data structure ( 数据结构 ):数据的固有维度 and/or 数据的稀疏性。本征维数是指数据所在 data lies 的维度  ,可以线性或非线性地嵌入到参数空间中。稀疏性是指数据填充参数空间的程度(这与sparse 矩阵中使用的概念区分开来。数据矩阵可以没有零个条目,但是在这个数据矩阵中,结构仍然可以是sparse” sense )。
    • Brute force 查询时间不受数据结构的影响。
    • Ball treeKD tree 查询时间可能受数据结构的很大影响。通常,具有较小固有维数的稀疏数据导致更快的查询时间。因为 KD 树的内部表示与参数轴对齐,所以它通常不会像任意结构化数据的 Ball tree 一样显示出更多的改进。
    机器学习中使用的数据集往往非常结构化,非常适合 tree-based ( 基于树 ) 的查询。
  • 查询点请求的邻居数 k
    • Brute force 时间在很大程度上不受 k 值的影响。
    • 随着 k 增加, Ball treeKD tree 查询时间将变慢。这是由于两个因素:首先,较大的 k 导致需要搜索参数空间的较大部分。第二,使用  ,当树被遍历时,需要对结果进行内部 queueing ( 排队 ) 。
    由于 k 与 N 相比变大,所以减少了 tree-based ( 基于树 ) 的查询中修剪分支的能力。在这种情况下,Brute force 查询可以更有效率。
    • 查询点数。 ball tree KD tree 都需要 construction phase ( 架构阶段 ) 。这种架构的成本在 amortized over many queries ( 许多查询中摊销 ) 时可以忽略不计。然而,如果仅执行少量查询,则架构可以占成本的很大一部分。如果需要很少的查询点, brute forcetree-based ( 基于树 ) 的方法要好。

目前,如果  ,并且 'effective_metric_' 位于 'kd_tree' 'VALID_METRICS' 列表中,则 algorithm ='auto' 选择 'kd_tree' 。如果  ,并且 'effective_metric_' 不在 'kd_tree' 'VALID_METRICS' 列表中,则选择 'ball_tree' 。如果  ,则选择 “brute” 。这个选择是基于以下假设:查询点的数量至少与训练点数量相同,并且 leaf_size 接近其默认值 30

Effect of leaf_size ( leaf_size 的影响 )

如上所述,对于小样本量,brute force search ( 强力搜索 ) 可以比 tree-based ( 基于树 ) 的查询更有效。这个事实在 ball treeKD tree 中通过内部切换到叶节点内的 brute force searches ( 强力搜索 ) 来解释。此 switch ( 开关 ) level 可以用参数 leaf_size 指定。此参数选择有很多效果:

construction time

较大的 leaf_size 会导致更快的树构建时间,因为需要创建更少的节点

query time

一个大或小的 leaf_size 都可能导致 suboptimal query cost ( 次优查询成本 ) 。对于 leaf_size 接近 1 ,遍历节点所涉及的开销显著减慢查询时间。对于接近训练集大小的 leaf_size ,查询变得基本上是 brute force 。这些之间的一个很好的折中方法是 leaf_size = 30 ,参数的默认值。

memory

leaf_size 增加时,存储树结构所需的内存减少。在对于每个节点存储 D维 重心的 Ball tree 的情况下,这是特别重要的。 BallTree 所需的存储空间大约是 1/leaf_size 乘以训练集的大小。

没有为 brute force queries 引用 leaf_size 。 

Nearest Centroid Classifier ( 最近的中心分类器 )

NearestCentroid 分类器是一个简单的算法,它通过其成员的质心来表示每个类。实际上,这使得它类似于 sklearn.KMeans 算法的标签更新阶段。它也没有参数可供选择,使之成为良好的基准分类器。然而,它确实存在 non-convex classes ( 非凸型类 ) ,以及当类具有截然不同的方差时,假设在所有维度上均等。对于没有做出这一假设的更复杂的方法,参见线性判别分析( sklearn.discriminant_analysis.LinearDiscriminantAnalysis )和二次判别分析( sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis )。默认 NearestCentroid 的使用很简单:

>>> from sklearn.neighbors.nearest_centroid import NearestCentroid
>>> import numpy as np
>>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
>>> y = np.array([1, 1, 1, 2, 2, 2])
>>> clf = NearestCentroid()
>>> clf.fit(X, y)
NearestCentroid(metric='euclidean', shrink_threshold=None)
>>> print(clf.predict([[-0.8, -1]]))
[1]

Nearest Shrunken Centroid ( 最近的 Shrunken 中心 )

NearestCentroid 分类器具有 shrink_threshold 参数,该参数实现最近的缩小质心分类器。实际上,每个质心的每个特征的值除以该特征的类内方差。然后,通过 shrink_threshold 降低特征值。最值得注意的是,如果特定特征值越过零,则将其设置为零。实际上,这将删除该功能影响分类。这是有用的,例如,去除噪声特征。
在下面的例子中,使用小的收缩阈值将模型的准确度从 0.81 提高到 0.82

nearest_centroid_1

nearest_centroid_2

示例:

Approximate Nearest Neighbors ( 近似近邻 )

对于低维度 d (约 50 ),有许多有效的精确最近邻搜索算法。然而,当 d 增加时,这些算法在空间和查询时间方面表现不佳。这些算法没有比将查询点与高维数据库中的每个点进行比较(参见 “Brute Force” )更好。这是被称为 “The Curse of Dimensionality ( 维度惩罚 )” 的现象的一个众所周知的后果。
有一些应用程序,我们不需要确切的最近的邻居,但有一个good guess ( 好的猜测 )” 就足够了。当答案不一定要准确时,LSHForest 类实现近似最近邻搜索。大概的最近邻搜索方法被设计为通过高维数据来加快查询时间。当目标是表征邻域而不是识别确切的邻居本身(例如:k-最近邻分类和回归)时,这些技术是有用的。一些最流行的近似最近邻搜索技术是局部敏感散列,最佳二进制拟合和 box-decomposition ( 平衡盒分解树 ) 搜索。

Locality Sensitive Hashing Forest ( 地点敏感的哈希森林 )

locality sensitive hashing ( 地点敏感散列 ) 的 vanilla 实现具有在实践中难以调整的 hyper-parameter ( 超参数 ) ,因此 scikit-learn 实现了一种称为 LSHForest 的变体,具有更合理的 hyper-parameter ( 超参数 ) 。两种方法都使用内部随机超平面将样本索引到存储桶中,并且仅针对与查询冲突的样本计算实际余弦相似度,从而实现子线性缩放。 (参见位置敏感哈希的数学描述)。
LSHForest 有两个主要的超参数:n_estimatorn_candidates 。可以使用以下曲线所示的这些参数来控制查询的准确性:

作为经验法则,用户可以将 n_estimator 设置为足够大的值(例如,1050 之间),然后调整 n_candidates 以便查询时间的准确性。
对于小数据集,精确最近邻搜索的 brute force 可以比 LSH Forest 更快。 然而, LSH Forest 具有索引大小的子线性查询时间可伸缩性。 LSH Forest 查询变得比强力更快的确切突破点取决于数据集的维度,结构,所需精度级别,运行时环境的特征,如 BLAS 优化的可用性,CPU 核心数量和CPU 大小缓存。 以下图表描述了具有索引大小的 LSHForest 查询的可伸缩性。

对于固定的 LSHForest 参数,查询的准确性往往随较大的数据集而慢慢下降。 以前绘图中的误差条表示不同查询的标准偏差。

示例:

Mathematical description of Locality Sensitive Hashing ( 局部敏感哈希的数学描述 )

 Locality sensitive hashing ( 局部敏感散列 ) ( LSH ) 技术已被用于在大尺度上进行最近邻搜索的许多领域。 LSH 背后的主要概念是使用多个(通常是简单的)散列函数对数据库中的每个数据点进行散列以形成 digest  ( 摘要 )(也称为 hash ( 散列 ))。在这一点上,collision - 两个对象具有相似的摘要 - 对于彼此接近的点远远高于远点。我们将哈希函数族的要求描述为如下所述的 locality sensitive ( 局部敏感度 ) 
domain S 到 range U 的函数的family H 被称为(r, e , p1 , p2 )-sensitive( 敏感 ),如果对于 满足以下条件( D 为距离功能):

  • 如果  则 
  • 如果  则 

根据定义,在距离 r 的距离内的附近点可能与概率 p_1 相冲突。相比之下,距离超过  的距离较远的点 p_2 的碰撞概率很小。假设有一个 LSH 函数系列H 。一个 LSH 索引建立如下:

  1. 选择 k个函数 随机(随替换)从 H 。对于,将 p放在桶中,标签为 。注意,如果每个 h_i输出一个 “digit” ,则每个桶都有一个 k-digit label  ( k位标签 )
  2. 独立地执行步骤1 l次以构造 l个单独的估计器,具有散列函数

在步骤1中连接散列函数的原因是尽可能地减少远处点的碰撞概率。概率从 p_2 下降到  ,对于大 k 而言可以忽略不计。 k 的选择强烈依赖于数据集的大小和结构,因此在实践中很难调整。有一个很大的 k 的副作用;它有可能减少附近点的相互碰撞的机会。为了解决这个问题,在步骤2中构建了多个估计器。
调整给定数据集 k 的要求使得经典的 LSH 在 实践中麻烦使用。 LSH 森林变种通过自动调整用于散列样本的位数来设计,以减轻这一要求。
LSH Forest 使用前缀树进行配置,树的每个叶对应于数据库中的实际数据点。有 l 个这样的树组成森林,它们是使用独立绘制的哈希函数的随机序列构建的。在这个实现中, “Random Projections” 被用作 LSH 技术,它是余弦距离的近似值。哈希函数序列的长度保持固定为 32 。此外,使用排序的数组和二进制搜索来实现前缀树。
为了回答查询以找到点 q 的 m 个最近邻居,使用了树遍历的两个阶段。首先,使用二进制搜索来执行自顶向下的遍历,以便在对 q 进行相同的散列函数之后,使用 q 的标签来识别具有最长前缀匹配(最大深度)的叶子。   点(total candidates ( 总候选人 ) )从森林中提取,从以前发现的最大深度向上同步跨越所有自下而上遍历的树。被设置为 cl ,其中 c ,从每棵树中提取的候选数是一个常数。最后,计算出每个这些 M 点与点 q 的相似度,并返回顶点 m 点作为q 的最近邻。由于这些查询中大部分时间用于计算候选人的距离,因此与 brute force 搜索相比的加速大约是  ,其中 N 是数据库中的点数。

参考:

 

 

  • 无标签