机器学习算法之K最近邻

最近邻(K-Nearest Neighbors, KNN)是一种基于实例的学习方法(instance-based learning)

通俗理解

就是选择最近邻,具体来说,就是选择那些“距离”被预测样本最近的K个样本,根据他们的标签值来决定要预测的样本的标签值是什么。

其实所谓最近,实际是最相似。举例:比如在现实中,预测某一个房子的价格,就参考最相似的K个房子的价格,比如距离最近、户型最相似等等。

原理

1、分类和回归的规则:

如果标签是离散变量(分类问题),就投票决定类别;如果是连续变量(回归问题),就看它们的平均取值,以此作为预测的依据。还可以基于“距离”的远近进行加权投票或加权平均,距离越近权重越高。

2、距离度量的选择:

首先,在机器学习中,这里的距离最近不是仅指现实中空间上的距离最近,而是指在特征空间上的距离最近。也就是说,预测某个房子的价格,不仅要看位置上的距离近,而且其他特征上的取值也要近,比如房间数目、层数、物业质量等等,一切有可能影响房价的因素,都可以作为特征,所有特征组成一个特征空间(就像xyz轴组成一个三维空间),在这个特征空间中的距离最近。

其次,不同规则的距离度量,包括欧几里得距离、曼哈顿距离等。

3、K值的选择:偏差与方差权衡

K值越小,偏差越小、方差越大,容易过拟合,不抗噪声。

K值越大,偏差越大、方差越小,容易欠拟合。

4、K近邻方法的实现:kd树算法

也就是说,计算机如何具体找到最近邻的那些样本。略。

5、KNN的bias(归纳偏好):

就是某算法更偏好的一些假设,当这些假设不成立时,算法就会显露它的缺点。

locality(局部性):KNN假设特征空间相近的两点更类似;

smoothness(平滑性):KNN用均值表示距离(即假设均值能很好的表现真正的距离)

equality(同等重要性):KNN假设特征(维度)都是同等重要的。

算法的评价

优点:

1、原理理解起来容易

2、lazy learning,无需进行训练

3、参数不多(主要是K)

4、在分割线比较模糊的分类问题上表现也能不错

缺点:

1、准确度相对不高

解决方法:调参;换算法

2、也需要面临k值大小的选择

解决方法:交叉验证;经验知识(通常选择一个较小的值)

3、各特征取值范围不同会影响效果:因为涉及到计算距离。

解决方法:归一化(缩放特征取值范围)、标准化(转换为标准正态分布)

4、因样本数量过少或(和)特征数量过多而导致维度灾难:无法满足密采样条件(样本稀疏问题:维度越高,填充空间所需的数据量越多,可能导致无法找到一个“最近”的样本);计算量太大(高维空间在距离计算上的问题)。

解决方法:增加样本数(不现实);降维等。

5、数据量也不能过多,因为其所耗时间和空间随着数据量增大。这是由于基于实例的方法需要把所有的实例数据(训练样本)都打包做成模型(因为它需要计算对所有样本的距离,然后排序取最近的),所谓数据即模型。其它方法只需提交训练得到的模型和参数即可。

应用

由于KNN训练的代价小(lazy learning不作训练),KNN或可被用于在线学习(online machine learning)中,即使用新数据不断训练和更新已有模型从而作出更好的预测。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180305G01G9B00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券