论文部分内容阅读
贝叶斯网络的学习问题一直是知识发现领域的重要研究方向,目前主要有两种贝叶斯网络结构学习算法:基于评分搜索的方法,基于依赖分析的方法。然而,贝叶斯网络的学习问题还没有完全被解决,由于在实际应用中,领域变量的数量一般是非常大的,随着变量个数的增加学习复杂度呈指数级别增长,如何有效地降低算法的学习复杂度成为关键问题。为了解决这个问题,有些研究者提出在贝叶斯网络的学习过程中使用专家知识作为指导,如根据专家知识对属性变量进行排序,或者使用专家知识进行属性子集的选择等等,这种方法被证明是十分有效的。在本文中,我们将考虑在关系数据库中存在的各种数据依赖关系,并把它们作为一种有价值的专家知识应用于贝叶斯网络的构造过程中。本文所提出的贝叶斯网络分类模型称为基于函数依赖与局部多值依赖的朴素贝叶斯(FM-NB),它继承了NB具有简单网络结构的优点,且保留了TAN能够表达属性之间的相互依赖关系的优势,从而放松了条件独立性假设。它在对数据集预处理的过程中,使用关联规则技术挖掘出属性之间存在的函数依赖与局部多值依赖关系,然后在分类过程中使用这些数据依赖删除冗余属性及构造初始的网络结构。我们通过分析数据库中的函数依赖关系,根据Armstrong公理给出与之对应的概率推理规则,并且发现在函数依赖右侧的属性对于分类来说是冗余的,从而可以在构造分类器之前挖掘出数据集中蕴含的函数依赖,然后使用它们删去冗余属性,如此可以降低算法的计算复杂度。对于数据库中的多值依赖关系,根据其自身的特点,论证了多值依赖及嵌入多值依赖与条件独立性之间的关系,为把它们运用到贝叶斯网络的学习过程中奠定了基础。由于多值依赖对属性集的限制条件较强,但它蕴含了条件独立性,而嵌入的多值依赖在现实生活中应用比较广泛,为了结合两者的优点,提出局部多值依赖的概念。为了把函数依赖与局部多值依赖运用到贝叶斯网络中,我们讨论了它们在不同情况下分别对应的局部网络结构,在构造贝叶斯网络时首先运用这些局部结构生成初始的网络结构,然后在此基础上构造整个网络,如此不仅保持了属性之间的相互依赖关系,而且简化了网络的构造过程。为了验证FM-NB的分类效果,我们对该模型进行了实现,在对连续属性进行离散化时使用混合的离散化方法,即根据不同属性的取值特点选择适当的离散化方法,从而能够最大程度地保留属性中所蕴含的信息,以保证分类器的性能;如果样本中存在空值,那么直接删掉该样本。对于来自UCI数据库中的9组数据集,在每组数据集上把FM-NB与其它三种分类模型进行了实验对比,分别为:基于向前顺序选择的选择贝叶斯分类器(SNB-SFS),使用经典浮动搜索策略的树增强贝叶斯分类器(TAN-CFS),使用关联规则获得分类规则的分类器(GARC)。实验结果表明,算法FM-NB具有较高的分类精度,且在相同支持度的条件下能挖掘出比GARC更多的规则。