对一种贝叶斯网络学习算法的改进及试验分析

Improvement to a Dependency Analysis Based Bayesian Network Learning Algorithm and Experiments

贝叶斯网络[4]是上世纪80年代发展起来的一种概率图形模型,它提供了不确定性环境下的知识表示、推理、学习手段,可以完成决策、诊断、预测、分类等任务,已广泛应用于数据挖掘、语音识别、工业控制、经济预测、医疗诊断等诸多领域.

This paper presents a dependency analysis based Bayesian network learning algorithm,which is an improvement to Jie Cheng'algorthm that requires O(N2) CI tests and uses (conditional)Mutual Information as CI test. We redefined the (conditional) MI to reduce the computing complexity of CI test. As a result our algorithm minimizes the number of data retrieving operations,requiring only one data query for each CI test and reduces O(r2) or O(rA+2) basic operations for each CI test. Experiments show our algorithm improves the efficiency of Jie Cheng'algorithm greatly.