1、KNN算法原理
KNN算法是选择与输入样本在特征空间内最近邻的k个训练样本，并根据一定的决策规则，给出输出结果 。常见的决策规则：分类任务，取前k个样本中类别最多的那张；回归任务，取前k个样本的平均值作为输出结果。

2、KNN算法三要素
KNN算法的三要素是，k值的选择，距离度量方法，决策规则。三要素一旦确定，对于一个输入样本而言，其输出也就是固定的。

（1）k值的选择。k值选择小时，模型复杂度高，训练误差小，泛化误差大；k值选择大时，模型复杂度小，训练误差大，泛化误差小。KNN模型对噪声越敏感，模型复杂度就越高。

（2）距离度量。常用的度量距离的方法，欧式距离，曼哈顿距离，闵可夫斯基距离。

（3）决策规划。KNN算法一般是用多数表决方法，即由输入实例的K个邻近的多数类决定输入实例的类。这种思想也是经验风险最小化的结果。

3、KNN算法暴力搜索实现
暴力搜索（brute-force search）是线性扫描输入实例与每一个训练实例的距离并选择前k个最近邻的样本来进行决策规划。这种算法简单，但是当训练集或特征维度很大时，计算非常耗时。

4、KNN算法kd树实现
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构，构造kd树相当于不断用垂直于坐标轴的超平面将k维空间进行划分，构成一系列的K维超矩形区域，kd树省去了对大部分数据的搜索，大大的较少了计算量。