KNN（K最近邻）算法：主要思想、例子案例
KNN算法的主要思想是将需要分类的数据与训练数据进行对比，在事先指定的范围内，在训练数据中找到与待分类的数据距离最近的训练数据，再根据这些数据的类别，将待分类的数据记录并归到最可能的类别中。前提是训练数据的分类必须已知；事先指定的范围可以是最相似数据的个数阈值K，也可以是以一定距离R为半径的圆周值；数据之间的相似程度一般使用欧式距离度量。
图3-12所示的是KNN算法的例子。
图3-12
这里通过欧式距离计算出点与点之间的距离，圆形点代表待分类的数据，矩形点与三角形点代表训练数据中已经被分成两类的数据。可以看出，在指定半径1中，三角形点的个数比矩形点的个数多1个，KNN算法会将圆形点分到三角形点一类中；在指定半径2中，矩形点比三角形点的个数多1个，所以KNN算法会将圆形点分到矩形点一类中。
使用KNN算法时会存在一些假设。首先，假设相同类型的点拥有同样的行为，其次，假设需要分类的点会做与其邻居相同的事情。如果这些假设条件不满足，那么KNN算法的效果也会大打折扣。
另外，把KNN算法归为基本的数据挖掘技术，是因为KNN算法本身并不是一个可以自行学习的算法，它只是机械地计算与周围邻居的距离，所以这个算法本身的效率比较低。比如，最开始的数据集有100万条数据，对于一条待分类的数据，KNN算法会计算其与所有100万条数据的距离，然后进行排序，取前K个邻居，再进行类别判断。对于下一条待分类的数据也是如此计算。
不过，KNN 算法可以明显提升模型的预测效果。还是用前面提到的杂志社的例子，可以看到，和Naive Predictions方法相比，除房屋杂志和运动杂志的预测结果的准确度一般外，其他杂志的预测结果的准确度都有大幅提升，如图3-13所示。
图3-13
