KNN 的工作原理
k-NearestNeighbor，邻近算法
1. 计算待分类物体与其他物体之间的距离；
2. 统计距离最近的 K 个邻居；
3. 对于 K 个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。
K值的选取很重要，K太小，容易过拟合；K太大，虽然鲁棒性更强，但是会产生欠拟合。一般采用交叉验证的方式选取 K 值。把样本集中的大部分样本作为训练集，剩余的小部分样本用于预测，来验证分类模型的准确性。所以在 KNN 算法中，我们一般会把 K 值选取在较小的范围内，同时在验证集上准确率最高的那一个最终确定作为 K 值。
距离的计算方式有下面五种方式：
1. 欧氏距离，最常用的
2. 曼哈顿距离，在几何空间中用的比较多。以下图为例，绿色的直线代表两点之间的欧式距离，而红色和黄色的线为两点的曼哈顿距离。所以曼哈顿距离等于两个点在坐标系上绝对轴距总和。用公式表示就是：
3. 闵可夫斯基距离，其中 p 代表空间的维数，当 p=1 时，就是曼哈顿距离；当 p=2 时，就是欧氏距离；当p→∞时，就是切比雪夫距离。
4. 切比雪夫距离，二个点之间的切比雪夫距离就是这两个点坐标数值差的绝对值的最大值，用数学表示就是：max(|x1-y1|,|x2-y2|)。
5. 余弦距离。计算两个向量的夹角，是在方向上计算两者之间的差异，对绝对数值不敏感。在兴趣相关性比较上，角度关系比距离的绝对值更重要，因此余弦距离可以用于衡量用户对内容兴趣的区分度。比如我们用搜索引擎搜索某个关键词，它还会给你推荐其它的相关搜索，这些推荐的关键词就是采用余弦距离计算得出的。
KD 树 一个二叉树的数据结构，方便存储 K 维空间的数据
创建 KNN 分类器
构造函数 KNeighborsClassifier(n_neighbors=5,weights=‘uniform’, algorithm=‘auto’, leaf_size=30)
1.n_neighbors：即 KNN 中的 K 值，代表的是邻居的数量。一般我们使用默认值 5。
2.weights：是用来确定邻居的权重，有三种方式：
weights=uniform，代表所有邻居的权重相同；
weights=distance，代表权重是距离的倒数，即与距离成反比；
自定义函数，你可以自定义不同距离所对应的权重。大部分情况下不需要自己定义函
数。
3.algorithm：用来规定计算邻居的方法，它有四种方式：
algorithm=auto，根据数据的情况自动选择适合的算法，默认情况选择 auto；algorithm=kd_tree，也叫作 KD 树，是多维空间的数据结构，方便对关键数据进行检索，不过 KD 树适用于维度少的情况，一般维数不超过 20，如果维数大于 20 之后，效率反而会下降；
algorithm=ball_tree，也叫作球树，它和 KD 树一样都是多维空间的数据结果，不同于KD 树，球树更适用于维度大的情况；
algorithm=brute，也叫作暴力搜索，它和 KD 树不同的地方是在于采用的是线性扫描，而不是通过构造树结构进行快速检索。当训练集大的时候，效率很低。
4.leaf_size：代表构造 KD 树或球树时的叶子数，默认是 30，调整 leaf_size 会影响到树的构造和搜索速度。
创建完 KNN 分类器之后，我们就可以输入训练集对它进行训练，这里我们使用 fit() 函数，传入训练集中的样本特征矩阵和分类标识，会自动得到训练好的 KNN 分类器。然后可以使用 predict() 函数来对结果进行预测，这里传入测试集的特征矩阵，可以得到测试集的预测分类结果。
如何用 KNN 对手写数字进行识别分类
https://github.com/cystanford/knn
