基于朴素贝叶斯与半朴素贝叶斯图像识别比较

刘 闯

(南京邮电大学 计算机学院、软件学院、网络空间安全学院，江苏 南京 210023)

0 引言

图像识别技术[1]指的是使用计算机对图像进行相应处理、分析以及理解，以此来识别出不同模式的目标和对象的一种技术。根据对图像的观测，对图像中的事物分辨其所属类别，做出清晰的判断。通过利用现代信息处理以及计算技术的方式，来模拟和完成人脑对于外物的认识以及理解的过程。一般来说，常见的图像识别系统主要由三个模块组成，分别是：图像切割、提取图像特征以及选择分类器。

贝叶斯分类算法[2]是统计学中一种常用的分类方法，其主要是利用概率论统计里的知识进行分类的算法。而基于条件独立性假设情况下的朴素贝叶斯分类器(Naive Bayes Classifier,NBC)有着坚实的数学基础以及相对稳定的对事物的分类效率。朴素贝叶斯分类算法在某些场景下可以与决策树算法以及神经网络分类算法相媲美，该算法也能够运用到大型数据库中，并且其拥有方法简单、分类准确率相对较高、执行速度快等优点。同时，NBC模型所需估计的参数相对较少，对某些缺失的数据不太敏感，从理论上来说，NBC模型与其他一些分类方法相比较而言，其具有最小的误差率。

本质上来说，图像识别同样是一个分类问题，通过使用朴素贝叶斯分类器将包含人体行为的图像进行识别分类,从而能够有效地识别出所测图像中的个体行为。而半朴素贝叶斯分类器(SEMI-NBC)[3]是在朴素贝叶斯分类器的基础之上对其的一种改进，由于朴素贝叶斯分类器对于属性条件独立性[4]进行了前提假设，但是在现实生活中，这类前提假设往往是难以成立的，因此人们尝试对这种前提假设进行一定程度上的放松，由此产生了半朴素贝叶斯分类器。半朴素贝叶斯分类器的基本设想是适当地考虑部分属性之间的相互依赖信息，从而既不需要计算其完全联合概率，又不至于完全忽略相对较强的属性之间的依赖关系，其中半朴素贝叶斯分类器最常用的一种思路是独依赖估计(One-Dependent Estimator)[5]。本文讨论了NBC和SEMI-NBC分类技术,将NBC和SEMI-NBC应用到图像识别上,对两种算法的准确率判定和执行时间进行比较。

1 朴素贝叶斯分类器NBC

朴素贝叶斯分类器是一类以贝叶斯定理与条件独立性假设为前提的分类方法，对于所给定的训练集，首先基于特征条件独立性的假设计算出输入/输出的联合概率分布，然后基于所得到的数据，对于所给定的输入数据x，再利用贝叶斯定理计算出后验概率为最大的输出y。朴素贝叶斯分类器实现起来相对简单，学习与预测出正确的结果的概率都很高。

设输入空间x∈Rn是n维向量的一个集合，输出空间是类标记集合y={c1,c2，…，ck}。输入是特征向量x∈x，输出为类标记y∈y。X是定义在输入空间x中的随机变量，Y是定义在输出空间y中的随机变量，其中P(X,Y)是X与Y的联合概率分布。

(1)

j=1,2,…,n;l=1,2,…,Sj;k=1,2,…,K

(2)

k=1,2,…，K

(3)

然后再根据公式确定输入x的类别：

(4)

但是当使用极大似然估计法时，可能会出现所需估计的概率值为0的情况，这时会影响到接下来后验概率的计算结果，从而使分类结果产生偏差，而解决这种情况的方法是采用贝叶斯估计，具体操作为：先计算条件概率的贝叶斯估计：

P(X(j)=ajl|Y=ck)=

(5)

其中，λ≥0，等价于在随机变量各个取值的频数上赋一个正数值λ≥0。当λ=0时就被称为极大似然估计。常取λ=1,这时这个等式称为拉普拉斯平滑，从而，对任何l=1,2,…,Sj;k=1,2,…,K,有:

Pλ(X(j)=ajl|Y=ck)>0

(6)

(7)

表明上式所计算的条件概率贝叶斯估计确实为一种概率分布。同样地，先验概率的贝叶斯估计调整为：

(8)

从而得到分类函数为：

(9)

最终将输入x分到后验概率最大的类y中，后验概率最大与0-1损失函数的期望风险最小化是相等价的。假设选择0-1损失函数：

(10)

式中f(X)是分类决策函数，此时，得到的期望风险函数为：

Rexp(f)=E[L(Y,f(x))]

(11)

其中期望是对联合分布函数P(X,Y)所取的，由此可以得出条件期望为：

(12)

为了最小化期望风险，只需要对X=x的值逐个极小化，由此得到：

(13)

因此，通过期望风险最小化准则转化也就得到了后验概率最大化的准则：

(14)

这就是朴素贝叶斯分类器所采用的基本原理[6]。

2 半朴素贝叶斯分类器SEMI-NBC

由于朴素贝叶斯分类器是基于属性条件独立性为前提的假设，然而，在现实生活中，这种假设往往是很难成立的，所以，人们试着对属性条件独立性这一假设进行某种程度上的放松，因此产生了半朴素贝叶斯分类器这一类型。

半朴素贝叶斯分类器的基本思路是，首先适当考虑部分属性之间的相互依赖关系，从而既不需要先计算完全的联合概率，也不会彻底忽视了较强的相关属性之间的依赖关系[7]。而独依赖估计是在半朴素贝叶斯分类器中的一种比较常用的策略，即首先假设在类别之外，每个属性最多仅依赖于另外一个其他属性，即：

(15)

其中，px(j)表示为属性x(j)所依赖的属性，为x(j)的父属性。接下来，对于每个属性x(j)，假如其父属性px(j)都是已知的，即可以求出相对应的概率值，那么，接下来的问题就是如何确定每一个属性的父属性，而采用不同的策略会产生不同的独依赖分类器，如图1所示。

图1 朴素贝叶斯与两种半朴素贝叶斯分类器属性依赖关系

其中，最直观的做法是首先假设所有的属性都通通依赖于同一个属性，这种做法称之为超父(Super-Parent)，接下来使用交叉验证等模型方法来确定其超父属性，这就是所谓的SPODE(Super-parent ODE)方法。而TAN(Tree Augments Naive Bayes)则是在最大带权生成树(Maximum Weighted Spanning Tree)算法的基础之上，通过下述步骤将不同属性之间的相互依赖关系构建成如图1所示的树形结构。

(1)计算任意两个属性节点之间的条件互信息[8]：

I(xi，xj|y)=

(16)

(2)把属性作为节点构建完全图，任意两个节点间的权重设为I(xi,xj|y)；

(3)以所构建的完全图构建最大带权生成树，然后挑选根变量，将边置为有向；

(4)加入分类节点y，增加从y节点到每个属性节点间的有向边。

由上述表明，条件互信息I(xi,xj|y)这一定义刻画了在已知类别情况下的属性xi和xj间的相关性，所以，通过最大生成树这一算法，TAN产生的结果是留下了强相关性属性间的相互依赖性。本文采用SPODE方法作为此半朴素贝叶斯分类器核心思想[9]。

3 图像识别方法流程

使用NBC的图像识别方法与使用其他机器学习方法流程基本上是一样的，它们都是利用对训练数据先进行学习得到其分类模型,再利用所得到的分类模型来对待分类的数据进行判断。不同的是,某些分类器所输出的结果是一个数值,比如决策树、SVM等。而有些分类算法输出的结果是一个概率值,比如朴素贝叶斯(NBC)、神经网络(NN)等。不管是哪种分类器都可以将数据进行分类。本文将利用朴素贝叶斯对图像中的人体行为进行四分类识别,即输出值是{0，1，2，3}。基于NBC与SEMI-NBC的图像识别方法如图2所示。

图2 基于NBC与SEMI-NBC的图像识别

在此方法中，首先对获取的图像进行预处理，包括将图像数值化、特征选择提取等。数据特征选择的目的是为了降低维数,有利于提高计算效率。

常见的模式识别[10]流程主要包含样本采集、数据预处理、特征选择与提取、特征变换与分类器。而实验样本采用了KTH activity数据库的图像，该数据库包含6个动作，分别为走、慢跑、挥手、打拳、拍手、快跑，每个动作有25个样本。本文选取其中四组动作，对每种动作视频中截取25张图片关键帧，共100张图像作为样本训练集，另外再截取50张图像作为样本测试集。

4 图像预处理与特征提取

首先截取每个视频样本中的一些关键帧图像，然后对图像做高斯模糊、灰度化、二值化、闭操作等处理后，再使用直方统计函数对图像进行特征提取。最后再使用朴素贝叶斯算法与半朴素贝叶斯算法作为分类器进行分类比较。对图片进行高斯模糊处理后，会使得图片变得模糊，目的是去除与图像识别不相关的干扰噪声，为接下来的Sobel算子图像处理步骤做准备。接着再对图像进行灰度化处理、二值化处理，以及对图像进行闭操作，取其最小外接矩形，最后获取仅包含人体动作行为的最小矩形块图像。

特征提取的目的是为了提取出对分类预测有帮助的信息，并且忽略不重要的信息与噪声。而数据特征选择能够有效提高数据的测试效率,若直接采用图像所有的像素点作为输入特征值，则会导致特征属性过大，从而不利于对信息的筛选与模型的预测。直方统计函数是图像特征提取的一种重要统计方式，其可以近似被认为是图像灰度密度函数。当图片的对比度较小时，其灰度直方图特征只在灰度轴上较小的一小段区域上为非零值，而相对较暗的图片因为其像素灰度值低的区域较大，所以它的直方图的主体特征出现在低值的灰度区间上，在高值灰度区间上，其幅度较小或者为零，这反映出图片像素矩阵中行与列之间的相关性和图像之间的特点。通过上述所做的预处理获取30×20像素的人体图像，将图像二值化后，统计每一行以及每一列中元素为1的数目，构成属性维度为50的特征向量，即为所需要的特征数据。

5 实验结果和分析

本实验采用Spyder作为编程环境，实验数据来自KTH数据库，通过随机选取的四组动作(走、跑、拳击、挥手)视频样本，从各视频中进行每隔5帧图片提取取样。每个视频样本选取25张图像，共获取100张图片作为训练数据。再另取四组动作图像共50张图像作为测试数据。

本实验对于四种动作进行了预测判断识别，实验中先通过对图像作高斯模糊、灰度化、二值化、闭操作等前期处理，从而将图像数据转化为一组向量数据，再分别利用朴素贝叶斯分类器与半朴素贝叶斯分类器对这包含四组动作的图片进行预测，计算其分类识别率。实验结果如表1所示。通过对比发现，采用半朴素贝叶斯分类器的准确率更高，而相对地其花费的时间也更多。究其原因，主要缘由是朴素贝叶斯分类器是以属性条件独立性假设作为前提条件，而这个假设在现实生活中很难成立，因条件过于苛刻，从而导致识别率较低，而半朴素贝叶斯分类器在一定程度上对这一条件进行松动，增加属性之间的依赖性，虽然增加了计算的复杂度，但也使得识别率有所提高。

表1 两种分类器的性能比较

6 结束语

朴素贝叶斯分类器是以属性条件独立性假设作为前提条件，而这个假设在现实生活中其实往往难以成立，但奇妙的是，在很多情况下朴素贝叶斯分类器都能够获取相当好的性能。而半朴素贝叶斯分类器是以对属性之间的部分依赖关系作出各种假设和约束来进行建模的。利用弱化条件独立性这一假设来提高朴素贝叶斯分类器预测的准确性。如果训练数据足够充分，且选择合适的父属性，其算法的泛化性能则会提升，但其缺点同样很明显，在有限的样本条件下，往往会导致其计算时间的开销过大。如何挑选能够使分类器产生较好的泛化性的属性作为父属性，是目前研究的重点。

虽然朴素贝叶斯分类器在很多情况下都能获得相当好的性能，但其应用的场景更多的是在信息检索领域以及文本分类领域。在图像识别方面受限于数据的特征维度以及特征值间的复杂依赖关系，而得不到很准确的识别效果。目前图像识别主流更多采用深度学习方法，并且能获得很好的识别率。