《Python人脸识别：从入门到工程实践》 ——2.5.2　分类算法

2.5.2　分类算法

常见的分类算法有K最近邻算法（k-Nearest Neighbor, kNN）、支持向量机（Support Vector Machine, SVM）、决策树（Decision Tree）、AdaBoost（Adaptive Boosting）等。在人脸识别中，使用较多的分类算法为支持向量机和AdaBoost算法，因此我们将主要介绍支持向量机与AdaBoost算法。

1.支持向量机

支持向量机的英文名称为Support Vector Machine，它是一个二分类器，所谓的二分类就是分类结果只有A或者B两个类别，这是机器学习中的非常常用的一种分类算法。

我们先从理论上对支持向量机算法进行介绍。

假设训练数据为{(xi,yi）i=1,K,m}，其中yi代表xi所属的种类，一般用yi=±1表示。假设存在超平面wTx+b=0，使得

xi到超平面wTx+b=0的距离为di=wTxi+bw2，我们把在yi=±1的类中距离超平面最近的xi称为支持向量。这里所谓的超平面与我们平时听到的平面概念类似，只不过平面是分布在三维空间中的二维图形，而超平面是分布在高维空间中的。超过三维的空间很难想象，我们在学习中可以将其类比到三维空间中进行想象。

设支持向量到超平面的距离为d，那么有

我们不妨设dw2=1，那么目标函数将变为：

我们注意到，最大化1w2与最小化12w2是等价的，因此我们将上式转换成凸问题：

这个式子也就是线性可分支持向量机在模型训练过程中的最优化问题。

图2-6　将类别进行二分类的3种情况

截至这里，我们就已经推导出支持向量机算法的一种最为基础的表现形式了。我们分析一下这个式子，这个优化问题的目标函数实际上就是两个类别的分解样本之间的距离，如图2-6所示。这个式子是在满足约束条件的前提下，求解决策边界最大化的过程。也就是说，虽然能够将数据集划分为两类的超平面很多，但是，它们并不都能保证决策边界的最大化。例如图2-6展示了进行二分类划分时候的3种情况。

在二维空间中，存在3条直线H1、H2与H3,它们均能在这个特征空间中进行类别的二分类。但是，这里面分类效果最优的应该为H3。

对于直线H1,它虽然能够进行二分类，但是存在很多误分点，划分后的类别存在较大的误差，效果比较差。

对于直线H2,虽然在该数据集中能无误差地将类别进行完全划分，但是划分后的决策边界之间的距离很小，也就是类别边界点到直线H2的距离很小，使得模型分类其他数据时候的泛化能力较差。故而，H3是这3条直线中分类效果最好的一条。

但是，对于这类优化问题，在实际中我们很难求解到全局最优解，一般情况我们所得到的解都是较优的近似解。

进一步说，如果数学基础比较好的话，我们不妨看一下该式对偶形式的推倒过程。上式的拉格朗日形式可以写成：

为了便于计算，将拉格朗日形式转换成它的对偶形形式，即

其中α是对偶变量，α≥0。在该式的基础上，通过一系列推导（参见参考文献\[1\]）可得：

转化成凸二次规划的对偶问题

假设a=［a1,a2,…,al］T是上述对偶最优化问题的解，那么存在下标j使得aj>0，由此可以得到下面这个结论：

那么，对于某一个类别y就可以通过下式来判断：

其中，sign代表符号函数，其结果为1或-1,即对应着两个不同的类别。

可以看到，支持向量机问题实际上是一个规划问题，求解的过程实际上是在寻找这个规划的全局最优解。在数学上一般常用序列最小最优化（Sequential Minimal Optimization，SMO）算法来求解支持向量机问题的全局最优解。SMO算法是1998年由Platt提出来的，可以用来快速求解凸二次规划问题的全局最优解。因此，我们将支持向量机的形式转变为对偶的形式后，可以用该算法来加速对支持向量机这个规划问题的最优解求解过程。SMO算法的计算过程比较复杂，在此不做探讨，感兴趣的读者可以查阅参考文献\[1\]进一步学习。

我们在上面看到的是支持向量机的一种最简单的形式——线性可分支持向量机，这个理论推导过程已经非常复杂了。我们更喜欢用直白、通俗的语言来描述一个数学算法。

我们熟悉二维平面，也熟悉三维空间。以三维空间为例，它是通过长、宽、高进行建模的，我们所接触的物体分布在三维空间的某一个位置上。我们由此想象，由于机器学习的某一个特征值是可以用标量数值来表征的，那么将这些特征分布在某一个空间中，这个空间我们便称之为特征空间。

我们每个人所处的位置是可以通过长、宽、高3个维度来表征的，这3个维度的坐标数值就可以看作是我们位置的具体特征。那么，我们将机器学习中的特征分布到某特征空间中，虽然这些特征的维度多半都是超过三维的，但是与我们每个人处在三维空间中的某个位置是一样的道理。

　图2-7　二维空间中使用支持向量机进行类别划分

而支持向量机所要做的就是在这个特征空间中寻找某一超平面，使得分布在特征空间中的样本点能够被这个超平面分割为两类。例如图2-7展示了在二维空间中，使用支持向量机算法将两个类别进行划分的过程。

在图2-7中我们可以看到，在由X1与X2两个特征向量所组成的特征空间中，存在两个类别——实心圆点和空心圆点。这两个类别可以通过一条直线wx－b=0进行区分，在该二维图像中，b为一个正实数，调整了其前面的符号，用以表示截距。由于是一条直线，w将不再表示一个向量，而是一个标量。那么也就是说，在这个特征空间中，我们可以获得一个判断类别的函数：f(x)=wx－b将某一个特征向量x带入这个公式中，如果这个结果是大于0的，也就是说上述函数在该直线之上的，即可以由算法判断为实心类别；反之，则判断为空心类别。这也进一步印证了机器学习训练过程中算法所做的事：通过现有的（x,y）数据样本，寻找f（x）中合适的（w,b）参数。

图2-7展示的是在二维特征空间中的样本分类，多维特征空间的原理也是一样的。例如，图2-8展示了在三维特征空间中分布的两个类别的样本。在该图中我们能够看到，用于区分这两个类别的不再是一条线段，而是一个平面。

通过图2-7与图2-8的展示，我们不难理解支持向量机的基本思路。对于维度高于三维的特征空间，我们很难用图像的形式直观展示出来，在我们的脑海中也是难以想象和建模的。但是，它们的基本原理是一致的。也就是说，对于具有N个特征的数据集，该数据集中的样本分布在一个N维的特征空间中，将这些样本点划分为两个类别的超平面也是N-1维的。

在前面我们介绍过支持向量机算法求得的解，对于线性可分支持向量机来说，存在以下不足：样本点在特征空间中的分布很多都是线性不可分的，也就是无法用一条直线、一个平面或者一个超平面来简单粗暴地将两个类别划分开，如图2-9所示。

                                                          图2-8　在三维特征空间中以一个平面将

样本划分为两个类别　          　图2-9　数据集不能线性可分的情况

那么对于图2-9所示的这种情况，我们该采用什么样的方法来解决呢？我们可以看到图2-9中的两类样本点虽然不可以完全使用一条直线进行分割，但是可以在容忍一定误差的情况下，近似地使用一条直线进行类别的划分。那么我们可以想一下：是否可以将支持向量机算法进行改进，在允许容忍一定误差的前提下，尽可能地对样本点进行分类呢？答案自然是可行的，这样就引出了线性支持向量机。

（1）线性支持向量机

我们知道，线性可分支持向量机强调的是可以通过线性手段严格地将样本点分为两类。这样就会有一个问题，如果样本点中存在噪声或者样本点的边缘的界定本身就比较“模糊”，这时就需要我们适当地“让出”一部分的区域，使得样本点能够被完全地分为两类。

线性不可分意味着某些样本点(xi,yi)不能满足函数间隔大于或者等于1的约束条件，这个约束条件如下：yi(wT·xi+b)－1≥0为了解决这个问题，为每一个样本点(xi,yi)引进一个松弛变量ξi，且该变量是一个大于等于0的实数。那么，我们便可以将约束条件更改为：yi(wT·xi+b)≥1-ξi这相当于我们在容忍了一定误差的前提下，使用线性的方法将数据集中的类别进行划分。这样，也就可以在一定程度上解决线性不可分的情况。我们通过对算法的学习可以了解到，支持向量机算法实际上是一个规划问题，在上述式子中，我们只是修改了支持向量机中的约束条件，对于规划的目标函数，我们也需要进行一下改造。我们将目标函数由最简单的线性可分支持向量机的形式12w2修改为：12w2+C∑Ni=1ξi其中，参数C表示惩罚参数，是该算法中一个可调的超参数，可以根据具体情况来调整。C值越大，对错误分类时的惩罚力度越大，反之亦然。那么，目标函数的作用将会比较清晰：保证决策边界尽量大，也就是12w2尽量小，同时也要求误分点的数量尽量少。那么参数C也就是平衡二者之间权重关系的参数，也就是调和二者的系数。因此，我们可以得到线性不可分的线性支持向量机学习过程的凸二次规划（convex quadratic programming）表达式：

（2)核技巧

我们通过前面的学习，发现支持向量机只能够对线性可分，或者近似线性可分的样本点进行分类。但是，我们平时所接触到的数据样本很多都是非线性的，这样岂不是极大地制约支持向量机这个算法的使用场景了吗？

非线性分类问题是指需要利用非线性模型才能够获得比较好的分类结果的一类问题。如图2-10所示，这个分类过程是一个非线性的分类过程。很明显，两类样本点之间无法通过一条直线、一个平面或者超平面进行分类，因此，我们称这些样本点是非线性可分的，　

图2-10　一种非线性分类的示例

我们需要用一种非线性的模型对样本点进行分类。如图2-10所示，对于这两类样本点，我们可以使用椭圆将其进行分类。

因此我们就可以引出支持向量机的一个精髓的设计思想——核技巧（kernel trick）。所谓核技巧就是在原有支持向量机算法的基础上，引入了一种变换函数，称之为核函数。核函数有一个作用，它的作用就是将非线性可分的特征空间映射到线性可分的特征空间中。当然，这个所谓的“映射”过程，更确切地说是一种变换的过程。

我们看一下如图2-11所示的过程，这是将图2-10中的由x(1)与x(2)组成的特征空间中，线性不可分的点映射到另一个由z(1)与z(2)组成的线性可分的特征空间中去。既然在这个新的特征空间中样本点是线性可分的，那么我们不妨对经过“变换”后的样本使用支持向量机算法，这样就可以实现对非线性可分的样本进行分类了。

图2-11　将原始的非线性可分的特征空间变换到线性可分的特征空间

由于非线性问题相对于线性问题更难求解，因此，支持向量机的核技巧思想便是希望使用一种非线性变换的思路来将非线性问题转换为线性问题，通过求解变换后的线性分类问题来间接地解决非线性分类问题。在图2-11中可以看到，数据集的原始特征空间（即输入空间）中能够对这两种点进行分类的一种模型椭圆也被核函数变换为了新的线性可分的特征空间中的一条直线了。数据集的输入空间往往是欧氏空间或离散集合，而变换后的特征空间是希尔伯特空间（是欧氏空间的推广，不再局限于有限维），核函数使得在欧氏空间中的某条超曲面对应着希尔伯特空间中的一条超平面。因此，我们可以将核函数的数学定义如下。

存在一个映射关系(x)将输入空间（欧氏空间）X变换到特征空间（希尔伯特空间）H中，(x):X→H使得对于所有的x,z∈X，函数K(x,z)满足：K(x,z)=(x)·(z)K(x,z)即为核函数，(·)即为映射函数。

支持向量机的核技巧是一个非常精巧的设计。这种算法的设计非常具有“工程”思想，类似我们在面向对象编程过程中设置了一个接口，用户可以自己发挥想象实现这个接口来达到预期的目的，而这个接口正是核函数。

常用的核函数有高斯核函数、Sigmoid核函数、多项式核函数等。有关核函数的进一步推导，在此不赘述，感兴趣的读者可以阅读参考文献\[1\]。

2.AdaBoost算法

AdaBoost英文全称为Adaptive Boosting。AdaBoost算法也被称作自适应增强算法，它是1995年由Yoav Freund和Robert Schapire提出，主要用于将预测精度低的弱分类器增强为预测精度高的强分类器，为直接构造强分类器提供了新的思路和方法。

提升过程的理论基础之一有一个有意思的结论：在概率近似正确（Probably Approximately Correct,PAC）的学习框架中，一个概念是强可学习（该概念存在一个由多项式组成并且预测正确率还很高的学习算法）的，则它也同样是弱可学习的，反之亦然。也就是我们所说的可以互相推导的充要条件。这自然就启发大家去寻找将弱可学习算法提升为强可学习算法的方法了。

AdaBoost算法是一种提升（boosting）方法，这是一种常用且十分有效的统计学习方法。这类算法的特点是：在分类问题中，它通过改变训练样本所占据的权重，来训练出多个分类器，这些分类器可能是分类能力较弱的弱分类器。提升方法将这些弱分类器进行线性组合，从而得到一个分类能力较强的强分类器。这种思想类似于俗话所说的“三个臭皮匠顶一个***”。虽然一种弱分类器分类效果比较差，但是“众人拾柴火焰高”，将它们组合到一起往往能够起到更好的分类效果。

它的核心思想是：首先为每个样本数据分配初始权值，然后在每步迭代过程中，通过新加入的基本分类器（弱分类器）的分类错误率来逐步调整权值，当达到预先指定的迭代次数或者预测错误率足够小时，便可以将迭代过程中的基本分类器进行组合得到一个强分类器。

算法具体输入输出如下。

输入：训练数据集(x1,y1）,…,(xN,yN）,其中xi为训练样本，yi∈{－1,1}为训练样本的类别标签，i=1,2,…,N，弱分类器hm,m=1,2,…,M。

输出：最终的强分类器H。

算法流程如下：

1）初始化训练样本的权值分布。

为每一个训练数据赋予相同的权值，即1/N，权值集合可表示如下。P0={p0,1,p0,2,…,p0,N}=1N,1N,…,1N2）进行迭代，k=1,2,…,K。

选取按照当前权值，分类错误率最低的弱分类器h作为第k个基本分类器Hk。计算Hk:X→{－1,1}的分类错误率ek。ek=∑Ni=1pk－1,iI(Hk(xi)≠yi)其中I(Hk(xi)≠yi)=1Hk(xi)≠yi

0Hk(xi)=yi计算当前弱分类器Hk在最终强分类器中的权重βk。βk=12ln1－ekek更新训练样本的权值分布Pk。Pk={pk,1,pk,2,…,pk,N}其中pk,i=pk－1,iexp(－βkyiHk(xi))γkγk=∑Ni=1pk－1,iexp(－βkyiHk(xi))为归一化常数。

3）按照各个弱分类器的权重组合弱分类器,得到最终的强分类器H。H=sign∑Ki=1βiHi其中sign(x)=1x<0

0x=0

1x>0下面举一个例子进行说明。

设训练数据集为(1,1），(2,1）,(3,1）,(4,－1），(5,－1）,(6,－1）,(7,1）,(8,1），这些数据的样本格式为(x,y)的数据对。我们希望找到一个分类模型，其能将给定的数值划分到{+1,-1}的某一类中。

我们按照上述AdaBoost算法进行计算。首先为上述数据分配初始权值如下：(0.125，0.125，0.125，0.125，0.125，0.125，0.125，0.125）第1次迭代过程：

选取错误率最小的分类器H1(x）=1x<3.5

－1x>3.5。

其分类错误率为0.250。h1在最终强分类器中的权重β1=0.5493，更新完的权值分布如下：P1=［0.0834,0.0834,0.0834,0.0834,0.0834，0.0834,0.2499,0.2499］第2次迭代过程：

选取错误率最小的分类器H2(x）=－1x<6.5

1x>6.5

其分类错误率为0.0834×3=0.2502。h2在最终强分类器中的权重β2=0.5488，更新完的权值分布如下：P2=［0.1666，0.1666，0.1666，0.0556，0.0556，0.0556，0.1666，0.1666］以两次迭代过程为例，我们最终得到的强分类器如下：H=sign(0.5493×H1+0.5488×H2)我们可以看到，AdaBoost算法是一个逐步迭代的算法，每一步计算都是在前一步计算的基础上，通过组合多个弱的分类器，最终得到一个强分类器。

3.PCA（Principal Component Analysis）算法

在机器学习与数据挖掘领域中，其数学模型算法的复杂度常常与数据维度有密切联系。如果算法中选取的特征向量的维度过大，也就是说在模型训练中选择的特征非常多，将会造成算法计算量的急剧膨胀，就是所谓的维数灾难（Curse of Dimensionality）。

维数灾难又名维度的诅咒，是一个由Richard E. Bellman在考虑优化问题时首次提出来的术语，用来描述当数学空间中维度增加或分析和组织高维空间时，因空间的体积指数增加而遇到各种问题场景。上述所说的问题出现在高维空间中，这些高维空间的维度通常是成百上千的，而这些问题在低维度空间中一般不会遇到。在数据采样、组合数学、机器学习和数据挖掘等很多领域中，都很容易遇到这样的情况。为了应对维数灾难，人们想到了将高维空间映射到低维空间的方法，从而将维数降低，也就是所谓的降维。

例如，我们赖以生存的地球是三维的，我们根据地球的形状制造出来的地球仪也是三维的，而世界地图却是二维的。虽然世界地图是二维的，但是它仍然能够与地球仪一样表示出不同国家在地球上的位置。从这个例子中我们不难看出，用地球仪来表示地球可以认为是对地球的一种缩放，而用世界地图来表示地球，这不仅对地球进行了缩放，还进行了降维，也就是将三维空间所表示的信息映射到二维平面中。虽然世界地图在表示上不如地球仪形象，丧失了空间特征，但是对于定位地球上不同国家的位置这样最主要，也是我们最关注的功能却依然能够实现。因此，我们可以得出：在降维过程中，必不可少地会损失一些次要信息，但是，我们最需要的、最主要的也是最关键的信息却被保留了下来，颇有一种“删繁就简”的感觉。而这也就是降维算法要实现的本质功能。因此，降维也可以看作对数据的一种有损压缩方式。

我们日常接触到的降维过程其实很多，例如我们的眼睛将三维空间转换为了二维图像供我们的大脑进行处理；拍照、绘画等也是类似的过程。实现降维的算法有很多，可以分为线性降维和非线性降维两类。我们在这里主要介绍的降维算法是线性降维算法中的PCA算法。

PCA算法即主成分分析算法，它通过线性变换，将原始数据投影到一组线性无关的低维向量上，从而实现对高维数据的降维。PCA算法可以归纳到机器学习算法中的无监督学习中。通俗一点理解，PCA算法的大致原理类似我们所熟知的“投影”过程。图2-12展现了将分布在三维特征空间中的样本点降维到二维特征空间中的示例。

图2-12所示的即为鸢尾花数据集进行降维的过程，图2-12a所示的为在鸢尾花数据集中选取3个特征使其分布在三维特征空间中的样本点，采用PCA算法将三维特征空间的维数降低至二维，则得到分布在二维特征空间中的样本点，如图2-12b所示。我们可以看到，在这个例子中，PCA算法找到某一个二维平面，将三维特征空间中的样本点映射到这个二维平面中，所得到的二维平面就是上述降维的结果。

图2-12　鸢尾花数据集的降维示例

而PCA算法的实际计算过程并没有上述那么简单，其计算过程涉及一些矩阵相关的概念，主要包括矩阵分解、协方差矩阵等。有些概念在本书中不涉及，读者可以阅读参考文献\[5\]。下面简要介绍一下PCA算法的实现步骤。

设数据集为{x1,x2,x3,…,xn},每个数据的维度为p,则将数据集写为p行n列的矩阵X。若将其降维至k维，则有：

1）对数据集中的每个数据、每一位特征（每一行）减去各自特征的平均值，即对数据中的每一个特征维度进行零均值化，得到归一化后的矩阵B。

2）求协方差矩阵C=1nBBT。

3）分解协方差矩阵C的特征值与特征向量。

4）将协方差矩阵分解后的特征值从大到小排序，选择其中最大的k个，然后将这些特征值对应的k个特征向量分别作为行向量组成特征向量矩阵P。

5）得到降维后的结果为：Y=PXPCA算法不仅可以使用矩阵分解的方法进行求解，还可以使用奇异值分解的方法来求解。第4章会给出使用Python实现PCA算法的例子，详见代码清单4-7。

PCA算法不仅在特征的预处理上具有重要作用，在人脸识别领域同样有十分重要的应用。例如，我们将某一张清晰度很高的图片转换为另一张清晰度较低的图片，这张转换后的图片同样能够分辨其所要表现的物体，也就是在不损失原有图像所要表达内容的前提下进行的。那么这个过程也是一个降维过程，因为高清度的图片像素点较多，经过转换的图片像素点降低很多，但是又不损失原有的主要信息，那么这个过程自然就是一个降维过程了。在后面，我们会具体讲解到使用PCA算法进行人脸识别的方法。