本文将讲解有关K近邻算法的相关知识，主要从算法思想、KNN算法三大基本要素以及KNN算法的实现之kd树来做介绍。
本文主要是依据李航老师的《统计学习方法》和邹博老师的机器学习教学视频总结编写的。文中所用到的有关机器学习的基本概念和方法可以参考本人博客中该系列之前的文章，或者直接上网搜索相关的内容。以下文章所列出的公式以及公式的推导读者们最好是在草稿本上自己推导一遍。由于本人水平所限，文章中难免有错误和不当之处，欢迎大家多多批评指正！
KNN算法思想
KNN算法的思想其实非常简单：如果现在有一堆已经标注好类别的样本，然后来了一个新的未标注的样本，让你确定它所属的类别，那么就可以计算已标注样本中离它距离最近的K个样本，那么这K个样本中的大多数所属的分类，就被当作所求样本的分类。 算法示意图如下：
由以上描述可知KNN算法中有三个基本要素：K值的选择、距离度量以及分类决策规则。下面一个个进行说明。
1.K值的选择
当K值太小时就意味着整体模型变得复杂，容易导致过拟合。极端情况下，当K值为1时，就成了最近邻算法，只由一个样本点就确定了待分类样本所属的类别，显然有点太草率了。而当K值太大时，与待分类样本相似度很低的样本也会影响到它所属的分类，从而使分类产生错误。极端情况下，当K值为样本数时，则所有待分类样本所属的类别都变成了已标记样本中最多的类别。在实际应用中，K往往会取一个比较小的值。
2.距离度量
上面提到要计算距离待分类样本最近的K个样本，而距离的定义又有很多中，其中最常见的是欧式距离，当然还有曼哈顿距离等。
3.分类决策规则
KNN算法的分类决策规则多采用多数表决规则，也就是取大多数样本所属的类别作为最终的分类类别。
4.kd树
一般情况下，如果要求离某个点距离最近的K个点时，必须先计算出当前点离其他所有点的距离，然后再对距离其进行排序，选出前K个距离最小的点。如果待求的样本点比较多事，就会使时间复杂度很高。为了更加高效的求出距离所求点最近的K个邻居，人们又提出了kd树的概念，不过由于该算法不易理解，而平常也很少用到，想要了解的朋友还请自行百度吧。
感觉本文好短啊……但是KNN算法的确是最简单的一个，而kd树的部分，我又怕自己讲不明白，唉~那就下一篇文章多写点吧。
- 本文作者： 俎志昂
- 本文链接： zuzhiang.cn/2019/08/17/KNN/
- 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！