关系学习中贝叶斯分类算法的比较研究

王 晶，张春英

（河北理工大学 理学院，河北 唐山063009）

0 引言

数据挖掘算法是在数据中寻找一种模式。现存的大多数数据挖掘方法都是在单一的表中寻找模式。而一个关系数据库一般由几个表组成，而不是一个表。近几年，数据挖掘的算法和模式已经扩展到多关系方面，而多关系学习（MRDM，MRL）方法也称为关系学习，是从关系数据库中寻找涉及多表（多关系）的模式。

分类是数据挖掘的一种主要的应用形式，其应用遍历机器学习、模式识别、统计学、神经网络、遗传算法、数据库、专家系统等多个领域。分类算法的核心部分是构造分类器。贝叶斯分类算法是数据挖掘领域的一种常用的分类方法，它是统计学分类方法，利用概率进行分类。

目前，在关系学习中，贝叶斯分类算法有很多种，对这些算法进行总结、比较，指出其优点与不足，对提高分类效率有很大帮助。故本文对已有的关系学习中贝叶斯分类算法作了详细的比较，并进行归纳总结。本文第三部分是对单关系学习中贝叶斯分类算法的比较；第四部分是对多关系学习中贝叶斯分类算法的比较；最后是对本文工作的总结与展望。

1 贝叶斯分类算法基本思想

给定一个具有K个属性的数据集，假设这K个属性值均为离散值，分类任务是预测测试集中每一个例子的类别。给定一个具体的例子，其属性值从ai到ak，该例子属于某一个类ci的概率是P(C=ci| A1=a1…

Ak=ak)。显然如果该例子属于某一个类的概率值具有最大值，那么该例子就属于这个类。根据贝叶斯定理

其中，P(C=ci)被称为先验概率，可以从训练数据集中计算得到。P(A1=a1,…, L,…, Ak=ak)与任何的 Ci都无关，也容易计算。求P(A1=a1…, L,…, Ak=ak| C=ci)。

如果属性值是独立的，则

将（2）式带入（1）式中，可得到朴素贝叶斯分类器所使用的方法[1]，即

其中，VNB表示朴素贝叶斯分类器输出的目标值。理论上讲，朴素贝叶斯分类与其他所有分类算法相比，具有最小的误分类率[2]。

2 单关系学习中贝叶斯分类算法比较

朴素贝叶斯方法就是以概率密度函数为基础，描述分类系统中条件属性和分类属性之间的映射关系，从理论上讲，与其它所有分类算法相比，具有出错率最小的特点，因而具有广泛的应用前景。但是贝叶斯方法有其自身的限制：一是先验概率定义困难；二是实际问题中条件属性的独立假设一般不成立，针对贝叶斯分类方法在实际应用中的约束和限制，许多研究者提出结合粗糙集与贝叶斯方法进行分类知识挖掘的解决方案和实际方法[3-7]。

2.1 基于粗集属性约简的朴素贝叶斯分类算法

郑建军等人于 2003年提出一种基于粗糙集的贝叶斯分类器算法，该算法在基于粗集属性约简方法的基础上，综合考虑条件属性和决策属性间的依赖性以及条件属性间的依赖性对约简的影响。通过基于依赖性的属性约简，改善属性变量间的独立性限制，发挥贝叶斯分类器的鲁棒性，优化贝叶斯分类器的性能。此方法解决了威胁度估计等C3I系统汇总的问题，效果良好。但是，此方法仅适用于完备数据的情况下。

在现实生活中，往往数据是不完备的。2006年，胡学刚等人也是利用属性的依赖性，提出了不完备信息系统中基于粗集的贝叶斯分类算法。该文给出了粗集的相似关系，利用基于粗糙集理论的不完备数据分析方法，调用ROUSTIDA算法，对空置属性做出处理，然后再通过属性约简，改善属性间的依赖关系，找到一组最近似独立的属性约简结果，最后利用贝叶斯方法对约简后的数据集进行训练得到分类器，达到理想的分类效果，提高了分类的正确率。

在单关系学习中，大多数学者通过引入粗集中属性依赖性这一特殊性质，改善了贝叶斯方法中属性独立的限制，扩大了贝叶斯分类器的应用范围。

2.2 加权朴素贝叶斯分类算法

朴素贝叶斯算法是一种简单而有效的分类算法，但是它的属性独立性假设一般在现实问题中不能成立，这在某种程度上影响了它的分类能力。一般并不是所有的属性对分类都是有用的，有的影响大，有的影响小一些。基于此，又有很多学者提出将各种特征加权算法与朴素贝叶斯算法相结合，给不同的属性赋不同的权值，使朴素贝叶斯得以扩展。下面给出几种典型的加权朴素贝叶斯分类算法的模型、权值确定方法、优缺点以及进一步的工作方向进行了详细的比较。其中，基于属性频率的加权朴素贝叶斯分类算法是本文提出的一种算法。

表1 几种不同的加权朴素贝叶斯算法的比较

3 多关系学习中贝叶斯分类算法比较

在现实生活中，海量数据越来越多，在单表框架下进行分类已不能满足人们的需求。多关系分类已成为数据挖掘领域中的研究和应用热点。多关系数据挖掘要从多个表中直接挖掘信息和发现知识，而不是将数据库中的多个表合并成一个表再进行挖掘。

基于此种情况，文[12]中就提出一种高效准确的多关系朴素贝叶斯分类算法—Graph-NB（语义关系图）。它通过引入语义关系图，对表进行裁剪（cutting off），达到优化语义关系图，从而一定程度上消除无关表对分类影响的目的，以提高分类准确率。但是，这种方法也有其自身的不足。对于朴素贝叶斯而言，参与分类的基本单位是属性而不是表，因此，直接删除语义关系较弱的表显然是不合适的。这样做，很容易导致信息的丢失。

徐光美等人在2008年4月扩展了语义关系图的定义[13]，针对现有多关系朴素贝叶斯分类器中存在的统计偏斜问题，给出了一种新的统计计数方法，为高效进行关系表连接，采用元组 ID号传播方法对关系表进行虚拟连接，为进一步提高分类准确率，使用扩展的互信息标准进行属性剪枝。实验显示此种分类器具有良好的分类能力。但是，在多关系情况下，每个关系同目标关系间的相关程度是不同的。此后，作者在文[14]中，基于上述问题，为每张表制定了一个权值w，它表示此表与目标表间的相关程度，一般由领域专家指定，w取值范围为[0，1]。

相对而言，对多关系朴素贝叶斯分类算法的研究，广度和深度都不是很大，很多是基于语义关系图、互信息或是通过空间分类创建决策树[15]的。因此，这方面需要进一步的工作。

4 结论与展望

本文是围绕贝叶斯分类方法展开，最主要的工作是对单关系和多关系情况下，几种改进的贝叶斯分类算法的简单综述，表明贝叶斯分类方法在数据分类方面的重要性。在单关系下，将粗集和贝叶斯分类算法相结合得到的新的贝叶斯分类算法已相当成熟和有效。但在多关系下，基于粗糙集理论的多关系朴素贝叶斯分类器的研究还不是很多。对多关系朴素贝叶斯分类器进行扩展，融合粗糙集理论，用以进行数据的预处理，属性约简，属性重要性度量，表关系权重计算等，构建一种基于粗糙集理论的多关系朴素贝叶斯分类算法，仍是今后工作的方向。

[1] Han Jianwei. Data m ining concepts and techniques [M]. 北京：机械工业出版社.2001

[2] 秦锋，任诗流，程泽凯，罗慧. 基于属性加权的朴素贝叶斯分类算法[J].计算机工程与应用.2008

[3] 闫德勤. 对Bayesian粗糙集模型的讨论[J].计算机科学.2006.

[4] 杨帆，张彩丽.基于粗集的朴素贝叶斯分类算法及其应用[J].计算机工程与应用.2007.

[5] 胡学刚，郭亚光. 一种基于粗糙集的朴素贝叶斯分类算法[J].合肥工业大学学报.2006.

[6] 郑建军，刘炜，刘玉树，王蕾. 基于粗集的贝叶斯分类器算法[J].北京理工大学学报. 2003.

[7] 李勃，王艳兵，姚青. 基于粗糙集分类算法研究与实现[J].计算机工程与应用.2008.

[8] 孙成敏，刘大有，孙舒杨. 粗集和多关系学习综述[J].吉林：计算机科学.2007.

[9] 钱晓东. 数据挖掘中分类方法综述[J]. 图书情报工作2007,51(3).

[10] 王国胤. Rough集理论与知识获取 [M].西安：西安交通大学出版社.2003

[11] 刘清. Rough集及Rough推理 [M].北京：科学出版社.2001

[12] 刘红岩，陈海亮. Graph-NB:一种高效准确的多关系朴素贝叶斯分类算法[J].信息系统学报.2008.

[13] 徐光美，杨炳儒，秦奕青. 一种新的多关系朴素贝叶斯分类器[J].系统工程与电子技术.2008.4

[14] 徐光美，杨炳儒，秦奕青，张伟. 基于互信息的多关系朴素贝叶斯分类器[J].北京科技大学学报.2008.8

[15] 刘伟辉，王丽珍. 基于多关系的空间分类算法研究[J].云南大学学报.2006，28（S1）:158-163

[16] 安利平. 粗糙集理论的方法与应用研究[J]天津大学学报.2001

[17] 邓维斌，王国胤，王燕. 基于Rough Set 的加权朴素贝叶斯分类算法[J].计算机科学.2007

[18] 程克非，张聪. 基于特征加权的朴素贝叶斯分类器[J].计算机仿真.2006.10

[19] 张明卫等. 基于相关系数的加权朴素贝叶斯分类算法[J].东北大学学报.2008

[20] Paw lak Z.Rough Sets. Journal of Computer Science, 1982, 11(5):341-356

[21] Paw lak Z.Rough Sets [M].London: Kluwer academ ic publishers, 1991.10