机器学习算法简介之二——邻近算法kNN

01

kNN

简介

邻近算法 (或k-Nearest Neighbor，简称“kNN算法”)是数据挖掘分类技术中最简单的方法之一。k最近邻，即k个最近的邻居，指的是每个样本都可以用它最接近的k个邻居来代表，k个最近邻中数量最多的那一类就是样本所属的类别。在实际操作中，邻近算法根据一些特征指标，按照相似度对无标签的样本进行分类。相似度以特征指标构成的多维空间中，各样本之间的欧式距离进行衡量。

邻近算法的主要优点是简单有效，且无需假设，训练过程迅速；主要缺点是没有相应的统计模型，指标与分类结果难以解释，且分类过程较慢，数据缺失的处理较为繁琐。

02

kNN

实例

本文将通过以下实例对邻近算法进行阐述，本例中主要解决问题：番茄是水果还是蔬菜？

Step 1:选取指标

为了了解水果、蔬菜等食物的特性，本例选取了两项特征指标：甜度和脆度，并对各样本的甜度和脆度进行评分，分值为1-10分。评分结果如下表所示：

表 1：食物的甜度和脆度情况表

Step 2:创建多维的特征空间

根据上述2个特征指标，我们可建立二维的样本分布空间，其中，横坐标表示食物的甜度，纵坐标表示食物的脆度；根据每一种食物的甜度和脆度，可以将其用平面上的点表示（如图1）。

不难发现，相邻的食物往往属于同一类。如图2所示，蔬菜类食品均具有不甜、较脆的特点，分布于左上部分；蛋白质类食品均具有既不甜也不脆的特点，分布于左下部分；水果类食品往往较甜，分布于右侧。

然后，我们将用平面上的点来表示番茄的甜度和脆度，并通过番茄与其他各类食品之间的距离来确定番茄与其他各类食品之间的相似度。

Step 3:计算欧式距离

在多维空间中，用以衡量两点之间的距离的指标较多， kNN 算法中，所采用的是欧式距离。 欧式距离指的是多维空间中两点之间的真实距离，其计算公式为：

其中， E(p,q)代表点 p 与点 q 之间的欧式距离，p1,p2,...,pn与q1,q2,...,qn分别代表点p与点q上n个指标的值。

利用上述欧式距离的计算公司，我们可计算各食品与番茄之间的欧式距离，结果如下表所示：

Step 4:选取k值

在获得排序之后， 我们需确定 k 的取值， k 的取值将会影响我们对番茄的分类。k 值就是使用 kNN 算法时，所参考最近邻的个数。如下图 4 所示，假设三角形代表水果，正方形代表蔬菜，当 k=3 时，最近邻中水果的个数多于蔬菜的个数，所以番茄分类为水果；当k=5时， 最近邻中蔬菜的个数多于水果的个数。k取值不同可能会导致样本的分类结果产生变化，这也是kNN 算法的缺点之一。

03

kNN

总结

kNN邻近算法的技术核心在于k值的选取。如果选择较小的k值，就相当于根据较少的最近邻进行预测，其近似误差会减小，只有与输入实例较近或相似的样本才会对预测结果起作用，其缺点是若近邻的实例点恰巧是噪声，预测就会出错；如果选择较大的K值，就相当于用较多的最近邻进行预测，其缺点是与输入实例较远实例也会对预测起作用，使预测发生错误。在实际应用中，k值一般取一个比较小的数值，或者采用交叉验证法（简单的说就是一部分样本做训练集，一部分做测试集）来选定最优的k值。

Attention！

联合信用公众平台正式推出“机器学习算法简介”系列，欢迎广大机器学习爱好者讨论交流！

第一期机器学习算法参见“联合征信”公众平台7月13日推文：朴素贝叶斯算法简介