当前位置:文档之家› 三种典型贝叶斯分类器的研究

三种典型贝叶斯分类器的研究


图2
TAN得到的网络结构
”在不同根结点情况下的分类准确度。图 4 给出了设置不同根结 点情况下 TAN 方法学习的贝叶斯网络结构。
-4-
中国科技论文在线
表4 数据集 Car 数据集 Car root=1 最大 95.19 最大 95.56 最小 92.24 root=4 最小 91.13
图 1 至图 3 列出了用这三种算法设计的分类器对“Tic-Tac-Toe”数据集进行分类得出的不 同贝叶斯分类器网络结构,结构图均是由 graphhviz 图形可视化软件包画出。
10
1
2
3
图1
4
5
6
7
8
9
NBC 得到的网络结构
2 4 3 5 6 1 8 7 10 9
10 1 6 3 4 9 2 5 8 7
3.3 贝叶斯网络分类器
贝叶斯网络分类器(bayesian network classifier,BNC),放弃了朴素贝叶斯分类器的条 件独立性假设, 所以最能与领域数据相吻合。 在贝叶斯网络的结构中类结点地位同其他属性
-2-
中国科技论文在线
法采用 K2 搜索算法和 BIC 评分函数。贝叶斯网络分类方法如下: 1)输入:训练集 D;变量顺序 ;变量父结点个数上界 u ; 2)K2 算法构造 BNC: a、所有结点组成无向图;
2 贝叶斯网络
贝叶斯网络是结合了图形表示方法和概率知识的有向非循环图。 在这个网络中, 节点表 示变量,有向边表示变量间的依赖关系,每个节点都有一个条件概率表,定量描述所有父节 点对于该节点的作用效果[4]。在数据挖掘中,贝叶斯网络可以用来处理不完整的带有噪声的 数据集,它用概率测度的权重来描述数据间的相互关系,语义清晰、可理解性强,这有助于 利用数据间的因果关系进行预测分析。 贝叶斯分类方法的核心是构造应用于分类的贝叶斯网络。 贝叶斯分类方法以概率统计方 法为基础,分类的主要思想是:在给定待分实例的条件下计算类别的后验概率,选择后验概 率最大的类别作为该样本的类别。
中国科技论文在线

三种典型贝叶斯分类器的研究
仝瑶瑶
中国矿业大学信息与电气工程学院, 江苏徐州(221116)
E-mail: lcxtynf@
摘 要: 贝叶斯分类方法是数据挖掘中一种重要的分类算法。 在贝叶斯家族中有三种典型的 贝叶斯分类器:朴素贝叶斯分类器、TAN 贝叶斯分类器和贝叶斯网络分类器。本文主要研 究了 TAN 分类器中根结点的设置对分类影响,以及将这三种典型贝叶斯分类器应用到 5 个 典型 UCI 数据集上,分析比较它们对不同类型和规模数据集的分类情况,总结这三种分类 器的适用范围。 关键词:朴素贝叶斯分类器;TAN 贝叶斯分类器;贝叶斯网络分类器;根结点;UCI
3 三种典型贝叶斯分类器
3.1 朴素贝叶斯分类器
朴素贝叶斯分类器(naive bayesian classifier,NBC)以简单的结构和良好的性能受到人 朴素贝叶斯分类器建立在一个类条件独立性假设(朴 们的关注, 它是最优秀的分类器之一[5]。 素假设)基础之上:给定类结点(变量)后,各属性结点(变量)之间相互独立[5]。朴素贝叶斯分 类器可以看作是贝叶斯网络的一种最简化的模型。 根据朴素贝叶斯的类条件独立假设, 则有:
I ( X i , X j / C)
xi , x j , c
P( x , x , c) log P( x / c) P( x
i j i
P( xi , x j / c)
j
/ c)
(3)
其中, xi 和 x j 分别是 X i , X j 的所有取值的一种组合。 b、以结点对 X i , X j 的条件互信息作为树中边 ( X i , X j ) 的权值,然后建立最大权重跨 度树。方法是:首先把边按权重由大到小排序,之后遵照选择的边不能构成回路的原则,按 照边的权重由大到小的顺序选择边, 这样由所选择的边构成的树便是最大权重跨度树, 最终 确定树中边的方向[8]; c、增加类结点到所有属性结点的有向边; d、使用最大似然方法或贝叶斯方法学习参数并输出 TAN 分类器。
-3-
中国科技论文在线
数据集 Iris Balan Tic Car Chess NBC (%) 最大 100 92.00 77.36 87.06 88.73 最小 92.00 74.00 66.98 82.81 87.14 平均 96.70 82.80 70.36 84.48 87.78 表 2 分类器分类准确度 TAN (%) 最大 100 72.00 77.99 95.93 89.11 最小 94.00 52.00 72.96 91.87 86.38 平均 97.90 62.50 75.96 93.98 87.73 最大 100 90.00 73.90 88.54 92.58
-5-
中国科技论文在线

由实验结果可以得出,用 Matlab 语言设计的朴素贝叶斯分类器、树扩展朴素贝叶斯分 类器、 贝叶斯网络分类器均是有效的, 都能完成分类的任务且对大部分数据集分类的正确率 都能保持在较高的水平上。 这三种构造分类器的方法充分利用了贝叶斯定理和贝叶斯网络的 知识, 并结合给出的训练样本知识构造出分类器。 下面主要从分类准确度和分类耗时这两个 方面分析比较这三种分类器[10,11]。 (1)朴素贝叶斯分类器。从分类准确度上看,NBC 虽然结构简单但是它的分类准确度 并不低。从分类耗时看,NBC 普遍比其它两种分类器花费的时间少,这与它不需要结构学 习,计算复杂度低是密切相关的。NBC 在现实中有着广泛的适应性,这主要还因为在大部 分领域中属性之间的依赖关系要明显低于属性和类别之间的依赖关系,所以 NBC 的条件独 立性假设是具有一定的现实意义的。 (2)基于 BIC 测度的 TAN 分类器是所有 NBC 改进分类器中效果最好的一个。从实验 中可以看到,TAN 分类器的分类准确度普遍高于 NBC,TAN 分类器放松了条件独立性假设 这是同现实世界相符合的,当属性之间关联性越大时,TAN 分类器的效果就越好,如“Car” 数据集。TAN 分类器中需要设置根节点,根节点就是选择除去类节点以外的属性节点作为 其它属性节点的根节点。在 TAN 试验的过程中,发现根节点的设置对分类准确度并没有很 大的影响,对于数据集“Car”的设置六个不同根节点结果相差不大。从分类时间上看,TAN 分类器在这三种分类器中是花费时间最长的。 (3)理论上 BNC 分类器应该有最好的分类效果,但是实验结果表明,BNC 的分类效 果并不理想,这主要与两个因素有关,一是数据集的规模,BNC 对大样本的“Chess”数据集 有较好的分类效果,在小规模数据集情况下就不如 NBC 和 TAN;二是在使用 K2 算法进行 结构学习的过程中有一个重要的参数 , 用来确定结点变量的次序,它对先验知识的依 赖性很大。 在不了解相关的领域或没有专家的指导的情况下, 确定变量的次序就变得相当困 难,变量次序的所有状态数是 n ! 。从分类耗时上看,BNC 分类器的分类耗时比 NBC 要长, 同 TAN 比较有一定的不确定性,根据这五个实验看它普遍要比 TAN 分类时间短。 从实验可以看出, 这三种分类器并不是对每种数据集都有好的分类效果, 因此在对数据 集选择分类器的时候还需要具体情况具体对待, 主要考查属性之间的关联性、 数据的规模和 时间限制等方面。数据集属性相关性小的时候选择 NBC 有较好的分类效果,数据集属性相 关性大时候选择 TAN 分类器。在数据集规模较大且具有一定先验知识时选择贝叶斯网络分 类器。
1 引言
近年来,随着网络的高速发展,各个领域的数据量急剧增加,分类成为数据挖掘中一项 重要的任务,一直受到人们的重视。在众多的分类方法中,贝叶斯分类方法以其丰富的概率 表达能力, 不确定知识表达形式和增和先验知识的增量特性, 已经成为最引人注目的分类方 法之一[1]。 1973 年,Duda 和 Hart 提出了朴素贝叶斯分类器[2]。它具有强限制条件,与现实情况不 相符合, 为此, 一些学者们相继提出了各种改进朴素贝叶斯分类器的方法。 1997 年, Fridman 提出了改进的朴素贝叶斯分类器:TAN 贝叶斯分类器[3]。它通过放松条件独立性假设,构造 最大权生成树从而改进朴素贝叶斯分类器。 贝叶斯网络分类器是目前学者研究最广泛的分类 方法,它可以更自然地表示属性间的依赖关系,前两种可以看作特殊的贝叶斯网络分类器。 本文分别对这三种典型贝叶斯网络分类器进行了研究,通过对 UCI 上的五类数据集分类, 分析比较这三种分类器的特点和它们的适用范围。

BNC (%) 最小 92.00 76.00 63.84 81.33 90.50 平均 95.80 81.79 70.12 84.44 91.52
表 3 分类器分类耗时 数据集 Iris Balan Tic Car Chess NBC (s) 1.82 1.80 8.19 8.70 85.6 TAN (s) 2.90 2.32 9.80 10.90 105 BNC (s) 4.30 2.26 6.84 9.45 73.4
P(ci / x )
P(ci ) P( x / ci ) P( x)
(1)
其 中 , X { X 1 , X 2 , , X n } 是 属 性 变 量 集 , x {x1 , x2 , xn } 用 来 描 述 对 n 个 属 性 结 点
X 1 , X 2 , X n 的 n 个度量, xi ( i 1, 2, , n )表示属性 X i 的取值。 C 表示类结点, ci 表 示类结点 C 的取值。 P ( x) 对于所有的类为常数, P(ci ) 为类的先验概率,于是计算的主 要目标是求 P ( x / ci ) 。

结点一样,也可以有父节点。本文采用基于搜索打分的方法构造贝叶斯分类器,搜索打分算
b、确定变量 X j 的父结点个数,等于 u 则停止为它寻找父结点; c、如果父节点的个数大于 u ,则从 中按顺序选择 X j 之前的节点,但不是 X j 父 结点的变量 X i 做为 X j 的父结点; d、使用 BIC 测度对新结构打分; e、同前次打分比较,如果评分高,则添加 X i 为 X j 的父节点;如果 BIC 评分低, 则停止为 X j 寻找父结点; 3)使用训练数据集进行参数学习(最大似然估计法) ; 4)对测试集分类,得出分类准确度。
相关主题