机器学习入门(二):最简单的ML算法--kNN算法


kNN in one sentence

kNN是最简单的机器学习分类算法,适用于多分类问题,其中心思想是,对于待预测点x,其最有可能属于距离其最近的k个sample中同类别数量最多的那一类。即所谓“近朱者赤,近墨者黑”。

对于kNN,我的建议是拿来入门,有优化kNN到足够的准确率/召回率的时间,(可能)够用一个新的模型优化新的参数轻松达到更好的效果了。

kNN简介

机器学习是一门看上去高大上的学科,而其中其实不乏接地气的算法,比如kNN。kNN算法又称为k近邻分类(k-nearest neighbor classification)算法。用kNN来入门机器学习,能轻松获得不小的成就感。

kNN是一种分类算法,可以适用于多分类。

kNN的学习方法很朴素,简单说就是站队,对于已有的训练集,当传入未知数据待分类时,分别计算未知数据和训练集所有数据点的距离,将距离从小到大取前k个。根据这k个点的分类情况判断未知数据的分类。通常哪个类别在前k个数据点中数量最多,我们就认为未知数据是哪个类别的。

kNN

如图,在拥有三个分类的若干样本点的训练集中,对未知元素Xu,我们取k=5,选取距离其最近的5个训练集的点,其中4个是红色圆圈,1个是绿色方块,0个蓝色三角,那么我们认为,其最可能所属的分类是红色圆圈。

kNN

由kNN算法的描述,可以看出,kNN是一个免训练的,参数少的,朴素的算法,然而kNN仍有几个关键点,距离的计算和k的选择。

距离的选择

在kNN的思想中,两个点之间距离的大小标定了两个点的相似度大小,通常距离小的点更加相似,也更容易属于一个类别。

距离的选择很大程度上影响kNN的效果好坏,距离大小必须足够体现出样本点之间的相似和不同的程度。

通常默认的距离是欧氏距离,这种我们从小开始学习的坐标系下的距离表示。然而对于向量化的文本和图片,有时欧式距离并不能正确衡量相似度的大小,所以根据具体问题,距离也会采用余弦距离、海明距离、编辑距离等等。

k的选取

容易理解,当k太小,分类结果易受噪声点影响;k太大,近邻中又可能包含太多的其它类别的点。

kNN

如图,k=3的时候,未知样本的类别被判断成红色三角,k=5的时候,分类结果则是蓝色方块,这个例子说明了k的取值对分类结果是有影响的。

通常通过cross validation来进行k的选取,从k=1开始进行交叉校验,直到k=n,取能使交叉校验得到最好的结果的k。

经验上,通常k小于数据集的平方根。

kNN的优点

kNN的优点有很多,最大的优点我认为还是简单。

  • 简单
  • 容易实现
  • 支持多分类
  • 无需训练,training set拿来就用

kNN的缺点

kNN同样有很多缺点

kNN

  • 对训练集要求苛刻,kNN要求训练集不同类别的数据不能相差太多,对上图的数据,可以预见,因为样本过少很有可能很少有数据被分类成蓝色圆圈—-即使它可能真的是蓝色圆圈
  • 计算量大。慢是kNN的致命伤,每一次都要计算未知数据和所有训练集的距离,当训练集非常大的时候,这会变得很慢;而训练集小的话,又会显得精确度不够。
  • 太简单,以至于几乎没有什么优化的空间。

kNN tricks

kNN虽然简单,也没啥好优化的,其仍然有不少tricks能够或多或少提供准确率的提升。

Normalization

当样本点向量的某一个维度范围(scale)非常大的时候,对维度进行normalization归一可能会对结果有好处。

kNN

如图,现在有两个分类但是x轴上的scale非常大,y轴的scale非常小,尽管两个分类有着肉眼可见的明显的界限,使用kNN时结果还是会变得非常难堪,因为x轴的scale太大,其在计算距离时的贡献过于大了,所以我们可以对维度的scale进行放缩,即所谓normalization,使x和y都在[0,1]的区间内,这样,样本的空间分布就是一个正方形(在这个例子中),没有哪一个坐标的贡献对距离过大了,如图,显然normalization之后结果会更喜人一点。

kNN

kNN加权

尽管目前的kNN对所有前k个样本点一视同仁,但是我们可能会想到和未知数据非常近的点可能同类别的概率非常大,距离越远,同类别的概率就越小,因此,可以根据距离的远近对这k个点进行加权,具体如何加权,就不具体讨论了。

kNN的实现

太简单,不说也罢,有空补上。

s