（计算机应用技术专业论文）数据流在线分类算法的研究与实现.pdf

_ i at k， _风_ 独创性l 声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 ： 思。 学位论文作者签名： 歹瘴 日 期： 。卯夕7 6 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文 的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或 部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： | 半年口一年豳一年半口两年口 学位论文作者签名： 歹毒 签字日期： 0 7 叼7 6 导师签名： 7 在乡 签字日期： 7 7 么 1 j j ? 东北大学硕士学位论文摘要 数据流在线分类算法的研究与实现 摘要 数据流挖掘是数据挖掘中的一个重要部分，相对于传统的静态数据，数据流连续、 单遍扫描、快速变化、海量无穷的特点使数据流的挖掘面临着新的挑战，因此静态数据 的分析技术已不适合于数据流分析，设计单遍扫描、实时、快速的算法是非常必要的。 作为数据流挖掘的重要组成部分，数据流分类研究也面临同样的问题，分类模型应用在 快速到来的数据流上，需要快速给出预测结果。并且实际应用中的数据流分布不是静止 不变的，因而为了适应数据分布的动态变化，分类模型必须做出相应的更新或重新训练 操作。 本文从概念漂移的检测及适应方面着手进行了研究。一方面，针对数据快速流入及 变化的特点，提出了基于聚类的分类方法，利用聚类方式将训练集中的数据以相同分布 聚类到相同的聚簇中，并基于每个簇训练单独的分类模型，当未知类别的新记录到来时， 用与其最接近的模型进行预测分类。同时在分类过程中采用更新机制维持算法总体分类 精确度，以及通过从误分类记录中启发式学习训练新分类器以适应概念漂移；另一方面， 研究了概念重复规律性出现的情况下，如何减少模型的更新以提高分类预测的速度及精 度，考虑实际应用中，数据流概念的数量的有限性，并且随着时间的推移，这些概念会 周期性重复出现，因此提出了充分利用历史概念的信息，利用己存在的分类模型对数据 流进行分类，进而提高分类的速度。 实验表明，本文提出的基于聚类的数据流分类方法在分类准确性和运行效率方面较 传统方法具有更大的优势，而对具有周期性概念漂移的数据流的分类算法在保证分类精 度的前提下，提高了在线分类工作的效率。 关键字：数据流；概念漂移；在线分类；聚类；周期性；历史概念 - t v 气 东北大学硕士学位论文a b s t r a _ c t s t u d ya n di m p l e m e n t a t i o no nd a t as t r e a m0 n l i n e c l a s s i 6 c a t i o n a 1 9 0 r i t h m a b s t r a c t d a t as t r e 锄m i n i n gh a sb e c o m ea ni m p o n 肌tp a r to fd a t am i n i n g ，c o m p 撕n gw i t ht h e 昀d i t i o n a ld a t am i n i n g ，t h ef e a t u r e so f c o n t i n u o u s ，s i n g l es c a n ，f 弧te v o l v i n g ，a n dp o t e n t i a l l y i n f i n i t ) ro fd a t as t i - e 锄c h a l l e n g et h em i n i n gw o r ko fs t r e 锄d a t 钆w h i c hm a k e ss o m eo ft h e t r a d i t i o n a lm i i l i n gt e c l l l l i q u e sd o n tm e e tt h er e q u i r e m e m s s o ，i t sl l i g h l yn e c e s s a r ) ，t od e s i g n s i n g l es c a n ，r e 出t i m e ，a n d 凤ta l g o r i t h m s a sa ni m p o r t 锄tp 砌o fd a t as t r e 锄m i n i n g ， c l a s s i f i c a t i o no fd a t as t r e 锄a l s of a c e st h es a n l ep r o b l e m s a st h ed a _ t as t r e a m so f 叩p l i c a t i o n s i nr e a l 、o r l dd on o tk e e ps t a b l e ，t h ec l a s s i 匆i n gm o d e lm u s tb eu p d a t e do rr e b u i l tt oa d 叩tt h e c h a n g i n go fs t r e a md 妇d i s t r i b u t i o n t h ep h e n o m e n o no fc h a n g ei nt h eu n d e r l y i n gc o n t e x to f d a t as n l e 锄t a k e st 1 1 ec h a n g e so f t a 略e tc o n c e p t i sr e f e r r e dt oa sc o n c e p td r i r t h i st h e s i sf o c u s e so nt h ed e t e c t i n ga 1 1 da d a p t i n gw o r ko fc o n c e p t 嘶ra p p e 撕n go nd a t a s t r e 锄s f o ro n ep a n ，f o rt h ef e a t u r e so ff 奴n o w i n gi i la i l dc h a n g i n go fd a t as t r e a m ，a c l a s s i f i c a t i o na l g o r i t h mb a s e do nc l u s t e r i n gh a sb e e np r o p o s e di nt m st h e s i st oi m p r o v et h e a c c u r a c yo fc l a s s i 匆i n gm o d e l 7 1 1 l e 打a i l l i n gd a t a s e ti sc l u s t e r e di n t od i f r e r e n tc l u s t e r sb a s i n g o nt l l e i rs i m i l 撕够a n dt h e nc l a s s i f i e r sa r et r a i n e d 仔o mt h e s sc l u s t e r s t h ec l a s s i f i e rh a st h e m o s ts i m i l 撕t yw i t ht h ec o m i n gr e c o r di s a s s i g i l e dw i t ht h ec l a s s i 匆i n gw o r k u p d a t i n g m e c h a n i s mi su s e dt om a i n t a i nt h et o t a lc l a s s i f i c a t i o na c c u r a c y ，a i l dah e u r i s t i cl e 觚l i n g m e t h o do ft r a i n i n gn e wc l a s s i 母i n gm o d e l sf r o mm i s c l a s s i f i e dr e c o r d si su s e dt o a d a p tt h e c o n c e p td r i r f o ra n o t h e rp a r t ，f o rt h es i t u a t i o no fp e r i o d i cr e c u l l r e n c eo fc o n c e p t ，at a r g e t e d a l g o r i t h mh a sb e e np r o p o s e di nt l l i st h e s i st or e d u c et h ec o s to fu p d a t i n gc l a s s i f y i n gm o d e l a 1 1 dq u i c k e nt h es p e e do fc l a s s i f i c a t i o n c o n s i d e r i n gt h a tt h ec o n c 印tn u m b e ro fd a 妇s t r e a m s o ft h er e a lw o r l d 印p l i c “o n si sl i m i t e da 1 1 d t 1 1 e s ec o n c e p t sc a nr e c i l r p e r i o d i c a l l y ，i nt h i s t h e s i s ，a i la l g o r i t l u l lo fm a k i n gf h l lu s eo ft h ei n f o 珊a t i o no f1 1 i s t o r i cc o n c e p ti sp r o p o s e df o r t h i sp a n i c u l a r 印p l i c a t i o n ，t h ec l a s s i 匆i n gm o d e l so ft h es 帅eh i s t o r i cc o n c e p ta r eu s e dt o c l a s s i 匆t h er e c u 丌e n td a t as t r e a mc o n c e p t t oq u i c k e nt h ec l a s s i 6 c a t i o na n dr e d u c et h em n n i n g t i m eo ft h eh o l ec l a s s i 匆i n gp r o c e d u r e e x p e r i m e n t ss h o wt h a t t h ec l a s s i 6 c “o na l g o r i t b a s e do nc l u s t e r i n gh a sab e t t e r p e b n n a n c eo nc l a s s i f y i n ga c c u r a c ya n dr u 肌i n gt i m et h a nt h et r a d i t i o n a lc l a s s i f i c a t i o n ，a n d i i i 东北大学硕士学位论文 a b s t r a c t t h ea l g o r i t f o rc o n c e p td r i f to fp e r i o d i cr e c u l l r e n c ei m p r o v e st h ee 街c i e n c yo fc l a s s i f y i n g 、o r k 谢t hl i t t l el o s so fa c c u r a c y k e y w o r d s ：d a t as t i i e 锄；c o n c e p td r i r ；o n l i n ec l a s s i f i c a t i o n ；c l u s t e r ；p e r i o d i c ；h i s t o r i cc o n c e p t i v 东北大学硕士学位论文 目 录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第l 章绪论l 1 1 数据流挖掘1 1 1 1 数据流的特点1 1 1 2 数据流处理模型的特点2 1 1 3 数据流挖掘的意义2 1 1 4 数据流上的应用3 1 2 概念漂移4 1 3 问题提出6 1 4 本文的研究内容8 1 5 本文的组织结构8 第2 章相关理论与技术9 2 1 数据流处理技术9 2 2 数据流挖掘方法1 0 2 2 1 频繁模式挖掘10 2 2 2 数据流聚类1 0 2 2 3 数据流分类1 1 2 3 数据流管理系统一l2 2 4 数据流分类的研究现状。1 4 2 4 1 增量学习方法1 4 2 4 2 系综学习方法1 5 2 4 3 其他分类方法15 2 4 4 存在的问题l6 2 5 本章小结17 第3 章基于聚类的数据流在线分类算法1 9 3 1 问题的提出19 3 1 1 当前算法存在的问题1 9 一v 东北大学硕士学位论文 目录 3 1 2 前提知识2 0 3 2c b c 算法概述21 3 3 离线过程2 2 3 3 1 数据预处理2 2 3 3 2 训练数据聚类2 3 3 3 - 3 子分类器训练2 4 3 3 4 离线过程算法2 4 3 4 在线过程2 5 3 4 1 在线预测2 5 3 4 2 分类器更新2 6 3 4 3 训练新的分类器2 7 3 5 概念漂移的检测2 8 3 5 1 误差变化率2 8 3 5 2 误分类速率2 9 3 6 基于聚类的动态数据流在线分类算法2 9 3 7 算法性能分析31 3 8 实验分析31 3 8 1 数据集3 1 3 8 2 参数说明3 3 3 8 3 基于距离聚类的有效性3 4 3 8 4 分类器更新与剪枝对算法性能的影响3 4 3 8 5 滑动窗口大小对算法性能的影响3 5 3 8 6 属性个数对算法性能的影响3 6 3 8 7 概念漂移的检测和适应3 7 3 8 8 总体性能4 0 3 9 本章小结4 1 第4 章具有周期性概念漂移的数据流的分类4 3 4 1 问题提出4 3 4 2 历史概念4 3 4 2 1 历史概念的定义4 3 4 2 2 概念的抽取及存储4 4 4 2 3 马尔科夫链模型描述概念转换4 5 v i ， 东 - 1 ， 东北大学硕士学位论文第l 章绪论 1 1 数据流挖掘 第1 章绪论 数据流挖掘( d a _ t as t r e 锄m i l l i n g ) ，是一种从连续不断的、快速的流数据中提取有用 的信息的过程，可以被看作是数据挖掘、机器学习与知识发现的分支领域，是最近几年 数据挖掘领域中的研究热剧啦，3 j 。 数据流( d a t as t r e 锄) ，是由一组有序序列的实例组成，并且通常只能被读取一次或者 由于有限的计算和存储空间只能被读取其中小部分内容。 随着计算机及数据库技术的快速发展，信息时代的各种应用为我们提供了大量的数 字数据，这些数据以一种不可预知的速度在不断地增长，使各领域的信息处于爆炸状态。 并且各种形式的应用所产生的数据，已不再局限于有限的静态的模式，而是海量的、时 间序列的、快速变化的和潜在无限的，如，商业信息系统、网络服务、电信提供商等， 它们每时每刻都在产生和存储新的数据，一个大学校园每分钟可以有1 7 4 0 0 次页面访问 请求，l y c o s 搜索引擎每天至少有5 0 0 0 0 0 次事务记录，m o o 每天能够发送上千万次访 问请求，等等，这些都是大数据量产生的实例。这些像金融数据、网络监控数据、传感 器网络、网页点击、卫星气象监测数据等新形式的数据被定义为数据流【4 】。传统的o l a p 和数据挖掘方法需要多遍扫描数据，因此对于流数据应用来说是不可行的，需要采用新 颖的算法实现不断流动着的数据的分析与挖掘【lj ，这种要求促使了数据流挖掘技术的产 生。 1 1 1 数据流的特点 通常，数据流上大量及潜在无限的数据是由实时监视系统、通信网络、i n t e m e t 传 输信息、金融市场或零售业的联机事务处理、电力供应网、a t m 交易、工业生产过程、 科学和工程试验、遥感器等其他动态环境产生。与传统的数据集不同，数据流以不同的 更新速率连续地流进流出计算机系统。这些数据具有按时间顺序的、实时的、快速变化 的、海量的和潜在无限的特点。具体地，数据流具有如下特点： ( 1 ) 有序性 数据流上记录的产生与到来，是有时间先后顺序的，这个顺序是无法控制的，一旦 产生，各条记录的相互顺序便固定不变。 ( 2 ) 实时性 数据流上的记录产生即到来，具有实时性。 1 ，r 【 东北大学硕士学位论文第l 章绪论 ( 3 ) 快速变化 由于产生数据流的潜在机制不是固定不变的，因此它所产生的数据的表现形式以及 数据所决定的类别范畴也都是不断变化的，在某一时刻前后的记录很有可能有着不同的 表现，并且在数据流上，我们无法判断这种变化的确切时刻。 ( 4 ) 海量潜在无限 数据的产生随着时间持续进行，很可能永久的进行下去，因此，这些数据是海量无 限的，不是有限存储空间就能够全部存储的。 1 1 2 数据流处理模型的特点 基于以上数据流的这些特点，对于数据流的处理系统也必须具有下列相应的性质才 能做好数据流的查询及其他处理工作： ( 1 ) 单遍扫描 由于数据流的实时性，只能对数据流上记录进行一次扫描与分析，而不能对其进行 重复扫描，除非用特定的存储空间将该记录存储起来，否则该记录将永久消失。 ( 2 ) 局部近似结果 由于是海量无限的我们无法存储数据流上所有的记录，因为它，因此处理系统只能 针对当前的局部数据作分析，并且由于数据流单遍扫描的特性，对数据的分析结果只能 是近似而非精确结果。 ( 3 ) 实时连续处理 数据流不停地流进流出，因此处理模型必须具有可持续的处理能力。 ( 4 ) 可适性 数据流处理模型还必须具有可变性，以适应不断变化的数据流。 1 1 3 数据流挖掘的意义 数据流上的数据挖掘具有非常重要的意义和实用价值。数据流中蕴含着大量潜在有 用的信息，如果将这些有用信息捕获将会对数据流的分析带来帮助，如从数据流中进行 实时监控、网络入侵检测、异常行为分析、分类预测、游离点检测、极端事件与欺 为的探测，通过数据流挖掘技术发现这些有用信息，为数据流未来事件做决策分析 帮助以减少异常等带来的损失。 数据流挖掘主要任务可分为查询、检测、预测。 ( 1 ) 查询 在数据流的实时查询中，分析用户的查询请求，实时返回查询结果，这种任务 2 东北大学硕士学位论文第l 章绪论 时响应要求非常高。如人事经理想要知道最近一个月内公司员工出勤率最高的是谁、最 近一周内都有谁按时上班、今天有谁迟到，或者市场调研员想要知道今天销售量最好的 商品是什么，针对这些查询请求，流查询系统需要能够快速从存储的概要信息中挖掘出 相应的信息，并汇总出结果返回给用户。处理查询的过程中需要用到的知识有频繁模式 挖掘【1 ，5 ，6 ，7 ，引，在线聚类【9 ，1 1 1 等。 ( 2 ) 检测 通过分析连续产生的数据流，数据流挖掘技术能够有效认识当前数据的状态，并做 出正确的分类。主要用于异常监测或概念漂移的识别中。如，在网络入侵检测中，对每 个网页请求能够及时分析其状态，正确区分出异常的请求行为，将其检测为入侵，或者 在信用卡欺骗检测中，能够及时分析每一笔交易信息，检测其是否是欺骗行为，等等。 在这些检测应用中，需要对数据流的状态进行实时分析，并且能够得出高精确度的结果， 以减少不必要的损失。 ( 3 ) 预测 数据流不断地产生，正常情况下，随着时间的推移，其分布能够呈现出一定的规律 性。对于这种数据流，挖掘并掌握其潜在规律，并利用该规律在已知当前数据流状态的 情况下，预测数据流将来的分布及状态，提供辅助决策以为适应该状态做提前准备。如 气候预测，一年四季或者一天内天气的变化都是有规律可循的，因此可通过分析数据流 上历史数据的状态信息，根据当前的气候状态来预测未来的气候状态，或者在股票市场 应用中，分析历史股票走势信息，来根据当前的状态预测今后的走势。在正常情况下， 根据历史规律预测未来状态的做法是可行的。 1 1 4 数据流上的应用 随着计算机技术的不断发展，如今已有很多应用领域的数据形式都以流形式存在， 而不再是一直不变的永久存放于数据库的静态数据。因此，应用数据流挖掘技术则可以 分析流数据的动态以掌握系统的状态，或者对数据流的趋势作提前预测。 ( 1 ) 传感器网络 传感器网络在多个领域都有应用，如环境的监测和保护、公路交通状况监控、医疗 护理、制造业流程监控等。通过分析实时监控数据，以掌握被检测环境的整体状态，以 及对异常情况的出现做出及时的响应。 ( 2 ) 网络流量及点击分析 在网络流量及网页点击流应用中，数据流挖掘技术主要用于监测网络流量、监控网 页的点击行为，发现网络入侵等不良行为，或者监测网络中分布式站点的状态，当某个 站点的流量超过负荷时，可以通过调用其它闲置的站点分担工作任务，从而使整个网络 气一 东北大学硕士学位论文第l 章绪论 处于平衡状态。 ( 3 ) 金融数据监控 流挖掘技术可以用于股票数据的在线分析，如可以分析多只股票的相关性、识别股 票价格走势、发现交易机会等，从而为股民提供辅助决策。 ( 4 ) 信用卡检测 在信用卡使用检测的应用中，主要目的是对每次信用卡的交易状况进行监控，用于 发现恶意的欺诈行为，且最主要的是提前预测欺诈行为的发生，这样为及时制止恶意行 为保证损失最小提供决策支持。 ( 5 ) 其他应用 如地球气候数据的监测及气候状态的预测，电力公司对某个区域某段时间用电情况 的掌握，网络分布式系统异常检测，等等，这些能够动态产生数据的应用里，都可以运 用数据流挖掘技术来进行实时监控或者趋势分析等工作。 1 2 概念漂移 概念漂移( c o n c e p td 打r ) ，是指在数据流挖掘中，数据流潜在的上下文的改变或多或 少会引起数据流目标概念统计信息的变化【l 2 ，1 1 ，12 1 ，同时，这种改变是以一种不可预知的 方式进行的。 在实际应用中，数据流的潜在分布，并不是始终保持一致不变，而是随着时间的推 移，这些数据可能会与之前的数据拥有不同分布，这种情况被称为概念漂移。 在数据流挖掘工作中，特别是分类工作中，概念漂移现象是不可避免的，一个数据 流在其存在过程中不可能只呈现出一种状态，肯定会受到周围环境变化的影响而表现出 不同的状态，如，一年中主要呈现出春暖、夏热、秋凉、冬冷四种不同的气候状态；网 络流量检测中，多数时间呈现出良好的状态，但偶尔也会有拥挤和空闲的状态；等，这 些都是概念漂移现象的实例。 概念漂移的出现，对数据流挖掘工作提出了新的挑战，尤其是分类工作，对数据流 的分类不再是只依靠单一的模型就能完成，而是需要逐步更新或学习全新的模型才能适 应数据流分布的变化，从而保证分类有较高的精确度。因此，分类器应该具有自动调整 功能，能自动检测概念漂移的发生，以及做出相应的动态调整来适应漂移，适应新的数 据分布。 在数据流处理过程中，概念漂移是需要重点考虑的问题，因此首先必须认识概念漂 移的种类，按照不同的分类标准，概念漂移有不同的分类结果。 ( 1 ) 突发漂移和缓慢发生漂移 按照漂移产生的速度，可以将概念漂移分为两种类型【12 1 ，一种是突发漂移( a b r u p t ， 4 东北大学硕士学位论文第1 章绪论 i n s t a n t a n e o u s ) ，另一种是缓慢漂移( g r a d u a l ) ，或者适中和慢速漂移两种【1 1 】。如突发的金 融危机，使得某公司经营状况从良好收支平衡状态突然转变成极度亏损状态，公司经营 状况的这种的转变是在短时间之内，是非正常经济规律所能解释的，这种情形便可以认 为是突发概念漂移，相反，公司的经营状况在正常时期，能够随着正常的经营业绩而发 生相应的变化，这种变化都可以认为是缓慢发生概念漂移。一般来讲，正常情况下的数 据流都能够发生缓慢的变化，突发漂移都是数据流正常的潜在变化规律收到外界不可预 知的突发的因素而引起的。如2 0 0 3 年非典期间，药店板蓝根的销售量激增；国际或国 内突发的政治事件，引起网络中相关网页的点击浏览数量激增；股票市场中某只股票的 买入卖出情况，由于某个有强大实力的公司的介入，而产生不可预料的变化；个人的信 用卡信誉额度，可能由于持卡者的突然失业或拥有一份好的工作而突然降低或者升高； 等等，这些都是突发概念漂移的例子。 ( 2 ) 虚假漂移和真实漂移 引发概念漂移的原因可能不仅是上下文潜在的改变，也有可能是潜在数据分布的改 变。有时数据表面分布发生变化，但目标概念却保持不变，这种情况下，也会引发分类 模型的更新工作。这种由于数据表面分布发生变化目标概念保持不变而引起模型更新工 作的情形，被定义为虚假概念漂移( v i n u a lc o n c e p td r i r ) 。相应的，真实漂移( t m ec o n c e p t 嘶r ) 是数据表面分布发生变化，并且目标概念也发生相应变化的情形。这种分类，是根 据产生模型更新的原因定义的。 ( 3 ) 采样漂移、概念偏移和概念漂移 采样漂移( s 锄p l i n gs l l i r ) 是指当数据分布发生改变但是目标概念保持不变的情况 下，也会引起当前模型的更新，l3 1 ，这同( 2 ) 中的虚假概念漂移相同。 概念偏移( c o n c e p ts h i r ) 是指概念转变速度很快，与( 1 ) 中的突发漂移相同，表示某一 时刻前后所代表的概念完全不同【1 3 ，i4 1 。 概念漂移( c o n c e p t 嘶r ) ，此处的概念漂移与前面常说的概念漂移不同，此分类中的 概念漂移只代表缓慢性发生概念转变的漂移，与( 1 ) 中的缓慢漂移概念相同。在这种漂移 中，可以认为当前数据流上的概念与即将出现的概念是相同或者相似的，即这两种概念 之间没有明显的分界点，概念的转化是在一段时间中完成的。 ( 4 ) 周期性与非周期性漂移 将数据流概念漂移与时间因素相关联，按照漂移在数据流中存在的形式，又可将数 据流概念漂移分为周期性i 】5 j 概念漂移与非周期性概念漂移。周期性概念漂移，意即在数 据流变化过程中相同的概念呈周期性重复出现，并且随着以前的变化趋势发生类似的概 念漂移，概念的状态可以预见，在这种类型的漂移中，概念的变化具有重复性，变化的 趋势亦具有相似性。气候的四季变化便是一个典型例证，每一年都是春夏秋冬四季交替 5 _ 东北大学硕士学位论文第l 章绪论 改变；工业生产在线监控中，产品的状态均是随着生产周期的进展而改变；工作日中每 天的道路交通情况都比较相近，分别在上班和下班时间路况进入拥挤状态；等等，这些 都是周期性的体现。与周期性相反，非周期性的概念漂移则没有周期重复性，没有一定 的规律可循，如一些异常的发生，这种概念漂移是不可预见的。 ( 5 ) 概念漂移的另一种分类 数据流上的概念即是一种分布状态【1 6 】，用概率的形式表达概念，则可认为是数据属 性x 与分类类别y 的联合分布，即尸( x ，y ) = 尸( j ，ix ) 尸( x ) 。使联合分布尸( y ，x ) 发生改 变的情况有以下几种： 1 ) 若保持尸( y ，x ) 不变，则只能满足尸( yx ) 与尸( x ) 都保持不变的情况，此时可认 为数据流上的概念是稳定的； 2 ) 若p ( x ) 变化而p ( yx ) 保持不变，由表达式可知，此时联合分布也会发生变化， 这种情况即上面提到过的虚假漂移或者采样漂移。 3 ) 尸( x ) 不变而p ( yx ) 变化，即数据属性的分布稳定不变，而其所决定的类别分布 却发生变化，当数据环境发生改变，相同的概念可能会代表不同的类别，如，拥有相同 信誉额度评价属性的记录可能在不同的国家有不同的划分结果，可能在比较发达的国家 内，其信誉额度处于中下，而在发展中国家中可能会处于中上。 4 ) 尸( x ) 和尸( 少ix ) 同时发生改变。现实生活中，观察到的变化都是x 和y 的联合概 率变化结果，很难断定是x 分布发生了变化，还是y 的条件概率分布发生了变化，但总 的来说能够通过某种度量手段来探测变化，如误差分析。 近些年在各种知名的国际会议上( 如s i g k d d ，s i g m o d ，v l d b 等) ，都有数据流 研究的专门讨论，有概念漂移的数据流的分类算法研究也越来越得到重视，并且取得了 很大的成效，其中增量学习方法和系综方法成为该领域的两个具有引导意义的学习方 法，均在适应概念漂移的工作中取得了良好的成绩，之后基于这两种方法的改进完善工 作以及新的算法被逐步提出来。 1 3 问题提出 数据流分类过程中遇到的问题有： ( 1 ) 数据流的状态不是稳定不变，而是动态变化随时发生概念漂移，因此，在分类 过程中必须对分类模型进行更新。 ( 2 ) 分类模型可能依赖某些潜在的隐藏因素，这些潜在隐藏因素共同影响着分类模 6 东北大学硕士学位论文第1 章绪论 型的行为。如，预测天气状况的行为会随着四季的不同而发生变化，季节的变化规律直 接影响着分类模型的行为，如果用预测春季天气的分类模型来预测冬天的天气，该模型 的准确率肯定不会很高，相反亦是如此。另外还有大众的消费模式也会随着时间变化而 变化，并且商品的自身质量、外在的经济环境、消费者本人的喜好程度以及其自身的经 济条件，等等，这些潜在因素也间接影响着消费模式的建立，当这些潜在影响因子发生 变化时，分类模型必须随之调整，才能反映出真正的消费情况，为商家提供准确的情报。 由于概念漂移的存在，对数据流的分类必须时刻考虑漂移，实时探测漂移并及时适 应漂移。而处理概念漂移的过程中一个重要的难点是区分噪音和真正的漂移。由此，需 要避免两个问题的出现：一是，过分关注噪音数据，引起模型的过分拟合，而将噪音数 据视为概念漂移；二是，为了避免受噪音数据影响，使模型过于稳定，以至于不能探测 概念漂移的发生，无法及时更新模型1 1 7 】。因此，一个理想的数据流分类模型必须既能够 对噪音健壮又能对真正的概念漂移敏感【l ，能够随着概念漂移的发生，及时调整模型， 使其可以反映新数据的分布情况。 然而，现有的方法在在分类变化数据流的过程中存在的问题有如下几点。 ( 1 ) 某些算法不能及时探测出概念漂移的发生，从而影响对数据流的变化所做出的 正确的调整，主要表现在，分类模型过于稳定无法探测出漂移的发生或者无法及时探测 出漂移的发生。 ( 2 ) 某些算法不能快速适应漂移，当能正确探测出漂移后，却没能采取及时恰当的 措施来更新或重新建立模型来适应数据流上新的概念，致使数据流分类精度降低。 ( 3 ) 为适应概念漂移追求较高分类精度而使运行效率降低。某些数据流分类器算法 为了取得较高的分类精度，而花费大量的运行时间在分类模型的不断更新和提高工作 上，使得整个算法的运行效率降低，不能实时得出分类结果。 ( 4 ) 为追求快速结果而损失分类精度，数据流处理中为适应快速流动的数据流采取 了一种折中方法是损失精确度获得时间上的实时响应。但在分类过程中，太低的精确度 也是不被允许的，因为，较低的分类精度可能会导致不可预知的损失和后果。 ( 5 ) 训练数据的获取问题，目前常用的获取途径是直接从数据流上在线获取，常采 用抽样方法，致使训练数据集的质量过分依赖于抽样的频率，若是高频率的抽样，会得 到过于局部的数据，若是长时间间隔的抽样，会导致获得的训练数据不能较好的描述一 段数据流。 总之，在数据流分类过程中，一个理想的分类系统，必须能够敏感探测出概念漂移 的发生，同时动态调整与更新模型以快速适应变化的概念。概念漂移的检测与适应成为 数据流分类了工作中研究的重点。 7 东北大学硕士学位论文第1 章绪论 1 4 本文的研究内容 跟随当前研究的足迹，本文亦对数据流分类做出了一些研究，提出了新的在线分类 算法，旨在提高分类精度。具体地： ( 1 ) 在保证实时响应的前提下，提高分类结果的精确度，同时能够敏感探测概念漂 移的发生，并且快速适应漂移能始终保证较高的分类精度。 ( 2 ) 同时，本文还关注了一种特殊情况的数据流，具有周期性概念漂移的数据流， 并针对这种特殊形式的数据流，提出了利用历史概念知识对重复出现的概念进行分类的 方法。在研究有概念漂移的数据流分类工作中，常用的方法是不断更新分类器模型或者 新建分类器模型来适应数据流上新的概念。然而在周期性概念漂移的数据流中，由于概 念周期性重复出现，这种每当发生漂移就更新或重新建立分类模型的做法就显得有点多 余，因为可以充分利用已有的成熟的知识来处理这些漂移，从而可以节省大部分模型更 新和建立的时间最终提高分类的效率。 1 5 本文的组织结构 根据上述研究内容，本文共分为5 部分。 第l 部分简单介绍了数据流挖掘的相关知识，指出了数据流的特点及其应用，并引 出概念漂移问题； 第2 部分阐述数据流挖掘领域中当前的相关理论与技术，以及指出这些技术中存在 的问题； 第3 部分详细描述本文提出的基于聚类技术的数据流在线分类方法，算法的实现， 以及与其他算法的实验比较； 第4 部分讨论一种特殊形式的数据流一具有周期性概念漂移的数据流，并针对这种 数据流提出有针对性的分类算法，同时证明所提出算法的可行性； 第5 部分总结本文，并提出相关讨论和工作展望。 8 东北大学硕士学位论文第2 章相关理论与技术 第2 章相关理论与技术 近几年来数据流挖掘技术已经成为挖掘领域的研究热点，由于数据流的特点，一些 传统的处理方法已经不能用于数据流处理中，必须设计新的算法来解决数据流挖掘过程 中面临的问题。本文将介绍数据流挖掘中的一些处理技术，以及针对数据流的挖掘方法， 如频繁模式挖掘、数据流聚类与分类，并介绍一些已有的数据流管理系统，以及数据流 分类工作中当前的研究动态。 2 1 数据流处理技术 由于数据流的新特性，为了有效处理数据流，需要建立新的数据结构、技术和算法。 由于我们不能用合适的存储空间存储流上所有的数据记录，这就需要在处理的过程中在 正确性欲存储空间之间进行平衡，通常的解决办法是牺牲精确度来降低对存储空间的要 求以及处理速度的需求。 在处理过程中常用到的方法是大纲( s y n o p s e s ) ，该方法只是提供比真实数据量小的多 的概要描述，它为查询提供近似结果。常用的大纲技术有如下几种【1 】： ( 1 ) 随机抽样 随机抽取数据流上某个长度的数据记录，而非整个数据流数据。如一种被称作水库 抽样( r e s e r v o i rs 锄p l i n g ) 的技术，对数据流数据进行无放回抽样，随机抽取s 数量的样本 并随机保持s 大小，当有新数据到来时，样本集中每个旧样本都有被新数据替代的可能。 这样就一直保持水库中s 个候选集合随时成为数据流数据的随机样本，具有实时性。 ( 2 ) 滑动窗口 不同于随机抽样，滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 对数据流上最近特定数量的 所有数据进行分析。基本思想是：仅基于最近的数据做出决策，在每个时刻t ，始终维 护一个保存当前w 条记录的窗口，作为分析的基础。当有新数据到来时，窗口中距当 前最“旧”的数据被新数据替换。这种滑动窗口模型对只关注数据流上当前最近的事件的 应用很有帮助，如股票分析。 ( 3 ) 直方图 这是一种大纲数据结构，可用来近似描述数据流中记录值的频率分布。它将数据划 分成一系列相邻的桶( 等宽或等深) ，然后统计每个桶内的频率计数，这样便可以产生近 似的查询回答。 ( 4 ) 小波 小波是一种信号处理技术，在数据流环境下，可用来构建输入信号的多分辨率层次 9 东北大学硕士学位论文第2 章相关理论与技术 结构。给定一个输入信号，我们希望用简单的正交基函数分解或重写它。对于查询优化， 小波已用作直方图的近似，且基于小波的直方图可以随时动态维护。因此，小波是一种 流行的数据流压缩的多分辨率方法。 ( 5 ) 梗概 梗概( s k e t c h ) 是指使用随机映射将数据流投射在一个小的存储空间内作为整个数据 流的概要，这个小空间存储的概要数据被称为略图，可用于近似回答特定的查询。 2 2 数据流挖掘方法 2 2 1 频繁模式挖掘 频繁模式的挖掘主要目的是对数据进行概括性的描述。在静态数据集中，频繁模式 的挖掘主要基于频繁模式的反单调性：若一个模式不是频繁的，则其所有超集都不是频 繁的；若一个模式是频繁的，则其所有子集也均是频繁的。基于这种思想，出现了许多 经典的频繁模式挖掘算法，例如a 研o r i 【5 1 ，f p g r o 嘶h 【6 】a c l o s e ( 基于a p r i o r i ) 【7 1 ， c l o s e t 【1 8 】，c h a i 洲【8 1 ，等。然而这些算法均是针对静态数据集而设计，因此不能在 数据流环境下进行增量更新。 与静态数据集挖掘相比，数据流需要更多的信息和更复杂的处理机制，频繁项集会 随时间变化，之前不频繁的项可能会变的频繁，因此，在这种情况下如果完全忽略不频 繁项则可能造成不可预知的损失。 为克服以上困难，可使用两种可能的方法，一种是仅保持一个余弦确定的想活项集 的有限集，一种是推导出答案的一个近似解集，后一种方法较常用。如，j hc h a n g 和w s l e e 在【1 9 】中提出了一种面向数据流的频繁模式挖掘算法，该方法对旧事物用遗忘因子来 减少其在当前频繁模式中所起的作用，当新事物流入时便更新事务子集中每个项集的频 繁计数，旧事务便乘以遗忘因子再加上新计数以作为该事务的最终频度。另外，c h 打s g i 锄e l l a 等在n s f 0 3 中提出了名为f p s t r e a m 的频繁模式挖掘算法【2 0 】，该算法采用倾 斜时间窗口技术来解决数据流时间敏感问题，算法过程中维护两个结构，一个是存储于 内存中用来捕捉数据流中最频繁和次频繁事务集信息的f p t r e e 结构，另一个为每个频 繁模式建立的倾斜时间窗口( t i l t e d t i m ew i n d o w ) 表结构，当数据流流入时，算法实时构 建、维护并更新f p s t r e 锄结构。 2 2 2 数据流聚类 目前存在的大量的聚类算法，可以分为划分方法( p a n i t i o n i n gm e t h o d ) ，层次方法 ( h i e r