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

郑州人学硕 学位论文 摘要 在信用卡欺诈监测、差异性营销、网络入侵检测和传感器网络等应用中，随 着时间的更迭而生成一种新型的具有连续、有序、变化、快速到达、海量等特征 的数据，即“数据流”，其数据量大且数据分布可能会发生变化( 即概念漂移) 。 如何从海量的数据中训练模型来有效地预测未来的数据趋势，正是数据流上的分 类算法所要解决的难点，同时也是一件非常有意义的工作。 分类是数据挖掘中的重要分支之一，在很多领域都具有广泛的应用。现在已 有许多成熟的分类方法，如决策树、贝叶斯网络、神经网络、支持向量机等，但 是在处理数据流时，仍然面临着新的挑战。近年来研究者们提出了几种数据流上 的分类方法：v f d t 和c v f d t 、v f d t c 、集成分类方法e n s e m b l ec l a s s i f i e r s 等。 集成多个分类器的方法通常可以提高分类准确率，特别是基分类器具有一定的差 异性时，它往往比单分类器的准确率高。w a n g 等人提出的集成方法以c 4 5 、 r i p p e r 、n a i v eb a y e s i a n 分类为基分类器，而采用其他类型的算法作为基分类 器仍需进一步研究。而e e p 具有良好的区分能力，并且基于e e p 的分类算法可以 与其他算法相媲美，同时基于e e p 的分类方法已经成功地应用于d n a 分析、文本 自动分类等领域。 基于以上考虑，本文提出一种基于e e p 的数据流分类器集成算法c e e p c e 。 本文的主要工作是：在总结数据流的特性和分析基于e e p 传统分类算法的算法思 想的基础上，将基本窗口和滑动窗口的概念与e e p 分类算法有机的结合以适应数 据流的特性并解决概念漂移的问题；其次在分类器构造的过程中，提出了加权集 成分类器的思想；最后，在未知样本分类的过程中，结合数据流挖掘分析多考虑 最近最新数据的特点，对不同的基分类器赋予不同的权值，提出一种“基于分类 误差的加权方法”来加权集成分类器，从而提高分类准确率。 实验对比和性能分析表明，本文提出的c e e p c e 算法能较好的适应数据流的 概念漂移，并且具有较好的分类准确率，足以与以c a 5 为基分类器的集成多分 类器方法相媲美。 关键字：数据流挖掘，数据流，分类，显露模式 垒些! ! 型 塑型叁兰堡! 兰竺丝塞 a b s t r a c t h u g ev o l u m e so fd a t as t r e a m sa r eg e n e r a t e da tu n p r e c e d e n t e dr a t e si n t h er a n g e o fa p p l i c a t i o n si n c l u d i n gc r e d i tc a r df r a u dp r o t e c t i o n ，t a r g e tm a r k e t i n g , n e t w o r k i n “1 l s i o nd e t e c t i o n n s o rn e t w o r k , e r e t h ed a t as t r e a m sa r ec o n t i n u o u s ，o r d e r e d ， c h a n g i n g , f a s ta n dh u g ea m o u n t ，m e a n w h i l e ，i t sd a t ad i s t r i b u t i o n i sl i k e l yt ob e c h a n g e d , n a m e l yc o n c e p td r i f t sw i l lh a p p e n h o wt ot r a i nt h ec l a s s i f i c a t i o nm o d e l t o p r e d i c tt h ec o m i n gd a t at r e n de f f e c t i v e l yi sj u s ta b o u t o n ed i f f i c u l t yi nt h er e s e a r c ho f d a t as t r e a mc l a s s i f i c a t i o na n di sa l s oa l li m p o r t a n tt a s k c l a s s i f i c a t i o ni s a l li m p o r t a n tt a s ki nt h ed a t am i n i n gd o m a i na n dt h e r ea r e c o m p r e h e n s i v ea p p l i c a t i o n s s u c ha sc r e d i tc a r df r a u dp r o t e c t i o n , t a r g e tm a r k e t i n g , n e t w o r ki n t r u s i o nd e t e c t i o n , e r e t h e r ee x i s ts o m ec l a s s i c a lc l a s s i f i c a t i o nm e t h o d s i n c l u d i n gd e c i s i o nt r e e ，b a y e s i a nn e t w o r k , n e u r a ln e t w o r ka n ds v m ，e t c ，w h e r e a s ， t h e ya r ef a c i n gn e wc h a l l e n g e ss u c ha st h eo v e r w h e l m i n g v o l u m eo ft h ed a t as t r e a m s a n dt h ec o n c e p td r i f t sw h e np r o c e s s i n gd a t as t r e a m s d u r i n gt h e s ey e a r ss e v e r a l s t r e a md a t ac l a s s i f i c a t i o na l g o r i t h m sa r ep r o p o s e db ys o m er e s e a r c h e r s ，s u c ha s v f d t & c v f d t , v f d t c a n de n s e m b l ec l a s s i f i e r s ，e t c w ec a r lu s u a l l yi m p r o v et h e c l a s s i f i c a t i o na c c u r a c yb yi n t e g r a t i n gs e v e r a lc l a s s i f i e r s ，e s p e c i a l l yw h e nh a v i n gs o m e d i v e r s i t yb e t w e e ne a c ht w ob a s ec l a s s i f i e r s e n s e m b l ec l a s s i f i c a t i o nm e t h o dp r o p o s e d b yw a n ge t a li sb a s e do nc 4 5 ，r i p p e r ，n a i v eb a y e s i a n , w h i l eu s i n go t h e r a l g o r i t h m sa sb a s ec l a s s i f i e r s i ss t i l lr e q u i r e dt os t u d y a sw ek n o w ，e e p ( e s s e n t i a l e m e r g i n gp a t t e r n s , e e p ) h a v e t h ef a v o r a b l ed i s t i n c t i v ef u n c t i o n a n de p - b a s e d a l g o r i t h mp e r f o r m sc o m p a r a b l yw i t h o t h e rt y p e so fc l 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 mh a sb e e na p p l i e di nm a n yd o m a i n ss u c c e s s f u l l y ， s u c ha sd n aa n a l y s i sa n dt e x ta u t o m a t i cc a t e g o r i z a t i o ne t c c o n s i d e r i n gt h ea b o v e m e n t i o n e df a c t o r s ，t h i sp a p e rp r o p o s e d a l la l g o r i t h m ， c a l l e dc l a s s i f i c a t i o nb ye e p b a s e dc l a s s i f i e r se n s e m b l e ( c e e p c e ) ，t oc l a s s i f yd a t a s t r e a m s t h em a i nr e s e a r c hc o n t e n t so ft h ep a p e ra r ci l l u s t r a t e da sf o l l o w s f i r s t l y ， b a s e do ns n m m a r i z i n gt h ec h a r a c t e r i s t i c so fd a t as t r e a ma n da n a l y z i n ge e p b a s e d a b s t r a d 郑州大学硕j ：学位论文 a l g o r i t h m ，w ec o m b i n e dt h ec o n c e p t so fb a s i cw i n d o w sa n ds l i d i n gw i n d o w sw i t ht h e e e p - 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 mt om a k eo u ra l g o r i t h ma p p r o p r i a t e f o r c h a r a c t e r i s t i c so fd a t as t r e a ma n ds o l v et h ep r o b l e mo fc o n c e p td r i f t s s e c o n d l y w e p r o p o s e dt h e i d e ao fw e i g h t i n gt h ec l a s s i f i e r se n s e m b l ei nt h ep r o c e s so ft h e c o n s t r u c t i n gd i f f e r e n td a s s i f i e r s f i n a l l y ，i nt h ep r o c e s so fc l a s s i f yt h ec o m i n gt e s t e 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 ，t h e r e f o r ee a c hb a s e c l a s s i f i e rw a sw e i g h t e db a s e do ni t sa r r i v i n gt i m e , i n t r o d u c e dan e ww e i g h t i n g s t r a t e g yn a m e db y ”t h ew e i g h t i n gm e t h o db a s e do nc l a s s i f i c a t i o na c c u r a c y ”t ow e i g h t d i f f e r e n tb a s ec l a s s i f i e r sa n de n s e m b l ea l ls e l e c t e dc l a s s i f i e r st or a i s ec l a s s i f i c a t i o n a c c u r a c y o u re x p e r i m e n t ss h o wt h a tc e e p c ea l g o r i t h mp r o p o s e di nt h ep a p e rc a n p r e f e r a b l ys o l v ec o n c e p td r i f t i n gi n d a t as t r e a m sa n do w n sah i g h e ra 洲a c yo f c l a s s i f i c a t i o nt h a nt h es i n 宙ec l a s s i f i e ra n dp e r f o r m sc o m p a r a b l yw i t ht h ee n s e m b l e m e t h o db a s e d0 1 1c 4 5 k e y w o r d s ：d a t as t r e a mm i n i n g , c l a s s i f i c a t i o n ，d a t as t r e a m ，e m e r g i n gp a t t e r n s ( e p ) 第章绪论郑州大学硕 学位论文 第一章绪论 面对日趋激烈的市场竞争，人们需要从这些蕴含着丰富决策信息的数据中抽 取能帮助领导进行决策的知识。在需求的强烈驱动下，数据挖掘【1 i 技术应运而生。 在信用卡欺诈监测、差异性营销、网络入侵检测和传感器网络等应用中，随着时 问的更迭而生成一种新型的具有连续、有序、变化、快速到达、海量等特征的数 据，即“数据流【2 l ”，其数据量大且数据分布可能会发生变化( 即概念漂移【3 j ) 。 如何从海量的数据中训练模型来有效地预测未来的数据趋势，正是数据流上的分 类算法所要解决的难点，同时也是一件非常有意义的工作。 分类是数据挖掘中的重要分支之一，也是一种重要的数据分析形式。分类是 一种有指导的学习过程，可以用于从数据库中提取重要数据类的模型或预测未来 的数据趋势。在商业、金融、电讯、d n a 分析、科学研究等诸多领域具有广泛 的应用。统计学、机器学习、神经网络等领域的研究者对分类问题进行了大量的 研究 4 1 ，提出了一系列的分类算法。 本文研究的内容属于数据挖掘中的分类问题，研究的对象是数据流数据。 1 1 数据挖掘 数据挖掘就是从大量的数据( 大型数据库和数据仓库) 中提取和挖掘知识的 过程，这些知识是人们感兴趣的、隐含的、事先未知的和潜在有用的信息吼 数据挖掘虽然只有十几年的历史，然而它出现之后被广泛应用于许多领域， 数据挖掘的研究蓬勃发展。商业、金融、电讯、d n a 分析、科学研究、医疗卫 生等应用领域都有大量数据挖掘技术成功的例子而且多数研究成果都能够迅速 的转化为实际应用。数据挖掘的功能一般可以分为两类：描述和预测。描述性挖 掘任务刻画数据库中数据的一般特性，预测性挖掘任务可以在当前数据上进行推 断，以进行预测。具体而言，数据挖掘的目标是完成如下功能： 概念，类描述( 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 y s i s ) 分类( c l a s 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 e r i n g ) 离群点分析( o u t l i e r a n a l y s i s ) 时序模式( r i m e s e r i e sp a t t e r n ) 偏差分析( d e v i a t i o n ) 每项数据挖掘功能可由多种不同的算法实现，分析研究和设计数据挖掘算法 是数据挖掘研究的一个重要课题。而数据挖掘是一个交叉学科领域，受多个学科 的影响，包括数据库系统、统计学、机器学习、可视化和信息科学。因此数据挖 掘算法的设计也涉及多学科技术，包括数据库技术、统计学、机器学习、高性能 计算、模式识别、神经网络、粗糙集理论等。根据数据挖掘的数据类型以及涉及 的应用领域，数据挖掘技术又可与空间数据分析、信息检索、图像分析、信号处 理、计算机图形学、w e b 技术、信息安全、经济、商业金融、生物信息学等领域 技术相关。目前数据挖掘技术已经成功的运用于这些领域，它既有多层次的研究 价值又有很高的应用价值。 1 2 分类问题 分类是数据挖掘中的重要分支之一，也是一种重要的数据分析形式。分类是 一种有指导的学习过程，可以用于从数据库中提取重要数据类的模型或预测未来 的数据趋势。在商业、金融、电讯、d n a 分析、科学研究等诸多领域具有广泛 的应用。统计学、机器学习、神经网络等领域的研究者对分类问题进行了大量的 研究，提出了一系列的分类算法。 分类问题可以描述为：数据集是一个标准关系表，它包含n 条记录，这些 记录通常称作元组( t u p l e s ) 、实例咖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 e a 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 ra t t r i b u t e s ) 。 2 第一章绪论郑州大学硕十学位论文 在分类研究中，数据集通常被分成训练集和测试集。训练集用来构造分类器， 测试集用来评估分类器的预测准确度。因为学习算法可能对数据过度拟合，所以 使用训练数据构造分类模型，然后用同样的数据集评估分类模型可能导致过于乐 观的估计。因此，通常采用测试集来评估分类模型。在分类研究中，通常采用 u c i 机器学习库【6 1 ( u c im a c h i n el e a r n i n gr e p o s i t o r y ) 中的数据集评估不同的分类 模型。这些数据集来源于广泛的应用领域，并且不同数据集的规模、目标类的个 数和属性个数变化很大，能够比较全面的反映算法的分类性能。 分类过程可以描述为两个步骤： 第一步，模型构建阶段。通过分析训练数据集，采用既定的算法，建立一个 模型，描述预定的数据类或概念集。分类模型也叫分类器，通常以分类规则、决 策树、模式或数学公式形式存在。训练阶段的目的是建立分类器，即从训练数据 集中获取可以进一步指导未知数据分类的专家知识。各种分类器以不同的形式描 述了某个类区别其他类的特征概念集。从另一个角度来看，也可以认为分类模型 是以某种特定的形式描述了训练集的数据分布特征。如果训练集能够代表整体数 据分布特征，那么由训练集获得的特征概念集就可以用来指导对未知数据的预 测。 第二步，使用模型进行分类。在使用分类模型对未知类标号的实例或对象分 类之前，首先要使用测试集评估分类模型的分类准确率。如果分类准确率达到既 定的目标，则该分类器才可以用于指导未知元组的分类。 1 3 研究背景 随着信息技术的快速发展和信息搜集能力的日益提高，产生了海量的数据。 这些海量的数据或以静态的形式存储在企业的物理存储器上，或是不被存储而瞬 时出现的动态数据。面对如此丰富的海量数据，传统的数据处理方法和能力已远 远不能满足实际的需求。基于数据流的相关研究目前已具备了较好的理论基础。 如与查询优化相关的：抽样技术川、直方图技术i 引、分位数技术f 们、小波分析技 术【1 0 l 、草图技术【1 1 l 等；与数据挖掘相关的：决策树技术捌、聚类技术【1 3 1 、频繁 模式挖掘技术【1 4 】等；一些相关的理论：模式增长理论【1 5 l 、边界理论1 1 6 l 等。基于 数据流的数据挖掘必须得到这些技术的有效支持，同时结合数据流和数据挖掘任 3 第一章绪论 郑州大学硕 学位论文 务本身的特性，从而得到基于数据流的数据挖掘任务解决方案。 分类是数据挖掘中的重要分支之一，在很多领域都具有广泛的应用，基于数 据流的分类算法研究是当前数据挖掘领域的一个热点。现在已有许多成熟的分类 方法，如决策树、贝叶斯网络、神经网络、支持向量机等，但是在处理数据流时， 仍然面临着新的挑战。近年来研究者们提出了几种数据流上的分类方法：v f d t 和c v f d t 坷、v f d t c 1 7 1 、集成分类方法e n s e m b l ec l a s s i f i e r s 1 8 】等。集成多个 分类器的方法通常可以提高分类准确率，特别是基分类器具有一定的差异性时， 它往往比单分类器的准确率高。w a n g 1 8 】等人提出的集成方法以c 4 5 、r i p p e r 、 n a i v eb a y e s i a n 分类为基分类器，而采用其他类型的算法作为基分类器仍需进 一步研究。而e e p 具有良好的区分能力，并且基于c e p 的分类算法可以与其他算 法相媲美，同时基于e p 的分类方法已经成功地应用于d n a 分析、文本自动分类 等领域。 基于以上考虑，我们对数据流环境下，基于e e p 的分类算法进行了深入的研 究。 1 4 论文结构及本文工作 本文主要的研究内容：首先在总结数据流的特性和分析基于e e p 传统分类算 法的算法思想的基础上，将基本窗口和滑动窗口的概念与e e p 分类算法有机的结 合以适应数据流的特性并解决概念漂移的问题；其次在分类器构造的过程中，提 出了加权集成分类器的思想；最后，在未知样本分类的过程中，结合数据流挖掘 分析多考虑最近最新数据的特点，对不同的基分类器赋予不同的权值，加权集成 分类器，从而提高分类准确率。 论文的组织结构如下： 第一章为本文的引言部分。简单介绍了数据挖掘的相关知识，并论述了本文 的研究背景、研究内容及论文的组织结构。 第二章为数据流相关知识的介绍。主要介绍了数据流的概念、特点；数据流 的一个特征概念漂移；处理数据流的常用技术糟动窗口技术；最后介绍 了当前数据流分类的研究动态。 第三章为传统分类方法的分析。主要分析了现有的传统分类方法，并以数据 4 第一章绪论 郑州大学硕i 。学位论文 流的角度比较算法的优缺点，最后结合自己研究的特点指出选用基于e e p 的分类 方法作为本文分类算法的核心。 第四章为基于e e p 的数据流挖掘算法c e e p c e ，这是本文的主要研究内容。 本章分为两个部分：第一部分是相关知识和概念定义。主要介绍了e p 挖掘问题 的相关知识和几个概念的定义。第二部分重点介绍了c e e p c e 算法。主要包括 基本思想、基分类器的构造、集成分类器的产生与更新和分类器集成等内容。 第五章为c e e p c e 算法的实验结果对比及性能分析。 最后是本文工作总结、致谢和参考文献。 5 第二二章数据流挖掘 郑州人学硕l ：学位论文 第二章数据流挖掘 在同益增多的信息处理应用中，信息呈现形式较多的不是静态方式，而是动 态连续“流”的形式，称之为数据流( d a t as t r e a m ) 。所谓数据流【2 】是指一系列 连续的数据序列研，按照下标i 的增序读取。数据流每隔一段时间流入一个 元组，这个序列中的数据按照固定的次序快速到达，而且只能被读取一次或几次。 数据流挖掘有着广泛的应用，如信用卡欺诈监测、差异性营销、网络入侵检测和 传感器网络、网络监控、流量控制、w e b 日志和网页点击流、商务点击流分析及 个性化分析等。 本章介绍数据流相关知识，主要包括：数据流的特征、数据流算法分析处理 时应满足的要求、概念漂移的问题、滑动窗口技术以及当前数据流分类算法的动 态。 2 1 数据流的特征 数据流是只是传统数据的一种特殊形式，但是它具有自己独特的不同于传统 数据的一些特征： 连续：数据流元素以连续的形式到达。 有序：数据流是有序的数据序列，系统不能控制数据流中数据的顺序。 快速：数据流的数据快速到达，因此必须要求数据流挖掘算法能够实时 响应，与数据流元素到达的速率相兼容。 变化：数据流中的数据分布是持续变化的，而不是保持固定的数据分布 不变，从而采用统一的模式进行处理是不合理的。 海量：数据流数据持续到达，其数量可认为是海量的。 2 2 数据流算法分析处理时应满足的条件 基于数据流的上述特征，在对数据流进行分析和处理时，应该基本满足下面 的条件： 实时处理，实时响应：由于数据流数据快速到达，因此对数据流进行处 6 第二章蠡据流挖掘郑州人学硕l ：学位论文 理必须能够快速处理，并且能够实时响应。 线性扫描：由于数据流快速到达，所以对数据流进行访问时不能采用传 统的多遍扫描数据访问方法，要求必须利用线性扫描方法进行处理。 适应概念漂移：数据流中的数据是持续变化的，因此对数据流的处理在 满足实时性要求的同时，也必须能够捕获这些数据的变化。 存储概要信息：由于数据流数据的海量特性，对数据流的处理一般是不 存储的。但是，在进行某些分析处理时，必须考虑历史数据的特性，因 此必须存储历史数据的一些概要的信息。 2 3 概念漂移 数据流的一个显著特征就是其数据分布随着时间而不断发生变化，这类不断 变化的现象就称之为概念漂移【3 】口原来绝大部分数据挖掘算法都假设所使用的数 据是服从一种固定的分布，但事实上几乎所有用来挖掘的数据都违背了这个假 设，当数据不断到达的过程中，数据类分布( 目标概念) 随时间不断发生变化。 目前解决概念漂移问题主要集中在两个方面： 首先是概念漂移的发现，也就是说发现概念漂移发生的时机。 在预测型的问题中，假设已经建立起一个预测模型，然后使用这个模型对每 一个到达的样本进行分类和诊断。如果可以在一段时间之后判断样本的真实属性 ( 比如预测型的问题) ，就可以对模型的诊断结果进行验证。当收集到足够多的 样本之后，就可以通过对样本数据预测准确率的变化来发现是否发生了概念漂 移。如果检测到模型对刚刚收集到的训练数据的平均预测准确率和模型以前的平 均预测准确率相比突然发生了明显的下降，那么就说明概念漂移发生了。 如果在短期时间内无法知道模型的分析结果( 比如描述型的问题) ，那么就 需要引入一个可靠性估计( r e l i a b i l i t ye s t i m a t i o n ) 的方法，为每一次预测都分配 一个可信度的值。尽管每次的预测结果都不一定可以获得，但是可以根据可信度 的变化来判断是否发生了概念漂移。 然后是在检测到概念漂移发生之后，如何处理概念漂移。概念漂移的解决办 法基本上有两种：重建模型和模型的自适应。 一般说来，可以给出一个信赖度变化范围的阂值，用统计的方法来检查已经 7 第二章数据流挖掘 郑州大学硕十学位论文 建立起来的模型对当前训练样本的预测准确度。如果准确度的变化范围超过了那 个阈值，就标志着模型对当前的样本不再适用，即说明了发生了概念漂移。如果 检测到概念漂移已经发生，那么就可以重新设置模型的各种参数，或在必要时重 建模型来达到适应概念漂移的目的。该方法的优点在于动态检测模型对最新样本 的预测准确率的变化十分方便，而且代价较小，模型可以一直使用，直到其准确 度不满足要求。在此期间，模型一直都可以认为是值得信赖的。它的缺点是如果 模型中的一些参数需要根据情况重新设置的话，那么在每次重建模型时就需要有 一个机器学习和数据挖掘的专家来指导。 另一种方法，就是不必精确的探测出概念漂移以及发生的程度，模型可以自 动的根据输入样本的变化来自动的调整自己。在概念漂移的情况下，最高效的机 器学习算法应该可以发现概念漂移的发生，可以迅速从概念漂移中恢复，自动调 整自己对概念的描述以适应新的概念，而且当新概念与旧概念相似时可以最大程 度的利用以前学习到的知识。该方法的优点在于，在整个过程中模型可以自动地 维护，动态地调整自身来适应新的概念，而不需要有人专门从事模型维护的工作， 更不需要专家的参与。模型在使用过程中随时都是最适应与当前概念的，准确率 更加稳定，可适用性更强。 2 4 滑动窗口技术的介绍 由于数据流具有动态性、快速变化性、无限性等特点，它无法在全部地保存 下来以后再进行处理，这就要求在有限的存储空间的限制下，数据流处理只能是 部分地处理。但是在许多数据流的应用领域中，人们常常关心的是最近到达数据 处理的结果，因此，基于滑动窗口的数据流处理技术能够很好地实现关于最近到 达的数据流中数据相关处理工作。 滑动窗口阻止陈旧数据影响分析和统计，同时也是有限内存情况下的一种近 似工具。已有研究将草图( s k e t c h e s ) ，抽样( s a m p l i n g ) 和v - o p t i m a l 直方图应 用到滑动窗口模型中。 数据流上的滑动窗口技术1 1 9 】【冽【2 1 】【2 2 l 是指：在数据流上设定一个区域范围， 数据流的处理对象就是那些处于窗口内的数据内容。滑动窗口通常包含那些最近 到达的数据；当最新数据到来的时候，窗口将向前移动，将最旧的数据移动出窗 8 第_ 二章数据流挖掘 郑州人学硕t 学位论文 口。根据滑动窗口具体实现方法的差异，可将滑动窗口技术分为基于序列的滑动 窗口技术和基于时间的滑动窗口技术。基于序列的滑动窗口技术特点是：在大小 为形的滑动窗口内保存的是最近到达的项数据。基于时间的滑动窗口技术特 点是：在大小为的滑动窗口内保存的是最近时间内到达的数据。数据流经 常与时间有着紧密联系，因此，基于时间的滑动窗口技术比较适合于数据流处理 过程。 在数据流上利用滑动窗口获取近似值是一种普通的方法。它有以下吸引人的 特征： 1 ) 定义明确，易于理解：近似值的语义清晰，所以系统用户能够确信理解 在产生近似结果时那些数据被丢弃了； 2 ) 确定性：不必担心不合适的随机选择会产生坏的近似结果； 3 ) 强调最近的数据：在大多数现实应用中最近数据比历史数据更重要和相 关，如果你试图实时搞清网络流量模式、电话呼叫记录、事务记录、科学传感器 数据的意思，那么基于最近的数据来理解将比基于陈旧数据更有信息量和更有 用。 2 5 当前数据流分类研究 近年来，经过许多研究者的辛勤努力，基于数据流的相关研究己具备了较好 的理论基础。如与查询优化相关的：抽样技术、直方图技术、分位数技术、小波 分析技术、草图技术等；与数据挖掘相关的：决策树技术、聚类技术、频繁模式 挖掘技术等；一些相关的理论：模式增长理论、边界理论等。 数据挖掘领域中，已经有许多静态数据上的分类方法，如决策树、贝叶斯分 类、神经网络、支持向量机等。分类包含两个阶段：学习或模型构建( 基于包含 类标号的训练数据集来构建模型) 、分类过程或模型使用( 用于预测新来数据的 类标号) 。而后者有助于数据流分类，因为当新样本数据到达时将被立即分类。 如何将传统的分类方法应用于数据流成为一个值得讨论的问题。在传统的框 架下，训练数据以相对静态的形式存储于数据库，而且很多分类方法均是多次扫 描训练数据集。显然，分类模型构建的过程是离线进行的批处理过程，然而对于 数据流，没有离线阶段，这是因为数据流入速度快，使得存储所有数据和多次扫 9 第二章数据流挖掘郑州大学硕十学位论文 描并不可行。 为进一步阐述为何传统的分类方法不适用于数据流环境，下面以决策树作为 模型具体说明。大多数决策树算法一般采用自上而下的迭代策略，然而，所用的 选择最佳分裂属性的统计方法有所不同。回顾一下，决策树包括内结点( 非叶子 结点) 、分枝和叶子结点。属性选择方法用来选择当前结点上的最佳分类属性， 即能够最佳的区分训练元组。一般地，由分裂属性的每个可能值生长一个分枝， 而训练元组被相应地分到各个分枝，整个构建决策树的过程即在每个分枝上迭代 的过程。但是，在数据流环境下，既不可能收集所有的数据，并且重新扫描数据 也不现实。因此，需要对此方法做修正。 与传统的数据库系统不同，数据流的显著特征是时变性( t i m e - v a r y i n g ) ，它仅 存储当前数据。数据分布发生变化的特征表现为目标分类模型随时间而发生变化 ( 即概念漂移) 。概念漂移是在处理数据流时要考虑的重要因素之一。 在数据流分类方面，研究者们已经提出了不同的分类方法。其中具有代表性 的有四种：h o e f f d i n g 树算法【矧、w d t t l 们( v e r yf a s td e c i s i o nt r e e ) 、c v l 州1 6 1 ( c o n c e p t - a d a p t i n gv e r yf a s td e c i s i o nt r e e ) 和使用投票表决的多分类器加权集成 方法e n s e m b l ec l a s s i f i e r s 1 8 1 。 ( 1 ) h o e f f d i n g t r e e 算法 h o e f f d i n gt r e e 算法是一种数据流上的决策树学习算法。它已被初步应用到 跟踪w e b 点击流并构建模型来预测哪些网站或主机经常被访问。该算法时间复 杂度是次线性的，并且能产生与传统的批处理方式下几乎一致的决策树。 h o e f f d i n gt 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 m o f f b o u n d ) ：对r 范围内 的随机变量r 进行次独立观测，是次观测的平均值。其中r 是属性选择方 法，对于h o e f f d i n gt r ，r 是信息增益( 对于概率，r 为1 ；对于信息增益，r 为 l o g c ，c 是类的个数1 。h o e f f d i n gb o u n d 理论保证r 的真实平均值至少为，一的概 率为1 - d ，d 由用户指定，e 由经验值确定。 r 。一 一旦学 ( + ) h o e f f d i n g t r e e 算法使用上述理论保证了以高概率、使用小样本来选择节点上 1 0 第二章数据流挖掘 郑州大学顾l 学位论文 的最优分裂属性。而所选取出的属性和使用无穷样本得到的结果一样。h o e f f d i n g b o u n d 理论与概率分布无关。因为不可能知道信息增益的概率分布或采用的属性 选择方法，所以采用该理论是合适的。 使用h o e f f d i n g t r e e 有另外的两个特性。首先，不再多次扫描数据集。再者， 算法能够增量更新。因此，在新数据流入时，可以同时利用已有的模型做预测， 并且可以引入新来的数据作为训练集，不断调整模型从而提高模型的准确率。 h o e f f d i n gt r e e 算法有一些不足之处。例如，当两个属性的分裂质量几乎相同 时，算法花费大量时间做此计算。另外，存储空间利用率可以进一步优化。最后， 算法无法处理概念漂移。 ( 2 ) v f d t 和c v f d t v f d t ( v e r yf a s td e c i s i o nt r e e ) 是对h o e f f d i n g 树算法的改进算法，提高了 速度和存储利用率。主要在以下方面做了改进：当结点上累积一定数目的训练样 本时才计算增益函数g ；删除最不常用的叶子节点；丢弃无价值的分裂属性；改 进初始化方法。但是，仍然不能够处理数据流中的概念漂移。 处理概念漂移的常用方法是使用滑动窗口，它引入新的样本并且删除历史样 本。在滑动窗口内反复训练传统的分类器，当新样本到达时，插入窗口的头部， 同时剔除尾部数据，从而保证训练得到的分类模型始终反映当前的数据分布。但 是，这种方法对窗口大小敏感。当窗口太大时，模型不能准确反映概念漂移；窗 口太小时，没有足够的数据用于构建准确的模型。再者，不停地构建分类器模型 的代价相当高。 为了解决数据流中的概念漂移，h u l t e n 等人对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 ) 分类器集成算法e n s e m b l ec l a s s i f i e r s 2 0 0 3 年，w a n g 等人提出了集成分类器的方法，它使用多个分类器来代替单 1 1 第二章数据流挖掘郑州人学硕l ：学位论文 个分类器，对不同时间段构造不同的分类器，利用最近的数据决定每个分类器的 权重，然后用多个分类器的加权和进行预测。实验表明与单分类器相比，该方法 具有更高的分类准确率。 v f d t 和v f d t c 是基于决策树的单分类器算法，利用单个分类器模型来反 映整个数据流分布，其预测准确率会受到概念漂移的影响。因为历史数据与未来 数据可能具有完全不同的分布。 w a n g 等人提出的集成方法以c 4 5 、r i p p e r 、n a i v eb a y e s i a n 分类为基分类 器，集成多个分类器的方法通常可以提高分类准确率，特别是基分类器具有一定 的差异性时，它往往比单分类器的准确率高。 2 6 小结 本章首先简单的介绍了数据流的特征和数据流挖掘算法分析处理时应满足 的条件；然后，重点介绍了概念漂移问题的相关研究和目前数据流挖掘常用的一 种技术滑动窗口；最后，简要介绍了当前数据流分类方面的研究工作。从而 说明本文所提出的分类算法有一定应用需求，同时说明本文算法必须满足的要 求，便于更加清楚地介绍。 第三章传统的分类方法郑州人学硕 学位论文 第三章传统的分类方法 数据挖掘领域中，已经有许多静态数据上的分类方法，如决策树、贝叶斯分 类、神经网络、支持向量机等。分类包含两个阶段：学习或模型构建( 基于包含 类标号的训练数据集来构建模型) 、分类过程或模型使用( 用于预测新来数据的 类标号) 。而后者有助于数据流分类，因为当新样本数据到达时将被立即分类。 大多数的数据流挖掘算法都是基于以往的静态数据挖掘算法，在已有算法的 基础之上增加了对“流”式数据的处理，早期的增量式数据挖掘算法是数据流挖 据算法的基础。增量式使已经建立好的数据模型可以重复使用，使得挖掘“流” 式数据成为可能。 如何将传统的分类方法应用于数据流成为一个值得讨论的问题。在传统的框 架下，训练数据以相对静态的形式存储于数据库，而且很多分类方法均是多次扫 描训练数据集。显然，分类模型构建的过程是离线进行的批处理过程，然而对于 数据流，没有离线的阶段，这是因为数据流入速度快，使得存储所有数据和多次 扫描并不可行。所以，必须对传统分类算法进行分析。 本章主要介绍了决策树分类、贝叶斯分类、源于关联规则的分类、基于e p 的分类算法、k 一最临近分类、神经网络分类等传统分类算法的思想、优缺点和主 要的实现算法，同时也比较了各个算法在u c i1 2 个数据集上的分类准确率，从 而为选择适当的分类算法作为基分类器的构造算法作好铺垫。 3 1 决策树分类 决策树( d e c i s i o nt r e e ) 是一个类似于流程图的树结构，决策树分类算法以 树形结构表示分类结果，树根节点代表整个数据集合空间，每个内部节点表示在 一个属性上的测试，每个分枝代表个测试输出，测试将数据集集合空间分割成 两个或多个块，而每个树叶节点代表类或是类的分布。由根节点到叶子节点的路 径描述了各种分类规则。该算法在统计学、机器学习和数据挖掘领域都有广泛的 应用。 决策树算法【2 4 】的采用“分而治之”的策略，基于信息熵递归地选择分割属性， 第三章传统的分类方法郑州大学硕士学位论文 根据属性集的取值选择实例的类别。主要是在树的每个节点上使用信息增益度量 选择测试属性，选择具有最高信息增益的属性作为当前节点的分割属性。 算法的基本策略： 树以代表训练样本的单个节点开始。 如果样本都在同一个类，则该节点成为树叶，并用该类标记。 否则，算法使用成为信息增益的给予上的度量作为启发信息，选择能够 最好地将样