组合数据下贝叶斯网络构建算法研究

孙晶 化越 赵会群

（北方工业大学信息学院 北京市 100144）

1 引言

贝叶斯网络以概率论和图论作为基础，通过有向无环图和条件概率表来表示随机变量之间的依赖关系。由于贝叶斯网络具有结合先验经验对不确定性知识进行有效推理和决策等特性，它已被应用在交通，故障检查和医学等领域当中[1，2，3]。贝叶斯网络结构学习算法一直以来都是贝叶斯网络研究的热点，其目的就是寻找到能够较好拟合数据集的网络结构[4]。由于传统的贝叶斯网络构造算法中，为了求得节点之间的依赖关系的评分函数，依赖对节点的指数级别的遍历过程，造成了时间复杂度过高，限制了大数据集的训练和学习，尤其是在数据源复杂和不同领域数据组合构建贝叶斯网络的情况更是如此。本文提出了组合数据下贝叶斯网络构建算法。首先训练不同领域数据的贝叶斯网络结构，再通过融合算法进行融合，解决因结点过多带来算法效率较低的问题。此外，本文利用K2 算法学习局部贝叶斯网络，但是K2 算法对于每一种结构，都要使用评分函数进行评分，这使K2 算法的计算强度大。针对此问题，本文提出K2 改进算法，新算法在评分的过程中通过减少评分函数的调用次数，减少算法的计算量，提高算法效率。

2 K2改进算法

K2 改进算法是在评分过程中加入了阈值ρ。对每个结点和可能成为其父亲结点进行评分，之后将评分值与阈值进行比较，如果评分值大于阈值且没有达到父亲结点个数上限，便将评分值所对应的父亲结点加入到最优父亲集合。K2 改进算法步骤为假设每个结点没有父亲结点，根据输入结点次序，排在当前结点前的结点皆有可能成为其父亲结点，假设Pre(Xi)为当前结点可能父亲结点集合，πi为最优父亲结点集合。利用K2 评分公式，如式（1）所示，计算将当前节点Xi和Pre(Xi)中每个节z1,l=1,2,…m,的评分Score，并计算阈值ρ。比较z1的评分Score 和阈值ρ 的大小，若Score＞ρ，则将z1加入πi中。当结点的父亲个数达到父亲结点上限个数，结点所有可能的父亲结点集合已经搜索完，这两个条件满足其中一个条件时，终止再为当前结点X_i 寻找最优父亲结点。

与K2 算法相比，改进算法不再对所有可能的结构进行评分，而是只对当前结点和每一个父亲结点分别进行评分，减少了K2 评分函数的使用，从而提高学习网络的质量并减少所需的计算量。本文对阈值取值有四种选择：（1）所有评分的均值。（2）所有评分的中位数。（3）所有评分之间产生随机数。（4）对于每个结点都设定一个阈值ρ。这时阈值ρ 的取值为每个结点的评分的随机数。

3 贝叶斯网络融合算法

在开始融合之前需要为贝叶斯网络结构中的结点和边进行打标签。为了保证融合网络结构过程中结点的有序性，需要根据每个结点所代表的实际意义为每个结点和每一条边打上标签。接着，将所有局部贝叶斯网络的结点和网络结构中重复的边作为初始网络G=(V,E)。为了融合后保留最多边和信息，将Ew加入到网络结构G中，其中Ew是在局部贝叶斯网络中出现的边但却不存在于G。为了保留最多的信息，将Ew中的边全部加入G 是最理想的情况，但这不适于所有情况，且易造成融合网络结构复杂或存在冗余边。因此在加入G 的时，文本基于原贝叶斯网络结构评分值对加入的边进行筛选，具体步骤为在改进K2 算法学习局部贝叶斯网络的过程中，分别得到局部贝叶斯网络中每条边评分值进行存储.分别给予局部网络结构的评分最小值不同的权重，计算出来加权平均评分值作为融合网络的边的阈值。若加入初始网络的边的评分大于等于阈值，则加入其中。在得到融合贝叶斯网络结构后，基于最大似然估计法求出条件概率表。对于根结点概率，可以根据结点不同取值的出现频率，作为根节点的概率参数。对于节点的条件概率，可由给定父结点集的值时，结点不同取值的出现频率求得。

表1：数据来源

表2：数据集展示

4 实验分析

本文选取2009 至2019年十年间宏观因素、股票以及房地产三方面，一共27 个数据来构建贝叶斯网络结构。14 个宏观因素分别从4 个途径获取，其中从开源数据集萝卜投研中获得居民消费水平、供应货币量、商品消费品总额、工业增加值、消费者信心指数和证券投资者信心指数、汇率；从中国人民银行官网获得存款利率、准备金利率，贷款利率、个人商业住房贷款利率和个人公积金贷款利率；从新浪财经爬取股票新闻数据；从国务院办公室爬取股票政策和新闻政策。11 个股票数据主要利用Tushare 数据库开源接口调用，获取沪深300、中国石油、宝钢股份、中国建筑、中国联通、中国中车、长江电力、格力电器、恒瑞医药、贵州茅台和中国平安；2个房地产数据分别从Tushare 数据库中获取地产指数以及从安居客网页上爬取房价数据。具体数据获取的内容如表1所示。

构建贝叶斯网络结构所需要的数据为离散变量，进行实验前需要对数据进行清洗和离散化，离散化后变量取值如下：

经过离散化后对于新闻类数据，得到了每个月利好股票新闻个数和每个月利空股票新闻个数。离散化处理后，股票新闻有三种取值[0，1，2，3]。0 表示小于100 个，1 表示大于100 并且小于300个，2 表示大于300 并且小于500 个，3 表示大于500 个。对于政策类数据，得到了每个月利好股票政策个数、每个月利空股票政策个数、每个月利好房地产政策个数和每个月利空房地产政策个数。股票和房地产政策有三种取值[0，1，2，3]，0 表示小于5 个，1表示大于5 并且小于10 个，2 表示大于10 并且小于20 个，3 表示大于20。其余数据均为每月涨幅度，有三种取值[0,1,2]，当月涨跌幅为(0,+∞)，即比上月上涨，变量取值为1；当月涨跌幅为(-∞,0)，即比上月下降，变量取值为0；当月涨跌幅等于0，即与上月持平，变量取值为2。

为进行实验，本文将数据整理为三个数据集，分别为股票数据集、房地产数据集和股票房地产组合数据集。其中股票数据集有24个特征，房地产数据集有15 个特征，股票房地产组合数据集有31个特征，具体特征如表2所示，具体特征描述如离散处理后部分所示。

将K2 算法和K2 改进算法分别在3 个集中选择不同结点个数进行运行，统计K2 评分函数的使用次数，如图1所示。

从图1 可以看出，与传统的K2 算法相比，改进算法减少了评分函数的使用次数，降低了计算量。随着结点个数增长，两种算法在计算量上的差距越来越明显。

下面进行阈值选取的实验，在阈值分别取所有评分的平均值，中位数以及随机产生评分的均值的情况下，比较改进算法和K2 算法生成的贝叶斯网络结构的边的数量以及两个网络结构的相似度。通过实验发现阈值选取的效果并不好，和K2 算法所得贝叶斯网络结构的相似度最高只有89.58%。在下面实验当中，阈值的选取不再只有一个，计算出每个结点的评分，在每个结点评分值区间内随机生成一个值作为阈值。利用3 组数据集，每个数据集进行了100次实验，统计了100 次实验中网络结构与K2 算法所得网络结构得相似度，如图2所示。

由图2 可以看出，在房地产数据集中相似度最高为91.56%。在股票数据集中相似度最高为91.84%。在股票和房地产数据集中相似度最高为91.36%。由以上实验可以知道，当选择一个合适阈值时，改进算法准确率可在90%以上。利用融合算法把股票贝叶斯网络结构和房地产贝叶斯网络结构进行融合，并且在不同数据量的情况下比较融合算法与K2 算法的运行时间，如图3所示。

从图3 可以看出K2 算法消耗大量的运行时间，而融合算法的运行时间明显减少，并且融合算法对样本容量的大小不敏感，具有处理大数据集的能力。

5 结束语

本文提出的组合数据下贝叶斯网络构建算法，首先对K2 算法进行修改，将阈值加入到K2 评分过程中，得到结点依赖关系，来减少评分函数计算量大的问题，并通过贝叶斯网络结构融合的方法，解决结点增加带来的运行时间过长的问题。算法能够随着样本数量的增加保持其稳定性，并通过实验结果证明了K2 改进算法和贝叶斯网络结构融合算法的可行性。

图1：评分函数调用次数比较

图2：相似度分析

图3：运行时间比较