第3章

图像分类之KNN算法

本章将讲解一种最简单的图像分类算法，即K-最近邻算法（K-NearestNeighbor，KNN）。KNN算法的思想非常简单，其涉及的数学原理知识也很简单。本章希望以KNN容易理解的算法逻辑与相对容易的Python实现方式帮助读者快速构建一个属于自己的图像分类器。

本章的要点具体如下。

•  KNN的基本介绍。

• 机器学习中KNN的实现方式。

•  KNN实现图像分类。

3.1　KNN的理论基础与实现

3.1.1　理论知识

KNN被翻译为最近邻算法，顾名思义，找到最近的k个邻居，在前k个最近样本（k近邻）中选择最近的占比最高的类别作为预测类别。如果觉得这句话不好理解，那么我们可以通过一个简单示例（如图3-1所示）来进一步说明。

绿色圆（待预测的）要被赋予哪个类，是红色三角形还是蓝色四方形？如果k=3（实线所表示的圆），由于红色三角形所占比例为2/3，大于蓝色四方形所占的比例1/3，那么绿色圆将被赋予红色三角形那个类。如果k=5（虚线所表示的圆），由于蓝色四方形的比例为3/5大于红色三角形所占的比例2/5，那么绿色圆被赋予蓝色四方形类。

通过上述这个例子，我们可以简单总结出KNN算法的计算逻辑。

1）给定测试对象，计算它与训练集中每个对象的距离。

2）圈定距离最近的k个训练对象，作为测试对象的邻居。

3）根据这k个近邻对象所属的类别，找到占比最高的那个类别作为测试对象的预测类别。

在KNN算法中，我们发现有两个方面的因素会影响KNN算法的准确度：一个是计算测试对象与训练集中各个对象的距离，另一个因素就是k的选择。

这里先着重讲一下距离度量，后面的小节中我们将着重讲述如何选择k（超参数调优）。对于距离度量，一般使用两种比较常见的距离公式计算距离：曼哈顿距离和欧式距离。

（1）曼哈顿距离（Manhattan distance）

假设先只考虑两个点，第一个点的坐标为(x1, y1)，第二个点的坐标为(x2, y2)，那么，它们之间的曼哈顿距离就是| x1-x2 | + | y1-y2 |。

（2）欧式距离（Euclidean Metric）

以空间为基准的两点之间的最短距离。还是假设只有两个点，第一个点的坐标为(x1, y1)，第二个点的坐标为(x2, y2)，那么它们之间的欧式距离就是。