基于贝叶斯网络工具箱的贝叶斯学习和推理_蒋望东
中图分类号:TP311 文献标识码:A 文章编号:1009-2552(2007)02-0005-04
基于贝叶斯网络工具箱的贝叶斯学习和推理
蒋望东1,林士敏2
(1.湖南财经高等专科学校信息管理系,长沙410205;2.广西师范大学计算机科学系,桂林541004)
摘 要:采用MATLAB语言编制的贝叶斯网络工具箱(Bayesian Networks Toolbox,B NT)可实现贝叶斯网络结构学习、参数学习、推理和构建贝叶斯分类器,此工具箱在贝叶斯学习编程方面非常灵活。介绍了用贝叶斯网络工具箱解决贝叶斯学习和推理问题,并给出了两个实例。
关键词:贝叶斯学习;贝叶斯网络工具箱;贝叶斯推理
Bayesian learning and inference algorithm based on
Bayesian Networks Toolbox
JIANG Wang-dong1,LIN Shi-min2
(1.Departm ent of Information Management,Hunan Financial&Eco nomic College,C hangsha410205,China;
2.C omputer Science Department,Guangxi Normal University,Guilin541004,C hina)
Abstract:Bayesian Networks Toolbox(B NT)based on MATL AB can implement Bayesian str ucture learning, parameter learning,inference algorithm in brief and construct Bayesian classifier.This toolbox is ver y agility in Bayesian programming.This paper introduces using BNT solving Ba yesian learning and infer ence algorithm, and pr esents two instances.
Key words:Bayesian learning;Bayesian Networks Toolbox;Bayesian inference algorithm
1 贝叶斯网络与贝叶斯分类器[1-2]
贝叶斯网络是在不确定性环境下有效的知识表
示和概率推理模型,是一种流行的图形化决策分析
工具。贝叶斯分类器指的是基于贝叶斯网络学习方
法的分类器。设有变量集U={A1,A2,…,A n,C},
其中A1,A2,…,A n是实例的n个属性变量,实例可
用向量x i=(a1,a2,…,a n)表示,其中,a i是A i的
值,令C为类变量,c表示C的值。应用贝叶斯定理,
实例x i属于类c j的概率为:
p(c j|a1,a2,…,a n)=p(a1,a2,…,a n|c j)p(c j) p(a1,a2,…,a n)
=
αp(a1,a2,…,a n|c j)p(c j)(1)其中,α是正则化因子,p(c j)是类c j的先验概率, p(c j|a1,a2,…,a n)是类c j的后验概率,先验概率独立于训练数据集,而后验概率反映了样本数据对类c j的影响。
依据概率的链式规则,式(1)可以表示为:
p(c j|a1,a2,…,a n)=αp(c j)∏n i=1
p(a1,a2,…,a i-1,c j)(2)贝叶斯分类模型的关键就是如何计算p(a i| a1,a2,…,a i-1,c j)。目前,不同贝叶斯分类模型的区别就在于,它们以不同的方式来求p(a i|a1,a2,…, a i-1,c j)。
实例:e(a1,a2,…,a n)为c类的概率为p(c|e) =
p(a1,a2,…,a n|c)p(c)
p(a1,a2,…,a n)
。实例e被分到c的最
大后验概率的类C＊中,g(e)=arg max
c
p(c|a1, a2,…,a n),g(e)称为贝叶斯分类器。
贝叶斯分类器是一种特殊的贝叶斯网络,它选取一个变量作为类变量,其余的变量作为属性变量。
收稿日期:2006-09-14
基金项目:清华大学智能技术与系统国家重点实验室开放课题(99002)
作者简介:蒋望东(1971-),男,硕士,湖南财经高等专科学校讲师,主要研究方向为人工智能、机器学习和数据挖掘。
—
5
—
贝叶斯分类器家族有三类分类器,朴素贝叶斯分类器NBC (Na ve Bayes Classifier ),树扩展朴素贝叶斯分类器TANC (Tree Augmented Na ve Bayes Classifier )和贝叶斯网络分类器B NC (Bayesian Net w or k Classifier )。NBC 的结构最简单,它基于属性变量条件独立的假设,B NC 最能与领域模型吻合,但学习算法复杂,TANC 介于NBC 和BNC 两者之间。
2 贝叶斯网络工具箱简介
[3-4]
MATLAB 作为一种拥有高速性能数值计算能力的通用科技计算语言,简单易用且功能强大,程序移植性比较好。它集成了数值分析、符号计算、图视能力、文字处理、可视化建模和实时控制能力,适合多学科、多部门的发展需求。基于MATL AB 的贝叶斯网络工具箱BNT 是Kevin P .Murphy 基于MATLAB 语言开发的关于贝叶斯网络学习的软件包,提供了许多贝叶斯网络学习的底层基础函数库,支持多种类型的结点(概率分布)、精确推理和近似推理、参数学习和结构学习、静态模型和动态模型。BNT 是个完全免费的软件包,其代码完全公开,系统的可扩展性良好。2.1 贝叶斯软件包BNT 中贝叶斯网络的表示方式
由于MATLAB 的基本数据单元是维数不加限制的矩阵,用户无需考虑大量的有关矩阵的运算该采用何种算法等低层问题,更不必深入了解相应算法的具体细节,因而对用户算法语言方面的要求十分宽松。因此,在贝叶斯软件包BNT 中,采用的贝叶斯网络的表示方式为矩阵方式。即用矩阵的形式表示贝叶斯网络的结构,若结点i 到结点j 有一条弧,则对应矩阵中(i ,j )值为1,否则为0。如图1所示的贝叶斯网络,其结构的矩阵表示形式如图2所示
。
图1 表示5个变量间因果关系的Bayesian 网 图2 矩阵表示法
2.2 贝叶斯软件包B NT 中贝叶斯网络结构学习算法函数
贝叶斯软件包BNT 为人们提供了较为丰富的结构学习函数,它们是:
①学习树扩展贝叶斯网络结构的TANC 算法learn struct tan ()。
②数据完整条件下学习一般贝叶斯网络结构的K2算法learn struct K2()、贪婪搜索GS (Greedy Search )算法learn str uct gs ()和爬山HC (Hill Climbing )算法learn struct hc ()等。
③缺失数据条件下学习一般贝叶斯网络结构的最大期望E M (Expectation Maximization )算法learn struct E M ()和马尔可夫链蒙特卡罗MC MC (Markov Chain Monte Carlo )learn struct mcmc ()算法。2.3 贝叶斯软件包B NT 中贝叶斯网络参数学习算法函数
贝叶斯软件包B NT 同时还提供了较为丰富的参数学习函数,它们是:
①完整数据时,学习参数的方法主要有两种:最大似然性估计learn params ()和贝叶斯方法ba yes update params ();
②数据缺失时,如果已知网络拓扑结构,用EM 算法来计算参数,倘若未知网络拓扑结构,贝叶斯软件包B NT 提供的方法是结构最大期望SE M (Str uctural E M )算法learn struct E M ()。2.4 贝叶斯软件包B NT 中贝叶斯网络的推理机制及推理引擎
为了提高运算速度,使各种推理算法能够有效应用,B NT 工具箱采用了引擎机制,不同的引擎根据不同的算法来完成模型转换、细化和求解。整个推理过程如图3所示
。
图3 推理过程
贝叶斯软件包B NT 提供了多种推理引擎,主要的有:
①联合树推理引擎jtree inf engine ();
②全局联合树推理引擎global joint inf
engine ();
③信念传播推理引擎belprop inf engine ();④变量消除推理引擎var elim inf engine ()。
3 基于BNT 的贝叶斯网络学习举例
[5]
现有由某移动通信部门提供的10000条原始数据,经过清洗、处理异常等工作,获取了1250条符合要求的侯选数据。结合电信市场得到的先验知识,选取了下列流失变量:本月话费下降比率、上月话费
—
6—
下降比率、是否呼叫转移到网外、与联通用户通话比例、是否拨打1001(联通服务热线电话),分别标记为A,B,C,D,E,即贝叶斯网络模型中的节点,得到侯选数据集,用Class标记该样本的用户状态值,“1”表示在网,“0”表示离网。
在BNT平台进行贝叶斯网络学习的源代码及运行结果如下(%贝叶斯学习举例,结构学习是K2算法,参数学习是最大后验):
n=6;
ns=[3,3,2,2,2,2];
names={′A′,′B′,′C′,′D′,′E′,′Class′};
A=1;B=2;C=3;D=4;E=5;Class=6;
order=[456321]; %指定节点次序
max fan in=2;
result matrix=zeros(ns(Class),ns(Cl as s));
%读入训练数据集
fn=′bdata0313.txt′;
l oad(fn); %装入测试例文件
data train1=bdata0313′;
[num attrib num cas es]=s ize(data train1);
data train=zeros(num attri b,num cas es);
%根据实例进行网络结构学习
dag gbn=zeros(n,n);
dag gbn=learn struc t K2(data trai n,ns,order,′max fan in′, max fan in);
bnet2=mk bnet(dag gbn,ns);
%对生成的结构进行参数学习
priors=1;
seed=0;
rand(′state′,seed);
for i=1:n
bnet2.CPD{i}=tabular CPD(bnet2,i,′CPT′,′uni f′,′prior type′,′dirichlet′,′dirichlet type′,BDeu′,′dirichl et weight′,priors);
end
bnet4=bayes update params(bnet2,data train);
CP T3-cell(1,n);
for i=1:n
s=struct(bnet4.CPD{i});
CPT3{i}=s.CPT;
end
%画出图形
draw graph(dag gbn
)
图4 客户流失分析模型
从贝叶斯网络学习的结构分析,影响客户流失
的因素是D(与联通用户通话比例),E(拨打联通热
线1001),与C(呼叫转移到网外)无关,同时客户流
失倾向将导致A(上月话费下降),B(前月话费下
降)。条件概率表则表明了各个节点之间相互影响
的程度,如图4所示。
4 基于BNT构建贝叶斯分类器实验
平台MBNC[6]
目前市面上还没有一个现成的贝叶斯分类器实验平台,要建构一个贝叶斯分类器需要考虑很多细
节问题,不能集中精力研究具体算法,这样效率较
低。B NT中的各种函数虽然非常丰富,但比较零散,
没有条理。因此,选用BNT软件包作为原型,进行
二次开发,建构了贝叶斯实验平台MBNC(Ba yesian
Networks Classifier using Matlab)[6],实现了多种贝叶
斯分类器模型。MB NC实验平台包含如下5个模
块:数据预处理模块、结构学习模块、参数学习模块、
分类推理模块、准确性评估模块。可以完成数据的
预处理、贝叶斯分类器结构学习和参数学习算法的
验证、分类算法的准确性评估,以及进一步研究分类
算法的优化。选用UCI[7](University of California in
Irvine)的实验数据集,数据集的选取与分类器准确
性评估方法与文献[1]一致,如表1所示。
表1 数据集的概况
数据集属性类别训练测试数据集属性类别训练测试Australian142690CV5Hepatitis19280CV5 Breaks92683CV5Iris43150CV5 Car641880CV5Letter1626150005000 Cleve102296CV5L ymphograph184148CV5 Corral62128CV5Mofn3-7-101023001024 Crx152653CV5Nurs ery8211025CV5 Diabetes82768CV5Pi ma52768CV5 Flare1021066CV5segment1871540770 German1521000CV5Shuttle s mall8738661934 Gl as s97214CV5Vehicle184846CV5 Glass292163CV5Vote162435CV5 Heart132270CV5Waveform211833004700
—
7
—
表2 实验结果数据
数据集NBC 文献结果TANC -CMI 文献结果TANC -MI BNC -K2BNC -GS Aus tralian 86.9486.2384.9381.3083.6285.5186.66Breaks 97.6597.36
96.9195.75
96.9196.7697.06Car 87.3991.2891.8192.1391.28Cleve 83.3982.7680.3479.0682.3783.0583.05Corral 86.485.8899.295.3284100100Crx 87.5486.2285.3983.7784.1586.3187.07Diabetes 77.7874.4876.9975.1378.9578.1777.78Flare 80.5679.4683.182.7482.6382.8282.54German 75.372.872.771.373.7Glas s 75.7168.5774.2965.7170.48Gl as s28583.7583.758575.63Heart 83.3381.4883.782.9683.779.2683.33Hepatitis 9091.2586.2585.0091.258586.25Iris 9495.3395.3394.6794Letter 74.9674.9685.3883.4484.476.7883.74L ymphograph 84.8379.7284.1466.8779.3178.6275.86Mofn3-7-10
86.6286.4290.1491.7091.590.2389.63Nurs ery 88.4490.7591.7692.5891.26Pima 79.2275.5176.7375.1377.5278.8277.51Segment 92.0894.8195.0694.8195.58Shuttle
s mall 98.8199.4899.4899.5999.69Vehicle 64.8558.2872.6667.8672.7868.5271Vote 90.1190.3495.489.2092.4193.193.1Waveform2178.7278.4778.0277.0475.6平均值
84.57
85.69
85.32
84.82
85.08
不同的数据集是在完全同等的环境下进行运算的,第3列是文献[1]中NBC 实验结果,第5列是文
献[1]中TANC 实验结果。空格表示文献[1]中没有列出的数据。实验结果如表2所示。所有算法的参数学习均采用BDeu 先验,先验值priors 取1,推理算法采用全局联合树推理算法。
由表2可知,NBC 和T ANC 的正确率均比Fried -man 文献[2]的结果高,T ANC -MI 算法和T ANC -C MI
算法的分类准确性差不多,T ANC -C MI 要略高于T ANC -C MI ,BNC 介于NBC 和T ANC 之间,B NC -GS 略高与BNC -K2。实验结果表明基于MBNC 实验平
台上设计的3类贝叶斯分类器是有效和正确的。3种分类器在不同的数据集里的结果也有差异。
Corral 数据集是一个7个属性(A0,A1,B0,B1,
Irrelevant ,Correlated ,Class )的人工数据集,简写为(A ,B ,C ,D ,E ,F ,Class )。其中,Class 是类结点,A 跟B
相关,C 跟D 相关,E 与Class 不相关,F 与Class 相关,干扰较大,其表达的关系式是(A xor B )or (C xor D )。NBC 的分类准确性就较低;TANC -CMI 算法能够比较准确的学习到网络的结构,TANC -MI 算法
就不行。TANC -CMI 算法考虑了类节点的概率,故在有些类结点与属性结点强相关的数据集,其分类效率比TANC -MI 要好;BNC 的2种算法虽然学习
的网络结构不同,但均准确的学习到网络结构,将结点E “排除”在外,其分类准确率都是100%。
图5列出了用这5种算法学习Corral 数据集得出的不同贝叶斯分类器网络结构,结构图均是由graphhviz 图形可视化软件包画出
。
图5 各种算法学习得到的贝叶斯网络结构
(下转第31页)
—
8—
进行基于包的通信时控制消息需要预估同步参数,额外的控制头长度会增加能量消耗。一个充分的降低能量消耗的方法是降低同步消息头长度,这是可以通过简化同步机制来实现的。
(4)可以在传感器网络中引入多速率机制(Multi-rate),其原理是针对不同的消息采用不同的发送速率,发送速率越高传输距离也越远。在无线传感器网MAC协议中可以使用这种方法,将RTS CTS ACK 控制消息使用较高的速率发送,数据消息使用较低的速率发送,这样可以有效降低隐藏站问题(hidden station problem)和暴露站问题(exposed station prob-lem)的影响,提高传输能量效率。
4 MAC协议的发展趋势
由于无线传感器网络具有能量受限的特点,许多的研究者都试图使用一种新的MAC协议来改善其节能性能。迄今为止,还没有一种MAC协议可以作为通用的标准。将来MAC协议的研究可从以下几个方面来展开:
(1)在对MAC协议的设计上可以考虑跨层设计,将MAC,IP,物理层上面的控制因素融合到一起,从整体上设计MAC协议,例如IP层根据MAC层的冲突情况来进行路由选择。
(2)将基于竞争的MAC协议和免竞争的MAC 进行结合。虽然竞争消除的协议实现起来相对复杂,但是它有优越的节能特性,所以将两种类型的MAC协议进行结合,能进一步优化网络性能。
(3)在保证一定的节能性的前提下,在各种性能指标之间进行折中。而对于特定的协议,各种指标不能同时达到最优。所以,在保证协议简单性和广泛适用性的前提下,研究综合指标更好的新协议是一个开放性的课题。
(4)增强协议对QoS业务的支持。随着各种应用的发展,能为不同业务提供不同的服务质量保障显得越来越重要。对于具有QoS支持能力的无线传感网络的MAC协议也将有待进一步研究。
5 结束语
本文分析了无线传感器网络能量消耗的原因,并对无线传感器网络中的MAC层协议当前所取得的研究成果进行了总结,分析了每种协议的优缺点并作了比较。最后对MAC层的节能技术进行了探讨,以便无线传感器网络MAC层协议的近一步研究和改进。
参考文献:
[1] Demirkol I,Ers oy C.MAC protocols for wireless sens or networks:a
survey[J].Communications Magazine,IEEE,2006:115-121. [2] Wei Ye,Heidemann J.An energy-efficient MAC protocol for wireles s
sens or net works[C].INFOCO M2002.IEEE,2002:1567-1576. [3] Brownfield M I,Mehrj oo K.Wireless sens or network energy-adaptive
MAC protocol[C].Consumer Communications and Net working Confe-
rence,2006:778-782.
[4] Heinz elman W R,Chandrakasan A.Energy-efficient communicati on
protocol for wirel ess microsensor networks[J].Syste m Sci ences,2000:
10.
[5] Qingchun R,Qilian L.A c ontention-based energy-efficient MAC
prot ocol for wirel es s s ensor net works[C].Wireless Communicati ons and
Networking Conference,IEEE,2006:1154-1159.
[6] Sangheon Pac k,Jaeyoung Choi.TA-MAC:Tas k Aware MAC Proto-
col for Wireless Sensor Networks[C].Vehic ular Technology Confe-
rence,2006.VTC2006-Spring.IEEE63rd.
[7] Gungor V C,Akan O B.DST:delay s ensitive transport in wireles s
s ensor networks Computer Net works[C].2006International Sympo-
s ium,2006:116-122.
[8] Liu Zhenz hen,Elhanany I.R L-MAC:A QoS-Aware Reinforcement
Learning based MAC Protocol for Wireless Sensor Networks[C].Net-
working Sens ing and Control,2006.ICN SC'06.2006:768-773. [9] Changsu S,Young-Bae K.A traffic aware,energy efficient MAC
protoc ol for wireles s s ensor networks,Circuits and Systems[C].IEEE
International Symposium,2005:2975-2978.
责任编辑:肖滨
(上接第8页)
5 结束语
通过两个实例说明了基于MATLAB的贝叶斯网络工具箱的强大功能,是学习和利用贝叶斯方法的好工具。而且用法比较灵活,只需对其有关模块进行适当修改,即可用来解决许多实际问题。
参考文献:
[1] Friedman N,Golds z midt M.Building class ifiers using Bayesian Net-
work[C]Proceedings AAAI-96,Thirteent h National Conference on Artificial Intell igence,1996:1227-1284.
[2] Friedman N.Bayesian network class ifiers[J].M achine Learning,1997
(29):131-163.
[3] Kevin P Murphy.The Bayes Net Toolbox for Matlab[EB OL].
[2001].http:www.cs.ubc.ca～murphyk.
[4] BNT软件包[EB OL].[2005].http:www.cs.ubc.ca～murphyk
Software BNT bnt do wnload.ht ml.
[5] 叶进,林士敏.基于贝叶斯网络的推理在移动客户流失分析中
的应用[J].计算机应用,2005,3(25):673-675.
[6] 程泽凯,林士敏,陆玉昌,等.基于M atlab的贝叶斯分类器实验
平台M BNC[J].复旦学报,2004,5:729-732.
[7] UCI数据[EB OL].[2004].http:https://www.sodocs.net/doc/1518015733.html,～mlearn ML-
Repos itory.html.
责任编辑:么丽苹
—
31
—