（计算机软件与理论专业论文）训练基于ep的分类器算法.pdf

摘要 数据挖掘又称数据库中知识发现，是从大量数据中用非平凡的方法发现有用 的知识。分类是数据挖掘中的一项非常重要的任务，在商业、金融、电讯、d n a 分析、科学研究等诸多领域具有广泛的应用。统计学、机器学习、神经网络等领 域的研究者提出了很多分类方法，大部分算法是内存驻留算法，适用于小型数据 集。随着数据集的数据量和维数的增加，建立高效的、适用于大型数据集的分类 法已成为数据挖掘的一个挑战性任务。 基于显露模式( e m e 蟛n g p a t c e m ，e p ) 的分类方法是针对大型数据集的分类 提出的，e p 是gd o n g 和j “提出的一种新的知识模式，这些模式能够捕获目 标类和非目标类上多组属性之间的不同，具有很好的分类性能。第一个基于e p 的分类算法是gd o n g 等提出的c a e p 算法，此后相继提出了j e p c l a s s i f i e r 、 b c e p 和d e e p s 等一系列基于e p 的分类算法。相关研究表明，基于e p 的分类算 法的平均分类准确率优于决策树等传统算法，显示了e p 在分类方面的优越性。 本文提出了一种可调整权值的基于e p 的分类方法c e p a w 。c e p a w 使用基 本显露模式( e e p ) 并聚合e e p 的区分能力建立分类器。在聚合e e p 的区分能 力时，e e p 的权值通过训练自适应地选取。训练分为两个阶段：第一阶段的主要 任务是挖掘e e p s ，构造初始分类器。在e p 的选取以及评分函数方面。我们都采 用了不同于以往的基于e p 的分类算法的方法。第二阶段是权值的自适应调整。 丌始，所有e p 的权值相同。反复地使用初始分类器对训练样本进行分类，并通 过考察每个e p 对训练样本的分类效果调整e p 的权值，直到分类器的分类准确 率不能再提高。 为了测试算法的分类性能，使用了u c i 机器学习库中的1 2 个数据集作为实 验数据集，并将实验结果与n b 、c 5 o 、c a e p 、l b 以及b c e p 算法进行比较。 结果表明，c e p a w 具有更好的分类准确率，自适应地选取e p 的权值比以支持 度为权值的评分策略更加合理。当数据分布发生轻微变化时，通过再训练，调整 e p 的权值，c e p a w 可以较好地适应新的数据分布。 关键字：机器学习，数据挖掘，分类，显露模式 a b s 8 c t a b s t r a c t d a t am i l l i n g ，a l s oh l o w n 鹤i ( i l o w l e d g ee 畦8 c o v e r yi nd a t a b a s e ，r e f b r st o m i n i n g k n o w l e d g e 丘d md a t a i nv e r yl a r g ed a t a b 嬲e si nn 0 枷v i a lm e m o d s c 1 a s s i f i 训o n ，a sa l li m p o n a f l tt l l e m ei nd a t a 嘶n i n 岛h a sb e e nr 鼯e 盯c h e de d i 盯i n s t a t i s t i c s ，m a c h i n el e a r i l i n & n e u r a ln e t w o r k ，e x p e ns y s t e i t l s ，e t c b u tm o s ta 1 9 0 r i t l l m s a r ec o n 6 n e d m e m o r y ，t y p i c a l l y 鹊s u m i n gas m a l ld a t as i z c w i t h 也eg r o w t ho fd a t ai n v o l 啪ea i l dd i m e l l s i o m l i t y ，i ti ss m lac h a l l e l l g et ob u i l de f f t i v ec l a s s m e r sf o rl a r g e d a t a b a s e s m e t l l o d sf o rc l a s s i f i c a t i o nb ye m e f g i n gp a t t e m s ( e p s ) w e r ep m p o s e di no r d e rt o c l a s s 母l a r g ed a t a s e t s e p sa r en e wl 【i n do fl ( 1 l o w l e d g ep a t c 锄p r e s e n 硼b ygd o n g a n dj “i n1 9 9 9 ，w h i c hc a nc 印m r cm ei n h 删l td i s d n c t i o n sb c t w e e nd i f f 旨t c l a s s e so f d a t a s oe p sa r cu s e 如l 衙b u i l d i n ga c c u 墙t ec l a s s i f i e r s c a e ew 】i i c hw a s p m p o s e db yl i ， d o n ga 1 1 dr 锄锄o h 柚啪oi n l9 9 9 ，i st h ef i r s te p - b a s e d c l a s s m c a t i o na l g o r i l i n a f t e rt l l a t ，as 商e so fe p _ b a s c dd 髂s 湎e r sw e r ep m p o s e do n e a f t e ra i l o m e rs u c ha sb c e p ，j e p d a s s m d e e p s ，e t c i th a ss h o w nm a te p _ b a s e d c l a s s i 矗e ri sb e t t e rt l l a ns o m ec l a s s i cc l a s s i f i c a t i o nm e l o d ss u c ha sd e c i s i o nt r e e s t h i sd i s s e r t a t i o np r o p o s e san o v e le p - b 踮c dc l a s s i f i c a t i o nm e t h o d ， c a l l e d c l a s s 硪c a d o nb ye m e r g i n gp a t t e m s 丽t ha d j u s t a b l ew e i 曲t s ( c e p a w ) i nt h e 响n i n g p h a s e ，c e p a wu s e sas p e c i a lk i n do fe p s ，c a l l e de s s e n t i a l 锄e r g i n gp a t t c i n s ( e e p s ) ， a n da g 争e g a t e sd i 彘r e n t i a t i n gp o w e r so fe e p st oc o n s m 】c tc l a s s i f i e r s i no r d e rt o a g 掣g a t ed i 丘孤t i a t i n gp o w c r so fe e p s ，e a c he e pi sa s s o c i a t e dw i t ha na d j u s t a b l e w e i 曲tt h a ti sc h o s e nb y 仃a 岫i n 吕t r a i n i n gi sd i v i d e di n t o 伽op h a s e s i nt h ef i r s t p h a s c ，e e p sa r em i n e da n da ni n i t i a ld a s s m e ri sc o n s t m c t e d o l l ra 1 9 0 r i t l l mi s d i 丘旨e n tf b mt l l ep r e v i o u se p _ b a s e da l g o r i t h m s 、v i 出r e s p e c tt ot h ek i n do fe pa 1 1 dt h e s c o r i r 喀矗m c t i o n i nm es e c o n dp h a s e ，m ew e i g h t so fc e p sa r ca d j u s t a b l eb yt r a i n i n g f i r s t l y ，w e i g h t so f a l le e p sa r es e te q u a l ly b yu s i n gm ei n i t i a ld a s s m e rt oc l a s s i 毋l e t r a i n i n gs 锄p l e si t e r a t i v e l y ，w ea d j u s tt h ew e i g h t so fe p sa c c o r d i n gt ot i l er e s u l t so f c l a s s i f 弭n g 吼t i lt h ea c c u r a c yr a t ec a nn o tb ei n c r e a s e d i no r d e rt oe s t i m a t e 廿l ea c c u 豫c yo fo u ra l g o t h m s ，o u re x p e m e n ts t u d yc 谢e d o n1 2b 髑曲m a 出d a l 够e t 8 台o m 乜弛u c 【m a c b i n ek ；蛐皿gr e p o s i t o r ys h o w st l l a t c e p a wp e r f o m l c 鼯c o m p a r a b l y 丽t l ld t l l 盯s t a t e - o f m e - a r td 鹊s i 丘c a t i o nm c l l l o d s s u c ha sn b ，c 5 o ，c b a ，c m a 咒c a e p 趾db c e pi nt e 肌so fo v e r a l lp r e d i c t i v e a c 咖c y - c o m p a r i n g 谢t l im c t l l o d s1 1 8 i n gs u p p o r t s 嬲w e i g h t s ，e x p 甜m e n t sh a v es h 嗍 t 1 1 a tc e p a wc a nc h o o s em o f er e 黯叩a b l ew e i 曲t st oa g 笋e g a l ed i 氆洲1 t i a t i n gp o w e 碍 o fe e p s w h e nt h ed a l ad i s m b u t i o nc h a i l g e ss l i 曲n y ，c e p a wc a i ia d a p tt ot l l en c w d a 协d i s m b u t i o nb yn 删i l i n g k e y w o r d s ：m a c i l i n el e 籼i n g ，d a t am i n i g ，c i a s s m c a t i o n ，e m e 唔n gp a t t e h l 郑重声明 本学位论文是在导师指导下独立撰写并完成的。除文中 已经注明引用的内容外，本论文不含任何其他个人或集体已 经发表或撰写过的作品或成果。学位论文没有剽窃、抄袭等 违反学术道德、学术规范的侵权行为，否则，本人愿意承担 由此产生的一切责任和法律后果。特此郑重声明。 学位论文作者( 签名) ：啦笔馁 口多年6 月年同 第一章绪论 第一章绪论 数据收集和数据存储技术的快速进步使得组织机构可以积累海量数据。然而 海量数据远远超过了人的驾驭能力，人们面临着“数据丰富，但信息贫乏”的尴 尬境地。因此，提取有用的信息成为巨大的挑战。通常，由于数据量太大，无法 使用传统的数据分析工具和技术处理它们。有时，即使数据集相对较小，由于数 据本身的非传统特点，也不能使用传统的方法。在其他情况下，需要回答的问题 也不能使用已有的数据分析技术来解决。这样，就需要开发新的方法。 数据挖掘是一种技术，它将传统的数据分析方法与处理大量数据的复杂算法 相结合。数据挖掘也为探查和分析新的数据类型，为使用新的方法分析原有的数 据类型提供了机会。 1 1 什么是数据挖掘 数据挖掘是在大型数据存储中，自动地发现有用信息的过程。数据挖掘技术 用来探查大型数据库，以发现先前未知的有用模式。数据挖掘还提供了一些机制， 用于预测未来的观测结果。许多人把数据挖掘和数据库中的知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b 8 s e s ，简称k d d ) 看作是等价的概念a 在这种 观点下，一种比较公认的定义是wj f r a w l e y ，gp i a t e t s k y s h 印i r o 等人提出的， 其描述为： “数据挖掘，即数据库中的知识发现( k d d ) ，是一个在数据中提取模式的 过程，这些模式是有效的、新颖的、有潜在实用价值的和易于理解的。” 而另一些人把k d d 看作发现知识的完整过程，数据挖掘只是这个过程中关 键的一个部分。这种观点对数据挖掘的定义是： “数据挖掘是数据库中的知识发现( k d d ) 过程中的一个步骤，这个步骤 由一些特定的数据挖掘算法组成，这些算法的任务是在满足一定计算效率的约束 条件下，从数据中提取有效的模式。” 1 2 数据挖掘的任务 通常，数据挖掘任务分两大类： 预测任务这些任务的目标是根据其他属性的值，预测特定属性的值。被预 第一章绪论 测的属性一般称目标( t a i 酣) 或依赖变量( d e p 姐d tv a r i 曲l e ) ，而用来做预测 的属性称解释( e x p l a l l a t o r y ) 或独立变量( i n d 印e i l d e n ta 州a b l e ) 。 摇述任务这里，目标是导出概括数据中潜在联系的模式( 相关、聚类、轨 道和异常) 。本质上，描述性数据挖掘通常是探查，并且常常需要后处理技术验 证和解释结果。 预测建模( p r 耐i c t i v em o d e 触g ) 涉及用函数为目标变量建立模型。有两类 预测建模任务：分类( c l a s s 壤c a t i o n ) ，用于离散的目标变量；回归( r e 掣e s s i o n ) ， 用于连续的目标变量。两项任务目标都是训练一个模型，它最小化目标变量预测 值与实际值之间的误差。预测建模可以用来确定顾客对产品促销活动的反应，预 测地球生态系统的扰动，或根据检查结果判定病人是否患有某种特定的疾病。 关联分析( a s s o c i a 廿蛆蚰a l y s i s ) 用来发现描述数据中强关联特征的模式。 所发现的模式通常用蕴涵规则或特征子集的形式表示。由于搜索空间是指数的， 关联分析的目标是以有效的方式提取最有趣的模式。关联分析的应用包括找出具 有相关功能的基因组，识别一起访问的w 曲页面，理解地球气候系统不同元素 之间的联系。 聚类分析( d u s t 盯蚰a l y s i s ) 旨在发现紧密相关的观测值组群，使得与属于 不同簇的观测值相比，属于同一簇的观测值相互之间尽可能类似。聚类用来对相 关的顾客分组，找出显著影响地球气候的海洋区域，压缩数据。 异常检测( a n o m a l yd e t e c d o n ) 的任务是识别其特征显著不同于其他数据的 观测值。这样的观测值称为异常点( a n o m a l y ) 或离群点( o u t l i e r ) 。异常检测算 法的目标是发现真正的异常点，而避免错误地将证常的对象标注为异常点。换言 之，一个好的异常检测器必须具有高检测率和低误报率。异常检测的应用包括欺 诈检测、网络攻击、疾病的不寻常模式、生态系统扰动。 1 3 数据挖掘算法的研究及应用概况 近十几年来，数据挖掘算法研究取得丰硕的成果，数据挖掘算法的主要研究 成果概要如下： 在关联规则研究方面的主要成果有：寻找频繁项集的a p r i o r i 算法、 f p g m w t l l 算法1 2 】针对不同情况设计的多维关联规则挖掘方法哪】和多层关联规 则挖掘方法【5 】等。 第一章绪论 在分类研究方面产生了多种分类方法和算法【6 】= 决策树分类算法、源于关联 规则的分类方法、贝叶斯分类方法、k 最i 临近分类、基于案例的推理、遗传算法、 粗糙集和模糊集方法等多种类型的分类方法。此外，还提出了以装袋( b a g g i n g ) 和提升( b o o s t i i l g ) 为代表的可以有效提升某些算法分类准确率的组合分类思想。 这些算法虽然来自不同领域并且具有各自不同的背景和特性，但是这些算法都在 一定的领域内取得了很大的成功。尽管我们把算法分为上述几个类型，但是这些 方法并不是孤立的，一个有效的分类算法可能是综合上述多种思想设计完成的。 关于分类研究的问题我们将在以后的章节做进一步的论述。 在聚类研究方面也存在多种算法：基于划分的聚类方法有k - m e a n s ， k m c d o i s 、和c i ，a r a 、c l a m n 等算法。层次聚类算法有a g n e s 算法、d i a n a 算法、b m t h 【”、c u r e 8 】、r o c k 9 1 、c h 栅d c o n 等算法。基于密度的聚类算 法有d b s c a 州1 ”、o p t i c s 、d e n c l u f l3 1 。基于网格的聚类方法有s t i n g 【1 4 】、 w a v e c l u s t 一15 1 、c l i o ue f l 6 等算法。基于模型的聚类算法有统计学方法 c o b w e b 【17 1 、c l a s s i t 、a u t o c l a s s 和神经网络方法 2 0 0 ”。 其他研究方向也取得了丰硕的研究成果，如序列模式的挖掘有 g s p 吲( g e n c r a l i z c ds e q u e n t i a lp a t t e m s ) 算法和 p r c f i x s p a n 吲( p r e f i x p 删e c t s e q u e n t i a lp a t t 锄i i l i m n 曲算法。w e b 挖掘研究有寻找权威页面的p a g c r a n k 【2 4 1 和 h i t s 2 5 1 算法( 目前g o o 掣e 搜索引擎使用该算法) 。总之，不同研究领域的研究 者都结合特定领域的应用背景和需求，成功的丌发出了多种类型的数据挖掘算 法。 1 4 本文的内容与组织 本文第一章简要介绍了数据挖掘的概貌。我们从数据挖掘概念的提出、研究 动态、应用概况，多个方面阐述了数据挖掘算法研究广阔的前景和很高的应用价 值，充分展示了本课题研究背景和意义。 本文的贡献主要包括以下几个方面：本文提出了种可调整权值的基于e p 的分类方法c e p a w ( c l a s s i f i c a t i o nb ye m e r g i n gp a t t e m sw i t h a d j u s t a b l ew e i 曲t s ) 。 c e p a w 使用基本显露模式( e e p ) 并聚合e e p 的区分能力建立分类器。在聚合 e e p 的区分能力时，e e p 的权值通过训练自适应地选取。与以支持度为权值的方 法相比，c e p a w 可以选取更合理的权值来聚合e e p 的区分能力。与现有的基于 第一章绪论 e p 的分类算法不同，本文所采用的初始分类器采用了增长率与e p 权值相结合的 评分策略。实验表明c e p a w 算法具有很高的分类准确率。 本文的其他部分将按如下结构组织： 在本文的第二章，我们将详细讨论分类的基本概念、常见的分类方法、分类 模型的准确性评估等问题。在本章将定义和阐明分类问题的最基本的概念以及分 类研究的一般过程，为我们下文深入探讨分类问题奠定基础。 在本文的第三章，我们详细介绍显露模式的概念以及现有基于e p 的分类算 法。通过本章的讨论，我们首先阐明e p 的概念、性质以及e p 的挖掘等问题。 其次通过对现有基于e p 的分类算法的介绍，可以更清楚的表明c e p a w 算法与 现有的基于e p 的分类算法之间的联系和区别。 在本文的第四章，我们介绍了一种可调整权值的基于e p 的分类方法 c e p a w 。在训练阶段，c e p a w 使用e e p 建立分类器，并在聚合e p 的区分能力 时通过训练自适应地确定e p 的权值。因为训练分类器分为两个阶段，我们分两 部分详细讨论了c e p a w 算法。首先介绍了初始分类器的构造，在e p 的选取以 及评分函数方面我们的初始分类器都不同于以往的基于e p 的分类算法。在训练 的第二部分，我们主要介绍了权值的自适应选取策略。 在本文的五章，我们给出了c e p a w 算法在u c i 机器学习库上的实验结果以 及与其他算法的对比分析。通过实验数据我们进一步讨论了c e p a w 算法的分类 特性，对算法进行了更深入的探讨。 第二章分类 第二章分类 数年来，分类问题一直是机器学习、模式识别和统计学领域的一个重要研究 课题，目前也成为数据挖掘的一个重要任务，当数据库中包含的实例能够作为将 来制定决策的基础时，分类特别有用，比如用于评估信用风险、医疗诊断、科学 数据分析等等。 2 1 分类概念 能够学习如何把一个对象划分到预定义的类被认为是智能的一个重要特征， 在人工智能、机器学习和神经网络等方面都有广泛的应用，这类任务被称作分类。 分类是一种有指导的学习，即学习过程是在被告知每个训练样本属于哪个类的 “指导”下进行的。 分类问题可以描述为：数据是一张标准关系表，它包含个记录，这些记 录通常称作元组( m p l e s ) 、实例( i n s t a l l c e ) 或样本( e x 锄p l e ) 。每一个实例用固定数目 的度量标准描述，这种度量标准称作属性( a t t r i b u t e ) 。每一个属性都有一个合法的 取值范围，称作该属性的域( d o m a i n ) 。如果属性域是实数域，那么则称该属性为 数值属性( n u m c r i c a la 州b 1 1 t e ) 或连续属性( c o n t i n u o l l sa t 城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 e a t 埘b u t e ) 。这些属性中有一个区别于其他的称作类标号( d a s sl a b e l ) ，类标号指示 元组所属的类。除了类标号之外的其他属性是预测未知样本类型的依据，因此也 称作预测属性( p r e d i c t o ra t 雠b u t e s ) 。 在分类研究中，数据集通常被分成训练集和测试集。训练集用来构造分类器， 测试集用来评估分类器的预测准确度。因为学习算法可能对数据的过分特化，所 以使用训练数据构造分类模型，然后用同样的数据集评估分类模型可能导致过于 乐观的估计。因此，通常采用测试集来评估分类模型。在分类研究中，通常采用 u c i 机器学习库例( u c im a c h i n el e a r i l i n gr 印o s i t o 啪中的数据集评估不同的分类 模型。这些数据集来自广泛的应用领域，并且不同数据集的规模、目标类的个数 和属性个数变化很大，能够比较全面的反映算法的分类性能。 分类过程可以描述为如下两个步骤： 第一步是建立一个模型，描述预定的数据类或概念集。训练阶段的目的是建 第二章分类 立分类器，即从训练数据集中获取可以进一步指导未知数据分类的专家知识。不 同的分类模型可能用不同的形式描述用于指导分类的知识，如分类规则、决策树 或数学公式等。这些分类模型以不同的形式描述了某个类区别其他类的特征概念 集。从另一个角度来看，也可以认为分类模型是以某种特定的形式描述了训练集 的数据分布特征。如果训练集能够代表整体数据分布特征，那么由训练集获得的 特征概念集就可以用来指导对未知数据的预测。 第二步，使用模型进行分类。在使用分类模型对未知类标号的实例或对象分 类之前，首先要使用测试集评估分类模型的分类准确率。如果分类准确率是可以 接受的，那么我们才可以真正把该模型用于指导未知元组的分类。有多种技术用 来评估分类模型的准确性，关于模型的评估的问题，本文在本章第3 节做进一步 论述。 2 2 基本的分类技术 分类技术在不同领域有广泛应用，因此，统计学、机器学习、神经网络等领 域的研究者提出了很多的分类方法。这些算法来自不同的领域、工作原理差别很 大，但是都在相应的领域取得了成功。本节将简要介绍分类的基本技术。现有的 分类技术主要有：基于决策树的分类、贝叶斯分类、基于案例的推理、基于源自 关联规则挖掘概念分类、神经网络、遗传算法、模糊集和粗糙集方法等。 2 2 1 基于决策树的分类 决策树学习【2 7 0 8 1 是以实例为基础的归纳学习算法。它着眼于从组无次序、 无规则的实例中推理出决策树表示形式的分类规则。它采用自顶向下的递归方 式，首先选择训练样本的一个子集形成一颗决策树，在决策树的内部结点进行属 性值的比较并根据不同的属性值判断该结点向下的分支，在决策树的叶结点得到 结论。所以从根到叶子节点的一条路径对应着一条合取规则，整个树就对应着一 组析取表达式规则。基于决策树学习算法的一个最大优点是它在学习过程中不需 要使用者了解很多背景知识( 同时这也是它的最大缺点) ，只要训练例子能够用 属性一结论式的方式表达出来，就能使用该算法来学习。基于决策树的分类方法 是一种监督学习的方法，树的数量决定于分类的精度和树的大小，决策树的构造 过程也就是假设特化的过程。基于决策树的分类算法很多，比较有影响的有i d 3 、 第二章分类 c 4 5 、c a r t 、s u o 、s p r t 、b o a t 和c ir 0 1 j d s 等算法和r 血l f 嘴t 框架。 i d 3 算法【2 册是国际上最早、最有影响力的决策树算法。该算法是j r d s s q 1 1 瑚蛆在1 9 8 6 年提出的。d 3 算法是基于信息熵、使用增量式学习技术的决策 树分类算法，根据属性集的取值选择实例的类别。它采用自顶向下不可返回的策 略，搜索出全部空间的一部分，它确保决策树的建立最简单、每次所做的测试数 据最少。l d 3 算法构造的决策树平均深度较小，分类速度较快。 但是i d 3 算法本身也存在些不足，如：m 3 算法偏向于选择属性值较多的 属性，学习简单的逻辑表达能力较差等。由于i d 3 算法的广泛应用，研究人员围 绕该算法做了大量富有成效的研究工作。1 9 9 6 年，j r o s sq u i n l a l l 对i d 3 算法进 行了补充和改进，提出了c 4 5 算法1 3 0 l 。c 4 5 算法不但解决了连续值数据的学习 问题，而且能够将决策树转化为等价的规则表示。但是c 4 5 算法同样存在一些 不足之处，如：c 4 5 算法采用分而治之的策略所得到决策树不一定是最优的， 决策树的结构调整、性能改善较困难等。 大部分决策树都限定训练样本驻留内存，这一限制制约了算法的可伸缩性。 在数据挖掘应用中，包含数以百万记的训练样本的非常大的训练集是很普通的。 因此，在这些算法用于非常大的、现实世界中的数据库的挖掘时，算法的有效性 和可伸缩性成为值得关注的问题。 对于大型数据库构造决策树，研究者提出不同的解决方案。如：对连续属性 离散化，在每个结点对数据选样。但是这种方法仍然假定处理后的训练集可以放 在主存中。另外一种解决方案是：将样本划分成多个子集，使得每个子集可以放 在内存中；然后，由每个子集构造一棵决策树；最后，输出的分类法将出每个子 集得到的分类法组合在一起。尽管浚方法可以用于大数据集的分类，但是可能会 降低分类准确性。 针对算法的可伸缩性，最近提出了适用于大的训练数据集进行决策树归纳的 算法。主要包括s l i o 、s p r i n t 和r a i l l f o r e s t 判定树归纳框架。这些方法着重解 决当训练数据量无法全部放入内存时，如何高速准确地生成决策树。s l i o 和 s p r 矾t 都是用了预排序技术，同时定义了新的数据结构，以利于决策树的构造。 s l i q 算法 3 1 】首先采用预排序技术，对非常大而不能放入内存的驻留磁盘的 数据集进行排序。同时s l i q 使用了若干个驻留磁盘的属性表和单一的驻留内存 第二章分类 的类表。类表的第n 项存放第n 条记录的类标号，所以类表的大小随训练集中元 组数目成比例增长。每个属性则对应一个属性表，由记录标志号建立索引。每个 元组由一个从每个属性表的一个表目到类表的一个表目的链接表示，而类表的每 一个表目都链接到它在决策树中对应的叶子节点。类表在决策树构造和剪枝过程 中需要频繁访问，因此应该驻留内存。当类表不能放在内存时，算法性能会急剧 下降。 s p r i n t 算法旧也需要使用预排序技术，它利用属性表存放类和记录标志符 信息。当节点分裂时，属性表被相应划分。s p r d 盯消除了所有内存限制，但仍 然需要使用正比于训练集的散列树。随着训练集的增长，这可能使代价变得昂贵。 s p r i n t 的设计易于并行化，这进一步增强了算法的可伸缩性。 r 啦! f o r e s t 框架【3 ，l 是用于可伸缩的决策树归纳的框架，它采用a v c 集 ( a t m b u t e 一u e c l 船sl a b d ，属性一值和类标号) 指示数据每个属性类分布，能 够使生成的决策树的质量仅取决于具体的决策树算法，而与本框架无关。它旨在 提高决策树算法的伸缩性，陔框架可运用于大多数决策树算法( 例如s p 硎【n t 和 s l i q ) ，使算法获得的结果与全部的数据放置于内存所得到的结果一致，但是在 运行时可以使用较少的内存。 决策树算法因为具有结果容易被人理解、分类模式易于转化成分类规则、输 入参数少、能处理多种类型数据( 连续值和离散值) 、能够设计出具有良好伸缩 性的算法等优点，因此在数据挖掘和机器学习等领域具有广泛的应用。 决策树归纳算法也可能面临一些问题，主要是碎片、重复和复制：碎片是指 通过重复划分数据集可能导致一些叶子包含的样本数目太少而失去统计意义。这 些叶子对应的是问题空间中不具有一般意义的规则或是噪音数据引起的过适应。 重复是一个属性沿树的一个给定分枝重复测试。复制是复制了决策树中已经存在 的子树。这三个问题不但使决策树变得更庞大，同时影响决策树的分类准确度。 因此，为了防止过分适应训练数据集、构造具有更高分类准确度的决策树，需要 采用一些应对策略，如剪枝、属性构造等。 2 2 2 贝叶斯方法 对于分类问题，有些情况下，输入特征向量唯一对应着一个类别，这种问题 称为确定性的分类问题；而更多的情况是，来自于不同类别的样本在外观特征是 一8 一 第一二章分类 具有极大的相似性的，我们必须为它选择一个类别。贝叶斯方法能够很好地处理 这类不确定性问题，其特点是以概率表示所有形式的不确定性，学习或其他形式 的推理都用概率规则来实现。贝叶斯学习的结果表示为随机变量的概率分布，其 解释为我们对不同可能性的信任程度。 基于贝叶斯的分类过程可以这样描述：假定有足个类c ，白c k ，给定未 知数据样本z 可以用一个维向量描述为j = 缸l ，娩靠 ，分类器将预测未知 样本工属于在各属性取值为工条件下的后验概率最高的类。即选择能够使p ( c f l 最大化的c ；作为未知样本所属的类 p ( a z ) p ( g i j ) ，1 ，k ，f 依据贝叶斯定理尸( gl x ) = ! 竺掣 其中，p ( 西对于所有的类都是常数，只需p 佣c i ) p ( c f ) 最大，而如果类的先 验概率未知，通常假定这些类是等概率的，即p 刊= 尸r j 列= = j d r c p 。类的先验 概率也可阻用尸( c p = 侧“习，其中| s i | 是训练集中c f 类的样本数，i s i 是训练集的样本 总数。因此，如何获得p f 硼c 砂成为基于贝叶斯的分类算法的关键问题。 朴素贝叶斯分类算法( n a 如eb a y e s i a n ，n b ) 做了一个简单的假定：对于给定 的c f 类，所有属性是相互独立的。在属性值相互条件独立的前提下，尸( 圈c f ) 的 计算可以简化为：p ( 工jc f ) = 兀p ( 工，lc j ) 。概率坼“q ，p 阢i q 一，p 阢i 咧 j = l 可以通过训练集估算。 朴素贝叶斯分类法的假设是为了简化计算，但是这种假设在现实世界中不是 总成立的，因为各个属性之间总存在着或多或少地相互依赖。贝叶斯信念网络 ( b a y e s i a l lb e l i e f n e 押o r k s ) 说明联合条件概率分布，它允许在变量的子集间定义 类条件独立性。还能够表示属性子集问的依赖。它提供一种因果关系的图形，可 以在其上进行学习。 贝叶斯网络的知识表示为判别函数，与数据挖掘中的其他知识表示的方法如 规则表示、决策树、人工神经网络等相比，贝叶斯网络在知识表示方面具有以下 优点：贝叶斯网络能够很方便地处理不完全数据。贝叶斯网络能够学习变量间的 因果关系。贝叶斯方法与其他模型相结合，通常可以有效的避免了数据的过分拟 第二章分类 a 2 2 3 近邻学习方法( a r e s t i g h b o r ) 最近邻分类是基于类比的学习。训练样本用n 维数值属性描述，每个样本代 表n 维空间的一个点。这样，所有的训练样本都存放在n 维模式空间中。给定一 个未知样本，k 近邻分类法搜索模式空间，找出最接近未知样本的k 个训练样 本。这k 个训练样本是未知样本的k 个“近邻”。“临近性”有不同的定义方式， 最简单的就是欧几罩德的距离定义，即根据两个点之间的距离来确定二者的临近 性。未知样本被分配到k 个最临近者中最公共的类，如果这些点属于不同的类， 则可以通过某种判断策略( 如多数表决方式) 来确定该未知样本的最终归属。 近邻分类是基于要求的或懒散的学习法，即它存放所有的训练样本，并且直 到新的( 未标记的) 样本需要分类时才建立分类。而急切学习法( 如决策树归纳 或后向传播) 则在接受新的样本之前构造一个一般模型。懒散学习法的所有计算 都推迟到分类预测时进行，因此如果训练集很大，可能的临近者数量也很大，懒 散的学习法可能导致很高的计算开销，使分类过程变得缓慢。 2 2 4 神经网络分类 神经网络f 州最早是出心理学家和神经生物学家提出的，旨在寻求开发和测 试神经的计算模拟。神经网络是一组相互连接的输入输出单元，每个连接都与 一个权值相连。在学习阶段，通过调整神经网络的权，使网络能够正确预测输入 样本的类标号来学习。 神经网络需要很长的训练时问，而且需要大量的参数，这些参数主要靠经验 确定，如网络拓扑或结构。人们很难解释蕴涵在学习权之中的符号的含义，因此 神经网络很难被理解和解释，神经网络的行为也像一个“黑盒子”。 神经网络也有一些其他算法所不具备的优点，如对噪声数据的高承受能力， 以及它对未经训练的数据分类模式的优秀表现。由于最近提出一些从训练过的神 经网络提取规则的算法。这些因素推动了神经网络在数据挖掘分类方面的应用。 2 2 5 粗糙集方法 现实生活中存在着许多不能简单地用真、假值来表示的含糊现象，如何表示 1 0 一 第二章分类 和处理这些现象就成为一个研究领域。 1 9 6 5 年z a d c i l 提出了模糊集，但遗憾的是模糊集是不可计算的，即没有给 出数学公式描述这一含糊概念。直至2 0 世纪8 0 年代，波兰的p a _ w l a k 提出了粗 糙集( r o u 曲s e t ) 。粗糙集理论可以用于分类，发现不准确数据或者噪声数据内 在的结构联系，该理论基于给定训练数据内部的等价类的建立。形成等价类的所 有数据样本是不加区分的，即对于描述数据的属性，这些样本是等价的。给定现 实世界数据，通常有些类不能被可用的属性区分。粗糙集可以用来近似或“粗略 地”定义这种类。给定类c 的粗糙集定义有两个集合近似：c 的下近似和c 的 上近似。c 的下近似有一些这样的样本组成，根据关于属性的知识，它们毫无疑 问属于c 。c 的上近似由所有这样的样本组成，根据关于属性的知识，它们不可 能被认为不属于c 。 粗糙集方法的知识表示是产生式规则。例如，给定一个顾客信用信息的数据 库，可以学习分类规则，根据他们的信誉度优良或相当好来识别顾客。这样的规 则可以用来为以后的数据样本分类，也能对数据库的内容提供更好的理解。 粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据的信 息，比如统计学中的概率分布、d e m p s t e 卜s h a f e r 理论中的基本概率赋值，或模糊 集理论中的隶属度或概率值。当然了，该理论也不是万能的，对建模而言，尽管 粗糙集论对知识不完全的处理是有效的，但是，由于这个理论没有包含处理不精 确或不确定原始数据的机制。因此，单纯地使用这个理论不一定能有效地描述不 精确或不准确的实际问题，这就意味着需要其他方法的补充( 如与证据理论和模 糊集理论的结合) 。 2 2 6 源于关联规则的分类 关联规则【”，3 6 1 挖掘是数据挖掘研究的一个重要的、高度活跃的领域。最近， 数据挖掘技术业已将关联规则挖掘用于分类问题，我们将依次讨论c b a 、c m a r 和c p a r 算法。 基于关联规则的分类( c l a s s i f i c a t i o nb a s e do na s s o c i a t i o n ，c b a ) 算法采用和 a d r i o r i s 算法类似的候选项产生测试的方法挖掘所有满足最小支持度和最小置信 度闽值的规则，然后使用数据覆盖的概念来选择一个规则集来建立分类器。c b a 使用形如j ，_ y 的关联规则，其中z 是一个属性值的集合而y 是类标号这样的 1 1 第二章分类 规则被称作类规则( c l a 船a s c i 撕o nr u l 锱，c a r s ) 。由于产生的c a j 塔总数很大， 所以c b a 采用启发式的剪枝策略，使用一个可以覆盖所有元组的最有效的规则 集来构造分类器。在预测未知元组的时，c b a 在规则集中从最有效规则开始的 按有效性顺序搜索分类规则，并用第一个匹配的规则预测未知元组的类标号。 c b a 在u c i 机器学习库上的平均分类准确性比c 4 5 高，并且分类器的构造具有 线性可伸缩性。 c m a r 算法( c l a s s 语c a t i o nb a s e do nm 1 l l t i p l ea s s o c i a t i o nr u l e s ，c m a r ) 扩 展了f p 骶e ，在每个节点上添加了类信息，并使用f p g r o w l 算法产生完整的 关联规则集。并把这些规则存储在一个称作压缩规则树( c o m p r e s s e dr u l e 仃， c r 仃e e l 的数据结构上，剪除置信度低的规则并依据关联分析和数据覆盖做进一 步剪枝。预测未知元组的类标号时，和c b a 仅使用一条规则做判断的方法不同， c m a r 使用所有匹配的规则共同预测的预测未知元组所属的类。为了解决不同 规则预测的类标号不同而造成的冲突，c m a r 为每一个关联规则给定一个权值。 u c i 机器学习库测试表明，c m a r 算法的分类准确度优于c 4 5 和c b a ，并且 c m a r 比c b a 使用更少的内存具有更好的可伸缩性。 c p a r 算、法f 3 8 1 是基于预测规则的分类算法( c l a s s m c a t i o nb 船e do np r e d i c t i v e a s s o c i a t i o nr u l e s ，c p a r ) ，它使用预测规则挖掘算法( p r e d i c t i v em l em i m n g ，p r m ) 产生预测规则。p r m 算法继承了f o l l 算法的基本思想，c p a r 采用贪婪算法 从训练集直接产生预测规则，而不象传统的基于关联规则的分类算法那样需要产 生大量候选规则。但是和传统的基于规则的分类算法相比，c p a r 产生并测试更 多的规则。这是因为p r m 和f o l l 不同，它在发现一个实例被规则覆盖之后并 不删除它，而是降低它的权重。因此，p r m 算法产生更多规则并且每个实例通 常被多个规则覆盖。并且不是仅仅选用最好的一条规则而是选择所有接近最好的 规则的策略可以避免丢失重要的规则。c 队r 在预测过程中用预期准确度来度量 每一个规则的贡献，使用最好的五个规则共同决定未知样本的所属类别。测试 结果显示，c 队r 取得了更好的分类精度和速度。 2 2 7 基于e p 的分类算法 1 9 9 9 年，d o n g 和l i 提出了一种新的知识模式，即显露模式【3 9 1 4 0 】( e m e r