AI教程

K近邻算法详解

笔者最近准备写一个系列的机器学习算法教程。每篇文章详细讲解一个机器学习的经典算法,旨在让零基础的读者可以快速入门。

1. 算法介绍

k近邻(k-neareast neighbor,kNN)是解决分类与回归问题最基本的算法之一。该算法没有显式的训练过程。

k近邻算法的核心思想用一句话就可以概括:

给定测试样本,基于某种距离度量找出训练集中与其最近的k个训练样本,然后基于这k个“邻居”的信息来进行预测。

——《机器学习》第10章

该算法有三个重要要素:距离度量、k值的选择和分类决策规则。

1.1 距离度量

假设一个人身高175cm,体重为65公斤,体重正常。我们可以用 X1 = [175, 60] Y1 = “非肥胖” 来表示这个人。同样,若一个人身高170cm,体重90公斤,体重超标。我们用 X2 = [170, 90] Y2 = “肥胖” 来表示此人。

现在已知一人X = [160,100](即身高160cm,体重100公斤),我们想要知道此人与前两人的相似程度,从而推断出此人是肥胖还是非肥胖。

这里的相似程度可用距离来表示,若两个人之间的X(特征)越接近,则认为这两个人越相似。

因此,我们需要考虑如何度量两个样本之间的距离。

距离的定义不止一种,一种通用的定义为Lp距离:

该定义为一种范数。当p=2时,即为我们常见的L2范数(欧式距离);p=1为L1范数(曼哈顿距离)

如下图,欧式距离为两点之间直线段长度,曼哈顿距离为各轴坐标差之和。

所选的距离的度量(曼哈顿距离、欧式距离、L3距离……)不同,各个点之间的距离不同,各点之间的最近邻点也可能不同。

欧式距离

对于上述体重的例子,X=[160,100] 与非肥胖样本 X1=[175,60] 的欧式距离(L2距离)为42.72;X=[160,100] 与肥胖样本X2=[170,90] 的欧式距离为14.14。

待预测样本X与肥胖样本X2更接近,因此我们预测样本X为肥胖样本。

这里有一个值得注意的细节:若我们把身高的单位变为毫米,把体重的单位变成吨。则样本之间的距离也会发生变化。一个人可以是1600mm身高,有0.1吨的体重。此时若是做样本之间欧式距离的计算,则身高的差距会在欧式距离中占据主导地位,而体重之间的差距几乎可忽略不计。

如果我们认为不同特征对结果同等重要的话,我们常常会对特征进行归一化处理——把样本数据缩放到一个指定范围内。

归一化的方法有很多,比如把分布在0-220cm的身高线性变换成分布在-1到1之间的数据、或者缩放成均值为0,方差为1的数据等等。

1.2 K值的选择

之前我们预测体重样本时,是选择与待测样本最近的一个样本来进行参考。

事实上,我们可以选择k个与待测样本最近的样本,并认为k个已知样本中出现次数最多的类别即为待测样本的类别。

有的时候,k值的选择不同,预测的结果也会不同。

k值的选择决定了绿色小球的类别

上图中,当k=3时,小球应该为红色三角;k=5时,小球应该为蓝色正方形。

k=1时

k=2时

在上图中,我们用颜色标记出各个类别的空间。当k>1时,可能会存在k个临近样本中有多个类别出现次数一样多(如右上图白色区域)。此时我们在出现次数最多个几个类别中随机选取一个类别即可。

k值越小,模型越复杂,越容易发生过拟合。k值越大,模型越简单。当k等于训练集样本数的时候,模型只是单纯返回训练集中出现次数最多的类别。

应用中,k值的选择通常为人为设定。一般取值都较小。可用交叉验证法来确定最优的k值。

1.3 分类决策规则

在分类问题(如判断人是否肥胖)中,我们通常是在取k个样本后,采取多数表决:出现次数最多的类别即为待测样本的类别。

亦可使用加权投票:与待测样本越近的样本权重越大,对各类别进行权重求和后,选择权重和最大的类别。

而在回归问题中(如已知一个人身高、年龄、平均每日摄取卡路里等信息,预测此人体重),我们可取k个样本后,对其结果Y进行平均或者加权平均

2. 代码实现

2.1 核心代码

本段代码改编自《机器学习实战》。在技术杂学铺公众号内回复“机器学习”即可下载电子版。

笔者已将《机器学习实战》第二章kNN全部代码整合为jupyter文件,并改版为python3版本且附带大量中文注释。读者可前往github下载 | jupyter环境安装

kNN算法
数据归一化算法

2.2 实战任务

这里我们使用sklearn函数库、Iris数据集。相关介绍可见往期文章

注:本任务需安装sklearn函数库。

Iris – 鸢尾花

已知三种品种的鸢尾花(山鸢尾、维吉尼亚鸢尾、变色鸢尾)的花萼长度,花萼宽度,花瓣长度,花瓣宽度4个属性各50条。数据样本如下:

花萼长度 花萼宽度花瓣长度花瓣宽度品种
6.42.85.62.22
5.02.33.31.01
4.92.54.51.72
4.93.11.50.10
5.73.81.70.30

任务:对Iris数据集,自行划分训练集与测试集,探究kNN算法对此数据集的效果如何。

鸢尾花数据分布图

第一步,导入数据。sklearn函数库自带iris数据集。直接导入即可。

共150条数据,X为样本特征,每个样本有4个数字属性。Y为样本的类别,取值在0、1、2之间。

第二步,划分训练集和测试集。

使用sklearn的函数train_test_split可将数据打乱后划分到训练集与测试集中。其中设置 test_size=0.2表示测试集占总数据的20%

第三步,创建kNN模型。

导入KNeighborsClassifier函数,设置其k的取值为5(n_neighbors)

设置完后我们会看到kNN模型的具体参数:

KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=1, n_neighbors=5, p=2,
           weights='uniform')

我们未设置其距离度量方式。模型默认取p=2,即为欧式距离。分类决策规则默认为多数表决。

使用 模型.fit(训练集特征,训练集类别) 可训练模型(kNN无需训练模型,这里只是绑定了训练集数据。若是其他模型执行fit函数,可能会需要训练一段时间)

第四步,结果评估。

使用 模型.predict(测试集特征) 可得到模型对待测样本的预测结果。在以后的模型应用时,执行此函数即可。

执行 模型.score(测试集特征,测试集类别) 可得到模型对于测试集预测的准确率,即可知道模型的好坏。

此代码文件与2.1节核心代码放在github同一目录下,读者可前往github下载

3. 其他

  • k近邻法一般都是线性扫描训练集样本。kd树可提高其搜索效率,其平均计算复杂度为O(logN)。具体算法可见《统计学习方法》。
  • kNN虽然算法简单,但在手写数字数据集MNIST上,识别错误率仅为5%,最好的kNN变体算法,识别错误率可低至0.52%!
kNN在MNIST数据集上的表现
从左至右分别为 算法名、预处理方法、错误率、来源

4. 总结

本文我们讨论了机器学习经典算法之一的k近邻算法。讨论其距离度量、k的选择和决策分类规则,并使用sklearn机器学习库来解决鸢尾花的分类问题。

k近邻算法无需提前训练模型,而是根据与待测样本最近的k个样本的信息来预测待测样本。

4.1 k近邻算法优点

  • 实现简单
  • 无需提前训练模型
  • 对异常值不敏感

4.2 k近邻算法缺点

  • 训练集过大时预测速度极慢(计算复杂度高)
  • 预测时需要保留训练数据集(空间复杂度高)
  • 无法给出数据的基础结构信息,不知道典型实例样本有怎样的特征

参考资料

  • 《机器学习实战》第2章 k-近邻算法
  • 《统计学习方法》第2章 k-近邻算法
  • 《机器学习》10.1 k近邻学习

One thought on “K近邻算法详解
发表评论