sklearn 笔记 BallTree/KD Tree

由NearestNeighbors类包装

1 主要使用方法

sklearn.neighbors.BallTree(X, leaf_size=40, metric='minkowski', **kwargs)

2 主要方法

2.1 get_arrays

import numpy as np
from sklearn.neighbors import BallTree
X = np.random.random((10, 3))
tree = BallTree(X)                
tree.get_arrays()
 
'''
(array([[0.90651098, 0.68471698, 0.6299996 ],
        [0.82751465, 0.31739009, 0.61572299],
        [0.22778906, 0.63614041, 0.73672184],
        [0.64655758, 0.9729849 , 0.68232389],
        [0.94992886, 0.72604933, 0.45649069],
        [0.34932115, 0.95985124, 0.41451989],
        [0.45131894, 0.21650206, 0.82466273],
        [0.87047096, 0.48403116, 0.58119046],
        [0.94468825, 0.14985636, 0.12132986],
        [0.62717326, 0.12924198, 0.23928098]]),
 array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], dtype=int64),
 array([(0, 10, 1, 0.61638879)],
       dtype=[('idx_start', '
 array([[[0.68012737, 0.52767645, 0.53022429]]]))
'''

• 返回了4个数组

  • 第一个数组：原始数据点数组

  • 第二个数组：整数数组，代表每个点的索引

  • 第三个数组：结构化数组，包含了 BallTree 的内部树结构的信息

    • idx_start 和 idx_end：定义了存储在当前节点的点的索引范围。
    • is_leaf：表明当前节点是否是叶节点。
    • radius：当前节点中所有点到节点中心点的最大距离
  • 第四个数组：树的每个节点的中心点

2.2 get_tree_stats

获取 BallTree 的状态信息：树的剪枝次数、叶节点的数量、分裂次数

2.3 query

查询树以找到 k 个最近邻居

query(X, k=1, return_distance=True, dualtree=False, breadth_first=False)

import numpy as np
from sklearn.neighbors import BallTree
X = np.random.random((100, 3))
tree = BallTree(X)                
tree.query(X[:3],k=3)
'''
(array([[0.        , 0.08335798, 0.15625817],
        [0.        , 0.06843236, 0.10825558],
        [0.        , 0.0968137 , 0.10245125]]),
 array([[ 0, 59, 88],
        [ 1, 70,  5],
        [ 2, 43, 20]], dtype=int64))
'''

2.4 query_radius

• 进行半径查询的功能
• 查询树，以找出在指定半径 r 内的邻居点

query_radius(X, r, return_distance=False, count_only=False, sort_results=False)

import numpy as np
from sklearn.neighbors import BallTree
X = np.random.random((100, 3))
tree = BallTree(X)                
tree.query_radius(X[:3],r=0.3)
'''
array([array([ 0, 68, 11, 31, 46, 19, 36, 63, 16, 86, 79], dtype=int64),
       array([26, 64, 20, 94,  1,  4, 13,  3], dtype=int64),
       array([35, 50, 30, 83, 85, 18, 15, 53,  2, 96, 81], dtype=int64)],
      dtype=object)
'''

2.5 two_point_correlation

计算距离小于等于r[i]的点的数量

two_point_correlation(X, r, dualtree=False)

返回值

counts (ndarray): counts[i] 包含距离小于或等于 r[i] 的点对数

import numpy as np
from sklearn.neighbors import BallTree
X = np.random.random((100, 3))
r=np.linspace(0.1,1,5)
tree = BallTree(X)                
tree.two_point_correlation(X[:3],r=r)
#array([  4,  34,  99, 196, 263], dtype=int64)
'''
返回的第一个值：和X[0]的距离小于r[0]的数量+和X[1]的距离小于r[0]的数量+和X[2]的距离小于r[0]的数量
'''

3 KD-Tree

和Ball-Tree 一模一样