kNN算法

2017-03-29 本文已影响0人 HowieCheng

kNN算法大概是机器学习相关算法中最容易理解的算法了。这篇文章的目的大概是介绍一下kNN算法，介绍一下其错误率的推导，以及论文中的精确推导。大概是这三个方面。

kNN（k nearest neighbor）算法的就用下面的图来介绍好了。

kNN

从上图中我们可以看到，图中的有两个类型的样本数据，一类是蓝色的正方形，另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。

如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3 个点投票，于是绿色的这个待分类点属于红色的三角形。
如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。
这个算法体现了当前主流机器学习算法的核心，基于统计。

这里需要注意的地方有两个

从上图也可以看出来，对于不同的k值，结果可能大不相同，因此，具体选取哪几个值，需要根据你的数据集来确定。

我们看这样一张图，虽然每一类分布相对集中。但是偏离分类中心的点会对结果造成影响。

考虑到这个问题，我们为每个样本的到测试样本的距离增加权重，距离越远权重越低。

推导过程来自周志华老师的《机器学习》
给定测试样本x，若最近样本为在，分类器出错的概率就是与z不同的概率。即

假设样本独立同分布，对任意x和任意小的整数 \delta ,在x附近\delt 距离内总能找到一个训练样本。即任意测试样本任意近的距离内总能相应的训练样本z。令

表示贝叶斯分类器的最优分类结果。

即其泛化误差不超过贝叶斯分类器的两倍。（关于贝叶斯分类器，后面的文章再做分析）。

todo