K近邻模型的3个要素

1.距离度量（如欧式距离）
2.k值的选择
3.分类决策规则（如多数表决）

线性搜索时间复杂度较高，因而引入了KD树这一数据结构，加快搜索。

构造KD树

如果实例点是随是随机分布的，kd树搜索复杂度是O(logN)，这里N是训练实例数，kd树更适合于训练实例数远大于空间维数时的k近邻搜索。
当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描