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

A Block Learning Algorithm With Improved K-means Algorithm for Learning Sparse BN Optimal Structure

目前贝叶斯网络(Bayesian networks,BN)的传统结构学习算法在处理高维数据时呈现出计算负担过大、在合理时间内难以得到期望精度结果的问题.为了在高维数据下学习稀疏BN的最优结构,本文提出了一种学习稀疏BN最优结构的改进K均值分块学习算法.该算法采用分而治之的策略,首先采用互信息作为节点间距离度量,利用融合互信息的改进K均值算法对网络分块;其次,使用MMPC(Max-min parent and children)算法得到整个网络的架构,根据架构找到块间所有边的可能连接方向,从而找到所有可能的图结构;之后,对所有图结构依次进行结构学习;最终利用评分找到最优BN.实验证明,相比现有分块结构学习算法,本文提出的算法不仅习得了网络的精确结构,且学习速度有一定提高;相比非分块经典结构学习算法,本文提出的算法在保证精度基础上,学习速度大幅提高,解决了非分块经典结构学习算法无法在合理时间内处理高维数据的难题.

At present,the traditional structure learning algorithm of Bayesian networks(BN)shows the problem of excessive computational burden and difficulty in obtaining the desired accuracy in a reasonable time when processing high-dimensional data.In order to learn the optimal structure of sparse BN under high-dimensional data,this paper proposes a block learning algorithm with improved K-means algorithm for learning sparse BN optimal structure.The algorithm adopts the strategy of divide and conquer.Firstly,we use mutual information as the distance between nodes,and the improved K-means algorithm with mutual information is used to block the network.Secondly,the MMPC algorithm is used to obtain the skeleton of the whole network.According to the skeleton,the possible connection directions of all edges between the blocks are found,so that all possible graph structures are found;after that,structural learning is performed sequentially for all possible graph structures;finally,the best BN is found by using scoring function.Experiments show that compared with the existing block structure learning algorithm,the proposed algorithm not only learns the optimal structure of the network,but also improves the learning speed definitely.Compared with the non-blocking classical structure learning algorithm,the learning speed of the algorithm proposed in this paper is greatly improved on the basis of ensuring accuracy,which solves the problem that the traditional algorithms cannot process high-dimensional data in a reasonable time.