kNN算法大概是机器学习相关算法中最容易理解的算法了。这篇文章的目的大概是介绍一下kNN算法，介绍一下其错误率的推导，以及论文中的精确推导。大概是这三个方面。
kNN算法介绍
kNN（k nearest neighbor）算法的就用下面的图来介绍好了。
kNN
从上图中我们可以看到，图中的有两个类型的样本数据，一类是蓝色的正方形，另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。
- 如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3 个点投票，于是绿色的这个待分类点属于红色的三角形。
- 如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。
这个算法体现了当前主流机器学习算法的核心，基于统计。
注意
这里需要注意的地方有两个
k的选取
从上图也可以看出来，对于不同的k值，结果可能大不相同，因此，具体选取哪几个值，需要根据你的数据集来确定。
距离度量
- 曼哈顿距离
- 欧几里得距离
- L1距离
- ...
改进方法
我们看这样一张图，虽然每一类分布相对集中。但是偏离分类中心的点会对结果造成影响。
考虑到这个问题，我们为每个样本的到测试样本的距离增加权重，距离越远权重越低。
错误率推导（大致）
推导过程来自周志华老师的《机器学习》
给定测试样本x，若最近样本为在， 分类器出错的概率就是与z不同的概率。即
假设样本独立同分布，对任意x和任意小的整数 \delta ,在x附近\delt 距离内总能找到一个训练样本。即任意测试样本任意近的距离内总能相应的训练样本z。令
即其泛化误差不超过贝叶斯分类器的两倍。（关于贝叶斯分类器，后面的文章再做分析）。
论文中的推导以及介绍
todo
