「算法」 Ball Tree
KD 树对于低维度 (D<20) 的近邻搜索非常快, 当 D 增长到很大时, 效率变低；这就是所谓的 “维度灾难” 的一种体现；KD 树只能处理欧式距离；
为了解决 KD 树在高维上效率低下的问题, ball 树 应运而生，同时 Ball tree 可处理一般的距离；
一、Ball-Tree
1. 介绍
KD 树沿卡迪尔轴（即坐标轴）分割数据, ball 树在沿着一系列的超球面（hyper-spheres）来分割数据. 构建树时要比 KD 树耗时, 但是他对于高结构化的数据是非常有效的, 即使在高维度上也是一样；
ball 树将数据递归地划分为由质心 C 和半径 r 定义的节点,使得节点中的每个点位于由 r 和 C 定义的 hyper-sphere 内. 通过使用三角不等式（triangle inequality）|x+y|<=|x|+|y| / \Vert x - y \Vert + \Vert y - z \Vert \ge \Vert x - z \Vert 减少近邻搜索的候选点数；计算测试点和质心之间的距离就足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点是球形几何, 它在高维度上的性能超出 KD-tree, 尽管实际的性能高度依赖于训练数据的结构；为什么球形就适应高维 为什么说实际性能以来与训练数据的结构
2. 原理
对于目标空间 (q, r) ，所有被该超球体截断的子超球体内的所有子空间都将被遍历搜索；
3. 应用
二、Ball-Tree 运算
1. 创建
2. 删除
3. 修改
4. 平衡
5. 查找-最邻近搜索
三、实践
三、思考
四、扩展
附录
A. KD-Tree 的创建方法
B. 资料
nonparametric classification](http://www.jmlr.org/papers/volume7/liu06a/liu06a.pdf). JMLR 7, 1135–1158 (2006).
[^3]: Omohundro, S.M.: Five balltree construction algorithms. Tech. rep., ICSI Berkeley
(1989).
Comments