（计算机应用技术专业论文）基于聚类的朴素贝叶斯分类模型的研究与应用.pdf

基于聚类的朴素贝叶斯分类模型的研究与应用 摘要 分类是数据挖掘领域中重要的研究分支，国内外己经取得了令人瞩目 的成就。朴素贝叶斯分类模型由于计算商效、精确度高，并具有坚实的理 论基础而得到广泛的应用。然而，朴素贝叶斯分类模型的条件独立性假设 和数据的完备性要求限制了对实际数据的应用。借鉴k - m e a n s 算法，用朴素 贝叶斯分类算法来解决分类问题，既能发挥k - m e a n s 算法的局部搜索能力， 又能提高朴素贝叶斯分类的准确度，从而更好地解决分类问题。主要工作如 下： 1 介绍分析聚类分析中的k m e a n s 算法和朴素贝叶斯分类算法；阐述 了朴素贝时斯分类的理论基础；讨论几种常见的贝叶斯分类模型。 2 将聚类算法引入到朴素贝叶斯分类研究中，提出一种基于聚类的朴 素贝叶斯分类算法( c n b c ) 。用k m e a n s 算法对原始数据中的完整数据子集 进行聚类，计算缺失数据子集中的每条记录与k 个簇重心之间的相似度， 把记录赋绘距离最近的一个簇，并用该簇相应的属性均值来填充该记录的 缺失值，然后用朴素贝叶斯分类算法对处理后的数据集进行分类。实验结 果表明，与朴素贝叶斯分类模型相比，基于聚类的朴素贝叶斯分类模型具 有较高的分类准确率。 3 基于聚类的朴素贝叶斯分类模型在高校教学管理中的应用。通过用 基于聚类的朴素贝叶斯分类算法建立大学生就业考研预测模型，充分利 用往届学生就业、考研的先验知识，指导学生根据自身的条件对以后的道 路做出合理地选择。 关键词：朴素贝叶斯分类聚类k m e a n s 算法学生模型 r e s e a r c ha n d a p p l i c a t i o n o fn a i v e b a y e s i a n c l a s s i f i c a t i o nm o d e lb a s e do i lc l u s t e r i n ga l g o r i t h m s a b s t r a c t t h ec l a s s i f i c a t i o ni sa ni m p o r t a n tr e s e a r c hb r a n c hi nt h ed a t am i n i n g d o m a i n t h e r ea r em a n ya m a z i n ga c h i e v e m e n t sh a v eb e e no b t a i n e d o w i n gt o i t sh i g h l ye f f i c i e n c i e sa n dh i g h l yp r e c i s ec a l c u l a t i o n ，a sw e l la si t ss t r i c t t h e o r e t i c a lf o u n d a t i o n ，n a i v eb a y e s i a nc l a s s i f i e rh a so b t a i n e dw i d e s p r e a d a p p l i c a t i o n h o w e v e r ，i t sc o n d i t i o ni n d e p e n d e n c ea s s u m p t i o na n dp e r f e c t i o n d a t ar e q u i s i t i o nl i m i ti t sr e a la p p l i c a t i o n t h el o c a ls e a r c h i n ga b i l i t yo f k m e a n sa l g o r i t h mi se x e r t e d ，a n dt h ep r e c i s eo fn a i v eb a y e s i a nc l a s s i f i e r i m p r o v e d i tc a ns o l v ec l a s s i f i c a t i o np r o b l e me f f e c t i v e l y t h em a i nw o r ko f t h ed i s s e r t a t i o ni sa sf o l l o w s ： 1 i n t r o d u c i n ga n da n a l y z i n gk - m e a n sa l g o r i t h m so fc l u s t e r i n ga l g o r i t h m s a n dn a i v eb a y e s i a nc l a s s i f i e ra l g o r i t h m t h eb a s i ct h e o r yo fn a i v eb a y e s i a n i s s t u d i e d ，a n ds o m ec o m m o nm o d e l so fn a i v eb a y e s i a nc l a s s i f i e r a r e d i s c u s s e d 2 an a i v eb a y e s i a nc l a s s i f i c a t i o nb a s e do nc l u s t e r i n gp r i n c i p l e ( c n b c ) b yi n t r o d u c i n gc l u s t e r i n ga l g o r i t h mi n t on a i v eb a y e s i a nc l a s s i f i c a t i o n t h e s i m i l a r i t yb e t w e e ne v e r yr e c o r d e ri na b s e n td a t as u b s e t sa n dt h ec e n t e r sk c l u s t e ri sc a l c u l a t e db yc l u s t e r i n gc o m p l e t ed a t as u b s e t so fi n i t i a ld a t ab y k - m e a n sa l g o r i t h m ，t h e nt h er e c o r d e ri ss e tt ot h en e a r e s tc l u s t e ra n dt h e a b s e n tv a l u eo ft h er e c o r di sf i l l e db yt h ec o r r e s p o n d i n ga t t r i b u t eo ft h ec l u s t e r , f i n a l l y , t h eh a n d l e d d a t as e ti sc l u s t e r e db yn a i v eb a y e s i a nc l a s s i f i c a t i o n a l g o r i t h m t h ee x p e r i m e n t ss h o wt h a tn a i v eb a y e s i a nc l a s s i f i c a t i o nb a s e do n c l u s t e r i n ga l g o r i t h m sh a st h eh i g h e rp r e c i s eo fc l u s t e r i n gc o m p a r i n gw i t h n a i v eb a y e s i a nc l a s s i f i c a t i o n 3 t h em o d e lo fn a i v eb a y e s i a nc l a s s i f i e rb a s e do nc l u s t e r i n ga l g o r i t h m s i sd e s i g n e dt oh e l pt h es t u d e n t st os e l e c te m p l o y m e n to rc o n t i n u es t u d y i n gi n u n i v e r s i t y b yc o n s t r u c t i n gt h em o d e la n du s i n gt h ee x p e r i e n c eg a i n e db yt h e s t u d e n t si nt h ep a s ti nt h e i rs e l e c t i o no fs p e c i a l t i e s ，s t u d e n t sc a nb a s et h e i r c o n d i t i o n st os e l e c tt h e i rw a y k e y w o r d s ：n a i v eb a y e sc l a s s i f i c a t i o n ：c l u s t e r i n ga l g o r i t h m s ；k - m e a n s a l g o r i t h m s ：s t u d e n tm o d e l 插图清单 图3 1 朴素贝叶斯分类模型示意图l o 图3 2 树扩展朴素贝叶斯分类模型示意图1 3 图3 3 主动选择优先实例增量分类1 5 图4 1 基于聚类的朴素贝叶斯分类算法处理过程2 6 图5 1 大学生就业考研模型的功能结构示意图3 6 图5 2 大学生就业考研预测模型主界面3 7 图5 3 聚类结果界面3 8 图5 4 预测结果分析饼图3 8 图5 5 预测结果界面3 9 表格清单 表4 1 两种分类方法正确率比较2 9 表5 1 淮北煤炭师范学院物理系某届学生的成绩表3 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得盒胆兰些盔堂 或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明井表示谢 意。 学位论文作者签字： 签字日期： 年月 日 学位论文版权使用授权书 本学位论文作者完全了解盒妲王些左堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金 胆王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 签字日期：年月日 学位论文作者毕业后去向： 工作单位： 通讯地址： 僦名：咖寻哳0 签字日期：彤年f 月；o 日 电话：们口f7 邮编：9 7 ，i 7 叼 致谢 在论文完成之际，首先衷心感谢我的导师胡学钢教授给予我的悉心指 导和帮助。从选题，定题到论文的修改和完成，每一步都离不开胡老师的 悉心教导。胡老师严谨的治学态度、渊博的专业知识、敏锐的洞察力将对 我以后的工作、学习和生活产生深远的影响。同时，真诚地感谢计算机与 信息学院的全体老师，特别感谢王浩教授、侯整风教授、沈明玉教授、郭 骏教授和其他帮助过我的老师给予我的教诲、关心和帮助，使我能够顺利 地完成我的研究生课程，并在学术方面促进我不断提高，没有他们的孜孜 不倦的教诲，我就不能顺利地完成学业。 感谢淮北煤炭师范学院物理系和计算机科学与技术系的领导和同事， 特别是魏仕民教授细心的指导，还有陈德宝博士的帮助。再次感谢他们给 予我工作和学业方面的支持和帮助。 感谢我的父母、丈夫多年来对我学习的支持、鼓励和关心，他们是我 的坚强后盾，使我能够克服种种压力，扎扎实实地走好人生的每一步。在 这里我祝愿他们身体健康，工作顺利! 最后，我要向所有培养、关心、帮助过我的老师、亲人和朋友表示衷 心的感谢! 作者：张亚萍 2 0 0 6 年1 0 月 1 1 数据挖掘研究概述 第一章绪论 半个多世纪以来，计算机技术的飞速发展使得信息技术已经渗透到人类活 动的各个领域。随着信息技术的快速发展和信息搜集能力的日益提高，产生了 海量的数据。这些激增的数据背后隐藏着许多重要的信息，人们面对着海量的 数据资源，却往往无法找到需要的信息，难以发现有用的知识，这就是“知识 爆炸”给人们带来的困惑。如何有效地利用和处理大量的数据，成为当今世界 共同关心的问题。社会需求是科学发展与创新的源动力，正是在这种社会背景 下，数据仓库( d a t aw a r e h o u s i n g ) 应运而生。数据仓库不同于管理日常工作 数据的数据库，它是为了便于分析针对特定主题的集成化的、时变的即提供存 储时间很长的数据，这些数据一旦存入就不再发生变化。 数据仓库的出现。为更深入对数据进行分析提供了条件。随着数据库技术、 人工智能、数理统计和计算机技术的相互渗透与融合，数据挖掘技术应运而生。 近十年来，数据挖掘的研究工作取得了很大的进展，各种数据挖掘软件的应用 极大地推动了人们掌握、处理信息的能力，并为人们带来了很好的经济效益。 数据挖掘是在数据仓库或大型数据库的基础上，从大量的、模糊的、随机 的数据中提取出数据间重要的但容易被人工分析忽略的知识和信息，自动地发 现隐藏在数据间的模式，做出预测性分析。数据挖掘的概念有广义和狭义之分， 但是无论从哪个角度来定义数据挖掘，都应体现数据挖掘的3 个基本特性，即 潜在性、价值性与可理解性。潜在性是指挖掘出来的知识是隐藏在数据中的， 事先不知道的；价值性指数据挖掘的结果是用户感兴趣的，有用的知识和模式： 理解性是指挖掘的结果应该具有可解释性，并可以被人们所接受和利用的知识。 数据挖掘是一门新兴的交叉学科，自2 0 世纪末提出来后，弓 起了许多专家 学者的广泛关注，并迅速在多个行业得到广泛的应用，成为一种利用信息资源 的有效方法和途径，具有广阔的开发前景和应用市场。数据挖掘技术已经在很 多领域取得令人满意的应用。在银行业，数据挖掘主要用于信用欺诈的建模和 预测、风险评估、趋势分析、收益分析以及辅助直销等活动。在金融市场，已 经将神经网络用于股票价格预测、债券等级评估、商品价格预测以及金融危机 预测方面。在医疗领域，在国外数据挖掘已得到广泛应用。例如，n e u r o m e d i a l 系统公司采用神经网络技术进行油性流质食物辅助诊断；v y s i s 采用神经网络 技术为药品开发进行蛋白质分析等。在电信部门，近年来，电信业发生了比其 它行业更激烈的竞争，人们需要理解并保持住客户，同时，也需要建立有效的 途径以便将新产品销售给这些客户。所有这些推动了电信业对数据挖掘的需求， 而这种需求在电信业也从未有过。像a t & t 、g t e 电信和a i r t o u c h 通信这样一 些公司已经宣布要采用数据挖掘技术。包括l i g h t b r i d g e 和g e t 在内的其它一 些公司也在考虑甄别移动通信欺诈”“。数据挖掘概念已经延伸的非常广泛，涉 及的数据种类日益多样化，给数据挖掘提出了许多挑战性的课题，包括需要进 一步研究的新应用的探索和处理复杂数据类型的新方法，算法的可伸缩性，基 于约束的挖掘和可视化方法，数据挖掘与数据仓库和数据库系统的集成，数据 挖掘语言的标准化，阱及数据隐私保护和安全等等。 1 2 数据挖掘技术在教学管理中应用现状及意义 数据挖掘技术在商业、金融业以及企业的生产、市场营销等方面都得到了 广泛的应用，而在教育领域应用相对较少，高校中对教师信息、学生信息、成 绩等数据的处理还一般停留在简单的数据备份和查询阶段。这些教学管理系统， 多半是以台帐管理为主的o l t p 系统，缺乏综合分析，辅助决策的能力；并且对 其历史积累的海量信息中隐含知识的利用无能为力。 近年来随着高校的不断扩招，学生人数大幅度增加，给高校学生管理、教 学工作带来了严峻考验，传统的教学管理手段逐渐不能适应社会的发展。随着 数据挖掘技术的成熟及应用领域的不断扩展，不少高校研究人员已开始研究将 数据挖掘技术应用于高校的教学、管理中，例如，将数据挖掘技术应用在素质 教育中，通过挖掘学生各个群体的各项素质数据中的关联规则，发现各项素质 之间的相关性和规律，因此素质教育中的关联规则发现的重点是各项素质之间 的关系而不再是某一个具体的学生，而发现素质间的关系有助于使教育决策者 获得启发进而从整体上对现有的教育方法进行改进【1 2 】；通过对毕业生数据库进 行数据挖掘研究，得到了有益于高等学校教学管理决策及毕业生就业指导的挖 掘结果”3 】：在制定人事激励制度时，为了针对不同类别的教师建立有针对性的 制度，可以应用分类和关联规则方法挖掘隐含的规则，从而为高校管理决策提 供科学依据【1 4 】等等。总之，将数据挖掘技术应用于学校的教学、管理中，对提 高学校教学管理水平起到了很好的指导作用，而且采用先进教学技术对考试过 程和教学环节中产生的数据进行多层次、多角度的分析，利用分析结果辅助教 学决策是保证教学质量、提高学生素质的必然要求。 1 3 本文研究内容及结构 本文认真研究和分析了数据挖掘的基本原理和一些常用的方法，对数据挖 掘的定义、相关技术进行了认真地归纳总结，充分详实地研究了数据挖掘技术 中的朴素贝叶斯分类和常用的几种分类模型，并学习和研究了聚类和几种主要 的聚类算法，在此基础上提出基于聚类的朴素贝叶斯分类模型，然后用实例比 较基于聚类的朴素贝叶斯分类模型和朴素贝叶斯分类模型的准确率。最后把基 于聚类的朴素贝叶斯分类模型应用到高校学生的就业考研预测模型中。全文共 分五章。 2 第一章绪论。介绍了数据挖掘的产生及研究现状；数据挖掘技术在高校 中应用的现状及意义。 第二章数据挖掘概述。首先介绍了数据挖掘的定义，接着简单的介绍了 数据挖掘中常用的方法，然后详细介绍了数据挖掘的流程。 第三章贝叶斯分类模型与聚类分析。简单介绍了分类的基本概念、贝叶 斯定理、极大后验假设与极大似然假设。详细介绍了几种常见的贝叶斯分类模 型和聚类的几种算法分析。最后介绍了聚类中最常用的k m e a n s 算法。 第四章基于聚类的朴素贝叶斯分类模型。在前几章的基础上提出了基于 聚类的朴素贝叶斯分类模型。对基于聚类的朴素贝叶斯分类模型和朴素贝叶斯 分类模型进行了比较，选择u c i 机器学习数据库提供的典型数据库实例，通过 实验对两种模型进行了分类准确度的比较。 第五章c n b c 在高校教学管理中的应用。用基于聚类的朴素贝叶斯分类建 立大学生就业考研预测模型。并用v i s u a lb a s i c 实现此模型的开发。 第六章总结。对已做的工作进行总结，并对下一步的工作进行了展望。 第二章数据挖掘概述 近年来，随着数据库信息量的急剧增长和存储设备的不断升级，带来了大 量的数据，远远超出了我们对数据的分析、综合和抽取“知识”的能力。人们 通过传统方法所获得的存在于这些数据中的信息仅仅是整个数据库所包含信息 的一小部分，即数据的表层信息，然而隐藏在这些数据之后的更重要的信息是 关于这些数据的整体特征的描述及对其发展趋势的预测等信息，即知识，是我 们无法用传统的方法来获取的。为了处理这些数据，开发新一代能够“自动地”、 “智能地”分析处理这些海量的原始数据工具显得非常必要。于是数据挖掘技 术运应而生，并成为一个新兴的、在数据库和信息决策领域处于前沿研究的方 向之一。数据挖掘方法的提出，让人们有能力最终认识数据的真正价值。 2 1 数据挖掘定义 数据挖掘( d a t am i n i n g ，简称d m ) ，简单地讲就是从大量数据中挖掘或 抽取出知识，数据挖掘概念的定义描述有若干个版本，以下给出一个被普遍采 用的定义描述： 数据挖掘，又称为数据库中知识发现( k n o w l e d g ed i s c o v e r yo nd a t a b a s e s ， 简称k d d ) ，它是一个从大量数据中挖掘出令人感兴趣的、有用的、隐含的、 先前未知的和可能有用的模式或知识i l l 。数据挖掘是多个学科的融合，它包括 了数据库系统、机器学习、算法、统计学、可视化等。 从理论上讲，数据挖掘可以在任何类型的信息存储上进行，数据挖掘的数 据源包括关系数据库、数据仓库、事务数据库、空间数据库、时间数据库、流 数据、多媒体数据库、面向对象数据库和对象关系数据库、文本数据库和万维 网( w w w ) 。对于不同的数据源，我们所采用的挖掘工具会有所不同，选用 适当的挖掘工具，不仅可以提高挖掘效率，也会改善挖掘效果。 2 2 数据挖掘方法简介 数据挖掘任务就是发现隐藏在数据中的模式f | 】，通常采用的方法有以下几 神： ( 1 ) 关联规则 关联规则挖掘就是从大量的数据中挖掘出有价值描述数据项之间相互联 系的有关知识1 2 1 1 3 1 。随着收集和存储在数据库中的数据规模越来越大，人们对 从这些数据中挖掘相应的关联知识越来越有兴趣。例如：从大量的商业交易记 录中发现有价值的关联知识就可帮助进行商品目录的设计、交叉营销或帮助进 行其它有关的商业决策。 ( 2 ) 聚类算法 聚类算法是通过对变量的比较，把具有相似特征的数据归于一类。因此， 4 通过聚类以后，数据集就转化为类集，在类集中同一类中数据具有相似的变量 值，不同类之间数据的变量值不具有相似性。区分不同的类是属于数据挖掘过 程的一部分，这些类不是事先定义好的，而是通过聚类算法采用全自动方式获 得【1 ”。 ( 3 ) 分类与预测方法 分类方法用于预测数据对象的离散类别；而预测则用于预测数据对象的连 续取值。通常分类与预测方法可以划分为以下几类： 基于决策树的分类方法 所谓决策树就是一个类似流程图的树型结构，其中树的每个内部结点代表 对一个属性( 取值) 的测试，其分支就代表测试的每个结果；而树的每个叶结 点就代表一个类别。 贝叶斯分类方法 贝叶斯分类器是基于贝叶斯定理的统计分类器，它能够预测类别所属的概 率。下面详细介绍。 神经网络分类方法 人工神经网络是模拟人类的形象直觉思维、是在生物神经网络研究的基础 上，根据生物神经和神经网络的特点，通过简化、归纳、提炼总结出来的一类 并行处理网络。利用其非线性映射的思想和并行处理的方法，用神经网络本身 结构可以表达输入与输出的关联知识。它完成输入空间与输出空间的映射关系， 是通过网络结构不断学习、调整，最后以网络的特点结构来表达的，没有显示 函数表达。 其它分类方法 k 一最邻近方法，基于示例推理、遗传算法、粗糙集方法、模糊集合方法、 线性与多变量回归等。 2 3 数据挖掘流程 数据挖掘过程包括问题的理解和提出、数据收集、数据挖掘、模式评估、 知识表示等过程，以上的过程不是一次完成的，其中某些步骤或者全过程可能 要反复进行。 2 3 1 定义问题 清晰地定义出业务问题，确定数据挖掘的目的。对问题的理解和提出：在 开始数据挖掘之前，最基础的工作就是理解数据和实际的业务同题，在这个基 础之上提出问题，对目标作出明确的定义。在这一阶段，应该了解应用的范围， 预先准备相关的知识，进行详尽的业务分折和数据分析，确定用户的最终目标a 一般来说，目标可以是关联规则的发现、数据分类、回归、聚类、数据汇总、 概念描述、相关分析、建模、偏差检测或误差检测等”。 2 3 2 数据预处理 数据预处理是进行数据再加工，包括数据清洗、数据集成、数据转换、数据消 减、自动生成概念层次树。 ( 1 ) 数据清理 数据清理：通过填补遗漏数据、清除异常数据、平滑噪声数据，以及纠正 不一致的数据。数据清洗的主要处理方法有”“： 遗漏数据处理：可以采用忽略该条记录、手工填补遗漏值、利用缺省值 填补遗漏值、利用均值填补遗漏值、利用最可能的值填补遗漏值。 噪声数据处理：平滑去噪的具体方法有b i n 方法、聚类方法、人机结合 检查方法、回归方法。 不一致数据处理：数据库中常出现数据记录内容不一致，其中一些数据 不一致可以利用它们与外部的关联手工加以解决。例如：输入发生的数据录入 错误一般可以与原稿进行对比来加以纠正。 ( 2 ) 数据集成 数据集成就是将来自多个数据源的数据，如数据库、数据立方、普通文件等结 合在一起并形成一个统一数据集合，以便为数据挖掘工作的顺利完成提供完整的数据 基础。数据集成过程中需要解决以下这样几个问题：模式集成、冗余问题、数据值冲 突检测与消除。 ( 3 ) 数据转换处理 所谓数据转换就是将数据转换或归并已构成一个适合数据挖掘的描述形 式。数据转换包括：平滑处理、合计处理、数据泛化处理、规格化、属性构造。 ( 4 ) 数据约简 对大规模数据库内容进行复杂的数据分析通常需要耗费大量的时间，这样 常常使得对数据的分析变得不太可行。数据消减技术正是用于解决这一难题的， 数据消减技术就是从原有庞大数据集中获得一个精简的数据集合，并使这一精 简数据集保持原来数据集的完整性，这样在精简数据集上进行数据挖掘效率会 更高，挖掘出来的结果与使用原有数据集所获得结果基本相同。 数据消减的主要策略有：数据立方合计、维数消减、数据压缩、数据块消 减、离散化与概念层次生成等等”1 。 2 3 3 数据挖掘 数据挖掘包括以下几个阶段1 ： ( 1 ) 确定挖掘的任务或目的：是选择数据分类、预测、关联规则发现还是 序列模式发现等。 6 ( 2 ) 挖掘算法的选择：因为不同的数据有不同的特点，所以需要用与之相 关的算法来进行挖掘。 ( 3 ) 实施数据挖掘操作：这个阶段是相当重要的，要获取有用的知识。 ( 4 ) 证实发现的知识。 2 3 4 结果分析 根据最终用户的决策目的对提取的信息进行分析，把最有价值的信息区分 出来，并且通过决策支持工具提交给决策者。因此，这一步的任务不仅要把结 果表达出来，还要对信息进行过滤处理。如果不能令决策者满意，还需要重复 以上数据挖掘的过程。 2 ，4 本章小结 本章首先介绍了数据挖掘的定义；然后介绍了数据挖掘常用方法：最后介 绍了数据挖掘的流程：定义问题、数据预处理、数据挖掘、结果表述与解释。 其中比较详细的论述了数据挖掘的流程，只有明确了数据挖掘流程，才能很好 地把数据挖掘技术应用到现实生活中来。 第三章贝叶斯分类模型与聚类分析 数据分类在数据挖掘中是一项非常重要的方法，在商业、金融行业应用非常广泛， 在其他领域的应用也在逐渐展开。本章把k - m e a n s 算法运用于朴素贝叶斯分类的缺 失值填充中，来解决分类问题，既能发挥k - m e a n s 算法的局部搜索能力，又能提 高朴素贝叶斯分类的准确度，从而更好地解决分类问题。 3 1 分类的基本概念 3 1 1 分类概念 分类是根据数据集的特点找出类别的概念描述，这个描述代表了这类数据 的整体信息，也就是该类的内涵描述“刮“”。 分类的目的是：分析输入数据，通过在训练集中的数据所表现出来的特征， 为每一个类找到一种准确的描述或者模型。这中描述常常用谓词表示。并使用 这类中的描述对未来的测试数据进行分类。尽管这些未来的测试数据的类标签 是未知的，我们仍可以由此预测这些新数据所属的类。 分类可描述为：给定一个训练数据的集合t ( 简称为训练集或训练数据库) ， t 中的元素记录由若干属性描述。在所有属性中有且仅有一个属性作为类别属 性。属性集合用矢量x = x 。，x ，x 。 表示，其中x ，( 1 i n ) 对应各非类别属 性，可以具有不同的值域，即对于任一属性x ，= x ，x ：，x 。) ，m ；随属性的不 同而变化。当一属性的值域为连续值域时，该属性称为连续属性( n u m e r i c a l a t t r i b u t e ) ，否则称为离散属性( d i s c r e t ea t t r i b u t e ) ；用c 表示类别属性， c = c ，c ：，c 。 ，即数据集有k 个不同的类别。那么，t 就隐含地确定了一个 从矢量x n 类别属性c 的映射函数h ：f ( x ) 一c ，分类的目的就是采用某种方法( 模 型) 将该隐含函数h 表示出来。 分类模型的构造方法有统计方法、机器学习方法、神经网络方法等。统计 方法包括贝时斯法和非参数法，对应的知识表示则为判别函数和原型事例。机 器学习方法包括决策树法和规则归纳法，前者对应的表示为决策树，后者则一 般为产生式规则。神经网络方法主要是b p 算法，它的模型表示是前向反馈神经 网络模型，b p 算法本质上是一种非线性判别函数。另外，还有兴起的粗糙集方 法，其知识表示是产生式规则。 3 1 2 分类方法评估标准 根据以下几条标准对各种分类方法进行评估l ： ( 1 ) 预测准确率，指模型能够正确预测未知对象类别或数据类别的能力。 ( 2 ) 速度，它描述在构造和使用模型时的计算效率。 ( 3 ) 鲁棒性，它描述在数据带有噪声和有数据遗失情况下，学习所获模型 ( 5 ) 易理解性，它描述学习所获模型表示的可理解程度。 3 2 贝叶斯分类 3 z 1 贝叶斯定理 贝叶斯学派是现代统计学中与经典频率学派并列的两大学派之一，贝叶斯 数据分析就是先验分布在经过数据提供的证据修订之后所形成的后验分布。 t o m a sb a y e s 宅e 17 3 6 年提出了后来以他名字命名的贝叶斯理论 1 0 l ：在具体行动 之前，无论决策是如何制定的，在结果的证据收集并确认后，决策是可以改变 的。 设试验e 的样本空间为s ，a 、b 为e 的事件，事件a 发生的概率记为p ( a ) ， 事件b 发生的概率记为p ( b ) ，事件a 事件b 同时发生的概率记为p ( a b ) ，在a 己经 发生的条件下，b 发生的概率称为a 发生的条件下事件b 发生的条件概率，记为： p ( b a ) ：p ( a b ) ( 3 1 ) p ( 锄 无论事件a 、b 是否是稆互独立的事件，下式显然成立； p ( 舢3 ) = v 0 3 ) p ( a i b ) = p ( a ) p ( b i a ) 称为概率乘法定理 假设b ，b ：，b 。是样本空间q 的一个划分，即满足： ( 1 ) b f 两两互斥，b ，b ，= 西( i j ) ： ( 2 ) b = q ( i = 1 ，2 ，n ) 则 p ( a ) 2 p ( a nq ) 2 p ( a n b j ) = p ( 爿层) 2 尸( 彳且) = p ( b 。) p ( a b s ) ( 3 2 ) 上式称为全概率公式。 在( 3 2 ) 中p ( b ，) 是以前的分析得到的，因此称为先验概率，而p ( a b ) 是根据新得到的信息( b 的信息) 重新加以修正的概率因此称为后验概率。 条件概率p ( a b ) 说明事件b 发生时事件a 的概率。相反的问题就是计算逆概 率，即当事件a 发生时，事件b 发生的概率。 根据乘法定理和全概率公式： 盹a ) 5 等2 警。勰 s ， 上式称为贝叶斯公式。 相互独立的随机事件是一系列这样的事件：其中任何一次事件发生的概 率，都与此前各事件的结果无关。因此，对于独立随机事件，借助已经发生事 件的结果来推测后来事件的概率是可能的。因此假如事件a 、b 是相互独立的事 9 件，则有：p ( b ) = p ( a ) 所以对于独立事件：p ( a b ) = p ( a b ) p ( b ) = p ( a ) p ( b ) 3 2 2 极大后验假设与极大似然假设 ( 3 4 ) ( 3 5 ) 在许多学习任务中，需要考虑候选假设集合h ，并在其中寻找给定的数据d 时可能性最大的假设h e h 。任何这样具有最大可能性的假设被称为极大后验假 设( m a x i m u map o s t e r i o r i ，m a p ) ，记为hm ： h m 2 a r g y l l b x p ( h d ) 2 a r g m a x p ( d f n ) p ( h ) p ( d ) h t i hh e l l = a r g m a x p ( d h ) p 0 a ) ( 3 6 ) h e h 由于p ( d ) 是不依赖于h 的常量，所以在最后一步出掉了p ( d ) 。上式就是一个 原始的分类模型。贝叶斯分类就是根据上述m a p 假设找出新实例最可能的分 类。所有对贝叶斯分类模型的研究工作都是以此假设为前提的。 在某些情况下，可假定h 中每个假设有相同的先验概率( 即对h 中任意的 h ，和h ，p ( h ，) = p ( h ，) ) 。这时可把( 3 6 ) 式进一步简化，只考虑p ( d h ) 来寻 找极大可能假设。p ( d h ) 常被称为给定h 时数据d 的似然度( 1 i k e l i h o o d ) ，任何使 p ( d h ) 最大的假设称为极大似然假设( m a x i m u ml i k e l i h o o d ，m l ) 记为：h m h m = a r g m a x p ( d h ) ( 3 7 ) h e 厅 在分类过程中，上式常被用来启发式搜索时进行模型检测。 3 2 3 朴素贝叶斯分类模型 朴素贝叶斯分类模型( n a i v eb a y e sc l a s s i f i e r ，n b c ) 是贝叶斯分类模型中一 种最简单、有效而且在实际使用中很成功的分类模型，其性能可以与神经网络、 决策树相媲美，甚至在某些场合优于其它分类模型。 朴素贝叶斯分类模型描述如图3 1 所示，设有变量集u = a ，a ：，a n ，c ， 其中a ，a ，。a n 是实例的属性变量，c 是取m 个值的类变量。假设所有的属性 都条件独立于类变量c ，即每一个属性变量都以类变量作为唯一的父节点，就 得到朴素贝叶斯分类模型 图3 1 朴素贝叶斯分类模型示意图 朴素贝叶斯分类模型假定特征向量的各分量间相对于决策变量是相对独立 的，也就是说各个变量独立地作用于决策变量，尽管这一假定在一定程度上限 1 0 制了朴素贝叶斯分类模型的适用范围，但在实际应用中，大大降低了贝叶斯网 络构建的复杂性。朴素贝叶斯分类模型已成功地应用到聚类、分类等数据挖掘 的任务中。 ( 1 ) 朴素贝叶斯分类的工作过程 给定一个没有类标号的数据样本x ，用n 维特征向量x = x ，x ：，x 。) 表 示，分别描述样本x 在n 个属性 a 。，a ：，a 。 上的属性值。假定有m 个类 c ，c2 ，c 。 ，那么，将样本x 分配给类c ，条件就是： p ( c ，x ) p ( c ，i x ) ( 1 s p ( x c ，) p ( c ，) ，1 匀茎m j i 。 朴素贝叶斯分类假定类条件独立，简化了计算。当假定成立时，与其它分 类算法相比，朴素贝叶斯分类是最精确的，同时在处理大规模数据库时表现出 了较高的分类准确性和运算性能，它还可为其它分类算法提供理论判断。例如： 在某种假定下，可以证明正如朴素贝叶斯分类一样，许多神经网络和曲线拟合 算法输出最大的后验假定。 ( 2 ) 朴素贝叶斯分类模型的不足 朴素贝叶颠分类模型中的类条件独立性假设和数据完备性要求是它的先天 不足所在，独立性假设和数据完备性要求在许多实际问题中并不成立，如果在 这些问题中忽视这两点，会引起分类的误差。为了克服这些不足。已有许多相 关文献对朴素贝叶斯分类算法作了一些改进，主要是放宽条件独立性的限制。 3 2 4 提升的朴素贝叶斯分类模型 改进朴素贝叶斯分类模型的性能可以通过“提升”( b o o s t i n g ) 的方法 p u ”1 。提升方法是由f r e u n d 和s c b a p i r e 于1 9 9 5 年提出，总的思想是学习一系列 分类模型，在这个序列中每一个分类模型对它前一个分类模型导致的错误分类 例子给予更大的重视，对训练实例的权重进行修正，再学习新的分类模型。例 如，学习完分类模型h 。之后，增加了由h 。导致分类错误的训练实例的权值， 并且通过重新对训练实例计算权值，再学习下一个分类模型h 。这个过程重 复t 次。从这系列的分类模型中可以综合得出最终的分类模型。 在这个过程中，每个训练例子被赋予一个相应的权值，如果一个训练 萝| l 子 被分类模型错误分类，那么就相应增加该例子的权重，使得在下一次的学习中， 分类模型对该例代表的情况更加重视。 f r e u n d 和s c b a p i r e 给出的a d a b o o s t 算法实现了提升算法对分类问题的处理， 具体算法如下。 i n p u t ：n 个训练实例：d = ( ( x 。，c 1 ) ，( x 。，c 。) ) 以及待分类实例x ，n 个训练 实例上的分布d ：w ，w 为训练实例的权向量。 t ：训练重复的趟数 1 o u t p u t ：h ( x ) = a r gm a x ) - i l l ( 1 0 9 去) j ( 向i x ) = c ) ，其中i ( 盯) 是示意函数，当 口- t 时i ( 岔) = 1 ，否则i ( 留) = o 步骤： 初始化训练实例的权向量，w ，= i n ，i ( 1 n ) ； f o r i = 1t o t 给定权值w ，( ”得到一个假设h o ：x 专c ； 估计假设h 的总体误差，e ( f ) = 二w 。1 ，( c 1 h ( o ( x 7 ) ) ； 计算) = p ”( 1 一) ； 计算下一轮样本的权值wf 【“lw f ( 。( 。) “。6 ”。； 1 2 正规化w ( f + 1 ) ，使其总和为1 ； e n d f o r 假设每一个分类模型都是实际有用的，e ( ，】 0 5 ，也就是说，在每一次分 类的结果中，正确分类的样本个数始终大于错误分类的样本个数。可以看出， 此时 o ，则有以下几种定义”“。 ( 1 ) 若g 中任意两个元素g 、g 一之间的距离不大于阈值，即有d ( i ，j ) t ，则称g 为类。 ( 2 ) 若g 中任意一个元素g ，它与其他元素间的距离均值不大于阈值，即 有j d ( f ，- ，) t ，则称g 为类。 l e j 女 ( 3 ) 若g 中任意一个元素g ，总存在另外一个元素g ，它们的距离不大于 阈值，即有d ( i ，j ) - t ，则称g 为类。 它们均通过限制元素间的距离来定义类，其中第一个定义的要求最高，凡 满足它的条件，一定也满足其它定义的条件。 3 3 2 数据对象问的柑异度 与普通的聚类分析不同，在数据挖掘领域，聚类分析中的数据呈现多样性。 经常出现的数据类型有区间标度变量、二元变量、标称型、序数型和比例标度 型变量等。对于不同的类型，对象间的相异度有着不同的度量方法。 ( 1 ) 区间标度变量 区间标度变量是一种线性标注的连续变量。如重量和高度。为避免度量单 位选择对聚类结果的影响，数据应当先标准化。进行如下变换： 计算平均的绝对偏差s 1 s = 二( i x l - m l + l x2 - m 卜+ i x 。一m i ) ( 3 1 2 ) 仃 其中x ，x ，x 。是n 个度量值，m 是它们的平均值，即 1 m = 二( x 1 + x2 + ，+ x 。) n 计算标准化的度量值z z ：三型( 3 1 3 ) 占 数据标准化处理后，对象间的相异度通常是基于对象问的距离来计算的。 最常用的距离度量方法是欧几里德距离，它的定义如下： d ( i ，j ) = jx n 一l1 2 + f x ，2 一x j 21 2 + + l x 妒一x 妒f 2 ( 3 1 4 ) 其中i = ( x ”x ， x ) y 日j j = ( x ，。，x ，：，x ，) 是两个p 维的数据对象。 ( 2 ) 二元变量 一个二元变量只有两个状态：o 或l 。o 表示该变量为空，1 表示该变量存在。 二元变量分为对称二元变量和非对称二元变量。 对称二元变量的两个状态是等权重的。如性别变量，1 表示男人，o 表示女 人。评价两个对象i 和j 之间相异度的最著名的系数是简单匹配系数，其定 义如下： 1 6 d ( i ，j ) = 型旦 g + r + s ( 3 t 5 ) ( 3 ) 标称变量 标称变量是二元变量的推广，它以具有多个状态值。如m a p - c o l o r 是一个标 称交量，它可能有五个状态：赤色、橙黄色、黄色、绿红色和青色。两个对象i 和j 之间的相异度：可以用简单匹配方法，其定义如下： d ( i ，j ) = 生兰 p ( 3 1 6 ) 其中m 是i 和j 取值相同的变量数目，p 是全部变量的数目。 ( 4 ) 序数型变量 离散的序数型变量类似标称变量，但其状态的排序是有意义的。如比赛中 的排名：金牌、银牌和铜牌。其相异度计算包括如下步骤： 将变量值用1 m 替代，其中m 为有序状态的个数。 将每个变量的值域映射到 0 ，1 】上，使每个变量有相同的权重。 采用区间标度变量的辐异度计算方法。 ( 5 ) 比例标度型变量 比例标度型变量在非线性的标度所取的度量值。如指数标度，典型的例子 包括细菌数目的增长、放射性元素的哀变。根据实际情况将比例标度型变量变 换成区间标度型变量，再计算相异度。 许多真实的数据库中，对象是被混合类型的变量描述的。假设数据集包含 p 个不同类型的变量，对象i 和j 之间的相异度d ( i ，j ) 定义为： 如盯略u d ( i j ) = 型了一 芝岛盯 ，- i ( 3 1 7 ) 其