k近邻法(k-nearest neighbor, k-NN)
参考:机器学习实战教程(一):K-近邻(KNN)算法(史诗级干货长文) (cuijiahua.com)
《机器学习实战》
《统计学习方法》
核心思想介绍
1. 算法简介
给定一个训练数据集,对新的输入实例,在训练数据集中找到于该实例最邻近的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。
模型主要由三个要素来决定:
距离度量、k值得选择和分类决策规则
2. 数理讲解
1)距离度量
主要引入较为普遍的欧式距离(二维情况下两点间距离):p>=1,即p=2时,
2)k值的选取会对该算法产生重大影响
![image-20220707153829905](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220707153829905.png)
3)分类决策规则
![image-20220707154133243](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220707154133243.png)
可以使误分类率最小,即经验风险最小。
3. 算法代码主体部分
代码实现如下,具体思路是输入一个实例,并将这个实例按照训练数据集实例个数,复制自身拓展为多维矩阵,分别与每一个训练数据集实例相减计算距离,将距离排序,筛选出最近的k个实例,了解k个实例中哪个类别的实例数量最多,那么就将这个类别判定给最新的这个实例。
|
应用案例一:使用k-近邻算法改进约会网站的配对效果
1. 背景和所涉函数&框架
背景:海伦一直使用在线约会网站寻找约会对象,她根据经验将约会对象分为三类(不喜欢的人、魅力一般的人、极具魅力的人),她搜集了一些约会对象的数据(有3个特征,分别是每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数),希望能采用kNN算法帮助她对未来的约会对象进行归类。
函数清单:
- classify0(inX, dataSet, labels, k)
inX是用于分类的输入向量,dataSet是训练集,labels是训练集对应的标签,k是最近邻实例的数量
k-近邻算法,计算距离并预测新实例所属类别
输出结果:sortedClassCount,是所属类别
file2matrix(filename)
filename是数据文件
数据整理,把数据整理为两个矩阵,一个是特征矩阵,一个是分类矩阵,并为分类矩阵打好数字标签
输出结果:datingDataMat 特征矩阵, datingLabels分类矩阵
showdatas(datingDataMat, datingLabels)
制作散点图
autoNorm(dataSet)
dataSet是特征矩阵
按照归一化的公式来对原始特征矩阵进行处理
输出结果:normDataSet新的特征矩阵, ranges最大最小值之间差, minVals最小值
2. 具体操作
(1)数据处理
测试数据描述:如下图,一共有1000个可选约会对象实例,前三列为特征向量(浮点数),最后一列为分类标签(字符)。
![image-20220705181116009](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220705181116009.png)
代码实现如下,主要思想是将文件内的数据按照行来打散成为字符串列表,按照每个实例(每行),将其前三列数值填充进形成好的零矩阵中,并将将最后一列标签值赋予数值,遍历所有实例,完成填充和赋值。
|
结果如下:1000个都已经赋值
![image-20220706231822222](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220706231822222.png)
(2)分析数据:使用Matplotlib创建散点图
通过描述性统计,采用不同特征组合,看下数据是否根据类别不同有所区分。
|
结果如下:可以看到采用第一和第二种特征搭配,能够将三个群体较有效地区隔开来。
![image-20220706232126367](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220706232126367.png)
(3)准备数据:归一化
根据下表可以看到,特征”每年获得的飞行常客里程数“整体数值远高出另外两种特征,因此在计算两个实例间的距离时,该特征的影响会被放大,因此需要将数值归一化,即将取值范围处理为0到1或者-1到1之间(三个特征值都同时被处理归一)。
![image-20220705235917444](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220705235917444.png)
具体归一化公式如下:
代码实现如下,主要思想是分别计算最大最小值,以及最大最小值之间的差,并在与原始值计算时将这些数值转化为矩阵模式来计算,按照如上的归一化公式计算得到最终新的特征矩阵:
|
结果如下:
![image-20220706232408013](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220706232408013.png)
(4)测试算法
采用错误率来测试算法是否准确,对于分类器来说,错误率就是分类器给出错误结果的次数除以测试数据的总数,完美分类器的错误率为0,而错误率为1.0的分类器不会给出任何正确的分类结果。
代码实现如下:
|
结果如下:可以看到本次结果有5%的可能性被分错
![image-20220706232522290](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220706232522290.png)
(5)使用算法
|
结果如下:输入三个特征维度值,预测结果如下,且可能有5%的概率是预测错误的。
![image-20220706233737086](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220706233737086.png)
应用案例二:手写识别系统
数据展示:第一个图片是文件夹打开后,将图像转化为.txt格式的二进制文件,文件名首位是该文件所代表的数值。
![image-20220707152627709](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220707152627709.png)
如下是文件打开后,是二进制图像
![image-20220707152833588](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220707152833588.png)
代码实现如下,基本思路和应用案例一一致,只是需要将每个图像转化为有1024个特征的向量:
|
结果如下:可看到该模型测试后误差比较高,可以通过改变k值改变误差,但效果不太好,可能和模型或者数据相关。
![image-20220707153235119](/2022/07/07/kNN%E7%AE%97%E6%B3%95/image-20220707153235119.png)
其他:关于hexo就本地图片无法显示的问题Hexo上markdown图片路径与Typora保持一致 | He’s Blog (algorithmofdish.tech)
关于hexo公式显示的问题如何在hexo显示图片与公式 | Keep (liaokai.com.cn)