机器学习实战-2-K近邻算法
本文中介绍的机器学习中最基础的一个算法:k-近邻算法,将从如下方面展开:
算法概述
k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。简单地说,k-近邻算法就是采用不同特征值之间的距离来进行分类,算法主要特点为:
- 优点:精度高,对异常值不敏感,没有数据输入假定
- 缺点:计算复杂度高,空间复杂度高
- 适用数据范围:数值型和标称型(男女)
有人曾经统计过很多电影的打斗镜头和接吻镜头,如下图显示的电影打斗镜头和接吻镜头:
假设有一部未看过的电影,如何确定它是爱情片还是动作片呢?我们看看下表的数据:
当我们不知道未知电影史属于何种类型,我们可以通过计算未知电影和其他电影的距离,按照电影的递增排序,可以找到k个距离最近的电影。在距离最近的电影中,选择类别最多的那部电影,即可判断为未知电影的类型。
比如k=5,这5部电影中3部是爱情片,2部是动作片,那么我们将未知电影归属为爱情片。
工作原理
- 存在一个样本数据集和数据标签,知道样本和标签的对应关系
- 输入没有标签的数据,将新数据的每个特征与样本集中数据对应的特征进行比较
- 提取样本集中特征最相似数据的分类标签,只选取前
k
个最相似的数据,一般k是小于20
算法步骤
- 计算已知类别数据集中的点与当前点之间的距离;
- 按照距离递增次序排序;
- 选取与当前点距离最小的
k
个点; - 确定前
k
个点所在类别的出现频率; - 返回前
k
个点所出现频率最高的类别作为当前点的预测分类。
机器学习中向量距离度量准则
下面👇列举了机器学习中常用的向量距离度量准则:
- 欧式距离
- 曼哈顿距离
- 切比雪夫距离
- 马氏距离
- 巴氏距离
- 汉明距离
- 皮尔逊系数
- 信息熵
图解过程
通过下面的一组图形来解释KNN算法的思想。
已知正方形和三角形两种类型,现在给定一个圆形,如何确定它是属于什么类型?
如果k=1,结果是三角形
如果k=3,结果还是三角形
如果k=5,结果是正方形
如果k=7,结果是正方形
通过上面的例子,我们得到一个结论:当k取不同值的时候,KNN算法的结果是不同的,所以k值的选取非常重要。
Python3版本代码
伪代码
首先给出KNN算法的伪代码(对未知类别属性的数据集中的每个点依次执行以下操作):
- 计算已知类别数据集中的点和当前点之间的距离
- 按照距离递增次序排序
- 选取与当前距离最小的k个点
- 确定k个点所在类别的出现频率
- 返回前k个点出现频率最高的类别作为当前点的预测分类
Python3实现
下面给出实际的Python3的代码。使用内置的collections
模块来解决:
1 | import pandas as pd |
运行上面的代码,显示的结果为:
- dist:待预测的电影和已知电影欧式距离
- k_labels:取出排序后前(k=3)3个最小距离的电影对应的类别标签,结果是
["动作片","动作片","爱情片"]
- label:判断的结果是动作片,因为动作片有2票
代码解释
1、函数首先需要生成数据集:关于给出的前4部电影,已知打斗次数和接吻次数,同时还有电影的分类情况;
2、现在新出现了一部电影:打斗次数是98,接吻次数是17,如何确定其属于哪种类型的电影?
打斗次数 | 接吻次数 | 电影分类 | |
---|---|---|---|
1 | 1 | 101 | 爱情片 |
2 | 5 | 89 | 爱情片 |
3 | 108 | 5 | 动作片 |
4 | 115 | 8 | 动作片 |
待预测 | 98 | 17 | ? |
不使用collections模块如何解决?
1 | import numpy as np |
classfiy函数有4个输入参数:
- 用于分类的输入向量inX
- 输入的训练样本集合为dataSet
- 标签向量为labels
- 用于选择最近邻居的数目k
其中标签向量的元素数目和矩阵dataSet的行数相同
看看具体的解释:
1、原始数据是什么样子?
打印出来的效果:
2、为什么使用np.tile方法?
为了和dataSet的shape保持一致,方便后续的求距离
3、每个距离和相对的索引关系
Jupyter notebook中使用KNN算法
步骤
下面也是通过一个模拟的电影数据来讲解如何在jupyter notebook
中使用KNN
算法,大致步骤分为:
- 构建数据集
构建一个包含接吻镜头、打斗镜头和电影类型的数据集
2、求距离
求出待预测分类的数据和原数据的欧式距离
3、距离排序
将求出的距离进行升序排列,并取出对应的电影分类
4、指定取出前k个数据
取出指定的前k个数据,统计这些数据中电影类型的频数,找出频数最多的类型,即可判断为未知待预测电影的类型
代码
1、模拟数据:
2、求解距离
3、对距离升序排列
4、取出前k个数并统计频数
封装成函数
将上面的整个过程封装成函数:
1 | import pandas as pd |
利用上面模拟的数据测试一下我们封装的代码,结果是相同的
参考资料
1、《机器学习实战》一书
3、《统计学习方法》-李航老师