（计算机科学与技术专业论文）基于显现模式分类能力的限制性贝叶斯网络分类算法.pdf

中文摘要 数据挖掘是研究从大量数据中用非平凡的方法发现有用知识的理论与方 法分类作为数据挖掘的一个重要课题，在统计学、机器学习、神经网络和专家 系统中得到了广泛的研究在分类方法研究中，利用“属性值序偶模式构造分 类器是一种重要的技术其中，基于显现模式构造的分类器在分类特征表现明显 的情况下具有较高的分类精度，但对数据特征不明显的数据集合，分类效果却较 差 本文首先介绍了分类的相关概念及基本技术，随后详细介绍了显现模式的基 本概念及有效的使用边界操作挖掘显现模式的m b d l l b o r d e r 算法，然后简要 分析比较了目前几种基于显现模式的分类方法最后，本文给出了两个利用显现 模式进行分类的算法一个是基于显现模式分类能力，同时利用贝叶斯网络分类 器的稳定性，构造的限制性贝叶斯分类算法本文提出了一种新的度量显现模式 分类能力的方法，该度量方式进一步反映了贝叶斯分类器中属性之间的依赖关 系这种限制性贝叶斯分类器从本质上减弱了朴素贝叶斯分类器的属性条件独立 性假设另一个是基于特殊显现模式的分类算法利用显现模式分类能力定义了 显现模式的分类系数，依据分类系数挖掘新的特殊显现模式，并且利用特殊显现 模式来构造分类算法，这个分类算法中主要内容是要对分类系数进行准确度量 为了测试算法的分类性能，在u c i 机器学习库中的2 0 个数据集上的实验结果 表明，与n b ，c 4 5 ，t a n 以及c a e p 比较分析，本文所提出的算法具有更好的分 类效果 关键词：分类技术；模式发现；贝叶斯网络；分类器；属性独立性；显现模式 分类号：t p 3 0 1 6 本文得到国家自然科学基金项目资助( 6 0 6 7 3 0 8 9 ) j 匕哀銮通盔堂亟堂位j 金塞 一 垦s 至b 至 a bs t r a c t d a t am i n i n gi st h et h e o r ya n dm e t h o do i lr e s e a r c h i n gh o wt om i n ek n o w l e d g ef r o m d a t ai nv e r yl a r g ed a t a b a s e si nn o n t r i v i a lm e t h o d s c l a s s i f i c a t i o n , a sa ni m p o r t a n tt h e m e i nd a t am i n i n g , h a sb e e nr e s e a r c h e de a r l i e ri ns t a t i s t i c s ，m a c h i n el e a r n i n g , n e u r a l n e t w o r k , e x p e r ts y s t e m s ，e t c i nt h em o s to fc l a s s i f i c a t i o nm o d e l s ，c o n s t r u c t i n ga c l a s s i f i e ru s i n gp a t t e r no f “a t t r i b u t e - v a l u e ”p a i r si so n eo fi m p o r t a n tt e c h n i q u e s ，i n w h i c h , ac l a s s i f i e rb u i l tb ye m e r g i n gp a t t e r n sh a sb e e ns h o w nb e t t e rc l a s s i f i c a t i o n a c c u r a c yf o rd a t as e t sw i t hs t r o n gc l a s s i f i e dc h a r a c t e r i s t i c s b u tw h e nt h ea t t r i b u t e so fa d a t a s e ta r en o tm u c hs e n s i t i v et oc l a s sl a b e l ，t h ee f f e c t i v e n e s su s i n ge m e r g i n gp a t t e r n s w i l lg e tw o r s e i nt h i s p a p e r , w ef i r s t l yi n t r o d u c et h ec o n c e p t a n db a s i c t e c h n o l o g ya b o u t c l a s s i f i c a t i o n t h e nw ep r e s e n tt h eb a s i cc o n c e p ta b o u te p sa n de f f i c i e n tm i n i n g a l g o r i t h mo fb o r d e r so p e r a t i o nn a m e dm b d l l b o r d e ri nd e t a i l a l s o ，w eb r i e f l y e x p o u n dt h ei d e ao fc l a s s i f i c a t i o na l g o r i t h m sw h o s eb a s i ca l g o r i t h mi se p s - b a s e d f i n a l l y , t w on o v e la l g o r i t h m sb a s e de p sa r ep r o p o s e d t h ef i r s ta l g o r i t h mi sar e s t r i c t e d b a y e s i a nn e t w o r kc l a s s i f i e rb a s e do nt h ec a p a b i l i t yo fe m e r g i n gp a t t e r n s an o v e l m e t h o di sp r o p o s e dt om e a s u r et h ec l a s s i f i c a t i o nc a p a b i l i t yo fe m e r g i n gp a t t e r n s ，a n d t h em e a s u r e m e n tc a nb ef u r t h e re x p r e s s e dd e p e n d e n c yr e l a t i o n si nb a y e s i a nn e t w o r k c l a s s i f i e rb e t w e e nt h ea t t r i b u t e s t h i sl 【i n do fr e s t r i c t e db a y e s i a nn e t w o r kc l a s s i f i e r e s s e n t i a l l yw e a k e n e dt h ea s s u m p t i o no fc o n d i t i o n a li n d e p e n d e n c ei nn a i v eb a y e s c l a s s i f i e r t h eo t h e ro n ei sac l a s s i f i c a t i o nu s i n gs p e c i a le m e r g i n gp a t t e r n s w eu s et h e a b i l i t yo fe m e r g ep a t t e r nt od e f i n ec l a s s i f i c a t i o nc o e f f i c i e n t , a n dt h e nu s ei tt od i s c o v e r n e ws p e c i a le m g e r g ep a t t e r n st ob u i l dc l a s s i f i e r t h o s en e wb u i l dc l a s s i f i e r sm a i n l y f o c u so nm e a s u r i n gt h ec l a s s i f i c a t i o nc o e f f i c i e n ta c c u r a t e l y i no r d e rt oe s t i m a t et h ea c c u r a c yo fo u ra l g o r i t h m s ，as e r i e so fe x p e r i m e n t sw e r e c o n d u c t e do nt h e2 0d a t as e t ss i n g l e do u tf r o mt h eu c im a c h i n el e a r n i n gr e p o s i t o r y t h ee x p e r i m e n t a lr e s u l t sh a v es h o w nt h a tt h i sa l g o r i t h mc a l lp r o d u c eg o o dc l a s s i f i c a t i o n r e s u l t sc o m p a r a b l yw i t ho t h e rs t a t e - o f - t h e - a r tc l a s s i f i c a t i o nm e t h o d ss u c ha sn b ，c 4 5 ， t a na n d c a e p k e y w o r d s ：c l a s s i f i c a t i o nt e c h n i q u e s ；p a t t e r nd i s c o v e r y ；, b a y e s i a n n e t w o r k ； c l a s s i f i e r , a t t r i b u t ei n d e p e n d e n c be m e r g i n gp a t t e r n s c l a s s n 0 ：t p 3 0 1 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：王也j 毙 签字日期：加。1 年6 月l c 1 日 导师签名： 芝髟 签字日期：刃哆年月形，日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名：王世弓鱼 签字日期： 妒。c 7 年6 月f 7 日 6 1 致谢 本论文的工作是在我的导师王志海教授的悉心指导下完成的，王老师严谨的 治学态度和科学的工作方法给了我极大的影响，他在科学研究上孜孜不倦的进取 精神更是深深地激励和鼓舞着我在整个论文的完成阶段，王老师自始至终都倾 注了大量的心血，从论文的选题、搜集资料、修改、直至论文定稿一直给予精心 地指导并提出大量珍贵的意见两年多来，王老师对我的学习和生活给予了许多 关心和帮助，不仅让我学到了很多的科研知识，而且还学到了许多做人的道理， 这些都将融入到我未来的生活中，令我受益终身在此衷心感谢王老师对我的关 心和指导 感谢瞿有利老师，他悉心指导我们完成了实验室的科研工作，在学习上和生 活上都给予了我很大的关心和帮助，在此向瞿老师表示衷心地谢意 感谢黄厚宽和f f l 盛丰教授，两位教授宽广豁达的长者风范、以及严谨的治学 态度始终让我深深地敬仰 感谢于剑老师、林友芳老师，他们一丝不苟的治学精神永远是我学习的榜样 感谢实验室的各位师兄、师姐、同窗、师弟、师妹们在本论文的完成过程 中，他们给了我很大的帮助 感谢我的家人和朋友，是他们一直以来对我生活上的关怀和精神上的鼓励， 给了我克服困难的信心和不断进取的动力 在我即将毕业之际，我衷心地感谢关心我的各位老师、同学和我的亲人们祝 你们心想事成，一切顺利! 1 引言 据统计，存储在全世界数据库里的数据量正以每二十个月翻一倍的速度增 长尽管很难从量的意义上真正验证这个数字，但是仍然可以从质上把握这个增 长速度，人们正在被数据淹没随着数据量的膨胀，以及利用机器承担数据搜索 工作已变得普通，数据挖掘的机会正在增长世界正越来越丰富多彩，数据挖掘 技术成为洞察构成数据的模式的唯一希望 1 1研究背景 数据挖掘( d a t am i n i n g ) 是一个多学科交叉研究领域，它融合了数据库( d a t a b a s e ) 技术、人工智能( a r t i f i c i a li n t e l l i g e n c e ) 、机器学习( m a c h i n el e a r n i n g ) 、统计学 ( s t a t i s t i c s ) 、知识工程( k n o w l e d g ee n g i n e e r i n g ) 等最新技术的研究成果经过十几年 的研究，产生了许多新概念和新方法，一些基本概念和方法趋于清晰，它的研究 正向着更深入的方向发展 为了介绍数据挖掘的概念，必须提到数据库中的“知识发现 ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e , k d d ) 关于k d d 与d a t am i n i n g 的关系，有许多不同的看 法，我们可以从这些不同的观点中了解数据挖掘的含义 ( 1 ) k d d 是数据挖掘的一个特例 既然数据挖掘系统可以在包括数据库等多种数据存储组织形式中挖掘知识， 那么数据库中的知识发现只是数据挖掘的一个方面这是早期比较流行的观点， 从这个意义上说，数据挖掘就是从数据库、数据仓库以及其他数据存储方式中挖 掘有用知识的过程这种描述强调了数据挖掘在数据源形式上的多样性 ( 2 ) 数据挖掘是k d d 过程的一个步骤 f a y y d ，p i a t e t s k y - s h a p i r o 和s m y t h 在1 9 9 6 年出版的论文集知识发现与数据 进展中给出了k d d 和数据挖掘的最新定义，并将二者加以区分 k d d 是从数据中辨别有效的、新颖的、潜在有用的、最终可理解的模式的 过程 数据挖掘是k d d 中通过特定的算法在可接受的计算效率限制内生成特定 模式的一个步骤 虽然我们可以从不同的数据源中挖掘知识，但是这些数据源和数据库技术是 相关的因此k d d 是一个更广义的范畴，它包括数据清洗、数据集成、数据选择、 数据转换、数据挖掘、模式生成及评估等一系列步骤这样，若把k d d 看做是一 些基本功能构成的系统，而数据挖掘就是这个系统的一个关键的部分源数据经 过清洗和转换等成为适合于挖掘的数据集，数据挖掘在这种具有固定形式的数据 集上完成知识的提炼，最后以合适的知识模式用于进一步分析决策工作将数据 挖掘作为k d d 的一个步骤看待，可以使我们更容易聚焦研究重点 ( 3 ) k d d 与数据挖掘含义相同 有研究者认为，k d d 与数据挖掘只是叫法不一样，它们的含义基本相同事 实上，在现今的文献中，这两个术语仍然不加区分的使用着有人说，k d d 在人 工智能领域更流行，而数据挖掘在数据库界使用更多 从上面的描述中可以看出，数据挖掘概念可以在不同的技术层面上来理解， 但是其核心仍然是从数据中挖掘知识数据挖掘的任务一般可以分为两类：描述 和预测描述性挖掘任务刻画数据库中数据的一般特性预测性挖掘任务在当前 数据上进行推测，以进行预测 ( 1 ) 分类或预测模型发现 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示分类是 利用训练数据集通过一定的算法而求得分类规则分类可被用于规则描述和预测 ( 2 ) 数据总结与聚类发现 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 类中的数据相异聚类分析可以建立宏观的概念，发现数据的分布模式，以及可 能的数据属性之间的相互关系 ( 3 ) 关联规则发现 关联规则挖掘首先由a g r a w a l ，l m i e l i n s k i 和s w a m i 提出两个或两个以上变 量的取值之间存在某种规律性，就称为关联数据关联是数据库中存在的一类重 要的、可被发现的知识关联分为简单关联、时序关联和因果关联关联分析的 目的是找出数据库中隐藏的关联网一般用支持度和可信度两个阈值来度量关联 规则的相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需 求关联规则是数据挖掘中研究比较成熟的问题 ( 4 ) 序列模式发现 时序模式是指通过时间序列搜索出的重复发生概率较高的模式与回归一样， 它也是用已知的数据预测未来的值，但这些数据的区别是变量所处时间的不同 ( 5 ) 混沌模式发现 混沌模式是存在于数据库中而经常被当作随机噪声关系处理的、尚未被研究 的一种有用模式，它是自然界复杂性的合理表现 除此以外，数据挖掘的任务还有相似模式发现、依赖关系或依赖模型发现、 2 异常和趋势发现等 根据数据信息存储方式，用于挖掘的对象有关系型数据库、面向对象数据库、 空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、遗产数据 库、w e b 数据等 数据挖掘技术从一开始就是面向应用的由于现在各行业的业务操作都向着 流程自动化的方向发展，企业内产生了大量的业务数据一般地，企业内的业务 数据是由于商业运作而产生的，很少是为了分析的目的而收集的因此，数据挖 掘的应用成为高层次数据分析和决策支持的骨干技术在很多领域，尤其是在诸 如银行、电信、保险、交通、零售( 如超级市场) 等商业领域获得了成功的应用， 而且在天文学、分子生物学等科学研究方面也表现出技术优势 1 2本文研究的工作和意义 本文研究的工作主要有以下几个方面： 第一，整体上分析了分类理论的基本概念：分类的概念，分类的基本技术， 尤其重点分析了贝叶斯分类，基于实例的分类以及其他的分类技术还分析了分 类模型的性能度量标准，包括分类性能评估的定性标准和定量标准最后对分类 模型评估标准进行了较为详尽的分析同时，还提出了一种新的度量分类性能评 估的标准，这种标准能够在全新的角度对不同的分类器进行评估，从而在总体上 对分类器的抉择提供更为全面的分析 第二，全面分析了显现模式的概念及技术首先介绍显现模式的概念，并对 显现模式诸多的特性进行了全面的汇总和介绍为了分析挖掘显现模式的技术， 还对集族和区间的概念，以及利用区间来表示项集的方法进行介绍其次，介绍 了显现模式的特性，尤其是重点介绍了常见特殊形式的显现模式最后，分析了 利用边界算法挖掘显现模式的b o r d e r d i f f 算法以及改进后的b o r d e r d i f f 算法 第三，给出了显现模式分类能力( a b i l i t y ) 的定义，以及度量显现模式分类能力 的方法显现模式分类能力这一新特性，可以进一步反映了贝叶斯分类器中属性 之间的依赖关系，利用显现模式的分类能力构造限制性贝叶斯分类器能够从本质 上弱化朴素贝叶斯分类器的属性条件独立性假设为了合理高效的利用显现模式， 还介绍了显现模式约简，以及阈值选择的方法 第四，提出了一种新的限制性显现模式特殊显现模式( s p e c i a l e p s e p ) 在 分析显现模式分类能力的基础上，为了度量每个显现模式对于分类所占的比重或 是贡献，还引入了分类系数九的概念，以及如何修正分类系数九最后给出了从显 3 现模式中挖掘特殊显现模式的算法和基于特殊显现模式的分类算法 本文工作的意义在于： 第一，挖掘了显现模式的新的特性分类能力这种特性真正定义了显现 模式用于分类的原理和统计学意义同时该特性还能用于利用显现模式构造分类 器的算法中，使得算法的分类准确率有了提高 第二，提出了一种新的限制性显现模式特殊显现模式( s e p ) 这种特殊显 现模式是在显现模式分类能力的基础上给出的，利用特殊显现模式构造的分类器 具有很好的分类准确率 第三，扩充了度量分类器性能评价标准引入了等级准确率的概念，利用这 种新的评价标准，能够对分类器对类别分类的效果做出评估，从而可以更好的选 择分类器 1 3本文的组织结构 论文的组织结构如下： 第l 章为本文的引言部分简要介绍了数据挖掘的概念及基本知识，并论述 了本文研究的工作和意义及论文的组织结构 第2 章详细讨论了分类的基本概念、分类的基本技术，并介绍了分类模型的 评估 第3 章首先详细地介绍了显现模式的基本概念、特性及其常见特殊形式的显 现模式，以及显现模式的挖掘算法 第4 章简要介绍了现有的几种基于显现模式的分类算法，并比较了几种算法 的优缺点然后详细给出本文提出的两个算法：基于显现模式分类能力的限制性 贝叶斯分类算法和基于特殊显现模式的分类算法 第5 章为本文算法的详细实验结果对比以及性能分析，给出了本文所提算法 在u c i 机器学习库上的实验结果以及与其他算法的对比分析 第6 章对本文的主要研究工作进行简要的总结，并对进一步需要研究的问题 进行了探讨和展望 4 2 分类理论综述 分类是数据挖掘中的一个重要问题，也是一种重要的数据分析形式分类学 习( c l a s s i f i c a t i o nl e a r n i n g ) 是用一个已分类的样本集来表示学习方案，并希望从这个 样本集中学习对未来样本进行分类的方法【1 】分类是一种有指导的学习过程，即 学习过程是在被告知每一个训练样本属于哪个类的“指导下进行的，可以用于 从数据库中提取重要数据类的模型或预测未来的数据趋势 在本章，主要介绍有关分类的相关知识，包括分类的概念、分类的基本技术、 分类模型的评估和分类算法性能的比较标准等 2 1分类概念 分类的任务是学习如何把一个对象划分到预定义的类，其在人工智能、机器 学习和神经网络等方面都有广泛的应用分类问题可以描述为：数据是一张标准 关系表，它包含个记录，这些记录通常称作实例( i n s t a n c e ) 或样本( e x a m p l e ) 每 一个实例用固定数目的度量标准描述，这种度量标准称作属性( a t t r i b u t e ) 每一个 属性都有一个合法的取值范围，称作该属性的域( d o m a i n ) 当属性域是实数域时该 属性为数值属性( n u m e r i c a la t t r i b u t e ) 或连续属性( c o n t i n u o u sa t t r i b u t e ) 当属性域是有 限的，该属性为分类属性( c a t e g o r i c a la 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 l a s sl a b e l ) ，类标号指示实例所属的类类 标号之外的其他属性是预测未知样本类型的依据，因此也称作预测属性( p r e d i c t o r a t t r i b u t e s ) 分类过程可以描述为如下两个步骤： 第一步，建立一个模型训练阶段的目的是建立分类器，即从训练数据集中 获取可以进一步指导未知数据分类的专家知识不同的分类模型可能用不同的形 式描述用于指导分类的知识这些分类模型以不同的形式描述了某个类区别其他 类的特征概念集，也可以认为分类模型是以某种特定的形式描述了训练集的数据 分布特征 第二步，使用模型进行分类首先要使用测试集评估分类模型的分类准确率， 如果分类准确率是可以接受的，那么我们才可以真正把该模型用于指导未知元组 的分类有多种技术用来评估分类模型的准确性，关于模型的评估的问题，本文 在本章第3 节做进一步论述 5 2 2分类的基本技术 由于分类技术在不同领域的广泛应用，统计学、机器学习、神经网络等领域 的研究者提出了很多分类方法，这些基本方法有机器学习方法，统计方法，聚类 分析方法，神经网络方法，遗传算法，数据库方法，近似推理和不确定性推理方 法，基于证据理论和元模式的方法，现代数学分析方法，粗糙集或模糊集方法， 集成方法等这些方法来自不同的领域，工作原理差别很大，但是都在相应的领 域取得了很大的成功本节将简要介绍分类的基本技术：贝叶斯网络分类、基于 实例的分类以及其他的分类技术 2 2 1贝叶斯网络分类 解决分类问题有多种技术手段和方法，其中基于贝叶斯理论的技术是一种有 效的方法贝叶斯网络分类器( b a y e s i a nn e t w o r kc l a s s i f i e r s ) 【2 - 4 】，是利用概率论 和统计学的原理，根据数据集归纳出属性之问的依赖关系，依据这些属性间的条 件依赖关系进而构造分类器，以进行待分类实例的概率分布计算完成分类任务对 于不同数据特征的数据集，贝叶斯分类器都能够产生较好的分类效果 基于贝叶斯的分类过程可以这样描述：假定有k 个类c l ，c 2 ，g ，给定未知 数据样本x 可以用一个维向量描述为胙 x j ，砣，而) ，分类器将预测未知样本x 属于在各属性取值为x 条件下的后验概率最高的类即选择能够使以gi 最大化 的c f 作为未知样本所属的类 只gl p ( c jlx ) ，l i 丘j i( 2 。1 ) 依据贝叶斯定理 h c fl 妒p lc j ) p ( 回p ( 2 2 ) 其中，j p 对于所有的类都是常数，只需p ( x ig ) p ( c f ) 最大，而如果类的先验概率 未知，通常假定这些类是等概率的，即p ( g ) 一p ( q ) = 一p ( c d 类的先验概率也可 以用尸( g ) = l s i l i s l ，其e e l s , i 是训练集中g 类的样本数，i s l 是训练集的样本总数因 此，如何获得p ( x lc f ) 成为基于贝叶斯的分类算法的关键问题 朴素贝叶斯分类算法( n a i v eb a y e s i a n ，n b ) 【5 】做了一个简单的假定：对于给定 的c f 类，所有属性是相互独立的在属性值相互条件独立的前提下，p ( xlg ) 的计 算可以简化为：p ( x ic d = i = ：i p ( x i q ) 概率m i lc d ，尸j 陋ig ) 一，讹，ig ) 可以通过 训练集估算 严1 尽管朴素贝叶斯分类算法很简单，但是在很多应用领域取得了巨大的成功， 6 分类准确度可以与决策树和神经网络等复杂的算法媲美应用于大型数据库，贝 叶斯方法表现出了高准确度与高速度当条件独立性假设成立时，朴素贝叶斯分 类是最精确的，然而朴素贝叶斯分类算法的条件独立性假设在现实数据集上通常 是不成立的因而研究者们开始研究准朴素贝叶斯分类器( s e m i n a i v eb a y e s c l a s s i f i e r s ) 6 7 】，使得能够最大程度的减小条件独立性假设，从而更能和实际的 数据集相符合，来提高分类的精度 众多准朴素贝叶斯分类器中，t a n 分类器是对朴素贝叶斯分类器的一种改进 和扩展【3 】，通过计算属性间的互信息，将各个属性形成树结构，应用最大生成树 算法，形成一颗树，最后根据这个树结构之间的条件依赖关系进行分类t a n 分 类器是目前公认的对朴素贝叶斯分类器性能改进最好的分类器之一另外， s p ( s u p e r - p a r e n t ) 算法也是对朴素贝叶斯方法的一种改进 8 】，该算法先找一个最佳 s u p e r p a r e n t 节点，然后再为该s u p e r p a r e n t 节点找一个最适合的f a v o r i t e c h i l d 节点， 从而引进了s u p e r p a r e n t 和f a v o r i t e c h i l d 之间的依赖关系 还有其他很多的准朴素贝叶斯分类器，例如a o d e 9 和l b i o a o d e 通过 集成若干单层依赖关系的分类器来放松独立性假设，同时通过对单层依赖关系分 类器的选择加以限制来避免模式选择带来的不利影响l b 算法在训练阶段结合频 繁项集挖掘算法挖掘出高阶的并且对分类提供新的信息的频繁项集，在分类的过 程中，从这些项集中选择一部分来改进朴素贝叶斯分类器的独立性假设还有懒 惰式的学习策略，在具体待分的每一条实例到来的时候，才根据一些相应的策略 建立分类器进行分类，l a z y d t 和l b r 就是利用l a z y 的思想来实现的分类器 1 1 1 2 对于t a n 分类器来说，存在着非类属性的单依赖关系以及结构学习的缺点， 因此z h a n g 提出了一个准朴素贝叶斯分类器模型h n b ( h i d d e nn a i v eb a y e s ) 1 3 ， 他认为每一个非类属性都有一个隐藏的双亲节点，每一个隐藏的双亲节点和该非 类属性之问的依赖关系用所有其它非类属性和该属性的条件互信息的加权平均值 来表示，最后利用非类属性和隐藏双亲节点的条件依赖关系的联合概率进行分 类试验结果表明h n b 分类器具有很高的分类精度，比t a n 分类器要好一些 上面所述的减弱n b 分类器属性独立性的方法，都是通过采用相应的策略寻找 属性间存在的某种确定依赖关系，进而放松朴素贝叶斯分类算法对条件独立性假 设的要求与数据挖掘中的其他知识表示的方法相比，贝叶斯网络在知识表示方 面具有以下优点：贝叶斯网络能够很方便地处理不完全数据，贝叶斯网络能够学 习变量间的因果关系，贝叶斯方法与其他模型相结合，通常可以有效的避免数据 的过分拟合【1 4 】 7 2 2 2基于实例的分类 在基于实例的学习中，训练样本被一字不差地保存，并且使用一个距离函数 来判定训练集中的哪个实例与一个未知的测试实例最靠近一旦找到最靠近的训 练实例，那么最靠近实例所属的类就被预测为测试实例的类基于实例的分类主 要内容包括距离函数的定义和有效的寻找最近邻 ( 1 ) 距离函数 大部分基于实例的学习方法使用欧几里德距离函数，属性值为a l ，a 2 ，a k ( 七 是属性的个数) 的实例与另一个属性值为b i ，赴一，b k 的实例之间的距离定义为： ( 口i - 4 ) 2 + ( 口2 一也) 2 + + ( 口t 一6 k ) 2( 2 3 ) 比较距离时，不必计算平方根，直接使用平方之和进行比较欧几里德距离 可以由曼哈顿( m a n h a t t a n ) 或者c i t y - b l o c k 距离度量来替代这两者不是计算属性值 差值的平方，而是将差值相加( 取绝对值以后) 其他方法采用指数大于2 的形式更 高的指数增加了大差异的影响力而削弱了小差异的影响力 不同的属性用不同的尺度量度，如果直接使用欧几里德公式，某些属性的结 果可能被另外一些使用较大量度尺寸的属性完全削弱所以，通常需要将所有属 性值正常化，在0 和l 之间通过计算： 彰一m l n 彰 a i2 m a x i = m m 矗 ( 2 4 ) v t m 、 这里，是属性f 的真实值，最大和最小属性值是从训练集的所有实例中获得的 这些公式隐含的假设为数值属性这里，两个值之间的差就是它们之间的数 值差异，将这个差值平方以后再相加得到距离函数对于名词性属性，属性值是 符号值而不是数值，两个不同的名词性属性值之差常认为是l ，如果名词性属性值 相同，它们的差值为0 这里无需量度尺寸，因为使用l 和o ( 2 ) 有效寻找最近邻 尽管基于实例的学习方法不但简单而且很有效果，但是通常速度很慢一种 显而易见、用于寻找哪个训练集成员最靠近未知的测试实例的方法便是，计算训 练集里的每一个训练实例到测试实例的距离，并选择距离最小的那一个这个过 程与训练实例的数量成线性关系，换句话说，就是做一个单独的预测所花费的时 间与训练实例的数量成比例关系处理整个测试集所花费的时间与训练集实例数 量和测试集实例数量的乘积成比例关系 以树的形式表示训练实例集能更加有效地找出最近邻实例，尽管怎样用树来 表示并不十分明显其中一种适合的树结构是柚树七d 树是一个二叉树，它用 一个超平面将输入实例空间分隔开，然后再将每一个部分递归地进行分裂在二 维数据空间上，所有的分裂都与一个轴平行或者垂直数据结构称为k d 树，是因 为它将一系列的数据点存储在k 维空间，k 是属性的数量 k d 树是可用于有效寻找最近邻的良好数据结构，但是，并不完美当处理不 均匀分布的数据集时便呈现出一个基本冲突：既要求树有完美的平衡结构，又要 求区域近似方形更重要的是，矩形，甚至正方形，都不是最好的使用形状，原 因是它们都有角解决的办法就是使用超球体( h y p e r s p h e r e ) 当然，相邻的球体可 能相互重叠，而矩形却可以彼此相毗邻，但这并不是一个问题，因为前面讲述的 用于柚树的最近邻算法并不需要区域之间不相交个称为球树( b a l lt r e e ) 的数据 结构定义了k 维超球体( “球 ) ，它覆盖了所有的数据点，并将它们安排成一个树 结构 2 2 3其他的分类技术 决策树分类算法 1 5 】以树形结构表示分类结果，树根节点代表整个数据集合空 间，每个分支节点是对一个属性的测试，该测试将数据集集合空间分割成两个或 多个块，而每个叶子节点代表一个类由根结点到叶节点的路径描述了各种分类 规则基于决策树的分类算法很多，比较有影响的有i d 3 、c 4 5 、c a r t 、s l i q 、 s p r i n t 、b o a t 和c l o u d s 等算法和r a i n f o r e s t 框架 i d 3 算法 1 6 是国际上最早、最有影响力的决策树算法，i d 3 算法是基于信息 熵、使用增量式学习技术的决策树分类算法，根据属性集的取值选择实例的类 别它采用自顶向下不可返回的策略，搜索出全部空间的一部分，它确保决策树 的建立最简单、每次所做的测试数据最少i d 3 算法构造的决策树平均深度较小， 分类速度较快c 4 5 1 1 7 算法解决了i d 3 算法中连续值数据的学习问题，而且能够 将决策树转化为等价的规则表示针对算法的可伸缩性，提出的适用于大的训练 数据集进行决策树归纳的算法，包括s l i q 1 8 、s p r i n t 1 9 和r a i n f o r e s t 2 0 判定 树归纳框架这些方法着重解决当训练数据量无法全部放入内存时，如何高速准 确地生成决策树s l i q 和s p r i n t 都是用了预排序技术，同时定义了新的数据结 构，以利于决策树的构造 神经网络【2 l 】最早是由心理学家和神经生物学家提出的，旨在寻求开发和测试 神经的计算模拟神经网络是组相互连接的输入输出单元，每个连接都与一个 权值相连在学习阶段，通过调整神经网络的权，使网络能够正确预测输入样本 的类标号来学习神经网络需要很长的训练时间，而且需要大量的参数，这些参 数主要靠经验确定，如网络拓扑结构人们很难解释蕴涵在学习权之中的符号的 9 含义，因此神经网络很难被理解和解释， 经网络有一些其他算法所不具备的优点， 未经训练的数据分类模式的优秀表现 神经网络的行为也像一个“黑盒子 神 如对噪声数据的高承受能力，以及它对 最临近分类是基于类比的学习训练样本用维数值属性描述，每个样本代 表维空间的一个点，所有训练样本都被存放在维模式空间中给定一个未知 样本，尽最临近分类法搜索模式空间，找出最接近未知样本的k 个训练样本这 k 个训练样本是未知样本的k 个近邻，临近性可以用欧几里德距离来定义给定 两个点胙伽i ，娩，而 和降秒l ，妮，龇) ，则欧几里德距离定义为 她驴三。( 一只) 2 ( 2 5 ) 未知样本被分配到k 个最临近者中最公共的类尽最临近分类是一种懒散的学习 方法，它保存所有训练样本直到未知样本需要时才建立分类，与决策树等急切学 习法形成鲜明的对比因为急切学习方法在接受未知样本之前，己经根据训练数 据集构造了一个一般的分类模型懒散学习法的所有计算都推迟到分类预测时进 行，因此如果训练集数据量很大，可能的临近者数量很大，懒散的学习方法可能 导致很高的计算开销，使分类过程变得缓慢 其他的分类算法还有很多，如支撑向量机、遗传算法、粗糙集算法、基于案 例的推理等多种类型的分类算法这些算法都具有自身的优点和不足，但是都在 一定的应用领域取得了成功如：支撑向量机具有良好的可伸缩性并且能够很好 的解决训练数据的过分拟合问题粗糙集方法分类可以发现不准确数据和噪声数 据的内在联系遗传算法和只能获得局部最优解的贪婪算法相比，通常能够获得 更具全局意义的满意解遗传算法易于并行，可以应用于分类和其他优化问题 上述类型的分类算法并不是彼此孤立的，有些分类算法可能会借鉴上述不同 类型算法的优点不存在某一类型或是某一个算法在所有的数据集上的分类准确 度、训练时间、强壮性、可规模化、可解释性等方面性能都优于其他类型的算法实 际应用中最好的解决方案常常是各方面性能要求的折中因此，评价一个算法的 优劣常常是结合具体的应用背景和领域要求 2 3分类模型的性能度量标准 分类模型的性能可以从多方面衡量，如：分类准确率、分类错误率、训练时 间、可伸缩性、健壮性和可解释性等分类模型的性能度量是评判分类器好坏的 前提，很多研究者提出了关于度量分类模型性能的标准，评价一个算法的优劣常 常是在具体应用背景的特定要求下进行的一般的来说，分类准确率是评估分类 l o 算法优劣的最常用的指标下面我们将从定性和定量两个方面来介绍较为重要的 度量分类模型性能的标准 对于数据量特别大甚至不能存放在内存的数据集，分类算法的可伸缩性显得 尤其重要另外，由于现实数据可能缺失属性和包含噪声，因此在某些应用中对 噪声数据的高承受能力成为对分类算法最基本的要求 2 3 1 分类性能评估定性标准 在比较不同的分类器时，常常参照的关键指标有 1 】： ( 1 ) 分类准确率 分类器正确预测新待测样本的类值的能力影响分类准确率的因素有：训练 数据集的样本数，属性数，属性中值的个数，待测样本的分布情况等 ( 2 ) 计算复杂度 计算复杂度决定着算法执行的速度和占用的资源，它依赖于具体的实现细节 和软硬件环境由于数据挖掘中遇到的经常是现实中的海量数据，因此空间和时 间的复杂度将是非常重要的课题 ( 3 ) 可解释性 分类结果的解释性是指容易理解的程度结果的可解释性越好，算法的可理 解性越高 ( 4 ) 可伸缩性 一个分类器是可伸缩的，是指在给定内存和磁盘空间等可用的系统资源的前 提下，算法的运行时间应当随数据库大小线性变化 ( 5 ) 稳定性 一个模型是稳定的，是指它没有随着它所针对数据的变化而过于剧烈变化 ( 6 ) 强壮性 是指在数据集中含有噪声等情况下，分类器正确分类的能力 一个模型总是综合考虑以上一个或多个因素，这主要取决于具体领域和用户 具体的要求 2 3 2分类性能评估定量标准 上面我们介绍了分类器性能评价的定性指标，本节介绍分类器性能评价的定 量标准，其中较常用的主要有准确度或错误度，查全率，查准率和f l 等 首先我们介绍混合矩阵，以两个类值的数据集为例表l 中，主对角线上分 别是被正确分类的正例个数( 和被正确分类的负例个数( z z v ) ，次对角线上分别是 被错误分类的负例个数( f ，即尸类错误分为类的个数) 和被错误分类的正例个 数，即类错误分为尸类的个数) 表1 两类问题的混合矩阵 t a b l elc o n f u s i o nm a t r i xo ft w oc l a s s e s 预测类值 pn p正确的正例( 错误的负例( 踟 实际类值 n 错误的止例( 删正确的负例( 刀v ) 由此混合矩阵我们可以得到：实际正例数p = - t p + f n , 实际负例数n = f p + t n ， 实际总数c 毛p + 另外，常用的数字评价标准： ( 1 ) 准确度( a c c u r a c y ) ：正确分类的测试实例个数占测试实例总数的比例， a c c u r a c y - - ( t p + t n ) c ( 2 ) 错误率( e r r o rr a t e ) ：错误分类的测试实例个数占测试实例总数的比例， 鼬e r r o rr a t e = l a c c u r a c y = l - ( t p + t n ) c = 世n + f n | c ( 3 ) 查准率( p r e c i s i o n ) ：正确分类的正例个数占分类为正例的实例个数的比例， 即p r e c h s i o n = t p ( 玎) + f p ) ( 4 ) 查全率( r e c a l l ) ：正确分类的正例个数占实际正例