学校编码 :10384 学号 :24320111152296 分类号 密级 UDC 硕士学位论文 朴素贝叶斯分类模型的改进研究 Research on Improving Naïve Bayes Classification Model 朱晓丹 指导教师 : 董槐林教授 专业名称 : 计算机软件与理论 论文提交日期 :2 0 1 4 年 4 月 论文答辩日期 :2 0 1 4 年 5 月 学位授予日期 :2 0 1 4 年月 指导教师 : 答辩委员会主席 : 2014 年月
厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下, 独立完成的研究成 果 本人在论文写作中参考其他个人或集体已经发表的研究成果, 均 在文中以适当方式明确标明, 并符合法律规范和 厦门大学研究生学 术活动规范 ( 试行 ) 另外, 该学位论文为 ( ) 课题 ( 组 ) 的研究成果, 获得 ( ) 课题 ( 组 ) 经费或实验室的 资助, 在 ( ) 实验室完成 ( 请在以上括号内填写课 题或课题组负责人或实验室名称, 未有此项声明内容的, 可以不作特 别声明 ) 声明人 ( 签名 ): 年 月 日
厦门大学学位论文著作权使用声明 本人同意厦门大学根据 中华人民共和国学位条例暂行实施办法 等规定保留和使用此学位论文, 并向主管部门或其指定机构送交学位论文 ( 包括纸质版和电子版 ), 允许学位论文进入厦门大学图书馆及其数据库被查阅 借阅 本人同意厦门大学将学位论文加入全国博士 硕士学位论文共建单位数据库进行检索, 将学位论文的标题和摘要汇编出版, 采用影印 缩印或者其它方式合理复制学位论文 本学位论文属于 : ( )1. 经厦门大学保密委员会审查核定的保密学位论文, 于年月日解密, 解密后适用上述授权 ( )2. 不保密, 适用上述授权 ( 请在以上相应括号内打 或填上相应内容 保密学位论文应是已经厦门大学保密委员会审定过的学位论文, 未经厦门大学保密委员会审定的学位论文均为公开学位论文 此声明栏不填写的, 默认为公开学位论文, 均适用上述授权 ) 声明人 ( 签名 ): 年月日
摘要 摘 要 分类是数据挖掘中的一个重要课题 分类的目的是为了构造出一个分类函数或者分类模型, 这个模型可以将数据库中对应的数据项映射到一个给定的类 数据挖掘的分类一般用在提取描述重要数据类的模型或者预测未来数据趋势 朴素贝叶斯分类模型是当前分类算法的研究热点之一, 它具有结构不复杂 分类精度 高和速度快等优点 运用该模型进行分类的原理是利用训练集构造出一个分类模 型, 如果训练集中有存在噪声实例, 那么它会降低分类器的性能 本文以优 化训练集为研究内容, 探讨了基于单属性有效度和结合双属性有效度的朴素贝叶斯分类改进模型, 通过自定义的单属性有效度和双属性有效度淘汰数据集中的噪声样本, 从而实现训练集优化, 提高分类准确率的目标 本文主要工作如下 : 1 介绍了贝叶斯分类的基本理论和朴素贝叶斯分类模型 2 对几种常用的改进朴素贝叶斯分类模型进行分析: 树扩展型贝叶斯分类模型 半朴素贝叶斯分类模型 贝叶斯信念网络分类模型 3 在使用训练集构建分类器前, 基于贝叶斯理论的思想, 以单属性为研究对象, 通过自定义的单属性有效度淘汰训练集中的噪声实例, 实现训练集的优化 4 在基于单属性有效度的改进模型的前提上, 结合双属性有效度, 发现和淘汰训练集中存在的更多噪声样本, 进一步优化训练集 基于大规模数据及大量的实验结果表明 : 本文提出的改进方法是可行的, 而且能有效的提高分类的准确率 关键词 : 朴素贝叶斯分类模型 ; 单属性有效度 ; 双属性有效度 I
Abstract Abstract Classification is an important task of data mining. The purpose of classification is to construct a classification function or classification model, which can map the unclassified sample in the database to a given class. Classification can be used to extract a model which describes important data or predicts the trend of data. Naive Bayes classification model is one of the research hotspots in current classification algorithms, and compared with other methods, Naive Bayes classification model owns features of simple structure, high classification accuracy and high speed, etc. Training set is used in Naive Bayes classification model to build a classification model, and if there are noise samples in the training set, the performance of the classification will be reduced. Taken optimizing the training set as research content, improved Naive Bayes classification model based on validity of single attribute and combined validity of double attributes are proposed. The noise samples in the training set are eliminated by validity of single attribute and validity of double attributes to achieve the goal of optimizing training set and improving classification accuracy. The main jobs are as follows: 1. The basic theory of Bayes classification and the Naive Bayes classification model are introduced. 2. Several common improved Naive Bayes classification model are analyzed: Semi Naïve Bayes Classifiers (SNBC), Bayes Belief Network (BBN) and Tree Augments Naïve Bayes (TAN). 3. Based on Bayes theory, the noises of the training examples are eliminated by validity of single attribute to optimize the training set before it is used to build classifiers. 4. Under the premise of Naive Bayes classification model based on validity of single attribute, an improved model combined validity of double attributes are proposed in order to discover and delete more noise samples. Experiment results based on mass data show that the proposed method in the II
Abstract dissertation is feasible, and they can effectively improve the classification accuracy. Keywords: Naïve Bayes Classification Model; Validity of Single Attribute; Validity of Double Attributes III
目录 目录 第一章绪论... 1 1.1 课题研究背景和意义... 1 1.1.1 数据挖掘基本理论... 1 1.1.2 数据挖掘的主要任务... 1 1.1.3 数据挖掘的现实意义... 2 1.2 数据挖掘中的分类... 3 1.2.1 分类模型的种类... 3 1.2.2 分类模型的评价标准... 4 1.3 国内外研究现状... 5 1.4 研究内容... 6 1.5 论文的组织结构... 6 第二章贝叶斯理论和朴素贝叶斯分类模型分析... 8 2.1 贝叶斯理论概论... 8 2.1.1 条件概率和乘法定理... 8 2.1.2 全概率公式和贝叶斯定理... 9 2.1.3 极大后验假设与极大似然假设... 9 2.1.4 事件的独立性... 10 2.2 朴素贝叶斯分类模型... 10 2.2.1 朴素贝叶斯分类模型描述... 10 2.2.2 朴素贝叶斯分类模型的实际应用... 13 2.2.3 朴素贝叶斯分类模型的特点... 14 2.3 本章小结... 15 第三章朴素贝叶斯分类模型的改进方法研究... 16 3.1 半朴素贝叶斯分类模型 (SNBC)... 16 3.1.1 半朴素贝叶斯分类模型工作原理... 16 3.1.2 半朴素贝叶斯分类模型优缺点... 19 IV
目录 3.2 贝叶斯信念网络分类模型 (BBN)... 19 3.2.1 贝叶斯信念网络工作原理... 19 3.2.2 贝叶斯网络的应用... 21 3.2.3 贝叶斯网络模型的优缺点... 24 3.3 树增强朴素贝叶斯分类模型 (TAN)... 26 3.3.1 树增强朴素贝叶斯分类模型工作原理... 26 3.3.2 树增强朴素贝叶斯分类模型的优缺点... 29 3.4 本章小结... 30 第四章基于单属性有效度的朴素贝叶斯分类模型研究... 31 4.1 单属性有效度的设定... 31 4.1.1 单属性有效度的设定思想... 31 4.1.2 单属性有效度的设定准则... 32 4.2 基于单属性有效度的朴素贝叶斯分类模型... 35 4.3 实验及结果分析... 36 4.3.1 实验数据... 36 4.3.2 实验平台... 36 4.3.3 实验结果分析... 37 4.4 本章小结... 39 第五章结合双属性有效度的朴素贝叶斯分类模型研究... 40 5.1 双属性有效度的设定... 40 5.1.1 双属性有效度的工作原理... 40 5.1.2 双属性有效度的设定方法... 40 5.2 结合双属性有效度的朴素贝叶斯分类模型... 43 5.3 实验及结果分析... 45 5.3.1 实验数据... 45 5.3.2 实验平台... 45 5.3.3 实验结果分析... 45 5.4 本章小结... 49 第六章总结及展望... 50 V
目录 6.1 总结... 50 6.2 展望... 50 参考文献... 52 攻读硕士期间的研究成果... 57 致谢... 58 VI
Contents Contents Chapter 1 Introduction... 1 1.1 Research Background... 1 1.1.1 Fundamental Theory of Data Mining... 1 1.1.2 Primary Task of Data Mining... 1 1.1.3 Practical Significance of Data Mining... 2 1.2 Classification in Data Mining... 3 1.2.1 Kinds of Classification Model... 3 1.2.2 Evaluation Criteria of Classification Model... 4 1.3 Research Status... 5 1.4 Main Research Contents... 6 1.5 Outline of the Dissertation... 6 Chapter 2 Analysis of Bayesian Theory and Naive Bayes... 8 2.1 Introduction of Bayesian Theory... 8 2.1.1 Conditional Probability and Multiplication Theorem... 8 2.1.2 Whole Probability Formula and Bayes Theorem... 9 2.1.3 Maximum a Posteriori and Maximum Likelihood Estimator... 9 2.1.4 Events Independences... 10 2.2 Naive Bayes Classification Model... 10 2.2.1 Description of Naive Bayes Classification Model... 10 2.2.2 Practical Use of Naive Bayes Classification Model... 13 2.2.3 Characteristics of Naive Bayes Classification Model... 14 2.3 Summary... 15 Chapter 3 Research of Improved Naive Bayes Classification Model 16 3.1 Semi Naive Bayes Classification Model(SNBC)... 16 3.1.1 Work of Semi Naive Bayes Classification Model... 16 3.1.2 Merits and Demerits of Semi Naive Bayes Classification Model... 19 VII
Contents 3.2 Bayesian Belief Network Classification Model(BBN)... 19 3.2.1 Work of Bayesian Belief Network Classification Model... 19 3.2.2 Use of Bayesian Belief Network Classification Model... 21 3.2.3 Merits and Demerits of Bayes Belief Network Classification Model 24 3.3 Tree Augement Naive Bayes Classification Model(TAN)... 26 3.3.1 Work of Tree Augement Naive Bayes Classification Model... 26 3.3.2 Advantages and Disadvantages of Tree Augement Naive Bayes Classification Model... 29 3.4 Summary... 30 Chapter 4 Research of Naive Bayes Classification Model Based on Validity of Single Attribute... 31 4.1 Setting of Validity of Single Attribute... 31 4.1.1 Thought of Setting... 31 4.1.2 Criteria of Setting... 32 4.2 Naive Bayes Classification Model Based on Validity of Single Attribute 35 4.3 Experiments and Results Analysis... 36 4.3.1 Experimental Data... 36 4.3.2 Experimental Platform... 36 4.3.3 Experimental Results and Analysis... 37 4.4 Summary... 39 Chapter 5 Research of Naive Bayes Classification Model Combined Validity of Double Attributes... 40 5.1 Setting of Validity of Double Attribute... 40 5.1.1 Thought of Setting... 40 5.1.2 Method of Setting... 40 5.2 Naive Bayes Classification Model Combined Validity of Double Attributes... 43 5.3 Experiments and Results Analysis... 45 VIII
Contents 5.3.1 Experimental Data... 45 5.3.2 Experimental Platform... 45 5.3.3 Experimental Results and Analysis... 45 5.4 Summary... 49 Chapter 6 Conclusions and Future Work... 50 6.1 Conclusions... 50 6.2 Future Work... 50 References... 52 Publications... 57 Acknowledgements... 58 IX
第一章绪论 第一章绪论 本章首先介绍数据挖掘研究背景, 即数据挖掘的基本理论与概念, 尤其对数 据挖掘中的分类问题作重点介绍 ; 其次, 介绍国内外朴素贝叶斯分类模型的研究 情况 ; 再次, 概括本文的主要研究内容 ; 在本章的最后, 给出论文的组织结构 1.1 课题研究背景和意义 在科技日新月异的信息时代, 计算机网络和数据库技术在商业 生活 科研等各方面发挥了重要的作用 通过计算机网络和数据库, 各种形式的信息被共享和保存 大量信息不仅给人们带来了方便, 而且同时也给人们带来了很多负面问题, 例如 : 信息过量 数据泛滥 真假难辨等导致数据安全难以保证, 以及信息形式的不一致造成在数据处理上增加很多困难等 人类正被信息淹没, 却饥渴于知识 [1] 数据挖掘(Data Mining,DM) [2], 是在此严峻的背景下出现的一门用于挖掘数据中有价值信息的新兴学科 1.1.1 数据挖掘基本理论数据挖掘 (Data Mining), 又称为数据库中有用知识的探索 [3] 数据挖掘的定义是从规模大, 可能有缺漏的 任意的 有噪声的真实数据中获取具有参考价值 容易明白 全新的 符合一定规范的数据 从数据库中提取出来的数据通常可用概念 (Concepts) 规律(Regulation) 规则(Rules) 模式(Patterns) 等形式来表示 数据挖掘包含数据库技术 数学统计学 人工智能 模式识别 机器学习 归纳推理 专家系统等多个领域 [4-6] 1.1.2 数据挖掘的主要任务数据挖掘的主要任务有两个, 它们分别为预测和描述 预测是指通过数据库中已存在的数据信息来推测其他可能存在的未知的数据情况 ; 描述是在大量的数据中发掘出一种可以用来描述数据 容易理解的模型 所要挖掘的知识不同, 相应的挖掘任务也不一样, 可以总结为以下几种 [7-9] : (1) 特征规则 : 是把所有数据满足的概念特征化, 并从中发现潜在的规则 1
朴素贝叶斯分类模型的改进研究 (2) 时间序列分析 (Time series analysis): 是一种用于处理动态数据的统计方法 (3) 分类 : 是数据挖掘中非常重要的一个方法 它的原理是利用已知数据生成特定的模型或者函数, 然后通过该模型或函数将其他未知的数据分派给某个类别, 前提是所给的类别是已知的 目前所使用的分类模型主要有以下几种 : 贝叶斯分类 决策树 粗糙集 神经网络 遗传算法等 实际分类过程中, 应根据 数据集的特点, 选择合适的分类模型, 从而达到最好的分类效果 (4) 关联规则 : 关联规则通过一定的阈值, 如支持度和置信度, 来发现数 据之间是否存在关联性以及关联性的大小, 数据之间的关联性一般用规则的形式来表达 关联规则是数据挖掘中应用较多的 技术较为成熟的技术 (5) 聚类 : 又称为群分析, 是研究分类问题的一种统计分析方法, 通过一定的模式将相似度较高的数据归到一个类中 (6) 预测 : 通过已知的数据构建模型, 并将模型用于预测类别未知的样本所述的类别或者取值 1.1.3 数据挖掘的现实意义数据挖掘技术在生活 工业 商业 科研等方面都有着非常重大的现实意义 首先, 在生活方面, 超市可以借助 啤酒与尿布 原理, 通过数据挖掘技术对以往的销售数据进行挖掘和分析, 从中发现商品间潜在的关联规则, 从而指导其调整货物的摆放模式, 促进销售, 提高营业额 其次, 在工业方面, 比如在制造业 方面, 利用数据挖掘技术进行机器故障诊断 故障排除情况等, 通过对产品整个 生产线进行分析, 从而发现容易出现问题的工序及相关故障因素 再次, 在商业 方面例如在金融方面, 银行可以通过顾客的前期理财记录中分析和挖掘出该顾客的理财偏向, 从而更准确 更有针对性的为其推荐合适的 易接受的理财产品, 促进银行理财产品的销售 最后, 在科研方面, 可以将数据挖掘技术用于卫星 医学等数据量大且复杂的科研领域, 从海量数据中发掘数据的规律, 提高科研工作者的工作效率 2
第一章绪论 1.2 数据挖掘中的分类 1.2.1 分类模型的种类 (1) 贝叶斯方法 贝叶斯理论用于解决不确定性的问题, 它基于数学中的统计学和概率论, 因 此具有牢固的数学基础 贝叶斯分类模型有两种 :NBC 模型和 BNC 模型, 其中 NBC 模型也是本文所要关注的分类模型 NBC 模型 : 它是具有监督和指导的一种学习方法, 其最大的特点就是假定 属性间的相互独立性, 但此条件限制性较强, 现状远远无法满足, 因此很多研究 者研究如何在放宽这个假设的前提下提高分类的性能 虽然如此, 朴素贝叶斯分 [10-11] 类器还是以高精度和高效率以及最小的误分类率等优点取得了较大的成功, 是目前较常使用的分类器之一 BNC 模型 : 它是一个带有概率注释的有向无环图, 图中的每个结点均表示 一个随机变量 若图中的两结点间存在着一条弧, 则表示这两个结点相对应的随 机变量是概率相依的, 反之则是条件独立的 贝叶斯网络分类模型有很多优点, 最突出的是它具有强大的推理能力, 能充分利用已知的数据信息来预测待定类数 据的类别 但是如果数据出现的概率或者事件发生的频率较低时则会造成预测效 果不佳 (2) 决策树 决策树是数据挖掘中较普遍使用的一种分类模型 使用决策树进行分类时, 借助了树的结构原理, 用从根部到叶子节点构成的路径来描述规则 决策树中每 个属性都用一个内节点来描述, 每个类都用一个树节点来表示 决策树分类模型 具有直观 可理解性较强的优点, 但其缺点是如果分类的数据规模比较大 数据 结构比较复杂, 那么处理过程中会由于噪声数据而产生碎片, 增大了分类的难度 决策树算法的典型算法有 C4.5,CART,ID3 等, 其中 ID3 算法是最原始 最 基础的决策树算法, 后续又出了 CART C4.5 CHAID 等改进版算法 其他的, 如 PUBLIC QUEST 以及 SLIQ 等等, 也都是属于决策树的改进算法 (3) 神经网络 3
朴素贝叶斯分类模型的改进研究 人工神经网络 (Artificial Neural Networks [12] ANNs), 简称为神经网络 (NNs) 或连接模型 (Connection Model) ANNs 的工作原理是来自于生物界中的动物神经所构成的网络 ANNs 工作时将内部节点之间相互连接的关系通过系统的复杂程度进行大幅度的调整, 从而实现相关信息的分布处理 使用该模型进行数据挖掘时, 利用它的并行结构 分布存储和并行处理本质的非线性系统 较强的容错性 自适应性等优点, 并且通过反复的训练建立与数据相对应的分类模型, 从该分类模型中获取出特定的方法, 运用到实际的分类中 (4) 遗传算法遗传算法 (Genetic Algorithm [13] 英文简称为(GA), 它的灵感源自于自然淘汰和遗传选择, 是一种简单 易懂的分类方法 它的核心原理是生物的适者生存的自然法则和遗传学 GA 是把整体中的全部的个体作为研究的目标, 通过模拟生物进化过程的全局优化方法, 将较差的原始解通过一个遗传算法, 即繁殖 交叉和变异, 按一定的随机规则迭代搜索和进化, 直至获得最优解 遗传算法是一种新兴的分类算法, 它具有算法简单 效率高 易懂 可同步处理等特点 它已经被应用到生产 生活等各个方面的领域中, 并且效果良好, 使之逐渐成为核心的分类智能算法 (5) 粗糙集理论 粗糙集理论 [14] 研究应用广泛, 对于不确定或者不完整的数据均可用粗糙集 理论作为基础来表达知识 学习及分类 由于粗糙集理论处理的属性必须是离散类型的, 因此在数据预处理时, 需要将数据先进行离散化的处理 运用粗糙集理论分类时, 会先根据数据情况建立相应的等价类, 并且产生这些等价类的数据是不会事先进行划分处理 粗糙集理论用概念的上 下近似和元素间的成员关系函数等来描述知识 如果某些数据类别不能通过属性进行判断和区分, 则可以使用上述方法来描述这些类 粗糙集理论相比较于贝叶斯方法等模型有一个优点, 即只需提供给它数据集信息, 而不需要额外的先验知识 1.2.2 分类模型的评价标准判断分类器性能的优劣, 可以通过下面列出的一些标准进行衡量 [15] (1) 分类正确率 : 在分类前, 每个待测样本都有一个已知的类别, 分类完 4
Degree papers are in the Xiamen University Electronic Theses and Dissertations Database. Full texts are available in the following ways: 1. If your library is a CALIS member libraries, please log on http://etd.calis.edu.cn/ and submit requests online, or consult the interlibrary loan department in your library. 2. For users of non-calis member libraries, please mail to etd@xmu.edu.cn for delivery details.