扫码加入数据分析学习群

对于给定数据集，K近邻的最优算法选择（algorithm）取决于多个因素：

• 样本数量N 和 维度D：

1. brute force 查询时间以O[DN]增长。
2. ball tree 查询时间大约以O[Dlog(N)]增长。
3. k-d tree 的查询时间变化是很难精确描述的，对于较小的D(小于20)的成本大约是O[Dlog(N)]，并且 k-d tree 更加有效。对于较大的D成本的增加接近O[DN]，由于树结构引起的开销会使得查询效率比 brute forse 还要低。

对于小数据集 (N小于30)，log(N)相当于N，brute forse 暴力算法比基于树的算法更加有效。

• 数据结构：

1. brute force 时间不受数据结构的影响。
2. ball tree 和 k-d tree 的数据结构对查询时间影响很大。一般地，小维度的 sparser (稀疏) 数据会使查询更快。因为 k-d tree 的内部表现形式是与参数轴对齐的，对于任意的结构化数据它通常不会表现的像 ball tree 那样好。

• query point（查询点）所需的近邻数 K：

1. brute force 查询时间几乎不受 K 值的影响。
2. ball tree 和 k-d tree 的查询时间会随着 K 的增加而变慢。这是由于两个影响: 首先，K 的值越大在参数空间中搜索的部分就越大。其次, 使用 K>1 进行树的遍历时, 需要对内部结果进行排序。

当 K 相比 N 变大时, 在基于树的查询中修剪树枝的能力是减弱的。在这种情况下, 暴力查询会更加有效。

• query points（查询点）数：

ball tree 和 k-d tree 都需要一个构建阶段。在许多查询中分摊时，这种结构的成本可以忽略不计。如果只执行少量的查询，可是构建成本却占总成本的很大一部分。如果仅需查询很少的点，暴力方法会比基于树的方法更好。