前言：OpenCV 的构建是为了提供计算机视觉的通用基础界面，现在已经成为经典和最优秀的计算机视觉和机器学习的综合算法工具集。作为一个开源专案，研究者、商业使用者和-部门都可以轻松利用和修改现成的程式码。
k-NN算法可以认为是最简单的机器学习算法之一。本文教你利用OpenCV 和 Python 的基础知识，实现 k-NN算法。
使用分类模型预测类别：问题的提出
假设在一个叫作随机镇的小镇，人们对他们的两个运动队随机城红队和随机城蓝队非常痴迷。红队历史悠久，深受人们喜爱。但随后一些外镇的百万富翁来到小镇，买下红队中最出色的得分手，并开始组建一支新的球队，蓝队。
除了让大部分红队球迷不满之外，那个最出色的得分手依旧可以在蓝队中一步一步赢得冠军。尽管依旧会有一些永远无法原谅他早期职业选择的球迷不满，几年之后他还是会返回红队。
但无论如何，你可以发现红队球迷与蓝队球迷的关系并不好。事实上，这两队的球迷因为不愿与对方做邻居，连住所都是分开的。我甚至听到过这种故事，红队球迷在蓝队球迷搬到家附近时，会故意搬走到其他地方。这是真实的故事！
无论如何，我们一无所知的进入这个小镇，尝试挨家挨户卖给人们一些蓝队的货物。然而，时不时地会遇到一些热血的红队球迷会因为我们售卖蓝队的东西而对我们大喊大叫，并把我们驱赶出他们的草坪。非常不友好！如果可以避免这些房屋而仅仅访问那些蓝队球迷的家，压力将会更小，也可以更好地利用时间。
由于坚信可以学会预测红队球迷居住的地方，我们开始记录每次的访问。如果遇到了一个红队球迷的家，就在手边的小镇地图上画一个红色三角形；否则，就画一个蓝色正方形。一阵子之后，我们就非常了解他们的居住资讯了。
▲随机镇的小镇地图
然而，现在我们到了地图中绿色圆圈标记的房子前了。应该敲门吗？我们尝试着找到一些线索来确定他们支援哪个球队（也许在后阳台上插著球队的旗帜），但没有找到。那如何知道敲门是否安全呢？
这个有些愚蠢的例子准确说明了监督学习算法可以解决的一类问题。我们有一些观察资讯（房屋、房屋的地点和他们支援球队的颜色）组成了训练资料。可以使用这些资料来从经验里学习，这样当面对预测新房子的主人支援的球队颜色这一任务时，就可以有足够的资讯做出评估。
正如前面所说，红队的球迷对他们的球队非常狂热，因此他们绝不可能成为蓝队球迷的邻居。我们是否可以使用这个资讯比对所有邻居的房屋，以此来查明居住在新房子中的是哪一队的球迷？
这正是k-NN算法将要处理的问题。
理解 k-NN 算法
k-NN算法可以认为是最简单的机器学习算法之一。原因是我们只需要储存训练资料集。接下来，为了对新资料点进行预测，仅需要在训练资料集中找到它最近邻的点就可以了。
简单而言，k-NN算法认为一个数据点很可能与它近邻的点属于同一个类。思考一下：如果我们的邻居是红队球迷，我们很可能也是红队球迷，否则我们可能很早之前就搬家到其他地方了。对于蓝队球迷而言也是这样。
当然，有些社群可能稍微复杂一些。在这种情况下，我们将不仅仅考虑我们最近邻的类别（即k=1），而是考虑k个最近邻的类别。对于前面提到的例子，如果我们是红队球迷，我们可能不会搬到邻居大部分都是蓝队球迷的地方。
这就是它的全部了。
使用 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]:
但如果想要一次就显示所有的训练资料集呢？可以写一个函式。这个函式的输入应该是一个所有都是蓝色正方形的资料点的列表（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]
最后，让我们画出所有的资料点：
这将会建立如下所示的图：
▲整个训练资料集的视觉化
现在是时候训练分类器了。
和其他所有的机器学习函式一样，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进行智慧影象处理》
扫码检视详情
推荐理由：
本书是一本基于OpenCV和Python的机器学习实战手册，既详细介绍机器学习及OpenCV相关的基础知识，又通过具体例项展示如何使用OpenCV和Python实现各种机器学习算法，并提供大量示列程式码，可以帮助你掌握机器学习实用技巧，解决各种不同的机器学习和影象处理问题。
作者介绍
Michael Beyeler，华盛顿大学神经工程和资料科学专业的博士后，主攻仿生视觉计算模型，用以为盲人植入人工视网膜（仿生眼睛），改善盲人的视觉体验。 他的工作属于神经科学、计算机工程、计算机视觉和机器学习的交叉领域。同时他也是多个开源专案的积极贡献者。
作为码书商店的运营人员，诚邀你们进入我们的“CSDN码书福利群”，群里会不定时的给大家赠书书籍、优惠券等，有书籍推荐或者物流方面资讯也可群里咨询~目前群已满100人，需要加群的请扫下方二维码新增微信，拉你入群哦~对此次活动不了解的也可咨询~
