IEEEJAS的个人博客分享 http://blog.sciencenet.cn/u/IEEEJAS

博文

一种学习稀疏BN最优结构的改进K均值分块学习算法

已有 201 次阅读 2020-7-29 17:54 |系统分类:博客资讯

贝叶斯网络是:系统描述变量之间因果关系的网络模型,是一种有向无环图。适用于表达和分析不确定性和概率性的事件,应用于有条件地依赖多种控制因素的决策,可以从不完全、不精确或不确定的知识或信息中做出推理。然而传统结构学习算法在处理高维数据时呈现出计算负担过大,在合理时间内难以得到期望精度结果的问题。因此研究更加高效的结构学习算法对于贝叶斯网络的研究具有重要意义。


结构学习算法是根据数据学习得到BN网络中各个节点间的因果关系,并根据这些关系构建BN结构,而正确的网络结构也是进一步进行参数学习重要基础。但是现有的传统结构学习算法存在以下问题:


(1)精确学习算法在处理高维数据时会出现维数灾难,无法在可接受的时间内获得结果;

(2)近似学习算法在一定程度上提高了学习的速度,但是获得的结果精度不能令人满意。


此外,近些年提出了一些较为新颖的分块学习算法,在学习策略上采用分而治之的方式学习网络结构,但是其根本还是一种近似学习。


本文针对较为新颖的分块学习算法进行改进,提出了学习稀疏 BN 最优结构的改进 K 均值分块学习算法(Optimal structure-improved Kmeans algorithm, OS-IKM algorithm)。该算法主要分为四步:


(1)由改进的K均值算法对网络进行分块;

(2)引用MMPC算法得到网络的无向图构架;

(3)调用Merge函数确定块与块之间的边,并假设边的方向,找到所有可能的图结构;

(4)对所有可能的图结构进行动态规划学习,根据BIC评分找到最优网络。


image005.png

K均值划分后使用MMPC习得的网络结构示意图


image007.png

根据Merge函数找到的所有块间可能的图结构


实验表明OS-IKM 算法相较于非分块经典结构学习算法有明显的时间优势, 能大大降低时间复杂度; 相比现有分块结构学习算法, OS-IKM 算法有一定的时间优势, 如对 Alarm 网络大约减少了 25 %的时间消耗; 根据汉明距离和 BIC 评分, OS-IKM算法达到了和目前现有算法一致的精度, 并有略微提升, 且保证最终习得的网络是全局最优网络。OS-IKM 算法是对大规模稀疏 BN 最优结构学习的一种可行算法。


引用格式:高晓光, 王晨凤, 邸若海. 一种学习稀疏BN最优结构的改进K均值分块学习算法. 自动化学报, 2020, 46(5): 923-933. 

链接:http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180837

作者简介


高晓光 西北工业大学电子信息学院教授. 1989 年获得西北工业大学飞行器导航与控制系统博士学位. 主要研究方向为贝叶斯和航空火力控制.

E-mail: cxg2012@nwpu.edu.cn


王晨凤 西北工业大学电子信息学院硕士研究生. 2017年获得西北工业大学学士学位. 主要研究方向为贝叶斯网络和数据挖掘. 本文通信作者.

E-mail: chen-cc@mail.nwpu.edu.cn


邸若海 西北工业大学电子信息学院博士后研究生. 2016年获得西北工业大学系统工程专业博士学位. 主要研究方向为小数据集条件下贝叶斯网络结构学习和参数学习. 

E-mail: diruohai@nwpu.edu.cn




http://blog.sciencenet.cn/blog-3291369-1244154.html

上一篇:多智能体深度强化学习的若干关键科学问题
下一篇:基于对称三角模糊集的股票投资者情绪传播模型

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-9-23 06:08

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部