一种局部打分搜索型限制性贝叶斯网络结构学习算法

摘要

贝叶斯网络是用概率方法解决分类问题的有效工具,但学习贝叶斯网络是一个non-deterministic polynomial-time(NP)难题.以往的限制性学习算法大都假设网络结构中的结点具有基本相同的父结点数目,这往往与现实不相符的.为了学习更符合实际数据分布的限制性网络结构,进一步提高分类器的性能,本文对网络中每一个结点单独限制其父结点的数目,各个结点间是否存在父子关系是由它们之间的依赖强度所决定的.本文采用条件互信息方法度量依赖关系,这是因为条件互信息方法不但能够度量网络中各个结点之间的依赖关系,而且能够从整体上对网络结构性能进行打分.条件互信息的分解属性可以将这两者联系起来,通过对每一个结点局部限制的策略,可实现整体网络结构优化.基于这些思想,本文提出了一种学习限制性贝叶斯网络结构的局部打分搜索算法,通过此算法在20个加州大学欧文分校(University of California,IV Vine,UCI)的标准数据挖掘数据集合上与BDeu打分算法,基于最小描述长度的打分算法(minimum description length,MDL)打分算法,基于条件互信息的打分算法(conditional mutual information,CMI)打分算法和tree augmented naive bayes(TAN)算法等的比较,充分表明了本文所提出的策略具有较低的平均误分类率.