学校编码 :10384 学号 : 分类号密级 UDC 硕士学位论文朴素贝叶斯分类模型的改进研究 Research on Improving Naïve Bayes Classification Model 朱晓丹指导教师 : 董槐林教授专业名称 : 计算机软件与理

Size: px

Start display at page:

Download "学校编码 :10384 学号 : 分类号密级 UDC 硕士学位论文朴素贝叶斯分类模型的改进研究 Research on Improving Naïve Bayes Classification Model 朱晓丹指导教师 : 董槐林教授专业名称 : 计算机软件与理"

增隗
5 years ago
Views:

1 学校编码 :10384 学号 : 分类号密级 UDC 硕士学位论文朴素贝叶斯分类模型的改进研究 Research on Improving Naïve Bayes Classification Model 朱晓丹指导教师 : 董槐林教授专业名称 : 计算机软件与理论论文提交日期 : 年 4 月论文答辩日期 : 年 5 月学位授予日期 : 年月指导教师 : 答辩委员会主席 : 2014 年月

2 厦门大学学位论文原创性声明本人呈交的学位论文是本人在导师指导下, 独立完成的研究成果本人在论文写作中参考其他个人或集体已经发表的研究成果, 均在文中以适当方式明确标明, 并符合法律规范和厦门大学研究生学术活动规范 ( 试行 ) 另外, 该学位论文为 ( ) 课题 ( 组 ) 的研究成果, 获得 ( ) 课题 ( 组 ) 经费或实验室的资助, 在 ( ) 实验室完成 ( 请在以上括号内填写课题或课题组负责人或实验室名称, 未有此项声明内容的, 可以不作特别声明 ) 声明人 ( 签名 ): 年月日

3 厦门大学学位论文著作权使用声明本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等规定保留和使用此学位论文, 并向主管部门或其指定机构送交学位论文 ( 包括纸质版和电子版 ), 允许学位论文进入厦门大学图书馆及其数据库被查阅借阅本人同意厦门大学将学位论文加入全国博士硕士学位论文共建单位数据库进行检索, 将学位论文的标题和摘要汇编出版, 采用影印缩印或者其它方式合理复制学位论文本学位论文属于 : ( )1. 经厦门大学保密委员会审查核定的保密学位论文, 于年月日解密, 解密后适用上述授权 ( )2. 不保密, 适用上述授权 ( 请在以上相应括号内打或填上相应内容保密学位论文应是已经厦门大学保密委员会审定过的学位论文, 未经厦门大学保密委员会审定的学位论文均为公开学位论文此声明栏不填写的, 默认为公开学位论文, 均适用上述授权 ) 声明人 ( 签名 ): 年月日

4 摘要摘要分类是数据挖掘中的一个重要课题分类的目的是为了构造出一个分类函数或者分类模型, 这个模型可以将数据库中对应的数据项映射到一个给定的类数据挖掘的分类一般用在提取描述重要数据类的模型或者预测未来数据趋势朴素贝叶斯分类模型是当前分类算法的研究热点之一, 它具有结构不复杂分类精度高和速度快等优点运用该模型进行分类的原理是利用训练集构造出一个分类模型, 如果训练集中有存在噪声实例, 那么它会降低分类器的性能本文以优化训练集为研究内容, 探讨了基于单属性有效度和结合双属性有效度的朴素贝叶斯分类改进模型, 通过自定义的单属性有效度和双属性有效度淘汰数据集中的噪声样本, 从而实现训练集优化, 提高分类准确率的目标本文主要工作如下 : 1 介绍了贝叶斯分类的基本理论和朴素贝叶斯分类模型 2 对几种常用的改进朴素贝叶斯分类模型进行分析: 树扩展型贝叶斯分类模型半朴素贝叶斯分类模型贝叶斯信念网络分类模型 3 在使用训练集构建分类器前, 基于贝叶斯理论的思想, 以单属性为研究对象, 通过自定义的单属性有效度淘汰训练集中的噪声实例, 实现训练集的优化 4 在基于单属性有效度的改进模型的前提上, 结合双属性有效度, 发现和淘汰训练集中存在的更多噪声样本, 进一步优化训练集基于大规模数据及大量的实验结果表明 : 本文提出的改进方法是可行的, 而且能有效的提高分类的准确率关键词 : 朴素贝叶斯分类模型 ; 单属性有效度 ; 双属性有效度 I

5 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

6 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

7 目录目录第一章绪论课题研究背景和意义数据挖掘基本理论数据挖掘的主要任务数据挖掘的现实意义数据挖掘中的分类分类模型的种类分类模型的评价标准国内外研究现状研究内容论文的组织结构... 6 第二章贝叶斯理论和朴素贝叶斯分类模型分析贝叶斯理论概论条件概率和乘法定理全概率公式和贝叶斯定理极大后验假设与极大似然假设事件的独立性朴素贝叶斯分类模型朴素贝叶斯分类模型描述朴素贝叶斯分类模型的实际应用朴素贝叶斯分类模型的特点本章小结第三章朴素贝叶斯分类模型的改进方法研究半朴素贝叶斯分类模型 (SNBC) 半朴素贝叶斯分类模型工作原理半朴素贝叶斯分类模型优缺点 IV

8 目录 3.2 贝叶斯信念网络分类模型 (BBN) 贝叶斯信念网络工作原理贝叶斯网络的应用贝叶斯网络模型的优缺点树增强朴素贝叶斯分类模型 (TAN) 树增强朴素贝叶斯分类模型工作原理树增强朴素贝叶斯分类模型的优缺点本章小结第四章基于单属性有效度的朴素贝叶斯分类模型研究单属性有效度的设定单属性有效度的设定思想单属性有效度的设定准则基于单属性有效度的朴素贝叶斯分类模型实验及结果分析实验数据实验平台实验结果分析本章小结第五章结合双属性有效度的朴素贝叶斯分类模型研究双属性有效度的设定双属性有效度的工作原理双属性有效度的设定方法结合双属性有效度的朴素贝叶斯分类模型实验及结果分析实验数据实验平台实验结果分析本章小结第六章总结及展望 V

9 目录 6.1 总结展望参考文献攻读硕士期间的研究成果致谢 VI

10 Contents Contents Chapter 1 Introduction Research Background Fundamental Theory of Data Mining Primary Task of Data Mining Practical Significance of Data Mining Classification in Data Mining Kinds of Classification Model Evaluation Criteria of Classification Model Research Status Main Research Contents Outline of the Dissertation... 6 Chapter 2 Analysis of Bayesian Theory and Naive Bayes Introduction of Bayesian Theory Conditional Probability and Multiplication Theorem Whole Probability Formula and Bayes Theorem Maximum a Posteriori and Maximum Likelihood Estimator Events Independences Naive Bayes Classification Model Description of Naive Bayes Classification Model Practical Use of Naive Bayes Classification Model Characteristics of Naive Bayes Classification Model Summary Chapter 3 Research of Improved Naive Bayes Classification Model Semi Naive Bayes Classification Model(SNBC) Work of Semi Naive Bayes Classification Model Merits and Demerits of Semi Naive Bayes Classification Model VII

11 Contents 3.2 Bayesian Belief Network Classification Model(BBN) Work of Bayesian Belief Network Classification Model Use of Bayesian Belief Network Classification Model Merits and Demerits of Bayes Belief Network Classification Model Tree Augement Naive Bayes Classification Model(TAN) Work of Tree Augement Naive Bayes Classification Model Advantages and Disadvantages of Tree Augement Naive Bayes Classification Model Summary Chapter 4 Research of Naive Bayes Classification Model Based on Validity of Single Attribute Setting of Validity of Single Attribute Thought of Setting Criteria of Setting Naive Bayes Classification Model Based on Validity of Single Attribute Experiments and Results Analysis Experimental Data Experimental Platform Experimental Results and Analysis Summary Chapter 5 Research of Naive Bayes Classification Model Combined Validity of Double Attributes Setting of Validity of Double Attribute Thought of Setting Method of Setting Naive Bayes Classification Model Combined Validity of Double Attributes Experiments and Results Analysis VIII

12 Contents Experimental Data Experimental Platform Experimental Results and Analysis Summary Chapter 6 Conclusions and Future Work Conclusions Future Work References Publications Acknowledgements IX

13 第一章绪论第一章绪论本章首先介绍数据挖掘研究背景, 即数据挖掘的基本理论与概念, 尤其对数据挖掘中的分类问题作重点介绍 ; 其次, 介绍国内外朴素贝叶斯分类模型的研究情况 ; 再次, 概括本文的主要研究内容 ; 在本章的最后, 给出论文的组织结构 1.1 课题研究背景和意义在科技日新月异的信息时代, 计算机网络和数据库技术在商业生活科研等各方面发挥了重要的作用通过计算机网络和数据库, 各种形式的信息被共享和保存大量信息不仅给人们带来了方便, 而且同时也给人们带来了很多负面问题, 例如 : 信息过量数据泛滥真假难辨等导致数据安全难以保证, 以及信息形式的不一致造成在数据处理上增加很多困难等人类正被信息淹没, 却饥渴于知识 [1] 数据挖掘(Data Mining,DM) [2], 是在此严峻的背景下出现的一门用于挖掘数据中有价值信息的新兴学科数据挖掘基本理论数据挖掘 (Data Mining), 又称为数据库中有用知识的探索 [3] 数据挖掘的定义是从规模大, 可能有缺漏的任意的有噪声的真实数据中获取具有参考价值容易明白全新的符合一定规范的数据从数据库中提取出来的数据通常可用概念 (Concepts) 规律(Regulation) 规则(Rules) 模式(Patterns) 等形式来表示数据挖掘包含数据库技术数学统计学人工智能模式识别机器学习归纳推理专家系统等多个领域 [4-6] 数据挖掘的主要任务数据挖掘的主要任务有两个, 它们分别为预测和描述预测是指通过数据库中已存在的数据信息来推测其他可能存在的未知的数据情况 ; 描述是在大量的数据中发掘出一种可以用来描述数据容易理解的模型所要挖掘的知识不同, 相应的挖掘任务也不一样, 可以总结为以下几种 [7-9] : (1) 特征规则 : 是把所有数据满足的概念特征化, 并从中发现潜在的规则 1

14 朴素贝叶斯分类模型的改进研究 (2) 时间序列分析 (Time series analysis): 是一种用于处理动态数据的统计方法 (3) 分类 : 是数据挖掘中非常重要的一个方法它的原理是利用已知数据生成特定的模型或者函数, 然后通过该模型或函数将其他未知的数据分派给某个类别, 前提是所给的类别是已知的目前所使用的分类模型主要有以下几种 : 贝叶斯分类决策树粗糙集神经网络遗传算法等实际分类过程中, 应根据数据集的特点, 选择合适的分类模型, 从而达到最好的分类效果 (4) 关联规则 : 关联规则通过一定的阈值, 如支持度和置信度, 来发现数据之间是否存在关联性以及关联性的大小, 数据之间的关联性一般用规则的形式来表达关联规则是数据挖掘中应用较多的技术较为成熟的技术 (5) 聚类 : 又称为群分析, 是研究分类问题的一种统计分析方法, 通过一定的模式将相似度较高的数据归到一个类中 (6) 预测 : 通过已知的数据构建模型, 并将模型用于预测类别未知的样本所述的类别或者取值数据挖掘的现实意义数据挖掘技术在生活工业商业科研等方面都有着非常重大的现实意义首先, 在生活方面, 超市可以借助啤酒与尿布原理, 通过数据挖掘技术对以往的销售数据进行挖掘和分析, 从中发现商品间潜在的关联规则, 从而指导其调整货物的摆放模式, 促进销售, 提高营业额其次, 在工业方面, 比如在制造业方面, 利用数据挖掘技术进行机器故障诊断故障排除情况等, 通过对产品整个生产线进行分析, 从而发现容易出现问题的工序及相关故障因素再次, 在商业方面例如在金融方面, 银行可以通过顾客的前期理财记录中分析和挖掘出该顾客的理财偏向, 从而更准确更有针对性的为其推荐合适的易接受的理财产品, 促进银行理财产品的销售最后, 在科研方面, 可以将数据挖掘技术用于卫星医学等数据量大且复杂的科研领域, 从海量数据中发掘数据的规律, 提高科研工作者的工作效率 2

15 第一章绪论 1.2 数据挖掘中的分类分类模型的种类 (1) 贝叶斯方法贝叶斯理论用于解决不确定性的问题, 它基于数学中的统计学和概率论, 因此具有牢固的数学基础贝叶斯分类模型有两种 :NBC 模型和 BNC 模型, 其中 NBC 模型也是本文所要关注的分类模型 NBC 模型 : 它是具有监督和指导的一种学习方法, 其最大的特点就是假定属性间的相互独立性, 但此条件限制性较强, 现状远远无法满足, 因此很多研究者研究如何在放宽这个假设的前提下提高分类的性能虽然如此, 朴素贝叶斯分 [10-11] 类器还是以高精度和高效率以及最小的误分类率等优点取得了较大的成功, 是目前较常使用的分类器之一 BNC 模型 : 它是一个带有概率注释的有向无环图, 图中的每个结点均表示一个随机变量若图中的两结点间存在着一条弧, 则表示这两个结点相对应的随机变量是概率相依的, 反之则是条件独立的贝叶斯网络分类模型有很多优点, 最突出的是它具有强大的推理能力, 能充分利用已知的数据信息来预测待定类数据的类别但是如果数据出现的概率或者事件发生的频率较低时则会造成预测效果不佳 (2) 决策树决策树是数据挖掘中较普遍使用的一种分类模型使用决策树进行分类时, 借助了树的结构原理, 用从根部到叶子节点构成的路径来描述规则决策树中每个属性都用一个内节点来描述, 每个类都用一个树节点来表示决策树分类模型具有直观可理解性较强的优点, 但其缺点是如果分类的数据规模比较大数据结构比较复杂, 那么处理过程中会由于噪声数据而产生碎片, 增大了分类的难度决策树算法的典型算法有 C4.5,CART,ID3 等, 其中 ID3 算法是最原始最基础的决策树算法, 后续又出了 CART C4.5 CHAID 等改进版算法其他的, 如 PUBLIC QUEST 以及 SLIQ 等等, 也都是属于决策树的改进算法 (3) 神经网络 3

16 朴素贝叶斯分类模型的改进研究人工神经网络 (Artificial Neural Networks [12] ANNs), 简称为神经网络 (NNs) 或连接模型 (Connection Model) ANNs 的工作原理是来自于生物界中的动物神经所构成的网络 ANNs 工作时将内部节点之间相互连接的关系通过系统的复杂程度进行大幅度的调整, 从而实现相关信息的分布处理使用该模型进行数据挖掘时, 利用它的并行结构分布存储和并行处理本质的非线性系统较强的容错性自适应性等优点, 并且通过反复的训练建立与数据相对应的分类模型, 从该分类模型中获取出特定的方法, 运用到实际的分类中 (4) 遗传算法遗传算法 (Genetic Algorithm [13] 英文简称为(GA), 它的灵感源自于自然淘汰和遗传选择, 是一种简单易懂的分类方法它的核心原理是生物的适者生存的自然法则和遗传学 GA 是把整体中的全部的个体作为研究的目标, 通过模拟生物进化过程的全局优化方法, 将较差的原始解通过一个遗传算法, 即繁殖交叉和变异, 按一定的随机规则迭代搜索和进化, 直至获得最优解遗传算法是一种新兴的分类算法, 它具有算法简单效率高易懂可同步处理等特点它已经被应用到生产生活等各个方面的领域中, 并且效果良好, 使之逐渐成为核心的分类智能算法 (5) 粗糙集理论粗糙集理论 [14] 研究应用广泛, 对于不确定或者不完整的数据均可用粗糙集理论作为基础来表达知识学习及分类由于粗糙集理论处理的属性必须是离散类型的, 因此在数据预处理时, 需要将数据先进行离散化的处理运用粗糙集理论分类时, 会先根据数据情况建立相应的等价类, 并且产生这些等价类的数据是不会事先进行划分处理粗糙集理论用概念的上下近似和元素间的成员关系函数等来描述知识如果某些数据类别不能通过属性进行判断和区分, 则可以使用上述方法来描述这些类粗糙集理论相比较于贝叶斯方法等模型有一个优点, 即只需提供给它数据集信息, 而不需要额外的先验知识分类模型的评价标准判断分类器性能的优劣, 可以通过下面列出的一些标准进行衡量 [15] (1) 分类正确率 : 在分类前, 每个待测样本都有一个已知的类别, 分类完 4

17 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 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.

2

10384 -------- 9601008 UDC---------------------- 1999 1999 1999 ------------------------ ------------------------ 1 2 .4...4 7 14.14..18..22..22..24 3 4.27.32.39 1 2 3 4 5 6 7 8 9 10 11 5 12 6 1 2 3 4

学校编码 :10384 学号 : 分类号 密级 UDC 硕士学位论文 朴素贝叶斯分类模型的改进研究 Research on Improving Naïve Bayes Classification Model 朱晓丹 指导教师 : 董槐林教授 专业名称 : 计算机软件与理

学校编码 :10384 学号 : 分类号密级 UDC 硕士学位论文朴素贝叶斯分类模型的改进研究 Research on Improving Naïve Bayes Classification Model 朱晓丹指导教师 : 董槐林教授专业名称 : 计算机软件与理