1 最近邻

class sklearn.neighbors.NearestNeighbors(*, n_neighbors=5, radius=1.0, algorithm='auto', leaf_size=30, metric='minkowski', p=2, metric_params=None, n_jobs=None)
  • 邻居搜索算法的选择通过关键字 ‘algorithm’ 控制，它必须是 [‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’] 中的一个。当传递默认值 ‘auto’ 时，算法尝试从训练数据中确定最佳方法。

2 主要参数

n_neighbors查询多少个邻居
radius用于 radius_neighbors 查询的参数空间范围
algorithm

({‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, 默认为 ‘auto’): 用于计算最近邻居的算法：

  • ‘ball_tree’ 将使用 BallTree。
  • ‘kd_tree’ 将使用 KDTree。
  • ‘brute’ 将使用暴力搜索。
  • ‘auto’ 将尝试基于传递给 fit 方法的值决定最合适的算法。
leaf_size

传递给 BallTree 或 KDTree 的叶子大小

这可以影响树的构建和查询速度，以及存储树所需的内存

metric用于距离计算的度量。默认为 “minkowski”，当 p = 2 时，结果为标准欧几里得距离

3 主要方法

3.1kneighbors

  • 寻找一个点的 K 个最近邻居。它返回每个点的邻居的索引和到邻居的距离

参数：

X查询点或点集
n_neighbors（int）每个样本所需的邻居数量
return_distance（bool）是否返回距离

返回值：

neigh_dist

(n_queries, n_neighbors)的ndarry

到点的距离的数组，仅当 return_distance=True 时存在

neigh_ind

(n_queries, n_neighbors)

最近点的索引

举例：

samples = [[0., 0., 0.], [0., .5, 0.], [1., 1., .5]]from sklearn.neighbors import NearestNeighborsneigh = NearestNeighbors(n_neighbors=2)neigh.fit(samples)neigh.kneighbors([[1., 1., 1.]],n_neighbors=1)#(array([[0.5]]), array([[2]], dtype=int64))

3.1.1 kneighbors中的n_neighbors和NearestNeighbors的区别是什么？

  • NearestNeighbors中的是默认的全局设置
  • kneighbors中的是仅限于特定方法调用的局部设置，如果在方法调用中指定了 n_neighbors，它将优先于构造函数中指定的值

3.2kneighbors_graph

kneighbors_graph(X=None, n_neighbors=None, mode='connectivity')

参数：

X查询点或点集
n_neighbors每个样本的邻居数量
mode

({‘connectivity’, ‘distance’}, 默认为 ‘connectivity’)

返回矩阵的类型：

  • ‘connectivity’ 将返回带有 0 和 1 的连通性矩阵
  • 在 ‘distance’ 模式下，边是点之间的距离，距离的类型取决于在 NearestNeighbors 类中选择的度量参数

返回一个稀疏矩阵

samples = [[0., 0., 0.], [0., .5, 0.], [1., 1., .5]]from sklearn.neighbors import NearestNeighborsneigh = NearestNeighbors(n_neighbors=2)neigh.fit(samples)neigh.kneighbors_graph([[1., 1., 1.]]).toarray()#array([[0., 1., 1.]])#和后两个相连，和第一个不连

3.3radius_neighbors

radius_neighbors(X=None, radius=None, return_distance=True, sort_results=False)

找到一个点或多个点周围给定半径内的邻居

返回每个点从数据集中位于查询数组点周围大小为半径的球内的点的索引和距离。位于边界上的点也包括在结果中

参数：

X查询点或点集
radius返回邻居的限制距离
return_distance(bool，默认为True):是否返回距离
sort_results

(bool，默认为False)

如果为 True，距离和索引将在返回前按距离递增排序

返回

neigh_dist到每个点的距离的数组
neigh_ind索引数组
import numpy as npsamples = [[0., 0., 0.], [0., .5, 0.], [1., 1., .5]]from sklearn.neighbors import NearestNeighborsneigh = NearestNeighbors(radius=1.2,n_neighbors=2)neigh.fit(samples)neigh.radius_neighbors([[1., 1., 1.]])'''(array([array([0.5])], dtype=object), array([array([2], dtype=int64)], dtype=object))'''

虽然n_neighbors也是2，但是举例卡在1.2，所以返回的也只有一个

3.4radius_neighbors_graph

和neighbors_graph类似，在radius限制下的neighbors_graph

4 最近邻算法的选择

4.1 样本数量和维度

4.2数据结构

4.3查询点的邻居数量

4.4查询点的数量

  • Ball 树和 KD 树需要一个构建阶段。当在许多查询中摊销时，这种构建的成本可以忽略不计。然而，如果只进行少量查询，构建可能占总成本的显著部分。如果查询点非常少，暴力搜索可能比基于树的方法更好。