Python AI 教学 | KNN算法及应用
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等期刊上。