摘要
第3章
基 本 概 念本章介绍机器学习中的常用概念,包括算法的分类、算法的评价指标,以及模型选择问题。按照样本数据是否带有标签值,可以将机器学习算法分为有监督学习与无监督学习。按照标签值的类型,可以将有监督学习算法进一步细分为分类问题与回归问题。按照求解的方法,可以将有监督学习算法分为生成模型与判别模型。
比较算法的优劣需要使用算法的评价指标。对于分类问题,常用的评价指标是准确率;对于回归问题,是回归误差。二分类问题由于其特殊性,我们为它定义了精度与召回率指标,以及真阳率和假阳率，在此基础上可以得到ROC曲线。对于多分类问题,常用的评价指标是混淆矩阵。
泛化能力是衡量有监督学习算法的核心标准。与模型泛化能力相关的概念有过拟合与欠拟合,对泛化误差进行分解可以得到方差与偏差的概念。正则化技术是解决过拟合问题的一种常见方法,本章介绍它的实例――岭回归算法。
3.1算法分类
按照样本数据的特点以及求解手段,机器学习算法有不同的分类标准。这里介绍有监督学习和无监督学习、分类问题与回归问题、生成模型与判别模型的概念。强化学习是一种特殊的机器学习算法,它的原理将在第22章详细介绍。
3.1.1监督信号
根据样本数据是否带有标签值(Label),可以将机器学习算法分成有监督学习和无监督学习两类。要识别26个英文字母图像,我们需要将每张图像和它是哪个字符（即其所属的类别）对应起来,图像的类别就是标签值。
有监督学习(Supervised Learning)的样本数据带有标签值,它从训练样本中学习得到一个模型,然后用这个模型对新的样本进行预测推断。样本由输入值与标签值组成: (x,y)其中，x为样本的特征向量,是模型的输入值;y为标签值,是模型的输出值。标签值可以是整数，也可以是实数,还可以是向量。有监督学习的目标是给定训练样本集,根据它确定映射函数: y=f(x)确定这个函数的依据是它能够很好地解释训练样本,让函数输出值与样本真实标签值之间的误差最小化,或者让训练样本集的似然函数优选化。训练样本数是有限的,而样本集所有可能的取值在很多情况下是无限集,因此，只能从中选取一部分样本参与训练。整个样本的集合称为样本空间。
日常生活中的很多机器学习应用,如垃圾邮件分类、手写文字识别、人脸识别、语音识别等都是有监督学习。这类问题需要先收集训练样本,对样本进行标注,用标注好的样本训模型,然后用模型对新的样本进行预测。
无监督学习(Unsupervised Learning)对没有标签的样本进行分析,发现样本集的结构或者分布规律。无监督学习的典型代表是聚类、表示学习和数据降维,它们处理的样本都不带有标签值。
聚类也是分类问题,但没有训练过程。算法把一批没有标签的样本划分成多个类,使得在某种相似度指标下每一类中的样本尽量相似,不同类的样本之间尽量不同。聚类算法的样本只有输入向量而没有标签值,也没有训练过程。在第18章中详细介绍各种典型的聚类算法。
无监督学习的另一类典型算法是表示学习,它从样本中自动学习出有用的特征,用于分类和聚类等目的。典型的实现有自动编码器和受限玻尔兹曼机,它们的输入是没有标签值的数据（如图像或语音信号）,输出值是提取的特征向量。在第14章详细介绍自动编码器和受限玻尔兹曼机的原理。
数据降维也是一种无监督学习算法,它将n维空间中的向量x通过某种映射函数映射到更低维的m维空间中,在这里m？n: y=？(x)通过将数据映射到低维空间,可以更容易地对它们进行分析与显示。如果映射到二维或三维空间,可以直观地将数据可视化。第7章将详细介绍数据降维算法。
对于有些应用问题,标注训练样本的成本很高。如何利用少量有标签样本与大量无标签样本进行学习是一个需要解决的问题,一种方法是半监督学习(Semi？Supervised Learning)。半监督学习的训练样本是有标签样本与无标签样本的混合,一般情况下,无标签样本的数量远大于有标签样本数。半监督学习的原理在第19章详细讲述。
〖1〗〖2〗机器学习――原理、算法与应用〖1〗第3章基本概念3.1.2分类问题与回归问题
在有监督学习中,如果样本的标签是整数,则预测函数是一个向量到整数的映射: Rn→Z这称为分类问题。样本的标签是其类别编号,一般从0或者1开始编号。如果类型数为2,则称为二分类问题,类别标签一般设置成+1和-1,分别对应正样本和负样本。例如,如果要判断一张图像是否为人脸,则正样本为人脸,负样本为非人脸。
对于分类问题,如果预测函数是线性函数则称为线性模型,它是n维空间的线性划分。线性函数是超平面,在二维平面中是直线,在三维空间中是平面。二分类问题的线性预测函数为sgn(wTx+b)其中，w是权重向量，b是偏置项。线性支持向量机、logistic回归等属于线性模型,它们的预测函数都是上面这种形式。
非线性模型的决策函数是非线性函数,分类边界是n维空间中的曲面。在实际应用中大多数情况下数据是非线性的,因此，要求预测函数具有非线性建模的能力。使用非线性核的支持向量机,人工神经网络、决策树等都属于非线性模型。
在有监督学习中,如果标签值是连续实数,则称为回归问题,此时预测函数是向量到实数的映射: Rn→R例如,我们根据一个人的学历、工作年限等特征预测他的收入,这就是一个回归问题,因为收入是实数值而不是类别标签。
与分类问题一样,预测函数可以是线性函数也可以是非线性函数。如果是线性函数则称为线性回归。
对于有监督学习,机器学习算法在训练时的任务是给定训练样本集,选择预测函数的类型称为假设空间,然后确定函数的参数值,如线性模型中的w和b。确定参数的常用方法是构造一个损失函数(Loss Function),它表示预测函数的输出值与样本标签值之间的误差。对所有训练样本的误差求平均值,这个值是参数θ的函数: minθL(θ)=1l∑li=1L(xi;θ)其中，L(xi;θ)为单个样本的损失函数,l为训练样本数。训练的目标是最小化损失函数,求解损失函数的极小值可以确定θ的值,从而确定预测函数。对机器学习算法来说关键的一步是确定损失函数,一旦它确定了,剩下的就是求解很优化问题,这在数学上一般有标准的解决方案。
下面以线性回归为例来说明有监督学习算法的训练过程。假设有l个训练样本(xi,yi),其中，xi为特征向量,yi为实数标签值。线性回归的预测函数为f(x)=wTx+b权重向量w和偏置b是训练要确定的参数。定义损失函数为误差平方和的均值,即均方误差: L=12l∑li=1(f(xi)-yi)2将回归函数代入损失函数的定义,可以得到如下损失函数: L=12l∑li=1(wTxi+b-yi)2为简化表述,将权重向量和特征向量进行增广,即将w和b进行合并,得到扩充后的向量: ［w,b］→w类似地,对x也进行扩充: ［x,1］→x目标函数可以简化为L=12l∑li=1(wTxi-yi)2可以证明这个目标函数是凸函数。目标函数展开后为L=12l∑li=1((wTxi)2+y2i-2yiwTxi)它的二阶偏导数为？2L？wi？wj=1l∑lk=1xkixkj其中,xki为第k个样本的特征向量的第i个分量。目标函数的Hessian矩阵为1l∑lk=1xk1xk1…∑lk=1xk1xkn
？？？
∑lk=1xknxk1…∑lk=1xknxkn写成矩阵形式为1lx1x2…xlxT1
xT2
？
xTl=1lXTX其中,X是所有样本的特征向量按照行构成的矩阵。对于任意不为0的向量x,有xTXTXx=(Xx)T(Xx)≥0因此,Hessian矩阵是半正定矩阵,上面的优化问题是一个凸优化问题,可以用梯度下降法或牛顿法求解。损失函数对wj的偏导数为？L？wj=1l∑li=1(wTxi-yi)xij得到对权重的梯度之后,可以用梯度下降法进行更新。由于是凸优化问题,梯度下降法可以保证收敛到全局很优解。也可以直接寻找梯度为0的点来解此问题,即求解线性方程组,这就是经典的最小二乘法。
3.1.3判别模型与生成模型
按照求解的方法,可以将分类算法分成判别模型和生成模型。给定特征向量x与标签值y,生成模型对联合概率p(x,y)建模,判别模型对条件概率p(y|x)进行建模。不使用概率模型的分类器也被归类为判别模型,它直接得到预测函数而不关心样本的概率分布: y=f(x)这3种模型也分别称为生成学习、条件学习和判别学习。
除此之外,对生成模型和判别模型还有另外一种定义。生成模型对条件概率p(x|y)建模,判别模型对条件概率p(y|x)建模。前者可以用来根据标签值y生成随机的样本数据x,而后者则根据样本特征向量x的值判断它的标签值y。
常见的生成模型有贝叶斯分类器、高斯混合模型、隐马尔可夫模型、受限玻尔兹曼机、生成对抗网络等。典型的判别模型有决策树、kNN算法、人工神经网络、支持向量机、logistic回归、AdaBoost算法等。
3.1.4强化学习
强化学习是一类特殊的机器学习算法,它根据输入数据确定要执行的动作,输入数据是环境参数。与有监督学习算法类似,这里也有训练过程。训练时,对正确的动作进行奖励,对错误的动作进行惩罚,训练完成之后用得到的模型进行预测。在第22章中详细介绍这种算法。
3.2模型评价指标
人们需要评价各种机器学习算法和模型的好坏,以进行比较,因此，需要定义衡量模型精度的指标。有监督学习分为训练与预测两个阶段,一般用与训练样本集不同的另一个样本集统计算法的精度。更复杂的做法是再引入一个验证集,用于确定模型的某些人工设定的超参数,优化模型。
对于分类问题,评价指标是准确率,它定义为测试样本集中被正确分类的样本数与测试样本总数的比值。对于回归问题,评价指标是回归误差,定义为预测函数输出值与样本标签值之间的均方误差。
3.2.1精度与召回率
对于二分类问题,它的样本只有正样本和负样本两类。以人脸检测问题为例,正样本是人脸,负样本是非人脸;对于垃圾邮件分类,正样本是垃圾邮件,负样本是正常邮件。
测试样本中正样本被分类器判定为正样本的数量记为TP(True Positive),被判定为负样本的数量记为FN(False Negative);负样本被分类器判定为负样本的数量记为TN(True Negative),被判定为正样本的数量记为FP(False Positive)。精度P定义为
P＝TPTP+FP
召回率R定义为
R＝TPTP+FN
精度是被分类器判定为正样本的样本中真正的正样本所占的比例,值越接近1,对正样本的分类越准确。召回率是所有正样本中被分类器判定为正样本的比例。一种特别情况是让分类器的输出都为正样本,此时召回率为1,但精度非常低。
F1值定义为
F1＝2PRP+R
3.2.2ROC曲线
对于二分类问题,可以调整分类器的灵敏度从而得到不同的分类结果。将各种灵敏度下的准确率指标连成一条曲线,就是ROC曲线(Receiver Operator Characteristic Curve, 接收机操作曲线)。首先定义真阳率和假阳率指标。真阳率(TPR)是正样本被分类器判定为正样本的比例:
TPR=TPTP+FN
在人脸检测中正样本是人脸,这个指标就是检测率,即所有待检测的人脸中能够检测出来的比例。假阳率(FPR)是负样本被分类器判定为正样本的比例:
FPR=FPFP+TN
对于人脸检测问题,这个指标就是误报率,即不是人脸的样本被分类器判定为人脸的比例。ROC曲线的横轴为假阳率,纵轴为真阳率。当假阳率增加时真阳率会增加,因此，它是一条向上增长的曲线。一个好的分类器应该保证假阳率低而真阳率高,因此，ROC曲线理想情况下应该接近于直线y=1,让曲线下面的面积尽可能大。
可以通过调整分类器的阈值（即灵敏度）,计算各种假阳率下对应的真阳率，绘制出ROC曲线。一般情况下分类器是如下判定函数: sgn (f(x))为了得到它的ROC曲线,需要为预测函数加上一个调节灵敏度的阈值ξ: sgn (f(x)+ξ)随着阈值的增大,被判定为正样本的样本数会增加,因此，真阳率会提高;但同时负样本被判定为正样本的数量也会增加,假阳率也会上升。通过调整ξ的值,每一个真阳率都会对应于一个假阳率,将这些点连起来就得到了ROC曲线。图3.1是人脸检测算法ROC曲线的一个例子。
图3.1ROC曲线的一个实际例子（来自FDDB官网）
图3.1取自人脸检测数据集FDDB的官网,横坐标是误报数,纵坐标是检测率。各种曲线代表各种不同的算法,ROC曲线越陡峭、越高,算法的性能越好。
3.2.3混淆矩阵
多分类问题的准确率可以用混淆矩阵定义。对于k分类问题,混淆矩阵为k×k的矩阵,它的元素cij表示第i类样本被分类器判定为第j类的数量:
c11…c1k
c21…c2k
？？
ck1…ckk
如果所有样本都被正确分类,则该矩阵为对角阵。因此，对角线上的值越大,分类器的准确率越高。
除了上面定义的这些通用指标,对于某些特定的问题还有特定的精度指标,例如，机器翻译、图像分割等问题都有自己的评价指标,在后面的章节中会具体介绍。
3.2.4交叉验证
对于精度指标的计算,最简单的做法是选择一部分样本作为训练集,用另一部分样本作为测试集来统计算法的准确率。交叉验证(Cross Validation)是一种更复杂的统计准确率的技术。k折交叉验证将样本随机、均匀地分成k份,轮流用其中的k-1份训练模型,1份用于测试模型的准确率,用k个准确率的均值作为最终的准确率。
3.3模型选择
3.2节定义了模型的评价指标,本节对导致模型误差的因素进行分析,并给出一般性的解决方案。
3.3.1过拟合与欠拟合
有监督学习训练的目标是使训练集上的误差最小化。由于训练样本集和测试样本集是不一样的,因此需要考虑下面几个问题。
（1） 算法在训练集上的表现。如果在训练集上表现不好,一般来说在实际使用时的精度很难保证。
图3.2欠拟合(2) 在训练集上学习得到的模型能否有效地用于测试集。衡量指标为泛化能力。泛化能力是指模型从训练集推广到测试集的能力。人们希望模型在训练集上有高准确率的同时在测试集上也有高准确率。针对上面两个问题定义了过拟合和欠拟合的概念。
欠拟合(Under？Fitting)也称为欠学习,其直观表现是训练得到的模型在训练集上表现差,没有学到数据的规律。引起欠拟合的原因: 模型本身过于简单,例如，数据本身是非线性的但使用了线性模型;特征数太少无法正确建立映射关系。图3.2是欠拟合的示意图。
图3.2中数据是线性不可分的,这两类样本的分界线是曲线而非直线,但使用了线性分类器,导致大量的样本被错分类,这时更好的选择是非线性分类器。
过拟合(Over？Fitting)也称为过学习,它的直观表现是在训练集上表现好,但在测试集上表现不好,推广泛化性能差。过拟合产生的根本原因是训练数据包含抽样误差,在训练时模型将抽样误差也进行了拟合。抽样误差是指抽样得到的样本集和整体数据集之间的偏差。直观来看,引起过拟合的可能原因如下。
(1) 模型本身过于复杂,拟合了训练样本集中的噪声。此时需要选用更简单的模型。
(2) 训练样本太少或者缺乏代表性。此时需要增加样本数,或者增加样本的多样性。
图3.3过拟合(3) 训练样本噪声的干扰,导致模型拟合了这些噪声,这时需要剔除噪声数据或者改用对噪声不敏感的模型。
图3.3是过拟合的示意图。
在图3.3中训练样本存在噪声,为了拟合它们,分类曲线的形状非常复杂,导致在真实测试时会产生错分类。
过拟合是有监督学习算法需要解决的一个问题。表3.1给出了实际应用时判断过拟合与欠拟合的准则。表3.1过拟合与欠拟合的判断标准训练集上的表现测试集上的表现结论不好不好欠拟合好不好过拟合好好适度拟合3.3.2偏差与方差分解
模型的泛化误差可以分解成偏差和方差。偏差(Bias)是模型本身标签导致的误差,即错误的模型假设所导致的误差,它是模型预测值与真实值之间的差值的数学期望。假设样本特征向量为x,标签值为y,要拟合的目标函数为f(x),算法拟合的函数为f^(x),则偏差为Bias(f^(x))=E(f^(x)-f(x))根据定义,高偏差意味着模型本身的输出值与期望值差距很大,因此会导致欠拟合问题。方差(Variance)是由于对训练样本集的小波动敏感而导致的误差。它可以理解为模型预测值的波动程度。根据概率论中方差的定义,有D(f^(x))=E(f^2(x))-E2(f^(x))根据定义,高方差意味着算法对训练样本集中的随机噪声进行建模,从而出现过拟合问题。模型的总体误差可以分解为偏差的平方与方差之和: E((y-f^(x))2)=Bias2(f^(x))+D(f^(x))+σ2其中,σ2为噪声项。这称为偏差？方差分解公式。下面给出推导过程。样本标签值由目标函数和随机噪声决定: y=f+ε其中,ε为随机噪声,其均值为0,方差为σ2,D(y)=δ2。根据定义,模型的总误差为E((y-f^)2)=E(y2+f^2-2yf^)
=E(y2)+E(f^2)-E(2yf^)
=D(y)+E2(y)+D(f^)+E2(f^)-2fE(f^)
=D(y)+D(f^)+(f2-2fE(f^))+E2(f^)
=D(y)+D(f^)+E(f-E(f^))2
=σ2+D(f^)+Bias2(f^)第3步使用了概率论中的结论: E(x2)=D(x)+E2(x)如果模型过于简单,一般会有大的偏差和小的方差;如果模型复杂则会有大的方差但偏差很小。这是一对矛盾,因此需要在偏差和方差之间做一个折中。
下面以一个简单的例子来解释偏差和方差的概念。在射击时,子弹飞出枪管之后以曲线轨迹飞行。如果不考虑空气的阻力,这是一条标准的抛物线;如果考虑空气阻力,这是一条更复杂的曲线。我们用弹道曲线作为预测模型,在给定子弹初速度的前提下,如果知道靶心与枪口的距离,可以通过调整枪口的仰角来让子弹命中靶心。
如果使用抛物线函数就会产生偏差,因为理论上子弹的落点不会在靶心而是在靶心偏下的位置,此时需要更换弹道曲线模型。无论选用哪种弹道曲线模型,受子弹初速度、风速等因素的影响,即使理论上瞄准的是靶心,子弹还是会随机散布在靶心周围,这就是方差。
3.3.3正则化
有监督机器学习算法训练的目标是最小化误差函数。以均方误差损失函数为例,它是预测值与样本真实值的误差平方和: L(θ)=12l∑li=1(fθ(xi)-yi)2其中，yi是样本的标签值，fθ(xi)是预测函数的输出值，θ是模型的参数。在预测函数的类型选定之后,能控制的只有函数的参数。为了防止过拟合,可以为损失函数加上一个惩罚项,对复杂的模型进行惩罚,强制让模型的参数值尽可能小以使得模型更简单,加入惩罚项之后损失函数为L(θ)=12l∑li=1(fθ(xi)-yi)2+λr(θ)函数的后半部分称为正则化项,这里的目标是让它的值尽可能小,即参数等于0或者接近于0。λ为惩罚项系数,是人工设定的大于0的参数。正则化项可以使用L2范数的平方（即平方和）λ2θTθ,也可以使用其他范数（如L1范数,即绝对值之和）λ‖θ‖。L2正则化在求解很优化问题时计算简单,而且有更好的数学性质,L2正则化项的梯度为λθ绝对值函数在0点不可导,如果不考虑这种情况,其导数为符号函数sgn(x)。L1正则化项的梯度为sgn(θ)与L2相比，L1正则化能更有效地让参数趋向于0,产生的结果更稀疏。除了直接加上正则化项之外,还有其他让模型变简单的方法,如决策树的剪枝算法、神经网络训练中的dropout技术、提前终止技术等,在后面各章中会详细介绍。
下面以岭回归为例说明正则化技术的使用,它是带L2正则化项的线性回归。在3.1.2节中已经介绍过,线性回归的目标函数是线性函数,训练时的目标是最小化均方误差损失函数: 12l∑li=1(wTxi-yi)2对wj求导并且令导数为0,可以得到下面的线性方程组: ∑li=1∑nk=1wkxik-yixij=0变形之后可以得到∑li=1∑nk=1xikxijwk=∑li=1yixij写成矩阵形式为下面的线性方程组: XTXw=XTy矩阵X是样本向量按行排列形成的矩阵,即X=xT1
xT2
？
xTl这是一个l×n的矩阵。如果系数矩阵ZTZ可逆,上面这个线性方程组的解为w=(XTX)-1XTy如果系数矩阵不可逆,则无法直接求解这个方程组。损失函数使用L2正则化项之后优化问题变为minw∑li=1(wTxi-yi)2+λ2wTw要求解的线性方程组变为(XTX+λI)w=XTy可以解得w=(XTX+λI)-1XTy如果参数λ的值足够大,可以保证这个方程组的系数矩阵可逆。如果一个矩阵严格对角占优,即每一行的主对角线元素的绝对值大于该行其他元素的绝对值之和,则矩阵一定可逆。除了使用L2正则化项,线性回归也可以使用L1正则化项,即LASSO回归。
参 考 文 献
［1］迪达,等. 模式分类［M］. 李宏东,等译.北京: 机械工业出版社,2003.
［2］米歇尔. 机器学习［M］. 曾华军,等译. 北京: 机械工业出版社,2002.
［3］Christopher M Bishop. Pattern Recognition and Machine Learning. Berlin: Springer, 2001.
［4］Kevin P Murphy. Machine Learning: A Probabilistic Perspective. Massachusetts: The MIT Press, 2004.
［5］Trevor Hastie, Robert Tibshirani, Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. New York: McGraw Hill, 2001.第二部分
主要的机器学习算法与理论
这部分是本书的主体,全面系统地讲解常用的机器学习算法与理论,包括有监督学习、无监督学习、半监督学习、强化学习4类算法。第4章讲解贝叶斯分类器,包括朴素贝叶斯与正态贝叶斯分类器。第5章讲述决策树,重点是分类与回归树。第6章讲述kNN算法与距离度量学习算法。第7章讲述数据降维算法,包括线性降维算法――主成分分析,以及非线性数据降维算法――流形学习。第8章讲述线性判别分析。第9章讲述人工神经网络,这是深度学习的基础。第10章讲述支持向量机。第11章讲述线性模型,包括logistic回归与线性支持向量机。第12章讲述第1种集成学习算法――随机森林。第13章讲述第2种集成学习算法――Boosting算法。第14章讲述深度学习的思想与基本概念,以及自动编码器、受限玻尔兹曼机。第15章讲述卷积神经网络。第16章讲述循环神经网络。第17章讲述生成对抗网络。第18章讲述聚类算法,包括层次聚类、EM算法、基于密度的聚类、谱聚类。第19章讲述半监督学习算法。第20章讲述隐马尔可夫模型。第21章讲述条件随机场。第22章讲述强化学习算法,包括经典的算法与深度强化学习。第4章
贝叶斯分类器贝叶斯分类器是一种概率模型,它用贝叶斯公式解决分类问题。如果样本的特征向量服从某种概率分布,则可以计算特征向量属于每个类的条件概率,条件概率优选的类为分类结果。如果假设特征向量各个分量之间相互独立,则为朴素贝叶斯分类器；如果假设特征向量服从多维正态分布,则为正态贝叶斯分类器。
4.1贝叶斯决策
贝叶斯公式描述了两个相关的随机事件或随机变量之间的概率关系。贝叶斯分类器［1］使用贝叶斯公式计算样本属于某一类的条件概率值,并将样本判定为概率值优选的那个类。
条件概率描述两个有因果关系的随机事件之间的概率关系,p(b|a)定义为在事件a发生的前提下事件b发生的概率。贝叶斯公式阐明了两个随机事件之间的概率关系: p(b|a)=p(a|b)p(b)p(a)这一结论可以推广到随机变量。分类问题中样本的特征向量取值x与样本所属类型y具有因果关系。因为样本属于类型y,所以具有特征值x。如果我们要区分男性和女性,选用的特征为脚的尺寸和身高。一般情况下男性的脚比女性的大,身高更高,因为一个人是男性,才具有这样的特征。分类器要做的则相反,是在已知样本的特征向量为x的条件下反推样本所属的类别。根据贝叶斯公式有p(y|x)=p(x|y)p(y)p(x)只要知道特征向量的概率分布p(x),每一类出现的概率p(y)即类先验概率,以及每一类样本的条件概率p(x|y),就可以计算出样本属于每一类的概率（后验概率）p(y|x)。分类问题只需要预测类别,比较样本属于每一类的概率的大小,找出该值优选的那一类即可,因此可以忽略p(x),因为它对所有类都是相同的。简化后分类器的判别函数为arg maxyp(x|y)p(y)实现贝叶斯分类器需要知道每类样本的特征向量所服从的概率分布。现实中的很多随机变量都近似服从正态分布,因此，常用正态分布来表示特征向量的概率分布。
贝叶斯分类器是一种生成模型。因为使用了类条件概率p(x|y)和类概率p(y),两者的乘积就是联合概率p(x,y),它对联合概率进行建模。4.2朴素贝叶斯分类器
朴素贝叶斯分类器［2］假设特征向量的分量之间相互独立,这种假设简化了问题求解的难度。给定样本的特征向量x,该样本属于某一类ci的概率为p(y=ci|x)=p(y=ci)p(x|y=ci)p(x)由于假设特征向量各个分量相互独立,因此有p(y=ci|x)=p(y=ci)∏nj=1p(xj|y=ci)Z其中，Z为归一化因子。上式的分子可以分解为类概率p(ci)和该类每个特征分量的条件概率p(xj|y=ci)的乘积。类概率p(ci)可以设置为每一类相等,或者设置为训练样本中每类样本占的比重。例如,在训练样本中第一类样本占30%,第二类占70%,我们可以设置第一类的概率为0.3,第二类的概率为0.7。剩下的问题是估计类条件概率值p(xj|y=ci),下面分离散型与连续型变量两种情况进行讨论。
〖1〗〖2〗机器学习――原理、算法与应用〖1〗第4章贝叶斯分类器4.2.1离散型特征
如果特征向量的分量是离散型随机变量,可以直接根据训练样本计算出其服从的概率分布,即类条件概率。计算公式为p(xi=v|y=c)=Nxi=v,y=cNy=c其中，Ny=c为第c类训练样本数;Nxi=v,y=c为第c类训练样本中第i个特征取值为v的训练样本数,即统计每一类训练样本的每个特征分量取各个值的频率,作为类条件概率的估计值。最后得到的分类判别函数为arg maxyp(y=c)∏ni=1p(xi=v|y=c)其中,p(y=c)为第c类样本在整个训练样本集中出现的概率,即类概率。其计算公式为p(y=c)=Ny=cN其中,Ny=c为第c类训练样本的数量,N为训练样本总数。
在类条件概率的计算公式中,如果Nxi=v,y=c为0,即特征分量的某个取值在某一类训练样本中一次都不出现,则会导致如果预测样本的特征分量取到这个值时整个预测函数的值为0。作为补救措施可以使用拉普拉斯平滑,具体做法是给分子和分母同时加上一个正数。如果特征分量的取值有k种情况,将分母加上k,每一类的分子加上1,这样可以保证所有类的条件概率加起来还是1: p(xi=v|y=c)=Nxi=v,y=c+1Ny=c+k对于每一个类,计算出待预测样本的各个特征分量的类条件概率,然后与类概率一起连乘,得到上面的预测值,该值优选的类为最后的分类结果。
4.2.2连续型特征
如果特征向量的分量是连续型随机变量,可以假设它们服从一维正态分布，称为正态朴素贝叶斯分类器。根据训练样本集可以计算出正态分布的均值与方差,这可以通过优选似然估计得到。这样得到概率密度函数为f(xi=x|y=c)=12πσexp -(x-μ)22σ2连续型随机变量不能计算它在某一点的概率,因为它在任何一点处的概率为0。直接用概率密度函数的值替代概率值,得到的分类器为arg maxcp(y=c)∏ni=1f(xi|y=c)对于二分类问题可以做进一步简化。假设正负样本的类别标签分别为+1和-1,特征向量属于正样本的概率为p(y=+1|x)=p(y=+1)1Z∏ni=112πσiexp -(xi-μi)22σ2i其中,Z为归一化因子,μi为第i个特征的均值,σi为第i个特征的标准差。对上式两边取对数得ln p(y=+1|x)=lnp(y=+1)Z-∑ni=1ln12πσi(xi-μi)22σ2i整理简化得ln p(y=+1|x)=∑ni=1ci(xi-μi)2+c其中,c和ci都是常数,ci仅由σi决定。同样可以得到样本属于负样本的概率。在分类时只需要比较这两个概率对数值的大小,如果ln p(y=+1|x)>ln p(y=-1|x)变形后得到ln p(y=+1|x)-ln p(y=-1|x)>0时将样本判定为正样本,否则判定为负样本。
4.3正态贝叶斯分类器
下面考虑更一般的情况,假设样本的特征向量服从多维正态分布,此时的贝叶斯分类器称为正态贝叶斯(Normal Bayes)分类器。
4.3.1训练算法
假设特征向量服从n维正态分布,其中μ为均值向量,Σ为协方差矩阵。类条件概率密度函数为p(x|c)=1(2π)n2|Σ|12exp-12(x-μ)TΣ-1(x-μ)其中,|Σ|是协方差矩阵的行列式,Σ-1是协方差矩阵的逆矩阵。图4？1是二维正态分布的概论密度函数。
图4.1二维正态分布的概率密度函数
在接近均值处,概率密度函数的值大;在远离均值处,概率密度函数的值小。正态贝叶斯分类器训练时根据训练样本估计每一类条件概率密度函数的均值与协方差矩阵。另外还需要计算协方差矩阵的行列式和逆矩阵。由于协方差矩阵是实对称矩阵,因此一定可以对角化,可以借助奇异值分解来计算行列式和逆矩阵。对协方差矩阵进行奇异值分解,有Σ=UWUT其中，W为对角阵,其对角元素为矩阵的特征值;U为正交矩阵,它的列为协方差矩阵的特征值对应的特征向量。计算Σ的逆矩阵可以借助该分解: (Σ)-1=(UWU-1)-1=UW-1U-1=UW-1UT对角矩阵的逆矩阵仍然为对角矩阵,逆矩阵主对角元素为矩阵主对角元素的倒数;正交矩阵的逆矩阵为其转置矩阵。根据上式可以很方便地计算出逆矩阵Σ-1;行列式|Σ|也很容易被算出,由于正交矩阵的行列式为1,因此,Σ的行列式等于矩阵W的行列式,而W的行列式又等于所有对角元素的乘积。
还有一个没有解决的问题是如何根据训练样本估计出正态分布的均值向量和协方差矩阵。通过优选似然估计和矩估计都可以得到正态分布的这两个参数。样本的均值向量就是均值向量的估计值,样本的协方差矩阵就是协方差矩阵的估计值。
下面给出正态贝叶斯分类器的训练算法。训练算法的核心为计算样本的均值向量、协方差矩阵，以及对协方差矩阵进行奇异值分解，具体流程如下。
(1) 计算每一类训练样本的均值μ和协方差矩阵Σ。
(2) 对协方差矩阵进行奇异值分解，得到U，然后计算所有特征值的逆，得到W－1，同时还计算出lnΣ。4.3.2预测算法 在预测时需要寻找具有优选条件概率的那个类,即优选化后验概率(Maximum A Posteriori, MAP),根据贝叶斯公式有arg maxc(p(c|x))=arg maxcp(c)p(x|c)p(x)假设每个类的概率p(c)相等,p(x)对于所有类都是相等的,因此,等价于求解该问题: arg maxc(p(x|c))也就是计算每个类的p(x|c)值,然后取优选的那个。对p(x|c)取对数,有ln(p(x|c))=ln1(2π)n2|Σ|12-12((x-μ)TΣ-1(x-μ))进一步简化为ln(p(x|c))=-n2ln(2π)-12ln (|Σ|)-12((x-μ)TΣ-1(x-μ))其中,-n2ln (2π)是常数,对所有类都是相同的。求上式的优选值等价于求下式的最小值: ln(|Σ|)+((x-μ)TΣ-1(x-μ))其中,ln (|Σ|)可以根据每一类的训练样本预先计算好,与x无关,不用重复计算。预测时只需要根据样本x计算(x-μ)Σ-1(x-μ)T的值,而Σ-1也是在训练时计算好的,不用重复计算。
下面考虑更特殊的情况,问题可以进一步简化。如果协方差矩阵为对角矩阵σ2I,上面的值可以写成ln(p(x|c))=-n2ln(2π)-2nlnσ-121σ2(x-μ)T(x-μ)其中:ln (|Σ|)=ln σ2n=2nln σ
Σ-1=1σ2I对于二分类问题,如果两个类的协方差矩阵相等,分类判别函数是线性函数: sgn(wTx+b)这和朴素贝叶斯分类器的情况是一样的。如果协方差矩阵是对角矩阵,则Σ-1同样是对角矩阵,上面的公式同样可以简化,这里不再详细讨论。
4.4实验程序
下面通过实验程序介绍贝叶斯分类器的使用。程序基于sklearn开源库，使用iris数据集。iris数据集包含3类鸢尾花的数据，分别为Setosa、Versicolour、Virginica，每类50个样本。样本包含4个属性，即特征向量的维数为4。这些特征分别是花萼长度（sepal length）、花萼宽度（sepal width）、花瓣长度（petal length）、花瓣宽度（petal width）。表4.1列出了此数据集中的部分样本数据，限于篇幅只显示了一部分。续表表4.1iris数据集中的部分样本
sepal lengthsepal width petal lengthpetal width类型5.13.51.40.2setosa4.93.01.40.2setosa4.73.21.30.2setosa7.03.24.71.4versicolor6.43.24.51.5versicolor6.93.14.91.5versicolor6.33.36.02.5virginica5.82.75.11.9virginica7.13.05.92.1virginica为了对样本数据进行可视化，只用了前两个特征分量。因此，特征向量是二维的，可以将平面内所有点的分类结果用图像直观地显示出来。
训练得到分类器模型之后，用整个图像平面上所有像素点的坐标作为测试样本的特征向量。将这些测试样本送入分类器预测，根据分类结果将像素显示成不同的颜色。另外还将训练样本用不同亮度值的圆显示出来。如不作特殊说明，后面各章的示例程序都使用这种做法。
在sklearn中正态朴素贝叶斯分类器由类GaussianNB实现，这是4.3.2节介绍的算法。分类器的训练函数为fit，传入参数为样本的特征向量集和样本标签值。训练成功后可以用模型进行预测，预测函数为predict，传入参数为样本特征向量，返回预测的类型。GaussianNB无须设置参数。
程序源代码可以通过下侧二维码获取。程序运行结果如图4.2所示。
NaiveBayes
图4.2朴素贝叶斯分类器对iris数据集的分类结果
图4.2中分类边界是曲线，这也说明正态贝叶斯分类器具有非线性分类的能力。
4.5应用
贝叶斯分类器是生成模型的典型代表,具有实现简单和计算量小的优点。在某些问题上有成功的应用,包括垃圾邮件分类问题［5］、自然语言处理中的文本分类问题［6］、智能视频监控中的背景建模算法［7］、人脸识别中的联合贝叶斯模型［8］。
贝叶斯框架在机器学习中的应用不仅有贝叶斯分类器,还有贝叶斯网络［3］［4］。贝叶斯网络可以实现各个变量之间的因果推理,是一种概率图模型,限于篇幅,在本书中不做详细介绍,感兴趣的读者可以阅读相关参考文献。其他一些应用（如语音识别、机器翻译等）中也使用了贝叶斯公式和优选化后验概率的思想,在第16章中将详细介绍。
参 考 文 献
［1］Chao K Chow. On Optimum Character Recognition System Using Decision Functions. IRE Transactions, 1957: 247？254.
［2］Rish Irina. An Empirical Study of The Naive Bayes Classifier. IJCAI Workshop on Empirical Methods in Artificial Intelligence, 2001.
［3］Nir Friedman, Dan Geiger, Moises Goldszmidt. Bayesian Network Classifiers.Machine Learning,1997.
［4］Wray L Buntine. A Guide to The Literature on Learning Probabilistic Networks from Data. IEEE Transactions on Knowledge and Data Engineering, 1996, 8(2): 195？210.
［5］Mehran Sahami, Susan T Dumais, David Heckerman, et al. A Bayesian Approach to Filtering Junk E？Mail, 1998.
［6］Yiming Yang, Xin Liu. A Re？Examination of Text Categorization Methods.International ACM Sigir Conference on Research and Development in Information Retrieval, 1999.
［7］Liyuan Li, Weimin Huang, Irene Y H Gu, et al. Foreground Object Detection from Videos Containing Complex Background. ACM Multimedia, 2003.
［8］Dong Chen, Xudong Cao, Liwei Wang, et al. Bayesian Face Revisited: A Joint Formulation. European Conference on Computer Vision, 2012.
