KNN分类

1. 什么是KNN

KNN的全称是K Nearest Neighbour,即K最近邻分类算法,其中的$K$表示最接近自己的$K$个数据样本。与K-Means算法不同的是,KNN算法用于分类,也就是样本空间中的每个样本都有一个类标号,现在要把未知的样本分配到某一类,而K-Means聚类将样本空间中的样本进行分组,根据某种相似度度量,将相近的元素划分为一组,不相近的元素划分为另一组。

KNN算法将样本空间中的每个样本看作$d$维空间上的一个数据点,其中$d$表示属性(特征)个数。给定一个测试样例,通过使用某种相似度度量,计算该测试样本与训练集中其他数据点的邻近度(相似度),给定测试样例$z$的K最近邻是指和$z$距离最近的$K$个数据点,然后根据这$K$个数据点所属的类别,将出现类别数最多的类标号作为测试样例$z$的类别。

用数学的语言描述如下:
假设样本空间中有$n$个样本点$(X_1, X_2, \cdots, X_n)$,它们所属的类标号是$(Y_1, Y_2, \cdots, Y_n)$,给定一个测试样本$Z$,通过使用某种相似度度量,计算出训练样本中与测试样本$Z$最近的$K$个样本点,假设这$K$个样本点的类标号是$(y_1, y_2, \cdots, y_k)$,则测试样本的类标号$C$为:

$$
C = mode(y_1, y_2, \cdots, y_k)
$$

即$C$等于序列$y_1,y_2,\cdots,y_k$的众数,也就是出现次数最多的数。

2. 例子

这里用一个简单的例子来说明KNN算法。如下图所示,假设我们的训练样本有两类,一类是蓝色正方形,另一类是绿色三角形,我们的相似度度量采用欧式距离。现在给定一个测试样本,也就是图中的红色圆形,我们应该把它归到蓝色正方形一类还是绿色三角形一类?


knn

  • 当$K=3$时,离红色点最近的有两个绿色点和一个蓝色点,在这3个点中,出现次数最多的是绿色点,由KNN算法,我们将红色点归到绿色三角形一类;
  • 当$K=5$时,离红色点最近的有三个蓝色点和两个绿色点,在这5个点中,出现次数最多的是蓝色点,因此我们将红色点归到蓝色正方形一类;

由上面的分析可以看到,不同的$K$会导致分类的不同。使用最近邻确定类标号的合理性用下面的谚语最能说明:“如果走像鸭子,叫像鸭子,看起来也像鸭子,那么它很可能就是一只鸭子”。

使用KNN算法的另外一个有趣的例子可以参考这篇博文

3. 参考资料