k 近邻（knn）是一种很简单的分类算法，它的基本原理是：给定一个实例点，然后在所有的数据中找到与该实例点距离最近的 k 个样本，最后选择 k 个样本中出现最多的分类标记作为实例点的分类预测结果。
下面这个视频比较清晰地说明了 knn 是如何工作的：How kNN algorithm works - YouTube
基本的原理很简单，所以它很“懒”，是“懒惰学习”代表，它遗留了两个问题给我们思考：
- k 值如何选择？
- k 值的选择不能过小，否则实例点会对自己周边的点异常敏感，容易过拟合
- k 值的选取也不能过大，容易产生较大的误差
- 一般选择一个合适的 k 值，用交叉验证法择优选取
- 如何定义实例点与样本点之间的距离？
- 欧式距离
- $L_p$距离，p=1时为曼哈顿距离
- 闵可夫斯基（Minkowski） 距离
- 如何快速找到实例点距离最近的 k 个样本？
关于问题 3 的回答，kd 树是 knn 的实现算法之一，参考【数学】kd 树算法之详细篇
