（计算机应用技术专业论文）基于衰减窗口与剪枝维度树的实时数据流聚类研究.pdf

武汉科技大学 硕士学位论文第1 页 摘要 实时数据流挖掘是目前数据挖掘与数据库领域的新兴研究热点，针对实时数据流的 聚类分析技术也是该研究中最具有挑战性的难题之一。本文首先介绍了基于实时数据流 的数据挖掘和知识发现的研究背景以及该领域现有的主要研究分支：聚类、分类、频繁 模式挖掘、关联规则分析等。然后综述了实时数据流聚类技术的最新研究进展，在介绍 实时数据流聚类相关理论和常用技术的基础上，对现有各种代表性实时数据流聚类算法 的优势和不足进行了系统地分析，从处理速度、聚类形状、演化分析、高维性能及噪声 健壮性五个方面对这些聚类算法的性能进行了深入地比较研究，探讨了基于聚类的实时 数据流演化分析方法及其局限性。 针对现有实时数据流聚类算法存在的处理速度慢、系统消耗大以及不能识别任意形 状聚类等问题，本文设计并实现了一种基于衰减窗口与密度维度树的实时数据流聚类算 法p d s 仃e 锄，该算法首先对数据空间进行网格划分，将数据流依次映射到网格空间中， 采用一种改进的维度树结构在线维护和更新数据流的概要数据结构，同时设计了一种周 期性剪枝策略，周期性地剪去维度树中的稀疏网格，以降低系统消耗，最后采用深度优 先搜索算法在线处理聚类请求，通过不同时刻的聚类结果比对来实现数据流的演化分析。 基于人工数据集和真实数据集的实验表明，本研究所提出的聚类算法p d s 仃e 锄可 以有效地发现实时数据流在任意时刻具有任意形状的聚类，并且聚类效果较好、内存消 耗少、处理速度快，具有较好的计算精度。 关键词：数据流挖掘；聚类分析；衰减窗口；密度维度树；剪枝策略 第1 i 页武汉科技大学硕士学位论文 a b s t r a c t m i n i n gr e a l - t i m ed a t as t r e a mi san o v e lr e s e a r c hh o t s p o ti nt h ef i e l do fd a t am i n i n ga n d d a t a b a s e t e c h n i q u eo fc l u s t e r i n ga n a l y s i sb a s e do nr e a l t i m ed a t as t r e a mi so n eo ft h em o s t c h a l l e n g i n gp r o b l e m si nt h i sr e s e a r c hf i e l d i nt h i st h e s i s ，r e s e a r c hb a c k g r o u n da n dm a i n r e s e a r c hb r a n c h e si nt h i sr e s e a r c h , f o re x a m p l e ，c l u s t e r i n g ，c l a s s i f i c a t i o n ，f r e q u e n c yi t e m m i n i n ga n da s s o c i a t i o nr u l e sa n a l y s i s ，a r ei n t r o d u c e df i r s t l y t h en e w e s td e v e l o p m e n to f r e a l - t i m ed a t as t r e a mc l u s t e r i n gr e s e a r c hi so v e r v i e w e d i ti n t r o d u c e si n t e r r e l a t e dt h e o r ya n d c o n l n l o nt e c h n i q u e so fr e a l - t i m ed a t as t r e a mc l u s t e r i n g t h e ns t r e n g t h sa n dw e a k n e s s e so f d i f f e r e n t k i n dr e p r e s e n t a t i o n a la l g o r i t h m sa r ea n a l y z e ds y s t e m a t i c a l l y p e r f o r m a n c e so ft h e s e a l g o r i t h m sa r ec o m p a r e ds u b s e q u e n t l yi n f i v ea s p e c t s ：e x e c u t i o ns p e e d ，s h a p eo fc l u s t e r , e v o l v i n ga n a l y s i s ，h i g h - d i m e n s i o na n dh a l e n e s so fn o i s e d a t as t r e a me v o l v i n ga n a l y s i sb a s e d o nc l u s t e r i n ga n di t sl i m i t a t i o n sa r ep r e s e n t e d i no r d e rt os o l v es o m ep r o b l e m so fp r e s e n ta l g o r i t h m s ，s u c ha sl o w p r o c e s s i n gs p e e d ，h i g h s y s t e mc o n s u m p t i o na n dd i s a b l e dt oa r b i t r a r yc l u s t e rs h a p e ，an o v e lr e a l t i m ed a t as t r e a m c l u s t e r i n ga l g o r i t h m ，c a l l e dp d s t r e a m ，i sp r o p o s e di n t h i st h e s i s p d s t r e a mi sb a s e do n d a m p e dw i n d o wa n dd e n s i t yd i m e n s i o nt r e e p d s t r e a mf i r s t l yd i v i d e sd a t as p a c ei n t o 鲥d s a n dm a p sa l lt h ed a t ap o i n t si n t ot h e 舀r ds p a c eo r d e r l y , a n dt h e na ni m p r o v e dd i m e n s i o nt r e e s t r u c t u r ei su s e dt om a i n t a i na n du p d a t et h es y n o p s i sd a t as t r u c t u r eo fd a t as t r e a m ap e r i o d i c a l p r u n i n gs t r a t e g yi sd e s i g n e dt op r u n et h es p a r s eg r i d si nd i m e n s i o nt r e ep e r i o d i c a l l y f i n a l l y t h ed e p t hf i r s ts e a r c hm e t h o di su s e dt od e a lw i t ho n l i n e c l u s t e r i n gr e q u e s t t h r o u g h c o m p a r i n gc l u s t e r i n gr e s u l t so fd i f f e r e n tt i m ei m p l e m e n t st h ed a t as t r e a me v o l v i n ga n a l y s i s t h ee x p e r i m e n t a lr e s u l t sb a s e do ns y n t h e t i cd a t a s e ta n dr e a ld a t a s e td e m o n s t r a t et h a tt h e p r o p o s e da l g o r i t h mp d s t r e a mc a ne f f e c t i v e l yd i s c o v e rc l u s t e r so fa r b i t r a r ys h a p ei nd a t a s t r e a ma ta n yt i m e p d s t r e a mh a st h ea d v a n t a g e so fe x c e l l e n tc l u s t e r i n gr e s u l t s ，l o wm e m o r y c o n s u m p t i o n ，h i 曲p r o c e s s i n gs p e e da n dp r e f e r a b l ep r e c i s i o n k e y w o r d s ：m i n i n gd a t as t r e a m ；c l u s t e r i n ga n a l y s i s ；d a m p e dw i n d o w ；d e n s i t yd i m e n s i o n t r e e ；p r u n i n gs t r a t e g y 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文储签名：簟日期攀：竺：y 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对外服务。 论文作者签名： 指导教师签名： 日 乞笠垃幻百一也基 武汉科技大学 硕士学位论文第1 页 1 1 问题提出的背景及意义 第一章绪论 传统的数据库系统( d a t 扭a s es y s t e l i l ，d b s ) 、数据仓库( d a t aw a r e h o u s e ，d w ) 以 及数据集市( d a t am m ) 通常用来存储没有时间概念的相对静止的数据，基于这种静态 数据集合的数据挖掘与知识发现已被研究多年，相关的技术也同趋成熟。 近年来，随着数据采集技术和网络技术的飞速发展，特别是移动通信设备和无线传 感网络得到了深入地研究和广泛地应用，在一些新的应用领域中，信息以数据序列的形 式出现【i 】：电信公司每天产生的实时电话记录流、i i l t e n l e t 上w e b 用户的点击流、网络监 测中的数据包、工厂自动化控制中产生的控制信息流、各类传感器网络中的通信数据流、 金融领域的证券数据流、零售业务中的交易数据流、航天卫星向地面接收站发回的实时 数据流等形成了一种与传统数据库中静态数据不同的数据形态，这种新的数据形态被称 之为实时数据流( r e mt i m ed a t as 仃e 锄) ，广泛出现于电信、互联网、金融、航天、工 业等各个领域。这些实时数据流一般具有数据量无穷、数据有严格的先后顺序、数据概 念随时间快速变化、富含噪声等显著特点。 由于实时数据流具有以上这些新的特性，对数据流相关领域的研究以及实际工程应 用都提出了新的难题。一方面，实际应用领域需要对海量实时数据流进行在线的、持续 的、快速的处理，这些特点和要求已经远远超出了传统数据库系统d b s 的解决能力；另 一方面，实时数据流中隐藏着丰富的知识和信息，但是这种新的数据形态给基于实时数 据流的数据挖掘和知识发现带来了极大的挑战，如何及时有效地从实时数据流中挖掘出 有用的知识和规则用于指导生产实践以及决策支持，具有非常重要的研究价值和实践意 义。目前，基于实时数据流模型的数据挖掘技术的研究己成为重要的研究热点课题【2 】， 引起了国内外研究者的广泛关注。 1 2 国内外研究现状 基于实时数据流的数据挖掘的研究最早可以追溯至1 9 9 9 年，h e n z i n g e r 等人在其论 文1 3 】“c o m p m i n go nd m as t r e 锄s 中首次将数据流作为一种新的数据处理模型提出来， 此后，数据流开始作为一个新的研究方向出现在数据挖掘与数据库领域的几大顶级国际 会议中，如v l d b 、s i g m o d 、s i g l d 、i c d e 、i c d m 等会议每年都有几篇有关数据 流处理的文章，由于数据流这一概念刚出现不久，在这一时期对数据流的研究尚未得到 广泛的关注。 在此后的一段时间内，实时数据流作为一种新的数据形态慢慢的开始引起了数据库 和数据挖掘领域的学者极大的兴趣，同时也开始得到了广泛的关注。这一时期比较显著 第2 页武汉科技大学 硕士学位论文 的阶段性研究成果就是有学者根据实时数据流的新特性提出了一种与传统的数据库管理 系统d b m s ( d a t ab a s em a n a g e m e n ts y s t e m ) 相对应的数据流管理系统d s m s t 4 】( d a t a s t r e a mm a n a g e m e n ts y s t e m ) 。如图1 1 所示，在传统的d b m s 中，数据库或数据仓库中 存储的是有固定的关系结构、长时间静态并可随机访问的数据，由用户( 程序) 通过d m l ( d a t am a n i p u l a t i o nl a n g u a g e ) 语言提交查询请求，返回精确的查询结果；而在d s m s 系统中，如图1 2 所示，存储的是半结构化的、与时间有关并只能按顺序访问的海量数 据流，数据流处理系统实时的维护一个数据流的摘要信息，当用户( 程序) 提出查询请 求时，系统快速地返回一个近似结果。 m 图1 1 数据库管理系统d b m s 体系结构图1 2 数据流管理系统d s m s 体系结构 自从d s m s 系统这一概念提出以后，国外研究者开始对实时数据流进行了深入地研 究，从研究的内容上大致可分为两个方面：( 1 ) 数据流管理系统d s m s 的设计与构建。 建立数据流管理系统d s m s 方面的研究主要集中在数据流查询。已有多个研究机构进行 了d s m s 的研究，并构建出一些原型系统，如s t r e a m 1 1 ，t e l e g r a p h c q t 5 】及a u r o r a 6 1 等。( 2 ) 数据流挖掘。数据流挖掘方面的研究主要包括多数据流挖掘和单数据流挖掘， 单数据流与多数据流的区别在于挖掘的对象是一条单个的数据流或者同时处理多条数据 流。目前已有学者提出了一些数据流挖掘算法，并设计和丌发出数据流挖掘原型系统。 如美国伊利诺伊大学香槟分校( u i u c ，u r b a n a c h a m p a i g n ) 的m a i d s 7 】( m i n i n g a l a r m i n g i n c i d e n t sf r o md a t as t r e a m s ) 就是一个集查询、聚类、分类、频繁项集挖掘，以及处理结 果可视化五大功能为一体的数据流挖掘系统。本文主要研究和探讨的是实时数据流挖掘。 在国外，实时数据流挖掘方面有两个比较有影响的研究小组，一个是斯坦福s t a n f o r d 大学的r m o t w a n i 教授领导的研究小组，他们主要侧重于数据流管理、数据流的连续查 询以及数据流的聚类研究，提出量不同于d b m s 的d s m s 系统，其研究得到了美国国 家自然科学基金的资助；另一个是u i u c 的c a g g a r w a l 教授和韩家炜教授领导的研究小 组，他们的研究主要侧重于数据流分析，在数据流的在线分析、聚类、分类、频繁项集 挖掘以及数据流可视化等方面做了相关的研究工作，他们的研究也得到了美国军方和国 家自然科学基金的资助。国内有关这一领域的研究起步比较晚，从2 0 0 4 年开始，有关数 据流挖掘研究的文章才开始出现，其中又以复旦大学的周傲英教授、中山大学的印鉴教 武汉科技大学硕士学位论文第3 页 授、哈尔滨工业大学的李建中教授及东南大学的孙志挥教授等人各自领导的研究小组的 研究比较活跃。 1 3 本文的主要工作 本文的主要研究内容为实时数据流聚类问题的求解，目前国内外已经有很多科学家 在这个方面做出了许多努力。如前所述，由于实时数据流具有数据量巨大、时序性、快 速变化、潜在无限、高维性等特点，使得基于实时数据流的聚类问题远不止传统的聚类 方法那么简单，传统的聚类技术也就无法直接应用于实时数据流。本文的工作也将围绕 该技术展开，所做的主要研究工作如下： 1 ) 深入调研和研究现有的实时数据流聚类算法以及该类算法中常用的各种处理技 术，从处理速度、聚类形状、演化分析、高维性能及噪声健壮性五个方面对算法的性能 进行了深入地比较研究，同时研究了基于聚类的实时数据流演化分析方法及其局限性； 2 ) 由于目前的许多高效近似求解算法在实际应用中存在着不足，主要弊端是真实数 据流中隐藏的聚类大多数为非球状、甚至是非凸形状的，而这些算法聚类结果多趋于球 形，无法识别数据流中任意形状的聚类；当该类算法面对海量的、高速的真实数据流时， 往往出现数据处理效率急剧下滑、系统资源消耗呈几何级数递增的现象，严重的影响了 数据流处理效率和聚类的精度。因此，针对真实数据流处理系统的实际应用需求，本文 在传统网格数据聚类技术的基础上，引入衰减技术和剪枝维度树结构，并且基于这种新 颖的数据流内存维护模式，提出一种周期性的剪枝策略，以进一步适应大数据量、高流 速的实时数据流，形成了一个新的实时数据流聚类算法p d s t r e a m ； 3 ) 首先将本研究提出的p d s t r e a m 算法用于两种二维的人工数据流，较成功地识别 出了不同流速和数据量的数据流中隐藏的任意形状的聚类；在人工数据流中对p d s t r e a m 算法的数据流演化分析性能进行了实验研究；然后，针对数据挖掘领域常用的真实数据 集f o r e s t c o r e r t y p e ，在相同的条件下将p d s t r e a m 算法与现有算法进行了对比实验，实 验结果表明在大多数情况下p d s t r e a m 算法的聚类精度都明显高于c l u s t r e a m 算法；最后， 研究了周期性剪枝策略的效果，及其对于密度维度树规模的影响。 1 4 本文的结构安排 本文分为六章，各章内容组织如下： 第一章简要的介绍了实时数据流挖掘的研究背景及意义、分析了国内外在该领域 的研究现状，并介绍了本文的主要工作及结构安排。 第二章介绍了实时数据流挖掘的相关基本知识，主要包括实时数据流模型以及基 于该模型下的四个主要研究分支：实时数据流聚类、实时数据流分类、实 时数据流频繁模式挖掘和实时数据流关联规则分析，同时，简要介绍了一 些数据流原型应用系统的研究现状。 第4 页武汉科技大学硕士学位论文 第三章介绍了实时数据流环境下聚类技术的发展与演变。首先综述了实时数据流 聚类技术的最新研究进展，从处理速度、聚类形状、演化分析能力、高维 性能及噪声健壮性五个方面对现有主要算法的性能进行了深入地比较研 究，探讨了基于聚类的实时数据流演化分析方法及其局限性。 第四章从五个方面介绍本研究所提出的实时数据流聚类算法p d s 仃e 锄，首先给出 基本的概念和定义；然后介绍该算法的基本框架；提出一种改进的维度树 结构用以维护和更新数据流的摘要信息；给出本文提出的一种周期性的剪 枝策略；最后介绍算法如何响应用户的在线聚类请求。 第五章将p d s t r e 锄算法应用于二维人工数据流以及真实高维数据流，主要进行了 五个实验：第一，针对二维小数据量的数据流进行聚类；第二，针对二维 大数据流的数据流进行实验；第三，p d s 舵锄算法对二维实时数据流的演 化分析性能；第四，针对高维真实数据流的聚类；最后，测试周期性剪枝 策略的效果。 第六章总结了本文的工作创新点及不足之处，并对将来的研究内容做出了展望。 武汉科技大学硕士学位论文第5 页 第二章实时数据流挖掘与知识发现 2 1 实时数据流的基本概念 实时数据流是一个有序的数据点序列：五，置，以，整个数据流对应于一个由 小到大的时间序列互，乃o - o 互，表示数据点五在z 时刻到达，也就是规定了当乃 乃 时，对应的数据点正比数据点x ，先到达。每一个数据点五都是一个d 维向量，记作 置= ( 爿，# ，) ，其中，彳( 1 - ，d ) 分别代表数据点置的d 个属性值。 实时数据流作为一种新的数据形态和数据处理模型，它具有许多传统的数据库或者 数据仓库中的数据不具备新的特性。传统的关系型数据库以及数据仓库一般存储的是没 有时间概念的、相对静止的数据，而实时数据流具有连续、近似无限、时变、有序及快 速流动等特性，且实时数据流中数据点的出现顺序、速率、时刻均不可控制【8 】。具体来 讲具有如下特点： 1 ) 数据量巨大( m a s s i v e ) 。实时数据流一般具有海量的数据，例如，我国“嫦娥一 号”探月卫星在正常的绕月探测过程中，向地面接收站发送的月球图像等数据流 每秒3 m ，一年的数据量可达2 8 t b ； 2 ) 时序性( t e m p o r a l l yo r d e r e d ) 。在数据流模型提出之初，就规定了当乃 正时， 数据点x ，比数据点x ，先到达，数据点之间存在严格的先后顺序： 3 ) 快速变化( v a r yr a p i d l y ) 。由于数据流的单向流动性，当前时间段内的数据流所 表达的概念与下一时间段的数据流所表达的概念可能会截然不同，这种现象称之 为数据流的概念漂移( c o n c e p td r i f t ) ，这样的数据流也称之为进化数据流 ( e v o l v i n gd a t as t r e a m ) ； 4 ) 潜在无限( p o t e n t i a l l yi n f i n i t e ) 。从理论上讲，数据流永远没有终止的时刻，具 有无限性，所以说它是潜在无限的； 5 l 高维性( h i g hd i m e n s i o n a l ) 。现实世界中的真实数据流往往都具有高维的特性， 且数据流一般同时具有连续属性和离散属性，数据流天生就是高维的【9 j ； 6 ) 存储限制( m e m o r yr e s t r i c t ) 。数据流的数据量十分庞大，具有潜在无限的特性， 不可能像传统的数据仓库一样将数据全部存储起来，再进行挖掘，挖掘算法在运 行的空间上是受到限制的； 7 1 时间限制( t i m er e s t r i c t ) 。多数实时数据流挖掘系统要求具备很短的响应时间， 能够提供随时( a n y t i m e ) 的用户请求，所以数据流挖掘是个连续在线的过程， 第6 页武汉科技大学硕士学位论文 要求处理的速度快； 8 ) 单边扫描或者有限次扫描( o n c es c a n ) 。算法在对数据流进行处理时，只允许按 照数据点流入的先后顺序逐个处理，回头去重新扫描前面的数据点是不允许的。 由于如上所描述的数据流的特点，使得传统的数据挖掘技术无法直接应用在实时数 据流上，必须研究和开发出适合数据流模型的算法，流式数据挖掘给数据挖掘界带来了 一个全新的课题与极大的挑战，引起了数据挖掘界和数据库领域学者极大的兴趣，在实 时数据流查询、实时数据流挖掘等领域展开了广泛的研究。本章主要从实时数据流挖掘 的角度分析和讨论相关的研究分支，目前在实时数据流挖掘上进行的主要研究包括有： 数据流聚类分析、数据流分类、数据流频繁模式挖掘、数据流的关联规则分析等。 2 2 实时数据流聚类 聚类( c l u s t e r i n g ) 就是按照一定的要求和规律对事物进行区分和分类的过程。在这一 过程中没有任何关于类别的先验知识，也没有教师的指导，仅靠事物间的相似性作为类 属划分的准则，属于无监督学习的范畴。对聚类问题有如下定义：对于一个给定的数据 点集合，把相似的数据点划分在一起，形成一个或多个组，相似性的度量采用某种距离 函数，使得聚类簇内的数据点具有较高的相似度，簇l 日j 的数据点具有较低的相似度。 传统的聚类分析技术已经被广泛研究了许多年，在数据挖掘领域已经存在许多用于 聚类静态数据的聚类算法，诸如基于划分的方法、基于层次的方法、基于密度的方法、 基于网格的方法等，由于数据流具有与常规的静态数据不同的特点，需要研究者提出适 合数据流模型的、内存受限的、处理时间有限的单遍数据流扫描的聚类算法。数据流对 在其上进行聚类的算法提出了如下要求【l o 】： 1 ) 聚类簇数事先未知。算法不可能预先知道数据流将会被聚类成为几个聚类簇，不 但如此，在数据流环境下，随着数据的不断流入，聚类簇的数目在动态的改变； 2 1 聚类形状任意。这对数据流聚类来说至关重要，例如，在网络监控环境中，连接 的分布一般是不规则的，这也表明，传统的基于欧式距离的相似度准则多数产生 球形的聚类结构，对数据流的任意形状聚类簇效果不好； 3 ) 对孤立点的分析能力。由于数据流在不断流动和进化( e v o l v i n g ) ，在当前时刻被 认为是孤立点的数据点，有可能在后续一系列数据点到达之后变成一个新的聚类 簇，当然也有可能仍然是一个孤立点而存在，聚类算法必须要能够实时的监控数 据流的变化情况。 实时数据流聚类的形式化描述如下：设d s = x i ，x 2 ，正，) 表示数据流，各个数 据点到达的时间戳分别是墨，互，瓦，每个数据点五= ( 爿，# ，# ) ，其中 0 ( 1 ，sd ) 是x ，在第，个特征上的赋值，数据流聚类分析就是把数据流d s 中当前时间 窗口( 实时数据流挖掘中常用“时间窗口”这一概念，其实质就是某个预先指定长度的 武汉科技大学硕士学位论文第7 页 特定时间段) 霉- 瓦，乙】内的刀- h + 1 个数据点，按照该数据点与已有聚类簇间的远近关 系以及约束条件，逐个加入到由前面j i l - 1 个数据点所形成的聚类结构c f , 一。中，形成新的 聚类结构c 巧。 在c 只中，已经流入的刀个数据点被划分成七个不相交的模式子集s = s i ，足，墨， 满足如下条件： s ，inu$2，u：-g(ulsks s f ，2 j 三七，i j ) ( 2 1 ) i fn ，= g ( 1 f ，七，) 卜“7 数据点彳_ ，刀) 对子集墨( 1 f 七) 的隶属关系可用隶属函数【1 1 1 表示为 c 耻- 拦蜀 亿2 ， m 肚= i o ，1 ) ，嘞= 1 ，v j ；o 嘞 刀，v i ( 2 3 ) 其中，隶属函数必须满足条件嘞e m 砧，也就是要求每一个数据点能且只能隶属于 某一个聚类簇，同时要求已经存在的聚类簇是非空的。对于后续的数据点，采用相同的 方式增量地聚类到前面已经存在的聚类结构中。现有实时数据流聚类技术及相关算法的 详细情况将在第三章进行介绍和比较分析。 2 3 实时数据流分类 数据分类是主要分为两个过程，即分类器或模型的构造( 其中，模型是基于训练数 据集标记了类别的元组构造) 和分类器或模型的使用( 其中，模型用于预测新数据集中 元组的类标号) 。在传统的环境下，训练数据一般驻留在一个相对静止的数据库中，许多 分类方法允许扫描训练数据很多次，所以说，分类器构造的第一步就是典型的脱机批处 理过程。然而，在实时数据流环境下没有脱机阶段，数据流的特点也决定了存储和多次 扫描是不可行的，由此可见，传统的分类方法完全不适合实时数据流环境。 以传统的决策树分类技术为例，一般都遵循自顶向下的递归策略，只是用于选择最 佳分裂属性的统计度量不同。决策树由内部节点、分支节点及叶子节点组成，属性选择 度量用来选择当前节点的分裂属性，该属性是按类最好的区分训练元组的属性，分类属 性的每个可能值都产生一个分支，训练元组也据此来划分，并在每个分支递归地重复这 一过程。但是在数据流环境下，既不可能收集完整的数据集、也不可能实现重复扫描数 据，因此，该类方法需要重新考虑【l2 j 【1 4 】，此外，前文提到的概念漂移也使得建立起来的 分类器应该是随时间而改变的。 第8 页武汉科技大学硕士学位论文 为了解决这些问题而实现数据流的分类，目前已有学者进行了相关的研究【1 5 】【2 1 1 ，并 提出一些可行的解决办法。主要的算法分为如下几类：h o e f f d i n g 树算法【1 5 】、快速决策树 【16 1 ( v e r yf a s td e c i s i o nt r e e v f d t ) 、概念自适应快速决策树【1 7 1 ( c o n c e p t a d a p t i n g v e r y f a s td e c i s i o nt r e e ，c v f d t ) 、分类器系综【1 8 】( 使用投票方法考虑多个分类器) 。 ( 1 ) h o e f f d i n g 树算法 该算法的主要思想是“小样本通常足以选择最佳分裂属性 ，其核心理论为概率论中 的切尔诺夫不等式( h o e f f d i n g 界) ，假设变量，范围为r ，观察甩个样本后，样本观测平 均值为，则样本真值以1 一万的概率保证至少为，一占，其中， r 2l n ( 1 8 ) 弘1 丁 ( 2 4 ) h o e f f d i n g 树算法就是以这样的高概率确定在一个节点选择分裂属性时需要的样本 的最小数量，l ，该属性将与使用无限样本得到的属性一样，接下来的工作就与传统决策 树的构建类似。切尔诺夫界一个非常重要的特性是它和样本分布是独立的，对于数据流 来说，这正是所希望实现的，因为不太可能看到信息增益的概率分布，或者使用哪种其 他的属性选择度量。此外，h o e f f d i n g 树的另一个优点在于不会对同一数据进行多次扫描， 这一点对于数据流环境是很重要的，因为数据流经常会变得太大，无法存储，而且， h o e f f d i n g 树算法是增量的，即随着新的样例不断流入，可以增量的将新样例并入树中， 即使树正在构造，也可以用它对数据分类，树会持续增长，并且随着更多训练数据流入 变得更加准确。 但是，由于树型结构本身的复杂性，算法会在近似等价分裂质量的属性花费大量的 时间，在内存的消耗上也不没有明显的优势，而且，h o e f f d i n g 树算法不能处理概念漂移， 因为h o e f f d i n g 树中的节点一旦创建，就无法改变。 ( 2 ) 快速决策树 快速决策树( 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 算法在选择属性时更主动地打破接 近平局，在训练完许多样例后计算评估函数，一旦内存消耗太大就解除最没有希望的叶 节点的活跃状态，删除分类效果不好的分裂属性。v f d t 算法对于数据流分类有较好的 效果，并且在速度和准确率上也比传统的方法好很多，但是v f d t 算法的一个问题是仍 然不能处理实时数据流中的概念漂移问题。 ( 3 ) 概念自适应快速决策树 为了能够处理实时数据流中的概念漂移，需要一种新的途径来及时识别数据流中与 当前概念不再一致的元素，滑动窗1 2 1 就是常用的方法之一，当新的样例到来时，插入到 窗口起始处，同时从窗口尾部删除相应数量的样例，在滑动窗口中重复使用传统的分类 方法。但是窗口大小缈是一个敏感参数，因为如果力太大，模型就不能准确地描述概念 的漂移，如果缈太小，又会导致没有足够的样例来构建模型。此外，不断地在滑动窗口 武汉科技大学硕士学位论文第9 页 中构造新的分类器模型会使系统开销增大。 概念自适应快速决策树( c o n e 印t m a p t i n gv e r yf a s td e o s i o nt r e e ，c w d t ) 就是在 v f d t 算法的基础上做了改进，以适应数据流的概念漂移。c w d t 算法就是基于滑动窗 口的，c w d t 算法通过增加与新样例相关联的计数，减少与旧样例相关联的计数来更 新统计量，因此，如果数据流中存在概念漂移，一些节点可能不再满足h o e 髓i n g 界， 这是将产生一颗替代的子树，子树的根具有新的最佳分裂属性，随着新的样例流入，替 代的子树持续生长，但是暂时不用于分类。一旦替代的子树变得比已有的子树更准确， 旧的子树将被取代。而且相关的实验研究表明，c v f d t 在随时间变化的数据流上能获 得比v f d t 更好的准确度。而且，v f d t 树中累积了太多过时的样例，这一点决定了 c v f d t 树要比v f d t 树小很多。 ( 4 ) 数据流分类的分类器系综方法 分类器系综( c l a s s i f i e re n s e m b l e ) 方法的主要思想是从数据流的相继数据块训练一 个分类器系综或一组分类器( 比如，使用c 4 5 或朴素贝叶斯) ，即当一个新的数据块到 来时，由它来建立一个新的分类器，个体分类器根据其在随时间变化的环境中期望分类 准确率加权，保留最高的k 个分类器，然后基于这些分类器的加权投票做出决策。相关 研究表明，采用加权投票技术综合使用多种分类器的系综方法比任何单个分类器的准确 率都要高。 2 4 实时数据流频繁模式挖掘 频繁模式挖掘具有重要的实践意义，例如，在网络监控和通信工程中，通过挖掘频 繁模式可以检测网络拥塞等异常情况，从而找出原因以实现快速自主式修复；在w e b 数 据流中发现频繁模式，可以优化网站结构，提高服务性能；在无线传感器网络数据流中 发现频繁模式，可以实现传感器节点的优化配置，提高无线传感器网络的数据处理能力， 数据流中的频繁模式挖掘由此成为数据流挖掘的热点与难点问题【2 2 】【2 7 1 。 频繁模式挖掘的主要任务是发现数据集中频繁出现的模式集，模式可以是项的集合、 子序列或者子结构。如果对于一个模式的计数满足最小支持度则称它是“频繁”的，传 统的可伸缩的频繁模式挖掘方法在静态数据集上已经得到了广泛的研究。实时数据流中 的频繁模式是动态的，即不频繁的项集随着时间的推移可能变成频繁的项集，频繁的项 集随着时间的推移也可能变成不频繁的项集。实时数据流环境下数据的单遍扫描以及有 限存储空间的约束使得我们一般只能推导出答案的一个近似解集，也正是因为近似，结 果会存在漏报( f f l s en e g a t i v e ，即没有获得所有正确的频繁模式) 或误报( f a l s ep o s i t i v e ， 即把非频繁模式认为是频繁模式) 的可能，这两类误差相互制约，也就说在实时数据流 环境下，近似算法不可能同时避免上述两类误差，降低一类误差会导致另一类误差的上 升，误差控制需要根据实际情况来确定。 大量实时数据流快速到达时，无法用有限的内存来精确发现频繁模式，迫使我们必 须放弃一些数据项或数据包，只对最可能频繁的数据项进行计数，从而得到近似的结果， 第1 0 页武汉科技大学硕士学位论文 实时数据流频繁模式挖掘的问题也就演变为一个对不完全样本进行统计计数的问题。现 有实时数据流频繁模式挖掘算法主要分为两类【2 8 】：基于概率误差区间( p r o b a b i l i s t i e b o u n d so i le r r o r ) ，基于确定误差区间( d e t e r m i n i s t i cb o u n d so ne r r o r ) 。 ( 1 ) 基于概率误差区间( p r o b a b i l i s t i cb o u n d so ne r r o r ) 基于概率误差区间的近似算法以较高的置信度将频率估计的相对误差控制在一个较 小的范围内，该误差区间并非完全确定，只能以较高概率得到保证。此类算法采用了采 样、哈希等随机方法，在处理过程中会带来随机性，致使项集的频率估计出现误差，误 差区间在统计意义下能够得到控制，从而获得近似结果。 常见的做法是在内存保存一个能够反映数据流统计特性的样本，基于该样本完成频。 率的近似计算。文献 2 9 】中利用“s t i c k y 采样”近似得到满足支持度要求的频繁项( 项集) ， 该采样方法中采样率以指数形式动态变化，当采样率动态变化时，随机减少计算器中计 数器的值，计数器值为0 的计数器将被删除以减小系统空间消耗。s t i c k y 采样方法使用 随机函数来存储和处理流入的数据项，所得估计频率的相对误差无法确定给出，只能保 证其至少以置信概率( 1 一万) 落入给定的范围0 s l ，而且该置信度与存储空间的大小 成正比，即空间足够大的时候，置信度逐渐趋近于1 。这种利用一定概率来保证误差区 间的方法，可以获得有效的频繁项集。 文献【3 0 将s t i c k y 采样技术与滑动窗e l 技术结合起来处理数据流中数据过期的问题， 实现数据的动态添加与删除。由于s t i c k y 等采样技术在处理数据项时可能会导致遗漏一 些重要信息，这种基于采样的方法在使用时也并不方便。另外一种则是基于哈希操作的 项集计数方法【3 1 h 3 3 1 ，它逐个对数据项进行哈希操作，能够将m ( m 一帅个不同的数据项 映射到更小的空间中，而且一个计数器可以被不同的数据项共享，同一个数据项会被不 同的哈希函数分配到不同的计数器，通过数据的流入流出来增加或减少对应的计数器， 这种方法操作简便，可以利用概率不等式确保误差区间的置信度。 此外，无漏报算法( n of a l s en e g a t i v e ) 常需要存储大量的非频繁集，占用了大量的1 系统存储资源，为了减少由此造成的空间消耗，j e f f r e y 等人【3 4 】设计了无漏报的算法，通 过在给定参数情况下利用切尔诺夫边界可以有效地控制项集的存储空间消耗，降低了算 法空间复杂度。 ( 2 ) 基于确定误差区间( d e t e r m i n i s t i cb o u n d so ne r r o r ) 基于确定误差区间的算法没有采用随机的方法来估算项集的频率，因此，相对误差 的上界是确定的，一般能确定给出频率估计相对误差的范围。在处理过程中，既不像采 样方法那样获得数据集的一个子集，也不存在哈希方法中的随机映射。该类算法往往依 据相对误差将流入的数据划分成段( s e g m e n t ) ，在段的边界处，根据项集频率舍弃那些 一般不会满足支持度要求的项集，以此来降低算法空间复杂度，整个过程中不存在随机 性，因此误差区间可以确定。文献 2 9 】中的l o s s y 频繁项计数方法就是将数据流分成事 务数相等的桶( b u c k e t ) ，由误差参数来控制桶的大小，项集频率估计厂及最大误差信 武汉科技大学 硕士学位论文第1 1 页 息保存在预先定义的数据结构d ( e ，f ，a ) 中。在桶的边界处更新该结构，删除那些频率较 低的项集，以实现在无漏报的前提下降低空间复杂度。 ( 3 ) 其他高效的挖掘算法 传统的基于界标模型( 参见第3 1 节有关界标模型的介绍) 的处理方法只是考虑数 据的不断累积和增长，实时上，在实时数据流挖掘领域一般需要考虑历史数据的作用不 断淡化和减弱，只有这样才能反映数据点动态变化以及数据点的最新趋势，为了达到这 一目标文献 3 5 1 采用衰减因子来削减历史事务对数据项集频率的影响，文献 3 6 贝j j 是根据 倾斜时间窗口与f p g r o w t h 的特点，采用对数倾斜时间窗口来维护频繁模式，从而实现 实时数据流中频繁模式的动态发现。l e e 等人【3 刀【3 8 】采用一种基于交易敏感的滑动窗i = i 来 维护数据流中的闭合频繁项集，并提出了一种高效的比特序列来描述这些闭合频繁项集， 有效地降低了系统的时空消耗。 2 5 实时数据流关联规则分析 实时数据流挖掘的对象可以是单条数据流，也可以是多条的数据流，对于多数据流 关联规则分析的研究主要包含两个方面：( 1 ) 计算两条数据流之间的关联系数；( 2 ) 计 算多条数据流的主分量。 ( 1 ) 多数据流的关联度计算 关联度计算是指当系统中存在多条数据流时，计算一对数据流之间的关联系数，用 以发现具有较高的正关联或负关联的数据流对，在数据流的流量很大的情况下，在线计 算每对数据流之间的关联系数具有很大的难度。文献 3 9 】中的s t a t s t r e a m 系统是一种基 于滑动窗口的关联度技术方法，滑动窗口内的数据流片段作为数据流的概要数据结构 ( s y n o p s i sd a t as t r u c t u r e ，s d s ) 。系统首先将数据流划分成固定长度的段，保存每个段内 数据点的离散傅立叶变换系数。通过使用离散傅立叶变换的保距性以及系数的对称性， 推导出数据流对的傅立叶变换系数之间的距离与管理系数之间的关系。通常情况下，系 统只对