KNN算法优缺点
- 优点
(1) 精度高
(2) 对异常值不敏感：某个异常值对整个结果不造成影响；
(3) 无数据输入假定：无数据的独立性等假设； - 缺点
(1) 计算复杂度高：因为要计算的点需要与所有点计算距离，所以复杂度很高；
(2) 空间复杂度高：因为需要加载所有的样本；
适应的数据范围
- 数值型和标称型（是或者否）
算法原理
K值选择
- 如果选择较小的K值
– 近似误差会减小（针对训练集），估计误差会增大（针对测试集或验证集）；
– 对噪声比较敏感；
– 容易过拟合（模型复杂），泛化能力差； - 如果选择较大的K值
– 近似误差增大，估计误差会减小；
– 整体模型变得简单；
距离选择
- 欧式距离：对异常值更敏感
- 曼哈顿距离
- 马氏距离：可以消除样本间的相关性，协方差矩阵可以降低样本差异性；
算法改进
- KD树
– 对K维空间的实例点进行存储以便快速检索；
– 是二叉树，相当于不断用垂直与坐标轴的超平面将K维空间切分构成一系列K维超矩形区域； - 例子
以中值作为切割点，对x轴从小到大排序
(2,3), (4,7), (5,4), (7,2), (8,1), (9,6) 此时x轴的中值位置为(7,2)；(2,3), (4,7), (5,4)作为左节点，(8,1), (9,4)作为右节点，分别对y轴切分； - 最终树结构如下：
- kd树查找（假设查找(2,4.5)节点）
通过KD树，找到最后一个叶子节点为(4,7)，与目标查找点的距离为3.202；回溯到根节点(5,4)，计算其与查找点之间的距离为3.041，小于3.202，所以“当前最近邻点”变成（5,4）；
以目标点（2,4.5）为圆心，以目标点（2,4.5）到“当前最近邻点”（5,4）的距离（即3.041）为半径作圆，如上图所示。可见该圆和y = 4超平面相交，所以需要进入（5,4）左子空间进行查找，即回溯至（2,3）叶子节点；
（2,3）距离（2,4.5）比（5,4）要近，所以“当前最近邻点”更新为（2,3），最近距离更新为1.5；
再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。 - 外部库使用（sklearn）