导读：OpenCV 的构建是为了提供计算机视觉的通用基础接口，如今曾经成为经典和最优秀的计算机视觉和机器学习的综合算法工具集。作为一个开源项目，研讨者、商业用户和政府部门都可以轻松应用和修正现成的代码。
k-NN算法可以以为是最简单的机器学习算法之一。本文教你应用OpenCV 和 Python 的基础知识，完成 k-NN算法。
作者：迈克尔·贝耶勒（Michael Beyeler）
如需转载请联络华章科技
01 运用分类模型预测类别：成绩的提出
假设在一个叫作随机镇的小镇，人们对他们的两个运动队随机城红队和随机城蓝队非常痴迷。红队历史悠久，深受人们喜欢。但随后一些外镇的百万富翁离开小镇，买下红队中最出色的得分手，并末尾组建一支新的球队，蓝队。
除了让大部分红队球迷不满之外，那个最出色的得分手照旧可以在蓝队中一步一步博得冠军。虽然照旧会有一些永远无法原谅他早期职业选择的球迷不满，几年之后他还是会前往红队。
但无论如何，你可以发现红队球迷与蓝队球迷的关系并不好。理想上，这两队的球迷由于不愿与对方做邻居，连住所都是分开的。我甚至听到过这种故事，红队球迷在蓝队球迷搬到家附近时，会故意搬走到其他地方。这是真实的故事！
无论如何，我们一无所知的进入这个小镇，尝试挨家挨户卖给人们一些蓝队的货物。但是，时不时地会遇到一些热血的红队球迷会由于我们售卖蓝队的东西而对我们大喊大叫，并把我们驱逐出他们的草坪。非常不敌对！假如可以避免这些房屋而仅仅访问那些蓝队球迷的家，压力将会更小，也可以更好地应用工夫。
由于坚信可以学会预测红队球迷寓居的地方，我们末尾记录每次的访问。假如遇到了一个红队球迷的家，就在手边的小镇地图上画一个红色三角形；否则，就画一个蓝色正方形。一阵子之后，我们就非常了解他们的寓居信息了。
▲随机镇的小镇地图
但是，如今我们到了地图中绿色圆圈标记的房子前了。应该敲门吗？我们尝试着找到一些线索来确定他们支持哪个球队（也许在后阳台上插着球队的旗帜），但没有找到。那如何知道敲门能否安全呢？
这个有些愚笨的例子准确阐明了监督学习算法可以处理的一类成绩。我们有一些观察信息（房屋、房屋的地点和他们支持球队的颜色）组成了训练数据。可以运用这些数据来从阅历里学习，这样当面对预测新房子的主人支持的球队颜色这一义务时，就可以有足够的信息做出评价。
正如后面所说，红队的球迷对他们的球队非常狂热，因此他们绝不能够成为蓝队球迷的邻居。我们能否可以运用这个信息比对一切邻居的房屋，以此来查明寓居在新房子中的是哪一队的球迷？
这正是k-NN算法将要处理的成绩。
02 了解 k-NN 算法
k-NN算法可以以为是最简单的机器学习算法之一。缘由是我们只需求存储训练数据集。接上去，为了对新数据点停止预测，仅需求在训练数据集中找到它最近邻的点就可以了。
简单而言，k-NN算法以为一个数据点很能够与它近邻的点属于同一个类。思索一下：假如我们的邻居是红队球迷，我们很能够也是红队球迷，否则我们能够很早之前就搬家到其他地方了。对于蓝队球迷而言也是这样。
当然，有些社区能够稍微复杂一些。在这种状况下，我们将不只仅思索我们最近邻的类别（即k=1），而是思索k个最近邻的类别。对于后面提到的例子，假如我们是红队球迷，我们能够不会搬到邻居大部分都是蓝队球迷的地方。
这就是它的全部了。
03 运用 OpenCV 完成 k-NN
运用OpenCV，可以很轻松地经过cv2.ml.KNearest_create()函数来创建一个k-NN模型。然后停止以下几步：
生成一些训练数据。指定k值，创建一个k-NN对象。找到想要分类的新数据点的k个最近邻的点。运用多数投票来分配新数据点的类标签。画出结果图。
首先引入一切必需的模块：运用k-NN算法的OpenCV、处理数据的NumPy、用于绘图的Matplotlib。假如运用Jupyter Notebook，别忘了调用%matplotlib inline魔法命令。
In [1]: import numpy as np
... import cv2
... import matplotlib.pyplot as plt
... %matplotlib inline
In [2]: plt.style.use('ggplot')
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值，并观察哪个的结果最好。
关于作者：Michael Beyeler，华盛顿大学神经工程和数据迷信专业的博士后，主攻仿生视觉计算模型，用以为盲人植入人工视网膜（仿生眼睛），改善盲人的视觉体验。 他的工作属于神经迷信、计算机工程、计算机视觉和机器学习的交叉范畴。同时他也是多个开源项目的积极贡献者。
本文摘编自《机器学习：运用OpenCV和Python停止智能图像处理》，经出版方授权发布。
延伸阅读《机器学习》
引荐语：OpenCV是一个综合了经典和先进计算机视觉、机器学习算法的开源库。经过与Python Anaconda版本结合，你就可以获取你所需求的一切开源计算库。本书首先引见分类和回归等统计学习的基本概念，然后详细讲处理策树、支持向量机和贝叶斯网络等算法，以及如何把它们与其他OpenCV函数结合。 |
