贝叶斯网络参数学习中的连续变量离散化方法研究∗
2018-05-29刘晓明李盼池刘显德
刘晓明 李盼池 刘显德 肖 红
（东北石油大学计算机与信息技术学院 大庆 163318）
1 引言
在贝叶斯网络的参数学习过程中，可以将新数据输入贝叶斯网络中，进一步更新各节点的概率，这个过程被称为概率繁殖［1］。利用新数据对网络中变量的先验分布进行更新，这是贝叶斯网络学习中的一个非常重要的问题。
在统计学中，参数学习称为参数估计，它有两种基本方法，即最大似然估计法和贝叶斯估计法［2］。目前对于完备数据的参数学习算法已经发展到比较成熟的阶段，但是对于从不完备数据中学习贝叶斯网络的参数却仍是一个亟需攻克的难题。
本文采用不同方法对原始数据进行离散处理，并构建相对应的贝叶斯网络以供后期预测分析使用。本文使用UCI数据库中的transfusion数据集，采自某血液采集服务中心，具体工作包括以下三部分：
1）利用Matlab采用两种不同（等宽法、ChiMerge法）方法对数据进行离散化处理；
2）利用离散后的数据运用Netica进行相应贝叶斯网络的构建，并进行参数学习；
3）利用构建的贝叶斯网络进行简单的预测分析。
2 数据的离散化
2.1 等宽法离散
等宽法是最简单的无监督离散化方法，指将连续变量的取值空间等分为多个取值区间［3］。它需要用户认为的指定离散的区间数目K，然后将数据集的值域{Xmin，Xmax}划分为K个区间，使得每个区间的宽度都相等，都等于(Xmax-Xmin)/K。等宽法虽然简单易于实现，但是存在着固有的局限性，当原始数据的值域中存在偏斜极为严重的点时，会大大影响离散化的效果。
如下，原始数据中的Recency、Frequency、Monetary、Time属性经过无监督的等宽法离散后得到的结果如表1、表2、表3、表4所示。本文在等宽法的离散中，将原始数据的值域等分为3份进行离散，以下表格显示了离散结果的区间名、对应值和每个区间中实例数目占总的实例数的百分比。
表1 Recency的等宽法离散结果
表2 Frequency的等宽法离散结果
表3 Monetary的等宽法离散结果
表4 Time的等宽法离散结果
2.2 ChiMerge法离散
ChiMerge是有监督的，自底向上基于合并的离散化方法［4］。它以卡方分析为基础进行数据的离散化，相邻区间中卡方值最小的两个合并在一起，循环直至计算合并符合停止准则为止。
卡方值的计算公式为
其中，m为每次进行比较的区间数目，此处为2；k为类别数量；Aij表示第i类区间中第j类实例的 数 量 ；表示第j类实例 的 数量；表示总的实例数量的期望频率。
具体算法如下：
1）初始化：根据要离散的属性对数据进行排序，每个数据为一个单独的区间，本文选取的是YNinMar2007属性，即是献血者是否在2007年3月份献过血；
2）计算每两个相邻区间的卡方值，将卡方值最小的两个区间进行合并；
3）判断是否符合循环终止条件，符合则跳出循环，不符合则返回执行2）。
如下，原始数据中的Recency、Frequency、Monetary、Time属性经过有监督的ChiMerge法离散后得到的结果如表5、表6、表7、表8所示。在本文ChiMerge法中，人为设定离散化的区间数目为3个，选取YNinMar2007属性即2007年3月献血者是否有献过血作为类别信息，总共分两类，YNin-Mar2007值为1表示献过血，为0表示没有献过血。以下表格显示了离散结果的区间名、对应值和每个区间中实例数目占总的实例数的百分比。
表5 Recency的ChiMerge法离散结果
表6 Frequency的ChiMerge法离散结果
表7 Monetary的ChiMerge法离散结果
表8 Time的ChiMerge法离散结果
2.3 离散结果分析
从两个离散结果来看，等宽法的弊端显示较为明显，由于只是无监督地划分，前三个维度的数据，即Recency、Frequency和Monetary的离散结果数据过于集中在一个区间里，这是由于原始数据的值域较大而数据分布不均匀导致的。整体看来，等宽区间由于其固有的局限性和原始数据的偏斜程度较大，离散出来的结果较为不理想。ChiMerge法的离散结果比较较为理想，但由于都是需要人为地指定离散的区间数，也存在一定的问题。这需要投入进一步的工作研究，探究如何科学地权衡区间数的选择，使得这两种离散方法更为完善和科学。
3 贝叶斯网络的构造和参数学习
对于之前离散化得出的结果，将748个数据分成两份，随机选取其中500个数据作为训练数据集（training set），其余的248个数据作为验证数据集（testing set）。使用Netica构造相应的贝叶斯网络，进行参数学习，并加入一个效用节点（utility node）和决策节点（decision node）进行简单的预测分析。
3.1 Netica简介
Netica是由加拿大的Norsys公司开发的一款专门用于贝叶斯网络的软件。Netica具有多种构造节点概率表（CPT）的途径：1）可以从文件中导入案例（case file）数据，基于案例通过贝叶斯网络参数学习自动获得；2）基于专家知识获得，可以直接手工编辑输入节点概率表的各项内容；3）手工编辑给出概率公式，计算获得节点概率表。本文通过导入case file进行参数学习获得贝叶斯网络的结构。
3.2 等宽法离散结果构建贝叶斯网络
3.2.1 构造的网络
根据第三章所介绍的等宽法离散后的数据以csv文件格式存储，在Netica软件中由导入案例的方法，作为case file导入并进行参数学习，获得如图1所示的贝叶斯网络，该网络中各个节点的条件概率表分别对应如图2、图3、图4、图5、图6所示。
构造的贝叶斯网络如图1所示。
图1 等宽法离散结果的贝叶斯网络
将Recency作为target node，学习得到的各点条件概率表如下：
1）Recency的条件概率表
图2 Recency的条件概率表
2）Frequency的条件概率表
图3 Frequency的条件概率表
3）Monetary的条件概率表
图4 Monetary的条件概率表
4）Time的条件概率表
图5 Time的条件概率表
5）YNinMar2007的条件概率表
图6 YNinMar2007的条件概率表
3.2.2 预测分析
在构造完成的贝叶斯网络中加入一个效用节点和一个决策节点，选择总的献血量以此预测一个献血者是否会献血的概率。
决策网络如图7所示。
图7 决策网络
决策节点D的条件概率表如图8：
根据预测分析，如果一个献血者的献血总量比较少的话，那他就倾向于不会献血，如果献血量是
一般或者多的话，那他就倾向于会献血。
图8 决策节点的条件概率表
3.3 ChiMerge法离散结果构建贝叶斯网络
3.3.1 构造的网络
使用ChiMerge法离散后的数据同样以csv文件格式存储，在Netica中以case file的形式导入并进行参数学习，得到如图9所示的贝叶斯网络，该网络中各个节点的条件概率表分别对应如图10、图11、图12、图13、图14所示。
构造的贝叶斯网络如图9所示。
图9 ChiMerge法离散结果的贝叶斯网络
将Recency作为target node，学习得到的各点CPT如下：
1）Recency的条件概率表
图10 Recency的条件概率表
2）Frequency的条件概率表
图11 Frequency的条件概率表
3）Monetary的条件概率表
图12 Monetary的条件概率表
4）Time的条件概率表
图13 Time的条件概率表
5）YNinMar2007的条件概率表
图14 YNinMar2007的条件概率表
3.3.2 预测分析
在如图9所示的贝叶斯网络基础上，加入一个效用节点U和一个决策节点D，根据总的献血量以此预测一个献血者是否会献血的概率。
决策网络如图15所示。
图15 决策网络
决策节点D的条件概率表如图16所示。
图16 决策节点的条件概率表
根据预测分析，如果一个献血者的献血总量比较少的话，那他就倾向于不会献血，如果献血量是一般或者多的话，那他就倾向于会献血。
3.4 结果分析
根据两种不同离散方法得出的结果构造出来的贝叶斯网络，我们可以看出，基于原始数据使用不同的离散化方法，得出的离散结果用于构造贝叶斯网络，所构造出来的网络结构是一样的。但是经过case file的加入进行参数学习后，各个节点的节点概率表呈现出了明显的差别。对于等宽法构造出来的贝叶斯网络，跟从原始数据离散后的结果一样，节点Recency、Frequency、Monetary的节点概率表也呈现出了很大程度的倾斜。ChiMerge法离散后的数据构造的贝叶斯网络虽然各节点的节点概率表不尽相同，但根据网络中从Monetary属性引出的决策节点D的条件概率表却大致相近，而等宽法构造的贝叶斯网络决策图对于献血者是否献血的预测则与ChiMerge法出入较大。
4 结语
本文中选用了比较有代表性的两个方法（等宽法、ChiMerge法）对数据进行离散化。根据离散化方法选择的不同，离散出的数据构造出来的贝叶斯网络也不尽相同。等宽法简单易行，但由于其算法固有的局限性，对于具体的数据集要求比较严格，当存在对于值域来说偏斜极为严重的点时，这种类型的离散化方法是极为脆弱的，离散的效果会大大降低。ChiMerge算法属于有监督的离散，在其离散的过程中考虑了类别信息，因此较为科学。但因为需要人为地指定离散的区间数目，由于人类认识的局限性，无法科学地权衡区间的个数以达到最好的离散效果，因此这需要进一步地投入研究，争取能探究出一个科学地权衡区间数的办法，使得这两种离散方法更为科学和完善。
［1］黄影平.贝叶斯网络发展及其应用综述［J］.北京理工大学学报，2013，33（12）：1211-1219.HUANG Yingping.Survey on Bayesian Network Development and Application［J］.Transactions of Beijing Institute of Technology，2013，33（12）：1211-1219.
［2］吴红，王维平，杨峰.贝叶斯网络参数学习中的连续变量离散化方法［J］.系统工程与电子技术，2012，34（10）：2157-2162.WU Hong，WANG Weiping，YANG Feng.Discretization Method of Continuous Variables in Bayesian Network Parameter Learning［J］.Systems Engineering and Electronics，2012，34（10）：2157-2162.
［3］周旋，王磊，朱延广，等.贝叶斯网参数学习中连续变量离散化方法研究［J］.计算机仿真，2009，26（9）：136-139.ZHOU Xuan，WANG Lei，ZHU Yanguang，et al.A Discretization Method of Continuous Variable in Bayesian Network Parameter Learning［J］.Computer Simulation，2009，26（9）：136-139.
［4］李晓毅，徐兆棣，孙笑微.贝叶斯网络的参数学习研究［J］.沈阳农业大学学报，2007-02，38（I）：125-128.LI Xiaoyi，XU Zhaodi，SUN Xiaowei.Study on Parameter Learning of Bayesian Network［J］.Journal of Shenyang Agricultural University，2007-02，38（I）：125-128.
［5］王飞，刘大有，薛万欣.基于遗传算法的Bayesian网中连续变量离散化的研究［J］.计算机学报，2002，25（8）：794-800.WANG Fei，LIU Dayou，XUE Wanxin.Discretizing Continuous Variables of Bayesian Networks［J］.Chinese Journal of Computers，2002，25（8）：794-800.
［6］厉海涛，金光，周经伦，等.贝叶斯网络推理算法综述［J］.系统工程与电子技术，2008，30（5）：935-939.LI Haitao，JIN Guang，ZHOU Jinglun，et al.Survey of Bayesian Network Inference Algorithms［J］.Systems Engineering and Electronics，2008，30（5）：935-939.
［7］Jaeger M.Parameter learning for relational bayesian networks［C］//In：Proceedings of the 24th international conference on Machine learning，ACM，2007：369-376.
［8］Udomsakdigool A，Khachitvichyanukul V.Ant colony algorithm for multi-criteria Job shop scheduling to minimize makespan，mean flow time and mean tardiness［J］.International Journal of Management Science and Engineering Management，2011，6（2）：117-123.
［9］Su J，Zhang H，Ling C X，et al.Discriminative parameter learning for Bayesian networks［C］//In：Proceedings of the 25th international conference on Machine learning，ACM，2008：1016-1023.
［10］Heckerman D，Geiger D，Chickering D M.Learning Bayesian networks：The combination of knowledge and statistical data［J］.Machine learning，1995，20（3）：197-243.
