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

独创性：声明 辫 iy 18 2 4 芗。岩l 苜。 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重废由e 电太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：匆彘鹨 签字日期：砂帕7 年f 月猸 学位论文版权使用授权书 本学位论文作者完全了解重迭自g 血太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽自e 血太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者躲袁硒 翩躲素畸 签字日期：易门7 年箩月乩日 签字日期： 垆爹月7 调 重庆邮电大学硕士论文 摘要 摘要 数据流是一种数据访问方式的形象化表述，数据源源不断到达主动触发系统 处理，系统一般只能访问数据一次，处理过程中要考虑数据权重。数据可表示属 于同类事物的个体，也可表示不同个体随时间变化的状态值，故数据流又可分为 单流和多流模型。数据挖掘是发现隐藏在大量数据背后的信息，着眼于数据从总 体上表现出来的特征：数据在空间中的分布状态、数据的不同维度在取值上的伴 生或依存关系等。数据流处理的一次扫描、权重问题以及数据量的潜在无限性等 约束增加了对流数据进行查询和挖掘处理的难度。 聚类依据数据间的相似性将数据集划分为多个不同的簇，本文研究多维数据 单流模型的聚类问题。考虑算法的可并行处理和数据挖掘的统一理论框架、突出 聚类在数据挖掘中的基础性地位，采用空间划分的思想生成保存数据分布状态的 概要数据结构，概要结构本身即表现出粗糙的聚类特征。基于概要数据结构的挖 掘，对其中的关键技术和算法进行研究和实现。 首先，基于应用驱动的研究思路，从广义的数据流概念和具体应用中抽取出 四种不同的数据流模型，给出数据流的形式化表示和界定本文所研究的数据流模 型；第二，采用时空划分的思想，用网格保存时间粒度内数据的分布状态，用倾 斜时间框架动态地生成和组织不同时间段的网格概要数据结构，研究基于网格重 组织和最小时间粒度调整的内存需求控制策略；第三，研究大粒度空间划分的可 容忍性，引进统计信息以获取网格单元内部数据的分布特征，探索相对大粒度空 间划分的可行性，实验仿真大粒度划分过程，直观地演示其有效性；最后，设计 基于时空划分和统计信息的数据流聚类处理框架，实现概要结构生成算法，仿真 模拟数据流聚类特征的演化过程，验证概要结构生成算法的去噪音效能，测试概 要结构不同表示法的执行时间、内存使用量，实验结果与理论分析一致。 关键词：数据流，时空划分，概要数据结构，统计信息，聚类 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t d a t as t r e 锄i st h ev i s u a ld e s c r i p t i o n0 fal 【i n d0 fd a t a c e s sm o d e i l l ed a t a 枷v e c o n t i n u o u s l y 锄dt r i g g c rs y s t e mt op r o c e s st h e ma c t i v e l y s y s t e mh 弱0 n l yo n ec h a n c c t 0v i s i tt h ed a t a 锄ds h o u l dc o n s i d e r t h ep r o c e s s e dw e i 曲tw h i c hd e p e n d so ni t sa r r i v a l t i m e t h ed a t ai nt h es t r e a mb e l o n gt 0t h ed i f f e r e n ti n d i v i d u a l si nt h es a m ec l a s s ，0 rt h e i n d i v i d u a l s s t a t ev a l u e sc h 卸酉n gw i t ht h et i m e ，s ot h ed a t as t r e 锄c a nb cc l a s s i f i e di n t 0 s i n 百es t r e 锄m o d e la n dm u l t i - s t i e 锄m o d e l d a t am i n i n gi s t 0f i n dt h ei n t e r e s t e d i n f o m a t i o n 行o ml a r g e 锄0 u n t0 fd a t 如w i t hav i e wt 0t h ew h o l ec h a r a c t e r i s t i c ，l i k et h e d i s t r i b u t i o ns t a t e ，t h ea s s o c i a t i o nm l e so rt h ei n t e r d e p e n d e n t 锄o n gt h ed i m e n s i o n s ，a n d s oo n b e c a u s eo ft h eo n es c a nb o u n d ，w e i g l l tp r o b l e m 锄dt h ei n f i n i t e n e s s ，t h cq u e r y a n dm i n i n gd a t as 仃e 锄a r em o i ed i f ! f i c u l t c l u s t e r i n gi so n e l 【i n do fm i n i n go p e r a t i o n sw h i c hd i v i d e st h ed a t 弱e ti n t 0d i 骶r e n t c l u s t e r sb a s e do nt h es i m i l a r i t y t h i st h e s i sf b c u s e so nt h ec l u s t e r i n go fd a t as t r e 锄 ( b n s i d e r i n gt h ep a r a l l e le x e c u t i o na n dt h eu n i f 0 珊t h e o r ) ro fd a t am i n i n g ，弱w e u 弱 e m p h a s i z i n gt h eb a s i cs t a t i o no fc l u s t e r i n g t h ep r c s e n tu s e st h ei d e a o fs p a c e p a n i t i o n i n gt og e n e m t eas ) r i l o p s i sd a t as t l l l c t u r ew h i c hc o n t a i n st h ed i s t 抽u t i o ns t a t eo f d a t a ，m i n i n gt h es y n o p s i st 0g e tt h ec l u s t e rf e a t u r e r e s e a r c ht h ek e yt e c h n o l o 酉e s 锄d t h ec o r r c l a t i v ea l g o r i t h m s f i r s t ，b a s e do nt h ei d e ao fa p p l i c a t i o n - d r i v e n ，a _ b s t r a c ts e v e m ld a t as t r c 锄m o d e l s 舶mt h eb r o a dc o n c e p to fd a t as t r e a m 锄dt h ec o n c r c t ea p p l i c a t i o n s g i v et h ef b 咖a l d e s c r i p t i o n 觚dd e f i n et h es t r c a mm o d e l sw h i c ht h i sp a p e rc o n c e m s s e c o n d ，m i n ed a t a s t r c a mb a s e d0 nt i m e 柚ds p a c cp a n i t i o n i n g u s eg r i ds t l l l c t u r ct 0c o n s e et h e d i s t r i b u t i o ns t a t eo fd a t ai nd i 凰：r e n tt i m eg r a n u l a r i t y u s eat i l tt i m e 仃a m et og e n e r a t e 锄do 唱a n i z et h es y n o p s i sd a t as t m c t u r e s0 fd i f ! l c r e n tt i m es e g m e n t ，a n dr c s e a r c ht h e c o n t r o ls t r a t e g i e so ft h em e m o r yr e q u i r c m e n tb a s e do nt h er c o 唱a n i z a t i o no f 黟i dc c l l s a n dt h ea d j u s t m e n to fm i n i m a l t i m eg r a n u l a r i t y t h i r d ，r c s e a r c ht h et o l e r a n c co fl a r g e s p a c c 黟a n u l a r i t yp a n i t i o n i n gb a s e do ns t a t i s t j c a li n f b 锄a t i o n g e tt h ed a t ad i s t r i b u t i o n r e 酉o ni n 伊i dc e ub ya d d i n gs o m es t a t i s t i c a li n f o 册a t i o n ；a n a l y z et h ef e a s i b i l i t yo f 化l a t i v e l yl a r g eg r a n u l a 哪s p a c ep a n i t i o n 1 1 h es i m u l a t i o ns h o w st h ef e a s i b i l i t yo fl a r g c 黟a n u l a r i t ys p a c ep a n i t i o n l a s t ，d e s i g nt h ef h m e0 fc l u s t e r i n gd a t as t r e a mb a s e d0 n t i m e 柚ds p a c cp a n i t i o n i n g 鲫ds t a t i s t i c a l i n f b 册a t i o n r e a l i z et h ea 1 9 0 r i t h mw h i c h 重庆邮电大学硕士论文 a b s t r a c t g e n e r a t e st h es y n o p s i sd a t as t l l l c t u r e s t h ee x p e r i m e n t ss h o wt h ed u s t e r s e v 0 l v e m e n t 0 ft h ed a t as t r e a ma n dt h ea l g o r i t h m se f f i c i e n c yo ne l i m i n a t i n gt h en o i s e sd a t a ( m p a r et h ee x e c u t i o nt i m e 锄dt h em e m o r yu s a g e0 fd i f ! l e r c n tr c p r e s e n t a t i o n ，柚dt h e r e s u l t sa 佗c o n s i s t e n tw i t ht h e o r ) ，a n a l y s i s k e yw o r d s ：d a t as t r e a m ，m m e 卸ds p a c cp a n i t i o n i n 岛s t a t i s t i c a li n f 0 加a t i o n ， s y n o p s i sd a t as t n l c t u r e ，c l u s t e r i n g i i l 重庆邮电大学硕士论文目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 论文选题背景1 1 2 研究现状2 1 2 1 数据流模型”2 1 2 2 数据流聚类4 1 3 主要研究内容”6 1 4 论文组织结构”7 第二章数据流的演化处理8 2 1 引言”8 2 2 时间衰减函数8 2 3 倾斜时间框架模型9 2 4 数据流挖掘算法的性能要求1 1 2 5 本章小结”1 2 第三章数据空间划分”1 3 3 1 引言1 3 3 2 数据分布状态1 3 3 2 1 概率表示法1 4 3 2 2 网格表示法1 5 3 3 基于概要结构的挖掘1 5 3 3 1 数据挖掘思路”1 5 3 3 2 网格概要结构1 6 3 4 内存控制策略1 7 3 4 1 索引结构1 8 3 4 2 混合结构”1 9 3 4 3 最小时间粒度“2 0 3 5 本章小结2 0 i v 重庆邮电大学硕士论文 目录 第四章基于统计信息的大粒度空间划分2 1 4 1 引言2 1 4 2 子区域数据分布状态2 1 4 3 子区域数据分布表示”2 3 4 4 紧密簇的获取分析一2 5 4 5 大粒度空间划分的可容忍性分析2 8 4 6 仿真实验2 9 4 7 本章小结3 0 第五章基于时空划分和统计信息的数据流聚类框架3 1 5 1 引言：3 1 5 2 两阶段挖掘框架3 1 5 3 在线阶段3 2 5 3 1 概要数据结构生成算法3 2 5 3 2s t s p 算法的理论分析3 3 5 4 离线阶段”3 3 5 4 1 聚类框架3 3 5 4 2 理论分析”3 4 5 5 实验测试3 4 5 5 1 演化测试3 5 5 5 2 去噪测试“3 6 5 5 3 执行时间测试3 7 5 5 4 内存需求测试3 8 5 6 本章小结”3 9 第六章总结及未来的工作4 0 6 1 总结4 0 6 2 未来的工作4 1 致谢4 2 攻硕期间从事的科研工作及取得的研究成果”4 3 参考文献4 4 v 重庆邮电大学硕士论文第一章绪论 1 1 论文选题背景 第一章绪论 数据流概念的提出源于近年涌现的一类新的应用，其主要特征是数据 在处理时的一次访问约束，如传感器网络、网络流量分析、股票交易价格 趋势分析、轨迹跟踪、科学与工程实验、网络日志和网页点击流、电信通 话记录等【卜5 1 ，数据以连续、快速、时变的方式到达，主动触发系统处理 数据，数据到达的顺序不可控制，数据量具有潜在的无限性i l 3 j 。 传统的d b m s ( d a t a b a s em a n a g e m e n ts y s t e m ：数据库管理系统) 并不是 为快速和连续装载单个数据元素而设计的【2 1 ，其用来管理存储大量的数据 元素，被动地工作于指令之下，不适合数据量潜在无限和主动触发处理的 数据流情形；其次，触发和报警功能在传统的d b m s 中没有受到重视；第 三，传统的d b m s 假设应用不需要实时服务【2 1 。因此有必要设计一种新的 数据处理系统，数据流处理也就成为一个研究热点。 数据流作为一种新的数据处理模型最初的研究主要面向数据流的近 似查询，如点查询和连续查询，预定义查询和即兴查询等1 1 ，5 】，随着一系 列以查询为主的数据流管理系统( d s m s ) 的实现，如斯坦福大学的s t r e a m 系统【6 ，7 l 、布朗大学和m i t 等研制的面向监控的a u r o r a 系统1 2 j 等，同时受 到数据挖掘研究的影响，数据流的研究重心逐渐转移到挖掘处理阶段，即 在流模型下进行数据挖掘研究。 数据流挖掘增加了数据一次访问约束和数据的处理权重问题，使其变 得相对复杂，也更具挑战性。对传统挖掘加以数据的一次访问约束，也可 视为数据流挖掘【5 1 。相对低层的查询处理而言，流挖掘和传统的挖掘具有 更多的相似性，查询处理将单个的数据作为独立的个体，事关大量的数据 对象，而挖掘操作考虑的是数据集合总体所表现出来的特征，将数据集作 为独立的处理对象。很多数据流挖掘算法源自对传统挖掘算法的改进。 聚类是一项基础性的数据挖掘操作，可以作为一项独立的数据处理技 术，也可作为其它挖掘操作的预处理阶段【引，因而显出其重要性和在数据 流模型下研究它的价值。传统的聚类给每个数据添加一个类标签，而数据 流环境下不保存数据，因此，聚类数据流是发现不同时间范围数据的聚类 特征或数据在空间的分布状态并有效的表示出来。 重庆邮电大学硕士论文第一章绪论 1 2 研究现状 最先将数据流作为一种数据处理模型提出来的是h e n z i n g e r 等人在 1 9 9 8 年发表的文章“c o m p u t i n go nd a t as t r e a m 【8 】”。从2 0 0 0 年开始，数据 流作为一个研究热点出现在数据库和数据挖掘领域，主要研究可以大致分 为两个方面：数据流管理系统( d a t as t r e a mm a n a g e m e n ts y s t e m s ，d s m s ) 和数据流挖掘例，d s m s 的研究主要集中在数据流查询，数据流挖掘方面 主要在于挖掘单流、多流以及变化的数据流。 数据挖掘是从数据中发现有趣的模式，挖掘任务可以分为两类：描述 和预测【6 1 ，预测性挖掘任务对当前数据进行推断，做出预测；描述性挖掘 任务描述数据库中数据的一般性质【5 1 。聚类属于描述性挖掘，它依据数据 间自身所体现出来的“相似性”将数据分为多个不同的簇。 1 2 1 数据流模型 数据流模型形式化表示为数据序列：。五圳置，x ，数据分别在时刻 。小，+ r 一到达，其中置为d 维数据，记为x ， 毫，x 工：，) 。数据流中的 每个数据作为独立的个体或事件参与在数据挖掘之中，数据在更高抽象层 上具有一致的意义，如属于同一类事物等，否则数据间不具备可比性，就 不能依据相似性进行数据的分类或聚类挖掘。 数据量的潜在无限性使得不可能将所有数据完全存储，有些应用中也 没有必要完全存储数据，数据到达主动触发系统处理，系统只有一次接触 数据的机会；其次，应用中往往对最近到达数据的兴趣度较大，故要考虑 数据的权重；第三，实时性要求算法的设计应尽量使用简单的运算。 由于以上制约，数据流的处理思路往往是从近段时间流过的数据中抽 取数据信息构建一个概要数据结构( s y n o p s i sd a t as t r u c t u r c ) ，在概要数据 结构上获得近似的处理结果，基于概要数据结构的查询是数据流的查询处 理的主流思路，如图1 1 所示，而数据流的挖掘并非如此，已有数据流挖 掘算法往往从数据中直接给出挖掘结果。 图1 1 数据流处理模型 2 口口口口口口口口口口口口口口口口口口口口 重庆邮电大学硕士论文第一章绪论 概要结构一般只保存最近时间段内到达数据的信息，如基于滑动窗口 构建的概要数据结构完全保存在内存，随着数据的到达实时更新之；而倾 斜时间框架将时间轴划分，保存粒度内数据的概要结构，时间越久远，粒 度越粗，全时间段保存数据信息以满足不同时间范围的近似查询。 从广义上说：如果处理过程中对任何或者大部分外界数据只需访问一 次，那么这样的处理系统就可以认为是数据流系统。现实应用中还可抽取 出其它三类也被学者称为“流 的数据流模型，数据表示属于同类事物的 个体，或个体随时间变化的状态，使数据流分为单流和多流模型。引进参 数d 表示数据维数和参数刀表示子流个数，以区别不同的流模型： 当万一l d 一1 ，一维数据单流模型； 当刀一1 ，d 1 ，多维数据单流模型； 当刀 l d 一1 ，一维数据多流模型； 当以 l d 1 ，多维数据多流模型。 ( 1 ) 一维数据单流模型又称为时间序列。聚类时间序列以发现频繁子序列 模式，如股票交易价格、传感器监测数据的变化模式等【1 0 d2 1 。模型用 离散曲线表示，如图1 2 所示。 图1 2 一维数据单流模型 ( 2 ) 多维数据单流模型是本文研究的数据流模型，数据作为直接处理对象 典型应用有网络入侵检测、网络流量分析、以及传统的一次数据扫描 的增量聚类等【1 3 2 2 1 。 ( 3 ) 一维数据多流模型是指多只时间序列，文献【2 3 2 7 】研究该类流模型的 聚类问题。典型应用如将价格具有相同变化趋势的股票分为一组，选 择不同组的股票组合投资，使投资风险最小化，模型如图1 3 所示。 时鼻u t时宣u t + w 图1 3 一维数据多流模型 t ( 4 ) 多维数据多流模型中厅 1 ，d 1 ，典型应用如运动物体按其轨迹实时分 成不同的簇1 2 引、基因片段按其空间结构的相似性分类等。为了叙述的 方便，以二维轨迹为例，设轨迹是由给定的相邻序列坐标构成的线段 3 重庆邮电大学硕士论文第一章绪论 组成。对于相似性计算， ( a ) 放缩 涉及到以下一些问题： 3 ( b ) 旋转( c ) 平移 图1 4 二维数据多流模型 i 放缩。如图1 4 a 所示：轨迹1 、轨迹2 的坐标按同比例放大或缩 小后，具有相似的轨迹： i i 旋转。如图1 4 b 所示：轨迹1 、轨迹2 、轨迹3 、轨迹4 、轨迹5 相互之间旋转一定角度后具有相似的运动轨迹； 1 1 1 平移。如图1 4 c 所示：轨迹2 向左平移x l 个单位，向上平移y h 个单位，二者具有相同的运动轨迹。 本文研究多维数据单流模型的聚类问题，相对而言，该模型更具一般 性，其它类数据流模型可以转换为多维数据单流模型。基于滑动窗口的时 间序列聚类被文献【1 0 】证明不能得到有意义的簇，故将时间序列列为流模 型的一种似乎不太合适；多维数据多流模型由于复杂性，强行转换为多维 数据单流模型也不太合理。因此对于聚类而言，单流多维模型至少蕴涵了 一维数据多流模型。 其次，多维数据单流模型的应用范围要广的多，入侵检测数据流、网 络点击流、通讯数据管理等【1 。3 1 ，现实中的事物往往需要从多个角度描述， 如数据库中的关系元组、面向对象方法中的对象等。 1 2 2 数据流聚类 在时间序列中发现频繁子模式是一项重要的应用，利用滑动窗口和更 新块生成子序列数据集，转换为多维数据单流模型，聚类之，得到的簇可 视作近似的频繁子序列模式。然而文献【1 0 】通过实验和理论分析得出基于 滑动窗口的时间序列聚类方法不可能发现有意义的簇，同时指出基于“基 序( m o t i f ) 的聚类方法在某些时间序列数续集上能够得到有意义的聚类结 果，文献【1 3 ，1 4 】分别提出了基于“基序 的获取算法，但再将之用于聚类 显然不满足数据的一次扫描约束条件。 多只时间序列的聚类主要是发现具有相似变化趋势的时间序列，利用 滑动窗口生成最新数据集，更新块即时更新数据确保数据集的时效性，处 4 重庆邮电大学硕士论文第一章绪论 理思路也是将一维数据多流模型转换为多维数据单流模型。文献【2 3 】基于 权重的增量维度相似性将多只数据流划分为多个组，将数据流当作数据 点，数据点的维度随数据的到达而增加，数据点中早期到达数据的权重随 时间流逝而降低：文献【2 4 ，2 5 】提出一种数据结构存储原始数据的压缩形 式，能够满足任意长度的时间窗口和演化速率的聚类查询；文献【2 6 】给出 了一种基于“事件”的聚类算法，自动发现异常或者满足条件的聚类或者 聚类的变化；文献【2 7 】基于一个足够“长”的能够表达出数据流变化趋势 的时间窗口，通过离散傅立叶变换降维，将多只流聚类成不同的簇，时间 窗口中的数据随新的数据到达不断更新。 多维数据多流模型是最复杂的数据流模型，大大增加了问题难度和计 算复杂性。文献【2 8 1 提出了一种轨迹的相似性检测算法，轨迹由不断到达 的坐标点表示，将具有相似运动轨迹的物体分进同一簇。通过复杂的转换 操作如平移、旋转、放缩或其变体，可将其转换为多维数据单流模型，然 而刻意的为了操作的统一而去做大量的工作似乎没有必要。 多维数据单流模型是研究的最多的数据模型【”之2 1 。其早期的聚类研究 受传统聚类思路的影响，把流的聚类简单地看成增量聚类问题1 1 6 】，算法采 用分治的原理【”d5 1 ，将数据划分为片段，利用k m e a n 算法聚类片段数据 获得簇心，当簇心积累到一定数量时，再利用改进的k m e a n 聚类之获得 个更高层次的簇；重复执行，生成一棵层次聚类树。文献【1 7 】给出了这类 算法性能在理论上的聚类保证。 应用中往往更重视最近到达的数据，最新得到的数据具有更高的处理 权重，即演化数据流。c l u s t r e a m 【1 6 j 是一种用户指定的，联机聚类查询的 演化数据流聚类算法，在线部分用微簇增量计算和存储数据流的汇总统计 信息，离线部分进行宏聚类，并利用存储的基于倾斜时间框架的汇总统计 信息来满足各种查询，微簇用聚类特征表示，聚类特征是b i r t h l 3 0 j 算法提 出的一个概念，其具备可加性，在数据流聚类分析中非常有用。 d e n s t r e a m 【1 8 】算法扩展划分和层次的方法，s t r e a m 【1 引、c l u s t r e a m 【1 6 】 和h p s t r e a m 【r 7 】等算法的主要问题在于：它们仅仅对球形的数据流进行聚 类分析时表现良好，但由于采用距离度量，它们不能很好地处理任意形状 的数据流。d e n s t r e a m 算法扩展了基于密度的方法d b s c a n 【3 2 】，着眼于处 理任意形状的数据流聚类问题。 d s t r e a m l 2 0 l 是基于密度和网格的算法。d s t r e a m 算法也着眼于任意形 状的数据流聚类问题，强调了孤立点探测，依据密度来判断聚类。d s t r e a m 算法同样分为联机和脱机两个部分。联机部分持续地读入新数据，将数据 5 重庆邮电大学硕士论文第一章绪论 映射到对应的网格单元中，更新密度网格的特征向量；脱机部分每隔一个 时隙动态地调整当前簇。初始簇在第一个时间隙后形成，此后算法周期性 地移除零星的簇、调节已经生成的簇。无需保留大量的原始数据，而仅仅 对网格进行操作，算法不会随着数据量的增大而变慢。但d s t r e a m 算法的 问题是划分粒度较小时，所生成的网格数量可能会非常大。 传统的增量式聚类算法有基于网格的聚类方法【3 6 q 4 1 ，典型特征是数据 的一次扫描和可并行执行。文献【3 6 】采用多层网格结构组织数据，每层网 格由低一层网格合并而成，主要支持数据查询任务；文献【3 7 3 8 】提出称为 c d s t r e e 的索引结构，c d s t r e e 仅索引出现数据的网格单元，对于倾斜 度很高的数据集有很好的效果，并且文献【3 7 】在大量数据集上实验，证明 了大多数数据集的倾斜度很高，即数据非均匀分布；文献【4 4 】是关于子空 间聚类算法的综述，详述了几种基于空间划分的子空间聚类算法。 b i r c h 【3 0 】算法是一经典的增量式聚类算法，是聚类算法处理大规模数 据集的一个突破1 39 1 ，对数据集线性扫描将数据压缩到一个位于内存中的 c f ( c l u s t e r i n gf e a t u r e ) 树中，b i r c h 提出的具有可加性聚类特征c f 的概 念，被后继算法广泛采用，c l u s t r e a m 【16 1 ，h p s t r e a m 【17 1 ，d e n s t r e a m 【1 8 】等。 本文的研究深受基于网格和b i r c h 方法的影响，尤其是网格算法的 一次数据扫描特性和聚类特征的可加性思想。 1 3 主要研究内容 流数据的潜在无限性和有限内存容量之间的矛盾就使得挖掘结果必 须在正确性和数据的保存之间进行平衡，获得近似而非精确的答案；很多 流应用假设计算设备比较简单，内存容量和处理器运算速度有限，而数据 流处理的实时性要求，故算法应尽量利用简单的计算。 采用时空划分的思想处理数据流。将时间轴划分成粗细不等的时间粒 度组织概要数据信息，划分最小时间粒度内到达数据形成的空间，保存每 个网格单元内数据个数及其它统计信息，粗时间粒度概要信息由细粒度的 可加性合并而成。 关键问题是如何控制内存需求，空间划分最大问题是划分粒度较小时 将产生大量的网格单元，从而需要大量的内存空间。所以基于空间划分的 内存控制策略是本文研究的重点，从两方面入手：网格单元的重组织和大 粒度空间划分的可容忍性研究探索，前者比较直观，后者相对于前者显得 6 重庆邮电大学硕士论文第一章绪论 更“柔性”一些。 1 4 论文组织结构 本文在行文上是这样安排的：数据流是包含时间属性的向量数据序 列，首先分析数据流与时间相关的问题，为挖掘保存不同时间断的数据信 息而又使存储的数据量很小；接着划分时间粒度内数据形成的空间，生成 一个保存数据分布状态的概要数据结构，重点探索基于空间划分的内存需 求控制策略。论文组织结构如下： 第一章介绍研究背景、各种数据流模型和数据流挖掘的研究现状，以 及本文所选择研究的流模型及原因。 第二章研究数据流与时间属性相关的问题，包括时间衰减函数和时间 倾斜框架等。 第三章分析采用空间划分思想处理数据挖掘问题的优越性和研究基 于网格单元重组织和最小时间粒度调整的内存控制策略。 第四章关于大粒度空间划分的可容忍性研究，引进统计信息，探索相 对大粒度划分的可行性。 第五章设计基于时空划分和统计信息的两阶段数据流处理框架，通过 仿真和测试实验，验证框架的获取数据流演化的聚类特征和去噪声效能， 比较不同概要结构表示法的执行时间和内存需求。 第六章对论文进行总结，提出下一步的研究计划。 7 重庆邮电大学硕士论文第二章数据流的演化处理 2 1 引言 第二章数据流的演化处理 数据流是带有时间属性的数据序列，数据流系统要处理与时间相关的 问题，表现出来就是要考虑数据的处理权重和应用查询的时间范围。数据 的处理权重依赖于数据的到达时间，一般随时间的流逝而衰减，应用中往 往对最近发生的事情更感兴趣，历史数据对即时挖掘的影响应可控。 数据的权重在处理过程中有两种方法体现出来：时间衰减函数和倾斜 时间框架。衰减函数周期的计算数据权重，比较连续地反映出处理权重的 变化。时间倾斜框架用不同的时间粒度保存不同时间段的数据信息，用粗 粒度存储时间久远数据的信息，用细粒度存储近期到达数据的信息，随着 时间的流逝，动态合并细粒度生成粗粒度数据信息。 本章分析数据流的数据权重处理方法，包括时间衰减函数和倾斜时间 框架模型，最后介绍数据流挖掘算法的性能要求。 2 2 时间衰减函数 用时间衰减函数模拟数据的演化过程，最近时刻到达数据的处理权重 越大，时间越远，处理权重越小，处理权重随时间的流逝而递减。类似放 射性元素的半衰期规律，定义时间衰减函数。 定义2 1 ：模拟流中数据权重的演化过程，时间衰减函数为： ，( f ) 一c 卜。( o ( () () () () () () () (x ) ( ) r、厂、厂、厂 、厂、 k # ，、 -# # ， rf、 一，一， ( a ) ( b ) 图4 51 单位粒度下的非理想划分 图中用实线圆表示真实的簇，虚线圆表示划分后得到的簇，存在着簇 心漂移的现象，图4 5 a 中簇心向右漂移了o 5 个单位，图4 5 - b 中簇心同 时向右和向下漂移了o 5 个单位，得到的并非真实的簇。 理想划分和非理想划分产生的原因在于无法准确得到数据的取值范 围。已有的算法往往通过读取部分数据，以此子数据集的取值范围作为全 局数据范围【3 9 1 ，划分之，因而产生误差。 在1 个单位划分粒度下，理想情形下能发现每一个真实的簇，每一个 簇包含在一个网格单元之中，然后通过统计信息获取簇的精确描述。传统 的空间划分用规则的“矩形”网格单元硬性地逼近簇，这种“矩形”当然 要小于簇。在引进统计信息后，理想情形下可以使得网格单元大于簇而精 确的发现簇，所以在同等精度下，引进统计信息后，相对大粒度空间划分 是可行的。 重庆邮电大学硕士论文第四章基于统计信息的大粒度空间划分 由于非理想情形出现的概率远远大于理想情形，能恰好包含每个簇的 网格单位的最佳划分粒度并不是合适的划分粒度，算法实现时采用的划分 粒度应比该粒度小，使划分后得到的网格单元至少要小于簇。 下面用0 5 个单位粒度划分数据空间，举例说明在小于最佳划分粒度 下可以比较精确的发现簇。划分粒度减小一半，在二维空间中，所需内存 空间最多增加4 倍。 在理想划分情形下，如图4 6 a 所示，o 5 个单位的划分粒度与1 个单 位的划分粒度所发现的簇和表示精度相同，只要划分粒度生成的网格单元 小于真实簇之间的最小空隙时，在理想划分和非理想划分情形下则都可以 发现真实的簇和获得精确的表示。 l234567l234567 飞hhh一飞 q yq y q y 沙 弋 hh 兔 h 、 yq yy弋 飞hhf飞 飞 q y 一q y弋y弋 )】【】 )】)1 )【)【) ( a ) 理想划分( b ) 非理想划分 图4 60 5 单位粒度的划分 在非理想划分情形下，如图4 7 - b 所示，划分粒度小于o 5 个单位时 总有多个相邻的网格单元，它们的密度要高于其它网格单元，合并之，合 并后的区域作为簇，能够保证合并区域内数据完全来自同一个簇。只是损 失了部分簇边缘数据和簇心出现漂移，但漂移局限在0 5 个单位的划分粒 度范围之内。 划分粒度大于0 5 个单元的划分，如0 7 个单位的划分粒度，如图4 7 所示，总能找到一个密度相对要高的网格单元，包含在该网格单元的数据 能够肯定属于同一个簇，而低密度网格单元的数据则很可能分属于多个相 邻的簇。 厂、厂 、厂、， 、 厂、厂、 厂 、7 ll 、 、， l 图4 70 7 单位粒度的划分 总之，对于划分粒度小于最佳划分单位时，总能发现真实的簇。对于 低密度网格单元，其内部数据可能分属多个簇，是不可分网格单元，其数 重庆邮电大学硕士论文第四章基于统计信息的大粒度空间划分 据一般属于簇的边缘数据，划分粒度越小，不可分数据越少。 基于上面的讨论，得出如下结论和设计准则：引进统计信息后，最佳 划分粒度在理想的情形下能够完全精确的发现簇，在实现中采用的划分粒 度一般应比最佳粒度要小。 上述讨论基于两个前提：一是可以获得数据簇的大小；二是每个簇的 数据分布均匀。通过统计信息生成的“球形”可以紧缩区域从而消减均匀 分布之限制，因为“球形 将数据分布范围向簇心收敛。对于簇的大小可 以根据经验值人为给出。 4 5 大粒度空间划分的可容忍性分析 数据空间中任意形状的簇，只要界线足够明显，用两种基本图形在相 对大粒度划分下都能比较精确的刻画出来。对多数簇而言，影响其刻画精 度的因素仅在于边缘的逼近，只用“矩形 时，划分粒度越小越精确的表 示簇，反之，则越不能精确的逼近边缘部分，所以，传统网格表示的精确 性与划分粒度成反比关系。“球形 大小由数据的实际分布决定，能够精 确和客观地反映网格单元内部数据的集中区域。 如图4 8 a 所示的簇，在两种基本图形的作用下，都能在大粒度划分 下精确的表示出来。 p f j q q f1 廿矿q7 舢 y 【二u h 弋9 门 u l = 一7 pr 1 1 j f ，输出网格单元统计信息f 6 。掌“- f 。，转 s t e p l ；否则，转s t e p l ； 组织概要数据结构的倾斜时间框架可在线处理，也可在离线阶段处 理。自然时间倾斜框架和对数时间倾斜框架的维护要反复的读取概要结 构，可在离线阶段处理；渐进对数倾斜时间框架在整个时间范围内生成概 要数据结构、在特定时刻输出概要数据结构，由于内存有限，涉及到网格 的删除。 5 3 2s t s p 算法的理论分析 对于每个数据，量化的时间复杂度为d ( 1 ) ；根据量化编号查找其所在 网格单元，设平均每个中间链表包含节点数为小，则查询特定节点的平均 时间复杂度为d 伽2 ) ，则查询一个网格单元的平均时间复杂度为 d 似小2 ) 。 5 4 离线阶段 离线阶段在组织概要数据结构的时间倾斜框架上挖掘各种感兴趣的 信息，更具用户需求，挖掘概要数据结构，以发现尽可能多的知识是离线 处理阶段的主要任务。 倾斜时间框架中隐含着数据分布的基本信息；每个子区域存储了数据 个数，数据在各维的线性加和、平方加和、最大值和最小值，利用索引结 构组织信息网格单元。离线阶段利用这些信息挖掘感兴趣的知识，也可根 据挖掘的目的，在网格单元中保存特定的信息。本节设计基于概要数据结 构的数据流聚类算法。 5 4 1 聚类框架 在概要数据结构上挖掘聚类特征是一个比较简单的过程，概要数据结 构保存数据在空间中的分布状态，是粗糙的聚类特征，在此基础上合并或 删除某些网格单元以获得界线清晰的聚类簇。 重庆邮电大学硕士论文第五章基于时空划分和统计信息的数据流聚类框架 根据4 2 节的分析，删除的网格单元应该是其中的数据分属于不同的 簇，这种情形可能发生于图4 1 a 所示分布状态，网格单元可能横跨了两 个或多个簇的边缘，其特征是其密度相对于周围网格单元的要低，由此可 以删除这类网格单元；接着合并相邻网格单元，以获得比较真实和精确的 簇，用一个或多个中心点表示簇。 算法5 2 ：基于概要数据结构的聚类算法 输入：概要数据结构s d s ，时间范围h ，密度阈值j d ； 输出：聚类特