（运筹学与控制论专业论文）数据流挖掘算法研究.pdf

摘要 摘要 近年来，得益于数据采集技术的发展，许多应用中的数据是以流的形式产生 的。分析和挖掘这类数据日益成为热点问题。相对于传统的静态数据库，数据流 有以下特点：( 1 ) 数据量是潜在无界的；( 2 ) 数据有很快的到达率；( 3 ) 不允许 反复扫描历史数据。 数据流的特点决定了数据流挖掘必须满足如下基本要求：首先，算法需要及 时处理高速到达的数据，因此，算法的计算复杂度要低；再者，有限的内存不可 能存储无界的数据量，因此，算法需要保持较低的空间复杂度，维持一个基本的 近似空间并在此得到问题的近似解；此外，由于数据流的动态性，算法必须动态 调整自身参数以适应数据流的变化。 传统的数据挖掘算法很难同时满足以上三个条件，需要对以往数据挖掘算法 进行改进或者设计出适应数据流的挖掘算法。近年来，数据流挖掘的研究己取得 很大进展，然而，这些新方法仍具有很大的局限性，能够处理数据流的种类也很 有限。 本文主要工作有如下两个方面： 1 本文提出一种高维混合型数据流的可视化算法。在尽量保证数据之间区分 度的前提下，算法动态调整参数，把数值型数据和分类型数据分别按照不同方法 映射到颜色空间上，由此得到最近一段时间内的颜色矩阵从而作出混合型数据流 的视图。 2 本文提出基于衰减聚类核心的高维混合型数据流聚类算法。首先，定义聚 类核心的概念，并在此基础上利用一种“打靶 的方法判断新数据所属的聚类。 针对数值型数据维和分类型数据维，定义不同的聚类核心以及不同的“打靶“方 法。算法中，每个参数以及数据结构都随时间而衰减，并根据相应的时间衰减因 子进行动态调整。实验表明，该算法能够动态适应数据流的变化并取得良好的聚 类效果。 关键词：数据流，数据挖掘，可视化，聚类 a b s t ra ( 了r a b s t r a c t i nr e c e n ty e a r s ，m a n ya p p l i c a t i o n sg e n e r a t ea l a r g en u m b e ro fs t r e a m i n gd a t ad u e t ot h ed e v e l o p m e n to fd a t ag a t h e r i n gt e c h n o l o g y a n a l y z i n ga n dm i n i n gs u c hk i n do f d a t ah a si n c r e a s i n g l yb e c o m eh o ti s s u e s c o m p a r e dw i t ht r a d i t i o n a ls t a t i cd a t a b a s e s ， d a t as t r e a m sh a v et h ef o l l o w i n gc h a r a c t e r i s t i c s ：( 1 ) p o t e n t i a l l yu n b o u n d e dv o l u m eo f d a t a ；( 2 ) r a p i da r r i v i n gr a t eo fd a t a ；( 3 ) i n a d m i s s i b i l i t yo fs c a n n i n gh i s t o r i c a l d a t a r e p e a t e d l y t 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 sr e q u i r et h a tm i n i n gd a t as t r e a m sm u s tm e e tt h e f o l l o w i n gb a s i cr e q u i r e m e n t s ：f i r s t , t h ea l g o r i t h m ss h o u l dp r o c e s sr a p i da r r i v i n gd a t a t h e r e f o r e ，t h ec o m p u t a t i o n a lc o m p l e x i t yo ft h ea l g o r i t h ms h o u l db el o w ；f u r t h e r m o r e , l i m i t e dm e m o r yc a n n o ts t o r eu n b o u n d e dv o l u m eo fd a t a t h e r e f o m ，t h es p a c e c o m p l e x i t yo ft h ea l g o r i t h m ss h o u l db el o wa n dt h ea l g o r i t h m ss h o u l dk e e pab a s i c a p p r o x i m a t es p a c ew h e r ei tc a ng e ta p p r o x i m a t es o l u t i o n s ；i na d d i t i o n ，d a t as t r e a m sa r e t i m ec h a n g i n gs ot h a tt h ep a r a m e t e r so ft h ea l g o r i t h m ss h o u l db ed y n a m i c a l l ya d j u s t e d t os u c hc h a n g e s t r a d i t i o n a ld a t am i n i n ga l g o r i t h m sc a nh a r d ym e e tt h ea b o v er e q u i r e m e n t sa tt h e s a m et i m e ，a n dt h u st h ea l g o r i t h m ss h o u l db ei m p r o v e do rd e s i g n e df o rt h o s en e wd a t a i nr e c e n ty e a r s ，t h ed a t as t r e a m sm i n i n gr e s e a r c h e sh a v em a d eg r e a tp r o g r e s s e s h o w e v e r , t h e s en e wm e t h o d ss t i l lh a v ea1 0 to fl i m i t a t i o n sa n dt h e yc a l lh a n d l el i m i t k i n d so fd a t as t r e a m s t h em a i nc o n t r i b u t i o n so ft h i st h e s i si n c l u d et h ef o l l o w i n ga s p e c t s ： 1 t h i sa r t i c l ep r e s e n t sa na l g o r i t h mf o rv i s u a l i z i n gh i g h - d i m e n s i o n a lm i x e dt y p e o fd a t as t r e a m s t h ea l g o r i t h ma d j u s t si t sp a r a m e t e r st ot h ei n c o m i n gd a t aa n dm a p s n u m e r i c a ld a t aa n dc a t e g o r i c a ld a t ai n t oc o l o rs p a c e 砸md i f f e r e n tm e t h o d s ，a s s u r i n g t h a td i f f e r e n td a t ac a l lb ed i s t i n g u i s h e df r o me a c ho t h e r , a n dt h u sar e c e n tc o l o rm a t r i x w i l lb ea v m l a b l ea n df i n a l l yw ew i l lg e tav i e w g r a p ho f r e c e n td a t a 2 t h i sa r t i c l ep u tf o r w a r d st h ea l g o r i t h mo fh s f cw h i c hi s s h o r tf o r h i g h d i m e n s i o n a ls t r e a mf a d i n gc o r ec l u s t e r i n g f i r s t ，t h ec o n c e p to fc l u s t e rc o r ei s d e f i n e d ，b a s e do nw h i c ht h ei n c o m i n gd a t a sc l a s sl a b e li sj u d g e db yt h em e t h o do f i i a b s t r a c t “t a r g e t i n g i nt h i sa l g o r i t h m ，a l lt h ep a r a m e t e r sa n dd a t as t r u c t u r e sa l ef a d i n gw i n lt i m e a n dt h e ya let ob er e a d j u s t e dw i t ht h ec o r r e s p o n d i n gf a d i n gf a c t o r s t h ee m p i r i c a l r e s u l t ss h o wt h a th s f cc a l lc o p ew i t l lc h a n g e so ft h ed a t as t r e a m sa n dg e tf i n e c l u s t e r i n gr e s u l t s k e y w o r d s ：d a t as t r e a m ，d a t am i n i n g ，v i s u a l i z i n g ，c l u s t e r i n g i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：翌担生：日期：沁p 吕年，月 e l 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：鱼担圭导师签名：丝 日期：h o 墨年，月2 , 7e l 第一章引言 1 1 数据流挖掘背景 第一章引言 近年来，随着软、硬件技术的发展，传感器网络、w e b 日记、路由信息、宇 宙电波等高速连续数据的自动产生、记录日趋普遍，这些数据称为数据流。相对 于时序数据等按照数据内部特征来定义的数据，数据流是一种根据数据到达速率 来定义的动态数据，其定义为高速到达的输入数据【l 埘。 数据流的高速性质意味着它对通信和计算有严格的要求【i 翻。因此，数据流处 理面临的问题在于：难以传输所有的数据，难以快速高效的计算复杂的函数，难 以存储所有的数据。 总之，数据流的单向无界性质决定了数据流挖掘不允许算法访问历史数据， 同时必须在计算资源( 内存、c p u 、带宽、能量等) 受限下挖掘数据流中的隐藏 信息。 传统的数据挖掘算法在分析静态数据领域取得了很多成果。然而，面对数据 流时，这些算法存在很多问题： 1 允许多次访问数据，无法处理潜在无界的数据流； 2 计算复杂度太大，难以与数据流达到同步； 3 空间复杂度太大，难以在有限内存下求解。 数据流无限增长的数据量与高速数据率使得数据流挖掘算法必须以增量方式 捕捉到数据流的发展变化。与传统数据挖掘相比： 1 由于数据量潜在无界，对数据流的扫描次数为一次或少量几次，一般不允 许访问历史数据。传统数据挖掘中，数据通常为静态数据，可以随机扫描数据。 2 数据流的高速到达要求挖掘算法的处理速度能够与数据流的到达同步，否 则算法会被数据淹没。而传统数据挖掘中，数据是静态的，算法在指定时间内一 般能够处理完所有数据。同时，系统的内存资源相对于数据流的数据量显得微不 足道，因此算法的空间复杂度通常要求在o ( p o l y ( 1 0 9 加) 内，而传统数据挖掘对算 法空间复杂度没有严格要求【3 圳。 3 数据流环境中，算法不允许访问或无法访问历史数据，因此数据流挖掘算 法需要维持历史数据的必要信息概况并产生近似挖掘结果。而传统数据挖掘算法 电子科技大学硕士学位论文 可以得到精确的挖掘结果。 4 数据流环境中，与数据相关的指标往往是动态的。例如数据流聚类中心的 变化以及分类的概念漂移。数据流挖掘算法必须捕捉到这些变化并不断修正算法 参数及数据结构。而传统数据挖掘基于静态数据库，这些数据往往基于同一分布， 挖掘结果是惟一的。 因此，传统的数据挖掘算法难以适应数据流挖掘的需要，必须改进或创造一 套新的模型和算法以挖掘日趋庞大复杂的数据流。 1 2 数据流挖掘研究现状 数据流挖掘近年来备受国外学者重视。数据库三大顶级会议s i g m o d ，v l d b ， i c d e 以及数据挖掘最高会议k d d 每年都发表不少数据流挖掘领域的高质量论文。 实际上，数据流挖掘的经典论文几乎都出自这几个会议。迄今为止，数据流挖掘 领域已出版一本专著【5 】并做出了一些成功的应用系统【6 - 9 1 。 1 3 课题的研究意义 数据流挖掘是数据挖掘和数据库领域的一个新的热点，正如s m u t h u k r i s h n a n 所说：“t r e n do rn o t ，d a t as t r e a m sa r en o wa r t 【2 】 数据流挖掘算法的研究，能够为日 益增加的海量数据分析提供理论和方法支持，对构建快速、节能的实时监控系统 也有指导作用。 1 4 论文结构及内容介绍 本文共分为六章。 第一章是引言部分，介绍了数据流挖掘的背景、研究现状以及研究意义。 第二章主要描述数据流挖掘相关的理论基础，包括数据分析相关理论，数据 流挖掘基于数据的技术和基于任务的技术。 第三章从数据流挖掘任务方面介绍了数据流挖掘技术，包括数据流分类、聚 类、频繁模式挖掘以及数据流挖掘的应用。 第四章提出一种高维混合型数据流的可视化算法。 第五章提出基于衰减聚类核心的高维数据流聚类算法。 2 第一章引言 第六章对本文的总结与今后工作的展望。 电子科技大学硕士学位论文 第二章数据流挖掘理论基础 数据流挖掘理论的发展，一方面得益于计算统计学等数据分析方法的深入研 究，另一方面则开辟了一条独特的研究方向。根据已经建立的统计和计算理论， 数据流挖掘理论可分为基于数据的理论和基于任务的理论【1 0 1 。基于数据的理论的 思想在于检验整个数据集的一个子集或把数据集转换到一个相对简单的数据集。 而基于任务的理论则在于寻求适合数据流挖掘的计算理论。本节将分别讨论这些 理论基础。 2 1 数据分析相关理论 数据分析相关理论从最底层面上对数据之间的比较和结果的正确性提供理论 保证。本节将简述相关内容。 2 1 1 数据集类型 数据集可以看作是数据对象的集合，数据对象用一组刻画对象基本特征的属 性描述【l l 】。根据属性的不同，数据可以分为分类的和数值的，而根据属性的取值 个数，数据可以分为连续的和离散的。 数据集的种类很多，并且随着数据挖掘的发展与成熟，更多类型的数据集将 用于分析。常见类型有：记录数据、基于图形的数据和有序数据。 记录数据中，每个记录包含固定的数据属性集。大部分记录数据的记录之间 没有明显关系，并且每个记录有相同的属性集。记录数据通常存储在平面文件或 关系数据库中。事务数据是一类特殊的记录数据，其中每个记录( 事务) 涉及一 个项的集合。在商店中，消费者的消费行为称为购物篮数据。 基于图形的数据主要有两种情况：图形表示数据对象之间的关系，数据对象 本身可以用图形表示。 考虑对象之间的重要联系的情况下，数据常常用图形表示，例如w e b 之间的 链接是w e b 结构挖掘的最重要信息之一。用图形表示的数据对象中，对象具有结 构，即包含联系的子对象。例如有机物的分子式，分析分子式中的子结构是这类 数据的个挖掘子领域。 4 第二章数据流挖掘理论基础 有序数据的属性涉及时间或空间的联系，主要分为时序数据、序列数据、时 间序列数据和空间数据 时序数据每个记录包含一个与之相关联的时间，典型的时序数据如春运期间 中国的客运量。序列数据是一个个体项的有序排列，与时序数据很相似，但没有 时间戳，起而代之的是序列中的位置。例如遗传信息的基因组序列数据。 时间序列数据中每个记录都是一个时间序列，例如股市数据。分析时间序列 数据需要考虑时间自相关，即如果两个测量的时间很接近，这些数据通常非常接 近。 空间数据除了具有以上数据的属性之外，还有空间属性。g i s 中，需要考虑时 间、空间等诸多属性。空间数据具有空间自相关的特点，即位置上靠近的地区其 它属性也类似。 2 。1 。2 数据的邻近度 两个数据之间的临近度是两者对应属性之间的临近度函数，包括相似性和相 异性f l l 】。两个数据之间的相似度是这两个对象相似程度的数值度量，两个数据之 间越相似，它们的相似度就越大。两个数据之间的相异度是这两个数据差异程度 的数值度量，两个数据之间越相异，它们的相异度就越大。相异度可以通过一个 单调减函数转换到相似度。 2 1 2 。1 数据的相似度 数值型数据相似度通常的方法是计算它们之间的方差和相关系数。对于混合 型数据x = ( ，) ，其中x 。为分类型数据，为数值型数据，则需要采取另外一 种方法。有时候，这种数据之间的比较当且仅当分类型数据相同的情况下才有意 义，这种情况下，数据x ，= ( ，巧) 和以= ( ，) 的相似度表示为： s ( z ，五) ：j 至二皇n 童- 幽i ，若： ( 2 1 ) s ( ，五) = 石工，一 ( 2 - ) 10 ， 其它 实际情况中，可以放宽上式满足的条件，只要分类型数据之间的某种邻近度达到 一定阈值就可以使用公式2 1 计算混合型数据的相似度，分类型数据之间的邻近度 可以采用海明距离计算。 一种常用的相似性系数是简单匹配系数( s i m p l e m a t c h i n g c o e f f i c i e n t ，s m c ) ， 5 电子科技大学硕士学位论文 定义如下： s m c ： ! 盘 五。+ 彳。+ 彳l + 厶 ( 2 - 2 ) 其中，石表示f j 匹配的个数，f ，j o ，1 ) 。 通常，文档用向量表示，向量的每个属性代表一个特定的词在文档中出现的 频率。尽管文档具有大量的属性，但每个文档时稀疏的。因此，文档的相似度需 要忽略0 - 0 匹配，余弦相似度就是文档现实性最常用的度量之一。如果x 和y 上两 个文档向量，则 酬舶= 赢 ( 2 - 3 ) 其中，胛表示向量内积，i ixi i = 面。 2 1 2 2 数据的相异度 描述数值型数据相异度通常用到的距离。数据挖掘中，数据薯，蕞之间最常 见的距离有： e u c l i d e a n 距离： m a n h a t t a n 距离： c a n b e r r a 距离： l r 芝( b 刊z - i = 1 x j , 。x u 善器 ( 2 - 4 ) ( 2 5 ) ( 2 6 ) 2 1 3 概率统计 在数据流挖掘领域，概率统计主要是用概率不等式对挖掘结果的正确性提供 6 第二章数据流挖掘理论基础 概率保证。 常用的概率不等式有马尔可夫不等式【1 2 1 ，切比雪夫不等式【1 2 1 ，h o e f f d i n g 不等 式【1 2 】和c h e m o f f 界 1 2 - 1 3 】： 1 令x 是期望为“方差为v a r ( x ) 的随机变量，对v s 0 ，马尔可夫不等式可 以保证段x 占) 兰。切比雪夫不等式则可保证 p ( i x 一“i u 6 ) 芝孕( 2 - 7 ) u 占 2 h o e f f d i n g 不等式对随机变量的累加和提供概率保证。令五，置，以为随 机变量，满足。五，j = 去喜置，“为贾的数学期望。对v 占 。，有 - 2 r a n - - 2 尸( j j u l - g ) 2 er2(28) 3 c h 锄f f 界可对独立b e r n o u l l i 事件累加和提供概率保证。令五，五，e 为独立b e r n o u l l i 事件且p ( 五= 1 ) = p ，p ( 互= o ) = 1 一p ，x = 五，则x 的数学 期望u = m p 。对v s 0 ，有 二生 p ( i x 一“i “占) 2 e 2 ( 2 9 ) c h e m o f f 界在计数查询方面能提供比h o e f f d i n g 不等式更小的界。 2 1 4 数据可视化 数据可视化是指以图形的形式显示信息。可视化需要将数据转换成可视信息， 使得能够借此分析或报告数据的特征和数据项或属性之间的关系。可视化的目标 是可视化信息的人工解释和信息的意境模型的形成【1 1 1 。 在实际应用中，数据可视化一般指在二维屏幕或纸面上呈现出数据的各种属 性。数据可视化揭示了数据最基本同时也可能是最重要的信息，是探索数据最直 接的方法之一。 低维数据的可视化比较容易，可以在二维坐标系或三维坐标系下表现出来， 7 电子科技大学硕士学位论文 这里不赘述。 高维数据的可视化需要对数据做一些预处理工作，这些技术有一些局限，只 能显示数据的某些侧面。 数据矩阵是值的矩阵排列，如果将数据矩阵的每个元素与图像中的一个像素 相关联，就可以把数据矩阵看作图像，像素值由矩阵对应元素的值决定。 平行坐标系中，每个属性有一个坐标轴，彼此之间是平行的，数据用线而不 是通常的点表示。具体的说，数据每个属性的值映射到与该属性相关联的坐标轴 上的点，然后将这些点连接起来形成代表该数据的折线。 此外，多维数据的一个点可以用二维图形表示，例如星图【1 4 j 和c h e m o f f 脸谱 【1 5 】，将数据的每个属性映射到图形的一个特征，使得属性的值决定特征的性质。 2 2 基于数据的技术 基于数据的理论在于降低数据的复杂性，对数据进行转换、简化是其目的。 本节将对抽样、减载、梗概、概要数据结构、聚合以及多分辨率方法进行简述。 2 2 1 抽样 对数据流抽样是指以一定概率决定是否处理当前到达的数据项。对于数据流， 预先不知道流的长度，考虑对其进行周期区间抽样，可以使用一种称作水库抽样【1 6 】 的技术无放回的选取j 个元素的无偏随机样本。维护一个大小至少为j 的样本，称 作“水库 ，可以从中产生大小为s 的随机样本。然而，从水库中产生样本可能代 价很大，特别是水库很大的时候。为了避免这种情况，在水库中维护s 个候选的集 合，形成到目前看到的数据流元素的真正随机样本。随着数据流的推进，每个新 元素都有一定的可能性取代水库中的旧元素。假定已经看到了流中的个元素。 随机选择一个新元素取代旧元素的可能性为s 。这就一直保持水库中s 个候选 集合形成一个到目前看到的数据流元素的随机样本。 2 2 2 减载 减载是指抛弃一列数据流 1 7 - 1 8 】，已成功用于数据流查询。然而，减载用于挖 掘还存在一些问题【1 0 1 ，因为抛弃的数据可能要用于挖掘模型的构建。对于时间序 列分析来说，这可能意味着抛弃一个有用的模式。 第二章数据流挖掘理论基础 2 2 3 梗概 梗概技术基于降维，即对到达的数据项在一组随机向量上做投影。这些投影 出来的值被称为梗概【1 9 之0 】。假设希望在数据流的对象的定义域上维护完全的直方 图，其中定义域为u = 1 ，2 ，) ，数据流a = 地，口：，口，) 。对u 中每个值f ， 要维护i 在彳中出现的频率或次数。如果i 【厂i 很大，这个结构也同样很大。因此， 需要更小的表达方式。 考虑彳的频率矩e ( f r e q u e n c ym o m e n t ) 定义为 最= 硝 ( 2 - 1 0 ) f 军i 其中，v 司u i ，m ，是f 在数据流中出现的频率，并且k 0 。特别的，r 是数据流 中不同元素的个数。只= n 是数据流的当前长度，e 是自连接的大小、重复率或 g i n i 指标。 单内存小于v 时，需要使用梗概( s k e t c h ) 的大纲对频率矩进行估计。使用数 据向量的随机线性投影，这些梗概建立分布向量的一个小空间汇总。梗概对近似 结果的质量提供概率保证。给定当前个元素和具有1 ，个值的定义域u ，这些梗 概可以在o ( 1 0 9 v + l o g 忉的空间上近似只、鼻和e 。其基本思想是，将每个元素 均匀随机的散列到弓e - 1 ，1 ) ，然后维护一个随机变量x = ，m i z i 。则x 2 是互的 一个估计。 梗概用于比较聚合序列( a g g r e g a t eq u e r y ) 中的不同数据流。主要缺点在于其 精确度，因而在数据流挖掘中应用很困难。为了降低误差，a l o n 等人利用多组相 互独立的投影( 或哈希函数) ，对所有估计值取中值作为最终估计值，从而在理论上 保证估计值误差不超过用户预先定义的允许误差。随机向量通过对随机变量进行 某种空间节省的计算来产生。h l d y k 等人【1 9 】提出了利用s t a b l e 分布来产生随机变量 的方法，可用于估计数据流的各种三阶矩。 其它一系列基于随机投影的方法，如b l o o m f i l t c r 2 0 ，随机子集和【2 1 1 ，c o u n t i n g s k e t c h t 2 2 1 ，这里不赘述。 主成份分析( p c a ) 可能会是一个更好的方法并已应用到实际数据流中【j 7 1 。 9 电子科技大学硕士学位论文 2 2 4 概要数据结构 概要数据结构是指可将数据流进行概括统计的数据结构 2 3 1 ，用这些数据结构 代表原始数据，包括小波分析和直方图等。小波分析将原始数据变换成一系列小 波参数。由少数几个小波参数保留原始数据的大部分特征【2 l 】，可以通过小波参数 近似还原原始数据。 直方图是一种概要数据结构，可以用来近似表示数据流中元素值的频率分布。 直方图把原始数据划分成多个相邻的桶( b u c k e t ) ，依照使用的划分规则，桶的宽 度( 桶的值域) 和深度( 每个桶里元素个数) 可以是不同的。根据桶的划分不同， 可以分为： 1 等宽直方图，其中各个桶包含的数据量相同。 2 压缩直方图，为频繁元素单独创建桶，对其它元素采用等宽直方图。 3 v 优化直方图，其划分桶的依据是使得各桶的方差和最小。 直方图建立好后可以对数据流进行近似查询。 2 2 5 聚合 聚合是计算数据流的统计量( 数学期望，方差等) 的过程，聚合结果可用于 挖掘算法。聚合对于浮动较大的数据流存在一些问题1 0 】。值得提出的是，文献 2 4 】 对离线聚合数据和在线聚合数据的合并进行了研究。 2 2 6 多分辨率方法 多分辨率数据结构是一种采用分治策略的数据归约方法，允许程序在准确性 和存储之间进行权衡，并可以借此在多层细节上理解数据流。 平衡二叉树是一个典型的例子，但新数据到来时，努力保持树的平衡。树的 每一层提供不同的分辨率，离树根越远的层，分辨率就越细。 一种更复杂的形成多分辨率的方法是使用聚类方法将数据流组织成为一个层 次结构的树。例如，使用一种像b i r c h 中的c f 树【2 5 】那样的层次聚类数据结构来 形成微簇的层次结构。随着动态数据流的推进，数据流的汇总统计量可以在微簇 的层次结构中增量的更新。根据应用的要求，可以将这些微簇中的信息聚集成较 大的宏簇中，导出多分辨率的一般数据统计量。 小波可以用来构建数据流的多分辨率层次结构。给定一个数据流，可以用简 l o 第二章数据流挖掘理论基础 单的正交基函数分解或重写它，最简单的基是哈尔小波，相当于在多分辨率上递 归的取平均和微分。哈尔小波易于理解和实现，尤其擅长处理空间和多媒体数据。 对于查询优化，小波已用作直方图的近似。此外，基于小波的直方图可以随时动 态维护。因此，小波是一种流行的数据流压缩的多分辨率方法。 2 3 基于任务的技术 基于任务的技术是数据流分析中应用的一系列改进技术或者专有技术，包括 近似算法，窗口模型和算法输出粒度。本节将对这些技术进行一个概括。 2 3 1 近似算法 近似算法能够在保证近似结果误差范围内为n p 难题提供一些计算代价较小 的近似解【2 6 1 。在资源受限的数据流环境下，近似算法在降低计算复杂度方面具有 举足轻重的地位。 假定一个近似算法的返回结果为随机变量，希望得到该随机变量尾概率的晁。 一个基本的工具是切比雪夫不等式( 见公式2 7 ) 。这个不等式可以用来限定随机 变量的方差的界。 在很多情况下，可以使用大量随机变量来提升结果的置信水平。只要这些随 机变量是完全独立的，就可以使用c h e m o f f 界。设墨，t ，e 独立服从泊松分布。 在不同的泊松实验中，成功的概率是不同的。如果x 是五到以的和，则一个较弱 的c h e m o f f 界表明 一z p ( x ( 1 + 万) ) e4(2一11) 其中艿( 0 , t 】。表明随着偏离均值，该概率指数递减，使得低质量的估计不大可能。 2 3 2 窗口模型 滑动窗口基于人们对最近到达的数据更感兴趣的事实设计而成。滑动窗口详 细分析最近的一些数据而对过去的数据仅做一些概括。其基本思想是：仅仅基于 最近的数据做出决策，而不是对目前为止看到的所有数据或对某个样本进行计算。 形式化的，若在每个时刻f 有一个新的数据元素到来。该元素在时亥u t + w 时将“过 期 ，其中w 为滑动窗口的大小。滑动窗口模型对于股票或传感器网络很有用，那 电子科技大学硕士学位论文 里只有最近的事件才可能是最重要的。由于只需存储小的数据窗口，滑动窗口技 术可以减少对内存的需求。 在数据流分析中，人们通常对细尺度上的当前变化感兴趣，但在粗尺度上对 长期变化感兴趣。因此，可以在不同粒度层面上记录时间。最近的时间在最细的 粒度上记录，较久远的时间在较粗的粒度上记录。粗略程度取决于应用需求和与 当前时间的长短。这样的时间维模型叫做倾斜时间框架( t i l t e dt i m ef l a m e ) 。这种 模型可以保证驻留在内存中的数据量总是很小。 在倾斜时间帧的设计上，窗口模型可分为自然倾斜时间帧模型、对数尺度倾 斜时间帧模型和渐进对数倾斜时间帧模型跚。 自然倾斜时间帧模型中，时间窗口时基于现实概念或通常的时间度量在多粒 度上构成的。图2 - 1 所示的自然倾斜时间帧模型中，最近的4 刻钟，刚刚过去的 2 4 小时，然后是3 1 天和1 2 个月。基于这个模型，可以计算前一个小时内的频繁 项集，进度为一刻钟，或过去一天中的频繁项集，精度为一个小时，如此下去直 到全年，精度为一个月。这种模型以远处时间力度的可接受的权衡只需要对一年 记录4 + 2 针31 + 1 2 = 7 1 个时间单位。 1 2 m o n t h s3 1d a y s 2 4h o u r s 1 4q t r s i l ju 止l jl jl jul j ! l jul jui 止l jl jl jl j i - f 锄e 图2 - 1 自然倾斜时间帧( 2 7 1 对数尺度倾斜时间帧模型中时间帧根据对数刻度在多粒度上构造。假定最近 的槽保存了最近一刻钟的事务。剩余的槽保留了前1 刻钟、2 刻钟、4 刻钟、8 刻 钟等等的事务，以指数的速率增长。根据该模型，可以把一年的数据精确到一刻 钟，将需要i1 0 9 ，( 3 6 5 x 2 4 x 4 ) + 1 l o g ，( 3 6 5 x 2 4 x 4 ) + li = 1 7 个时间帧来存储压缩信 息。 ! ：凸当蛩白兰白：山胍 图2 - 2 对数尺度倾斜时间帧口刀 渐进对数倾斜时间帧模型中，快照依赖于其崭新程度存储在不同的粒度曾。 假定r 为自数据流开始以来流逝的时间。快照分类到不同的框架编号中，编号可以 从0 变化到t n a x f r a m e ，其中m a x _ c a p a c i t y _ g ，就可以确信的说这个差 大于0 。算法选择4 为最好的分裂属性，其置信度为1 一万。 h o e f f d i n g 树算法惟一需要维护的统计量是具有类标号) ，。的属性4 的值，的 计数玎船。因此，如果d 是属性的个数，1 ，是属性值的最大个数，c 是类的个数，z 是 树的最大深度，则内存总需求为o ( 1 d v c ) 。与其它决策树算法相比，这一内存的需 求是适度的。 b y t e s p r o t o c o l2h a p p r o t o c o l = f l p 图3 - 1 增量的创建h o e f f d i n g 数的节点口哪 除了在小样本的高准确率之外，对于处理数据流，h o e f f d i n g 树还有其他吸引 人的性质。首先，永远不会执行对同一数据的多次扫描。此外，算法是增量的， 这一点可以从图3 1 看出。该图表明，随着新样例的流入，算法如何把它们并入树 1 5 电子科技大学硕士学位论文 中。此外，增量的性质使得即使树正在构造，也可以用它对数据进行分类，树会 持续增长，并且随着更多训练数据流入而变得更准确。 然而，h o e f r d i n g 树算法也有缺点，算法会在近似等价分裂质量的属性花费大 量时间，另外内存利用率可以进一步优化。此外，该算法不能处理概念漂移，因 为一旦创建了一个节点，就不能再改变它。 v f d t 算法对h o e f f d i n g 树算法进行了一些改进，以提高处理速度和内存利用 率。这些改进包括在属性选择时更主动的打破接近平局，在训练完许多样本之后 计算g 函数，一旦内存不够就解除最没有希望的节点的活跃状态，删除拙劣的分 裂属性，以及改进初始化方法。v f d t 算法对数据流运行良好，并且在速度和准确 率上要优于传统的分类方法。但是，它仍然不能处理概念漂移问题。 c v f d t 算法基于v f d t 算法，使用滑动窗口的方法，通过增加与新样例相关 联的计数，减少与旧样例相关联的技术来更新统计量。如果存在概念漂移，一些 节点可能不再满足h o e f f d i n g 界。这种情况下，将产生一棵替代子树，子树的根具 有新的最佳分裂属性。随着新的样例到达，替代的子树继续成长，却不用于分类。 一旦替代子树变得比已有子树更准确，将取代已有子树。研究表明，c v f d t 算法 在随时间变化数据流上比v f d t 有更高的准确率，另外，c v f d t 树比v f d t 树小。 分类器系综是另一种能够处理概念漂移的数据流分类算法。主要思想上从数 据流的相继块训练一个分类器系综或一组分类器。也就是说，当一个新的数据块 到达时，由它建立一个新的分类器。个体分类器根据它在随时间变化的环境中期 望分类准确率加权。最后仅保留最高的k 个分类器，基于这些分类器的加权投票做 出决策。实验表明，分类器系综方法比任何单个分类器的准确率都要高。 3 2 数据流聚类 设想一个海量动态数据流，许多应用需要根据现实性把这种数据自动聚类。 这类应用包括网络入侵检测、分析网络点击流和股票市场分析等。 针对数据流聚类，已提出一些思想方法【3 0 j ，如下所示： 1 计算和保存过去数据的汇总信息：由于内存空间的限制和快速响应的需求， 计算以前数据的汇总信息，保存相关的结果，并在需要的时候用这些汇总信息计 算重要的统计量。 2 应用分治策略：按照数据到来的次序把数据流分块，计算这些块的汇总信 息，然后合并这些汇总信息。在这种方式下，较大的模型可由较小的块构建而成。 1 6 第三章数据流挖掘技术 3 输入数据流的增量聚类：由于数据流连续和增量的进入系统，因此导出的 簇必须增量的更新。 4 进行微聚类和宏聚类分析：流聚类的计算可分成两部：( 1 ) 在微簇层计算 和存储汇总信息，其中微簇使用一种层次自底向上的聚类算法形成。( 2 ) 在用户 指定层上计算宏簇。这两步计算有效的压缩了数据，并且通常导致较小的误差范 围。 5 利用多个时间粒度来分析簇的演变：由于在数据流分析中，最近的数据所 起的作用通常与过去的数据不同，因此，使用倾斜时间帧模型存储不同时间点的 汇总数据快照。 6 把流聚类划分成联机和脱机处理：当数据流到达时，应该计算、存储和增 量的更新数据快照的基本汇总信息。这样，联机处理过程需要维护这样一个动态 变化的簇。同时，用户可以对过去、当前或演变的簇进行查询。这种分析可以脱 机处理或当作独立于联机聚类维护的过程。 目前数据流聚类算法主要可以分成两类：单