第5章贝叶斯分类算法 5.基本概念 1.主观概率 5.1 贝叶斯算法是一种研究不确定性的推理方法。不确定性常用贝叶斯概率表示,它是 一种主观概率。通常的经典概率代表事件的物理特性,是不随人意识变化的客观存在。 而贝叶斯概率则是人的认识,是个人主观的估计,随个人主观认识的变化而变化。例如, 事件的贝叶斯概率只指个人对该事件的置信程度,因此是一种主观概率。 投掷硬币可能出现正反面两种情形,经典概率代表硬币正面朝上的概率,这是一个客 观存在;而贝叶斯概率则指个人相信硬币会正面朝上的程度。 同样的例子还有,一个企业家认为“ 的概率是0.这 里的0. 一项新产品在未来市场上销售” 8, 8是根据他多年的经验和当时的一些市场信息综合而成的个人信念。 一个投资者认为“购买某种股票能获得高收益” 6,6是投资者根 的概率是0.这里的0. 据自己多年股票生意经验和当时股票行情综合而成的个人信念。 贝叶斯概率是主观的,对其估计取决于先验知识的正确性和后验知识的丰富和准确 度。因此贝叶斯概率常常可能随个人掌握信息的不同而发生变化。 对即将进行的羽毛球单打比赛结果进行预测,不同人对胜负的主观预测都不同。如 果对两人的情况和各种现场的分析一无所知,就会认为二者的胜负比例为1∶1;如果知 道其中一人为奥运会羽毛球单打冠军,而另一人只是某省队新队员,则可能给出的概率是 奥运会冠军和省队队员的胜负比例为3∶1;如果进一步知道奥运会冠军刚好在前一场比 赛中受过伤,则对他们胜负比例的主观预测可能会下调为2∶1 。所有的预测推断都是主 观的,基于后验知识的一种判断,取决于对各种信息的掌握。 经典概率方法强调客观存在,它认为不确定性是客观存在的。在同样的羽毛球单 打比赛预测中,从经典概率的角度看,如果认为胜负比例为1∶1,则意味着在相同的条 件下,如果两人进行100 场比赛,其中一人可能会取得50 场的胜利,同时丢掉另外 50 场。 主观概率不像经典概率那样强调多次重复,因此在许多不可能出现重复事件的场 合能得到很好的应用。上面提到的企业家对未来产品的预测,投资者对股票是否能取 得高收益的预测以及羽毛球比赛胜负的预测中,都不可能进行重复的实验,因此,利用 主观概率,按照个人对事件的相信程度而对事件做出推断是一种很合理且易于解释的 方法。 101 5.1.2 贝叶斯定理 1.基础知识 (1)已知事件A 发生的条件下,事件B 发生的概率,叫作事件B 在事件A 发生下的 条件概率,记为P (B A ) ,其中P (A ) 叫作先验概率,P (B A ) 叫作后验概率,计算条件 概率的公式为 P (B A ) =P (A ∩B ) P A ( ) (5-1) 条件概率公式通过变形得到乘法公式为 P (A ∩B ) =P (B A )P (A ) (5-2) (2)设A ,B 为两个随机事件,如果P (AB ) =P (A )P (B ) 成立,则称事件A 和B 相 互独立。此时有P (A B ) =P (A ) ,P (AB ) =P (A )P (B ) 成立。 设A1,A2,…,An 为n 个随机事件,如果对其中任意m (2≤m ≤n) 个事件Ak1 , Ak2 ,…,Akm ,都有 P Ak1 ,Ak2 ,…,Akm ( ) =P (Ak1 )P (Ak2 ) …P Akm ( ) (5-3) 成立,则称事件A1,A2,…,An 相互独立。 (3)设B1,B2,…,Bn 为互不相容事件,P (Bi ) >0,i=1,2,…,n,且∪n i=1 Bi=Ω,对任 意的事件A .∪n i=1 Bi,计算事件A 概率的公式为 P A ( ) =Σn i=1 P (Bi )P (A Bi ) (5-4) 设B1,B2,…,Bn 为互不相容事件,P (Bi ) >0,i=1,2,…,n,P (A ) >0,则在事件A 发生的条件下,事件Bi 发生的概率为 P (Bi A ) = P (BiA ) P A ( ) = P (Bi )P (A Bi ) Σn i=1 P (Bi )P (A Bi ) (5-5) 则称该公式为贝叶斯公式。 2.贝叶斯决策准则 假设Ω= {C1,C2,…,Cm } 是有m 个不同类别的集合,特征向量X 是d 维向量, P (X Ci ) 是特征向量X 在类别Ci 状态下的条件概率,P (Ci ) 为类别Ci 的先验概率。根 据前面所述的贝叶斯公式,后验概率P (Ci X ) 的计算公式为 P (Ci X ) = P (X Ci ) P X ( ) P (Ci ) (5-6) 其中,P X ( ) =Σm j=1 P (X Cj )P (Cj ) 。 贝叶斯决策准则:如果对于任意i≠j,都有P (Ci X ) >P (Cj X ) 成立,则样本模式 102 X 被判定为类别Ci。 3.极大后验假设 根据贝叶斯公式可得到一种计算后验概率的方法:在一定假设的条件下,根据先验 概率和统计样本数据得到的概率,可以得到后验概率。 令P c( ) 是假设c 的先验概率,它表示c 是正确假设的概率,P X ( ) 表示的是训练样 本X 的先验概率,P (X c) 表示在假设c 正确的条件下样本X 发生或出现的概率,根据贝 叶斯公式可以得到后验概率的计算公式为 P c( X ) =P (X c)P c( ) P X ( ) (5-7) 设C 为类别集合,也就是待选假设集合,在给定未知类别标号样本X 时,通过计算找 到可能性最大的假设c ∈C,具有最大可能性的假设或类别被称为极大后验假设 (maximumaposteriori),记作cmap。 cmap =argmax c∈C P c( X ) =argmax c∈C P (X c)P c( ) P X ( ) (5-8) 由于P X ( ) 与假设c 无关,故上式可变为 cmap =argmax c∈C P (X c)P c( ) (5-9) 当没有给定类别概率的情形下,可做一个简单的假定。假设C 中每个假设都有相等的先 验概率,也就是对于任意的ci,cj∈C i( ≠j) ,都有P c( i ) =P c( j ) ,再做进一步简化,只需 计算P (X c) 找到使之达到最大的假设。P (X c) 被称为极大似然假设(maximum likelihood),记为cml。 cml=argmax c∈C P (X c) (5-10) 5.2 贝叶斯分类算法原理 5.2.1 朴素贝叶斯分类模型 贝叶斯分类器诸多算法中朴素贝叶斯分类模型是最早的。它的算法逻辑简单,构造 的朴素贝叶斯分类模型结构也比较简单,运算速度比同类算法快很多,分类所需的时间也 比较短,并且大多数情况下分类精度也比较高,因而在实际中得到了广泛的应用。该分类 器有一个朴素的假定:以属性的类条件独立性假设为前提,即在给定类别状态的条件下, 属性之间是相互独立的。朴素贝叶斯分类器的结构示意图如图5-1所示。 假设样本空间有m 个类别{C1,C2,…,Cm } ,数据集有n 个属性A1,A2,…,An ,给定 一未知类别的样本X= (x1,x2,…,xn ) ,其中xi 表示第i 个属性的取值,即xi∈Ai,则可 用贝叶斯公式计算样本X = (x1,x2,…,xn ) 属于类别Ck (1≤k≤m ) 的概率。由贝叶斯 公式,有P (Ck X ) =P (Ck )P (X Ck ) P X ( ) μP (Ck )P (X Ck ) ,即要得到P (Ck X ) 的值,关 键是要计算P (X Ck ) 和P (Ck ) 。令C (X ) 为X 所属的类别标签,由贝叶斯分类准则,如 103 图5-1 朴素贝叶斯分类器的结构示意图 果对于任意i≠j 都有P (Ci X ) >P (Cj X ) 成立,则把未知类别的样本X 指派给类别 Ci,贝叶斯分类器的计算模型为 V (X ) =argmaxP (Ci )P (X Ci ) (5-11) 由朴素贝叶斯分类器的属性独立性假设,假设各属性xi i( =1,2,…,n) 间相互类条件独 立,则 P (X Ci ) =Πn k=1 P (xk Ci ) (5-12) 于是式(5-11)被修改为 V X ( ) =argmax i P (Ci ) Πn k=1 P (xk Ci ) (5-13) P (Ci ) 为先验概率,可通过P (Ci ) =di/d 计算得到。其中,di 是属于类别Ci 的训练样 本的个数,d 是训练样本的总数。若属性Ak 是离散的,则概率可由P (xk Ci ) =dik/di 计算得到。其中,dik 是训练样本集合中属于类Ci 并且属性Ak 取值为xk 的样本个数,di 是属于类Ci 的训练样本个数。朴素贝叶斯分类的工作过程如下。 (1)用一个n 维特征向量X= (x1,x2,…,xn ) 来表示数据样本,描述样本X 对n 个 属性A1,A2,…,An 的量度。 (2)假定样本空间有m 个类别状态C1,C2,…,Cm ,对于给定的一个未知类别标号的 数据样本X,分类算法将X 判定为具有最高后验概率的类别,也就是说,朴素贝叶斯分类 算法将未知类别的样本X 分配给类别Ci,当且仅当对于任意的j,始终有P (Ci X ) > P (Cj X ) 成立,1≤i≤m ,1≤j≤m ,j≠i。使P (Ci X ) 取得最大值的类别Ci 被称为最 大后验假定。 (3)由于P X ( ) 不依赖类别状态,对于所有类别都是常数,故根据贝叶斯定理,最大 化P (Ci X ) 只需要最大化P (X Ci )P (Ci ) 即可。如果类的先验概率未知,则通常假设 这些类别的概率是相等的,即P (C1 ) =P (C2 ) = … =P (Cm ) ,所以只需要最大化 P (X Ci ) 即可,否则就要最大化P (X Ci )P (Ci ) 。其中,可用频率Si/S 对P (Ci ) 进行 估计计算,Si 是给定类别Ci 中训练样本的个数,S 是训练样本(实例空间)的总数。 (4)当实例空间中训练样本的属性较多时,计算P (X Ci ) 可能会比较费时,开销较 大,此时可以做类条件独立性的假定:在给定样本类别标号的条件下,假定属性值是相互 条件独立的,属性之间不存在任何依赖关系,则下面等式成立:P (X Ci ) = Πn k=1 P (xk Ci ) 。 104 其中,概率P (x1 Ci ) ,P (x2 Ci ) ,…,P (xn Ci ) 的计算可由样本空间中的训练样本进行估 计。实际问题中根据样本属性Ak 的离散连续性质,考虑下面两种情形。 . 如果属性Ak 是连续的,则一般假定它服从正态分布,从而计算类条件概率。 . 如果属性Ak 是离散的,则P (xk Ci ) =Sik/Si。其中,Sik 是在实例空间中类别 为Ci 的样本中属性Ak 上取值为xk 的训练样本个数,而Si 是属于类别Ci 的训 练样本个数。 (5)对于未知类别的样本X,对每个类别Ci 分别计算P (X Ci )P (Ci ) 。样本X 被 认为属于类别Ci,当且仅当P (X Ci )P (Ci ) >P (X Cj )P (Cj ) ,1≤i≤m,1≤j≤m,j≠i, 也就是说,样本X 被指派到使P (X Ci )P (Ci ) 取得最大值的类别Ci。 朴素贝叶斯分类模型的算法描述如下。 (1)对训练样本数据集和测试样本数据集进行离散化处理和缺失值处理。 (2)扫描训练样本数据集,分别统计训练集中类别Ci 的个数di 和属于类别Ci 的样 本中属性Ak 取值为xk 的实例样本个数dik ,构成统计表。 (3)计算先验概率P (Ci ) =di/d 和条件概率P (Ak=xk Ci ) =dik/di,构成概率表。 (4)构建分类模型V X ( ) =argmax i P (Ci )P (X Ci ) 。 (5)扫描待分类的样本数据集,调用已得到的统计表、概率表以及构建好的分类准 则,得出分类结果。 5.2.2 贝叶斯信念网络 朴素贝叶斯分类器的条件独立假设似乎太严格了,特别是对那些属性之间有一定相 关性的分类问题。下面介绍一种更灵活的类条件概率P (X Y ) 的建模方法。该方法不 要求给定类的所有属性条件独立,而是允许指定哪些属性条件独立。 1.模型表示 贝叶斯信念网络(BayesianBeliefNetwork,BBN),简称贝叶斯网络,用图形表示一组 随机变量之间的概率关系。贝叶斯网络有以下两个主要成分。 (1)一个有向无环图(DirectedAcyclicGraph,DAG),表示变量之间的依赖关系。 (2)一个概率表,把各节点和它的直接父节点关联起来。 考虑3个随机变量A、B 和C,其中A 和B 相互独立,并且都直接影响第3个变量C。 3个变量之间的关系可以用图5-2(a)中的有向无环图概括。图中每个节点表示一个变 量,每条弧表示变量之间的依赖关系。如果从X 到Y 有一条有向弧,则X 是Y 的父母, Y 是X 的子女。另外,如果网络中存在一条从X 到Z 的有向路径,则X 是Z 的祖先,而 Z 是X 的后代。例如,在图5-2(b)中,A 是D 的后代,D 是B 的祖先,而且B 和D 都不 是A 的后代节点。贝叶斯网络的重要性质:贝叶斯网络中的一个节点,如果它的父节点 已知,则它条件独立于其所有的非后代节点。图5-2(b)中给定C,A 条件独立于B 和D , 105 因为B 和D 都是A 的非后代节点。朴素贝叶斯分类器中的条件独立假设也可以用贝叶斯 网络来表示。如图5-2(c)所示,其中Y 是目标类,{X1,X2,…,X5} 是属性集。 图5-2 贝叶斯网络 在贝叶斯网络中,除了网络拓扑结构要求的条件独立性外,每个节点还关联一个概率 表。如果节点X 没有父节点,则表中只包含先验概率P (X );如果节点X 只有一个父节 点Y,则表中包含条件概率P (X Y ) ;如果节点X 有多个父节点{Y1,Y2,…,Yk} ,则表中 包含条件概率P(X|Y1,Y2,…,Yk)。 图5-3是贝叶斯网络的一个例子,对心脏病或心口痛患者建模。假设图中每个变 量都是二值的。心脏病节点(HD)的父节点对应于影响该疾病的危险因素,如锻炼(E) 和饮食(D )等。心脏病节点的子节点对应该病的症状,如胸痛(CP)和高血压(BP)等。 如图5-3所示,心口痛(HB)可能源于不健康的饮食,同时又可能导致胸痛。 图5-3 发现心脏病和心口痛病人的贝叶斯网络 影响疾病的危险因素对应的节点只包含先验概率,而心脏病、心口痛以及它们的相 应症状所对应的节点都包含条件概率。为了节省空间,图中省略了一些概率。注意 P (X =x- ) =1-P (X =x ) ,P (X =x- Y ) =1-P (X =x Y ) ,其中x- 表示与x 相反的结 106 果。因此,省略的概率可以很容易求得。例如,条件概率 P (心脏病= no 锻炼= no,饮食= 健康) = 1-P (心脏病=yes 锻炼= no,饮食= 健康) =1-0.55 =0.45 2.模型建立 贝叶斯网络的建模包括两个步骤:创建网络结构以及估计每个节点的概率表中的概 率值。网络拓扑结构可以通过对主观的领域专家知识编码获得,算法5.1给出了归纳贝 叶斯网络拓扑结构的一个系统过程。 算法5.1 贝叶斯网络拓扑结构的生成算法。 (1)设T = (X1,X2,…,Xd ) 表示变量的一个总体次序。 (2)FORj=1tod DO。 (3)令XT j( ) 表示T 中第j 个次序最高的变量。 (4)令π (XT j( ) ) ={X1,X2,…,XT j( -1) } 表示排在XT j( ) 前面的变量的集合。 (5)从π (XT j( ) ) 中去掉对Xj 没有影响的变量(使用先验知识)。 (6)在XT j( ) 和π (XT j( ) ) 中剩余的变量之间画弧。 (7)ENDFOR。 以图5-3为例解释上述步骤,执行步骤(1)后,设变量次序为(E,D ,HD,HB,CP, BP),从变量D 开始,经过步骤(2)~(7),得到以下条件概率。 .P (D E ) 化简为P (D ) 。 .P (HD E,D ) 不能化简。 .P (HB HD,E,D ) 化简为P (HB D ) 。 .P (CP HB,HD,E,D ) 化简为P (CP HB,HD) 。 .P (BP CP,HB,HD,E,D ) 化简为P (BP HD) 。 基于以上条件概率,创建节点之间的弧(E,HD) 、(D ,HD) 、(D ,HB) 、(HD,CP) 、 (HB,CP) 和(HD,BP) 。这些弧构成了如图5-3所示的网络结构。 算法5.1保证生成的拓扑结构不包括环。这一点的证明也很简单。如果存在环, 至少有一条弧从低序节点指向高序节点,并且至少存在另一条弧从高序节点指向低序 节点。由于算法5.1不允许从低序节点到高序节点的弧存在,因此拓扑结构中不存 在环。 然而,如果对变量采用不同的排序方案,得到的网络拓扑结构可能会有变化。某些拓 扑结构可能质量很差,因为它在不同的节点对之间产生了很多条弧。从理论上讲,可能需 要检查所有d! 种可能的排序才能确定最佳的拓扑结构,这是一项计算开销很大的任务。 一种替代的方法是把变量分为原因变量和结果变量,然后从各原因变量向其对应的结果 变量画弧。这种方法简化了贝叶斯网络结构的建立。一旦找到了合适的拓扑结构,与各 节点关联的概率表就确定了。对这些概率的估计比较容易,与朴素贝叶斯分类器中所用 的方法类似。 107 5.3 贝叶斯算法实例分析 5.3.1 朴素贝叶斯分类器 【例5.1】 应用朴素贝叶斯分类器来解决这样一个分类问题:根据天气状况来判断 某天是否适合打网球。给定如表5-1所示的14个训练实例,其中每天由属性outlook, temperature,humidity和windy来表征,类属性为playtennis。 表5-1 14个训练实例 day outlook temperature humidity windy playtennis 1 sunny hot high weak no 2 sunny hot high strong no 3 overcast hot high weak yes 4 rain mild high weak yes 5 rain cool normal weak yes 6 rain cool normal strong no 7 overcast cool normal strong yes 8 sunny mild high weak no 9 sunny cool normal weak yes 10 rain mild normal weak yes 11 sunny mild normal strong yes 12 overcast mild high strong yes 13 overcast hot normal weak yes 14 rain mild high strong no 现有一测试实例x:,问这一天是否适合打网球? 显然,我们的 任务就是要预测此新实例的类属性playtennis的取 值(yes或no),为此,我们构建了如图5-4所示的朴 素贝叶斯分类器。 图中的类节点C 表示类属性playtennis,其他 4 个节点A1,A2,A3,A4 分别代表4个属性 outlook,temperature,humidity,windy,类节点C 是 所有属性节点的父节点,属性节点和属性节点之间没有任何的依赖关系。根据公式有 V x( ) =argmax c∈{yes,no}P c( )P (sunnyc)P (coolc)P (highc)P (strongc) 贝叶斯算法 实例分析 108 为计算V (x ) ,需要从如表5-1 所示的14 个训练实例中估计出概率:P (yes) , P (sunnyyes) ,P (coolyes) ,P (high yes) ,P (strongyes) ,P (no) ,P (sunny no) , P (coolno) ,P (high no) ,P (strong no) 。具体的计算如下: P (yes) =9/14 P (sunnyyes) =2/9 P (coolyes) =3/9 P (high yes) =3/9 P (strongyes) =3/9 P (no) =5/14 P (sunny no) =3/5 P (coolno) =1/5 P (high no) =4/5 P (strong no) =3/5 所以有 P (yes)P (sunnyyes)P (coolyes)P (high yes)P (strongyes) =0.005291 P (no)P (sunny no)P (coolno)P (high no)P (strong no) =0.0205704 可见,朴素贝叶斯分类器将此实例分类为no。 【例5.2】 应用朴素贝叶斯分类器来解决这样一个分类问题:给出一个商场顾客数 据库(训练样本集合),判断某一顾客是否会买计算机。给定如表5-2所示的15个训练实 例,其中每个实例由属性age,income,student,creditrating来表征,样本集合的类别属性 为buycomputer,该属性有两个不同的取值,即{yes,no} ,因此就有两个不同的类别(m=2)。 设C1 对应yes类别,C2 对应no类别。 表5-2 15个训练实例 age income student creditrating buycomputer ≤30 high no fair no ≤30 high no excellent no 31~40 high no fair yes >40 medium no fair yes >40 low yes fair yes >40 low yes excellent no 31~40 low yes excellent yes ≤30 medium no fair no ≤30 low yes fair yes >40 medium yes fair yes 续表 109 age income student creditrating buycomputer ≤30 medium yes excellent yes 31~40 medium no excellent yes 31~40 high yes fair yes >40 medium no excellent no 现有一测试实例x:(age≤30,income=medium,student=yes,creditrating=fair), 问:这一实例是否会买计算机? 我们的任务是要判断给定的测试实例是属于C1 还 是C2。 根据公式有 V x( ) =argmax c∈{yes,no}P c( )P (age≤30c)P (mediumc)P (yesc)P (fairc) 为计算V (x ) ,计算每个类的先验概率P (Ci ) ,即 P (Ci ) :P (buycomputer=y' es') =9/14=0.643 P (buycomputer=n' o') =5/14=0.357 为计算P (X Ci ) ,i=1、2,计算下面的条件概率: P (age=' ≤30' buycomputer=y' es') =2/9=0.222 P (age=' ≤30' buycomputer=n' o') =3/5=0.6 P (income='medium' buycomputer=y' es') =4/9=0.444 P (income='medium' buycomputer=n' o') =2/5=0.4 P (student=y' es' buycomputer=y' es') =6/9=0.667 P (student=y' es' buycomputer=n' o') =1/5=0.2 P (creditrating=f'air' buycomputer=y' es') =6/9=0.667 P (creditrating=f'air' buycomputer=n' o') =2/5=0.4 X = (age≤30,income=medium,student=yes,creditrating=fair) P (X Ci ) :P (X buycomputer=y' es') =0.222×0.444×0.667×0.667=0.044 P (X buycomputer=n' o') =0.6×0.4×0.2×0.4=0.019 P (X Ci )·P (Ci ) :P (X buycomputer=y' es')·P (buycomputer=y' es') =0.028 P (X buycomputer=n' o')·P (buycomputer=n' o') =0.007 因此,对于样本X ,朴素贝叶斯分类预测buycomputer='yes'。 5.3.2 贝叶斯信念网络应用 使用如图5-3所示的BBN 来诊断一个人是否患有心脏病。下面阐释在不同的情况 下如何做出诊断。 情况一:没有先验信息。