（管理科学与工程专业论文）聚类分析与案例推理在数据流管理中的应用研究.pdf

聚类分析与案例推理在数据流管理中的应用研究 摘要 数据流挖掘是数据挖掘的一个新的研究方向，已经逐渐成为许多领域的有 用工具。传统数据库除非时间标记被事先定义，否则只能存储未被实现定义时 间的静态关系数据集。当这一模型在商业和个人信息中被广泛使用时，一些现 有的应用软件需要对快速变化的数据流进行在线分析和处理。传统数据库管理 系统在支持流应用时所表现出来的局限性已被广泛认识，这也促进了对改进现 有技术和建造新的流数据管理系统的研究。现有的数据流系统的开发主要是围 绕连续查询处理系统方面，而对于数据流挖掘方面的研究主要是对数据流系统 的查询结果再次进行其他智能操作，如案例库挖掘、聚类挖掘、智能决策分析 等。但很少有系统能够直接对数据流进行挖掘操作，这也大大降低了系统的实 用性。 由于众多应用领域的需求，近几年数据流处理问题，特别是数据流挖掘问 题已受到越来越多研究人员的关注。而现有数据流系统的局限性以及数据流的 单遍特性，导致很难有效地在海量的流数据中提取有用数据，并对其进行进一 步操作。因此本文研究的主要内容是对现有的数据流管理系统的性能进行评述， 并强调应用程序需求、数据模型、持续查询语言以及查询评估。在此基础上， 对聚类分析与案例推理在数据流管理中的应用前景进行研究，并提出一种高效 的数据流聚类算法和一个切实可行的对数据流进行查询、分析以及挖掘的数据 流管理系统模型。 本文提出了一种基于原有数据流系统、数据流聚类算法以及基于案例推理 的新的数据流管理系统。该方案首先对现有的数据流系统的查询结果进行动态 聚类分析，并从每一类中随机提取案例，形成所需要的案例库，为将来的进一 步挖掘提供前提条件。本文阐述了所提出的数据流聚类算法以及数据流管理系 统模型的基本构架，并在试验中得到了初步满意的结果。 关键词：案例推理，数据流管理，数据挖掘，聚类 c l u s t e r i n ga n dc a s e - b a s e dr e a s o n i n g i n d a t a - s t r e a mm a n a g e m e n t a b s t r a c t d a t a s t r e a mm i n i n gi san e wr e s e a r c ha s p e c to fd a t am i n i n g i th a sb e c o m ea u s e f u lt o o lf o rm a n yf i e l d s t r a d i t i o n a ld a t a b a s e ss t o r es e t so fr e l a t i v e l ys t a t i c r e c o r d sw i t hn o p r e - d e f i n e dn o t i o no ft i m e u n l e s st i m e s t a m p a t t r i b u t e sa r e e x p l i c i t l ya d d e d w h i l et h i sm o d e la d e q u a t e l yr e p r e s e n t sc o m m e r c i a lc a t a l o g u e so r r e p o s i t o r i e so fp e r s o n a li n f o r m a t i o n ，m a n yc u r r e n ta p p l i c a t i o n sr e q u i r es u p p o r tf o r o n l i n ea n a l y s i so f r a p i d l yc h a n g i n gd a t as t r e a m s l i m i t a t i o n so ft r a d i t i o n a ld b m s s i ns u p p o r t i n gs t r e a m i n ga p p l i c a t i o n sh a v eb e e nr e c o g n i z e d ，p r o m p t i n gr e s e a r c ht o a u g m e n te x i s t i n gt e c h n o l o g i e sa n db u i l dn e ws y s t e m st om a n a g es t r e a m i n gd a t a n o w a d a y st h em a i nr e s e a r c ho fd a t a - s t r e a mi ss e q u e n c eq u e r y , a n dt h em a i n r e s e a r c ho fd a t a - s t r e a mm i n i n gi sr e s e a r c ho nt h er e s u l to ft h ed a t a s t r e a ms y s t e m f o re x a m p l e ，k d c ( k n o w l e d g ed i s c o v e r yi nc a s eb a s e ) ，c l u s t e r i n g ，i n t e l l i g e n c e d e c i s i o na n ds oo n b u tn os y s t e mc a nm i n eo nt h ed a t a - s t r e a ms t r a i g h t l y i t sa l s o r e d u c i n gt h ef u n c t i o no ft h es y s t e m r e c e n t l y , b e c a u s eo ft h ed e m a n di nm a n yf i e l d s ，r e s e a r c h e r sp a ym o r e a t t e n t i o n st ot h ep r o b l e m so ft h ed a t a - s t r e a m ，e s p e c i a l l yt h ep r o b l e m so f d a t a - s t r e a mm i n i n g n o w a d a y st h ed i s a d v a n t a g e so fd a t a s t r e a ms y s t e ma n dt h e o d e - p a s so fd a t a s t r e a ml e a dt h a ti ti sh a r dt og e ta n dm i n eu s e f u ld a t af r o mh u g e d a t a - s t r e a m t h em a i nc o n t e n to ft h i sp a p e ri st or e v i e wr e c e n tw o r ki nd a t a - s t r e a m m a n a g e m e n ts y s t e m s ，w i t ha ne m p h a s i so na p p l i c a t i o nr e q u i r e m e n t s ，d a t am o d e l s ， c o n t i n u o u sq u e r yl a n g u a g e s ，a n dq u e r ye v a l u a t i o n a n dr e s e a r c ho ft h ec l u s t e r i n g a n dc a s e b a s e dr e a s o n i n g ( c b r ) a p p l yt ot h ed a t a - s t r e a mm a n a g e m e n t , p r o p o s e d a ne f f e c t i v ed a t a s t r e a mc l u s t e ra l g o r i t h ma n dad a t a - s t r e a mm a n a g e m e n ts y s t e m w h i c hc a l lb eu s e df o rq u e r y i n g ，a n a l y s i s ，m i n i n gd a t a s t r e a m i nt h i sp a p e r , w ep r o p o s ean e wm o d e lo fd a t a s t r e a mm a n a g e m e n ts y s t e m w h i c hb a s e do l ld a t a - s t r e a ms y s t e m ，d a t a - s t r e a mc l u s t e ra l g o r i t h ma n dc b r f i r s t l y , t h i sm o d e lc l u s t e r i n gt h er e s u l t so fd a t a - s t r e a ms y s t e m ，t h e ng e tc a s ef r o me a c h c l u s t e r , a n da d dt ot h ec a s eb a s et h a ti st h ep r e p a r a t i o nf o ra d v a n c e dm i n i n g t h i s a r t i c l ee x p o u n d st h em o d e lo fd a t a - s t r e a mc l u s t e ra l g o r i t h ma n dd a t a s t r e a m i i m a n a g e m e n ts y s t e m t h i si n i t i a le x p e r i m e n t a lp r o t o t y p eh a ss h o w nu sa s a t i s f a c t o r yr e s u l t k e yw o r d s ：c a s e - b a s e dr e a s o n i n g ，d a t a - s t r e a mm a n a g e m e n t ，d a t am i n i n g ， c l u s t e r i n g n l 插图清单 图2 1 一个神经元网络7 图2 2 一颗简单的决策树一8 图2 3s t r e a m 算法聚类示意图1 1 图2 4 金字塔时间窗口快照示意图1 2 图3 1c b r 的工作过程1 7 图4 1 分而治之思想示意图3 3 图4 2 数据流滑动窗口示意图3 4 图4 3 金字塔时间窗口快照示意图3 5 图5 1 数据流管理系统结构模式4 0 图5 2c f 树结构4 2 图5 3 一个不好的聚类4 3 图5 41 0 0 0 0 点下相同阈值的结果4 5 图5 51 0 0 0 0 0 点下相同阈值的结果4 6 图5 6 融入c b r 和动态聚类算法的数据流管理系统4 7 v l l 表格清单 表3 1c b r 系统及开发工具1 8 表4 1 聚类算法的比较3 1 表4 2 数据流聚类算法比较3 7 v i l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金目b 王些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所傲的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： i j 文 签字日期：w 7 年月，日 学位论文版权使用授权书 本学位论文作者完全了解盒b l 兰些盍堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘。允许论文被查阅和借阅。本人授权艘 王些盍堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 听奴 签字日期：砷7 年月f 吕 ， 学位论文作者毕业后去向： 工作单位：堵杈中啄嗜p 建并一聪磊匿观 通讯地址：蠹彪牛确曲块，7 专 导师签名： 钇幼 签字日期：如一年r 月“日 电话：，；5 铭77 p 参扣 邮编： ，o o ；i 致谢 在论文完成之际，首先感谢我的导师倪志伟教授，在三年的学习、论文写 作以及平时的生活中，导师给予我很大的关心和帮助，从论文的选题、研究、 项目的完成、小论文的发表、论文的撰写到论文的修改无不渗透着导师的智慧 和心血。倪老师渊博的知识、严谨的治学作风以及富于创新的学术思想，让我 在学业上受益匪浅，同时也培养了我踏踏实实研究学问的态度。在此，我谨向 导师致以崇高的敬意和衷心的感谢! 我要衷心感谢李锋刚博士生，黄玲博士生，李建洋博士生，以及我的同学 刘晓硕士生，李伟东硕士生，刘志伟硕士生，陶亮硕士生，赖建章硕士生，潘 永刚硕士生，刘烨硕士生。在学习和撰写论文的过程中，他们或者提供了宝贵 的资料，或者一起参与了探讨，使我受益匪浅。 我还要感谢合肥工业大学管理学院2 0 0 4 级研究生1 3 班的全体同学。他们 在近三年的学习和生活中给了我帮助和鼓励。 感谢各位评审专家在百忙之中抽出时间对论文进行了仔细的评阅l 借此机会，感谢我的父母，感谢他们给我健康的身体、勤劳朴实的作风、 上进的思想! 在母校度过了三年美好的大学生活，母校帮助我成长，感谢母校给予的一 切! 作者：忻凌 2 0 0 7 年5 月 第一章绪论 本文主要研究聚类分析与案例推理在数据流管理中的应用，因此必须 首先了解数据挖掘、数据流管理、基于案例推理以及聚类算法的相关内容。 数据挖掘( d a t a m i n i n g 。d m ) 就是从大量的、不完全的、有噪声的、模糊 的、随机的实际应用数据中，提取隐含在其中的，人们事先不知道的，但 又是潜在有用的信息和知识的过程【1 ) 。数据挖掘的技术很多，按发现知识 类型可分为关联规则发现，序贯发现，时序发现，离群分析，分类，聚类 等。 数据流由一系列按序到达的数据组成，也可看作是信息传输过程中经 编码处理的数字信号串【2 1 。数据流管理针对这些动态的产生的数据进行处 理。耳前数据流管理与挖掘的研究主要是从理论方面、联机算法的设计以 及数据流模型这三个方面进行的。 基于案例推理 3 1 ( c a s eb a s e dr e a s o n i n g ，c b r ) 是近十几年来人工智 能中新崛起的一项重要技术，并在一定程度上弥补了基于规则推理技术中 存在的知识获取的瓶颈问题的缺陷m 】。其核心在于用过去的实例和经验来 解决新的问题，这正好符合人类平常的推理习惯；解决新问题时总是在记 忆里搜寻以往的经验，试图找到一个与新问题相似的案例，然后把该案例 中的有关信息和知识应用到新问题的求解中。 聚类分析( c l u s t e r i n g ) 【5 】是依据样本问关联的量度标准将其自动分成 几个群组，且使同一群组内的样本相似，而属于不同群组的样本相异的一 组方法。一个聚类分析系统的输入是一组样本和一个度量两个样本间相似 度( 或相异度) 的标准。聚类分析的输出是数据集的几个组( 类) ，这些 组构成一个分区或一个分区结构。聚类分析的一个附加的结果是对每个类 的综合描述，这种结果对于更进一步深入分析数据集的特性是尤其重要 的。 1 1 相关背景 1 1 1 数据流管理 数据流由一系列按序到达的数据组成，也可看作是信息传输过程中经 编码处理的数字信号串【2 l 。令t 表示任一时间戳，q 表示在该时间戳到达的 数据。流数据可以表示成a “，a i l i 一) ，对应描述了一个隐函数 a ：【l 】_ 矗2 。 数据流问题已引起了广大科研学者的关注。二十世纪末期，国外开始 了数据流的研究热潮，目前已有一些系统项目闯世，如通用流系统等。但 在数据模式和查询语言中加入时间、顺序、窗口；实现近似计算操作的方 法如滑动窗口技术等；设计可以重新优化的适应性查询；适合于流操作的 调度策略；分布式查询的处理，数据流挖掘等熟点问题，尚没有产品原型 出现【6 】，需要进一步研究。近几年来，数据流问题开始受到国内学者关注， 但与国外的研究相比尚处于起步阶段【_ 7 ，s 】。 针对数据流以及持续序列设计的数据流管理系统具有以下特点1 9 ： ( 1 ) 数据模型和查询语义必须能够允许时间序列。 ( 2 ) 因为无法存储整个完整的数据流，所以需要模拟一个近似结构。 这样，查询将无法得到一个准确的结果。 ( 3 ) 流查询将无法使用阻塞操作，这样在获取结果之前必须输入全部 序列。 ( 4 ) 由于性能和存储容量的限制，放弃整个数据流是不可能的。在线 数据流算法必须获取所有数据。 ( 5 ) 数据流应用程序和监视器必须实时地、快速地对非正常数据做出 反应。 ( 6 ) 持续序列的共享操作需要保持可测量性。 1 1 2 基于案例推理 2 0 世纪9 0 年代以来，人工智能有两个方向发展：一方面，基于数据 挖掘和分析的计算智能；另一方面，在传统人工智能领域，基于规则推理 的方法在解决复杂领域或知识不完备领域的一些问题时，越来越显示出它 的不足，而基于相似性的推理则倍加受到重视，从而提出了基于案例的推 理方法。 c b r 是近十几年来人工智能中新崛起的一项重要技术，并在一定程度 上弥补了基于规则推理技术中存在的知识获取的瓶颈问题的缺陷。其核心 在于用过去的实例和经验来解决新的问题，这正好符合人类平常的推理习 惯：解决新闯题时总是在记忆里搜寻以往的经验，试图找到一个与新问题 相似的案例，然后把该案例中的有关信息和知识应用到新问题的求解之 中。 c b r 作为一种利用知识重用来解决问题的技术在众多领域取得了巨 大的成功 1 0 , l l 】，其主要思想是通过访问知识库中过去同类问题求解过程与 结果从而获得当前问题的答案。 2 1 1 3 聚类算法 聚类( c l u s t e r i n g ) 是将数据对象分组为多个类或簇( c l u s t e r ) 的数据 挖掘技术，聚类分析方法作为统计学的分支，在其多年的研究中主要集中 在距离的聚类分析上。这些方法已经在许多统计软件包中得到应用，例如 s p s s 和s a s 统计软件包中均有聚类方法在数据挖掘中，聚类分析主要 集中在聚类方法的可伸缩性、对聚类复杂形状和类型的数据有效性、高维 聚类分析技术以及针对大型数据库中混合数值和分类数据的聚类方法上。 1 1 4 国内外研究现状 近年来，越来越多的领域产生了数据流的应用，它不同于传统的存储 在磁盘上的静态的数据，而是一类新的数据对象，它是连续的、有序的、 快速变化的、海量的数据。典型的数据流包括网络与道路交通监测系统的 监测信息数据、电信部门的通话记录数据、由传感器传回的各种监测数据、 股票交易所的股票价格信息数据以及环境温度的监测数据等。数据流分析 是数据流研究的一个重要方向，目前的研究主要包括数据流聚类、分类、 频繁模式以及数据流o l a p 等。 二十世纪末期，国外开始了数据流的研究热潮，目前已有一些系统项 目问世，如通用流系统等。但在数据模式和查询语言中加入时间、顺序、 窗口；实现近似计算操作的方法如滑动窗口技术等：设计可以重新优化的 适应性查询；适合于流操作的调度策略；分布式查询的处理，数据流挖掘 等热点问题，尚没有产品原型出现1 6 】，需要进一步研究。近几年来，数据 流问题开始受到国内学者关注，但与国外的研究相比尚处于起步阶段 7 , 8 j 。 而关于c b r 的研究，国外起源于2 0 世纪8 0 年代初期，由r o g e rs h a n k 在1 9 8 2 年 ￥4 0 , 0 0 0 工作时何 5 年 八 氍风险 高风险 矗风险 低风险 图2 2一颗简单的决策树 决策树中最上面的节点称为根节点，是整个决策树的开始。本例中根 节点是“收入 ￥4 0 ，0 0 0 ”，对此问题的不同回答产生了“是”和“否”两个分 支。每个节点子节点的个数与决策树利用的算法有关，如c a r t 算法得到 的决策树每个节点有两个分支，称为二叉树，允许节点含有多于两个予节 点的树称为多叉树。每个分支或是一个新的决策节点，或是树的结尾，穆 为叶子。在沿着决策树从上到下遍历的过程中，在每个节点都会遇到一个 问题，对问题的不同回答导致不同的分支，最后会到达一个叶子节点。此 过程即为利用决策树进行分类的过程，利用几个变量( 每个变量对应一个 问题) 来判断所属的类别( 最后每个叶子会对应一个类别) 。 决策树是数据挖掘中的常用技术，可用于分析数据，也可用于预测， 常用算法有c h a i d 、c a r t 、q u e s t 和c 5 0 。 决策树极适合于处理非数值型数据，与神经网络只能处理数值型数据 比较而言免去了很多数据预处理工作但某些决策树算法是专为处理非数 值型数据而设计的，因而当采用此方法建立决策树同时又要处理数值型数 据时，就需要进行将数值型数据映射到非数值型数据的预处理工作。 ( 3 ) 其他技术方法 遗传算法：基于进化理论，并采用遗传结合、遗传变异、以及自然 选择等设计方法的优化技术。 近邻算法：将数据集合中每一个记录进行分类的方法。 规则推导：从统计意义上对数据中的“如果那么”规则进行寻找和推 导。 上述技术在很多专门的分析工具中已应用发展了近十年，但应用的数 s 悬 债知 据量还相对较小随着技术的不断成熟，在很多大型的工业标准的数据仓 库和联机分析系统中也已集成了上述技术。 2 2 数据流聚类算法研究 数据流聚类问题是指对实时的、持续的、有序的流数据进行聚类操作。 如何选择一种最佳的聚类算法，使它可以有效的对快速、大量产生的数据 进行聚类，是这一问题的关键所在自从2 0 0 0 年首次提出数据流聚类这 一概念之后【”】，这方面的研究己受到广泛的关注。现在的数据流聚类的研 究仍处在对传统聚类方法的基础上增量式聚类方法的研究【l 1 6 】或是将聚 类过程用在线和离线两个进程来实现 1 7 , 1 8 】，也有运用一些数学模型对在 线数据流进行聚类操作的【l ，1 ，但都缺少有效的方法同时保证准确和高效， 要在动态数据流中进行快速准确地聚类仍具有很大的难度。 2 0 0 3 年，b a r b a r t 对可用于数据流聚类的一些算法进行了研究，提出 了数据流聚类需要满足的3 个要求【2 0 】：紧密的表达；对新数据点快 速、增量的处理过程；清晰、快速地处理离群点。这也将是本文处理 闯题所要遵循的标准。 2 2 1 最小距离原则聚类算法 文献【2 卜2 2 】分别提出了针对分类属性数据和数值属性数据的最大相似 度或最小距离( 差异) 原则的聚类算法，不需要聚类个数的先验知识，扫描 数据集一趟即将数据分割为半径几乎相同的超球体。s q u e e z e r 算法【2 1 1 采用 不同属性值的取值频度来表示类，而文献 2 2 j 使用质心来表示类。算法的基 本思想是：初始时，聚类集合为空，读入一个新的对象；以这个对象 构造一个新的类；若已到数据库末尾，则转，否则读入新对象，利用 给定的距离定义，计算它与每个已有类间的距离，并选择最小的距离； 若最小距离超过给定的阈值r ，转；否则将该对象并入具有最小距离 的类中，转；结束。 2 2 2b i r c h 算法 b i r c h 是一个综合的层次聚类算法，它用聚类特征和聚类特征树( c f ) 来概括聚类描述，描述如下 定义：对于具有n 个d 维数据点的簇仉) 0 = 1 ，2 ，3 ，n ) ，它的聚类特 征向量定义为： 9 c f = 西船) 其中n 为簇中点的个数：西表示n 个点的线性和( 二； ，反映了 簇的重心，s s 是数据点的平方和( - i 2 ) ，反映了类直径的大小。 此外，对于聚类特征有如下定理。 定理；假设c 写= ( 1 ，碣，踊) 与c f 2 = ( n ：，丛：，s s 2 ) 分别为两个类的聚 类特征，合并后的新类特征为 讧+ c f , = ( l + 2 ，碣+ 如，蹈+ 鸡) 该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间 距离的运算。 c f 树是一个具有两个参数分支因子b 和阈值t 的高度平衡树，它存 储了层次聚类的聚类特征。分支因子定义了每个非叶节点孩子的最大数 目，而阈值给出了存储在树的叶子节点中的子聚类的最大直径。c f 树可 以动态的构造，因此不要求所有的数据读入内存，而可在外存上逐个读入 数据项。一个数据项总是被插入到最近的叶子条目( 子聚类) 。如果插入 后使得该叶子节点中的子聚类的直径大于阈值，则该叶子节点及可能有其 他节点被分裂。新数据插入后，关于该数据的信息向树根传递。b i r c h 算 法通过一次扫描就可以进行较好的聚类，故该算法的计算复杂度是d ( ，1 ) ，n 是对象的数且。 2 2 3s t r e a m 算法 s g u h a 等人在提出了基于k m e 缸s 的s t r e a m 算法【1 3 】，使用质心和 权值( 类中数据个数) 表示聚类。s t r e a m 算法采用批处理方式，每次处 理的数据点个数受内存大小的限制。对于每一批数据只，s t r e a m 算法对 其进行聚类，得到加权的聚类质心集g 。s t r e a m 算法采用分级聚类的方 法，如图2 3 所示，首先对最初的m 个输入数据进行聚类得到阢置) 个1 级带权质心，然后将上述过程重复m o ( k ) 次，得到m 个l 级带权质心， 然后对这i n 个l 级带权质心再进行聚类得到d 暖) 个2 级带权质心；同理， 每当得到m 个i 级带权质心时，就对这些质心进行一次聚类得到翻x ) 个 i + l 级带权质心；重复这一过程直到得到最终的o ( k ) 个质心。对于每个第 i + l 级带权质心而言，其权值是与它对应的i 级质心的权值之和 t o 图2 3s t r e a m 算法聚类示意图 2 2 4c i u s t r e a m 算法 c a g g a r w a l 。j h a n 等人在文献【1 7 】中提出了流数据聚类算法c l u s t r e a m ， 首次提出把数据流看成一个随时问变化的过程，而不是一个整体进行聚类 分析，该算法有很好的可扩展性，可产生高质量的聚类结果，尤其是在数 据流随时间变化较大时比其它算法产生更高质量的聚类。c l u s t r e a m 算法 不仅能给出整个数据流聚类的结果，还可以给出任意时间范围内的聚类结 果，以及进行数据流的进化分析。该算法由在线和离线两部分构成，在线 部分用m i c r o c l u s t e r 定时存储数据流的摘要信息，对数据的处理和更新是 增量式的，离线部分m a c r o c l u s t e r 通过对在线部分保存的中间结果的再处 理得到用户感兴趣的不同时间范围内数据漉的聚类结果。通常最近的数据 比历史数据更重要，为了既体现数据流进化的过程又不消耗过多的存储空 闻，c a g g a r w a 等人提出了倾斜时间窗口的概念，用不同的时间粒度对数 据流信息进行存储和处理，最近的数据变化以较细的时间粒度刻画，而离 现在较远的数据以较粗的时间粒度刻画。c l u s t r e a m 算法采用特殊的倾斜 时间窗口金字塔时间型时间窗口分级保存摘要信息 m i c r o c l u s t e r 是对b i r c h 算法中聚类特征树的一种带时序的扩充。对 于带有时间戳t i t k 的d 维对象x 1 x k ，其m i c r o c l u s t e r 定义为元 组：( c r 2 3 ，c f l l , c f 2 t , c f i , j ，其中n 为对象个数，c f r 、c f 2 1 是d 维 向量，分别表示n 个对象相应属性值的和与平方和；c 列、c f 2 分别表 示时间戳t l t k 的和与平方和。所有m i c r o - c l u s t e r 在某一特定时间点 上会作为整个数据流的快照保存。这些快照依照其生成时问t ( 从数据流 的第1 个点开始计对) 与当前时间的距离按不同的粒度级别保存到第1 至 第l o g 。( 乃层，第i 层只存储t 能够被a 整除的快照，其中口是一个给定的 整数白1 ) ；在任意时刻，对于第i 层，只保存最新的口+ j 个快照，其中，是 一一个给定的整数u 1 ) 图2 4 给出了，= 2 ，搿= 2 ，= 5 5 时的快照示意图。 c l o c kt 虹 5 s5 4s 35 25 l 5 45 2 5 0 4 84 6 5 2 档4 44 03 6 4 8 稠3 22 41 6 4 霉3 21 6 3 2 图2 4 金字塔时间窗口快照示意图 假设在任意时刻，算法在内存中保存q 个m i c r o ，c l u s t e r ( m l m 。) ， 并在创建m i c r o c l u s t e r 时赋予其惟一i d ( 合并m i c r o c l u s t e r 时，为新的 m i c r o c l u s t e r 刨建一个i d 列表，用于记录合并成此m i c r o c l u s t e r 的已有 m i c r o ，c l u s t e r 的i d ) 。算法初始化时，对最初的i n i t n u m b e r 个对象用标准 k m e a n s 算法聚类，得到q 个初始的m i c r o c l u s t e r ，这里i n i t n u m b e r 可以 在计算能力允许的情况下取尽可能大的值。初始化后，如果新的对象以落 到离它最近的m i c r o c l u s t c r m p 的最大边界之内，则将其加入m 。，否则为 丘创建一个新的m i c r o c l u s t e r 。在创建新的m i c r o c l u s t e r 后，为保持 m i c r o c l u s t e r 的数目q ，要删除一个最近最少使用的m i c r o c l u s t e r 或者合并 两个m i c r o c l u s t e r ( 通过存储在m i c r o c l u s t c r 中的时间戳信息来决定) 。 由于聚类特征具有可加性和可减性，使得只需从金字塔型时间窗口中 选择两个快照就可找出给定时间范围内产生的m i c r o c l u s t e r 。设用户查询 时间终点为t c ，时间窗口长度为h ，在金字塔型时间窗口内保存的t c h 之 前距t e - h 最近的快照为s 以一j l ) ，t c 之后距t c 最近的一个快照为s ( f c ) ，则 s 以) 中每个m i c r o c l u s t e r 都可通过它对应的i d 或者i d 列表在s ( 屯一| | i ) 找 到相应的m i c r o c l u s t e r ，然后将这些m i c r o c l u s t e r 的聚类特征相减就可得 到t c h 到t c 之间生成的m i c r o c l u s t e r 集纯，j | i ) ( ( 乙，= s ( t c ) 一s 也一 ，) ) 。 把以，h ) 看做带权值的数据点的集合，用改进的k - m e a n s 算法再进行聚类 就可得到这一时间范围内数据流聚类的结果。 利用聚类特征的可减性，可以很容易分析聚类进化的情况设用户给 定的时间长度h 和两个时间点t l 与t 2 ，计算编，n ( t 2 ，。通过比较 瓴，h ) ，n 也，| i ) ，很容易找出哪些m i c r o - c l u s t e r 在( t l ，h ) 和( f 2 ，h ) 中都出 现，哪些m i c r o c l u s t e r 只在其中的一个出现，由此可以分析数据流的进化 情况。 下面对前面提及的聚类算法的特点进行一个简单总结：时间复杂度 低、时效性好，具有好的可扩展性；采用摘要信息，也就是不同属性值 的取值频度或质心来简单地表示类，除c l u s t r e a m 算法外，其它算法没有 考虑时态特性。使得对动态变化较大的数据流聚类结果质量不理想；新 的对象到达时，不需要与过去的对象进行比较，而只需利用摘要信息进行 计算即可得到新的聚类结果；s t r e a m 算法和c l u s t r e a m 算法都采用分 治策略，将数据流中的对象划分成适当大小的块，分别对这些块进行聚类， 然后再将处理结果合并；s t r e a m 算法和c l u s t r e a m 算法都采用分级 聚类的思想，以k m e a n s 算法为基础，由一级或者多级聚类对象进行大规 模压缩，然后对压缩后的结果进行二次聚类得到最终结果；只能适用于 纯数值属性数据 1 7 以2 1 ，或纯分类属性数据f 2 ，不能适用于混合属性的数据， 而许多应用领域中的数据往往具有混合属性，这也是许多传统聚类算法存 在的问题。 2 3 数据流分类挖掘算法研究 在数据流分类方面主要是p d o m i n g o s 和g h u l t e n 的研究成果【2 孔2 4 】。 在文献【2 3 】中他们提出了一种改进的h o e f f d i n g 决策树分类算法v f d t ( v e r y f a s t d e c i s i o n t r e e ) ，使用恒定的内存大小和时间处理每个样本，有效地解 决了时间、内存和样本对数据挖掘，特别是高速数据流上的数据挖掘的限 制。v f d t 使用信息熵选择属性，通过建立h o e f f d i n g 树来迸行决策支持， 并使用h o e f f d i n g 约束来保证高精度地处理高速数据流。既可连续处理数 据，也可通过二次抽样，重新扫描数据集，因此可以处理非常庞大的数据 集v f d t 的另一个特点是增量式学习及随时可用性，它是一个实时算法， 在学习了最初的一些样本之后，就提供了一个随时可用、不断优化的决策 树。 v f d t 和其它大多数机器学习方法一样，假设数据是从静态分布中随 机获取的，不能反映数据随时问变化的趋势。因此，p d o m i n g o s 和g h u l t e n 在文献【2 4 】中引入了滑动窗口技术，对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 td e c i s i o nt r e e ) 算法，除了保留v f d t 算法在速 度和精度方面的优点外，增加了对数据产生过程中变化趋势的检测和响 应，使得算法更好地适应对高速时变流数据的分类。c v f d t 利用样本窗 口来有效维护决策树的更新和模式的一致性，然而它并不需要在每个新样 本到来的时候都学习新的模式，而是通过增加相应新样本的总数来更新充 分统计量，相应地减少滑动窗口中旧的节点数量。如果基本概念是静态的， 将不会产生影响；然而，如果概念是动态变化的，因为一个可替换的属性 有更高的增益，使得某些先前通过h o e f f d i n g 测试的分支不再起作用。在 这种情况下，c v f d t 开始在根节点用新的更好属性生成一棵用于替换的 子树，当这棵替换的子树在新的数据上比旧的子树更精确时，就用新的子 树代替旧的子树。 2 4 数据流频繁模式挖掘算法研究 频繁模式挖掘无论在理论还是应用方面均得到了广泛的研究并取得 了非常多的成果，出现了许多经典算法，如a p r i o r i 、f p - g r o w t h 、c l o s e t 、 c h a 。r m 算法，但这些算法难以增量式更新，不适合数据流挖掘。因为挖 掘频繁模式是一系列连接操作的集合，在看到所有过去和将来的数据之 前，任何项集的计算不可能完整地完成，使得在数据流环境中挖掘和更新 频率模式变得困难。与对静态数据集的挖掘相比，数据流有更多信息要追 踪和更复杂的情况要处理，频率项集会随时间而变化( 或者说是时间敏感 的、，非频率项在后来可能成为频繁项而不容忽视，存储结构需要动态调整 以反映频繁项集随时间进化的情况。在很多情况下模式的改变和它们的趋 势比模式本身更令人感兴趣，希望找出频繁模式随时间变化或进化的情 况。 针对数据流的频繁模式挖掘，文献【2 5 】提出了基于f p - t r e e 模型的有效 算法f p s t r e a m ，采用倾斜时阆窗口技术来维护频繁模式以解决时间敏感问 题。研究了在数据流中构造、维护和更新f p s t r e a m 结构的有效算法，提 出了计算和维护所有频率模式并动态更新它们。建立一个框架来挖掘带近 似支持度的时间敏感模式，为每个模式在多时间粒度上增量维护一个倾斜 时间窗口，在这种框架下可以构建和回答感兴趣的查询。f p s t r e a m 结构由 两部分组成：一个用来捕获频繁和准频繁项信息的频繁模式树；为每 个频繁模式提供的倾斜时间窗口表。 文献【2 6 】提出了一种利用有限存储空间通过一趟扫描来估计数据流中 最大频繁项集的算法，该算法采用了称为“c o u n ts k e t c h ( 概要计数) ” 的数据结构，使得可在流中可靠地估计频繁项集的频率。 目前提出的算法均是近似算法，对数据进化不能很好地体现，特别是 当模式变化较快时，准确性受到极大影响。 2 5 数据流挖掘方法所面临的问题 从本章的描述我们不难看出，目前的数据挖掘方法很多，但可以应用 于数据流挖掘的算法与技术却很少问题主要集中在如何改进现有的数据 挖掘技术，使其能够适应于数据流的动态与单遍特性。本文将在后面的章 节着重讨论这一问题，并在第五章提出一种具有针对性的解决方案。 1 4 2 6 本章小结 在数据流挖掘中，数据摘要或模型表示、趋势检测、异常检测是关键 技术。基于目前数据流挖掘的现状，以下方面的研究将得到更多的关注： 针对数据流高维时态混合属性的特点，寻找新的适于数据流的数据结构 和建模方法，研究有效度量数据相似性的方法；研究针对数据流的高效 异常挖掘算法；研究数据流基于时间变化的特性，探索数据流变化的表 示与建模方法，挖掘数据进化和变化的趋势；研究数据流基于约束的聚 类分析；研究数据流的局部周期挖掘算法。 第三章基于案例推理 案例推理【3 】( c a s e - b a s e dr e a s o n i n g ，c b r ) 是由目标范例的提示而得到 历史记忆中的源范例，并由源范例来指导目标范例求解的一种策略，它是 一种重要的机器学习方法。c b r 是区别于基于规则推理的一种推理和学习 模式，它是指借用旧的事例或经验来解决问题、评价解决方案、解释异常 情况或理解新情况。c b r 兴起的主要原因是传统的基于规则的系统存在诸 多缺点，如知识获取的瓶颈问题，对于处理过的问题没有记忆，导致推理 效率低下，处理领域中例外事件格外困难，整体性能较为脆弱，等等。而 c b r 恰好能很好地解决以上问题。 3 1c b r 概述 c b r 是指利用过去经历的典型事例( 称为案例) 求解或理解当前问题， 即处理问题时不是从零开始考虑各种细节及其关系，而是依据过去的典型 事例做适当调整以处理当前问题。因而又称之为“即时推理”( i n s t a n t r e a s o n i n g ) ，适合于知识缺乏或知识过于复杂但经验又相对丰富、稳定的 领域。 3 1 1c b r 的起源和概念 案例推理的概念第一次由耶鲁大学r o g e rs c h a n k 教授在其1 9 8 2 年的 著作 d y n a m i cm e m o r y ) ) 中提出并描述。他在对人类认知科学的研究过程 中，提出了教本的知识表示概念。并提出了基于m o p s ( m e m o r y o r g a n i z a t i o n p a c k e r s ，记忆组织包) 的动态记忆理论。这个理论被认为是最早的关于 c b r 思想在人工智能领域中的描述。 1 9 8 3 年佐治亚工学院的j a n e tk o l o d n c r 教授，基于动态存储模型和 m o p 理论，开发了第一个真正意义上的c b r 系统c y r u s 。从事机器学习 方面研究的德克萨斯大学教授p b r u c ep o r t e r 开发了知识表示结构的系统 p r o t o s ，将领域知识和特定的知识整合在一起。p r o t o s 系统被应用在 临床诊断中，通过对病人的检查情况对疾病进行分类。 c b r 的研究起源于从认知科学的角度对推理和学习机制的探索过程。 认知心理学研究认为基于过去案例的推理是人类最常用的学习和解决实 际闯题的办法，比基于规则的推理更接近人类的