教你用OpenCV实现机器学习最简单的k-NN算法

前言：OpenCV 的构建是为了提供计算机视觉的通用基础接口，现在已经成为经典和最优秀的计算机视觉和机器学习的综合算法工具集。作为一个开源项目，研究者、商业用户和政府部门都可以轻松利用和修改现成的代码。

k-NN算法可以认为是最简单的机器学习算法之一。本文教你利用OpenCV 和 Python 的基础知识，实现 k-NN算法。

01 

使用分类模型预测类别：问题的提出

假设在一个叫作随机镇的小镇，人们对他们的两个运动队随机城红队和随机城蓝队非常痴迷。红队历史悠久，深受人们喜爱。但随后一些外镇的百万富翁来到小镇，买下红队中最出色的得分手，并开始组建一支新的球队，蓝队。

除了让大部分红队球迷不满之外，那个最出色的得分手依旧可以在蓝队中一步一步赢得冠军。尽管依旧会有一些永远无法原谅他早期职业选择的球迷不满，几年之后他还是会返回红队。

但无论如何，你可以发现红队球迷与蓝队球迷的关系并不好。事实上，这两队的球迷因为不愿与对方做邻居，连住所都是分开的。我甚至听到过这种故事，红队球迷在蓝队球迷搬到家附近时，会故意搬走到其他地方。这是真实的故事！

无论如何，我们一无所知的进入这个小镇，尝试挨家挨户卖给人们一些蓝队的货物。然而，时不时地会遇到一些热血的红队球迷会因为我们售卖蓝队的东西而对我们大喊大叫，并把我们驱赶出他们的草坪。非常不友好！如果可以避免这些房屋而仅仅访问那些蓝队球迷的家，压力将会更小，也可以更好地利用时间。

由于坚信可以学会预测红队球迷居住的地方，我们开始记录每次的访问。如果遇到了一个红队球迷的家，就在手边的小镇地图上画一个红色三角形；否则，就画一个蓝色正方形。一阵子之后，我们就非常了解他们的居住信息了。

▲随机镇的小镇地图

然而，现在我们到了地图中绿色圆圈标记的房子前了。应该敲门吗？我们尝试着找到一些线索来确定他们支持哪个球队（也许在后阳台上插着球队的旗帜），但没有找到。那如何知道敲门是否安全呢？

这个有些愚蠢的例子准确说明了监督学习算法可以解决的一类问题。我们有一些观察信息（房屋、房屋的地点和他们支持球队的颜色）组成了训练数据。可以使用这些数据来从经验里学习，这样当面对预测新房子的主人支持的球队颜色这一任务时，就可以有足够的信息做出评估。

正如前面所说，红队的球迷对他们的球队非常狂热，因此他们绝不可能成为蓝队球迷的邻居。我们是否可以使用这个信息比对所有邻居的房屋，以此来查明居住在新房子中的是哪一队的球迷？

这正是k-NN算法将要处理的问题。

02 

理解 k-NN 算法

k-NN算法可以认为是最简单的机器学习算法之一。原因是我们只需要存储训练数据集。接下来，为了对新数据点进行预测，仅需要在训练数据集中找到它最近邻的点就可以了。

简单而言，k-NN算法认为一个数据点很可能与它近邻的点属于同一个类。思考一下：如果我们的邻居是红队球迷，我们很可能也是红队球迷，否则我们可能很早之前就搬家到其他地方了。对于蓝队球迷而言也是这样。

当然，有些社区可能稍微复杂一些。在这种情况下，我们将不仅仅考虑我们最近邻的类别（即k=1），而是考虑k个最近邻的类别。对于前面提到的例子，如果我们是红队球迷，我们可能不会搬到邻居大部分都是蓝队球迷的地方。

这就是它的全部了。

03 

使用 OpenCV 实现 k-NN

使用OpenCV，可以很轻松地通过cv2.ml.KNearest_create()函数来创建一个k-NN模型。然后进行以下几步：

1. 生成一些训练数据。

2. 指定k值，创建一个k-NN对象。

3. 找到想要分类的新数据点的k个最近邻的点。

4. 使用多数投票来分配新数据点的类标签。

5. 画出结果图。

首先引入所有必需的模块：使用k-NN算法的OpenCV、处理数据的NumPy、用于绘图的Matplotlib。如果使用Jupyter Notebook，别忘了调用%matplotlib inline魔法命令。

1. 生成训练数据

第一步是生成一些训练数据。我们将使用NumPy的随机数生成器来完成这个操作。我们将固定随机数生成器的种子值，这样重新运行脚本将总可以生成相同的值。

In [3]: np.random.seed(42)

好了，现在可以开始了。那么我们的训练数据到底应该是什么样子的呢？

在前面的例子中，数据点是小镇地图中的房子。每个数据点有两个特征（也就是，在小镇地图上的位置的x和y坐标）以及一个类别标签（也就是，如果是蓝队球迷居住的地方则是一个蓝色的正方形，如果是红队球迷居住的地方则是一个红色的三角形）。

单独数据点的特征可以用一个具有两个元素的向量表示，这个向量表示数据点在小镇地图上的x坐标和y坐标。相似的，如果标记是蓝色的正方形，则类别是数字0，如果是红色的三角形，则类别是数字1。

可以通过从地图上随机选择一个位置并随机分配一个标签（不是0就是1）就可以生成一个数据点。假设小镇地图的范围是0≤x＜100和0≤y＜100。那么可以使用下面的代码来生成一个随机数据点：

In [4]: single_data_point = np.random.randint(0, 100, 2)
...     single_data_point
Out[4]: array([51, 92])

正如上面的输出结果所示，这段代码将会从0到100之间获取两个随机的整数。我们将把第一个整数当作数据点在地图上的x坐标值，第二个整数当作数据点的y坐标值。同样，可以为这个数据点选择一个标签：

In [5]: single_label = np.random.randint(0, 2)
...     single_label
Out[5]: 0

结果表示这个数据点的类别是0，我们把它当作一个蓝色的正方形。

把这个过程包装成函数，输入是要生成的数据点的个数（即num_sample）和每个数据点的特征数（即num_features）。

In [6]: def generate_data(num_samples, num_features=2):
        """随机生成一些数据点"""

因为在这个例子中特征的数量是2，使用默认的参数值是没有问题的。在这种调用函数时不显式指定num_features值的情况下，这个参数会被自动分配为2。相信你已经了解了这个知识点。

我们想要创建的数据矩阵应该有num_samples行、num_features列，其中每一个元素都应该是[0, 100]范围内的一个随机整数。

...     data_size = (num_samples, num_features)
...     train_data = np.random.randint(0, 100, size=data_size)

同样，我们想要创建一个所有样本在[0, 2]范围内的随机整数标签值的向量：

...     labels_size = (num_samples, 1)
...     labels = np.random.randint(0, 2, size=labels_size)

别忘了让函数返回生成的数据：

...    return train_data.astype(np.float32), labels

Tips：OpenCV对于数据类型有些过分的讲究，因此确保总是把数据点的类型转换为np.float32！

接下来对函数进行测试，先生成任意数量的数据点，比如说11个数据点，并随机选择它们的坐标：

In [7]: train_data, labels = generate_data(11)
...     train_data
Out[7]: array([[ 71.,  60.],
               [ 20.,  82.],
               [ 86.,  74.],
               [ 74.,  87.],
               [ 99.,  23.],
               [  2.,  21.],
               [ 52.,   1.],
               [ 87.,  29.],
               [ 37.,   1.],
               [ 63.,  59.],
               [ 20.,  32.]], dtype=float32)

可以从上面的输出结果看到，train_data变量是一个11x2的数组，每一行表示一个单独的数据点。可以通过使用数组的索引获取第一个数据和它对应的标签：

In [8]: train_data[0], labels[0]
Out[8]: (array([ 71.,  60.], dtype=float32), array([1]))

这个结果告诉我们第一个数据点是一个蓝色的正方形（因为它的类别是0），它在小镇地图的坐标位置是(x, y) = (71, 60)。如果想要的话，可以使用Matplotlib在小镇地图上画出这个数据点：

In [9]: plt.plot(train_data[0, 0], train_data[0, 1], 'sb')
...     plt.xlabel('x coordinate')
...     plt.ylabel('y coordinate')
Out[9]: <matplotlib.text.Text at 0x137814226a0>

但如果想要一次就显示所有的训练数据集呢？可以写一个函数。这个函数的输入应该是一个所有都是蓝色正方形的数据点的列表（all_blue）和一个所有都是红色三角形的数据点的列表（all_red）：

In [10]: def plot_data(all_blue, all_red):

接下来函数应该可以把所有蓝色数据点用蓝色正方形画出来（使用颜色'b'和标记's'），可以使用Matplotlib中的scatter函数完成这个任务。在使用这个函数时，需要把蓝色数据点当作N×2的数组来传入，其中N是样本的数量。接着all_blue[:,0]包含了所有蓝色数据点的x坐标，all_blue[:, 1]包含了所有蓝色数据点的y坐标：

...    plt.scatter(all_blue[:, 0], all_blue[:, 1], c='b', marker='s', s=180)

同理，对于所有的红色数据点也可以这么做：

...    plt.scatter(all_red[:, 0], all_red[:, 1], c='r', marker='^', s=180)

最后，设置绘图的标签：

...     plt.xlabel('x coordinate (feature 1)')
...     plt.ylabel('y coordinate (feature 2)')

在我们的数据集上测试一下这个函数吧！首先需要把所有的数据点分成红色数据集和蓝色数据集。可以使用下面的命令（其中ravel将平面化数组）快速选择前面创建的labels数组中所有等于0的元素：

In [11]: labels.ravel() == 0
Out[11]: array([False, False, False,  True, False,  True,  True,  True,  True,
               True, False], dtype=bool)

前面创建的train_data中对应标签为0的那些行就是所有蓝色的数据点：

In [12]: blue = train_data[labels.ravel() == 0]

对于所有的红色数据点也可以同样操作：

In [13]: red = train_data[labels.ravel() == 1]

最后，让我们画出所有的数据点：

In [14]: plot_data(blue, red)

这将会创建如下所示的图：

▲整个训练数据集的可视化

2. 训练分类器

现在是时候训练分类器了。

和其他所有的机器学习函数一样，k-NN分类器也是OpenCV 3.1 中ml模块的一部分。可以使用下面的命令来创建一个新的分类器：

In [15]: knn = cv2.ml.KNearest_create()

Tips：在OpenCV的旧版本中，这个函数可能叫作cv2.KNearest()。

接下来把训练数据传入到train方法中：

In [16]: knn.train(train_data, cv2.ml.ROW_SAMPLE, labels)
Out[16]: True

这里，必须告诉knn我们的数据是一个 N×2 的数组（即每一行都是一个数据点）。这个函数会在执行成功后返回True。

3. 预测新数据点的类别

knn提供的另一个非常有用的方法叫作findNearest。它可以根据最近邻数据点的标签来预测新数据点的标签。

由于有generate_data函数，我们可以非常容易地生成一个新的数据点！可以把新数据点当作只有一个数据的数据集。

In [17]: newcomer, _ = generate_data(1)
Out[17]: newcomer

函数也返回一个随机的类别，但我们对它不感兴趣。相反，我们想要使用我们训练的模型对它进行预测！可以通过一个下划线（_）让Python忽略输出值。

回到我们的小镇地图，我们要像之前一样把训练数据集画出来，并将新的数据点加入，用绿色的圆圈表示（因为我们现在还不知道它应该是一个蓝色的正方形还是一个红色的三角形）。

In [18]: plot_data(blue, red)
...      plt.plot(newcomer[0, 0], newcomer[0, 1], 'go', markersize=14);

Tips：可以在plt.plot函数后面添加一个分号以抑制输出，与Matlab一样。

上面的代码将生成下面这幅图（不包含圆环）：

▲整个训练数据集，加上一个有待确定标签的新数据点（绿色）

如果要你根据它的临近点猜测，你会给新的数据点分配什么标签，蓝色还是红色呢？

其实，这也看情况，不是吗？如果看离它最近的房子（那个位置大致在(x, y)=(85,75)，上图中点圆里面的房子），可能会把新的数据点同样分配一个红色的三角形。这也确实是在k=1的情况下我们的分类器预测的结果。

In [19]: ret, results, neighbor, dist = knn.findNearest(newcomer, 1)
...      print("Predicted label:\t", results)
...      print("Neighbors label:\t", neighbor)
...      print("Distance to neighbor:\t", dist)
Out[19]: Predicted label:        [[ 1.]]
...      Neighbors label:       [[ 1.]]
...      Distance to neighbor:   [[ 250.]]

这里，knn报告说最近邻的点有250个单位远，其类别是1（我们说过1对应的是红色三角形），因此新的数据点类别应该也是1。如果设置k=2最近邻和k=3最近邻，结果也是一样的。

但要小心不要选择任意偶数的k值。为什么呢？其实，可以从上面的图中看出来（虚线圆），在虚线圆里面的6个最近邻点中，有3个蓝色正方形和3个红色三角形—这是个平局！

Tips：在这种平局的情况下，OpenCV的k-NN实现将会选择到数据点整体距离更近的邻居。

最后，如果非常大地扩大搜索窗口，根据k=7最近邻来对新数据点分类（在前面的图中是实线圆），会发生什么呢？

通过调用findNearest方法并设置k=7，可以看到结果：

In [20]: ret, results, neighbor, dist = knn.findNearest(newcomer, 7)
...      print("Predicted label:\t", results)
...      print("Neighbors label:\t", neighbor)
...      print("Distance to neighbor:\t", dist)
Out[20]: Predicted label:        [[ 0.]]
         Neighbors label:       [[ 1.  1.  0.  0.  0.  1.  0.]]
         Distance to neighbor:   [[  250.   401.   784.   916.  1073.  1360.  4885.]]

忽然之间，预测的标签变为0（蓝色正方形）。原因是现在实线圆内有四个邻居是蓝色正方形（标签0），而只有三个是红色三角形（标签1）。因此多数投票建议预测新来者也是一个蓝色正方形。

正如所看到的，k-NN的输出结果会随着k的变化而变化。然而，大多数情况下是无法提前知道k为何值时是最合适的。对于这个问题最简单的解决方法是尝试一组k值，并观察哪个的结果最好。

本文摘编自《机器学习：使用OpenCV和Python进行智能图像处理》，经出版方授权发布。

《机器学习：使用OpenCV和Python进行智能图像处理》

作者：Michael Beyeler