（计算机软件与理论专业论文）适应概念漂移的数据流分类算法研究.pdf

意 扛 c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho nd a t as t r e a mc l a s s i f i c a t i o n a l g o r i t h mo fa d a p t i n g t ot h e c o n c e p t - d r i f t c a n d i d a t e ：c a oz h e n x i n g s u p e r v i s o r ：p r o f y a n gj i n g a c a d e m i cd e g r e e a p p l i e df o r ：m a s t e ro f e n g i n e e r i n g s p e c i a l i t y ：c o m p u t e rs o f t w a r ea n dt h e r o y d a t eo fs u b m i s s i o n ：m a r c h , 2 0 1 0 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：、彩墟琶 日期：a 口年多月，a 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：曾砺考导师( 签字) ：夕隆姑 - 日期：如矿年乡月俗昌 c 7 , 。1 。年弓月1 7 日 。 哈尔滨工程大学硕士学位论文 摘要 近几年，数据挖掘领域涌现出一种的新研究课题一数据流挖掘。在许多 实际应用中，如股票分析、网络故障监测、信用卡欺诈领域得到了广泛的应 用。数据挖掘研究领域里分类挖掘是其中重要的分支之一。现在成熟的数据 流分类挖掘算法有：基于h o e f f d i n g 树的v f d t 、适应概念漂移的c v f d t 、 集成分类器e n s e m b l ec l a s s i f i e r s 、v f d t c 等。其中，集成分类方式被广泛应 用在数据流分类挖掘领域。数据流的特点之一一概念漂移，是当今所有数据 流分类算法必须面对的最大的挑战。分类算法性能的高低，取决于其适应概 念漂移的能力。如今大多数性能优越的分类算法均采用集成分类方法。 本文首先阐述了数据挖掘理论的相关知识，详细介绍了经典数据流分类 算法e c 4 5 ，以及概念漂移的概念。与e c 4 5 相比，c e e p c e 算法提高了分 类的准确率，但仍存在适应概念漂移能力不足的问题。本文提出的适应概念 漂移的数据流分类算法基于集成分类器的构造、淘汰、更新、以及差异性加 强等因素来优化分类性能。首先，介绍了基分类器的构造方式，结合e e p 的 特性构造出有较高区分度的基分类器。其次，给出了分类器的淘汰标准，根 据基分类器的分类误差率进行淘汰。此外，根据算法c e e p c e 提出了两点改 进。第一次改进提出了基于分类误差权值的差异性加强方法，从而提高了集 成分类器的分类精度。在保证基分类器分类性能的前提下，通过差异性加强 方法提取最终的分类器集合。第二次改进对集成分类器的更新方式进行优化， 更新时根据分类器的平均错误率与随机分类错误率的比较，选择是否加入相 反分类器，这种验证方式虽然在时间效率上有所降低，但面对大数据量的分 类时，其适应当前概念的优越性将会体现出来。 关键词：数据挖掘；数据流；分类；概念漂移；集成分类器 ，i lp；r。l。 ， ， 哈尔滨工程火学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，d a t am i n i n gh a se m c e e dan e wf i e l do fr e s e a r c h - d a t a s t r e a mm i n i n g i nm a n yp r a c t i c a la p p l i c a t i o n s ，s u c ha ss t o c ka n a l y s i s ，n e t w o r k f a u l td e t e c t i o n ，a n dc r e d i tc a r df r a u d ，d a t am i n i n gh a sb e e nw i d e l yu s e d i nt h e f i e l do fd a t am i n i n g ，c l a s s i f i c a t i o nm i n i n gi so n eo ft h ei m p o r t a n tb r a n c h e s n o w t h e r ea r es o m ec o m p r e h e n s i v ec l a s s i f i c a la l g o r i t h m s ：v f d t - b a s e do nh o e f f d i n g t r e e ，c v f d t - a d a p t i n gt ot h ec o n c e p td r i f t ，e n s e m b l ec l a s s i f i e r sa n dv f d t c e n s e m b l ec l a s s i f i e r si sw i d e l yu s e di nd a t as t r e a mc l a s s i f i c a t i o nm i n i n g c o n c e p t d r i f t o n eo ft h ec h a r a c t e r i s t i c so fd a t as t r e a m s ，i st h eb i g g e s tc h a l l e n g ei n c l a s s i f i c a t i o nm i n i n g t h ep e r f o r m a n c eo fc l a s s i f i c a t i o na l g o r i t h md e p e n d so ni t s a b i l i t yt oa d a p tt o t h ec o n c e p td r i f t n o w ，e n s e m b l ec l a s s i f i e r s i st h em o s t s u p e r i o rp e r f o r m a n c e o ft h ea l g o r i t h m f i r s tt h ep a p e rg i v e st h et h e o r yo fk n o w l e d g eo fd a t am i n i n ga n ds h o wt h e a l g o r i t h me c 4 5a n dt h ec o n c e p to fc o n c e p t - d r i f t i n g c o m p a r i n gw i t he c 4 5 ， a l t h o u g ha l g o r i t h mc e e p c ei m p r o v e st h ea c c u r a c y ，h o w e v e r ，t h ea b i l i t y o f a d a p t i n gt ot h ec o n c e p t d r i f t i n gi ss t i l li n a d e q u a t e t h ec l a s s i f i c a t i o na l g o r i t h m t h a ta d a p tt ot h ec o n c e p td r i f ti sb a s e do nt h ee n s e m b l ec l a s s i f i e r s c o n s t r u c t i o n ， e l i m i n a t e d ，u p d a t e ，a n d t h es t r e n g t h e n i n go fd i f f e r e n c e sf o ro p t i m i z i n gt h e c l a s s i f i c a t i o np e r f o r m a n c e f i r s t ，t h ep a p e rd e s c r i b e st h ec o n s t r u c t i o no ft h eb a s e 曩 c l a s s i f i e ra n dt h ee l i m i n a t i o nc r i t e r i a ，c o m b i n i n gt h ec h a r a c t e r i s t i c so fe e pw i t ht o 己 c o n s t r u c tah i g h e rd e g r e eo fd i s t i n c t i o nb e t w e e nt h eb a s ec l a s s i f i e r s s e c o n d ，t h e 簟 p a p e rf i n g e ro u tt h es t a n d a r do ft h ee l i m i n a t i o no ft h ec l a s s i f i e r sa c c o r d i n gt ot h e i e r r o rr a t eo fc l a s s i f i e r s m o r e o v e r ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fa l g o r i t h m s c e e p c e ，t h ep a p e rp r o s p e r st w oi m p r o v e m e n t s t h ef i r s t m e t h o dg i v e st h e m e t h o do fs t r e n g t h e n i n go fd i f f e r e n c e sb a s e do nc l a s s i f i c a t i o ne r r o rt oi m p r o v e t h e a c c u r a c y o fi n t e g r a t e dc l a s s i f i e r s u n d e rt h ep r e m i s eo fe n s u r i n gt h e - ， i 哈尔滨： 程犬学硕士学位论文 p e r f o r m a n c eo fb a s ec l a s s i f i e r ，e x t r a c tt h ef i n a l s e to fc l a s s i f i e r s n es e c o n d m e t h o di m p r o v e st h eu p d a t i n gw a y i no r d e rt oc h o o s ew h e t h e rt oj o i nt h e o p p o s i t ec l a s s i f i e rb a s e do nt h ec o m p a r i s o no ft h ea v e r a g ee r r o rr a t ea n dr a n d o m c l a s s i f i c a t i o ne r r o rr a t e ，w h e nu p d a t i n gt h ec l a s s i f i e r s a l t h o u g hw a s t i n go ft i m e ， w h e nf a c e dw i t hl a r g ea m o u n t so fd a t ac l a s s i f i c a t i o n ，t h es u p e r i o r i t yt oa d a p tt o t h ec o n c e p to f c h a n g ew i l lb er e f l e c t e d k e y w o r d s ：d a t am i n i n g ；d a t as t r e a m s ；c l a s s i f i c a t i o n ；c o n c e p td r i f t ；i n t e g r a t e d c l a s s i f i e r 锤 j 嚣 ， f p 翟 哈尔滨： 程大学硕十学位论文 目录 第1 章绪论1 1 1 研究背景1 1 2 国内外研究现状2 1 3 本文研究内容2 1 4 全文组织和结构3 第2 章数据挖掘基础”4 2 1 数据挖掘概述4 2 1 1 数据挖掘基础4 2 1 2 分类定义和过程6 2 1 3 贝叶斯定理8 2 1 4 决策树模型9 2 2 显露模式1 2 2 2 1 基本概念1 2 2 2 2 基于显露模式的分类算法1 3 2 3 数据流挖掘1 3 2 3 1 数据流分类1 4 2 3 2 数据流聚类”1 5 2 3 3 滑动窗口- 1 5 2 4 概念漂移1 6 2 4 1 概念漂移的基本特征1 6 2 4 2 适应概念漂移的分类算法的研究一1 8 2 5 集成分类器e c 4 5 ”1 9 2 5 1 离线c 4 5 的介绍1 9 2 5 2 集成分类器e c 4 5 ”1 9 2 6 本章小结2 0 哈尔滨一 程大学硕士学位论文 第3 章适应概念漂移的优化分类算法2 1 3 1 问题的提出2 1 3 2 相关概念和定义2 2 3 3 算法提出及描述2 3 3 4 集成分类器的构造2 4 3 4 1 基分类器的构造2 5 3 4 2 分类器的分类误差加权“2 7 3 4 3 集成分类器的更新方式2 9 3 4 4 分类器的差异性加强3 0 3 5 分类器的流程描述及构造算法3 2 3 6 本章小结“3 4 第4 章相关实验结果及分析3 6 4 1 实验原理“3 6 4 2 算法性能分析3 7 4 3 本章小结4 3 结论”4 5 参考文献4 6 攻读硕士学位期间发表的论文和取得的科研成果5 1 致谢”5 2 一， 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 研究背景 伴随信息技术的高速发展和搜索能力的日益提高，产生了海量的数据信 息。过去这些海量数据的存储形式为静态地存储在物理存储器上。近年来， 产生了一类新的数据密集型的领域一数据流挖掘，这类流数据广泛存在于网 络、电信、股票等众多应用领域。面对如此丰富的流数据，传统的数据挖掘 方法已远远不能满足该领域的需要。目前，数据流挖掘领域的相关研究取得 了一定的进展。如：边界理谢t 】、频繁模式挖掘技术1 2 l 、分位数技术l a l 、聚类 技术1 4 l 、草图技术 s l 、决策树技术1 6 1 、还有模式增长理论1 7 1 等；此外，还有直方 图技术i s l 、小波分析技术| 9 】、抽样技术【1 0 1 等。这些技术给予了数据流挖掘有效 的技术支撑，同时将数据流和传统数据挖掘的特点相结合，可以得到基于数 据流挖掘任务的解决方案。 这种新式的数据挖掘技术的应用范围正在扩大，应用数量正在增长。这 些领域的相同特征就是要求在大量、快速的数据流上进行一次性准确的扫描， 挖掘其中有用的信息，以获取当前数据的趋势、模式和异常等。这种新特性 产生了一些新的本质性问题，这都是传统数据挖掘技术、数据库技术解决不 了的。为了面对这些新的挑战，适应新的应用背景，数据流分类挖掘技术产 生了。 目前，大量的数据流分类挖掘的研究工作旨在高效准确地解决隐含概念 漂移( c o n c e p td r i f t ) 的数据流分类问题。概念漂移的存在使得数据流分类挖掘 时产生一定的误差，对分类工作的最终结果产生较大的影响。本文将针对概 念漂移问题提出一种分类算法，旨在提高算法对概念漂移的适应能力，面对 大数据量的分类问题时，尽量降低算法的时间消耗，最终提高算法的分类精 度。 ， l b q 哈尔滨工程大学硕十学位论文 1 2 国内外研究现状 目前，国内关于数据流分类挖掘技术的研究相对较少，主要集中在集成 分类器算法和自适应方面的研究。最近复旦大学秦首科博士通过对数据流的 概念突变检测技术研究提出了数据流异常检测技术，是原有技术的的补充和 创新。其中基于直方图( i h ) 的数据流突变检测技术更加全面地概括了数据流 上的突变信息，并区分开了噪声数据的干扰。基于单调搜索空间的数据流突 变检测算法拥有较高的分类精度，并且时间、空间的利用率较低，更符合突 变检测的低标准要求。基于分段分形技术的数据流突变检测算法有很高的分 类准确率以及较高的执行效率。此外数据流上的分段分形模型，还能在保证 一定误差界限的条件下，用于重构原始数据流。 国外的各研究机构都展开了对数据流分类算法关于概念漂移问题的相关 领域的研究。国外与数据流概念漂移问题相关领域的代表性研究包括：2 0 0 1 年，d o m i n g o s 等人在决策树算法的基础上，提出了一种改进的适应概念漂移 的算法v f w w - j 。v f d t 思想是基于h o e f f d i n g 边界理论来处理数据流的单个分 类决策树算法。此后，g a m a 等人在v f d t 的基础上对分类性能做了进一步提 升，提高了v f d t 树的性能【6 1 。同年，s t r e e t 等人提出了集成分类器算法思想， 并命名为s e a 。此外，也把该算法思想移植到概念漂移检测的应用领域中， 同时给出了理论s e ac o n c e p t l n l 。2 0 0 3 年，w a n g 等人对集成分类器中权值的 削减和设定进行了深层次的讨论，并且提出了依据分类器的分类错误实时做 出变化的技术。2 0 0 4 年，r u s h i n g 等人提出c b e a l t ，l ，讨论了一种基于聚类思 想的集成分类器算法，文中强调了此研究领域的应用背景的重要性。2 0 0 4 年，c h u 等人将流行的b o o s t i n g 技术应用到数据流分类挖掘领域中，给出了自适 应集成分类器挖掘算法【2 9 】。 1 3 本文研究内容 面对数据挖掘领域涌现出的新的热点方向一数据流分类挖掘。本文将根 据数据流几个方面的特点进行分析，研究流数据对传统分类方法的新要求和 2 、 、 - 4 哈尔滨工程大学硕士学位论文 数据流领域的最新研究成果。针对处理快速到达的数据方面数据流分类算法 存在的时间效率和分类精度低的不足方面，提出一种适应概念漂移的数据流 分类算法，以便提高分类算法的准确率。 本文将从下面四个方面进行研究： ( 1 ) 首先研究数据挖掘领域的基础，传统数据分类挖掘算法在数据流挖掘 领域的应用。 ( 2 ) 研究分析数据流的特点和一些数据流分类算法在数据流挖掘领域存 在的问题。 ( 3 ) 针对概念漂移、时间效率和分类精度等方面的不足提出改进策略。 ( 4 ) 最后通过实验验证算法适应概念漂移能力以及分类准确率方面的可 行性。 1 4 全文组织和结构 本文总共分四章。第1 章是全文绪论的绪论部分，主要介绍了研究目的、 意义及论文的结构。第2 章主要介绍数据挖掘的理论及相关技术以及数据流 挖掘的基本特点，重点介绍概念漂移的特点和显露模式的相关概念。第3 章 在对上文分析介绍的基础上，针对现有数据流分类算法处理数据流时在适应 概念漂移的能力和分类精度上的不足，提出一种能较好处理数据流分类中适 应概念漂移问题的集成分类算法，对集成分类器的更新方式进行改进，结合 分类误差进行了集成分类器的差异性加强。第4 章是对本文提出的分类算法 进行实验分析。最后一部分是结论。 3 k 、 哈尔滨工程大学硕+ 学位论文 第2 章数据挖掘基础 2 1 数据挖掘概述 2 1 1 数据挖掘基础 近十几年来，人们搜集数据的能力有了长足的进步，并且已经能够运用 信息技术高效地生产。各式各样的数据库应用于科学研究、政府办公、工程 运作和商业管理等领域。就在这个时候，一个新的问题被提了出来。就在这 个信息爆炸的时期，海量的信息成为每一个人必须面对的问题。怎样才能不 被海量的信息所淹没，并且从中挖掘有用的知识，提取有效信息称为新的挑 战。面对这些挑战，数据挖掘技术应运而生。 数据挖掘 2 1 就是从大量随机的模糊的且不完全的并伴有有噪声的数据中 提取隐含在里面的、不被人们所知道的、但又是潜在有用的知识和信息的过 程。数据挖掘的概念有很多不同的表述。例如，从数据库中发现数据分析、 数据融合( d a t af u s i o n ) 、知识( k d d ) 和决策支持等。专家认为形成知识的根本 就是原始数据。原始数据可以分为结构化和半结构化。关系数据库中是结构 化的数据，而如图形、图像、文本等数据均是半结构化的。还有一种分布在 网络上的数据大部分都是异构型。发现知识的方法多种多样，有数学方式的， 也有归纳的，有非数学的，也有演绎的。挖掘出的知识可以用于决策支持、 过程控制、查询优化、信息管理等多种有实际应用意义的领域。 数据挖掘是一门综合学科，其综合许多其他学科的先进理念，包含了很 多的实用的功能，主要功能有以下几方面： ( 1 ) 分类：依据待处理对象的属性等因素，构建不同的类别用来描述所有 对象。比如，银行系统依据过去的数据将服务过的所有客户分为彼此不同的 种类，当新客户到来时，就能够根据预先设计的分类区分新到来的客户，以 便能够直接的采用相应的服务。 ( 2 ) 聚类：将数据按照一定规则划分，相似的数据划分为同一个类中。类 4 哈尔滨工程大学硕士学位论文 之间的数据不同。 ( 3 ) 关联规则：关联是当一件事发生的前提下，令一件事也会发生的联系， 类似于这种关系。比如：天天读书的人也有可能天天做作业，这种比例有多 高，应用可信度和支持度加以描述。 ( 4 ) 序列模式：与关联不同，关联是横向的联系，而序列则相反，是一种 纵向的联系。比如，今天外汇储备的变化，将会带来明天股票市场的变化。 ( 5 ) 预测：控制待处理对象的发展规律，据此对以后的趋势提供预判。例 如，对全球经济的预判。 ( 6 ) 偏差检测：对特殊对象的描述，分析内在的因素。假设股市中4 5 万 的交易量里面有1 1 1 例的不规范交易，为了规范股市秩序，必须发现这1 1 1 例的发生的原因，增强股市的规范性。 上面六点是数据挖掘领域的几个重要技术，需要特别注意的是：这几项 功能不是相互独立的，在数据挖掘领域中相互支撑，共同发挥作用。 数据挖掘领域里通常运用的技术大致有以下五种： ( 1 ) 可视化技术：一般做法是将数据直观的展示出来，同时应用描述统计 的方式，图表就是这种形式，例如直方图。可视化技术的难点在于随着数据 维度的提升而加大。 ( 2 ) 传统的统计方法：将抽样技术使用在海量数据的统计上。分析全部的 数据是没有必要的同样也是不可能的，只能在理论的基础上进行有效的抽 样；如因子分析、聚类分析、多元统计分析等。 ( 3 ) 决策树：应用事先约定的规则进行划分，根据属性划分树状图，可用 于未知样本的分类和划归。经典的算法有哪、a a d 、劢、c a 5 、( 2 5 0 盘莹 守o ( 4 ) 神经网络：将人类的神经元作为研究对象，分析其工作的流程。期间 将访问输入层，隐藏层，输出层等，对经过的数据进行处理，并得出最后的 结论。 ( 5 ) 关联规则挖掘算法：用来描述每个数据之间关系的规则。此外，还有 5 k 、。 “ 哈尔滨工程大学硕士学位论文 最邻近算法，模糊集合方法，粗糙集方法等。 2 1 2 分类定义和过程 如今，经典的静态数据的分类挖掘方法有：贝叶斯分类、支持向量机、 神经网络、决策树分类。下面首先介绍分类的定义，以及通用的分类的评估 准则，然后再给出各种经典分类技术的介绍。 分类的定义以下面描述概括：大量的数据组成输入的样本集，也就是训 练集( t r a i n i n g s e t ) 。各个样本均有多个属性，属性分为两种，连续的和离散的。 每个样本都有一个称为类的属性，该属性标明所属的类。因此，分类过程就 是基于类别已知的训练样本进行分析，使用样本剩余的属性构建的一个分类 模型，然后判定新的测试样本的所属类。 分类的过程可以分为两步： 第一步是模型的建立，建立模型描述训练数据集。通过对数据库元组属 性的理论分析建立模型。假设各个元组属于不同的预定义类，类的归属由类 标号属性确定。基于分类挖掘，元组也可以称作实例、样本和对象。用作构 建模型的元组集称为训练样本集。训练样本集内的每个元组称作训练数据， 均由样本群随机的进行抽取。因为训练样本均带有类标号属性，所以这一步 骤也称作有指导性地学习( 也就是说模型的构建是在知道各个训练数据所属 类的情况下有指导性的进行) 。这一过程与无指导性地学习( 例如聚类) 相异， 聚类中的各个训练数据的类标号是不知道的，同理，学习的集合类和个数事 先也可能不知道。 一般情况下，模型的学习方式以决策树、数学公式或者分类规则的形式 给出。比如，给定一个数据库，里面存储了顾客的信用度等信息，模型可以 基于分类规则的学习，依据顾客信誉度的优良水平对顾客进行识别( 见图 2 1 ) 。应用的规则可以为后来的测试样本进行分类，也为数据库存储的信息 能得到更好的理解提供了帮助。 6 哈尔滨t 程大学硕士学位论文 训练数据 姓名年龄收入信誉度 张三 4 0中良 宋刚3 1 4 0高优 1t 分类方法 1r 分类规则 l f 年龄= 3 1 4 0 a n d 收入= 高t h e n 信誉度= 优 图2 1 获取顾客信誉规则 第二步( 见图2 2 ) ，应用新建立的模型对未知样本进行分类。首先，应 对模型或分类规则的预测准确率进行评估。其中，保持方法是一种应用带有 类标号的测试样本集的简单方法。测试样本基于随机选取的方式，独立于用 来建立模型的训练数据。模型针对测试样本集的准确率是被模型正确分类的 测试样本所占的比重。将模型分类的结果与样本的类标号进行比较。为了准 确得到模型的准确率，如果使用训练数据进行评估，模型的可信度可能会较 低，故通常应用测试样本集进行评估。 7 哈尔滨jl = 程大学硕十学位论文 测试数据 姓名年龄收入信誉度 小一 l 。当d ) = 8 时， 称此时e p 为j e p ( j u m p i n g e p ) 。 当两个类之间的变化程度较大时，表明两个类之间的属性有较大的不同。 此时，e p 的优越性体现出来，它可以有效的区分两个类之间属性的不同。可 以看出，e p 具有较高的区分能力。x 是一个特定的属于类c ；的e p ，如果对于 任一样本s ，满足x s ，则称e p 覆盖了样本s ，也可称为s 包含e p 。 e p 表明样本属性的支持度变化较大的一类，但大量的数据中会存在大量 1 2 哈尔滨：i = 稗大学硕十学位论文 的e p 。一个良好的有价值的e p 应相互独立而且不存在包含的关系【4 1 j 。这样可 以提升分类的效果。经过大量的实验证明，单纯的e p 对分类的效果产生的影 响并不好。因此，k r a m a m o h a n a r a o 和h f a n 提出了一个特殊的e p ，称为e e p 。 定义4 ( e e p )当样本x 是项集d 的e p 时，并满足： ( 1 ) s u p d ( 为的大小大于或等于预先确定的一个阈值。 ( 2 ) x 是满足条件1 的最小项集。 满足上面两个条件的e p 称作e e p 。可以看出，e e p 是e p 的子集且是最小的。 当满足给定的增长率及支持度的条件时，e e p 所用到的属性最少。e e p 的特性 使得分类器更为精简，同时又具备较高的区分能力以及抗干扰能力。 2 2 2 基于显露模式的分类算法 1 9 9 9 年d o n g 提出显露模式( e p ) 概念后，应用e p 作为分类因子的分类算 法得到了许多专家的认可。随后产生出第一个应用e p 的分类算法c a e p t 4 4 j 。 随着c a e p 的产生，许多研究者又构造了如j e pc l a s s i f i e f l s s 】、b c e p t 3 9 j 和 d e e p s t 4 0 j 等经典算法，这些算法继承了传统分类算法的优点，同时又提高了预 测精度。但这些算法在构造以及更新方式上都仍有改进的空间。最近又提出 了一种基于e p 的c e e p c e t 4 2 1 算法，该算法在一定程度上改进了原有的算法， 提升了分类的精度，但更新方式以及分类精度上仍有不足之处。 2 3 数据流挖掘 数据流的数据分布不稳定、高速到达、一次性扫描等特点决定了数据流 挖掘技术要比传统的数据挖掘更复杂，所以数据流挖掘技术主要需解决以下 几点问题： ( 1 ) 算法必须在有限的内存资源条件下进行挖掘。由于数据流是连续到达 的，需要大量的内存资源，所以只能对数据流进行实时的处理。因此，在设 计数据流挖掘算法时如何利用有限的资源是必须考虑的问题。这样才能使算 法一次性可以处理大量的数据。 ( 2 ) 挖掘算法必须高效。对数据流挖掘的过程中，内存中的数据必须保证 1 3 哈尔滨：翻犟大学硕士学位论文 都是新近的数据，实时性要求内存中的数据没被将到达的数据替换前，就得 对数据进行处理。因此算法的高效与否直接影响到挖掘的效率，即设计一种 在最短的时间里对数据有效挖掘的算法。 ( 3 ) 挖掘算法必须一次性扫描设数据。因为数据流是快速、连续不断的产 生，这种特点决定了算法不能有阻塞数据流的行为，因此只能扫描一次新近 的数据，即挖掘算法必须一趟扫描完毕。 2 3 1 数据流分类 分类( c l a s s i f i c a t i o n ) t t 5 1 的目的是将待分类对象划归到一个预定义的目标 类。而传统分类挖掘算法的目的是利用有限内存里存储的大量的数据来构造 模型，许多经典算法均是采用该思想。! z h r a i n f o r e s t t t 5 】、s p r i n t t l s j 算法等。 然而，这些传统算法均是在进行多次性扫描的前提下实现的，算法本身并不 能适应数据流一次性扫描、快速到达等特点，所以这些算法并不适合数据流 的分类挖掘。 为了解决数据流分类的要求，d o m i n g o s 等人设计了一个基于增量模型的 决策树算法- v f d t ( v e r yf a s td e c i s i o nt r e e ) 。v f d t 能够在有限的内存资源里 利用固定的时间构建决策树，有效地解决了内存、时间的利用率问题。在 h o e f f d i n g 边界理论的保证下，v f d t 与批量学习( b a t c hl e a r n e r ) 的二者的输出 模型基本能取得一致。 与其他的大多数学习系统一样，v f d t 将数据看做是从静态数据分布中 随机挖掘的，不能体现出数据流随时间变化而变化的动态趋势。为了解决这 个问题，g h u l t e n 和p d o m i n g o s 将滑动窗口引入到t 算法中，针对v f d t 在这方面的不足加以改进，设计出算法c v f d t ( c o n c e p t a d a p t i n gv e r yf a s t d e c i s i o nt r e e ) ，c v f d t 不仅仍具有v f d t 算法在精度和速度方面的优势外， 还加入了对数据流到来时概念变化的监测以及响应机制。c v f d t 更好的适应 了数据流的特点，以及数据流的分类。c v f d t 不足之处在于数据流发生概念 漂移时，只能重新构建分类模型，这样大大降低了算法的时间效率。 1 4 哈尔滨工程大学硕十学何论文 2 3 2 数据流聚类 数据聚类是指将抽象或物理对象所组成的集合划分为相似度较高的对象 组成的各个类的过程1 1 6 】，是数据挖掘领域的一个重要组成部分。聚类过程所 产生的簇是由同一组数据对象组合而成，簇内的每个对象彼此相似，而簇与 簇之间的对象彼此又有很大的差别。许多应用里都将同一簇中的对象数据当 做同一个整体。聚类不同于分类，其并不依靠实现设定的带类标号的训练数 据。所以，聚类是无指导、观察式的学习。许多应用领域中均可以看见聚类 分析的影子，如将客户群划分到不同类等，其他算法中的提前处理部分也可 以用到聚类分析，因此聚类分析有很大的研究价值。 如今，数据流聚类算法也有成熟的理论，主要集中在k 平均问题上。g u h a 等人设计了一种易于理解的数据流聚类算法，是关于k m e a n s 的常数因子的 相近算法旧。其基本思想是：原始数据用带权值的中心点来代表，然后用其 他数据实现增量聚类。l i a d a n0 c a l l a g h a n 等人设计的高速的k - m e a n s 算法， 提高了聚类的质量，并且将该算法应用到数据流的环境中1 1 8 】。当数据流连续 到达时，算法均产生有界的误差。只是这些算法必须提前指定k 的取值，聚 类的个数也不能随意变动。 2 3 3 滑动窗口 因数据流具有一次性扫描、高速、动态性、变化、无限性等特点，致使 无法将全部数据保存以后再处理，这就使得只能在有限的存储资源下，进行 处理部分的数据流。大多数数据流的实际应用中，常常只关注最新近数据的 处理结果。而在进行数据流处理时，应用滑动窗口技术能够对新近数据达到 最好的处理结果。 滑动窗口摒弃过时的数据，排除了过时数据对统计分析的影响。是有限 存储资源的情况下较理想的工具。已经有研究表明：将抽样( s a m p l i n g ) ，直方 图( v - o p t i m a l ) 和草图( s k e t c h e s ) 应用到具有滑动窗e 1 技术的模型中具有良好的 效果。 哈尔滨工程大学硕十学位论文 滑动窗口包含最新近的数据；当新的数据到达之后，滑动窗口向前移动， 将停留窗口内时间最长的数据移出窗口之外。依据滑动窗口具体实现方式的 不同，可以将滑动窗口技术分为两种：基于序列和时间的滑动窗口技术。前 者的特点是：在长度为w 的滑动窗口内存储新近到达的w 个样本。后者的 特点是：在长度为w 的滑动窗口内存储最近w 时间内到达的样本。数据流 的特点之一是要求实时性，因而后者更加适用于数据流挖掘。 应用滑动窗口对新近数据进行处理是一种普遍的做法。其主要的优势主 要有以下几点： ( 1 ) 语义清晰，便于理解：用户可以很容易理解在得到处理结果时究竟抛 弃了哪些数据。 ( 2 ) 明确性：不用为不适宜的选择所产生不理想的处理结果而担心。 ( 3 ) 重点在于最新近的数据：大部分的应用场合相对于历史数据而更注重 新近的数据。如果试图时刻分析清楚事务记录、电话呼叫记录、网络流量模 式、科学传感器数据的含义，那么针对最新近的数据进行分析将更加有助于 得到理想的处理结果。 2 4 概念漂移 2 4 1 概念漂移的基本特征 数据流的特点之一就是其数据的走向及分布将随着时间的流逝而不断变 化，这种分布不断变化的现象称为概念漂移【9 1 。过去大部分的经典数据挖掘 算法均假设数据的分布是固定不变的，然而几乎所有到达的数据流都不符合 这种假设，当数据不断流入时，其分布也就是概念随着时间的流逝是不断变 化的。这就给数据流挖掘带来了新的挑战，解决概念漂移的能力是衡量一个 数据流挖掘算法性能的重要指标。 如今大多解决概念漂移的算法都集中在两方面：概念漂移的检测以及漂 移的程度。 概念漂移的检测意思是关于监测到概念漂移发生具体时间的问题。 1 6 哈尔滨：l = 程大学硕+ 学位论文 对于预测型的情况，现在已经构建了一个模型，此后应用此模型对每个 新近的数据进行诊断和分类。若经过一段时间后能够判断出数据的确切属性， 此时可以对模型的处理结果进行分析并加以验证。当到达足够多的数据时， 就能够通过模型对数据预测准确率的变化程度来验证数据是否发生概念漂 移。若模型对最近收集的训练数据的预测准确率比模型先前的预测准确率有 了较大幅度的下降，则说明发生了概念漂移。 而在较短时间罩不能得到模型的处理结果( 例如描述型的模型) ，此时就 得引进可靠性估计( r e l i a b i l i t ye s t i m a t i o n ) 方式，来给每次的预测一个可信度权 值。因为每一次的处理结果有可能得不到，所以可依据可信度值的变化程度 验证数据流是否已经产生概念漂移。 最后，当在监测概念漂移以后，应考虑如何针对概念漂移加以处理。解 决概念漂移的方式大致有两类：模型