Python AI 教学 | KNN算法及应用

1、KNN的数学原理

KNN(K-Nearest Neighbor)

∈ 分类算法 ∈ 监督学习 ∈ 机器学习

基本思想

简单来说,KNN可以看成有一堆你已经知道其所属类别的数据(训练数据),然后当一个新数据进入的时候,就开始跟训练数据里的每个点求距离,然后挑离这个新数据最近的K个点(K的选择极其重要)看看这几个点属于什么类型,然后用少数服从多数的原则,给新数据归类到多数数据所在的类别里。

1.1

距离的计算

一般来说,我们选择欧氏距离公式计算数据之间的距离:

例如,在三维空间以下(数据只有一到三个维度),其欧氏距离也即空间距离,如图1所示:

图1

1.2

k值的选择

K的选择非常重要!

例如,从图2来看,如果K=3,那么离绿色点最近的3个点中有2个红和1个蓝,这三个点执行“少数服从多数”规则,于是绿点就属于红色类别。而如果K=5,那么离绿点最近的5个点中有2个红和3个蓝,同样执行“少服多”规则,于是绿点就属于蓝色类别。

图2

2、KNN算法实现

准备数据

假设有四个点,已知各自的坐标与标签:右上角的两个点标签为A,左下角的两个点标签为B。那么任意给定一个坐标,它应被贴上哪个标签呢?

算法实现

导入数据·

·KNN算法·

运行结果:

函数说明

在这个算法中,我们可以学习到四个函数,分别是:

【1】np.shape——用于读取矩阵的形状

运行结果:

此外也可以用来调节数组的大小:

与之相关的关于数组属性的函数还有:

详见:

http://www.runoob.com/numpy/numpy-array-attributes.html

【2】tile——用于复制矩阵

运行结果:

常见的数组操作还包括修改矩阵形状,翻转数组,修改数组维度,连接数组,分割数组,数组元素的添加与删除。

详见:

http://www.runoob.com/numpy/numpy-array-manipulation.html

【3】argsort——用于对矩阵中的元素由小到大进行排序,并提取其相应的位置(index)

运行结果:

【4】 sorted——用于对矩阵中的元素进行条件排序,并返回输入数组的排序副本。其基本函数语法如下:sorted(iterable, key=None, reverse=False)

其中①iterable为操作对象数组;②key指定操作对象数组中的一个元素来进行排序;③reverse为排序规则,True为降序,False为升序(默认)。

运行结果:

详见:

http://www.runoob.com/numpy/numpy-sort-search.html

3

KNN应用

海伦一直以来都在使用约会网站寻找适合自己的约会对象。该约会网站使用了KNN算法作为推荐系统。为了测试约会网站所推荐的人选是否靠谱,海伦决定自己收集约会数据以验证其有效性。

3.1

收集与准备数据

海伦将长久以来收集的数据存放在文件datingTestSet.txt中,这是一组1000行的数据(海伦交往过的1000个人),每行数据有四个元素:包括三个特征(分别为:“每年的飞行常客里程数”、“玩游戏所占时间百分比”、“每周消费的冰淇淋公升数”)与一个标签(标签有三种类型:“不喜欢”、“魅力一般”、“极具魅力”)。

【1】将这些数据转化为Python可读取的格式

运行结果:

【2】利用Matplotlib制作散点图,使原始数据可视化

运行结果:

【3】归一化处理

KNN的核心是通过计算欧氏距离确定数据之间的相关性。因此数字差值最大的属性对于计算结果的影响也就越大,也就是说,“每年的飞行常客里程数”对于计算结果的影响将远远大于其他两个特征“玩游戏所占时间百分比”和“每周消费的冰淇淋公升数”的影响。因此需要对数据进行归一化处理。

运行结果:

3.2

测试与使用算法

如果该约会网站的推荐系统(KNN分类器)的正确率满足要求,海伦就可以放心的与约会网站推荐的人选进行约会了。

【1】测试算法:将海伦所收集的1000行数据按照9:1的比例,随机分为训练集与测试集。分类器的错误率即,错误结果的总数/测试集的总数。

【2】使用算法:以上结果说明该约会网站的推荐系统的错误率仅为0.1%,因此海伦完全可以信任该约会网站所推荐的人选。也可以通过输入某个人的特征信息,由分类软件帮助其判断该对象的可交往程度,即标签。

责编 | 申 罗 栾

指导 | 薛

后注:

本文转载自公众号:老薛带你学Python

作者简介:

薛巍立,男,博士,东南大学经济管理学院教授,博士生导师,国家自然科学基金优秀青年基金项目获得者。博士毕业于香港中文大学系统工程与工程管理系,主要从事供应链物流管理、运营风险管理和医疗服务运作管理等。主要成果发表在Operations Research、Production and Operations Management、Transportation Science、European Journal of Operational Research、Operations Research Letters等期刊上。

本文分享自微信公众号 - 数据魔术师(data-magician)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-06

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券