Graph-NB:一种**准确的多关系朴素贝叶斯分类算法/刘红岩,陈海亮,Han Jiawei,Yin Xiaoxin
目前,绝大多数的信息存储在多关系数据库中,这些数据库一般具有多个相互存在联系的数据表。多关系数据挖掘致力于从多个表中直接挖掘信息和发现知识,而不是将数据库中的多个表合并成一个表后再进行挖掘。分类是数据挖掘领域中的一种重要技术,它根据数据集的特点构造出一个分类器(或分类模型),利用分类器对未知类别的样本赋予类别。
多关系分类算法大致可以分为两类:**类是使用propositionalization的传统分类算法。由于传统分类算法都是在单个表的基础上实现的,要将这些方法应用到多关系的背景下,需要使用propositionalization方法对数据库进行相应的转换,这种方法容易造成丢失信息,严格地说这类算法不属于多关系分类算法;第二类算法是直接以多个表为挖掘对象而构造分类器的方法。这类算法常见的可分为两种,**种是基 Inductive Logic Programming的方法,如FOIL,TILDE,ILP—RE,1BC,1BC2等;第二种将传统分类方法与多关系的相结合产生的方法。其中包括将朴素贝叶斯分类方法应用到多关系背景下的方法,如CrossMine和Mr-SBC等。这些方法的共同特点是没有对数据库中的表进行选择,只要是直接或间接地与目标表(包含分类属性的表)相连接的表都考虑在内,这不仅会使算法效率降低,有时也会降低分类准确率。
为此,本文提出一种基于语义关系图的多关系朴素贝叶斯分类算法——Graph—NB算法。Graph—NB首先通过深度优先或广度优先策略遍历语义关系图中的所有表并收集相应的概率信息,然后通过应用多关系朴素贝叶斯分类算法,比较使用语义关系图中不同表时得到的训练集分类准确度来选取*优点对语义关系图进行裁剪简化,*后使用裁剪优化的语义关系图对测试集进行分类。该算法经过大量实验证明在效率和准确度方面均有提高。
……