推荐星级：
- 1
- 2
- 3
- 4
- 5
基于蚁群节点寻优的贝叶斯网络结构算法研究
资料介绍
K2算法是学习贝叶斯网络结构的经典算法。针对K2算法依赖最大父节点数和节点序的不足,以及蚁群算法搜索空间庞大的问题,提出了一种新的贝叶斯结构学习算法-MWST-ACO-K2算法。该算法通过计算互信息建立最大支撑树(MWST),得到最大父节点数;然后利用蚁群算法(ACO)搜索最大支撑树,获得节点顺序;最后结合K2算法得到最优的贝叶斯网络结构。仿真实验结果表明,该方法不仅解决了K2算法依赖先验知识的问题,而且减少了蚁群算法的搜索空间,简化了搜索机制,得到较好的贝叶斯结构。最后将该算法应用到冀东水泥回转窑的实际数据中,构建水泥回转窑的贝叶斯网络结构,提高了故障诊断的准确率。
部分文件列表
| 文件名 | 大小 |
| 基于蚁群节点寻优的贝叶斯网络结构算法研究.pdf | 2M |
部分页面预览
（完整内容请下载后查看）仪
器
仪
表
学
报
38
1
期
Vol. 38 No. 1
Jan． 2017
第
卷
第
Chinese Journal of Scientific Instrument
2017
1
月
年
*
基于蚁群节点寻优的贝叶斯网络结构算法研究
1
1
2
1
1
，
刘浩然 孙美婷
，
李
， ，
刘永记 刘
雷
彬
( 1．
066004; 2．
066004)
燕山大学电气工程学院 秦皇岛
燕山大学信息科学与工程学院 秦皇岛
: K2
。
算法是学习贝叶斯网络结构的经典算法 针对
K2 ，
算法依赖最大父节点数和节点序的不足 以及蚁群算法搜索空间庞
摘
要
，
大的问题 提出了一种新的贝叶斯结构学习算法
-MWST-ACO-K2
。
( MWST) ，
得到最
算法 该算法通过计算互信息建立最大支撑树
K2 。
算法得到最优的贝叶斯网络结构 仿真实验
;
大父节点数 然后利用蚁群算法
( ACO)
，
;
搜索最大支撑树 获得节点顺序 最后结合
，
结果表明 该方法不仅解决了
K2
， ， ，
算法依赖先验知识的问题 而且减少了蚁群算法的搜索空间 简化了搜索机制 得到较好的贝叶
。 ， ，
斯结构 最后将该算法应用到冀东水泥回转窑的实际数据中 构建水泥回转窑的贝叶斯网络结构 提高了故障诊断的准确率
。
: ;
关键词 互信息 蚁群优化
; K2
;
;
算法 贝叶斯网络结构学习 水泥回转窑
: A : 520． 20
国家标准学科分类代码
+
: TH165 ． 3
中图分类号
文献标识码
Study on Bayesian network structure learning algorithm based on
ant colony node order optimization
1
1
2
1
1
Liu Haoran ，Sun Meiting ，Li Lei ，Liu Yongji ，Liu Bin
( 1． School of Information Science and Engineering，Yanshan University，Qinhuangdao 066004，China;
2． School of Electrical Engineering，Yanshan University，Qinhuangdao 066004，China)
Abstract: K2 algorithm is the classical learning algorithm of Bayesian network structure． Aiming at the problems that K2 algorithm
depends on the maximum number of parent nodes ＆ node order and ant colony optimization algorithm has large search space，this paper
proposes a new Bayesian structure learning algorithm - MWST-ACO-K2 algorithm． Firstly，through calculating the mutual information，
the algorithm establishes the Most Weight Supported Tree ( MWST) and obtain the maximum number of parent nodes． Secondly，ant
colony optimization algorithm is adopted to search the Most Weight Supported Tree and obtain the node order． Finally，combining with
K2 algorithm，the proposed algorithm can obtain the optimal Bayesian network structure． The simulation experiment results show that the
proposed algorithm not only solves the problem that K2 algorithm relies on prior knowledge，but also reduces the search space of ant
colony algorithm，simplifies the search mechanism and obtains good Bayesian structure． The proposed algorithm was applied to the
operation data of the cement rotary kiln in Jidong Cement Company，established the Bayesian network structure model of the cement
rotary kiln and achieved precise and rapid fault diagnosis．
Keywords: mutual information; ant colony optimization ( ACD) ; K2 algorithm; Bayesian network structure; cement rotary kiln
。
数据挖掘和软件测试等领域的研究热点
BN 、
学习由参数学习 结构学习和推理分析三部分组
1
引
言
， ， 。
成 其中参数学习是基础 结构学习是核心 一般贝叶斯
，
结构是根据专家知识来确定的 但由此方法得到的结构
( Bayesian network，BN)
贝叶斯网络
又称因果概率
具有强大的知识推
理 直观的表达能力 清晰的拓扑结构及方便的决策机制
［1］
。 ，
模型无法保证客观性和准确性 因此 如何从观测数据
，
，
网 是图论与概率论结合的产物
。 ，
中学习贝叶斯结构引起了国内外学者的思考 目前 完
、
、
: 1)
全从观测数据中学习贝叶斯结构主要有两种方法
条
， ， 、
等优点 影响力逐年扩大 已经成为人工智能 模式识别
、
: 2016-07
Received Date: 2016-07
收稿日期
*
:
基金项目 国家自然科学基金
( 51641609) 、 ( F2016203354)
河北省自然科学基金 项目资助
144
3 8
卷
仪
器
仪
表
学
报
第
，
件独立性法 通过测试节点变量间的条件独立性关系来
I( X; Y) ＞ 0 。 I( X; Y) ＞ 0 ，
当 说明随机变量
X
Y
间
和
和
［2］
; 2)
— ，
打分 搜索法 按照
获取最优表达这些关系的结构
，
存在弧但不确定方向 故用无向边
X-Y
，
代替 并且
I( X; Y)
一定的搜索策略和评分准则来获取评分最高的网络结构
， 。 ，
越大 说明变量间的依赖性越强 反之 说明随机变量
X
［3］
。
作为最优结构
Y
， 。
相互独立 不存在相对应的弧 因此互信息值的大小
和
-
打分 搜索法是构建
BN
，
结构最常见的方法 而评分
。
可以作为一种启发性知识来引导蚂蚁对边的选择
。
函数的选取和搜索方法的选择是该方法的两个关键
目
MWST
。
是利用互信息得到的一种树状网络结构
在
［3］
: K2
、
贝叶斯狄利
前应用比较多的评分函数包括
度量
，
最大支撑树的构建过程中 只保留具有最大互信息的无
［4］
( Bayesian Dirichlet，BD)
、
克雷评分
贝叶斯信息准则
， ，
向边 并且遍历所有的随机变量 即可完成最大支撑树的
［5］
［14］
( Bayesian information criterion，BIC)
评分 和最短描述
。
建立
由于最大支撑树中的无向边表示两随机变量
［6］
( minimum description length，MDL)
。
搜索算法主
长度
，
间的紧密程度 转化到贝叶斯结构中即为父节点与子节
［7］
［8］
［9］
、
、
要有爬山算法
遗传算法
模拟退火法 和蚁群算法
。
点之间的关系 故根据最大支撑树中节点的连接关系
，
。
等元启发算法 蚁群算法以多种形式被应用于贝叶斯网
。
可以得到最大父节点数 μ
［10］
，
络结构的学习中 如
De Campos L． M．
等人 提出基于
2． 2 ACO
节点寻优
结构是一个有向无环图
K2
ACOB
，
算法 该算法有着较好的学
评分和蚁群算法的
BN
( directed acyclic graph
［11］
;
习精度和效率 冀俊忠等人 将约束方法与
ACOB
算法
DAG) ，
故准确地判断节点间的父子关系是非常必要的
。
，
进行有效的融合 在算法求解速度和处理大规模数据的
MWST
，
中的无向边代表最大互信息关系 因此在
MWST
［12］
;
能力上有着较大的改进 胡云安等人 将爬山法和模式
BN
。
结构中 所以通过
中出现的边必然存在于最终的
ACO MWST
BN
。
构造的速度 由上述文献结论可
算法相结合加快了
， ，
的无向边进行搜索 确定边的方向
算法对
进而获得节点的排序
ACO
: 、
知 蚁群算法具有分布式特性 鲁棒性强及易与其他算法
。
，
相结合的优点 所以蚁群算法在构建贝叶斯结构方面表
。
算法是一种用来寻找最优解的机率性算法
。
现出很大的优越性
K2
m
，n 。
为蚂蚁数量 为贝叶斯结构中节点的数量 为了
设
，
针对
最大支撑树
( ant colony optimization，ACO)
算法依赖最大父节点数和节点序的问题 将
，
满足无环的约束条件 在完成一次循环前不允许蚂蚁选
( most weight supported tree，MWST)
和蚁群算
MWST-
，
择已经 访 问 过 的 节 点 该 过 程 由 禁 忌 表
tabu
。
控 制
，
进行结合 提出
法
tabu ( s)
k
k s ， k
表示蚂蚁 的禁忌表中第 个元素 即蚂蚁 走
ACO-K2
。
算法 该算法首先利用最大支撑树得到最大父
s
过的第 个节点
。
; ，
节点数 其次在无环约束条件下 利用蚁群算法对最大支
，
初始时刻 蚂蚁
k( k = 1，2，…，m)
被随机分配到
，
撑树进行搜索获得节点序 从而解决了
K2
算法依赖先验
MWST
i( i = 1，2，…，n) ， 1 。
如图 所示
的节点
。 ，
知识的问题 同时 该算法利用最大支撑树限制了蚁群
， ，
的搜索空间 简化了搜索机制 降低了蚁群算法陷入局部
， BN
最优的风险 为
，
结构的构建提供了一种新思路 具有
。
一定的实用价值
2
MWST-ACO-K2
算法的设计原理
，
首先利用变量间最大互信息关系建立最大支撑树
1
图
蚂蚁转移图
。 ，
得出最大父节点数 μ 其次 通过蚁群算法搜索最大支
Fig． 1 The ant transition diagram
。 ， ，
撑树得到节点序 ρ 最后 在 μ 和 ρ 已知的前提下 结合
K2 ACO
，
评分函数获得贝叶斯结构及评分 为
ACO ，
算法多次迭代 找到评分最
算法的信
t
， i k
时刻 位于节点 的蚂蚁 在当前的候选集中选
在
。
息素更新提供依据
经
j
取节点 的转移概率公式为
:
α β
［ ( t) ］［ ( t) ］
η
ij
BN
。
高的
结构
τ
ij
k
P ( t)
ij
=
( 2)
α β
［ ( t) ］［ ( t) ］
η
ir
2． 1
最大支撑树
τ
∑
ir
r
allowed
k
∈
［13］
。
互信息 是表示随机变量间的相互依赖强度 以任
:
式中 α 和 β 分别表示信息素和启发式信息的相对重要
X
Y
，
来说明 互信息
I( X; Y)
:
意两个随机变量
和
表示为
; allowed = { 1，2，…，n} － tabu
程度
允许选择的节点 τ
k
表示蚂蚁 下一步
k
k
P( X，Y)
I( X; Y)
=
P( X，Y) log
( 1)
;
( t)
t a
表示 时刻在边 上的信息素
ij
。
∑
ij
P( X) P( Y)
XY
，
起始时刻 各条边具有相等的信息素 τ
( 0)
=
(
τ τ 为
0
ij
0
: P( X，Y)
X
Y
，P( X)
的联合概率
X
为变量
式中
为变量
I( X; Y)
和
) ; ，
常数 η 为启发式信息函数 根据评分函数的可分离性
ij
。
的概率 由于
0 ， : I( X; Y) = 0
因此分为两种情况
≥
全部评论(0)