1. 算法
KNN算法也是使用距离来衡量样本点之间的相似性，但其与Kmeans中的K含义不同。
KNN的决策过程：
1、计算测试集样本点到训练集中每个样本点的距离
2、按照距离的远近排序
3、选取与当前测试样本最近的K个训练样本，作为该测试样本的邻居
4、统计这K个邻居的类别频率，即为该测试样本的类别
如果每个测试样本点都要计算一遍到所有训练集的距离，再加上排序，时间复杂度为o(Bn*Tn*ln(Bn))，因此一般使用kd树来降低时间复杂度，建树时间复杂度为o(n)，具体参考文末链接。
2. 优缺点
2.1、优点：
理论成熟，思想简单，既可以用来做分类也可以用来做回归；
可用于非线性分类；
训练时间复杂度为O(n)；
对数据没有假设，准确度高，对outlier（异常值）不敏感；
2.2、缺点
属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离
样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差，可以调整样本权值改善
可解释性差，无法给出类似决策树那样的规则
向量的维度越高，欧式距离的区分能力就越弱
样本空间太大不适合，因为计算量太大，预测缓慢
需要大量的内存；
在训练集较小时，泛化能力很差，非常容易陷入过拟合。
无法判断特征的重要性。
链接
k近邻法的原理与实现
https://blog.csdn.net/beckham999221/article/details/80135042
https://blog.csdn.net/weixin_44508906/article/details/90116509
KD树简介
https://zhuanlan.zhihu.com/p/53826008
KNN算法和kd树详解（例子+图示）（例子最详细）
