首页 > 学术百科

【机器学习】一文搞懂K近邻算法（KNN），附带多个实现案例

【机器学习】⼀⽂搞懂K近邻算法（KNN），附带多个实现案

例

【机器学习】⼀⽂搞懂K近邻算法(KNN)，附带多个实现案例

⼀、KNN回顾

kk k 近邻学习是⼀种常⽤的监督学习⽅法，⽐如：判断⼀个⼈的⼈品，只需要观察与他来往最密切的⼏个⼈的⼈品好坏就可以得出，即“近朱者⾚，近墨者⿊”。

⼆、KNN三要素

1、K值的选择

对于K值的选择，⼀般根据样本分布选择⼀个较⼩的值，然后通过交叉验证来选择⼀个⽐较合适的最终值；

当选择⽐较⼩的K值的时候，表⽰使⽤较⼩领域中的样本进⾏预测，训练误差会减⼩，但是会导致模型变得复杂，容易导致过拟合；

当选择较⼤的K值的时候，表⽰使⽤较⼤领域中的样本进⾏预测，训练误差会增⼤，同时会使模型变得简单，容易导致⽋拟合；

2、距离度量

思其始而成其终⼀般使⽤欧⼏⾥德距离

关于距离度量，还有其他⽅式

3、决策规则

KNNKNN KNN在做回归和分类的主要区别在于最后做预测时的决策⽅式不同：

（1）分类预测规则：⼀般采⽤多数表决法或者加权多数表决法

假设图中 “？”表⽰待预测样本，红⾊圆表⽰⼀类，蓝⾊⽅块表⽰⼀类，2和3表⽰到待预测样本的距离

1. 多数表决法：

一位母亲与家长会阅读答案2. 加权多数表决法：

（2）回归预测规则：⼀般采⽤平均值法或者加权平均值法

假设上图中的2和3表⽰邻近样本的⽬标属性值（标签值），此时没有类别，只有属性值1. 平均值法

1. 加权平均值法

栗东生

图中，双箭头线上的数表⽰到待预测样本的距离

三、⼿写kk k近邻算法

实现kNN分类算法的伪代码：

对未知类别属性的数据集中的每个点依次执⾏⼀下操作：

（1）计算已知类别数据集中的点与当前点之间的距离国外育儿经

（2）按照距离递增次序排序

（3）选取与当前点距离最⼩的k个点

（4）确定前k个点所在类别的出现频数

叶氏养胃汤（5）返回当前k个点出现频数最⾼的类别作为当前点的预测分类

欧⽒距离公式：

d=∑mi=1(xi−yi)2−−−−−−−−−−−−√d = \sqrt{\sum_{i=1}^m(x_i - y_i)^2}d=i=1∑m(xi−yi)2

例如求点(1,0,0,1)(1,0,0,1)(1,0,0,1)和(7,6,9,4)(7,6,9,4)(7,6,9,4)之间的距离：

(7−1)2+(6−0)2+(9−0)2+(4−1)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−√\sqrt{(7-1)^2+(6-0)^2+(9-0)^2+(4-1)^2}(7−1)2+(6−0)2+(9−0)2+(4−1)2

以上算法的实现是⽤于分类的，决策规则使⽤了多数表决法；此算法通过改变决策规则，同样可以⽤于回归。

源代码可见：下 01_k近邻算法.py

四、使⽤⼿写kk k近邻算法的案例

1、案例1：约会⽹站的配对效果

样本包括3种特征：

每年获得的飞⾏常客⾥程数

玩视频游戏所耗时间百分⽐

每周消费的冰淇淋公升数

样本包括3种标签：

不喜欢的⼈

魅⼒⼀般的⼈

极具魅⼒的⼈

部分数据格式为：

每年获得的飞⾏常客⾥程数玩视频游戏所耗时间百分⽐每周消费的冰淇淋公升数标签409208.3269760.9539523 144887.153469 1.6739042 26052 1.4418710.8051241

代码可见：02_约会⽹站的配对效果.py

2、案例2：⼿写数字识别系统

数据集包括训练集和测试集

数据是32*32的⼆进制⽂本⽂件

需要将⽂本数据转换为Numpy数组

如下是0的⼀种表⽰：

<span ><code>00000000000001100000000000000000

00000000000011111100000000000000

00000000000111111111000000000000

00000000011111111111000000000000

00000001111111111111100000000000

00000000111111100011110000000000

00000001111110000001110000000000

00000011111100000001110000000000

00000011111100000001111000000000

00000011111100000000011100000000

00000011111000000000001110000000

00000001111100000000000111000000

00000011111000000000000111000000

00000000111100000000000011100000

00000000111100000000000111100000

00000000111100000000001111100000

00000000011110000000000111110000

台湾公共电视00000000011111000000001111100000

00000000011111000000011111100000

00000000011111000000111111000000

00000000011111100011111111000000

00000000000111111111111110000000

00000000000111111111111100000000

00000000000011111111110000000000

00000000000000111110000000000000

</code></span>

预测错误的总数为：10

⼿写数字识别系统的错误率为：0.010571

代码可见：03_⼿写数字识别系统.py

六、KD树

KNN算法的重点在于出K个最邻近的点，主要⽅法如下：

1、蛮⼒实现(brute)

计算出待预测样本到所有训练样本的训练数据，然后选择最⼩的K个距离即可得到K个最邻近点；

当特征数⽐较多，样本数⽐较多的时候，算法的执⾏效率⽐较低

2、KD树(KD_Tree)

KD_Tree算法中，⾸先是对训练数据进⾏建模，构建KD树，然后再根据构建好的模型来获取邻近样本数据KD_Tree是KNN算法中⽤于计算最近邻的快速、便捷构建⽅式

除此之外，还有⼀些从KD_Tree修改后的求解最邻近点的算法，⽐如：Ball Tree、BBF Tree、MVP Tree等

本文发布于:2024-09-22 11:33:57，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/326076.html

上一篇：KNN算法应用

下一篇：knn算法是有监督还是无监督

标签：预测样本算法数据距离

留言与评论（共有 0 条评论）