最懒惰的算法—KNN

总第77篇

本篇介绍机器学习众多算法里面最基础也是最“懒惰”的算法——KNN(k-nearest neighbor)。你知道为什么是最懒的吗?

01|算法简介:

KNN是英文k-nearest neighbor的缩写,表示K个最接近的点。该算法常用来解决分类问题,具体的算法原理就是先找到与待分类值A距离最近的K个值,然后判断这K个值中大部分都属于哪一类,那么待分类值A就属于哪一类。

这其实和我们生活中对人的评价方式一致,你想知道一个人是什么样的人,你只需要找到跟他关系最近(好)的K个人,然后看这K个人都是什么人,就可以判断出他是什么样的人了。

02|算法三要素:

通过该算法的原理,我们可以把该算法分解为3部分,第一部分就是要决定K值,也就是要找他周围的几个值;第二部分是距离的计算,即找出距离他最近的K个值;第三部分是分类规则的确定,就是以哪种标准去评判他是哪一类。

1、K值的选取

K值的选取将会对KNN算法的结果产生重大的影响,下面通过一个简单的例子说明一下:如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。

图2.1——来源于网络

大家可以看到k值的选取会直接影响到评测结果,如果k值选取过大,相当于用较大领域中的训练实例进行预测,这样看起来是觉得数据越多可能越准确,但实际上并不然,如果要想获得较多个k值,这样你就需要把距离进一步扩大,预测准确率自然会下降。

还是拿那个我们判断一个人是什么样子的人为例,如果选择较大的k值比如一个班的人,然后根据这一个班所有人的情况去预测这个班里面的某一个人是什么样子的,这样很明显是不准确的。

如果k值选取过小,则这些很有可能是特例,也会影响预测的结果。

过大也不好,过小也不好,那么我们该怎么办?最笨的也是最有效的方法就是试,我们在上一篇推文说模型选择有一种方法是交叉验证,机器学习开篇。我们在k值选择的时候也可以用交叉验证这种方法。

2、距离的度量

我们在评判人与人之间的关系远近的时候没有一个量化的关系,只会用一些词去形容两个人之间关系的远近,比如闺蜜(发小)》舍友》同学。

但在统计学习中我们评判两者的远近关系的时候是有一个可以量化的东西,这里我们用的是欧式距离。

欧式距离又称欧几里得距离,是指在m维空间中,两个点之间的真实距离。

  • 二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离:
  • 三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离:
  • 两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离:

  也可以用表示成向量运算的形式:

当然我们还可以使用其他距离来度量两者的远近关系,比如曼哈顿距离(是不是觉得名字很高大上),更多详情点击:https://wenku.baidu.com/view/ebde5d0e763231126edb1113.html

3、分类规则的确定:

这里我们目前就使用多数表决的分类规则,即这距离最近的k个值中的大部分值的类别就是待预测值的类别。

04|算法步骤:

  1. 收集数据:找寻待训练的文本数据。
  2. 准备数据:利用python解析文本文件。
  3. 分析数据:对数据进行一些统计分析,有个基本的认识。
  4. 训练算法:KNN没有这一步,这也是为何被称为最懒算法的原因。
  5. 测试算法:将提供的数据利用交叉验证的方式进行算法的测试。
  6. 使用算法:将测试得到的准确率较高的算法直接应用到实际中。

05|利用python对未知电影进行分类:

1、背景:

假设爱情电影和动作电影之间的区别可以用打斗次数和接吻次数这两个特征来决定,下面提供了一些电影的类别以及其对应的接吻和打斗次数(训练数据集)。

表6-1:来源于网络

现在有一电影A,已知其打斗次数为18,接吻次数为90,需要利用knn算法去预测该电影属于哪一类别。

2、准备数据

3、分析数据

4、测试算法

通过测试最后得出,如果一部电影中含有18次打斗次数,90次接吻次数,那么可以判定为该电影是爱情片。

5、应用算法:

通过修改inX的值,就可以直接得出该电影的类型。

06|最后:

上面python实现过程中涉及的一些知识点:

  1. pandas数据转换成numpy,df.matrix()
  2. matplotlib中文显示乱码问题
  3. 列表生成式
  4. np.tile()函数
  5. np.sum()函数
  6. np.argsort()函数
  7. dict.get()方法
  8. dict.items()方法
  9. operator.itemgetter()函数

原文发布于微信公众号 - 张俊红(zhangjunhong0428)

原文发表时间:2017-08-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏游戏开发那些事

【计算机图形学】计算机图形学中的坐标系统

  马三最近开始学习计算机图形学了,买了两本书,其中一本是国内的,还是什么大学的教材,不过写得真不咋样啊。另外一本是大名鼎鼎的《计算机图形学》第四版。最近接触了...

14110
来自专栏AI研习社

一文详解 Word2vec 之 Skip-Gram 模型(实现篇)

前言 上一篇的专栏介绍了Word2Vec中的Skip-Gram模型的结构和训练,如果看过的小伙伴可以直接开始动手用TensorFlow实现自己的Word2V...

68240
来自专栏深度学习自然语言处理

【收藏版】长文详解基于并行计算的条件随机场

之前写过CRF的详解,只是为了让大家详细了解下原理,但是那种是没有优化的,速度很慢。在实际应用中,还是需要用到batch,也就是需要用到GPU的,那么此时并行计...

8320
来自专栏杨熹的专栏

自己写个 Prisma

Sirajology的视频链接 前一段时间特别火的 Prisma 大家都玩了么,看了这篇文章后,你也可以自己写一个 Prisma 迷你版了。 ? 这个 idea...

41450
来自专栏ATYUN订阅号

解决机器学习中不平衡类的问题

大多数实际的分类问题都显示了一定程度的类不平衡,也就是当每个类不构成你的数据集的相同部分时。适当调整你的度量和方法以适应你的目标是很重要的。如果没有这样做,你可...

38060
来自专栏AI科技大本营的专栏

基于TensorFlow实现Skip-Gram模型

作者 | 天雨粟 整理 | AI100(rgznai100) 原文 - https://zhuanlan.zhihu.com/p/27296712 前言 上一篇...

26140
来自专栏大数据挖掘DT机器学习

逻辑回归之基础知识及手写数字识别实例

作者:daniel-D 原文:http://www.cnblogs.com/daniel-D/   这学期 Pattern Recognition 课程的 p...

90490
来自专栏AI研习社

机器学习算法究竟需要试验多少次,才能有效反映模型性能?

编者按:本文作者 Jason Brownlee 为澳大利亚知名机器学习专家,对时间序列预测尤有心得。原文发布于其博客。AI 研习社编译。文中相关链接详见文末“阅...

29260
来自专栏云时之间

关于分类问题的一些学习

这几天的时间里看了一下关于分类算法的一些知识,趁热打铁写下博客来拯救下记忆力不好的自己,话不读多说,马上开始! 先说一下前提的题设条件.假设我们现在有了一封邮...

27050
来自专栏AI科技大本营的专栏

AI从入门到放弃2:CNN的导火索,用MLP做图像分类识别?

阅读本文的基础:我会认为你对BP神经网络有充分的了解,熟读过我上一篇文章,本文会大量引用上一篇文章的知识以及代码。

15320

扫码关注云+社区

领取腾讯云代金券