机器学习|机器学习(KNN一)——原理概述

从这篇博客开始机器学习最大的一块——分类(有监督学习),并以KNN做为开篇。(当然KNN也可用做回归)
K近邻(K-nearst neighbors, KNN)是一种基本的机器学习算法,所谓k近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。比如:判断一个人的人品,只需要观察与他来往最密切的几个人的人品好坏就可以得出,即“近朱者赤,近墨者黑”;KNN算法既可以应用于分类应用中,也可以应用在回归应用中。
KNN在做回归和分类的主要区别在于最后做预测的时候的决策方式不同。KNN在分类预测时,一般采用多数表决法;而在做回归预测时,一般采用平均值法。
一、 原理 过程

  1. 从训练集合中获取K个离待预测样本距离最近的样本数据;
  2. 根据获取得到的K个样本数据来预测当前待预测样本的目标属性值。
【机器学习|机器学习(KNN一)——原理概述】机器学习|机器学习(KNN一)——原理概述
文章图片

如上图,绿色圆要被决定属于哪个类,是红色三角形还是蓝色四方形?
  • 如果k=3,由于红色三角形所占比例为2/3,绿色圆将属于红色三角形那个类。
  • 如果k=5,由于蓝色四方形比例为3/5,因此绿色圆将属于蓝色四方形类。
举例
机器学习|机器学习(KNN一)——原理概述
文章图片

上图中对多种食物提供两个特征:
  • 一个特征是对配料有多脆的度量(crunchiness),取值范围 1 ~ 10;
  • 第二个特征是对配料有多甜的度量(sweetness),取值范围1~10;
我们标记配料为3中类型之一:fruit(水果)、vegetable(蔬菜)或者protein(蛋白质)
我们绘制二维数据的散点图,维度X表示配料的甜度(sweetness),维度y表示配料的脆度(crunchiness),散点图如下:
机器学习|机器学习(KNN一)——原理概述
文章图片

大致的标出对应的区域:
机器学习|机器学习(KNN一)——原理概述
文章图片

问题: 西红柿是属于哪类呢??
二、三要素 1. K值的选择 对于K值的选择,一般根据样本分布选择一个较小的值,然后通过交叉验证来选择一个比较合适的最终值;当选择比较小的K值的时候,表示使用较小领域中的样本进行预测,训练误差会减小,但是会导致模型变得复杂,容易过拟合;当选择较大的K值的时候,表示使用较大领域中的样本进行预测,训练误差会增大,同时会使模型变得简单,容易导致欠拟合;
2. 距离的度量 一般使用欧氏距离(欧几里得距离);
3. 决策规则 在分类模型中,主要使用多数表决法或者加权多数表决法;在回归模型中,主要使用平均值法或者加权平均值法。
1)分类
多数表决法:每个邻近样本的权重是一样的,也就是说最终预测的结果为出现类别最多的那个类,比如下图中蓝色圆圈的最终类别为红色;
加权多数表决法:每个邻近样本的权重是不一样的,一般情况下采用权重和距离成反比的方式来计算,也就是说最终预测结果是出现权重最大的那个类别;比如下图中,假设三个红色圆点到待预测样本点的距离均为2,两个黄色五角星到待预测样本点距离为1,那么蓝色样本的最终类别为黄色。
到圆的距离为2,则权重为 1/2;到五角的距离为1,则权重为1。
1 / 2 ? 3 < 1 ? 2 1/2 * 3 < 1 * 2 1/2?3<1?2,所以为五角
机器学习|机器学习(KNN一)——原理概述
文章图片

3)回归
平均值法:每个邻近样本的权重是一样的,也就是说最终预测的结果为所有邻近样本的目标属性值的均值;比如下图中,蓝色圆圈的最终预测值为:2.6
( 3 + 3 + 3 + 2 + 2 ) / 5 = 2.6 (3+3+3+2+2)/5 =2.6 (3+3+3+2+2)/5=2.6
加权平均值法:每个邻近样本的权重是不一样的,一般情况下采用权重和距离成反比的方式来计算,也就是说在计算均值的时候进行加权操作;比下右图中,假设上面三个点到待预测样本点的距离均为2,下面两个点到待预测样本点距离为1,那么蓝色圆圈的最终预测值为:2.43。(权重分别为: 1/7和2/7)
到③的距离都为3,到②的距离都为1。和权重成反比,则分别为1/3,1。
做归一化: ( 1 / 2 ) / ( 1 / 2 ? 3 + 1 ? 2 ) = 1 / 7 , 1 / ( 1 / 2 ? 3 + 1 ? 2 ) = 2 / 7 (1/2) / (1/2 * 3 + 1*2) = 1/7, 1 / (1/2 * 3 + 1*2) = 2/7 (1/2)/(1/2?3+1?2)=1/7,1/(1/2?3+1?2)=2/7
则: 3 ? 1 / 7 ? 3 + 2 ? 2 / 7 ? 2 = 2.43 3*1/7*3 + 2*2/7 * 2 = 2.43 3?1/7?3+2?2/7?2=2.43
机器学习|机器学习(KNN一)——原理概述
文章图片

三、 实现方式 KNN算法的重点在于找出K个最邻近的点,主要方式有以下几种:
1. 蛮力实现(brute)
计算预测样本到所有训练集样本的距离,然后选择最小的k个距离即可得到K个最邻近点。缺点在于当特征数比较多、样本数比较多的时候,算法的执行效率比较低;
2. KD树(kd_tree)
KD树算法中,首先是对训练数据进行建模,构建KD树,然后再根据建好的模型来获取邻近样本数据。
3. 其他
除此之外,还有一些从 KD_Tree 修改后的求解最邻近点的算法,比如:Ball Tree、BBF Tree、MVP Tree等。
注:
  • 如果样本数据为稀疏矩阵,刚只能采用蛮力法。哪怕给定KD树方式实现,内部也会转为蛮力法。
  • KD:指K个维度
KD 树 KD Tree是KNN算法中用于计算最近邻的快速、便捷构建方式。当样本数据量少的时候,我们可以使用brute这种暴力的方式进行求解最近邻,即计算到所有样本的距离。但是当样本量比较大的时候,直接计算所有样本的距离,工作量有点大,所以在这种情况下,我们可以使用kd tree来快速的计算。
1. 构建方式
KD树采用从m m m 个样本的n n n 维特征中,分别计算n n n 个特征取值的方差,用方差最大的第k k k 维特征n k n_k nk? 作为根节点。对于这个特征,选择取值的中位数n k v n_{kv} nkv? 作为样本的划分点,对于小于该值的样本划分到左子树,对于大于等于该值的样本划分到右子树,对左右子树采用同样的方式找方差最大的特征作为根节点,递归即可产生KD树。(方差越大,分割性质越好。方差本身代表偏移量,离散程度,在树上体现左右两子树的更离散、差异更大)
举例
二维样本: {(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}
构建结果:
机器学习|机器学习(KNN一)——原理概述
文章图片

转换成特征空间的划分
机器学习|机器学习(KNN一)——原理概述
文章图片

2. 查找
当我们生成KD树以后,就可以去预测测试集里面的样本目标点了。对于一个目标点,我们首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心,以目标点到叶子节点样本实例的距离为半径,得到一个超球体,最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点,检查另一个子节点包含的超矩形体是否和超球体相交,如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了,我们直接返回父节点的父节点,在另一个子树继续搜索最近邻。当回溯到根节点时,算法结束,此时保存的最近邻节点就是最终的最近邻。
举例:查找(2,4.5)
机器学习|机器学习(KNN一)——原理概述
文章图片

反应在特征图上的:
机器学习|机器学习(KNN一)——原理概述
文章图片

总 总的来说,KNN特别好理解,就是我说常说的“近朱者赤,近墨者黑”。

    推荐阅读