扫码加入数据分析学习群

Nearest Neighbor Algorithms

最近邻算法的选择可通过关键字‘algorithm’来控制，其参数有[‘auto’，‘brute’，‘kd_tree’，‘ball_tree’]，默认使用‘auto’时算法尝试从训练数据中确定最佳方法。

• Brute Force

brute forse也称暴力计算， 是最简单的近邻搜索的实现，即数据集中所有成对点之间距离的暴力计算，对于D维度中的N个样本来说，这个方法的复杂度是O[DN²]。 在小数据样本中，暴力近邻搜索是非常高效的。然而随着样本数N的增长，暴力计算方法很快变得不切实际了。

• K-D Tree

为了解决效率低下的暴力计算方法，已经发明了大量的基于树的数据结构。k-d tree的基本思想是 若A点距离B点非常远，B点距离C点非常近，可知A点与C点很遥远，不需要明确计算它们的距离。通过这种方式，近邻搜索的计算成本可以降低为O[DNlog(N)]或更低。这对于暴力搜索在大样本数N中表现的显著改善。

• Ball Tree

为了解决 k-d tree在高维数据上效率低下的问题，ball tree数据结构就被研发出来了。其中 k-d tree沿卡迪尔轴（即坐标轴）分割数据，ball tree在沿着一系列的超维球来分割数据。通过这种方法构建的树要比 k-d tree消耗更多的时间，但是这种方法对于高结构化的数据是非常有效的，即使在高维度上也是一样。