http://blog.csdn.net/pipisorry/article/details/53156836

ball tree

k-d tree也有问题[最近邻查找算法kd-tree ]。矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图6中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。为了解决上面的问题，我们引入了ball tree。

ball tree

解决上面问题的方案就是使用超球面而不是超矩形划分区域。使用球面可能会造成球面间的重叠，但却没有关系。ball tree就是一个k维超球面来覆盖这些观测点，把它们放到树里面。图7（a)显示了一个2维平面包含16个观测实例的图,图7（b）是其对应的ball tree，其中结点中的数字表示包含的观测点数。

   

                   图 7  ball tree对二维平面的划分和ball tree

不同层次的圆被用不同的风格画出。树中的每个结点对应一个圆，结点的数字表示该区域保含的观测点数，但不一定就是图中该区域囊括的点数，因为有重叠的情况，并且一个观测点只能属于一个区域。实际的ball tree的结点保存圆心和半径。叶子结点保存它包含的观测点。
    使用ball tree时，先自上而下找到包含target的叶子结点，从此结点中找到离它最近的观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离大于这个圆的圆心加上前面的上界的值，则这个兄弟结点不可能包含所要的观测点。（如图8）否则，检查这个兄弟结点是否包含符合条件的观测点。

 

    图 8 点与超圆
    那么，ball tree的分割算法是什么呢？
    选择一个距离当前圆心最远的观测点i1，和距离i1最远的观测点 i2，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。
    与k-d tree一样，如果结点包含的观测点到达了预先设定的最小值，这个顶点就可以不再分割了。

[【机器学习】K-means聚类算法初探 ]

kdtree和balltree的区别和联系

个人见解，
kd-tree基于欧氏距离的特性：
balltree基于更一般的距离特性：
因此：
kd-tree只能用于欧氏距离，并且处理高维数据效果不佳。
balltree在kd-tree能够处理的数据范围内要慢于kd-tree。

皮皮blog

sklearn中使用kdtree和balltree

这个库的tree实现不太好，输入的数据会转换成ndarray，输出也是ndarray，这样就没办法传递附加数据了。。。也是烦人。。。

参数训练

KDTree(X, leaf_size=40, metric=’minkowski’, **kwargs)

BallTree(X, leaf_size=40, metric=’minkowski’, **kwargs)

参数解释

X : array-like, shape = [n_samples, n_features] 但也可以是dataframe类型（只要输入原始df数据的float类型的列（或者提前转换成）就可以）

leaf_size : positive integer (default = 40)
改变leaf_size不会改变查询结果，但是会显著影响查询速度（其实应该也包含训练速度吧）和存储内存。The amount of memory needed to store the tree scales as approximately n_samples / leaf_size.

metric : string or DistanceMetric object 用于树的距离度量：the distance metric to use for the tree. Default=’minkowski’with p=2 (that is, a euclidean metric). See the documentationof the DistanceMetric class for a list of available metrics.ball_tree.valid_metrics gives a list of the metrics whichare valid for BallTree.

查看可用的度量方法

from sklearn import neighbors

neighbors.KDTree.valid_metrics

['chebyshev',
 'manhattan',
 'infinity',
 'p',
 'l1',
 'cityblock',
 'euclidean',
 'minkowski',
 'l2']

[sklearn距离度量函数[sklearn.neighbors.DistanceMetric¶]

近邻查找

query(X[, k, return_distance, dualtree, ...])	query the tree for the k nearest neighbors
query_radius	query_radius(self, X, r, count_only = False)

Note:

1 query查询时返回的是距离和下标，下标对应的是输入的原始数据的下标，所以原始数据可以附加很多字段（只是不输入到树的构建数据中）就可以了。

2 lz测试时发现每次query查询时都会调用距离度量函数。

query

dist, inds = loc_kdtree.query(l_array[0].reshape(1, -1), k=5)

query返回值是距离（这里的数值就是metrics计算出来的那个数值）和samples的下标。

Note: 要注意的是index返回的是一个二维数组，第个一维数组元素对应的是一个查询的近邻结果。所以如果训练数据直接调用l_array[inds]返回的是一个三维数组，只查询一个二维数据的近邻时应该使用l_array[inds[0]]。

i : array of integers - shape: x.shape[:-1] + (k,). each entry gives the list of indices ofneighbors of the corresponding point.

query_radius半径查找

默认只返回index：ind = tree.query_radius(X[0], r=0.3)

count : if count_only == True

ind : if count_only == False and return_distance == False

(ind, dist) : if count_only == False and return_distance == True. 注意返回顺序还和query还不一样。。。

count : array of integers, shape = X.shape[:-1]  each entry gives the number of neighbors withina distance r of the corresponding point.

其它参数及其含义

# variables to keep track of building & querying stats
    cdef int n_trims
    cdef int n_leaves
    cdef int n_splits
    cdef int n_calls

    def get_tree_stats(self):
        return (self.n_trims, self.n_leaves, self.n_splits)

    def reset_n_calls(self):
        self.n_calls = 0

    def get_n_calls(self):
        return self.n_calls

    def get_arrays(self):
        return (self.data_arr, self.idx_array_arr,
self.node_data_arr, self.node_bounds_arr)

[scikit-learn/sklearn/neighbors/binary_tree.pxi]

皮皮blog

kdtree实现时的错误

还有一个坑就是sklearn版本问题，本地错误解决，放到服务器上远程跑还是出错，发现从0.18升级到0.18.1就不会报错了，也是醉了。。。

ValueError: metric PyFuncDistance is not valid for KDTree

    The ball tree works with any of the following distance metrics, which match those found in the module scipy.spatial.distance:['euclidean', 'minkowski', 'manhattan', 'chebyshev',  'seuclidean', 'mahalanobis', 'wminkowski', 'hamming',  'canberra', 'braycurtis', 'matching', 'jaccard',  'dice', 'kulsinski', 'rogerstanimoto', 'russellrao',  'sokalmichener', 'sokalsneath', 'haversine']
Alternatively, the user can specify a callable Python function to act as the distance metric. While this will be quite a bit slower than using one of the optimized metrics above, it adds nice flexibility.
    The kd-tree works with only the first four of the above metrics. This limitation is primarily because the distance bounds are less efficiently calculated for metrics which are not axis-aligned.

[Benchmarking Nearest Neighbor Searches in Python]

直接将metric写成一个函数会出错，因为metric参数接受的类型为：string or DistanceMetric object

loc_kdtree = neighbors.KDTree(l_array, metric=lambda i, j: distance.vincenty(tuple(i), tuple(j)).miles)

        if callable(metric):
            if algorithm == 'kd_tree':
                # callable metric is only valid for brute force and ball_tree
                raise ValueError(
                    "kd_tree algorithm does not support callable metric '%s'" % metric)
        elif metric not in VALID_METRICS[alg_check]:
            raise ValueError("Metric '%s' not valid for algorithm '%s'" % (metric, algorithm))

ValueError: func must be a callable taking two arrays

[Sklearn kNN usage with a user defined metric]

[Sklearn kNN usage with a user defined metric (again)]

[Sklearn kNN usage with a user defined metric]

TypeError: __init__() takes exactly 1 positional argument (0 given)

参数是func=lambda不是pyfunc=lambda

loc_kdtree = neighbors.KDTree(l_array, metric='pyfunc', func=lambda i, j: distance.vincenty(i, j).miles)

或者loc_kdtree = neighbors.KDTree(l_array, metric=neighbors.DistanceMetric.get_metric('pyfunc',func=lambda i, j: distance.vincenty(i, j).miles))

ValueError: Buffer has wrong number of dimensions (expected 2, got 1)

用于训练的数据应该是二维的，如果输入的是一维的列表什么的，可以在外面加一个[]号。

sklearn Deprecation Warning

Deprecation Warning: Passing 1d arrays as data is deprecated in 0.17 and will raise ValueError in 0.19

出错问题：

分类器分类预测时：clf.predict([1, 1])

最近邻查询时：kdtree.query(l_array[0])...

原因：输入的预测或者查询不是二维的而是一维的

解决：改成二维的：clf.predict([[1, 1]]), kdtree.query([l_array[0]])

Note: 这个warning有点坑啊，应该可以通过修复sklearn代码解决吧。

[Getting deprecation warning in Sklearn over 1d array, despite not having a 1D array]

皮皮blog

最近邻查找的应用

[Is a kd-tree suitable for 4D space-time data (x,y,z,time)?]

[Datetime as a dimension in python KDTree]

from: http://blog.csdn.net/pipisorry/article/details/53156836

ref: [scikit-learn modules 1.6. Nearest Neighbors]

[scikit-learn/sklearn/neighbors/]