朴素贝叶斯分类器的改进

摘要：朴素贝叶斯分类器是一种简单而高效的分类器，但是它的属性独立性假设使其无法表示现实世界属性之间的依赖关系，以及它的被动学习策略，影响了它的分类性能。本文从不同的角度出发，讨论并分析了三种改进朴素贝叶斯分类性能的方法。为进一步的研究打下坚实的基础。

关键词：朴素贝叶斯；主动学习；贝叶斯网络分类器；训练样本；树增广朴素贝叶斯

1 问题描述

随着计算机与信息技术的发展，人类获取的知识和能够及时处理的数据之间的差距在加大，从而导致了一个尴尬的境地，即“丰富的数据”和“贫乏的知识”并存。在数据挖掘技术中，分类技术能对大量的数据进行分析、学习，并建立相应问题领域中的分类模型。分类技术解决问题的关键是构造分类器。分类器是一个能自动将未知文档标定为某类的函数。通过训练集训练以后，能将待分类的文档分到预先定义的目录中。常用的分类器的构造方法有决策树、朴素贝叶斯、支持向量机、k近邻、神经网络等多种分类法，在各种分类法中基于概率的贝叶斯分类法比较简单，在分类技术中得到了广泛的应用。在众多的分类器的构造方法与理论中，朴素贝叶斯分类器(Naive

Bayesian Classifiers)[1]由于计算高效、精确度高。并具有坚实的理论基础而得到了广泛的应用。文献朴素贝叶斯的原理、研究成果进行了具体的阐述。文章首先介绍了朴素贝叶斯分类器，在此基础上分析所存在的问题。并从三个不同的角度对朴素贝叶斯加以改进。

2 研究现状

朴素贝叶斯分类器（Naïve Bayesian Classifier）是一种基于Bayes理论的简单分类方法，它在很多领域都表现出优秀的性能[1][2]。朴素贝叶斯分类器的“朴素”指的是它的条件独立性假设，虽然在某些不满足独立性假设的情况下其仍然可能获得较好的结果[3]，但是大量研究表明此时可以通过各种方法来提高朴素贝叶斯分类器的性能。改进朴素贝叶斯分类器的方式主要有两种：一种是放弃条件独立性假设，在NBC的基础上增加属性间可能存在的依赖关系；另一种是重新构建样本属性集，以新的属性组（不包括类别属性）代替原来的属性组，期望在新的属性间存在较好的条件独立关系。

目前对于第一种改进方法研究得较多[2][4][5]。这些算法一般都是在分类精度和算法复杂度之间进行折衷考虑，限制在一定的范围内而不是在所有属性构成的完全网中搜索条件依赖关系。虽然如此，寻找条件依赖关系依然需要较复杂的算法。而通过重新构建样本属性集的方式则可以避免寻找条件依赖关系，保持朴素贝叶斯分类器的简单和直观。事实上，属性构造方法一直是机器学习领域中重要的方法之一，在决策树、规则学习、神经网络等方面得到了有效应用[6][7]。Pazzani提出了一种构建NBC的方法：BSEJ算法，该算法是基于原有属性的笛卡儿积来构建新的属性。

3 算法原理

3.1朴素贝叶斯分类器

朴素贝叶斯分类器假定特征向量的各分量间相对于决策变量是相对独立的，并使用概率规则来

实现学习或某种推理过程，即将学习或推理的结果表示为随机变量的概率分布。这可以解释为对不同可能性的信任程度。它的出发点就是贝叶斯定理和贝叶斯假设[3]。

假定随机向量x，Θ的联合分布密度是p(x，Θ)，它们的 边际密度分别为p(x)，p(Θ)。一般情况下设X是观测向量。Θ是未知参数向量，通过观测向量获得未知参数向量的估计。贝叶斯定理记作：

从上式可以得知，对未知向量的估计综合了它的先验信息和样本信息，这正是贝叶斯增量学习模型的基础。可简单地理解为：后验知识(I1)=先验知识(I0)+样本信息(s)。当新的样本到来时，上面的后验知识变为先验知识，因 此它是一个利用样本知识来修正当前知识的连续的动态的过程 。

朴素贝叶斯分类器将每个训练样本数据分解成一个n维特征向量x和决策类别变量c，并假定特征向量的各分量间相对于决策变量是相对独立的。

设特征向量X={xl，x2，…，xn}表示数据个属性(Al，A2，…，An)的具体取值，类别变量C有m个不同的取值Cl，C2，…，Cm，即有m个不同的类别。则：

由贝叶斯定理知x属于Ck的后验概率为：

朴素贝叶斯分类器将未知类别的决策变量X归属于类别当且仅当：

由于P(X)对于所有类别均是相同的，因此： 3 / 7

由于类别的事前概率是未知的，因此，可以假设各类别出现的概率相同，P(C1)= P(C2)= …=

P(Cm)。这样求公式(2)的最大转换为求P(X|CK)最大，否则就要求P(X|CK)P(CK)得最大。可以通过训练样本数据集合估计P(Xi|CK) (1≤i≤n，1≤k≤m)：

其中，Sk为训练样本数据集合 中类别为的样本个数，为整个训练样本数据集合的容量。为训练样本数据集合中类别为且属性A，的取值为Xi的样本个数。

4 算法实现

4.1从属性变量间的关系来改进朴素贝叶斯分类器

朴素贝叶斯分类器关于变量独立性的假设虽然大大减少了参数量，但在现实生活中，这种独立性假设经常是不满足的。经过分析得知，朴素贝叶斯分类器的本质是一种具有很强限制条件的贝叶斯网络分类器，但是它限制条件太强。不适于现实应用；然而，完全无限制的贝叶斯网络也是不现实的，因为学习这样的网络非常耗时，其时间复杂度为属性变量的指数级，并且空间复杂度也很高。因此，可以从属性变量间的关系来改进朴素贝叶斯分类器，研究具有较宽松条件限制的贝叶斯网络分类器。

4.1.1 属性分组

适用于属性可以分为独立的子集合的情况。

Kononerko提出一种采用穷尽搜索的属性分组技术，假定同一组内的属性之间可能是相互依赖

的，但组与组之间是满足独立性假设的属性集合。也就是说，独立性假设弱化为这些属性组之间的独立性。但是，这种算法的复杂性要远远高于朴素贝叶斯分类器，而且在现实世界中，属性可以完全被分成独立的子集合只是少数情况。

4.1.2 树增广的朴素贝叶斯分类器TAN

这种结构允许各属性节点之间构成一树形结构，即若去掉根结点到各属性节点之间的有向弧，各属性节点之间形成树形结构(如图1)。学习该模型结构的典型方法是以条件互信息为评分函数的网络结构学习算法，学习TAN的一般过程可描述为：

图1 TAN模型

(1)计算各属性节点间的条件互信息；

(2)以属性变量为节点，以条件互信息为节点之间的连接权，构造无向完全图；

(3)生成最大权张树；

(4)转换无向的最大权张树为有向树；

(5)从类别变量向各属性节点引一条有向边，生成TAN模型。

这种方法可以增强朴素贝叶斯分类器的表达能力，但计算量明显变大。

4.2朴素贝叶斯分类器的提升

提升方法[2](Boosting)总的思想是学习一系列分类器，在这个序列中每一个分类器对它前一个

分类器导致的错误分类例子给予更大的重视。尤其是，在学习完分类器 Hk之后，增加了Hk导致分类错误的训练例子的权值。并且通过重新对训练例子计算权值，再学习下一个分类器Hk+ 1。这个过程重复T次。最终的分类器从这一系列的分类器中综合得出。在这个过程中，每个训练例子被赋予一个相应的权值，如 果一个训练例子被分类器错误分类，那么就相应增加该例子的权重，使得在下一次的学习中，分类器对该例代表的情况更重视。对多类分类问题的提升方法如下：

对多类分类问题的提升方法如下：

Input：N个训练实例：<(X 1，y1)，…，(X N，yN)

N个训练实例上分布D：W，W，为训练实例的权向量。

T为训练重复的趟数。

(1)Initialize；

(2)初始化训练实例 的权向量。

Wi=1/N，i=1, …，N

(3)for t=l to T

(4)给定权值Wit得到一个假设：H(t)：X一>Y

(5)估计假设H(t)的总体误差， 5 / 7

(6)计算

(7)计算下一轮样本的权值

(8)正规化W（it+1），使其总和为1

(9)End for

(10)Output

(11)

这里I(Θ)=1，如果Θ=T；否则，I(Θ)=0。

提升方法可以保证训练集的差错率维持在较低的水平上，并可进一步提高分类精度；但当训练集的噪音很多时，这种提升效果不大。

4.3基于主动学习的朴素贝叶斯分类器

按照分类学习对训练样本的处理方式，可将分类模型分为两类：被动分类模型和主动分类模型[5]。被动学习也称为“从样本中学习”，它随机地选择训练样本被动地接受这些样本的信息。如图2。 它对于具有严格序关系的训练样本来说是必要的。也是不可改变的。然而绝大部分分类学习中都认 为训练样本是独立分布的，这种被动的学习显示出明显的不足：(1)有顺序地处理训练样本往往会使学习的分类器具有顺序相关性，对数据过分敏感；(2)遇到噪音样本时会使这种噪音一直传播下去，影响分类精度；(3)缺乏综合未带标注样本信息的能力。在学习分类模型中，未带类别标注的样本往往包含有助于分类的信息。在这种情况下，选择好的未带类别标注的样本，把它加入到当前的分类器中是相当重要的。主动分类模型对训练样本的选择是主动的。它首先选择最有利于分类器性能的样本来训练分类器。属于更高层次的、具有潜意识的学习，如图3。主动学习分类模型在较难获得标注样本或者获得标注样本的费用较高时。其优越性特别明显。

图2 被动学习模式 6 / 7

图3 主动学习模式

在这里，我们可以结合主动学习的思想，来学习朴素贝叶斯分类器。基本模型如图 4。

图4 主动贝叶斯分类器模型

首先，主动贝叶斯模型利用标注数据。获得一个初始分类模型。由于我们的学习算法是在大量的未标注样本下进行的，为了加快算法效率，在主动选择训练实例时，我们从这些样本中选出一部分。放入数据池中。只在数据池中选择新的训练实例。为避免朴素贝叶斯模型在学习过程中，出现某个类别的概率趋近于1或0。我们采用随机抽样的方法，从未标注样本中选择数据。主动选择算子 (Active Selector)根据一定的选择策略从数据池中选择出训练样本，并用当前的分类模型，进行类别标注。这个部分是系统的关键部分。它的任务有三个：

(1)用当前的分类器对数据池中的每个未标注样本进行评价。并选出最优的训练样本集。回收剩余的样本到未标注样本集：

(2)对最优训练集中的每个样本用当前的分类模型进行类别标注；

(3)使用加上类别标注的最优训练样本集中的数据重新修正分类器的参数。

直观上看，上述模型的实现是相当复杂的一个过程，它需要反复地对样本进行分类和修正分类器参数。然而由于朴素贝叶斯模型所具有的一些特性，可以使计算的复杂性大大降低。

我们选用Delicious中的数据来进行测试，首先随机取出10个样本作为训练集。记作A，然后将数据分成两个不相交的子集B(2000)和c(1196)，括号内数字为该集合所含的样本个数。试验结果如下：

从试验结果可以看出：对相同的训练集、测试集而言，基于主动学习的朴素贝叶斯的分类精度明显优于朴素贝叶斯分类器。

5 实验结果

训练集 测试集 朴素贝叶斯分类器 基于主动学习的朴素贝