混合式朴素贝叶斯分类模型_图文

1、第25卷第1期吉林大学学报(信息科学版V o.l25N o.1 2007年1月Jou rna l of Jili n U nive rsit y(In f o r m ati on Science Ed itionJan.2007文章编号:1671-5896(200701-0057-05混合式朴素贝叶斯分类模型董立岩1a,刘光远1b,苑森淼1a,李永丽2,孙铭会1a(1.吉林大学a.计算机科学与技术学院,长春130012;b.通信工程学院,长春130022;2.东北师范大学计算机学院,长春130024摘要:为了降低朴素贝叶斯分类模型的独立性假设约束,提出一种混合式朴素贝叶斯分类模型(M BN:

2、M ixedN a i ve Bay es。通过分析贝叶斯定理,把条件属性集合划分成若干个独立的属性子集,用树增广朴素贝叶斯分类对属性子集分别进行分类学习,通过公式进行整合。将该模型算法与朴素贝叶斯及树增广朴素贝叶斯进行实验比较,实验结果表明M BN分类器在多数数据集上具有较高的分类正确率。关键词:贝叶斯定理;朴素贝叶斯;数据挖掘;分类中图分类号:TP181文献标识码:AM i xed N ai ve Bayes C lassifierM odelDONG Li-yan1a,LI U Guang-yuan1b,YUAN Sen-m iao1a,LI Yong-li2,SUN M i n g-h

3、ui1a(1a.C ollege ofC o m pu ter Science and Techno l ogy,Jili n Un i versit y,C hangchun130012,Ch i na;1b.Coll ege ofC o mmun icati on Engineeri ng,Jilin Un iversit y,Changchun130022,C hina;2.C ollege ofC o m pu ter,Nort heas tNor m alUn i versit y,C hangchun130024,Ch i naAbst ract:In order to decre

4、ase t h e attribu t e independence assu m p tion w hich is m ade by N aive Bayesian,a ne w Bayesian m ode lMBN(M i x ed Naive Bayesis intr oduced.It divides a ttri b ute sets into severa l i n dependent sub-sets by ana l y zi n g Bayesian theore m.The subsets ar e trained by TAN(Tree Aug m en ted N

5、aive B ayesand t h e re-su lts are integ rated by fo r m u la.MBN classifier is co m pa r ed w it h Naive B aye s classifier and TAN classifier by an experi m en.t Experi m en tal resu lts sho w t h at t h ism ode l has h i g he r c lassification accuracy in m ost data se ts.K ey w ords:bay s t h eo

6、 r e m;naive bayes;data m i n ing;c l a ssify引言当今,社会已经进入了网络信息时代,计算机与网络信息技术的飞速发展使各个领域的数据和信息急剧增加,并且由于人类的参与使数据与信息系统中的不确定性更加显著。如何从海量数据中挖掘潜在的、有利用价值的信息,给人类的智能信息处理能力提出了前所未有的挑战,由此产生了人工智能研究的一个新领域:数据挖掘(DM:Data M ining。分类是数据挖掘中的一项重要任务,它属于预测,预测的目的是利用历史数据记录自动推导出对给定数据的推广描述,从而对即将到来的数据进行预测。它是根据数据集的特点构造一个分类器,利用分类器对未

7、知类别的样本赋予类别的一种技术。构造分类器的过程一般分为训练和测试两个步骤。在训练阶段,分析训练数据集的特点,为每个类别产生一个对相应数据集的准确描述或模型;在测试阶段,利用类别的描述或模型对测试进行分类,测试其分类准确度。目前主要的数据挖掘分类方法有:决策树学收稿日期:2006-03-06基金项目:国家自然科学基金资助项目(60275026作者简介:董立岩(1966,男,长春人,吉林大学副教授,博士研究生,主要从事数据挖掘研究,(Tel86-133*(E-m aildongl y jl ;苑森淼(1943,男,石家庄人,吉林大学教授,博士生导师,主要从事数据库、人工智能及计算机网络系统研究,

8、(Tel86-431-85094663(E-m ailyuansenm iao126.co m。习1,2、贝叶斯学习35、人工神经网络6、遗传算法7等。由于贝叶斯理论具有坚实的数学理论基础、综合先验信息的能力,并且随着理论的不断完善,贝叶斯理论用于解决数据挖掘分类问题的技术得到了迅速发展。为了解决贝叶斯学习用于分类任务时遇到的学习效率及正确率的问题,笔者分析了几种经典贝叶斯模型的优缺点,提出了一种全新的混合式朴素贝叶斯模型(MNB :M ixed N aive Bayes 。1知识准备1.1信息论中的相关定义设样本空间U =X 1,X 2,X n ,C ,其中X =X 1,X 2,X n 是属

9、性变量集,C 是类别变量,对于样本空间U 共分为m 类,类变量C 的取值为c 1,c 2,c m ,属性X i 的取值为x i 。设信源X 为离散型随机变量,则用来度量X 的不确定性的信息熵8H (X =-XP (x log P (x (1设(X ,Y 均为离散型随机变量,用来度量二元随机变量不确定性的联合信息熵8H (X ,Y =-XYP (x ,y log P (x ,y (2条件信息熵8H (X |Y 用来度量在收到随机变量Y 提供的信息后,随机变量X 仍然存在的不确定性,其定义为H (X |Y =-XYP (x ,y log P (x |y (3互信息8I (X ;Y 用来描述随机变量

10、Y 提供的关于X 的信息量的大小I (X ;Y =H (X -H (X |Y =XYP (x ,y logP (x ,y P (x P (y (41.2贝叶斯的发展贝叶斯理论是英国牧师数学家托马斯 贝叶斯1763年提出的,贝叶斯理论假设是如果事件的结果不确定,则量化它的唯一方法就是事件的发生概率。如果过去试验中事件的出现率已知,则根据数学方法可以计算出未来试验中事件出现的概率。应用贝叶斯定理,样本u i =x 1,x 2,x n 属于类c j (1j m 的概率为P (c j |x 1,x 2,x n =P (x 1,x 2,x n ,c j P (x 1,x 2,x n =P (c j &#

11、215;P (x 1,x 2,x n |c j P (x 1,x 2,x n =P (c j ×ni =1P (x i |x 1,x i-1,x i +1,x n P (x 1,x 2,x n =P (c j ×ni =1P (x i |x i P (x 1,x 2,x n (5式(5中,x i 代表条件属性X i 所有父结点的集合,不同的贝叶斯分类模型区别即在此处。朴素贝叶斯模型(NB :Na i v e Bayes 假定所有的条件属性是相互独立的,条件属性共有一个父结点就是类属性结点,这个假设叫做条件独立性假设。该假定构造出来的NB 模型结构简单,以指数级降低了贝叶斯网

12、络构造的复杂性,运用该假定后,式(5变为P (c j |x 1,x 2,x n =P (c j ×ni =1P (x i |c j P (x 1,x 2,x n (6数据挖掘中所处理的数据往往具有杂乱性、重复性、不完整性,这使得NB 模型的条件独立性假设在现实问题中很难满足,如何放松甚至消除该条件独立性假设是研究人员研究的热点之一。树增广朴素贝叶斯网络分类器9(TAN :T r ee Aug m en t e d N aive B aye s 是由Fried m an 提出的一种树状贝叶斯网络,它借鉴贝叶斯网中表示依赖关系的方法,扩展朴素贝叶斯的结构,使其能容纳属性间存在的依赖关系,

13、但对其表示依赖关系的能力加以限制。在朴素贝叶斯分类器的基础上,在属性之间增添连接弧,以消除NB 关于条件独立的假设,另外TAN 要求属性结点除类结点为父结点外最多只能有一个条件属性父结58吉林大学学报(信息科学版第25卷点,即有P (c j |x 1,x 2,x n =P (c j ×ni =1P (x i |x t c j P (x 1,x 2,x n (7其中,x t 为一条件属性X t (1t n ,且t i 的值,与类属性C 一同作为条件属性X i 的父结点。据TAN 假设,条件属性X t 可以不存在而只有类属性C 为条件属性X i 的父结点。无约束贝叶斯网络分类器将类属性与

14、其他属性混同处理,类属性只是图形结构中普通的一个结点,对网络结构没有做任何条件假设。对于有n 个变量的问题域,对应的网络结构空间为n 个结点构成的所有可能的有向无环图,显然结构空间大小是n 的指数次,虽然它的精度可能会增强但是学习效率的代价却很大。2MNB 模型的提出2.1贝叶斯定理公式探讨由于数据挖掘处理的多是海量数据,这些数据的属性也是错中复杂,它们相互间存在各种联系,通过一些方法可以把关系紧密的属性分到一起,假设属性变量集X =X 1,X 2,X n 被分为S 个独立的属性子集E 1,E 2,E S 。再次分析样本u i =x 1,x 2,x n 属于类c j (1j m 的概率P (c

15、 j |x 1,x 2,x n =P (c j ×P (x 1,x 2,x n |c j P (x 1,x 2,x n =P (c j ×P (E 1|c j ××P (E S |c j P (x 1,x 2,x n =P (c j ×P (E 1×P (c j |E 1P (c j ××P (E S ×P (c j |E S P (c j P (x 1,x 2,x n =P (E 1××P (E S ×P (c j |E 1××P (c j |E S P

16、 (x 1,x 2,x n ×P (c j =×P (c j |E 1××P (c j |E S (8其中,=P (E 1××P (E S P (x 1,x 2,x n ×P (c j S -1,如果测试样本给定,则值即为确定。观察式中项P (c j |E 1,P (c j |E S 的形式,为S 个属性子集E 1,E 2,E S 分别独立的属于类c j 的概率。依据此规律,分别让S 个属性子集独立地通过TAN 模型来判定所属类别,然后通过式(8对结果进行综合处理,最终得出结论。当S =1时,即属性聚在一个集合,此时MNB

17、即为TAN 模型;当S =n 时,即属性间相互独立,此时MNB 即为NB 模型。图1MNB 模型实例图Fig .1The m ixed na i v e bayes c l a ssifier m ode l2.2MNB 模型图示MNB 模型如图1所示。Ou t p u t 1,Output S 为S 个小分类器得到的预测结果,Ou t p u t 为样本通过MNB 模型得到的最终预测结果。2.3MNB 模型构建步骤构造MNB 模型的关键在于如何找到S 个互相独立的条件属性子集,然后形成S 个小分类器,最后根据公式(8形成最终分类器。这里运用遗传算法改进后的K -m eans 聚类方法10划分

18、条件属性子集。详细构建步骤。步骤1利用聚类算法将属性变量集X =X 1,X 2,X n 分为S 个条件独立的属性子集E 1,E 2,E S 。1根据式(4计算出I (X i ;C 作为属性的空间矢量点坐标。2把聚类算法中的K 值用二进制串表示,作为染色体。为避免初始位置对K -m eans 算法的影响,59第1期董立岩,等:混合式朴素贝叶斯分类模型使用伪随机数来初始化聚类中心。3循环对染色体进行交叉、变异操作,直至通过适应度函数(各类之间距离和最大而类内间的距离最小找到最优的K 值,进而找到K 个聚集。步骤2在各个属性子集内分别建立T AN 模型。1通过训练集计算属性对之间的条件互信息I (X

19、 i ,Y j |C (i j 。2建立一个以E i (1i S 内部各条件属性为结点的加权完全无向图,结点X i ,Y j 之间的权重为I (X i ,Y j |C (i j 。3利用求最大权生成树算法,建立该无向图最大权重跨度树。首先把边按权重由大到小排序,之后遵照被选择的边不能构成回路的原则,按照边的权重由大到小的顺序选择边,这样由所选择的边构成的树便是最大权重跨度树。4指定一个属性结点作为根结点,将所有边的方向设置成由根结点指向外,把无向图转换成有向图;加入类结点C ,并添加从C 指向每个属性结点X i 的弧。5计算P (c j |E i (1i S ,1j m 。步骤3把上述求出的P

20、 (c j |E i (1i S ,1j m 带入式(8,求出使后验概率P (c j |x 1,x 2,x n 得到最大值的类别,即为该样本实例的类标签。3实验结果实验环境:采用DELL GX620机器,2.8GH z I n t e lCPU ,512M 内存,W indo w s XP 操作系统,O ra -cle 10g 数据库,所有算法代码采用C +在V isual S tudio 2005环境下编译执行。实验数据采用从UC I 数据集11选出12个数据集合(见表1。笔者提出的模型没有考虑存在连续变量的情况,对于存在连续变量的数据集,分别使用了Jie Cheng 提供的数据预处理工具P

21、rePr ocessor 进行离散化,离散化的参数选用默认设置。对于实例中缺失数据项,按照缺失值对应属性中出现次数最多的值补齐。表1实验数据集Tab .1The da ta sets used in the experi m en tsN o D a taSet A ttri bu t e C lasse s Instances N o D ataSe t A ttribute C lasses Instances 1M ushroom 22237637Po st -O perative 83902Car 6417288V eh icle 1848463Contac t -Lenses 432

22、49N u rse ry 85129604Segm en t 197231010House -V o t e s -841624355G er m an 202100011A nnea l 3868986F lare C132138912Z oology167101图2MNB 与NB 、TAN 模型的分类正确率比较F i g .2Expe ri m enta l r e sults by co m paringt h e accu r acy ofMNB 、NB and TAN在某些数据集中各属性间相关度弱,聚类算法把所有条件属性分别各归为一类,则MNB 模型就变为NB 模型;有时属性间相关度

23、很强,聚类算法把所有属性归为一类,则MNB 模型变为TAN 模型。通过实验可以看出,MNB 模型分类器针对不同的数据集合可以自适应的调整K 值,当K 1时,它去除了TAN 模型中一些冗余的边,分类效果在大部分数据集中比NB 、TAN 模型的分类正确率要高(见图2。60吉林大学学报(信息科学版第25卷4结语笔者通过深入研究数据挖掘贝叶斯分类模型,针对朴素贝叶斯的独立性假设约束过高及在现实世界中的不合理性,提出了一种新型贝叶斯模型MNB 。MNB 模型降低了NB 模型的约束条件,它可以随着样本集的不同自适应变化聚类参数值,使模型可在NB 和TAN 模型间弹性的变化,在大部分数据集合中的分类正确率比

24、NB 、TAN 也高,通过实验验证了MNB 模型具有较高的分类性能。目前,MNB 模型还只能处理离散型分类数据样本集,对于连续型样本集还只能通过先离散化然后处理的方法来建立模型,而离散化可能会造成数据的消损。如何通过模型对连续型样本集进行建模成为未来进一步研究的问题。参考文献:1QU I NLAN J R.Inducti on of D ec ision T rees J .M achine Learni ng ,1986,1(1:81-106.2QU I NLAN J R.C4.5:P rog ram s fo rM achine Learni ng M .San M a t eo ,CA

25、,U S A :M organ -K auf m ann Publis hers ,1993.3C HENG J ,BELL D ,L I U W.Learni ng Be lief N e t w orks fro m D a t a :A n Infor m a ti on T he roy Based Approach C P roceed -ings o f t he S ixth A C M Internati onal Confe rence on Info r m a tion and K now ledge M anagemen.t Bo st on ,MA ,U S A :s

26、 .n .,1997:103-113.4HECK ERMAN D ,GE I GER D.Lea rning Bayesian N et wo rks :A U nica tion fo r D isc re t e and G aussian Dom ains C P roceed -ing s of t he 7th A nnual Confe rence on U ncertainty i n A rticia l Inte lligence .L os A nge l e s ,CA :s .n .,1995:274-284.5COOPER G ,HERSKOV ITS E .A Ba

27、y esi anM e t hod f o r t he Induction o f P robabilistic N et wo rks fro m D a t a J .M achi ne L earn -ing ,1992,9(4:309-347.6FU L .N eura lN e t w orks in Co m pu t e r Inte lligence M .N ew Yo rk :M cG ra w H ill ,1994.7HO LLAND J H.A dap t a tion in N a t u ra l and A rtificia l Syste m M .A nn A rbor :U niversity o fM ichi g an P ress ,1975.8朱雪龙.应用信息论基础M .北京:清华大学出版社,2001.ZHU Xue -l ong .F unda m enta ls of A pp lied Infor m a tion T heo ry M .Beijing :T singhua Un i ve rsit y P re ss ,2001.9FR I EDM AN N ,G EI G ER