KNN算法

2020年11月15日 / 5次阅读 / Last Modified 2020年11月23日
算法

KNN算法,K最近邻 (K-Nearest Neighbors)是一种分类算法, 1968年由 Cover和 Hart 提出, 应用场景有字符识别、 文本分类、 图像识别等领域。该算法的思路是:如果一个测试样本与数据集中的K个样本最相似, 这K个样本中的大多数属于某一个类别, 则该测试样本也属于这个类别。

KNN不仅可以用于分类,还可以用来做回归(regression),思路是:测试样本的某个属性值,可以直接用其K个最邻近的数据集中样子的相同类别属性值求平均。

Nearest是什么?一般采用欧氏距离或者曼哈顿距离,即L2范数或L1范数。这就要求所有的数据都要用vector来表示,这样就可以计算距离,多维空间中两个点之间的距离,个人感觉欧式距离更好更自然一些。(用np.linalg.norm计算L2和L1范数

K值如何选择?这可能是KNN算法最trick的一个细节。

K的最小取值是1,此时数据集中谁最近,测试样本就跟它的类别一样。K的最大理论值是全体数据集的数量N,此时,全体数据集N中,哪个类别的样本数量最多,测试样本就属于哪一类,这显然是错误的。

KNN中的K值选取对K近邻算法的结果会产生重大影响。如李航博士的一书「统计学习方法」上所说:如果选择较小的K值,就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小,只有与输入实例较近或相似的训练实例才会对预测结果起作用,与此同时带来的问题是“学习”的估计误差会增大,换句话说,K值的减小就意味着整体模型变得复杂,容易发生过拟合。如果选择较大的K值,就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。K=N,则完全不可取,因为此时无论输入实例是什么,都只是简单的预测它属于在训练实例中最多的累,模型过于简单,忽略了训练实例中大量有用信息。在实际应用中,K值一般取一个比较小的数值(我看到有人说一般不大于20),例如采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。

K值越小越容易overfitting,K值越大预测效果就越差,因为与测试样本较远的数据也在发挥作用。想象一个分布不均衡的数据集,有一个类别A只有较少的数据,另一个类别B有很大量的数据,此时如果K值很大,预测的结果就会严重偏向B,仅仅是因为B本来就比较多而已。

所以,K值的选择,不仅要做一些测试,还要考虑到数据集中各个类别的分布情况!

KNN算法属于监督学习,但其实并没有真正的学习过程,有人说这是惰性学习(lazy learning)。在数据集和测试样本都准备好的时候,KNN直接计算测试样本与数据集中样本的距离,选择最好的K个,然后得出预测结果。预测的过程,就是学习的过程,因此,KNN在做预测的时候,计算量会较大。仔细想这个过程,KNN算法还有一个特点,即结果可重复,对于每一个测试样本,只要数据集不变,每一次测试的结果一定是一样的!

KNN算法简单有效,复杂度低,代码实现起来非常容易。下图是博主做的一个测试,在K=10的时候,将KNN用于MNIST和FMNIST两个数据集,测试的结果如下图:

KNN算法在MNIST和FMNIST数据集上的测试(K=10)
KNN算法在MNIST和FMNIST数据集上的测试(K=10)

获取测试代码:https://github.com/xinlin-z/teapot

KNN算法在做分类的时候,要考虑一个细节,当K个邻近中,存在多个出现频率相同的数据时,如何选择?这种情况常常发现,以上测试代码的实现是,永远选择加总距离最小的那个。

-- EOF --

本文链接:https://www.pynote.net/archives/2784

留言区

电子邮件地址不会被公开。 必填项已用*标注


前一篇:
后一篇:

More


©Copyright 麦新杰 Since 2019 Python笔记

go to top