（计算机软件与理论专业论文）基于eep的数据流分类算法研究.pdf

摘要 随着信息技术的快速发展和信息搜集能力的日益提高，近些年产生了一种新 型的具有快速、海量、变化等特性的数据，即“数据流”。这些数据流或以静态 的形式存储在企业的物理存储器上，或是不被存储而瞬时出现的动态数据。 分类是数据挖掘中的一个重要问题，也是一种重要的数据分析形式，在传统 静态数据环境中，数据分类已经有了比较充分的研究，但是面对具有快速、海量、 变化及线性访问等特性的数据流，数据分类面临着新的挑战。通过汇总和分析， 发现当前在数据流环境中，已经有文献介绍相关的分类算法研究，但是，并没有 基于e e p 分类的相关研究。而e e p 具有良好的区分能力，并且基于e e p 的分类 算法可以与其他算法相媲美，同时基于e e p 的分类方法已经成功地应用于d n a 分析、文本自动分类等领域。 鉴于此，本文对数据流环境下，基于e e p 的分类算法进行了深入的研究。提 出种基于e e p 的数据流分类算法d s c e e p 。本文的主要工作是：在总结数据流 的特性和分析基于e e p 传统分类算法的算法思想的基础上，将基本窗口和滑动窗 r _ ：i 的概念与e e p 分类算法有机地结合以适应数据流的特性并解决概念漂移的问 题；其次在分类器构造的过程中，提出了多分类器的“三层构造模型”，即：e e p 的挖掘和加权、基分类器的构建、多分类器的组合；最后，在对未知样本分类的 过程中，结合数据流挖掘分析多考虑最近最新数据的特点，对不同的基分类器赋 予不同的权值，并提出了多分类器“董事会股权投票”策略，从而提高分类的准 确率。 经过实验对比和性能分析可以看出，本文提出的d s c e e p 算法能较好地适 应数据流的概念漂移，且具有较好的分类准确率，足以与以c 4 5 为基分类器的 集成多分类器算法相媲美。 关键字：数据挖掘，分类，数据流，显露模式( e p ) a b s t r a c t w i 也f h s td e v e l o p m e n to f 也ei n f o r m a 垃o nt e 6 h n o l o g y8 n dg r e a ti m p m v e m e n to f i n f 0 肌a t i o nc 0 1 1 e c t i n ga b i l i t y ，an e wk i n do f d a t ah a sb e e ng c n 啪t e di nm a l l y a p p l i c a t i o n sr c c e l l t i y ，n 锄e l y d a t as 仃e 锄”，w i mc h a r a d e r i s t i c so fn e w l yf a s t ，l a r g e v 0 1 u m e ，t i m e v a r y i n g ，c t c t h e s ed a t ai ss t o r e di nd i s k so fe 1 1 t e r p r i s e si nt h ef o h no f s t a t i cd a t ao r 印p e a r si n 也ef 矗mo f t i m e c h a n 西n gd a t a c l a s s i f i c a t i o ni so r l co fm em o s ti m p o r t 觚tp r o b l c l n si nd a t am i n i n ga n da l s oa k i n do fi m p o n a n td a t aa n a l 河sf o n l l f o rm et r a d i 廿o n a ls t “c a l l ys t o r e dd a t a ，m e c l a s s i f i c a t i o na l g o r i m m sh a v ea l r e a d yb e e l le x t c n s i v e l yr e s e a r c h e d ，b u ti nd a t as 乜e a m e n v i r o n m 锄t ，m o s ea i g o f i m m sa r ec i l c 0 _ l l i l t c r e dw i mm a n yn e wc h a l l e n g e s t l e r e h a v e b e e ns o m ed a t as t r e a md a s s i f i c a t i o na l g o r i t h m sp r o p o s e di nan u m b e ro f p a p e r s ， b u tn o t 锄yr e l a t e dr e s e a r c h e sb a s e do e e p ( e s s e l l t i a ie m e r g j n gp a t t e m s ) e e p sh a v e g o o dd i f 挹r e n t i a d o na b i l i t y 柚de e p - b a s e da l g o m h m sp e r f o 肌c o m p a r a b l yw i lo t l l e r t y p e so fd a s s i f i c a t i o na l g o r i t h m s m e a n w h i l e ，e e p - b a s e da l g o r i t h i n sh a v e b e c n a p p l i e d i nm a n yd o m a i n ss u c c e s s 缸n y ，s u c ha sd n aa n a l ”i s ，a u t o m a t i ct e x t c a t e g o “z a t i o n ，e t c c o n s i d 甜n gw h a tm e i l t i o n e da b o v e ，w ec 枷e do u tt h o r o u 曲r e s e a r c hi n e e p - b a s 司“g o r i t h n l si nd a t as h a mc o n t e x ta n dp r o p 0 3 e dac l a s s 俯c a t i o na l g 耐t h i n d s c e e p ( d a 诅s t r e 锄c 1 a s s i f i c a t i o nb ye e p ) t h em a i nc o n t c n t so ft h ep 印e ra r e i l l u s t r a t e da sf o l l o w s f i r s t ly s 咖嘶z i n gt h ec h a r a c t 嘶s t i c so fd a t as t r e 锄a i l d a i l a l y z i n ge e p 小a s e da l g o r i 山n ，w ec o m b i i l c dt h ec o n c c p t so fb a s i cw i n d o w sa n d s l i d i n gw m d o w s “m 也ee e p - b a s c dd a s s i f i c a t i o na l g o r i m mt om a l 【eo u ra l g o r i t h m a p p m 砸a t ef o rd a t as 仃e 锄a n ds o i v et h ep m b l c mo fc o n c e p td r i f i i n g s e c o n d ly w e p r o p o s e dam o d e lc a l l e d “m r e el a y e rs 仃1 l c t l l r em o d e l s ”t oc o n s t r u c tm u l t i c l a s s 试e r s n 锄e l y ，m n i n ge e p sa n da d d i n gar e l e v a n tw e i g h tt oe a c he e p ，c o n s t f u c t i n gb a s e c l a s s i f i e ra n dc o m b i n i n gt h em u l t i p l ec l a s s i 矗e r s a t l a s t ，i nt h ep m c e s so fc l a s s i f 弘n g t h ec o m i n gt e s t i n ge x a m p l e s ，w ep a i dm u c hm o r ea t t e n t i o nt ot h el a t e s td a t ab l o c k s s o e a c hb a s ec l a s s 访e rw a sw e i 蛳e db a s e do ni t sa m “n gt i m e w ea l s o 协的d u c c da n e wv o t m gs 仃a t e g yn 锄e db y ”s h a r e _ b a s e db o a r d s v o t e ”t om i s ed a s s i f i c a t i o n a c c u r a c y a si ss h o w ni nt 1 1 ee x p 甜m e l l t s ，恤c l a s s i 丘c a t i o na l g o r i t md s c e e p p m p o s e d i nm i sp 印e ra d 印t sb e t t e ft o l e c o n c 印td r i f i i n go fd a t as t r e 锄a n dh a sah i 吐 a c c u r a c yc o m p a r a b l ew i t l lt 1 1 ee n s 锄b l em e m o db a s e do nc 4 5 k e y w o r d s ：d a t a m i n i n g ，c l a s s i f i c a t i o n ，d a t as 仃c 锄，e m e r g i n gp a t t e m s ( e p ) 郑重声明 本学位论文是在导师指导下独立撰写并完成的。除文中 已经注明引用的内容外，本论文不含任何其他个人或集体已 经发表或撰写过的作品或成果。学位论文没有剽窃、抄袭等 违反学术道德、学术规范的侵权行为，否则，本人愿意承担 由此产生的一切责任和法律后果。特此郑重声明。 学位论文作者( 签名) 祷宏杰 p 衫年，月上日 第一章引言 面对日趋激烈的市场竞争，人们需要从这些蕴含着丰富决策信息的数据中抽 取能帮助领导进行决策的知识。在需求的强烈驱动下，数据挖掘技术应运而生。 而近些年随着信息技术的快速发展和信息搜集能力的r 益提高，产生了一种新型 的具有快速、海量、变化等特性的数据，即“数据流”。这些海量的数据流或以 静态的形式存储在企业的物理存储器上，或是不被存储而瞬时出现的动态数据。 面对如此丰富的海量数据，传统的数据处理方法和能力已远远不能满足实际的需 求。 分类是数据挖掘中的一个重要问题，也是一种重要的数据分析形式。分类是 一种有指导的学习过程，可以用于从数据库中提取重要数据类的模型或预测未来 的数据趋势。在商业、金融、电讯、d n a 分析、科学研究等诸多领域具有广泛 的应用。统计学、机器学习、神经网络等领域的研究者对分类问题进行了大量的 研究【2 l ，提出了一系列的分类算法。 本文的题目是“基于e e p 的数据流分类算法研究”。其研究的内容属于数据 挖掘中的分类问题，研究的对象是数据流数据。 1 1 数据挖掘 数据挖掘就是从大量的数据( 大型数据库和数据仓库) 中提取和挖掘知识的 过程，这些知识是人们感兴趣的、隐含的、事先未知的和潜在有用的信息 3 】。 数据挖掘虽然只有十几年的历史，然而它出现之后被广泛应用于许多领域， 数据挖掘的研究蓬勃发展。商业、金融、电讯、d n a 分析、科学研究、医疗卫 生等应用领域都有大量数据挖掘技术成功的例子而且多数研究成果都能够迅速 的转化为实际应用。那么数据挖掘能够发现什么类型的知识模式呢? 数据挖掘发 现的知识模式一般可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数 据的一般特性，预测性挖掘任务可以在当前数据上进行推断，以进行预测。数据 挖掘的功能 4 以及发现知识模式包括以下几个类型： 概念，类描述( c l a s s c o n c e p td e s c r i p t i o n ) 关联分析( a s s o c i a t i o na n a l v s i s ) 分类( d 踮s i f i c a t i o n ) 预测( p r e d i c t i o n ) 聚类( c l u s t c r ) 孤立点分析( o u i c ra n a l v s i s ) 演变分析( e v o l 砸o na i l a l v s i s ) 每项数据挖掘功能可由多种不同的算法实现。分析研究和设计数据挖掘算法 是数据挖掘研究的一个重要课题。数据挖掘算法的设计涉及多学科技术，包括数 据库技术、统计学、机器学习、高性能计算、模式识别、神经网络、粗糙集理论 等。根据数据挖掘的数据类型以及涉及的应用领域，数据挖掘技术又可与空间数 据分析、信息检索、图像分析、信号处理、计算机图形学、w w w 、经济、商业、 生物信息学以及心理学领域技术相关。目前数据挖掘技术已经成功的运用于这些 领域，它既有多层次的研究价值又有很高的应用价值。 1 2 分类 分类是数据挖掘中的一个重要问题，也是一种重要的数据分析形式。分类是 一种有指导的学习过程，可以用于从数据库中提取重要数据类的模型或预测未来 的数据趋势。在商业、金融、电讯、d n a 分析、科学研究等诸多领域具有广泛 的应用。统计学、机器学习、神经网络等领域的研究者对分类问题进行了大量的 研究，提出了一系列的分类算法。 分类问题可以描述为：数据是张标准关系表，它包含n 个记录，这些记 录通常称作元组( t u p l e s ) 、实例( i n s t a l l c e ) 或样本( e x a m p l e ) 。每一个实例用固 定数目的度量标准描述，这种度量标准称作属性( a t 埘b u t e ) 。每一个属性都有一 个合法的取值范围，称作该属性的域( d o m a i n ) 。如果属性域是实数域，那么则 称该属性为数值属性( n u m 耐c a la t 埘b u t e ) 或连续属性( c o n t i n u o l l sa t 砸b u t e ) 。如 果属性域是有限的，那么则称该属性为分类属性( c a i e g o r i c a la t 研b u t e ) 或离散属 性( d i s c r e t ea t 缸b u t e ) 。这些属性中有一个区别于其他属性的称作类标号( c l a s s l a b e l ) ，类标号指示元组所属的类。除了类标号之外的其他属性是预测未知样本 类型的依据，因此也称作预测属性( p r c d i c t o ra t t r i b u t e s ) 。 在分类研究中，数据集通常被分成训练集和测试集。训练集用来构造分类器， 测试集用来评估分类器的预测准确度。因为学习算法可能对数据的过分特化，所 以使用训练数据构造分类模型，然后用同样的数据集评估分类模型可能导致过于 乐观的估计。因此，通常采用测试集来评估分类模型。在分类研究中，通常采用 u c i 机器学习库f 5 ( u c im a c h i n el e 锄i n gr 印o s i t o r y ) 中的数据集评估不同的分 类模型。这些数据集来自广泛的应用领域，并且不同数据集的规模、目标类的个 数和属性个数变化很大，能够比较全面的反映算法的分类性能。 分类过程可以描述为如下两个步骤： 第一步，模型构建阶段，描述预定的数据类或概念集。训练阶段的目的是建 立分类器，即从训练数据集中获取可以进一步指导未知数据分类的专家知识。不 同的分类模型可能用不同的形式描述用于指导分类的知识，如分类规则、决策树 或数学公式等。这些分类模型以不同的形式描述了某个类区别其他类的特征概念 集。从另一个角度来看，也可以认为分类模型是以某种特定的形式描述了训练集 的数据分布特征。如果训练集能够代表整体数据分布特征，那么由训练集获得的 特征概念集就可以用来指导对未知数据的预测。 第二步，使用模型进行分类。在使用分类模型对未知类标号的实例或对象分 类之前，首先要使用测试集评估分类模型的分类准确率。如果分类准确率是可以 接受的，那么我们才可以真正把该模型用于指导未知元组的分类。 1 3 研究背景 随着信息技术的快速发展和信息搜集能力的日益提高，产生了海量的数据。 这些海量的数据或以静态的形式存储在企业的物理存储器上，或是不被存储而瞬 时出现的动态数据。面对如此丰富的海量数据，传统的数据处理方法和能力已远 远不能满足实际的需求。基于数据流的相关研究目前己具备了较好的理论基础。 如与查询优化相关的：抽样技术【6 】、直方图技术7 1 、分位数技术8 1 、小波分析技 术 9 】、草图技术等；与数据挖掘相关的：决策树技术f 1 1 】、聚类技术、频繁模 式挖掘技术等； 一些相关的理论：模式增长理硷 1 4 】、边界理论旧等。基于数 据流的数据挖掘必须得到这些技术的有效支持，同时结合数据流和数据挖掘任务 本身的特性，从而得到基于数据流的数据挖掘任务解决方案。 基于数据流的分类算法研究是当前数据挖掘领域的一个热点，对于我们来说 是一个好的研究机遇，但是同时又是一个挑战。目前，在数据流环境中，已经有 文献介绍相关的分类算法研究，但是，并没有基于e e p 分类的相关研究。而e e p 具有良好的区分能力，并且基于e e p 的分类算法可以与其他算法相媲美，同时基 于e p s 的分类方法已经成功地应用于d n a 分析、文本自动分类等领域。鉴于此， 我们对数据流环境下，基于e e p 的分类算法进行了深入的研究。 1 4 论文内容及结构 本文主要的研究内容：首先在总结数据流的特性和分析基于e e p 传统分类算 法的算法思想的基础上，将基本窗口和滑动窗口的概念与e e p 分类算法有机的结 合以适应数据流的特性并解决概念漂移的问题；其次在分类器构造的过程中，提 出了多分类器的“三层构造模型”，即：e e p 的挖掘和加权、基分类器的构建、 多分类器的组合；最后，在对未知样本分类的过程中，结合数据流挖掘分析多考 虑最近最新数据的特点，对不同的基分类器赋予不同的权值，并提出了多分类器 “董事会股权投票”策略，从而提高分类的准确率。 论文的组织结构如下： 第一章为本文的引言部分。简单介绍了数据挖掘的相关知识，并论述了本文 的研究背景、研究内容及论文的组织结构。 第二章为数据流相关知识的介绍。主要介绍了数据流的概念、特点；数据流 的一个特征概念漂移：处理数据流的常用技术一一滑动窗口技术；最后介绍 了当前数据流分类的研究动态。 第三章为传统分类算法的分析。主要分析了现有的传统分类方法，并以数据 流的角度比较算法的优缺点，最后结合自己研究的特点指出选用基于e e p 的分类 方法作为本文分类算法的核心。 第四章为基于e e p 的数据流分类算法d s c e e p ，这是本文的主要研究内容。 本章分为两个部分：第一部分是相关知识和概念定义。主要介绍了e p 挖掘问题 的相关知识和几个概念的定义。第二部分重点介绍了d s c e e p 算法。主要包括 基本思想、基分类器的构造、多分类器的产生与更新和多分类器分类等内容。 第五章为d s c e e p 算法的实验结果及性能分析。 最后是本文工作总结、致谢和参考文献。 第二章数据流相关知识介绍 在只益增多的信息处理应用中，信息呈现形式较多的不是静态方式，而是动 态连续“流”的形式，称之为数据流( d a t as t r e 锄) 。所谓数据流【1 6 】是指一系列 连续的数据序列，这个序列中的数据按照固定的次序快速到达，而且只能被读取 一次或几次。基于数据流的数据挖掘有着广泛的应用，如网络路由管理以及网络 的入侵检测、电信业中的欺诈分析、金融检测及金融仲裁、商务点击流分析及个 性化分析等。 本章介绍数据流相关知识，主要包括：数据流的特征、数据流分析算法的要 求、概念漂移的问题、滑动窗口技术以及当前数据流分类算法的动态。 2 1 数据流的特征 数据流是只是传统数据的一种特殊形式，但是它具有自己独特的不同于传统 数据的一些特征1 1 7 】： 连续：数据流元素以连续的形式到达。 有序：数据流数据是一种天然的有序序列，在时问维上存在次序关系。 变化：数据流中的数据分布是持续变化的，而不是保持固定的数据分布 不变，从而采用统一的模式进行处理是不适合的。 快速：数据流的数据快速到达，因此必须要求数据流挖掘算法能够实时 响应，与数据流元素到达的速率相兼容。 海量：数据流数据持续到达，其数量可认为是海量的。 2 2 数据流算法满足的要求 基于数据流的上述特征，在对数据流进行挖掘分析时，应该基本满足下面的 要求： 实时处理，实时响应：由于数据流数据快速到达，因此对数据流分析处 理必须能够快速处理，且能够实时响应。 线性扫描，不允许随即访问：由于数据流快速到达，所以对数据流进行 5 访问时不能采用传统的多边扫描数据访问方法，要求必须利用线性扫描 方法进行处理。 适应数据的概念漂移发生，要求能够捕获这些变化：数据流中的数据是 持续变化的，因此对数据流的处理在满足实时性要求的同时，也必须能 够捕获这些数据的变化。 存储概要信息：由于数据流数据的海量特性，对数据流的处理一般是不 存储的。但是，在迸行某些分析处理时，必须考虑历史数据的特性，因 此必须存储历史数据的一些概要的信息。 2 3 数据流的一个显著特征概念漂移 数据流的一个显著特征就是其数据分布随着时间而不断发生变化，这类不断 变化的现象就称之为概念漂移【培】。原来绝大部分数据挖掘算法都假设所使用的数 据是服从一种固定的分布，但事实上几乎所有用来挖掘的数据都违背了这个假 设，这些数据都是经过长年累月的采集而来在这么长时f i i j 的采集过程中数据的分 布很可能已经发生变化。 目前解决概念漂移问题主要集中在两个方面： 首先是概念漂移的发现，也就是说发现概念漂移发生的时机。 在预测型问题中，假设已经建立起一个预测模型，然后使用这个模型对每一 个到达的样本进行分类和诊断。如果可以在一段时问之后知道样本的真实属性 ( 比如预测型的问题) ，就可以对模型的诊断结果进行验证。当收集到足够多的 样本之后，就可以通过对样本数据预测准确率的变化来发现是否发生了概念漂 移。如果检测到模型对刚刚收集到的训练数掘的平均预测准确率和模型以前的平 均预测准确率相比突然发生了明显的下降，那么就说明概念漂移发生了。 如果在短期时间内无法知道模型的分析结果( 比如描述型的问题) ，那么就 需要引入一个可靠性估计( r d i a b i l i t y e s t i m a l i o n ) 的方法，为每一次预测都分配 一个可信度的值。尽管每次的预测结果都不一定可以获得，但是可以根据可信度 的变化来判断是否发生了概念漂移。 然后是在检测到概念漂移发生之后，如何处理概念漂移。概念漂移的解决办 法基本 = 有两种：重建模型和模型的自适应。 一般说来，可以给出一个信赖度变化范围的阈值，用统计的方法来检查已经 建立起来的模型对当前训练样本的预测准确度。如果准确度的变化范围超过了那 个阈值，就标志着模型对当前的样本不再适用，即说明了发生了概念漂移。如果 检测到概念漂移已经发生，那么就可以重新设置模型的各种参数，或在必要时重 建模型来达到适应概念漂移的目的。该方法的优点在于动态检测模型对最新样本 的预测准确率的变化十分方便，而且代价较小，模型可以一直使用，直到他的准 确度不满足要求。在此期问，模型一直都可以认为是值得信赖的。它的缺点是如 果模型中的一些参数需要根据情况重新设嚣的话，那么在每次重建模型时就定 需要有一个机器学习和数据挖掘的专家来指导。 另一种方法，就是不必精确的探测出概念漂移和释放以及发生的程度，模型 可以自动的根据输入样本的变化来自动的调整自己。在概念漂移的情况下，最高 效的机器学习算法应该可以发现概念漂移的发生，可以迅速从概念漂移中恢复， 自动调整自己对概念的描述以适应新的概念，而且当新概念与旧概念相似时可以 最大程度的利用以前学习到的知识。该方法的优点在于，在整个过程中模型可以 自动地维护，动态地调整自身来适应新的概念，而不需要有人专门从事模型维护 的工作，更不需要专家的参与。模型在使用过程中随时都是最适应与当前概念的， 准确率更加稳定。 2 4 滑动窗口技术的介绍 由于数据流具有动态性、快速变化性、无限性等特点，它无法在全部地保存 下来以后再进行处理，这就要求在有限的存储空间的限制下，数据流处理只能是 部分地处理。但是在许多数据流的应用领域中，人们常常关心的是最近到达数据 的处理结果，因此，基于滑动窗口的数据流处理技术能够很好地实现关于最近到 达的数据流中数据相关处理工作。 数据流上的滑动窗口技术 1 9 】 2 0 】 2 1 】是指：在数据流上设定一个区域范围， 数据流的处理对象就是那些处于窗口内的数据内容。滑动窗口通常包含那些最近 到达的数据；当最新数据到来的时候，窗口将向前移动，将最旧的数据移动出窗 口。根据滑动窗口具体实现方法的差异，可将滑动窗口技术分为基于序列的滑动 窗口技术和基于时问的滑动窗口技术。基于序列的滑动窗口技术特点是：在大小 为w 的滑动窗口内保存的是最近到达的w 个数据。基于时间的滑动窗口技术特 点是：在大小为w 的滑动窗口内保存的是最近w 时间内到达的数据。数据流经 常与时间有着紧密联系，因此，基于时间的滑动窗口技术比较适合于数据流处理 过程。 2 5 当前数据流分类研究 近年来，经过许多研究者的辛勤努力，基于数据流的相关研究已具备了较好 的理论基础。如与查询优化相关的：抽样技术、直方图技术、分位数技术、小波 分析技术、草图技术等；与数据挖掘相关的：决策树技术、聚类技术、频繁模式 挖掘技术等；一些相关的理论：模式增长理论、边界理论等。在数据流分类方面， 研究者们已经提出了不同的分类方法。其中具有代表性的有四种：h o e 仃d i n g 树 算法【2 3 】、v f d t ( v 哪，f a s td e c i s i o nt r e e ) 2 4 】、c v f d t ( c o n c e p t a d 印t i n gv e r yf a s t d e c i s i o nt r e e ) 2 5 】和使用投票表决的多分类器加权集成方法c l a s s 诲e rc 1 1 s e m b l e 2 6 】。 ( 1 ) h o e f f d j n 2 t r e e 算法 h o e 衄i n gt r e e 算法是。种数据流上的决策树学习算法。它己被初步应用到 跟踪w c b 点击流并构建模型来预测哪些网站或主机经常被访问。该算法时间复 杂度是次线性的，并且能产生与传统的批处理方式下几乎一致的决策树。 h o e 嗣i n g t r e e 采用了一种思想：选择最佳分裂属性时，小样本数据常常足够使用。 该思想是基于统计理论h o e f f d i n g b o u n d ( a d d i t i v ec h e n l o f r b o l l l l d ) ：对范围r 内 的随机变量r 进行n 次独立观测，r 是n 次观测的平均值。其中r 是属性选择方 法，对于h o e 衄i n g 仃e e ，r 是信息增益( 对于概率，r 为1 ：对于信息增益，r 为1 0 9 c ，c 是类的个数) 。h o e 筋i n g b o u n d 理论保证r 的真实平均值至少为，一8 的 概率为1 - 6 ，6 由用户指定，由经验值确定。 。：，侄! 型盟 v2 九 ( 半) h o e 删i n gt r e e 算法使用上述理论保证了以高概率、使用小样本来选择节点上 的最优分裂属性。而所选取出的属性和使用无穷样本得到的结果一样。h o e 删i n g b o u n d 理论与概率分布无关。因为不可能知道信息增益的概率分布或采用的属性 选择方法，所以采用该理论是合适的。 使用h o e 筋i n g 订c e 有另外的两个特性。首先，不再多次扫描数据集。再者， 算法能够增量更新。因此，在新数据流入时，可以同时利用已有的模型做预测， 并且可以引入新来的数据作为训练集，不断调整模型从而提高模型的准确率。 h o e 删i n g 仃e e 算法有一些不足之处。例如，当两个属性的分裂质量几乎相同 时，算法花费大量时间做此计算。另外，存储空间利用率可以进一步优化。最后， 算法无法处理概念漂移。 ( 2 ) v f d t 和c v f d t v f d t ( v q f a s t d e c i s i o nt r e e ) 是对h o e 懿协g 树算法的改进算法，提高了 速度和存储利用率。主要在以下方面做了改进：当结点上累积一定数目的训练样 本时才计算增益函数g ；删除最不常用的叶子节点；丢弃无价值的分裂属性；改 进初始化方法。但是，仍然不能够处理数据流中的概念漂移。 处理概念漂移的常用方法是使用滑动窗口，它引入新的样本并且删除历史样 本。在滑动窗口内反复训练传统的分类器，当新样本到达时，插入窗口的头部， 同时剔除尾部数据，从而保证训练得到的分类模型始终反映当前的数据分布。但 是，这种方法对窗口大小敏感。当窗口太大时，模型不能准确反映概念漂移：窗 f 太小时，没有足够的数据用于构建准确的模型。再者，不停地构建分类器模型 的代价相当高。 为了解决数据流中的概念漂移，h u l t 朗等人对v f d t 进行了扩展，提出了 c v f d t 算法。c v f d t 仍然使用滑动窗口的方法，但是，它不再每次都在暂存区 构建新模型。c v f d t 通过增加( 减少) 与新( 旧) 样本相关的计数来更新各结 点上的统计信息。因此，当概念漂移发生时，生成可替换子树，当可替换子树比 历史子树的分类准确率更高时，替换历史子树。 实验表明，c v f d t 比v f d t 拥有更高的准确率，c v f d t 中树的大小比v f d t 的要小。 ( 3 ) 分类器集成算法( c l a s s 嫡e re n s e m b i e ) 2 0 0 3 年，w a n g 2 6 等人提出了集成分类器的方法，它使用多个分类器来代替 单个分类器，对不同时间段构造不同的分类器，利用最近的数据决定每个分类器 的权重，然后用多个分类器的加权和进行预测。实验表明与单分类器相比，该方 法具有更高的分类准确率。 2 6 小结 本章首先简单的介绍了数据流的特征和数据流挖掘算法需要满足的条件；接 下来，重点介绍了概念漂移问题的相关研究和目前数据流挖掘常用的一种技术 滑动窗口；最后，简要介绍了当前数据流分类方面的研究工作。从而说明本 文所提出的分类算法有一定应用需求，同时说明本文算法必须满足的要求，便于 更加清楚地介绍。 第三章传统分类算法的分析 数据挖掘领域中，己经有许多静态数据上的分类方法，如决策树、贝叶斯分 类、神经网络、支持向量机等。分类包含两个阶段：学习或模型构建( 基于包含 类标号的训练数据集来构建模型) 、分类过程或模型使用( 用于预测新来数据的 类标号) 。而后者有助于流数据分类，因为当新样本数据到达时将被立即分类。 如何将传统的分类方法应用于数据流成为一个值得讨论的问题。在传统的框 架下，训练数据以相对静态的形式存储予数据库，而且很多分类方法均是多次扫 描训练数据集。显然，分类模型构建的过程是离线进行的批处理过程，然而对于 数据流，没有离线阶段，这是因为数据流入速度快，使得存储所有数据和多次扫 描并不可行。所以，必须对传统分类算法进行分析。 本章主要介绍了基于判定树的分类、贝叶斯分类、源于关联规则的分类、基 于e p 的分类算法、k 最临近分类、神经网络分类等传统分类算法的思想、优缺 点和主要的实现算法，同时也比较了各个算法在u c i1 2 个数据集上的分类准确 率，从而为选择适当的分类算法作为基分类器的构造算法作好铺垫。 3 1 基于判定树的分类 判定树( d e c i s i o nt r c e ) 是一个类似于流程图的树结构，其中每个内部节点表 示在个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点代表类或 类分布。该算法在统计学、机器学习和数据挖掘领域都有广泛的应用。 判定树分类算法 2 7 以树形结构表示分类结果，树根节点代表整个数据集合空 间，每个分支节点是对一个属性的测试，该测试将数据集集合空间分割成两个或 多个块，而每个叶子节点代表一个类。由根节点到叶子节点的路径描述了各种分 类规则。它的基本算法思想是贪心算法，它以自顶向下递归的各个击破方式构造 判定树。主要是在树的每个节点上使用信息增益度量选择测试属性，选择具有最 高信息增益的属性作为当前节点的测试属性。 算法的基本策略： 树以代表训练样本的单个节点开始。 如果样本都在同一个类，则该节点成为树叶，并用该类标记。 否则，算法使用成为信息增义的给予上的度量作为启发信息，选择能够 最好地将样本分类的属性，该属性成为该节点的“测试”或“判定”属 性。 对测试属性的每个已知的值，创建一个分枝，并据此划分样本。 算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个 属性出现在一个节点上，就不必考虑该节点的任何后代上。 递归划分步骤仅当下列条件之一成立时停止： a 、给定节点的所有样本属于同一类； b 、没有剩余属性可以用来进一步划分样本。在此情况下，使用多 数表决。 c 、分支测试属性没有样本。 基于判定树的分类算法很多，比较有影响的有i d 3 、c 4 5 、c a r t 、s u o 、 s p r j n t 、b o a t 和c l o u d s 等算法和r a i n f o r e s t 框架。 传统的判定树算法的结果容易被人理解、分类模式易于转化成分类规则、输 入参数少、能处理多种类型数据( 连续值和离散值) 、能够设计出具有良好伸缩 性的算法。 同时，决策树归纳算法也可能面临一些问题，主要是碎片、重复和复制：碎 片是指通过重复划分数据集可能导致一些叶子包含的样本数目太少而失去统计 意义。这些叶子对应的是问题空间中不具有一般意义的规则或是噪音数据引起的 过适应。重复是一个属性沿树的一个给定分枝重复测试。复制是复制了决策树中 已经存在的子树。这三个问题不但使决策树变得更庞大，同时影响决策树的分类 准确度。因此，为了防止过分适应训l 练数据集、构造具有更高分类准确度的决策 树，需要采用一些应对策略，如剪枝、属性构造等。 前面2 5 中介绍到当前的v f d t 和c v f d t 算法，就是根据判定树思想提出 的一种h o e 彻i n gt r e e 算法，该算法时蒯复杂度是次线性的，并且能产生与传统 的批处理方式下几乎一致的判定树。且通过实验表明，浚算法在数据流分类问题 上有显著的效果。 3 2 贝叶斯分类 贝叶斯分类 2 8 1 是统计学分类方法，它基于贝叶斯定理，使用后验概率预测类 成员关系的可能性，如给定样本属于某一特定类的概率。 假定有足个类c l ，c 2 c k ，给定未知数据样本可以用一个维向量描述 为工= f x l ，x 2 ，x 。 ，分类器将预测未知样本肖属于在各属性取值为条件下的 后验概率最高的类。即选择能够使p ( c i 心) 最大化的c ，作为未知样本所属的类 p ( c fj z ) p ( g l z ) ，1 ，足，_ ，f 依辊唰叶撕常理p ( c fl x ) = ! 紫 依据贝叶斯定理 ，j 其中，j p ( x ) 对于所有的类都是常数，只需p ( 瑚c ，) 尸( c j ) 最大，而如 果类的先验概率未知，通常假定这些类是等概率的，即p ( c 1 ) 叩( c 2 ) = = 尸( c f ) 。类的先验概率也可以用p ( c f ) = | s f i 俩l ，其中酬是训练集中c f 类的样本 数，i s 是训练集的样本总数。因此，如何获得_ p ( 固c ，) 成为基于贝叶斯的分类 算法的关键问题。 贝叶斯分类基于贝叶斯定理，它主要有朴素贝叶斯分类和贝叶斯信念网络。 朴素贝叶斯分类算法( n 舐v e b a y e s i 肌，n b ) 做了一个简单的假定：对于给 定的c i 类，所有属性是相互独立的。在属性值相互条件独立的前提下，p ( 瑚c ，) p ( j c ) = 兀p ( _ lc j ) 的计算可以简化为： 州 。概率p ( x 1 i c ；) ，p ( x 2 l c i ) ， p ( x 。l c f ) 可以通过训练集估算。当条件独立性假设成立时，朴素贝叶斯分类是 最精确的，然而朴素贝叶斯分类算法的条件独立性假设在现实数据集上通常是不 成立的。 贝叶斯信念网络( b a y e s i a l l b d i e f n 。t w o r k ) 【2 川说明联合概率分布，允许在变 量的子集问定义类条件独立性，通过因果关系图来体现属性之间的依赖关系。它 主要由两部分构成：有向无环图和每个属性的条件概率表。它可以通过梯度下降 方法得到训练。分类过程返回类标号属性的概率分布。 在假设成立的前提f 分类速度快准确率高。并且，认为贝叶斯信念网络可以 在线性时间内完成数据的分析同时它还具备学习的呵能，从而适应数据流的数据 不断变化的特点。 3 3 源于关联规则的分类 关联规则 3 0 f 3 1 】挖掘是数据挖掘研究的一个重要的、高度活跃的领域。数据 挖掘技术业已将关联规则挖掘用于分类问题， 基于关联规则的分类( c l a s s i 矗c a t i o nb a s c do na s s o c i a t i o n ，c b a ) 算法采用 候选项产生测试的方法挖掘所有满足最小支持度和最小置信度阈值的规则，然后 使用数据覆盖的概念来选择一个规则集来建立分类器。c b a 使用形如x 一 v 的 关联规则，其中x 是一个属性值的集合而y 是类标号这样的规则被称作类规则 ( c l a s s a s s o c i a t i o n r u l c s c a r s ) 。由于产生的c a r s 总数很大，所以c b a 采用 启发式的剪枝策略，使用一个可以覆盖所有元组的最有效的规则集来构造分类 器。在预测未知元组的同时，c b a 在规则集中从最有效规则开始按有效性顺序 搜索分类规则，并用第一个匹配的规则预测未知元组的类标号。 c m a r 算法( c l a s s i f i c a t i o n b a s e do nm u l t i d l e a s s o c i a t i o nr u l e s ，c m a r ) 【3 2 1 扩展了f p t r e e ，在每个节点上添加了类信息，并使用f p g m w t h 算法产生完整 的关联规则集。并把这些规则存储在一个称作压缩规则树( c o m d r c s s e dr u l e 仃e e ， c rt r e e ) 的数据结构上，剪除置信度低的规则并依据关联分析和数据覆盖做进一 步剪枝。预测未知元组的类标号时，和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 算法是基于预测规则的分类算法( c l a s s m c a t i o nb a s 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 ) i 3 3 j ，它使用预测规则挖掘算法( p r e d i c t i v en 】1 em i n i n g p r m ) 产生预测规则。p r m 算法继承了f o l l 算法的基本思想，c p a r 采用贪 婪算法从训练集直接产生预测规则，而彳i 象传统的基于关联规则的分类算法那样 需要产生大量候选规则。但是和传统的基于舰则的分类算法相比，c p a r 产生并 测试更多的规则。这是因为p r m 和f o l l 不同，它在发现一个实例被规则覆盖 之后并不删除它，而是降低它的权重。因此，p r m 算法产生更多规则并且每个 4 实例通常被多个规则覆盖。并且不是仅仅选用最好的一条规则而是选择所有接近 最好的规则的策略可以避免丢失重要的规则。c p a r 在预测过程中用预期准确度 来度量每一个规则的贡献，使用最好的世个规则共同决定未知样本的所属类别。 测试结果显示，c p a r 取得了更好的分类精度和速度。 3 4 基于e p 的分类算法 基于显露模式( e m e 四n g p a t t e m ，e p ) 【3 4 】 3 5 1 的分类器和传统的分类算法不 同。传统的分类算法在作微观决策的时候仅考虑一个属性或一组属性，而基于 e p 的分类算法，通过聚合多个e p 在做决策时考虑了多组属性，能够捕获不同类 之间的差异和取值倾向，从而提高了分类的准确率。，所以说，e p 具有很好的区 分性能比较适合用来指导分类。 基于e p 的分类算法主要有两个过程，一、基分类器的构建：采用挖掘