1 前言

这一章我们将会开始讨论将视觉转化为感知的机器，换句说该机器将视觉输入转化为有意义的视觉语义。

前几章中我们已经讨论了如何将2维，或者3维传感器收集到的信息转化为特征、类簇、或者几何信息。在接下来的几章中，我们会将这些信息转化为对场景或者目标模型的感知，即判断机器看到的是什么，它相对于相机的位置。

在本章中我们将会讨论机器学习的基础，焦点主要在于机器学习是什么。我们也将看到OpenCV提供的一些简单机器学习能力，这是我们全面理解机器学习基本理论的一个很好切入点。在下一章中我们会看到更多现代机器学习方法在OpenCV中的实现细节。机器学习和很多其他模块一样，通过opencv_contrib提供扩展能力，这在本系列后续文章后记B中有更详细的介绍。如需了解更多细节，请参考源代码仓库内的深度神经网络模块cnn_3dobj和dnn。

2 什么是机器学习

机器学习(Machine Learning, ML)的目标是将数据转化为信息。通过一定数据集的学习后，我们想让机器具备回答和数据相关的问题，例如其余那部分数据和该数据最相似，图像中是否存在汽车，什么广告能够得到用户回应。考虑到成本因素，这个问题可以是，在我们利润最高的一系列产品中，如果我们通过广告推销，用户最可能购买的是哪一个。机器学习从该数据中提取规则或者模式将数据转化为信息。

机器学习是一个很宽的话题，OpenCV主要处理统计机器学习而不是如贝叶斯网络，马尔可夫随机场，和图形模型这样的主题。这里推荐一些比较好的机器学习相关文献。《The Elements of Statistical Learning: Data Mining, Inference and Prediction》、《Pattern Recognition and Scene Analysis》、《Pattern Classification》、《Pattern Recognition and Machine Learning》、《Evaluating mapreduce for multi-core and multiprocessor systems》、《Map-reduce for machine learning on multicore》

2.1 训练集和测试集

我们感兴趣的机器学习处理的是原始的数值数据，例如温度值，股票价格，和颜色强度。这些数据通常被预处理成特征，例如我们可能有一个包含1万张人脸图像的数据库，对人脸应用边缘检测，然后手机入边缘方向，边缘强度，以及边缘和中心的距离等特征。对于每张脸，我们我们可能能得到500个这样的特征值，或者说是一个包含500个元素的特征向量（Feature Vector）。接下来我们可以使用机器学习技术根据这些采集到的数据重建某种类型的模型。如果我们想要知道这些人脸能够被分成几组(宽的、窄的等)，聚类算法（Clustering Algorithm）就是最好的选择。如果我们想要根据例如在人脸图像上检测到的边缘模式预测对应人的年龄，则分类器算法（Classifier Algorithm）将会是合适的选择。为了实现我们的目标，机器学习算法根据该目标不断的分析收集到的特征，然后调整权重、阈值和其他模型参数从而得到最佳性能。这个为了满足某个目标的调参过程就称为机器学习。

在本文撰写的时候OpenCV还没有包含深度学习，因为尽管它们的发展前景比较好，但是这些技术仍然太新，还不能确定到底应该包含哪些内容。然而卷积神经网络《Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position》、《Neural Networks: Tricks of the Trade》、《Convolutional neural network committees for handwritten character classification》绝对是深度学习未来的重要内容之一。

了解机器学习的性能总是非常重要的，这也是一个非常精细的任务。传统上将可用数据集分为一个较大的训练集和一个较小的测试集，在我们的例子中将1万个人脸数据分为9千个样本的训练集和1千个样本的测试集。接下来在训练集上运行分类器，使用数据特征向量学习年龄预测模型。当学习完成后就可以在测试集的图像上厕所年龄预测分类器。

测试集不会用于训练，并且我们不会讲测试集的标签暴露给分类器。只有在训练完成后，才会对1000个样本的测试集中的每一张人脸图片运行分类器，并记录基于特征向量预测到的年龄和实际年龄之间匹配度。如果分类器的预测结果很糟糕，我们可能需要在数据中添加一些新的特征或者考虑使用不同类型的分类器。这一章中我们将会看到很多类型的分类器，以及训练它们的多种算法。

如果分类器的预测质量不错，我们现在就有了一个具有潜在价值的模型，我们可以将它部署在真实世界的数据上。可能这个系统将会被用在基于年龄设置视频游戏的行为这种场景中。当玩家准备游玩时，他的脸部图像将会被提取出500个特征，如边缘方向，边缘强度，距离中心的距离等。分类器就会处理这些数据，并预测用户的年龄并根据该值设置游戏的游玩行为。当分类器被部署后，它处理的人脸图像是之前并未见过的，并根据在训练集中学习到的信息作出决策。

最后，当部署一个分类系统时，我们通常还会使用一个验证数据集。有些时候在最后测试整个系统是一项艰巨的任务，在讲分类器提交到最终测试之前我们经常想要对一些参数进行调整。为了处理这个问题，我们可以将1万个脸部图像数据集分为3部分，分别是包含8000个样本的训练集，1000个样本的验证集，1000个样本的测试集。通过训练集完成学习后，可以在验证集上预测试分类器的效果。当对验证集上的性能感到满意时，我们再到测试集合上运行分类器做最终校验。

你可能想到一种相较于直接从9000个样本的训练集中分离出8000个样本的训练集和1000个样本的测试集更好的策略。的确，这种场景下的标准实践其实是多次重复这种分组策略。在本例中重复9次，每一次都抽取其中1000个样本作为验证集，另外8000个样本训练集。这个过程称为k次折叠交叉验证(k-fold cross-validation)。这里的k次折叠意味着k次分组，这里k的值为9。

2.2 有监督学习和无监督学习

数据有时时候是没有标签的，例如我们可能只是想基于边缘检测的信息观察人脸图像自然的被标记为某一类。有时候数据是有标签的，例如每张图片中人物特征的年龄。这意味着机器学习数据的时候可能是需要受到监督(Supervised)的，例如需要利用教学信号或者标签，和数据特征向量协同工作。当然也有可能是不需要监督的(Unsupervised)，即机器学习算法无法获取这样的标签，并且我们期待算法自己能够弄清数据的结构。下图演示了这个过程。

有监督学习可以用于分类(Categorical)，例如将名字和脸关联起来，或者为数字加上一个有序的或者是数值化(Numeric or Ordered)的标签，例如年龄。当数据的标签是名字的时候，这种类型被称为分类(Classification)，当数据是数值时，这种类型被称为回归(Regression)，回国通过一些类别活着数值输入你和一个数值输出。

监督学习也有一些灰色地带，包括标签和数据向量的一一匹配，另外它也可能由加强学习(Reinforcement Learning)组成，有些时候也称为延迟学习(Deferred Learning)。在加强学习中，数据标签(也被称为奖励(Reward)与惩罚(Punishment))在单个数据向量被观察到后较长时间才会生效。当一个老鼠在迷宫中寻找食物的时候，它可能需要经历一系列的转弯才能最终找到食物，然后获得奖励。这个奖励一定会以某种方式反向影响以后它在寻找食物之前的行为与见解。加强学习以相同的方式工作，系统接收到一个延时信号，可能是一个奖励活着是一个惩罚，尝试推导出一个在未来运行时应当采取的行为，更正式的被称为策略。在这个场景下，学习到的策略实际上是做决策的方式，例如在穿越迷宫时在每一步应该选择哪条路。有监督学习同样可能只有部分标签，其中的一些标签可能缺失，这也被称为半监督学习(Semisupervised Learning)。也可能存在一些噪声，提供的某些标签可能是错误的。大多数机器学习算法只能狗处理一种或者两种上述场景，例如某个算法可能能够处理分类，但是不能给处理回归，某个算法可能能够处理半监督学习，但是不能处理加强学习，某个算法可能能够处理数值数据，但是不能处理分类数据等。

与之相比，通常我们没有数据的标签，并且更想观察是否数据会被自然分为多个组。这种无监督学习的算法通常被称为聚类算法(Clustering Algorithms)。在这种情况下，算法的目标时将未标记的相”近”(预先定义的度量标准或者可能是通过学习得到的概念)的数据向量分为一组。我们可能只是想看这些人脸是如何分布的，它们是否构成了瘦、宽、长或者短的脸这样几组。如果我们正在研究癌症数据，是否可以根据不同的化学信号将它们分入到不同的组内。无监督学习的聚类数据通常也被用于构造特征向量供高层有监督分类器使用。我们可能首先将脸部图像聚合成几类(宽的、窄的、长的和短的)，然后将它们作为输入，再结合一些其他数据，入平均声音频率，从而预测当事人的性别。

常见的两个机器学习任务，分类和聚类，和计算机视觉中最常见的两个任务，识别和分割，有着一些共通之处。有时我们将其称之为“什么”(what)和“哪里”(where)。也就是说我们通常想要计算机对图像中的某个目标模型命名(识别、或者是确定这是什么)，也想知道该模型出现的位置(分割、或者是确定它在哪里)。因为计算机视觉如此频繁的利用到机器学习的知识，OpenCV在ML库中包含了很多强大的机器学习算法，可以在目录…/opencv/modules/ml和…/opencv/modules/flann中找到。

OpenCV中的机器学习代码是通用的，也就是说尽管这些代码在处理视觉任务是非常有用，但是它们的使用并不限于视觉。使用合适的函数甚至可以研究基因组序列。当然我们这里主要关注的还是使用图像中提取到的特征向量进行目标识别。

2.3 生成式和判定式模型

现在已经有很多算法用于分类和聚类，OpenCV提供了一些最有用的当下可用的统计机器学习方法。基于概率的机器学习方法，如贝叶斯网络（Bayesian Networks）或者图形模型（Graphical Models）在OpenCV中支持得没有那么好，部分原因是这些方法都很新，并且正处于活跃的发展阶段。OpenCV倾向于支持判定式算法（Discriminative Algorithms），该算法计算的是给定数据标签的概率P(L｜D)，而不是倾向于支持生成式算法（Generative Algorithms），该算法计算的是给定标签的数据的分布P(D｜L)。尽管这两者之间的区别并不总是很清晰，但是判定式模型对于给定做出预测的场景工作很好，而生成式模型善于给出关于数据的更强大的表现，或者有条件的合成新的数据。在脑海想象一下大象的画面，你将会根据条件“大象”想像出很多数据。

因为生成式模型是对数据的形成过程建模，尽管有时得到的模型并不一定准确，因此通常它更容易被解释。判定式机器学习通常会基于一些可能看上去是随意选取的阈值做出决策。例如，假定在场景中路上的一小块区域由于其颜色中的红色分量低于125被识别出来，但是这意味着红色分量等于126的地方一定不是路吗？这个问题很难被解释。而生成式的模型通常处理的是给定类别情况下的数据条件分布，因此能够很容易感觉出它与实际的分布是否相似。

2.4 OpenCV中的机器学习算法

大多数OpenCV中的机器学习算法都被划分在ML模块中，但是Mahalanobis算法和K均值算法在Core模块中，人脸检测和目标识别算法在objdetect模块中，FLANN算法在flann模块中，其他算法在opencv_contrib扩展库内。

2.4.1 Mahalanobis

Mahalanobis算法定义了一种距离的度量方式，也被称为马氏距离，它通过将距离除以协方差从而得到一个具有空间拉伸的距离。如果协方差矩阵是单位矩阵，那么这个距离就等于欧式距离。详细的算法介绍可以参考论文《On the generalized distance in statistics》。

2.4.2 K-均值(K-means)

K-均值算法是一个无监督的聚类算法，它使用用户定义的K个中心表示数据的分布。该算法和期望最大算法的区别是其使用的中心不是高斯分布的，因此聚类的结果看上去更像是肥皂泡，因为每个中心都“竞争”着去“捕获”最近的数据样本。这些聚类区域通常被用作稀疏直方图的条从而表示数据。该算法由Steinhaus发明，相关论文为《Sur la division des corp materiels en parties》。由Lloyd使用，相关论文为《Least square quantization in PCM’s》。

2.4.3 正态/朴素贝叶斯分类器(Normal/Naive Bayes Classifier)

一种生成式分类器，它假定特征是高斯分布的，并在统计学上服从独立分布，相互之间不影响，但是这种假设太严苛通常情况下都无法成立。也是因为这个原因它经常被称为朴素贝叶斯分类器（Naive Bayes Classifier）。然而这个方法经常却工作得出奇的好，最早提及该方法的论文是《Automatic indexing: An experimental inquiry》和《Steps toward artificial intelligence》。

2.4.4 决策树(Decision Trees)

决策树是一个判定式分类器，它通过在当前节点寻找一个数据特征和一个阈值从而将数据最优划分到不同的类别中。每次处理完数据后都会跳转到左子树或者右子树，并沿着树向下重复这个流程。虽然该算法的表现并不是最好，但是通常你应该首先尝试这个算法，因为它的运行速度非常快，并且具有功能很强大。更多算法细节可以参考论文《Classification and Regression Trees》。

2.4.5 期望最大算法(Expectation Maximization, EM)

一个用于聚类的生成式无监督学习算法，它使用N维高斯分布拟合数据，这里的N由用户选择。在只有少量参数，如均值和方差时，它是一个表示更复杂数据分布的有效方式。该方法通常用于分割。更详细的算法细节请参考论文《Maximum likelihood from incomplete data via the EM algorithm》。

2.4.6 Boosting算法

它由一组判定式分类器组成，最终的分类结果是组内各个分类器结果的加权结果。在训练时会逐个训练组内的分类器，这些分类器都是“弱”分类器，其性能仅仅略高于随机选择一个分类。它们由简单称为“桩”（Stumps）的单变量决策树组成。在训练的时候决策桩不仅需要从数据中学习分类决策，还需要根据它处理数据的精度学习到自己“投票的权重。在处理每个分类器的间隙，数据样本的权重会重新分配，从而使得错分的数据能够得到更多的关注。这个过程一直重复直到由不同决策树的投票加权结果产生的整体误差低于预设的某个阈值。这个方法需要在训练集较大时才会取得较好的结果。更多的细节可以参考论文《A decision-theoretic generalization of on-line learning and an application to boosting》。

2.4.7 随机森林(Random Trees)

由很多决策树组成的判定式森林，每个决策树都向下重逢以获取最大深度。在学习过程中，每棵树的每个节点都允许从数据特征的随机子集中选择类别划分变量。这有助于每棵树成为一个统计学上相互独立的决策者。在运行模式下，每棵树进行不加权的投票。这个方法通常很有效，并且对每棵树的输出平均后还可以用于处理回归问题。更多的算法细节请参考论文《Random decision forest》、《Decision forests for computer vision and medical image analysis》和《Fast approximate energy minimization via graph cuts》。

2.4.8 K临近算法(K-nearest neighbors)

这可能是最简单的分类器。训练数据和对应的标签被同时保持，处理测试数据时，根据离它最近(欧式距离)的K个样本的投票对被测样本进行分类。该算法通常很有效但是运行速度比较慢，并且需要大量的类次。更多算法细节可以参考论文《Discriminatory analysis, nonparametric discrimination: Consistency properties》和FLANN的相关介绍。

2.4.9 快速近似最近邻法(FLANN)

OpenCV包含一个快速近似最近邻库，由Marius Muja开发，支持最近邻的近似和K个最近邻的匹配。更多的细节可以参考论文《Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration.》。这里的FLANN的全称是Fast Library for Approximate Nearest Neighbors。

2.4.10 支持向量机(SVM)

一个判定式的分类器，它也可用于回归。算法定义了任意两个样本在一个更高维度空间内的距离函数。将数据投影到更高维度的空间会使得数据更可能是线性可分的。算法学习一个分类超平面，它能最大程度的在更高维度内对数据分类。当数据样本有限时该算法趋于获得近似最佳的效果，而当数据量非常大时，bossting或者随机森林算法能够获得更高的效果。更多的算法细节可以参考论文《An introduction to the Kalman filter》。

什么是大的数据，这里没有明确的答案，因为它取决于底层生成过程的变化有多快。但是这里有一个非常粗暴的经验法则，每个分类/目标在每个有意义的维度/特征上包含10个数据样本。因此对于两个分类，三个维度的场景需要的数据至少大于2✖️10✖️10✖️10=2000个数据样本才能称为大的数据。

2.4.11 人脸识别/级联分类器

一个巧妙使用boosting分类器的目标检测应用。OpenCV提供了训练过的正面人脸检测器，它的检测效果非常好。你可以用这个算法来训练软件提供的其他目标。当然你也可以使用其他特征或者未这个分类器创建你自己的特征。这个算法非常善于处理刚性物体和特征视图。该算法也被称为Viola Jones分类器，这个根据作者的名字命名的。更多的算法细节可以参考论文《Robust real-time face detection》。

2.4.12 Waldboost

该算法事Viola级联算法的一种衍生版本。它是一个运算非常快的目标检测器，在处理一系列任务的时候也要优于传统的级联分类器。可以在模块…/opencv_contrib/modules中找到，更多的算法细节可以参考论文《WaldBoost - learning for time constrained sequential detection》。

2.4.13 隐变量支持向量机(Latent SYM)

隐变量支持向量机使用一个局部模型，基于识别目标单个部分，并通过学习一个模型关联不同的部分来识别复合目标。更多的算法细节可以参考论文《Object detection with discriminatively trained part-based models》。

2.4.14 词袋模型

词袋方法将文档分类中使用非常频繁的技术推广到了图像分类。该方法非常强大，因为它不仅可以标识单个物体，还可以用于标识场景和环境。

2.5 使用机器学习处理视觉任务

通常情况下前文提到的那些算法的输入是由很多特征构成的数据向量，这些特征的数量可能高达几千个。假定你的任务是识别一个特定类型的对象，例如一个人。你遭遇的第一个问题就是如何收集数据，并将其标记为有人和没有人的两类。你很快会意识到人像在图像上呈现不同的比例，你可能发现有的人像仅仅覆盖很少的像素，而有的图片上一只耳朵就能占据整个图像。甚至更糟糕的情况是人们经常被遮挡，如在车里的人，一张女人的脸，从树后伸出的一条腿。你需要定义哪种情况下可以判定场景内出现了人。

接下来的问题是如何收集数据，是使用相机采集，还是去照片分享网站上尝试找到“人物”的分类标签，或者两种方式都使用以及更多的方式。是否采集移动信息，以及一起其他的信息，如场景中的门是否开启，时间、季节和温度信息。一个能够在沙滩上搜索人物的算法在处理滑雪斜坡时可能无法正常工作。你需要捕获数据中的这些变化信息，如不同的视角、光照、天气条件、阴影等。

收集完数据之后，首先你需要确定想要通过标签表述什么信息，你是想确定场景中是否存在人物？他们的动作是否重要？是在跑步，走路，爬行还是追踪。你可能收集到超过百万张图片，甚至更多。标记这些信息有很多技巧，例如在受控的设置下应用背景提取并收集被分割出来的走入场景的前景人物。你也可以使用一些数据服务来帮你完成分类工作，例如可以通过亚马逊的Mechanical Turk服务雇人来处理你的数据。如果你将工作排列得比较简单，就能将成本控制在约每个标签1便士以下。最后你再使用图像硬件如GPU或者其他计算族群完成目标、人物、人脸、手臂的渲染。使用相机模型参数，你通常可以得到背景已知的非常逼真图像，因为数据是你自己生产的。

标记完数据之后，你必须决定从目标中提取哪些特征。如果人物总是正面站立的，就没有必要使用旋转不变性的特征，也没有必要在处理图像之前旋转它们。总的来说，你需要找到能够表述目标固有属性的特征，例如对缩放不敏感的梯度或者颜色直方图，或者是流行的SIFT特征。关于SIFT特征更多细节可以参考Lowe的Keypoint demo。如果有背景信息，你可能想首先移除这些信息。接下来需要对图像进行处理，其中包括对图像的标准化处理，和计算不同类型的特征。其中标准化处理包括缩放、旋转、直方图均衡等。得到的每个数据向量都会分配一个标签，它们和目标、运动或者场景相关联。

当数据收集完成后需要将它转换为特征向量，通常需要将它们分为训练、验证(可选)和测试集。正如我们前面提到过，训练策略的一个最佳实践就是使用交叉验证的方式进行训练、验证和测试。回顾前文提到的具体做法，将数据氛围K个子集并执行多个训练、验证(可选)和测试会话，每次会话包含不同的数据集用于训练、验证(可选)和测试。通常可以包含5到10次训练会话。不同会话的测试结果经过平均得到最终的性能结果。交叉验证能够更准确的表述分类器部署到新的数据时的效果。

数据准备好后就需要选择分类器，通常分类器的选择和计算效率，数据条件，和内存条件相关。对于某些应用程序，例如在线用户偏好偏好建模，你必须快速的训练分类器。在这种情况下最近邻、贝叶斯或者决策树都是不错的选择。如果对内存要求苛刻，决策树或者神经网络能够高效的利用内存空间。如果分类器的训练时间充分，但是要求判断迅速，神经网络是很好的选择，当然朴素贝叶斯和支持向量机也是不错的选择。如果训练的时间充分，并且也支持一定的时间做出判断，但是要求较高的精度，则bossting和随机森林可以满足你的需求。如果只是想要一个简单的，易懂的便于检查特征选择的是否好的分类器，则决策树或者最近邻是很好的选择。当然要获得最好性能，最好首先尝试boosting或者随机森林。

需要注意没有最好的分类器，更多细节可以参考文章No Free Launch Theorem(http://en.wikipedia.org/wiki/No_free_lunch_theorem)。对所有可能存在的数据分布类型平均后，所有的分类器表现都差不多。因此我们不能够说某个算法就是最好的。但是对于特定的数据分布或者数据集分布而言，确实有最好的分类器。因此当处理真实数据时多尝试不同的分类器是一个不错的主意。首先确定你的目的，是要得到正确的分数，或者是想要解释数据。你是否追求更快的计算效率、更小的内存消耗或者对决策的置信度有要求？不同的分类器在这些维度上有不同的表现。

2.6 变量的重要性

前文列举的机器学习算法中有两个可以判断变量的重要性(Variable Importance)。已知特征向量，判定这些特征对分类准确性的重要性是一个常见的问题。二叉决策树可以直接表示这个信息，通过在每个节点选择最能将数据分成不同部分的特征来训练模型。顶层的节点表示的变量则是最重要的变量，第二层的节点对应的变量则是次重要的变量，并以此类推。该算法对噪声非常敏感，二叉树真正做的是为每个节点构建代理分支，并计算该节点上所有分割方案的重要性。随机森林算法使用了Leo Breiman开发的技术，也能够计算变量的重要性。该技术能过被用在任意分类器中，但是到目前为止OpenCV中只有决策树和随机森林算法实现了这个技术。

变量重要性的一个使用场景就是减少分类器需要考虑的特征数量。对于特征数量很多的数据，训练分类器并找到每个特征相较于其他特征的重要程度。然后丢弃不重要的特征。因为算法不再需要技算这些特征数据，消除不重要的特征能提升算法效率，让训练和测试过程变得更快。同样的，如果已有的数据并不充分，通常我们会面临这种情况，则消除不重要的变量能够提升分类器的准确性，这样能够提升算法的效率并得到更好的结果。

Breiman的重要性算法主要步骤如下：

1. 在训练集上训练分类器。
2. 使用验证或者测试集判断分类器的准确性。
3. 对于选定的一个特征，将每个样本该特征的值都随机的使用集合中其他样本的值替换，这种技术也被称为替补抽样(Sampling with Replacement)。这样就抱着了特征的分布并不会改变，但是实际的结构或者说含义被消除了。随机森林算法的实际实现并不会生成新的值，实际上只是在样本中交换了它们。
4. 在改变后的训练集上训练分类器，然后在改变后的验证和测试集上计算分类器的准确性。如果准确性降低很多，则该特征就是非常重要的，如果对准确性影响不大，则该特征就是一个可以被移除的特征候选项。
5. 恢复数据集，并重复3-4的步骤处理其他特征。再将所有特征根据重要程度排序得到最后的结果。

这个过程被内置再随机森林和决策树算法中，因此可以直接使用这两个算法决定我们实际需要的是哪些特征，然后使用瘦身后的特征向量来训练同一个或者其他类型的分类器。

2.7 常见的机器学习问题

让机器学习算法工作理想不仅是个科学问题，更是一门艺术。算法通常能够解决大多数问题，但其结果又不完全和你预期的一致。这就是艺术所在，为了让它工作更好，你需要找出是哪个地方存在问题。尽管这里我们不会讲解所有的细节，但是会大致介绍一些你可能遭遇到的常见问题。斯坦福大学的Andrew Ng教授开授了名为Advice for Applying Machine Learning(http://www.stanford.edu/class/cs229/materials/ML-advice.pdf)的网络课程，你可以从这里找到更多的细节。

首先介绍重要的经验法则，更多的数据比更小的数据更重要，更好的特征比更好的算法重要。如果你的特征设计得非常好，即使它们之间的相互独立性更强，并使它们受不同环境的影响更小，则几乎任意的算法都会工作得非常好。除了这两点之外，还有三个常见的问题。

• 欠拟合：模型的假设太严格，因此不能很好的匹配数据。
• 过拟合：算法将没有排除噪声，因此不具很好的通用性。
• 错误：机器学习代码通常会包含一些表面上看上去非常严重的Bug，它们在预期完全错误的时候通常会降低算法性能。

下图介绍了统计机器学习的基本结构，它的工作方式是对函数f进行数学建模，该函数将给定的输入数据转换成一个确定的输出。这个函数可能是一个回归问题，例如根据人脸预测某个人的年龄。可能有些精明的读者会认为因为该场景中计算得到的年龄都是整数，因此它更像一个分类问题。但是回归问题和分类问题的定义是输出结果的连续性，因此这实际上是一个回归问题。另外这个函数也可能是一个分类预测问题，例如根据脸部特征识别莫个人。在真实世界中，噪声和一些未考虑到的影响将会导致观察到的输出数据和理论输出值不同。例如在人脸识别应用程序中，我们可能需要学习一个模型通过测量眼睛、嘴巴和鼻子之间的距离来识别特定的脸。但是由于附近闪烁的灯光导致光照条件的改变可能产生测量误差，或者一些质量较低的相机透镜可能在测量时产生系统扭曲，这些因素我们都没有考虑到模型中，它们会影响模型的精度。

下图演示了欠拟合和过拟合对测试集和训练集的误差影响，其中上方的两幅图分别表示的是欠拟合和过拟合的场景中模型的匹配情况，下方的两幅图则是对应的训练以及测试过程中误差和对应集合样本数量大小点关系。在欠拟合场景中，通过左上角的图可以看到模型设置非常严格，它和真实的函数f并不匹配，在下方对应的误差分析图也可以看到这种情况下无论是训练和测试误差都很大，即使有着大量数据也并不能很好的处理误差，只是让测试和训练误差更接近而已。对于右侧两幅图中过拟合的场景，模型和实际的样本严格匹配，但是这样却考虑了所有的噪声，从下方的误差分析图中可以看到这样也会导致很大的误差。总结一下就是相对低的训练误差和高测试误差表示模型欠拟合，而训练误差较低，测测误差很高则表明模型过拟合。

有时需要仔细思考正在处理的问题是否是你想要解决的那个问题，如果你得到了较低的测试和训练误差，但是算法在实践中工作得并不理想，那么可能是因为数据集采集时处于非真实的条件或者环境，可能这些不真实的条件或者环境使得数据更容易采集和模拟。如果这个算法不能够重现测试集和数据集的表现，可能是因为使用了错误的算法，从数据中提取的特征是无效的，或者说真正的信号并不在收集的数据中。

下表列出了我们之前讨论的问题的一些可能解法，当然这里并未列出全部的问题，也并未列出所有的解法。为了机器学习模型能过工作得更好，需要收集哪些数据，以及从中提取哪些特征是需要仔细思考和设计的。同样诊断机器学习问题也需要系统的思考。

交叉验证、booststrapping、ROC曲线和混淆矩阵

最后介绍一些度量机器学习结果优劣的基本工具，在有监督学习中，一个最基本的问题就是确定算法的性能，算法分类或者拟合数据的精确度。可能我们会认为这很简单，只需要在测试和验证集上运行算法并获取结果就可以了。但是在处理真实问题的时候，我们必须考虑噪声、采样误差和采样错误。简单的说，测试和验证集可能并不能准确的反映真实数据的分布。为了更准确的评估分类器的性能，我们采用交叉验证(Cross-Validation)或者类似的bootstrapping技术。

在最基本的形式下，交叉验证将数据分为K个不同的子集。使用K-1个子集训练模型，并使用剩下的那个子集作为测试集。这样操作K次，每个子集都会作为一次测试集，然后将结果平均。

Boostrapping和交叉验证类似，但是验证集是从训练数据中随机选择的。每次从全部数据中随机选出一部分样本作为子集作为验证集，并使用剩下的数据训练模型，这样执行N次并将所得的结果进行平均。因为每次验证集都是随机选择的，因此某些样本可能在不同迭代轮次的验证集中重复出现。通常情况下使用Boostrapping算法得到的结果会优于使用交叉验证得到的结果。Boostrapping的主要目标是找到最优的训练参数，因为平均训练误差是容易的，但是将多个模型平均成一个模型可能是不常见或者低效的。

使用这些技术的任意一种都能够得到更准确更优秀的评估结果。在你重复的改变参数、训练模型得到结果的过程中，增加的准确性又能反过来用于参数的调优。

另外两个非常有用的评估和调整分类器的方法是绘制ROC(Receiver Operating Characteristic)曲线，和填充混淆矩阵(Confusion Matrix)。如下图，ROC曲线描述了分类器的正确识别率(识别为真的结果中实际为真的结果占全部实际为真结果的比例)和错误识别率(识别为真的结果中实际为假的结果占全部实际为假结果的比例)的关系，它们是衡量分类器性能的重要指标。曲线上的每个点都可能是使用交叉验证法计算得到的结果。我们假定分类器的参数是一个阈值，更具体点我们假定需要在图像中识别出黄色的花，并且我们定义了一个颜色阈值作为我们的检测器。如果我们将阈值设置得非常高，则检测器识别的结果为假，也就是说分类器的错误识别率和正确识别率都为0。也就是下图曲线的左下角点。另一方面，如果黄色的阈值被设置为0，则所有的结果都被识别为真，也就是说错误识别率和正确识别率都是100%，即下图曲线的右上角点。最好的ROC曲线是几乎沿着Y轴上升到正确识别率100%后再沿着X轴到达右上角的折线。当然实际上这很难做到，但是曲线越靠近左上角，分类器性能越好。实际应用中，通常计算曲线下方面积占整个画面的比例，结果越接近1表明分类器的性能越好。

尽管在其他文献中有数不清的关于分类器品质的定义，并且它们都有同样多的理由认为自己更优秀，但是这并没有太大意义。文中使用到的定义是其中很常见的一种，可能该定义并不一定是关于某个分类器质量最好的表述，但是这种定义更容易理解，并且它对于几乎任意分类问题都有足够好的定义。

上图中的混淆矩阵行分别表示实际的真值和加值，列分别表示预测的真值和价值，理想情况下评估一个分类器性能时，我们希望右对角线上的值都是100%，而其他地方的值为0%。如果分类器能够学习到两个以上的类别，如多层感知神经网络的随机森林分类器一次能够学习到很多不同的类别标签，则混淆矩阵可以推广到覆盖所有标签的形式，矩阵中的每个实体都表示该情景的样本数量占整行样本的比例。但是ROC曲线在处理多个分类标签时只能记录在测试集上做出的正确和错误抉择。

分错类的成本

错误分类的成本我们还没有详细讨论，假定我们的分类器用于识别食用蘑菇，在下一章会有具体的实例。显然我们可以接受模型具有较大的错误拒绝率（即将可食用的蘑菇标记为不可食用的），同时我们想尽量减小模型的错误识别率（将有毒的蘑菇标记为可以食用的）。ROC曲线可以帮助我们实现这样的目标，可以调整ROC参数从而在曲线的左下段选择一个操作点。另外一种方式是在生成ROC曲线时，给错误识别率相较于错误拒绝率更大的权重。例如你可以将每个错误识别的成本设置为10倍错误拒绝的成本。另外如果你有一些两个错误类型的相对成本的具体先验概念，这种方式非常有用。例如在超市结账时一个商品被错误分类成另外一个商品的成本很容易预先准确量化。

在一些OpenCV的机器学习算法种，如决策树和SVM，你可以通过指定不同类型自己的先验概率（即哪些类更容易被标记，哪些类更不容易被标记），活着指定单个训练样本的权重来平衡命中率和虚警率，即正确识别率和错误识别率。

特征方差不一致

在训练分类器时另外一个常见的问题时特征向量种的特征方差不一致。例如假如某个特征使用小写的英文字符的ASCII表示，则该特征的只有26个不同的取值，而假如有另外一个特征描述的是显微镜下玻片上的细胞数量，该特征的的取值可以在几百万个值中变化。类似于K最邻近算法这样的机器学习算法可能会将第一个特征视为常量，也就是从该特征种无法学到东西。处理这个问题的方式是先使用特征各自的方差对数据进行标准化处理。当特征之间没有关联时这种做法时可以接受的，当它们之间存在关联时，你可以食用它们的平均方差活着协方差来标准化数据。特征方差不一致对一些算法没有影响，如决策树，此时这种预处理操作不需要执行。决策树算法不受方差不一致因素影响是因为对于每个特征仅搜索有效分离阈值，换句话说，只有能够找到明确的分离值，变量的数值范围有多大并不重要。

一个经验法则是如果算法依赖于某种距离度量的方式，如加权值，则你应该对各个特征的方差进行归一化处理。一个可以一次标准化处理所有特征值并解释它们的协方差的手段是马氏距离（Mahalanobis Distance），在本章的后半部分我们将深入介绍该技术。熟悉机器学习或者信号处理的读者可能已经意识到这实际上就是数据”美白”技术。

接下来将会讨论一些在OpenCV中支持的机器学习技术。

3 ML库中遗留的算法

大多数ML库都是用了基于对象的公共C++接口，并在继承于该基类的对象中实现了这些算法。通过这种方式可以通过标准方式在这些库中访问和使用这些算法。然而一些最基本的算法由于它们在引入这种规范之前就被设计，因此并不遵守这些标准。接下来在本节中我们将介绍K均值聚类算法，马氏距离及其在K均值聚类算法中的使用，然后再介绍一种分割技术，它常用于提高K均值聚类算法的速度和准确度。

3.1 k-均值算法

K-均值算法尝试找到使用向量表示的数据集的自然分簇。用户设置需要的分簇数量，K-均值算法会快速的找到它们的数据中心的一个较好解决方案，当然这里的较好值的是数据簇中心趋于整个数据集自然分类的中。该算法是最常用的一种分簇技术，并和期望最大算法(Expectation Maximization)，以及前面章节提到的均值漂移算法(即函数cv::meanShift()内部的算法)类似。更准确的说，K-均值算法是和使用高斯混合模型的期望最大算法相似。在OpenCV中的实现接口是cv::EM()，在本章的后续部分还会详细介绍。正如在OpenCV中的实现一样，K-均值算法是一个迭代算法，它也被称为Lloyd算法，具体参考论文《Least squares quantization in PCM》，同时它还被称为Voronoi迭代。该算法的主要步骤如下。

• 接收用户的输入，包含数据集D以及期望分簇的数量K。
• 随机但足够分散的分配数据簇中心。
• 将每个数据点关联到最近的数据簇中心。
• 将数据簇中心移动到各自数据子集的质心。
• 回到第三步直至算法收敛，也就是说质心不再移动。

下图演示了一个K-均值算法应用的实例，在这个例子中算法迭代三次就收敛。在实际的应用中通常算法收敛速度非常快，但是也有需要大量迭代才能收敛的情况。在下图中，图a随机分配了三个数据簇中心，并将所有样本点关联到最近的数据中心，图b将这些数据中心移动到各自子集的质心，并将所有样本点重新关联到最近的集合中心，图c和图d实际上是重复了图b的操作得到新一轮迭代的结果。

3.1.1 相关问题以及解决方案

K-均值算法是一个非常有效的聚类算法，但是它有三个重要的缺陷。

• 它不能保证找到分类中心的最佳解决方案。它只保证收敛到某一个解决方案，即迭代不会无限的进行下去。
• 算法不能告诉调用方应该选择的分类数量。如果对于上图的场景我们确定分簇数量为2或者4将会得到不同甚至不合理的结果。
• 它并不关心数据在空间中的协方差是否匹配，或者说数据已经归一化处理。后面还会对该点详细解释，并引入马氏距离(Mahalanobis Distance)。

这三个问题都有一个解决方案，或者说至少有一个可以提供帮助的方法。前两种结局方案都依赖于解释数据的方差。在K-均值算法中，每个聚类中心都管理着自己的样本子集，我们会计算这些样本的方差。在这里方差值的是点到聚类中心到距离。点的方差通常是这些点的正交积(Quadrature Sum)，这个积也被称为紧凑度(Compactness)。

最好的聚类方案在不造成太大的复杂度即数据簇的数量不太大的情况下，使分簇结果整体方差最小。基于此，我们可以通过如下方式改善上述列出的问题。

1. 多次执行K-均值算法，这样每次随机选择的初始聚类中心几乎不会相同，并选择整体方差最小的结果。
2. 将聚类的数量设置为1，然后再依次递增迭代执行K-均值算法，每次迭代都是用方案1的策略得到当前聚类数量下最好的结果。通常情况下整体方差变化会快速趋于平坦，接着在方差曲线上将会出现一个拐点。这意味着新增一个聚类中心不会明显的减少方差，此时可以停止迭代并使用当前的聚类中心数量。
3. 将数据集乘以方差矩阵的逆矩阵，在本章后续部分介绍马氏距离的时候还会解释。例如，如果输入的数据D中每个样本都是使用一行来描述的，通过计算局长D🌟来标准化数据，此处D🌟 = DΣ^-1/2。

3.2.2 相关接口

OpenCV中提供的K-均值算法接口如下。

// 返回值：紧凑度
// data：待处理的数据样本，元素为float类型
// K：聚类中心的数量
// bestLabels：数据样本被分到的聚类中心索引，元素为int类型
// criteria：算法终止迭代的条件，可以指定迭代数或者指定最小聚类中心偏移距离
// attempts：设定算法总体迭代次数，即前文的解决方案1，选择不同的初始聚类中心
// flags：初始化选项
// centers：找到的聚类中心，如果不需要该结果直接传入cv::noArray()
double cv::kmeans(cv::InputArray data,
int K,
cv::InputOutputArray bestLabels,
cv::TermCriteria criteria,
int attempts,
int flags,
cv::OutputArray centers = cv::noArray());

该接口中参数data是一组多维样本点的矩阵，其中每一行都表示了一个样本，矩阵中的每个元素都是浮点类型的，如CV_32FC1。当然矩阵也可以只有一列，但此时元素类型需要是多通道的，如CV_32FC2、CV_32FC3甚至CV_32FCM等。参数criteria可以指定算法迭代结束的条件，可以从迭代执行次数和最小距离两个角度，这里的最小距离指的是算法两次计算出的聚类中心之间的距离低于设定阈值时算法结束迭代。参数attempts指定了算法的总体迭代次数，一次总体迭代表示算法寻找新的聚类中心初始位置，也就是前文解决方案1描述的策略，算法会保存最好的结果。这里结果的质量通过紧凑度衡量，也就是说所有样本点到各自关联的聚类中心的距离平方和。

参数flags的取值包含cv::KMEANS_RANDOM_CENTERS、cv::KMEANS_USE_INITIAL_LABELS、cv::KMEANS_PP_CENTERS，其中第一个是默认值。cv::KMEANS_RANDOM_CENTERS表示的是前文提到的随机选择初始的聚类中心。cv::KMEANS_USE_INITIAL_LABELS表示使用参数bestLabels的信息来计算初始的聚类中心。而cv::KMEANS_PP_CENTERS表示使用Sergei Vassilvitskii和David Arthur提出的K-均值++的方式去计算初始的聚类中心，具体可以参考论文《k-means++: the advantages of careful seeding》。K-均值++内部的原理这里不用关心，我们暂时只需要知道该算法会更谨慎的选择初始的聚类中心，通常比使用默认选项算法执行更少的迭代次数，并且现代引用中，K-均值++也逐渐成为标准策略。

需要注意的是理论上K-均值算法可能得到非常糟糕的结果，但是它在实践中却仍被大量使用是因为大多数时间它都能得到很好的结果。在最坏的情况下分簇问题是一个NP问题，意味着不太可能得到一个真正的优解，但是对于大多数应用而言一个较好的解已经足够。 除此之外该算法还有一些其他问题。其中一个就是在特定的场景下，该算法可能得到一个数学家称为”Arbitrarily Bad”的结果。也就是无论你认为得到的结果有多糟糕，总有人会面临同样或者更糟的结果。在过去几年中也出现了一些应对这个问题的新技术，它们旨在提供一些通用的性能改进，或者在最好当前情况下一些技术还能提供一些可以证明的边界，这些边界能在算法结果上给用户多一点信心。这些改进技术中的一个就是前文提到的K-均值++算法。

使用K-均值算法的示例程序核心如下，阅读该部分源码对理解算法是有帮助的，并且数据生成部分的代码也可以用于测试其他机器学习程序。完整的源码请前往程序KMeans，更多关于算法的细节请参考前文列出的论文。

3.2 马氏距离(Mahalanobis Distance)

前文的章节中已经介绍过马氏距离可以计算点到分布中心的距离，并且它的计算结果与分布形状密切相关。在K均值算法的背景下，马氏距离的概念有两种用途。第一个应用来源于将其视为在变形空间上测量欧式距离(Euclidean Distance)的观点，这使得我们可以使用马氏距离对数据进行处理从而明显提升K均值算法的性能。第二个应用是将其作为为K均值算法定义的类簇分配新数据点的方法。

3.2.1 使用马氏距离约束输入数据

在示例程序KMeans中，我们简要提到了数据在空间上的分布可能极其不对称。当然使用K-均值算法的核心是保证数据在空间上是不均匀分布的，然后尝试找到类簇。然而不均匀(Nonuniform)和不对称(Asymmetrical)之间有非常重要的差异。例如假如数据在某个维度上的分布较松散，而在另外一个维度上分布较为紧凑，则K均值算法的计算结果会较差。马氏距离使我们可以将数据的协方差看作是空间上的拉伸，如下图中，左图中的原始数据在垂直方向上的距离要小于水平轴上的距离。右图中，空间使用方差归一化后数据之间的水平距离小于对应的垂直距离。

这种情况经常出现，因为数据向量的不同维度通常具有不同的度量单位。例如如果使用身高、体重和受教育的年限来表示社区内的某个人，最明显的就是身高和年的度量单位并不相同，这使得它们各自维度上的数据分布并不相同。类似的，尽管年龄和受教育的时间度量单位都是年，但是他们在自然人口中的数据分布差异也非常大。这个例子引出了一个简单有用的技术，可以将数据集合看作是一个整体，并计算整个数据集协方差矩阵，然后使用协方差对原始数据进行缩放。

在前文章节介绍函数cv::Mahalonobis()时曾介绍过马氏距离。传统的马氏距离沿着某个点的特定方向，使用分布的方差作为度量单位测量了任意点到数据分布中心的距离。对于这些和统计学上的Z-score概念相似的算法而言，马氏距离是Z-score在多维空间上的推广。我们使用分布的协方差逆矩阵来计算马氏距离，协方差矩阵的计算公式如下。

其中E[.]表示期望，则两个点之间的马氏距离计算公式如下。

此时，我们有两种选择继续使用马氏距离。首先我们可以在K均值算法中使用马氏距离替换欧式距离，其次我们也可以首选对数据进行缩放，然后在变形空间上使用欧式距离。第一个方案可能更直观，但是假如我们不想破坏已有还不错的K-均值算法实现的话，第二个方案在计算上会容易很多。最后，因为马氏距离对数据的缩放是线性的，因此可以直接对缩放后的结果进行插值。

显然采用第一种方案，我们可以通过如下公式对原始进行处理。其中D🌟是处理后的数据，D是原始数据，【∑-1/2】是逆协方差的平方根的倒数。这里协方差相关项放在等式的末尾是因为在机器学习库ML的惯例中，矩阵中每行表示一个样本，其中的每列表示不同的维度。也就是说数据是按行排列的，而不是按列排列。

这里我们不直接使用函数cv::Mahalanobis()计算马氏距离，相反我们使用函数cv::calcCovarMatrix()计算协方差矩阵，再使用函数cv::invert()和参数cv::DECOM_EIG计算其逆矩阵，最后再计算其平方根。

在计算逆矩阵时，分解方式也可以选择cv::DECOMP_SVD，但是这种方式的计算速度更慢，并且精度更低。另外即使DECOM_EIG所耗费的时间比DECOM_LU更长，但是当数据的维度明显低于数据集的样本数量时仍然应该选择这种方式。这种情况下整个算法的总体时间由函数cv::calcCovarMatrix()控制。因此更明智的方式是多花一点点时间用于计算逆协方差矩阵从而获得更高的精度。另外这里并没有一个通用的计算平方根函数，但是由于协方差矩阵自身的特性。可以先对其对角化处理，然后再分别计算特征值的平方根，然后再使用对角化处理时的特征向量将其旋转回原始的坐标系。

3.2.2 使用马氏距离分类

给定一个使用K均值或者其他算法分类的标签，我们可以尝试预测新的样本点最有可能属于哪一个分类标签。当这些分类本身是，或者认为它们是高斯分布时，在处理数据的不同维度之间可能存在相关性时，应用马氏距离对于分类预测也是有意义的。
首先我们需要描述每个类簇的平均值和协方差，然后就可以计算新样本点到每个类簇中心的马氏距离。到这里你可能会猜测新样本点属于具有最小马氏距离的类簇，然而事情并没有如此简单。准确的说只有当所有的类簇包含相同数量的元素时这个猜测才是正确的，或者从统计学的角度说，如果属于每个类簇的先验概率是相同的情况下，这个猜测才成立。

这个差异可以简洁的使用贝叶斯规则描述，即对于事件A和B，事件B成立前提下A成立的概率，和事件A成立前提下B成立的概率并不相同。用公式概括如下：

贝叶斯规则也提到事件B成立概率与事件B成立前提条件下事件A成立概率的乘积，和事件A成立概率与事件A成立前提条件下事件B成立概率的乘积相等，用公式概括如下：

为了将这些概率理论和马氏距离分类问题联系在一起，回想一下马氏距离告诉我们的是特定样本X位于分类C前提条件下P(C)，出现对应观测值的概率P(X | C)，马氏距离越，概率越低。其中关键的是它前提已经假定了样本X属于分类C。但是我们想要知道的是出现样本X的观测值P(X)前提条件下，样本属于类簇C的概率P(C | X)。基于贝叶斯规则的计算公式如下：

随机从集合中抽取到一个样本，其位于分类C的概率P(C)近似等于类簇C的样本数量NC和ND的比值。这意味着为了比较两个不同类簇的马氏距离，我们需要考虑类簇的样本数量。假定每个类簇的概率分布都是高斯分布，我们应该比较的的指标被称为似然性，其计算公式如下：

你可能注意到在这个公式中没有P(X)的计算，这是因为样本在没有确切分配到每个类别中时，我们没有任何预先理由相信任意的特定样本取值会比其他取值出现的概率更高，即使特定的取值确实有着更高的概率也不重要，因为这个概率对于我们比较的所有组别都是相同的。等式的后半部份首先对类簇C的协方差矩阵计算其行列式结果后区平方跟的倒数，然后将马氏距离的平方作为自然数e的指数。

小结

在这一章我们首先讨论了什么是机器学习，以及这个庞大的问题集合中哪些部分可以使用OpenCV库解决，以及哪些不能。我们讨论了测试数据和训练数据之间的区别。我们了解到生成式模型在无监督或者没有带标签的训练数据前提下尝试找到数据中的结构，而判别式模型从示例中学习并尝试从已知的信息中推广数据结构。然后我们开始研究OpenCV库中的两个基本工具，K均值聚类算法和马氏距离。我们看到如何使用这些工具构建简单的模型从而解决有趣的问题。我们顺便提到OpenCV目前也支持深度神经网络，但是它们当前还位于实验性质的库OpenCV_Contrib中。在最后的附录B种的示例cnn_3dobj和dnn中将会有更详细的描述。