基于Gauss分布和Gram-Schmidt正交化的朴素贝叶斯分类算法.pdf

收稿日期:.基金项目:江西省高校人文社会科学研究项目(J Y );贵州省自然科学技术基金项目(Y );重庆市自然科学技术基金项目(c s t c j c y j m s x mX );陕西铁路工程职业技术学院基金项目(KY ).作者简介:黄小杰(),男,讲师,博士.通信作者:吴春(),男,副教授,博士.E m a i l:w u c h u n c o m.黄小杰,刘芝秀,邓梓杨,等基于G a u s s分布和G r a m S c h m i d t正交化的朴素贝叶斯分类算法J南昌大学学报(理科版),():HUAN GXJ,L I UZX,D E N GZY,e ta l N a i v eB a y e sc l a s s i f i c a t i o na l g o r i t h mb a s e do nG a u s sd i s t r i b u t i o na n dG r a m S c h m i d to r t h o g o n a l i z a t i o nJJ o u r n a l o fN a n c h a n gU n i v e r s i t y(N a t u r a lS c i e n c e),():基于G a u s s分布和G r a m S c h m i d t正交化的朴素贝叶斯分类算法黄小杰,刘芝秀,邓梓杨,刘红军,吴春(南昌工程学院理学院,江西 南昌 ;南昌大学数学与计算机学院,江西 南昌 ;贵州师范大学数学科学学院,贵州 贵阳 ;重庆师范大学数学科学学院,重庆 )摘要:朴素贝叶斯分类算法是一种简单实用的分类方法,人们对它的属性间条件独立性假设做了许多研究,致力于消除冗余属性、减少属性间的关联性,以获得一些新属性来使用朴素贝叶斯算法,但新属性间的独立性却不易度量,因而改进之处的理论支撑有所不足,改进后的朴素贝叶斯算法的效果更多的是由数据实验进行佐证.本文定义了G a u s s分布型数据,提出了经G r a m S c h m i d t正交化方法改进的朴素贝叶斯算法,使其可以方便地使用于G a u s s分布型数据的分类.该改进方法不同以往显式的构造新属性集或属性变换矩阵,而是直接正交化属性的样本数据,并证明了正交后的属性数据所对应的抽象新属性的独立性.这说明对于G a u s s分布型数据的分类,原朴素贝叶斯算法中的条件独立性的假设不会给算法的使用造成障碍,经G r a m S c h m i d t正交化后即可满足这个约束条件.关键词:G a u s s分布型数据;G r a m S c h m i d t正交化;朴素贝叶斯;分类中图分类号:T P 文献标志码:A文章编号:()N a i v eB a y e s c l a s s i f i c a t i o na l g o r i t h mb a s e do nG a u s sd i s t r i b u t i o na n dG r a m S c h m i d t o r t h o g o n a l i z a t i o nHUANGX i a o j i e,L I UZ h i x i u,D e n gz i y a n g,L I U H o n g j u n,WUC h u n(D e p a r t m e n to fS c i e n c e,N a n c h a n gI n s t i t u t eo fT e c h n o l o g y,N a n c h a n g ,C h i n a;S c h o o l o fM a t h e m a t i c sa n dC o m p u t e rS c i e n c e,N a n c h a n gU n i v e r s i t y,N a n c h a n g ,C h i n a;S c h o o l o fM a t h e m a t i c a lS c i e n c e s,G u i z h o uN o r m a lU n i v e r s i t y,G u i y a n g ,C h i n a;S c h o o l o fM a t h e m a t i c a lS c i e n c e s,C h o n g q i n gN o r m a lU n i v e r s i t y,C h o n g q i n g ,C h i n a)A b s t r a c t:T h en a i v eB a y e sc l a s s i f i c a t i o na l g o r i t h mi sas i m p l ea n dp r a c t i c a lm e t h o df o rc l a s s i f i c a t i o n T h e r ew e r eal o to fs t u d i e s o nt h e a s s u m p t i o no f c o n d i t i o n a l i n d e p e n d e n c eb e t w e e na t t r i b u t e s T h e r e s e a r c h w a s c o mm i t t e d t oe l i m i n a t e r e d u n d a n t a t t r i b u t e sa n dt or e d u c e t h ec o r r e l a t i o nb e t w e e na t t r i b u t e s,w i t ht h ea i mt oo b t a i ns o m en e wa t t r i b u t e sb e i n g m o r e i n d e p e n d e n t o fa n da d a p t e dt on a i v eB a y e sa l g o r i t h m H o w e v e r,t h e i n d e p e n d e n c eb e t w e e nn e wa t t r i b u t e sw a sn o te a s yt om e a s u r e T h e r e f o r e,t h e i m p r o v e m e n t o f t h en a i v eB a y e s a l g o r i t h mw a sn o t s u p p o r t e ds u f f i c i e n t l yb y t h e o r yb u tw a sm o r e s u p p o r t e db yd a t ae x p e r i m e n t s T h i sp a p e rd e f i n e d G a u s sd i s t r i b u t e dd a t aa n dp r o p o s e d a ni m p r o v e dn a i v eB a y e sa l g o r i t h mu s i n gt h eG r a m S c h m i d to r t h o g o n a l i z a t i o nm e t h o d,m a k i n g i t c o n v e n i e n t f o r c l a s s i f i c a t i o nw i t hG a u s s i a nd i s t r i b u t i o nd a t a T h e i m p r o v e dm e t h o dw a sd i f f e r e n t f r o mt h ep r e v i o u sm e t h o d U n l i k ep r e v i o u sm e t h o d s t h a t e x p l i c i t l yc o n s t r u c tn e wa t t r i b u t e ss e t o r a t t r i b u t e s t r a n s f o r m a t i o nm a t r i x,t h ea p p r o a c h i nt h ec u r r e n tp a p e rd i r e c t l yo r t h o g o n a l i z e dt h es a m p l ed a t ao fa t t r i b u t e s I tw a sa l s op r o v e d t h a tt h ea b s t r a c tn e wa t t r i b u t e sc o r r e s p o n d i n gt ot h eo r t h o g o n a l i z e da t t r i b u t e sd a t a w e r e i n d e p e n d e n c e T h i ss h o w e d t h a t t h ea s s u m p t i o no fc o n d i t i o n a l i n d e p e n d e n c e i nt h eo r i g i n a l n a i v eB a y e s a l g o r i t h mw i l l n o t c a u s eo b s t a c l e s t o t h eu s eo f t h e a l g o r i t h mf o r t h e c l a s s i f i c a t i o no fG a u s sd i s t r i b u t e dd a t a,a s t h i sc o n s t r a i n t c a nb es a t i s f i e da f t e rG r a m S c h m i d to r t h o g o n a l i z a t i o n 第 卷第期 年月南昌大学学报(理科版)J o u r n a l o fN a n c h a n gU n i v e r s i t y(N a t u r a lS c i e n c e)V o l N o J u n K e yW o r d s:G a u s sd i s t r i b u t i o nd a t a;G r a m S c h m i d to r t h o g o n a l i z a t i o n;n a i v eB a y e s;c l a s s i f i c a t i o n朴素贝叶斯算法是一种简单实用的概率估计与分类算法,它有着广泛的应用.例如可用于山火风险评估、内河航运事故分析、垃圾邮件过滤、冰雹天气识别、缺失数据处理等各个方面.然而,朴素贝叶斯算法要求属性之间具有条件独立性,这个假设往往与实际情况相左,从而影响了它的使用性能.为了满足属性的条件独立性假设以便合理地使用朴素贝叶斯算法,就必须尽量消除冗余属性、减少属性间的关联性,对此人们进行了大量的研究,主要集中在筛选或构造的新属性集.如,利用互信息、相关性等计算属性间的相关度,剔除冗余属性;利用主成分分析(p r i n c i p a l c o m p o n e n ta n a l y s i s,P C A)对原属性集进行降维处理,使新主成分属性之间互不相关;利用独立分量分析方法(i n d e p e n d e n t c o m p o n e n t a n a l y s i s,I C A)将原属性变换到新的属性空间中以消除属性之间的相关性,使得新属性尽可能满足朴素贝叶斯算法的条件独立性假设,从而提高它的概率估计与分类效率.但是,通过消除冗余属性、减少属性间的关联性获得新属性集后,新属性间的条件独立性却难以度量,成为了一个新的问题,因而其理论支撑有所不足,经改进后的朴素贝叶斯算法的分类效果通常是用数据实验进行佐证.显然,朴素贝叶斯及其改进算法并不能适用所有类型的数据,对算法适用的数据类型做更充分的说明是必须的.事实上,数据和算法是强耦合的,先对数据进行说明不但能够更全面地评估算法的效果,而且有助于进行更深入的理论分析.我们首先定义了G a u s s分布型数据,提出了基于G r a m S c h m i d t正交化方法 改进的朴素贝叶斯算法、它和以往具体的构造出新属性或属性变换矩阵(P C A、I C A)不同,而是将属性的样本数据直接正交化处理.自然地正交后的数据抽象的对应着一些新的属性.我们同时也证明了这些未显式构造出的抽象属性是独立的,这说明了对于G a u s s分布型数据的分类,经G r a m S c h m i d t正交化方法改进的朴素贝叶斯算法可以规避原算法中条件独立性假设所带来的障碍.我们另用鸢尾花数据做了数据实验,首先检验了鸢尾花数据是G a u s s分布型数据,其次验证了无论按哪种属性排序顺序正交化鸢尾花的属性数据,未经改进的朴素贝叶斯算法对鸢尾花数据的分类准确率都低于经G r a m S c h m i d t正交化方法改进后的朴素贝叶斯算法对鸢尾花数据的分类准确率.说明对于G a u s s分布型数据的分类,经G r a m S c h m i d t正交化方法改进的朴素贝叶斯算法的效果是显著的.G a u s s分布型数据定义 G a u s s分布记n,n,n nnnn n.设是一个n维随机向量,和分别是随机向量的数学期望及协方差矩阵,即jEj,jn;j kE(jj)(kk),j,kn以T记矩阵的转置,则tTnitii;表示的逆矩阵;d e t表示的行列式.如果n维随机向量的密度函数为p()()n/(d e t)/e x p()T()则称随机向量服从G a u s s分布,G a u s s分布通常记为N(,).定义G a u s s分布型数据.假设样本数据集D,含有N个样本,每个样本包含n个属性A,A,An,样本数据共有m个类,用Cc,c,cm 中的元素表示其类别.那么第r个样本数据可记为(xr,xr,xr n,cj),r,N,j,m其中,xr i表示第r个样本数据的属性Ai(i,n)的取值,cj表示第r个样本数据的类别.如果数据集D(xr,xr,xr n,cj),r,N,j,m在类别给定条件下如类别为cj的属性数据子集(xr,xr,xr n),r有Ncj个取值 来自G a u s s分布,其中Ncj表示类别为cj的样本数据的个数,则称数据集D为G a u s s分布型数据.注若不论类别,数据集D所有的属性数据(xr,xr,xr n),r,N 均来自G a u s s分布,则数据集D必为G a u s s分布型数据.南昌大学学报(理科版)年使用G r a m S c h m i d t正交化改进朴素贝叶斯算法的原理下面是G r a m S c h m i d t正交化方法.引理 设,n为欧式空间中的线性无关向量组,令,e|;(,e)e,e|;kk(k,e)e(k,e)e(k,ek)ek,ekk|k|其中(k,et)Tket表示内积k,n,t,k,则,n为欧式空间中的正交向量组,e,en为标准正交向量组.另外,我们还需要G a u s s分布的两个重要性质.引理 若(,n)T服 从n元G a u s s分布N(,),而C为任意mn阵,则C服从m元G a u s s分布N(C,CCT).引理 若(,n)T服 从n元G a u s s分布N(,),则,n相互独立的充要条件是它们两两不相关.设G a u s s分布型数据集DDt r a i nDt e s t包含训练数据集Dt r a i n和测试数据集Dt e s t,Dt r a i n中含有N个训练数据,Dt e s t含有M个测试数据,它们可分为m个类,类别的集合是Cc,c,cm,用Ncj表示Dt r a i n中类别为cj的训练数据的个数.又设DDt r a i nDt e s t中的数据包含n个属性A,A,An,将第r个样本数据表示为xr(xr,xr,xr n),r,N,N,NM其中,xr i表示第r个样本属性Ai(i,n)的取值.不妨设前N个样本数据属于Dt r a i n,后M个样本数据属于Dt e s t,我们可以使用前N个数据(即Dt r a i n)的类别信息和所有数据(即DDt r a i nDt e s t)的属性信息.对于上述数据集DDt r a i nDt e s t,在Dt e s t任取一个数据xr(xr,xr,xr n),rN,NM,不妨设rN,设其类别为cj.进而取出Dt r a i n中所有类别为cj的数据(xr,xr,xr n),r有Ncj个取值,不妨设r,Ncj.记(x,x,xNcj,xN )T(x,x,xNcj,xN )Tn(xn,xn,xNcjn,xN n)T()它们实际上是由上下排列的样本属性数据矩阵的列所构成的向量.按引理的G r a m S c h m i d t正交化方法,将,n正交化为,n,再补充正交化后遗失的信息.其中的信息损失可从正交化表达式中得知,例如,在将k变为k的过程中,kk(k,e)e(k,e)e(k,ek)ek 损失了(k,e)e(k,e)e(k,ek)ek.为弥补信息损失而将,n变换为,n如下.,|,|n,|,|,|n,|kkk,k|k|k|k|k,k|k|k|k|n,k|k|k|k|nn()若记(x,x,xNcj,xN )T(x,x,xNcj,xN )Tn(xn,xn,xNcjn,xN n)T则样本数据由xr(xr,xr,xr n),r,Ncj,N转变为了xr(xr,xr,xm),r,Ncj,N定理对G a u s s分布型数据集,上所述()式向量组,n是相互正交的.注意到每个向量i的分量数据集xr i|r,Ncj,N,i,n第期黄小杰等:基于G a u s s分布和G r a m S c h m i d t正交化的朴素贝叶斯分类算法所蕴含的潜在结构(即某个概率分布)对应着一个抽象的属性(即某个随机变量),记为Ai,i,n即xr i|r,Ncj,N 是属性Ai的观察值,则属性Ai,i,n在类别给定的条件下相互独立.从而用其代替原属性Ai,i,n可改进朴素贝叶斯算法.证明由()式,n分别与,n共线,而,n是相互正交的,因为它们是由()中的向量,n经过正交化得到的,所以,n也是正交的.数据集DDt r a i nDt e s t是G a u s s分布型数据,在给定类别cj条件下,它的属性数据(xr,xr,xr n),r,Ncj,N是来自G a u s s分布,即,n服从G a u s s分布.由G r a m S c h m i d t正交化过程知,n是,n的线性组合,从而,n也是经,n线性变换得到的,根据引理知,n服从G a u s s分布.又由于,n两两正交,所以它们两两线性无关,根据引理知,n独立,从而其对应的抽象属性Ai,i,n是条件独立的.注在定理的证明中,n两两正交,则意味着根据属性Ai,i,n的样本数据(i,i,n,的分量数据集)估计得到了属性间的相关系数为,从而推断属性Ai,i,n的线性无关性和独立.根据大数定律,i的分量数据集越大,推断属性的独立性就可靠.注类似于定理的证明可知用P C A或I C A构造新属性或属性变换矩阵来改进朴素贝叶斯的方法,新属性是原 属性的线性 变换,所以对 于G a u s s分布型数据集,由P C A和I C A构造的新属性也是条件独立的,从而满足应用朴素贝叶斯算法的前置条件.由此可知,在对改进算法所适用的数据类型做明确的界定后,算法改进之处的理论支撑才显得更为牢固.改进的朴素贝叶斯算法算法经G r a m S c h m i d t正交化方法改进的朴素贝叶斯算法.输入:Dt r a i n中数据的属性信息和类别信息,以及Dt e s t中数据的属性信息输出:Dt e s t中数据的类别信息(a)依次选取Dt e s t中的数据xr(xr,xr,xr n),rN,NM,重复执行(b)(f)步,下面以rN为例;(b)设xr,rN,类别为cj.选取Dt r a i n所有类别为cj的数据(xr,xr,xr n),设共有Ncj个数据,不妨设r,Ncj;(c)按()式记,n,使用G r a m S c h m i d t正交化方法,将它们正交化为,n;(d)按()式补充正交化后遗失的信息,将,n变换为,n;(e)用如下()式计算xr(即xr),rN,属于类别cj的条件概率P(cj|xr);(f)依次取cj,j,m,重复执行(b)(e)步,可得到待判样本xr(即xr)属于各类的概率为PjP(cj|xr),j,m如果Pkm a xP,P,Pm,那么将待判样本xr(即xr)判别为ck类.注对于待判样本xr变换后的xr,rN,根据定理其分量所对应的各个属性A,A,An相互独立,那么由各抽象新属性之间的独立性和贝叶斯公式,可计算出待判样本xr(即xr),rN,属于类别cj的条件概率为,:P(cj|xr)P(cj)P(xr)niP(xr i|cj),P(cj)NcjN()其中,xr i是待判样本xr属性Ai的取值;P(xr)为xr(xr,xr,xr n)的联合分布概率;P(xr i|cj)为样本类别是cj的前提下待判样本xr的属性Ai的取值为xr i的条件概率;P(cj)为第cj类的先验概率,Ncj表示数据集Dt r a i n中类别为cj的样本个数,N表示数据集Dt r a i n中的样本个数.由于Ai(i,n)是相互独立的连续属性,且数据集D为G a u s s分布型数据,因此P(xr i|cj)可等价(与概率大小保序)的表示为P(xr i|cj)cj,ie x p(xr icj,i)cj,i南昌大学学报(理科版)年其中,cj,i是xr i|r,Ncj,N 的均值;cj,i是xr i|r,Ncj,N 的方差.因此,()式可等价的改写为P(cj|xr)P(cj)ni cj,ie x p(xr icj,i)cj,i()数据实验下面我们再用i r i s数据的分类实验来辅助检验上述改进的朴素贝叶斯算法的效果.i r i s数据集是机器学习领域的经典数据集,该数据集分为个类别:s e t o s a,v e r s i c o l o u r和v i r g i n i c a;每个样本数据都有个属性:s e p a l l e n g t h、s e p a lw i d t h、p e t a l l e n g t h以及p e t a lw i d t h.我们可以通过这四个属性来判断i r i s隶属于个类别中的哪一类别.实验主要检验由G r a m S c h m i d t正交化处理后的数据对朴素贝叶斯算法分类效果的影响,根据注的说明,我们尽可能地将更多同类数据正交化,因此,将 个i r i s数据全部分组正交化.按类别分组,每组 个数据.首先将每组数据做均值方差标准化处理,再用S W检验检验三组数据均显著服从G a u s s分布,即i r i s数据是G a u s s分布型数据.将数据按类别分组正交化后,再将所有数据随机分为两组,各占 和.注意到即使是将原始的朴素贝叶斯算法用于i r i s的分类,其准确率也非常高,所以我们将占 的数据设置为训练数据,而 的数据设置为测试数据,取 次平均,记录有关数据实验的结果如表所示.表中N B和G S N B分别表示未经改进的朴素贝叶斯分类器和经G r a m S c h m i d t正交化方法改进的朴素贝叶斯分类器,其中,个属性数据按正交化顺序不同,共有!种正交化过程.表N B和G S N B对i r i s分类的准确率T a b A c c u r a c yo f i r i s c l a s s i f i c a t i o nb yu s i n gN Ba n dG S N B算法准确率/平均准确率/N B G S N B G S N B G S N B G S N B 从表可以看出,对于i r i s这样的G a u s s分布型数据,经G r a m S c h m i d t正交化方法改进后的朴素贝叶斯算法较之于未经改进的朴素贝叶斯算法的分类效果有稳定和明显的提升.参考文献:周恩泽,黄勇,龚博,等基于朴素贝叶斯网络的输电走廊山火风险评估模型J南方电网技术,():叶子阳,陈沿伊,张培林,等基于数据驱动贝叶斯网络的内河船舶交通事故分析J安全与环境工程,():徐健锋,刘承启,黄传华,等反垃圾邮件及粗糙朴素贝叶斯邮件分类器J南昌大学学报(理科版),():李冰村,唐晓文,何建新,等基于机器学习的冰雹天气识别研究J气象科学,():张文,姜祎盼,殷广达,等基于朴素贝叶斯和EM算法的软件工作量缺失数据处理方法J系统工程理论与实践,():L I U H,S UNJ,L I UL,e t a l F e a t u r es e l e c t i o nw i t hd y n a m i c m u t u a li n f o r m a t i o nJ P a t t e r n R e c o g n i t i o n,():洪智勇,刘灿涛,邓宝林基于二次R e n y i熵的正则化互信息特征选择方法J计算机应用,():杨立洪,李琼阳,李兴耀基 于信 息 值的 相关 属性 约减加权二分类朴素贝叶斯算法研究J统计与决策,():张静,王建民,何华灿基于属性相关性的属性约简新方法J计算机工程与应用,():李海军,王钲旋,王利民,等基于主成分分析提升朴素贝叶斯J仪器仪表学报,():HYVA R I N E N A,HUR R IJ,HOY E RPOI n d e p e n d e n t c o m p o n e n t a n a l y s i sML o n d o n:S p r i n g e r,HYVA R I N E NAS u r v e yo n i n d e p e n d e n t c o m p o n e n t a n a l y s i sJ N e u r a lC o m p u t a t i o n,():李思奇,吕王勇,邓柙,等基于改进P C A的朴素贝叶斯分类算法J统计与决策,():张贤科,许甫华高等代数学(第二版)M北京:清华大学出版社,李贤平概率论基础M北京:高等教育出版社,李航机器学习方法M北京:清华大学出版社,秦锋,任诗流,程泽凯,等基于I C A方法的朴素贝叶斯分类器J计 算 机 工 程 与 设 计,():第期黄小杰等:基于G a u s s分布和G r a m S c h m i d t正交化的朴素贝叶斯分类算法