文档章节

机器学习 -- KNN(k-Nearest Neighbor)最邻近规则分类算法

大海201506
 大海201506
发布于 2017/05/16 00:17
字数 1023
阅读 164
收藏 1

1. 综述

Cover和Hart在1968年提出了最初的邻近算法,也被称为基于实例的学习或懒惰算法。
与决策树算法相比,处理训练集的时候并不建立任何模型,进行分类时才将测试样例和所有已知实例进行比较进而分类。
2. 例子

上图中主要有蓝色方块和红色三角两种色块,如果要对绿色未知圆点进行判断分类,那么它是属于蓝色方块还是红色三角呢?

算法的思路:如果一个样本在特征空间中的K个最相似(即特征空间中最邻近)的样本中的大多数属于这一类别,则该样本也属于这个类别。

KNN算法一般可以分为两步:

  1. 以所有已知的实例作为参考,计算未知圆点和所有色块的距离。
  2. 选择一个参数K,判断离未知实例最近的K个实例是什么类型,以少数服从多数的原则进行分类。

上图中,如果我们选择的K值为1,则离未知圆点最近的一个色块是蓝色,未知实例会被归类为蓝色。假设我们选择的K值为4,很明显距离未知圆点最近的4个色块分别为:3个红色三角和1个蓝色方块,那么未知圆点就会被归类为红色三角(少数服从多数)。

所以K的选择对结果的影响很大,在一定范围内通过增大K可以增强抗噪性。

对于距离的衡量方式有很多种,例如Euclidean Distance,余弦值(cos),相关度 (correlation),曼哈顿距离 (Manhattan distance),最常用的是Euclidean distance: 

二维的下距离计算公式如上图简单的数学公式,扩展到n维下x,y两点的距离公式:

注解:设n维空间两点的坐标:
Px(x1,x2,...,xn)
Py(y1,y2,...,yn)
那么Px、Py两点间距离(平方):
(x1-y1)^2+(x2-y2)^2+.+(xn-yn)^2

KNN算法虽然从原理上也依赖于极限原理,但在类别决策时,只于极少量的相邻样本有关。由于KNN算法主要依靠周围有限的邻近样本,而不是依靠判别类域的方法来确定所属类别,因此对于类域的交叉或重叠较多的待分样本集来说,KNN算法较其他算法更为适合。

KNN算法不仅可以用于分类,还可以用于回归。通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。

不足一:需要大量的空间存储所有实例,以及计算量较大。因为对每一个未知实例都要计算它到所有实例的距离,才能求得它的K个最近邻点。

解决方法:目前常用的解决方法是事先对已知样本点进行剪辑,
事先去除对分类作用不大的样本。这个解决方法比较适用于那些样本容量比较大的类域,而样本容量比较小的类域采用这种算法比较容易产生误分。

不足二:当其中一类样本过大,则不管未知实例属于哪一类,都很容易归为数量过大的这一类。

如图:

 

因为Y点在红色区域内,用肉眼去看很容易判断出它多半属于红色一类,但是因为蓝色过多,若K值选取稍大则很容易将其归为蓝色一类。为了改进这一点,可以为每个点的距离增加一个权重,这样离得近的点可以得到更大的权重,比如距离d,权重1/d。

参考:http://www.cnblogs.com/kuihua/p/5883691.html

参考:http://blog.csdn.net/ewfwewef/article/details/52798611

参考:http://blog.csdn.net/erzr_zhang/article/details/53506860

© 著作权归作者所有

大海201506
粉丝 5
博文 96
码字总数 173986
作品 0
广州
程序员
私信 提问
K最近邻(k-Nearest Neighbor) 浅析

K最近邻(k-Nearest Neighbor,KNN)分类算法的核心思想是如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。KNN算法可用于多...

刘敬
2018/05/08
0
0
kNN(K-Nearest Neighbor)最邻近规则分类

KNN最邻近规则,主要应用领域是对未知事物的识别,即判断未知事物属于哪一类,判断思想是,基于欧几里得定理,判断未知事物的特征和哪一类已知事物的的特征最接近; K最近邻(k-Nearest Neig...

最帅的刘先生
2016/12/23
72
0
分类(二):基于向量空间模型的文本分类

利用向量空间模型进行文本分类的思路主要基于邻近假设(contiguity hypothesis)。 邻近假设: 同一类的文档会构成一个邻近区域,而不同类的邻近区域之间是互不重叠的。 1、Rocchio方法 Rocc...

_Roger_
2015/10/22
226
0
数据挖掘十大算法以及scikit-learn算法选择图

1. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进: 1) 用信息增益率来选择属性,克服了用信息...

kwame211
2018/05/16
0
0
【Machine Learning】KNN算法虹膜图片识别

K-近邻算法虹膜图片识别实战 作者:白宁超 2017年1月3日18:26:33 摘要:随着机器学习和深度学习的热潮,各种图书层出不穷。然而多数是基础理论知识介绍,缺乏实现的深入理解。本系列文章是作...

伏草惟存
2017/01/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部