（计算机软件与理论专业论文）基于eep的两阶段方法分类研究.pdf

摘要 羔二s 3 s 7 t 分类是数据挖掘中的一项非常重要的任务，几十年来一直是统计学、机器学 习、神经网络和专家系统等领域内的一个重要研究课题。目前在政府组织、科学 研究、商业等领域有着广泛的应用。在解决数据挖掘领域中的分类问题时，基于 规则的建模技术是很受欢迎的。但是，传统的基于规则的分类算法多数采用顺序 覆盖技术来训练分类规则，这种方法有着自身无法很好解决的问题，在稀有类分 类中这种问题更加突出。基于此，r a m e s h a g a r w a l 和m a h e s h v j o s h i 于2 0 0 0 年 提出了基于规则的两阶段方法，实验结果表明，两阶段方法能够很好地用于分类， 特别是在稀有类分类时取得了比其它分类算法更好的效果。 1 9 9 9 年d o n g 等人提出了一种被称作显露模式( e m e r g i n g p a t t e r n ，e p ) 的新的 知识模式，并受到了数据挖掘界的广泛重视。基于e p 的分类算法通过聚合多个 e p 的分类能力来分类，综合考虑了不同数据集在多组属性上的差异，能够弥补 传统分类方法( 如决策树方法) 只考虑一组属性而形成的缺陷，取得了很好的分 类结果。然而，对于稠密数据集和高维数据集来说，e p s 的数量巨大，因而增加 了算法的时空复杂度。2 0 0 0 年f a n 和r a m a m o h a n a r a o 又提出了一种特殊形式的 e p ：e e p ( e s s e n t i a le m e r g i n gp a t t e r n ，基本显露模式) ，有效遣解决了一般形式的 e p 在分类时的冗余问题，同时又不会丢失太多对分类有用的信息。 本文结合两阶段思想和e e p 在分类方面的优势，提出了一种新的分类算法 基于e e p 的两阶段方法分类( c l a s s i f i c a t i o no fe s s e n t i a le m e r g i r i gp a t t e r ni n t w op h a s e s ，c e e 盯p ) 。该算法使用两个阶段挖掘e e p 并用于分类，分类时考 虑第二阶段对第一阶段的修正作用，这与t p c e p 有些相似之处。与t p c e p 不同 的是，我们在分类时采用了以增长率为标准的评分策略，充分利用了e e p 的区 分能力；同时，我们通过调整第二阶段的权重，使之更好地发挥对第一阶段结果 进行修正的辅助作用。实验结果表明，c e e p t p 在u c i 机器学习库中的1 1 个数 据集上可以取得与已有的几个优秀分类算法如n b ，c a 。5 ，c b a ，c m a r ，c a e p , b c e p 相媲美的整体分类效果。同时，我们还将c e e p t p 与t p c e p 、c e e p 分别 在多个数据集上作了分类准确率对比，表现出较好的性能。最后，为了显示对第 二阶段作用的调整产生的影响，我们将调整前后的结果作了对比，结果表明，调 整后的结果比调整前有了一定的改善。 关键词：数据挖掘，分类，两阶段，显露模式，基本显露模式，增长率 a b s t r a c t c l a s s i f i c a t i o ni sa l li m p o r t a n td a t a m i n i n gt a s ka n dh a sc o n t i n u e dt ob ea n i m p o r t a n tr e s e a r c ht o p i ci nt h ef i e l d so fs t a t i s t i c s ，m a c h i n el e a m i n g , n e u r a ln e t w o r k s a n de x p e r ts y s t e m s i th a sb r o a da p p l i c a t i o n si ng o v e r n m e n to r g a n i z a t i o n s ，s c i e n t i f i c d o m a i n s ，a n db u s i n e s sc o r p o r a t i o n sa n ds oo n t e c h n i q u e st h a nl e a l t lr u l e - b a s e d m o d e l sa r e e s p e c i a l l yp o p u l a ri ns o l v i n g c l a s s i f i c a t i o n p r o b l e m s i nd a t a m i n i n g h o w e v e r , m o s to ft h et r a d i t i o n a lr u l e b a s e dc l a s s i f i c a t i o na l g o r i t h m su s es e q u e n t i a l c o v e r i n gt e c h n i q u ew h e nt r a i n i n gc l a s s i f i c a t i o nr u l e sw h i c hh a ss o m ec h a l l e n g i n g p r o b l e m sh a r dt ot a c k l e ，e s p e c i a l l yi nc l a s s i f i c a t i o nf o rr a r ec l a s s f o rt h i sr e a s o n ， r a m e s h a g a r w a la n dm a h e s hv j o s h ip r o p o s e dr u l e - b a s e dt w o p h a s ec l a s s i f i c a t i o n m e t h o di n2 0 0 0 ，a n di ts h o w st h a t t w o p h a s e m e t h o di ss u i tf o rc l a s s i f i c a t i o n ， e s p e c i a l l ys u p e r i o rt ot r a d i t i o n a la l g o r i t h m sa sf o r r a r ec l a s sc l a s s i f i c a t i o n ak i n do fn o v e lk n o w l e d g e p a t t e r n ，c a l l e de m e r g i n gp a t t e m p ) ( d o n g & l i ， 1 9 9 9 ) i si n t r o d u c e da n dh a sb e e ns u b s t a n t i a l l ys t u d i e di nd a t am i n i n g e p b a s e d c l a s s i f i c a t i o n a l g o r i t h m s c o n s i d e rm u l t i a t t r i b u t ed i s t i n c t i o n sb e t w e e nd i f f e r e n t s d a t a s e t sb ya g g r e g a t i n gt h ed i f f e r e n t i a t i n gp o w e ro fac o l l e c t i o no fe p s w h i c hm a k e u pt h el i m i t a t i o n so ft r a d i t i o n a le l a s s i f i c a t i o nm e t h o d sc o n s i d e r i n go n eg r o u po f a t t r i b u t e s ，a n da r r i v ea ts a t i s f y i n gr e s u l t s h o w e v e r , t h en u m b e ro fe p si nd e n s e d i m e n s i o n a ld a t a s e t si sh u g ew h i c hi n c r e a s e st h et i m ea n d s p a c ec o m p l e x i t y r e c e n t l y , an e wk i n do fe p s , n a m e de s s e n t i a le m e r g i n g p a t t e r n ( e e p ) ( f a n & r a m a m o h a n a r a o 2 0 0 0 ) i sp r o p o s e d a n di t c a ne f f i c i e n t l ym i n i m i z et h er e d u n d a n c eo fe p sw i t h o u t l o s i n gm u c h u s e f o li n f o r m a t i o ni nc l a s s i f i c a t i o n i nt h i sp a p e r , w ep r o p o s ean o v e la l g o r i t h m ，c a l l e dc e e p t p ( c l a s s i f i c a t i o no f e s s e n t i a le m e r g i n gp a t t e r n si nt w o p h a s e s ) , w h i c hc o m b i n e t h ea d v a n t a g e so ft w o p h a s e sf r a m e w o r ka n de e p i nc l a s s i f i c a t i o n c e e p t pm i n e se e p si nt w op h a s e sf o r c l a s s i f i c a t i o na n dc o n s i d e r sm o d i f i c a t i o no ft h es e c o n d p h a s ef o rt h ef i r s to n e w h i c h h a ss o m es i m i l a r i t i e sw i t hr i p c e p c e e p i 甲i sd 曲f e r e n tf r o mt p c e pi nt h a t ：1 ) i t t a k e san e ws c o r es t r a t e g yb a s e do n g r o w t h r a t eo fe a c he e pw h i c h s u f f i c i e n t l yu t i l i z e t h e i rd i f f e r e n t i a t i n g p o w e r , a n d2 ) i ta d j u s t st h ew e i g h to f t h es e c o n d p h a s e i no r d e rt o p l a yt h ea s s i s t a n tr o l ef o rr e m e d y i n g t h er e s u l to ft h ef i r s to n e n e e x p e r i m e n ts t u d y c a r r i e do n1 1b e n c h m a r kd a t a s e t sf 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 ys h o w s t h a tc e e p i 甲p e r f o r m sc o m p a r a b l yw i t ho t h e re x c e l l e n tc l a s s i f i c a t i o nm e t h o d ss u c h a sn b ，c 4 5 ，c b a , c m a r ，c a e p , a n db c e em o r e o v e r , c e e p t pa c h i e v e sb e t t e r c l a s s i f i c a t i o na c c u r a c yt h a nt p c e pa n dc e e po nm a n y d a t a s e t s f i n a l l y , i no r d e rt o s h o we f f e c t so fm o d i f y i n gt h er o l eo ft h es e c o n dp h a s e ，w ec o m p a r et h e r u n n i n g r e s u l t so fc e e f i pa n di t se d i t i o nb e f o r ea d j u s t e do n m a n y d a t a s e t s ，a n dt h er e s u l t si i n d i c a t et h a tc e e p l 瞪m a k e ss o m e i m p r o v e m e n t s j nc l a s s i f i c a t i o np r e s i c i o n k e y w o r d s ：d a t am i n i n g , c l a s s i f i c a t i o n ，t w op h a s e ，e m e r g i n gp a t t e r n s ，e s s e n t i a l e m e r g i n gp a t t e r n s ，g r o w t hr a t e i i 基于e e p 的两阶段方法分类研究 第一章绪论 近年来，随着各项工作和个人生活计算机化的不断深入，和当今计算机在存 储、处理和网络等方面能力的飞速发展，人们能够以极快的速度、从很大范围内 产生和收集数据，包括科学领域( 比如人类基因工程) 、政府组织( 比如入口普 查项目) 、以及商业集团( 比如超市交易) 。由于数据库和存储技术的飞跃发展， 把海量数据存储在c d r o m 、硬盘和磁带中形成堆积如山的数据已经是轻而易 举的事情了。 传统的把数据转化成知识的方法都依赖手工分析和解释，但是，对数据集的 这种形式的处理速度慢、代价高，并且有很大的主观性。事实上，随着数据量和 维数的动态增长，这类手工的数据分析在许多领域内已经完全不可行了。数据库 大小以两种方式增加：1 ) 记录或对象的数目；2 ) 对象的字段或属性个数。包含 1 0 9 个对象的数据库越来越司空见惯，比如在天文学方面。同样，字段数目也很 容易达到1 0 2 甚至1 0 3 ，比如在医疗诊断应用中。谁能够全面掌握这样上百万条 具有上百个字段的数据呢? 我们相信这不是人类所能完成的工作，因而，分析工 作需要自动化，至少是部分的自动化【”。 我们需要增强人类自身的分析能力以便处理我们收集的大量数据，而且这种 需要无论从科学上还是经济上都是值得的。商家通过运用数据来增强竞争优势、 提高生产效率、以及为客户提供更有价值的服务。我们获取的关于环境的数据则 可以作为基本的证据来构建关于我们生存的宇宙的理论和模型。既然计算机使得 我们能够收集远远超过我们的理解能力的数据，那么，让计算机去帮助我们从大 规模数据中发现有意义的模式和结构也就是自然而然的了【2 1 。因此，我们目前面 临的最大困惑就是“数据爆炸，知识贫乏”，如何有效地从堆积如山的数据中发 现有用的知识是一个极具挑战性的课题。 1 1 k d d 和数据挖掘 1 1 1 基本定义 在当今这个数据信息时代，人们迫切需要新一代的计算理论和计算工具来帮 助人类从快速增长的信号数据中提取有用的信息( 知识) ，这些理论和工具正是 1 基于c e p 的两阶段方法分类研究 新兴学科一数据库的知识发现( k n o w l e d g e d i s c o v e r y i nd a t a b a s e s ，k d d ) 雌捌 的主题。传统上，k d d 如下定义： k d d 就是识别数据中有效的、新颖的、潜在有用的并且最终可被人们理解 的模式的非平凡的过程。 这里，“数据”就是一组事实的集合( 如关系数据库中的记录) 。而“模式” 是这个定义中的核心词，它用来描述数据的一个子集或者适用于这个子集的模型 的一种语言表达形式，并且由一些有趣的特性比如有效性、新颖性、有用性和可 理解性来限制，提取模式也可以被认为是从数据中发现结构，或者，更抽象地说， 对数据集作一些高层次的描述。“过程”一词暗示着k d d 包含许多步骤，这些 包括数据准备、模式搜索、知识评价和反复的修改求精，每一步都可以多次重复。 “非平凡”则表示涉及到一些搜索和推理，要有一定的智能性和自动性( 简单地 求平均值或者求所有数据的总和都不算是知识发现) 。k d d 过程中至关重要的一 步就是标识“非平凡”的模式，这一步被称为数据挖掘( d a t am i n i n g ) ，它由特 定的算法组成，这些算法能够在可以接受的计算效率限制内产生一定数量的有用 的模式。发现到的模式应该是对新数据有一定程度的有效性( c e r t a i n t y ) 。我们还 期望模式是新颖的并且是潜在有用的，也就是说，能够为用户或者解决问题提供 一些帮助，用在决策支持系统中能够提高经济效益。最后，模式还必须是可理解 的，要么能够立即被理解，要么经过一些预处理。有趣性( i n t e r e s t i n g n e s s ) 通常 是衡量一个模式价值的综合标准，它包含了有效性、新颖性、有用性和简单性。 在给定这些概念的前提下，如果一个模式超过了一定的有趣性阂值，我们就 认为它是知识。事实上，这种定义的知识纯粹是面向用户、基于特定领域的，并 且决定于用户使用什么样的函数以及采用的阈值。 1 1 2k d d 和数据挖掘的关系 历史上，关于从数据中发现有用模式的术语除了数据挖掘之外，还有一些与 之类似但稍微不同的概念，如知识提取、信息发现、信息获取、数据考古和数据 模式处理【2 4 1 。数据挖掘大多被用于统计学、数据分析和管理信息系统中，在数 据库领域中也比较常见。k d d 一词在1 9 8 9 年被首次提出，它强调知识是数据驱 动的发现的最终产品，在人工智能和机器学习领域中最为常见。 2 基于e e p 的两阶段方法j 类研究 关于数据挖掘和k d d 的关系有两种不同的观点：一部分人把数据挖掘视为 k d d 的同义词，而另一部分人则认为k d d 是指从数据中发现有用知识的全过 程，而数据挖掘指这一过程中的一个基本步骤，专指应用特定算法从数据中抽取 模式。k d d 过程中的步骤包括数据准备、数据选择、数据清理、对先验知识的 适当整合、数据挖掘、以及对挖掘结果的恰当解释，这些对于保证能够从数据中 提取有用的知识也是很重要的。盲目的应用数据挖掘方法是一个危险的活动，很 容易造成的结果就是发现一些无意义的、无效的模式。 1 1 3 数据挖掘概述 数据挖掘( d a t am i n i n g ) ，也叫数据开采、数据采掘，就是按照既定的业务 目标从海量数据中提取可以解释为知识的规则( 或模式) ，包括关联规则、特征 规则、区分规则、分类规则、总结规则、偏差规则、聚类规则等1 4 引。 大多数据挖掘方法都基于来自机器学习、模式识别、神经网络和统计学的试 探( t r i e d ) 和测试( t e s t e d ) 技术：分类、聚类、回归等等，这些技术对应的方 法对于无论新手还是有经验的数据分析家都常常带有很大的迷惑性。 可以认为，数据挖掘方法主要有3 部分组成：模型表示、模型评价和搜索【2 】。 模垄襞豕是一种用于描述能够被发现的模式的语言。如果这种表示太受限 制，再多的时间和例子也不能够为数据产生一个精确的模型。对一个数据分析家 来说，充分掌握可能隐含在特定方法中的有代表性的假设是很重要的。同样，对 一个算法设计者来说，能够清楚地表达一个特定算法能作出什么样的有代表性的 假设也非常重要。注意，随着模型表示能力的增强，模型对于训练数据的过适应 性( o v e r f i t t i n g ) 的危险性也与之增加，从而导致它对未知数据的预澳4 准确性降 低。 貘型炉诊葫豫邑对一个特定模式( 模型及其参数) 满足k d d 过程目标的程 度的定量描述( 或适应性函数) 。例如，我们常常用模型对于测试数据的预测正 确性来判断其性能。描述模型可以通过其预测准确度、新颖性、可用性和可理解 性的度量尺度来评估。 镬案苏兹由两部分组成：参数搜索和模型搜索。模型表示和模型评价标准一 旦确定，数据挖掘问题就简化为纯粹的优化任务：从已选择的模型家族中寻找能 够优化评价标准的参数和模型。参数搜索时，算法必须在给定观察数据和固定的 3 基于e e p 的两阶段方法分类研究 模型表示的情况下，搜索能够优化模型评价标准的参数。模型搜索以循环的形式 发生在参数搜索方法之上：改变模型表示以便考虑整个模型家族。 1 1 4 研究和应用面临的挑战 k d d 研究和应用已经取得令人嘱目的成绩，与此同时，一些尚未解决和完 善的具有挑战性的难题也摆在了研究者面前1 2 3 捌，它们是算法的效率和可规模 性、过适应问题、数据的时序性、丢失的数据和噪声数据处理、字段间的复杂关 系、模式的可理解性、用户交互性和先验知识、与其他系统的集成、互联网上的 知识发现、私有数据的保护和数据安全性等等，有效解决上述问题将具有非常重 要的意义。 1 2 分类 数年来，分类问题一直是机器学习、模式识别和统计学领域的一个重要研究 课题，目前也成为数据挖掘的一个重要任务，当数据库中包含的实例能够作为将 来制定决策的基础时，分类特别有用，比如用于评估信用风险、医疗诊断、科学 数据分析等等。首先引入几个基本定义： 样本也称为实例，指分类算法作用的对象，是现实世界数据集合的一个真子 集，一般以元组的形式存放：类标号是样本的一个重要属性，用于标识元组所属 的类别；分类器，也称为分类函数或分类模型，是指一个有学习能力并且能通过 其内部结构给未知类标号的实例确定类标号的系统模型；分类器的精确度 ( a c c u r a c y ) 就是给一个随机选择的样本正确分类的概率；训练数据集是为建立 分类器而被分析的数据元组集合，其中的单个元组称为训练样本；测试数据集是 为评估分类器的性能而被分析的数据元组集合，其中的单个元组称为测试样本。 现在，分类过程主要是在计算机程序的支持下完成的，这样分类就获得了比 以前更快的性能。这就可以更好地让数据“讲话”，让机器“思考”。 1 2 1 有指导的分类和无指导的分类 根据分类任务侧重的具体目标，分类问题可以分为两类：有指导的和无指导 的【1 ，6 1 。假设给定一个实例集合，无指导分类( 也称为聚类) 就是定义类和确定 实例所属类的过程。这一过程的主要目标就是发现样本点之间最本质的“抱团” 4 基于e e p 的两阶段方法分类研究 性质并形成类：在选定了表示样本的特征之后，样本点就表示特征空间中的一个 点，如果再选定样本点之间的相似性度量函数，那么结果就应该是确定的总 之，它是样本点“抱团”性质的一种客观反映。通常，每个类有一个与其他类不 同的标号。无指导分类任务的第二个目标是把一个新的实例归类到已有的簇中， 或者生成一个包含新实例的新簇。 另一方面，在有指导的分类中，每个给定实例的类标号必须明确给出( 这在 无指导分类中不是必需的) ，并且需要一个训练数据集。主要目标就是从给定训 练数据集中获取知识( 规则或模式) ，然后以发现的知识为指导把每一个新实例 分到预先定义的某个类中。在这个过程中，需要有领域专家知识的指导，有领域 专家指明哪些样本属于一个类，哪些样本属于另一个类，但是这种先验知识常常 具有很大的主观性不同领域的专家有不同的观点，即使是同一领域的不同专 家观点之间也会有很大的差异。 然而，如果从信息粒度的角度来看的话，就会发现二者也有很大的相通之处： 前者操作实际上是在一个统一的粒度下进行计算，而后者操作是在不同的粒度之 下进行计算。信息粒度是对信息和知识细化的不同层次的度量，因为人们在认知 和处理现实世界的问题时，常常采用从不同层次观察问题的策略，即往往从不同 的信息粒度上观察和分析同一问题【6 】。 1 2 2 分类器的构造 分类的目的是构造一个分类器，并用它对新的未知的数据分类，以用于决 策支持。其构造过程分两步【4 】：第一步，建立一个模型，描述预定的数据类集和 概念集，通过分析由属性描述的训练数据集来构造模型。假定每个元组属于一个 预定义的类，由一个类标号属性确定。这一步称为“训练阶段”或“学习阶段”。 第二步，使用模型进行分类。首先使用测试集评估模型的预测准确率( 这一步称 为“测试阶段”) ，如果认为模型的准确率可以接受，就可以用它对类标号未知的 数据元组或对象进行分类。 分类器的构造方法有统计方法、神经网络方法、机器学习方法和粗糙集方 法等等【3 1 。 统计学方法 统计学方法包括贝叶斯方法和非参数法( 近邻学习或基于范例的推理) ，对 s 基于e e p 的两阶段方法分类研究 应的知识表示则为判别函数和原型事例。 1 贝叶斯方法 分类规则发现是根据客体的特征向量值及其它约束条件将其分到某个类 中。在数据挖掘中，主要研究如何从数据或经验中学习这些分类规则。对于分类 问题，有些情况下，输入特征向量唯一对应着一个类别，这种问题称为确定性的 分类问题；而更多的情况是，来自于不同类别的样本从外观特征是具有极大的相 似性，而我们去必须为它选择一个类别。贝叶斯方法能够很好地处理这类不确定 性问题，它的特点是以概率去表示所有形式的不确定性，学习或其他形式的推理 都用概率规则来实现。贝叶斯学习的结果表示为随机变量的概率分布，它可以解 释为我们对不同可能性的信任程度。 最为简单的贝叶斯分类方法是朴素贝叶斯分类 7 1 ( n a i v eb a y e s ，n b ) ，它建 立在一个假设的基础上：一个属性值对给定类的影响独立于其它属性的值，这一 假定称为“类条件独立”。这种方法虽然思想简单，但从分类算法的比较研究发 现，其性能可以与决策树和神经网络分类算法相媲美，对于大型数据库能够表现 出高准确率与高速度。 朴素贝叶斯分类的假设的好处是简化了计算，但是，这种假设在现实世界 中不是总能成立的，因为各个属性之间可能是或多或少地相互依赖的。贝叶斯信 念网络( b a y e s i a n b e l i e f n e t w o r k s ) 说明联合概率分布，它允许在变量的子集间定 义类条件独立性，还能够表示属性子集间的依赖。它提供一种因果关系的图形， 可以在其上进行学习。 贝叶斯网络的知识表示为判别函数，与数据挖掘中的其他知识表示的方法 如决策树、人工神经网络等相比，它具有以下优点：( 1 ) 贝叶斯网络能够很方便 地处理不完全数据；( 2 ) 贝叶斯网络能够学习变量间的因果关系；( 3 ) 贝叶斯网 络与贝叶斯统计相结合能够充分利用领域知识和样本数据的信息；( 4 ) 贝叶斯方 法与其他模型相结合，有效的避免了数据的过适应。 2 近邻学习方法( n e a r e s tn e i g h b o r ) 近邻分类基于类比学习。训练样本用n 维数值属性描述，每个样本代表n 维空间的一个点。这样，所有的训练样本都存放在n 维模式空间中。给定一个未 知样本，k - 近邻分类法搜索模式空间，找出最接近未知样本的k 个训练样本。 基于e e p 的两阶段方法分类研究 这k 个训练样本是未知样本的k 个“近邻”。“临近性”有不同的定义方式，最 简单的就是欧几里德的距离定义，即根据两个点之间的距离来确定二者的临近 性。 未知样本被分配到k 个最临近者中最公共的类中，如果这些点属于不同的 类，则可以通过某种判断策略( 如多数表决方式) 来确定该未知样本的最终归属。 近邻分类是基于要求的或懒散的学习法，即它存放所有的训练样本，并且 直到新的( 未标记的) 样本需要分类时才建立分类。而急切学习法( 如决策树归 纳或后向传播) 则在接受新的样本之前构造一个一般模型。正如所预料的，懒散 学习法在训练时比急切学习快，但在分类时很慢，因为当与给定的无标号样本比 较的可能的临近者( 即存放的训练样本) 数量很大时，懒散学习法可能有很大的 计算开销。 3 基于范例的推理( c a s e - b a s e d r e a s o n i n g ，c b r ) k o l o d n e r 在“c a s e - b a s e dr e a s o n i n g ”一书中给出了范例( c a s e ) 的一个定 义：“范例是一段有上下文信息的知识，该知识表达了推理机在达到其目标的过 程中能起到关键作用的经验”【3 l 。 基于范例推理作为一种方法论是合理的，因为客观世界有两个特点：规整性 和重现性。世界从整体上看有一定的规整性，相似条件下发生的动作会产生相似 的结果。“历史是惊人的相似”，过去的经历很有可能预示未来。 基于范例的推理分类法是基于要求的。跟近邻学习方法不同，它不将训练样 本作为欧氏空间的点存放，c b r 存放的样本或“范例”是复杂的符号描述。其 分类过程如下：当给定个待分类的新范例时，基于范例的推理首先检查是否存 在一个同样的训练范例。如果找到一个，就返回附在该范例上的解，否则，基于 范例的推理将搜索具有类似于新范例成分的训练范例。概念上讲，这些训练范例 可以视为新范例的邻接者，c b r 试图组合临近的训练范例，提出新范例的解。 如果解之间出现不相容，可能需要回溯搜索其它解。 c b r 存在的挑战包括找到一个好的相似性度量( 例如匹配子图) ，开发对训 练范例索引的有效技术和组合解的方法。 机器学习方法 机器学习方法中决策树法的用途最广，对应的知识表示为决策树或判别树 7 基于e e p 的两阶段方法分类研究 ( d e c i s i o nt r e e ) 。决策树学习1 3 , 4 1 是以实例为基础的归纳学习算法。它着眼于从一 组无次序、无规则的实例中推理出决策树表示形式的分类规则。它采用自顶向下 的递归方式，首先选择训练样本的一个子集以形成一个决策树，在决策树的内部 结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树 的叶结点得到结论。所以从根到叶子节点的一条路径就对应着一条合取规则，整 个树就对应着一组析取表达式规则。基于决策树的学习算法的一个最大优点是它 在学习过程中不需要使用者了解很多背景知识( 同时这也是它的最大缺点) ，只 要训练例子能够用属性一结论式的方式表达出来，就能使用该算法来学习。基于 决策树的分类方法是一种监督学习的方法，树的数量决定于分类的精度和树的大 小，决策树的构造过程也就是假设特化的过程。 c l s 学习算法是早期的决策树学习算法，其基本思想是从一个空的决策树 出发，通过选取测试属性、添加新的评定节点来改善原来的决策树，直至该决策 树能够正确地将训练实例分类为止。c l s 学习算法的缺点是，它每次运行开始的 时候都要知道所有训练实例，当训练集过大的时候，实例无法立刻全部放入内存， 会发生一些问题。 关于如何选取测试属性，有多种选择标准。最有影响的是o u i n l a n 在1 9 7 9 年提出的i i ) 3 算法【8 】，它以信息熵的下降速度作为选取测试属性的标准，另外， 它还引入了增量式学习的技术。i d 3 的不足之处：( 1 ) i d 3 算法偏向于选择属性 值较多的属性，而属性值较多的属性却不总是摄优的属性；( 2 ) 学习简单的逻辑 表达能力较差。 自i d 3 出现后，研究人员围绕该算法展开了大量的研究，提出了许多富有成 效的改进、优化算法。其工作主要集中在如下几个方向：( 1 ) 扩充决策树属性的 取值范围及改进选择分离属性的选择；( 2 ) 提高决策树构造效率，削减数据库遍 历次数，减少i 0 操作；( 3 ) 优化决策树，简化决策树输出；( 4 ) 扩充决策树， 形成决策图；( 5 ) 将遗传算法、神经网络技术引入决策树算法。 c 4 5 算法【9 】是对1 ) 3 算法的补充和改进，其基本思想是先从所有的实例中 选取一部分构造决策树，再用剩下的实例测试决策树并对它进行调整。它不仅能 处理连续属性，还可以对属性的取值集合进行等价类划分，划分在同一类的属性 值在进行判断时走向同一分支。 8 基于e e p 的两阶段方法分类研究 无论是i d 3 还是c 4 5 ，虽然对c l s 作出了很多改进，但这些早期的算法都 存在着一个共同的缺陷：都是基于内存的，不能有效地解决大型数据库的数据挖 掘问题。近年来，研究者们针对算法的可规模性作了大量的工作，提出了如 s l i q 1 0 、s p r i n t l l ”、“雨林”算法【1 2 】和b s d t 等些伸缩性较好的算法。 神经网络方法 神经网络最早是由心理学家和神经生物学家提出的，目的在于寻求开发和 测试神经的计算模拟。粗略的说，神经网络是一组连接的输入输出单元，其中 每个连接都与一个权相联。在学习阶段，通过调整神经网络的权，使得能够预测 输入样本的正确类标号来学习。由于单元之间的连接，神经网络学习又称连接者 学习。 神经网络的学习问题 3 娥是网络的权值调整问题，其学习方法归纳起来有如 下几种类型：从学习过程的组织与管理而言分为有监督学习与无监督学习；从学 习过程的推理和决策方式而言分为确定性学习( 大多数学习方法属于此类) 、随 机学习和模糊学习。 b p ( 后向传播) 算法【4 ，1 3 】是一种主要的神经网络方法，它的模型是前向反 馈神经网络模型( 代表神经元的节点和代表联结权值的边组成的一种体系结构) ， b p 算法本质上是一种非线性判别函数，它为多层前向神经网络的研究奠定了基 础。“后向传播是如何工作的呢? ”后向传播通过迭代地处理一组训练样本，将 每个样本的网络预测与实际中的类标号比较进行学习。对每个训练样本修改权 值，使得网络预测和实际类之间的均方误差最小。这种修改“后向”进行。即由 输出层，经过每个隐藏层，到第一个隐藏层( 因此称为后向传播) 。一般地，权 值最终收敛( 尽管不能保证) ，学习过程结束。 神经网络的优点包括其对噪声数据的高承受能力，以及它对未经训练数据 的分类能力。但是，神经网络学习的最大缺点是学习速度慢，它需要大量的参数， 这些通常要靠经验确定( 如网络拓扑) ，其次，它所表示的知识的可理解性很差。 粗糙集方法 现实生活中存在着许多不能简单地用真、假值来表示的含糊现象，如何表 示和处理这些现象就成为一个研究领域。 1 9 6 5 年z a d e h 提出了模糊集，但遗憾的是模糊集是不可计算的，即没有给 9 基于e e p 的两阶段方法分类研究 出数学公式描述这一含糊概念。直至2 0 世纪8 0 年代，波兰的p a w l a k 提出了粗 糙集( r o t l l ! hs e t ) 。粗糙集理论可以用于分类，发现不准确数据或者噪声数据内 在的结构联系，该理论基于给定训练数据内部的等价类的建立。形成等价类的所 有数据样本是不加区分的，即对于描述数据的属性，这些样本是等价的。给定现 实世界数据，通常有些类不能被可用的属性区分。粗糙集可以用来近似或“粗略 地”定义这种类。给定类c 的粗糙集定义有两个集合近似：c 的下近似和c 的 上近似。c 的下近似有一些这样的样本组成，根据关于属性的知识，它们毫无疑 问属于c 。c 的上近似由所有这样的样本组成，根据关于属性的知识，它们不可 能被认为不属于c 。 粗糙集方法的知识表示是产生式规则。例如，给定一个顾客信用信息的数 据库，可以学习分类规则，根据他们的信誉度优良或相当好来识别顾客。这样的 规则可以用来为以后的数据样本分类，也能对数据库的内容提供更好的理解。 粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据的信 息，比如统计学中的概率分布、d e m p s t e r - s h a f e r 理论中的基本概率赋值，或模糊 集理论中的隶属度或概率值。当然了，该理论也不是万能的，对建模而言，尽管 粗糙集论对知识不完全的处理是有效的，但是，由于这个理论没有包含处理不精 确或不确定原始数据的机制。因此，单纯地使用这个理论不一定能有效地描述不 精确或不准确的实际问题，这就意味着需要其他方法的补充( 如与证据理论和模 糊集理论的结合) 。 1 2 3 分类器的性能评估 为了使发现的知识更好地用于决策支持，人们总是期望使用“最好的”分类 器。因此，对分类器分类准确率进行有效地评估并且试图通过一些方式提高分类 器的准确率是很有必要的。 1 分类器的性能评估尺度 不同的分类器有不同的特点，在选择时必须参照以下几个评估尺度 3 j 4 ：预 测准确性、可理解性、计算复杂度和稳定性。没有普遍适用的分类模型，选择的 标准也会具体领域和我们期望模型所实现的功能而异。 预测准确性也可以称为正确性，它不是总能用一个简单的尺度来衡量的，但 是，对一些模型来说，一个整体上的正确度分值就足够了。一般来说，至少要用 n 基于e e p 的两阶段方法分类研究 到两个衡量标准：灵敏性( s e n s i t i v i t y ，预测到的正例与所有正例的比值) 和确 切性( s p e c i f i e i t y ，预测到的反例与所有反例的比值) 。这两个参数适用于有二值 结果的问题。例如，给定 r 个类标号己知的实例，其中m 个属于类白，心个 属于类c 2 。对一个分类器p ，如果把个实例标记为类c i ，而其中确实属于类 g 的实例数只有j7 个，如果把 声个实例标记为类g ，而其中确实属于类。 的实例数只有27 个，那么，我们说p 的灵敏性为m ，确切性为( - j ) 飓，而预测准确性为( j7 + 2 7 ) n 。 可理解性在许多领域内对于模型都有重要的意义。模型的这种特性使得它具 有很好的适应性并且易于改进。有一个共识就是模型越简洁可理解性越好，研究 者们最近把焦点集中于其他的因素，比如对于领域约束的依赖性。当今时代，医 学都要基于事实，在我们试图把医疗实践做得更加正规和客观的时候，形成符合 领域知识的有效的协议和指导规则是一个首要问题。要使指导规则有价值，可理 解性是必不可少的。有一个基本的事实表明，医务工作者比较喜欢那些不会破坏 已有规则的模型。 计算复杂度依赖于具体的实现细节和软硬件环境，由于在数据挖掘中的操作 对象是海量的数据库，因此空间和时间的复杂度将是非常重要的问题。 模型的稳定性可从结构上和功能上着眼，高稳定性意味着从不同部分样本中 产生的模型之间存在很小的变异( v a r i a n c e ) 。如果大部分随机生成的训练集能够 产生结构上相似的模型，就表明生成了一个稳定的模型。结构上不同的模型的功 能稳定性可以通过其对一个有代表性的测试样本在分类时的变异性来评估。 t u m e y 1 5 】讨论了决定模型稳定性的语法与语义上的相似度标准( 分别对应于结构 稳定性和功能稳定性) ，他赞成用语义相似度标准来确定稳定性，因为这种标准 对于代表的肤浅的变种不太敏感。 模型的适当性可以认为是它的正确性、可理解性、计算复杂度和稳定性的函 数，它往往是跟具体领域和具体用户相关的。在医疗领域中，如果一个模型能够 提供有效的指导，它在这些方面就能获得很高的分值。 在上面讨论的几种标准中，准确度是用得最多的一种。与之类似的另一个标 准被称为泛化误差【插l ( g e n e r a t i o ne r r o r ) ，是指分类器在测试数据集上产生的平 均误差。一般来讲，准确度越高，相应的泛化误差就越小。 基于e e p 的两阶段方法分类研究 2 准确度评估方法 分类准确度可以如下定义 p = ( 1 2 3 1 ) 其中，p 表示分类准确度， d 是由有限个以( x i ，y i ) 表示的样本组成的集合，x i 是数据样本中除y i 以 外的属性序列，y i 是指数据样本的类标号属性， g 表示分类器，输出结果为预测的类标号， f ( a ，b ) 是一个比较函数，输入为a 和b ，如果a = b ，输出1 ；否则，输 出0 。 常见的评估分类准确率的方法有以下几种1 1 , 1 6 , 1 7 , 1 8 , 1 9 ： 1 ) 保持方法( h o l d o u t ，简称h o ) ： 其执行步骤如下： 1 通过不旅佰描，擘粑数据集x 分为两个相互独立的子集：训练集品。 和测试集( 保持集) 。通常情况下，指定这个数据集的2 3 作 为训练集，而被其余的1 3 作为测试集； 2 用凰曲来训练分类器，用置。来评估该分类器的准确率p ： p = n | 3 ( 1 2 3 2 ) 其中，n 是指x 中的样本数。 2 ) 蒙特卡罗交叉验证( m o n t e c a r l oc r o s s v a l i d a t i o n ，或简称c v ) ； 其执行步骤如下： 1 不放回抽样方式从数据集x 中随机抽取样本；这些样本形成新的训 练集曲；x 中其余的元素形成测试集豇。通常，x 中的2 3 元 素作为墨曲，而剩下的1 3 作为置。； 2 用蜀m 来训练分类器，用五。来评估该分类器的准确率b ： 1 2 基于e e p 的两阶段方法分类研究 p t n 鸭 f ( g ，y i ) n | 3 ( 1 2 3 3 ) 其中，n 是指x 中的样本数。 3 步骤1 和2 循环k 次，k 越大越好。最终的分类器准确率如下定义： 足 v 只 尸