KNN算法原理及代码实现

在本文中,我们将讨论一种广泛使用的分类技术,称为K最近邻(KNN)。我们的重点主要集中在算法如何工作以及输入参数如何影响预测结果。

内容包括:

何时使用KNN算法?

KNN算法原理

如何选择K值

KNN算法伪码

Python实现KNN算法

与scikit-learn比较

何时使用KNN算法

KNN算法可以同时应用到分类和回归问题。然而,KNN在实际应用中更多的是用于分类问题。为了更好的评价一个算法优劣,我们从以下三个重要的指标分析:

预测结果的可解读性

运行时间

预测准确性

KNN算法与逻辑回归(Logistic Regression)、决策树CART(Classification And Regression Tree,简称CART)、随机森林(Random Forest)对比如下表

相对于其他算法,KNN算法在这三个评价指标表现相对均衡优异。

如何选择K值

让我们看一个简单的例子来理解KNN。下图中有三种点,(3个带你)、(3个点)以及未知类别的某。

我们试图找到的所属类别,它要么属于要么属于。算法KNN中的指的是某点的K个用来投票的邻居,少数服从多数。K个邻居中投票最多的属性代表该点的属性。在本例子中我们将K设置为3,我们会给画一个圈围住最近的K=3个点。最终大概类似于下图

我们看到最近的三个邻居都是,所以我们可以认为蓝星的类别是。在本例中,对的分类是非常明显的,因为来自最近邻居的三张选票都投给了。参数K的选择在该算法中非常重要。接下来我们将了解哪些因素需要考虑,以得出最佳的K。

如何选择K值

首先让我们理解K值到底如何影响KNN算法。如果我们

有很多蓝色点和红色点数据,使用不同K值,最终的分类效果大概如下图。我们发现随着K值的增大,分界面越来越平滑。

一般在机器学习中我们要将数据集分为训练集和测试集,用训练集训练模型,再用测试集评价模型效果。这里我们绘制了不同k值下模型准确率。

从上图中我们发现当和时,KNN的误差都很大。但是在某个点时能够将误差降低到最小。在本例中

KNN算法伪码

我们现在设计下KNN伪码:

一. 读取数据二. 初始化k值三. 为了得到测试数据的预测类别,对训练集每条数据进行迭代

计算测试数据与训练集中每一条数据的距离。这里我们选用比较通用的欧几里得距离作为距离的实现方法。

对距离进行升序排列

对排列结果选择前K个值

得到出现次数最多的类

返回测试数据的预测类别

用Python实现KNN算法

这里我们使用iris数据集来构件KNN模型。

我们先测试下

运行结果

现在我们将k设置为3.

运行结果

运行结果

与scikit-learn比较

运行结果

我们仅仅用了一个例子,当k=3时,从scikit库knn算法的运行结果与我们设计的完全一致。neigbors都是[141, 139, 120]

小节

KNN算法是最简单的分类算法之一,即便算法如此简单,模型表现极佳。 KNN算法也可用于回归问题。 与所讨论方法的唯一区别是使用最近邻居的平均值而不是最近邻居的投票。

往期文章

昨日财报

赞赏、点赞、转发、AD支持都是对大邓的认可和支持,希望大家在阅读后顺便帮大邓转发一下。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180620G0DSRS00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券