选择性贝叶斯分类算法研究

论文摘要

分类是模式识别、机器学习以及数据挖掘中一项基本而又重要的任务。在众多的分类方法中,贝叶斯分类方法因建立在贝叶斯统计学和贝叶斯网络基础上,能够有效地处理不完整数据,并且具有模型可解释、精度高等优点,而被认为是最优分类模型之一。尤其是朴素贝叶斯分类器,虽然结构简单,但在很多情况下却具有相当高的分类精度,可以达到甚至超过其它成熟算法如C4.5的分类精度,而且对噪声数据具有很强的抗干扰能力。自从朴素贝叶斯分类器提出以后,就被应用到了众多领域中,其有效性已经为实践所证明。但是,随着应用领域的扩大,该种分类器的不足也更加明显。朴素贝叶斯分类器要以一个很强的条件独立性假设为前提,即假设在各个类中,每个属性变量（也称作特征）的概率分布独立于其它属性变量的概率分布。然而,实际中的数据一般难以满足这一假设前提。如果不满足这一前提条件,分类器的分类效果往往会明显下降。弥补这一不足的一种有效的方法是利用属性选择去除数据集中的冗余属性,使选择出的属性尽可能地满足条件独立性假设。然后,在选择出的属性子集上构建贝叶斯分类器,即选择性贝叶斯分类器。目前已有不少学者对选择性贝叶斯分类器进行过研究,并给出了一些有效的算法,但这些算法大都是用于完整数据和低维数据。虽然实际中不完整数据大量存在,并且这些数据大都包含着严重影响分类效果和效率的冗余属性和无关属性,然而,由于处理不完整数据的复杂性,目前用于不完整数据的选择性分类算法却很少见。因此,充分利用贝叶斯分类方法能够有效地处理不完整数据的优势,来构造用于不完整数据的选择性贝叶斯分类算法是一项重要的研究课题,这正是本文主要研究内容之一。另外,随着现代信息技术的不断发展,大量的高维数据不断涌现,而朴素贝叶斯简单高效,适于处理高维数据,同时又对属性选择很敏感,因此对用于高维数据的选择性贝叶斯分类算法的研究具有重要的意义,也是本文的另一项主要研究内容。本文的主要贡献如下:（1）通过分析以往在分类过程中对不完整数据的处理方法,给出了一种基于分布的不完整数据分类算法DBCI（Distribution-based Bayesian Classifiers forIncomplete data）。该算法在训练过程中将缺失值的频数合理地分配到其它观测值的频数中。因此,不完整数据集中所包含的信息可以得到充分利用。该算法与分类效果和效率都很突出的不完整数据分类器RBC（Robust Bayes Classifiers）相比,其分类效果与后者相当,而算法的效率明显高于后者。（2）虽然不完整数据集中也通常包含着大量影响分类效果和效率的冗余属性或无关属性,但是,目前用于不完整数据的选择性分类器却极为少见。针对这一问题,基于包装法（wrappers）给出了两个有效的选择性不完整数据分类器。首先,通过分析以往的不完整数据分类算法,构造了选择性不完整数据分类器SRBC（Selective Robust Bayes Classifiers）。与高效的RBC以及DBCI相比,SRBC不仅能获得显著更高的分类准确率,同时还能大幅度地降低冗余属性和无关属性的数目。然后,利用提出的更加高效的DBCl分类器构造了选择性分类器SDBC（Selective Distribution-based Bayesian Classifiers for incomplete data）。与SRBC相比,SDBC的分类准确率和效率都有明显提高。（3）为进一步提高上述SPBC和SDBC的效率,基于混合法构造了三个更加高效的选择性不完整数据分类器。首先,利用一个简化的增益率计算式和SRBC构造了分类器SRBCBG（Selective Robust Bayes Classifiers Based on Gain ratio）。与此同时,利用用于不完整数据的卡方统计量和SRBC构造了分类器CBSRBC（Chi-square-Based Selective Robust Bayes Classifiers）。与SRBC和SDBC相比,SRBCBG和CBSRBC具有更高的分类效率和更好的分类效果。然后,为了构造对大型不完整数据集具有更好的扩展性的选择性贝叶斯分类器,又利用推广的Relief算法和SDBC构造了比CBSRBC和SRBCBG更高效的分类器RBSD（Relief-F-algorithm-Based Selective DBCI）。（4）针对最为常见的高维数据——文本数据,给出了两个用于贝叶斯分类器的多类别文本数据属性评价函数,以构造基于过滤法的选择性贝叶斯分类器。在文本数据集上的分类结果显示,利用这两个属性评价函数构造的选择性贝叶斯分类器具有更好的分类效果。

论文目录

• 致谢
• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 贝叶斯网络的发展及现状
• 1.1.1 贝叶斯网络的学习
• 1.1.2 贝叶斯网络推理
• 1.2 贝叶斯分类算法的发展及现状
• 1.3 存在的问题
• 1.4 本文的主要工作
• 1.5 本文的组织结构
• 第二章 贝叶斯分类算法
• 2.1 贝叶斯网络简介
• 2.2 贝叶斯网络的参数学习
• 2.2.1 完整数据条件下的参数学习
• 2.2.2 不完整数据条件下的参数学习
• 2.3 贝叶斯网络的结构学习
• 2.3.1 完整数据条件下的结构学习
• 2.3.2 不完整数据条件下的结构学习
• 2.4 贝叶斯分类的一般问题
• 2.5 朴素贝叶斯分类器
• 2.6 朴素贝叶斯分类器的扩展
• 2.6.1 半朴素贝叶斯分类器
• 2.6.2 TAN分类器
• 2.6.3 网络扩展的朴素贝叶斯分类器
• 2.6.4 普通贝叶斯网络分类器
• 2.7 选择性贝叶斯分类算法
• 2.7.1 FSS算法
• 2.7.2 FSSJ与BSEJ算法
• 2.7.3 K2-AS算法
• 2.7.4 Info-AS算法
• 2.7.5 SBC算法
• 2.8 本章小结
• 第三章 不完整数据分类算法
• 3.1 几种主要的不完整数据分类算法
• 3.1.1 简单丢弃法和设置特定取值法
• 3.1.2 概率参数优化法
• 3.1.3 健壮贝叶斯分类器
• 3.2 基于分布的不完整数据贝叶斯分类器
• 3.2.1 DBCI分类器的训练过程
• 3.2.2 DBCI分类器的分类过程
• 3.2.3 DBCI分类器的计算复杂度分析
• 3.3 实验
• 3.3.1 实验数据集
• 3.3.2 实验结果与分析
• 3.4 本章小结
• 第四章 基于包装法的选择性不完整数据贝叶斯分类器
• 4.1 包装法
• 4.2 选择性不完整数据分类器SRBC
• 4.2.1 不完整数据分类器的选取
• 4.2.2 其它要素的确定
• 4.2.3 SRBC的算法描述
• 4.3 选择性不完整数据分类器SDBC
• 4.4 实验
• 4.4.1 实验1
• 4.4.2 实验2
• 4.5 本章小结
• 第五章 基于混合法的选择性不完整数据贝叶斯分类器
• 5.1 混合法
• 5.1.1 过滤法
• 5.1.2 混合法
• 5.2 基于混合法的选择性分类器SRBCBG与CBSRBC
• 5.2.1 评价函数的选取
• 5.2.2 SRBCBG与CBSRBC的算法描述
• 5.3 基于混合法的选择性分类器RBSD
• 5.3.1 Relief算法的扩展
• 5.3.2 RBSD的算法描述
• 5.4 实验
• 5.4.1 实验1
• 5.4.2 实验2
• 5.5 选择性不完整数据分类器在实际应用中的意义
• 5.6 本章小结
• 第六章 用于文本数据的选择性贝叶斯分类器
• 6.1 文本分类中的特征选择
• 6.1.1 信息增益
• 6.1.2 互信息
• 6.1.3 卡方统计量
• 6.1.4 优势率
• 6.1.5 文档频数
• 6.1.6 期望交叉熵
• 6.2 文本分类中两种常用的朴素贝叶斯分类模型
• 6.3 两种特征评价函数
• 6.4 实验
• 6.4.1 数据集及实验设置
• 6.4.2 分类效果的评价指标
• 6.4.3 实验结果及分析
• 6.5 本章小结
• 第七章 结束语
• 7.1 本文工作的总结
• 7.2 进一步研究的展望
• 参考文献
• 攻读博士期间发表和已录用的论文
• 学位论文数据集