机器学习实战之拆解K近邻算法！

点击上方关注，All in AI中国

作者——Onel Harrison

K近邻算法(KNN)是一种简单、易于实现的有监督机器学习算法，可用于分类和回归问题的求解。现在，来让我们了解它。

ABC，我们要保持它的简单性！

把它拆散

监督机器学习算法(相对于无监督的机器学习算法)是一种通过标记的输入数据来学习在给定的、新的未标记数据时产生适当输出函数的算法。

想象电脑是一个孩子，我们是它的主管(例如家长、监护人或老师)，我们想让孩子(电脑)知道猪长什么样。我们将给孩子看几张不同的照片，其中一些是猪，其余的可能是任何东西(猫、狗等)的照片。

当我们看到一只猪，我们喊"猪！"当它不是猪的时候，我们就喊"不，不是猪！"在和孩子做了几次之后，我们给他们看了一张照片，问"猪？"，他们会正确地(大多数时候)说"猪！"或者"不，不是猪！"，这取决于图片是什么。这就是有监督的机器学习。

"猪！"

有监督的机器学习算法被用来解决分类或回归问题。

分类问题的输出值是离散的。例如，"喜欢菠萝味的比萨饼"和"不喜欢菠萝味的比萨饼"的情况是离散的。不存在"喜欢又不喜欢"的情况。上面教孩子识别猪的类比是分类问题的另一个例子。

显示随机生成数据的图像

此图像显示了分类数据可能是什么样子的基本示例。我们有一个预测器(或一组预测器)和一个标签。在图像中，我们可能会根据某人的年龄(预测因素)来预测某人是否喜欢菠萝味的披萨(1)。

标准做法是将分类算法的输出(标签)表示为整数，如1、-1或0。在这种情况下，这些数字仅用来表示。不应该对它们执行数学运算，因为这样做是毫无意义的。因为"喜欢菠萝味"+"不喜欢菠萝味"是不符合我们的表达的，所以我们也不应该对它们的数字表示"指手画脚"。

回归问题的输出多是实数(带有小数点的数字)。例如，我们可以使用下表中的数据根据身高来估计一个人的体重。

图像显示了部分身高和体重的数据集（http://wiki.stat.ucla.edu/socr/in

回归分析中使用的数据将类似于上面图像中显示的数据。我们有一个自变量(或一组自变量)和一个因变量(通过自变量，我们正在试图猜测的东西)。例如，我们可以说身高是自变量，重量是因变量。

此外，每一行通常被称为示例、观察或数据点，而每一列(不包括标签/因变量)通常被称为预测器、维数、自变量或特征。

而无监督机器学习算法使用没有任何标签的输入数据，换句话说，没有老师(标签)告诉孩子(计算机)什么时候正确，什么时候出错，他要进行自我纠正。

不像监督学习，它试图学习一个函数，让我们在一些新的没有标记的数据下做出预测，无监督学习试图学习数据的基本结构，让我们对数据有更深入的了解。

K近邻算法

KNN算法假设相似的事物在很近的距离内存在。换句话说，相似的事物是相互接近的。

即"物以类聚"。

图像将显示相似的数据点是如何相互靠近的（https://commons.wikimedia.org/

请注意，在上面的图像中，大多数情况下，相似的数据点是相近的。KNN算法依赖于这样的假设，只有在这样的假设下，该算法才是有效的。KNN算法用我们小时候学过的一些数学知识(计算图上点之间的距离)来描述相似(有时称为距离、接近)的概念。

注：在继续之前，了解我们如何计算图上点之间的距离是必要的。如果你不熟悉或需要对此计算方法进行复习，请阅读"两点之间的距离"

（https://www.mathsisfun.com/algebra/distance-2-points.html）。

还有其他计算距离的方法，根据我们正在解决的问题，有一种方法可能更可取。在这里，直线距离(又称欧几里得距离)是一种很受欢迎和熟悉的选择。

KNN算法

1.加载数据

2.将近邻算法中的K初始化

3.对于数据中的每个示例

3.1在数据中计算所求证示例与当前示例之间的距离

3.2将示例的距离和索引添加到有序集合中

4.按距离将距离和索引的有序集合从最小到最大(按升序排列)排序

5.从排序集合中选择第一个K项

6.获取所选K项的标签

7.如果回归，则返回K标签的平均值

8.如果分类，则返回K标签的模式

KNN实现(从头开始)

为K选择正确的值

为了选择对你的数据正确的K，我们尝试使用不同的K值多次运行KNN算法，并选择误差较小的K值，同时保持该算法在给定数据时精确预测的能力，这是我们以前从未见过的。

以下是一些需要记住的事：

当K减小到1时，我们的预测就不那么稳定了。想想看，图像K=1，我们有一个查询点，被几个红色和一个绿色包围着(我想的是上面彩色图的左上角)，但是绿色是最近的一个邻居。合理地说，我们认为查询点很可能是红色的，但是因为K=1, KNN错误地预测查询点是绿色的。

但是，随着K值的增加，我们的预测变得更加稳定，因此，我们更有可能做出更准确的预测(直到在某个点结束)。但俗话说"物极必反"，如果我们把K的值推得太远了，我们会发现错误变得越来越多。

如果我们在标签中进行了多数"投票"(例如在分类问题中选择模式)，我们通常会使K为奇数，以得到一个平分。

优点

1.该算法简单，易于实现。

2.没有必要建立一个模型，调优几个参数，或作出额外的假设。

3.该算法是通用的。它可以用于分类、回归和搜索(我们将在下一节中看到)。

缺点

随着示例数/预测因子/自变量的增加，算法速度明显变慢。

KNN在实践中的应用

KNN的主要缺点是随着数据量的增加而明显变慢，因此在需要快速进行预测的环境中，KNN是一种不切实际的选择。此外，还有更快的算法可以产生更准确的分类和回归结果。

但是，如果你有足够的计算资源来快速处理用于进行预测的数据，那么KNN在解决具有依赖于识别相似对象的解决方案的问题时仍然很有用。其中一个例子是在推荐系统中使用KNN算法，这是对KNN-search函数的一个应用。

推荐系统

在规模上，这看起来就像是在亚马逊上推荐产品，在媒体上发表文章，在Netflix上看电影，或者在YouTube上播放视频。尽管如此，我们可以肯定，尽管它们处理的数据量很大，但它们都有一套有效的方法来提出建议。

我们可以在较小的范围内复制这些推荐系统上的内容，使用我们在本文中学到的知识，来建立电影推荐系统的核心。

我们要回答什么问题？

在给定我们的电影数据集中，选择出的与你选定电影最相似的5部电影是什么？

收集电影数据

如果我们在Netflix、Hulu或IMDb工作，我们可以从他们的数据仓库获取数据。但是我们在任何一家公司都不工作，所以我们必须通过其他方法来获取我们的数据。我们可以从UCI机器学习库（https://archive.ics.uci.edu/ml/datasets/Movie）、IMDb的数据集（https://www.imdb.com/interfaces/）或者辛苦地创造我们自己的数据集。

探索、清理和准备数据

无论我们在哪里获得数据，都可能存在一些错误，我们需要对其进行修正，以便为KNN算法做好准备。例如，数据可能不是算法所期望的格式，或者在将数据排入算法之前，我们应该填充或删除数据中缺少的值。

我们上面KNN算法的实现依赖于结构化数据。它必须是表格格式。此外，该实现假定所有列都包含数值数据，并且数据的最后一列具有可以执行某些功能的标签。因此，无论我们从哪里获得数据，我们都需要使其符合这些条件。

下面的数据是我们要举的一个例子。该数据包含30部电影，包括七种类型的电影的数据及其IMDB评分。标签列为零是因为我们没有使用这个数据集进行分类或回归。

自制电影推荐数据集

此外，在使用KNN算法时，电影之间的关系将不会被考虑(例如演员、导演和主题)，因为捕捉这些关系的数据在数据集中丢失了。因此，当我们在数据上运行KNN算法时，相似性将完全基于包含的类型和电影的IMDB评级。

使用算法

想象一下。我们正在浏览MoviesXb网站，这是一个IMDb派生的网站，我们突然看见了《The Post》（https://www.imdb.com/title/tt6294822/?ref_=adv_li_tt ），我们不确定我们是否想看它，但它的体裁吸引了我们；我们对其他类似的电影很好奇。我们向下滚动到"更像这个"部分，看看MoviesXb将提出什么建议，算法的齿轮也将开始转向。

MoviesXb网站向其后端发送一个请求，以获取最类似于《The Post》的电影。后端具有与我们完全相同的推荐数据集。它首先为Post创建行表示(通常称为feature vector)，然后运行一个类似于下面的程序来搜索与《The Post》最相似的5个电影，最后将结果发送回MoviesXb网站。

当我们运行这个程序时，我们看到MoviesXb推荐了为奴12年, 钢锯岭, 卡推女王, 风起云涌和美丽心灵等电影。现在我们已经完全理解了KNN算法是如何工作的，我们能够准确地解释KNN算法是如何提出这些建议的。祝贺你!

总结

K近邻(KNN)算法是一种简单、有监督的机器学习算法，可用于分类和回归问题的求解。它很容易实现和理解，但它的一个主要缺点是，随着使用中的数据的大小增加，它的速度会明显减慢。

KNN的工作方式是查找查询和数据中所有实例之间的距离，选择最接近查询的指定数量的示例(K)，然后"投票"选出频率最高的标签(在分类情况下)或平均标签(在回归情况下)。

在分类和回归的情况下，我们看到为我们的数据选择正确的K是通过尝试几个K并选择最有效的K来完成的。

最后，我们研究了KNN算法在推荐系统中的应用实例，这是 KNN-search函数的一个应用。