（管理科学与工程专业论文）时态数据流的增量聚类算法研究及其应用.pdf

浙江工业大学硕士学位论文 时态数据流的增量聚类算法研究及其应用 时态数据流的增量聚类算法研究及其应用 摘要 聚类分析是数据挖掘领域一项重要的研究课题。近年来，随着 计算机和应用技术的高速发展，人们获得数据的能力有了极大的提 高，同时获得的数据途径也越来越多。数据流( d a t as t r e 锄) 作为一 种特殊的数据来源，越来越备受关注。如w e b 点击流、气象观测 信息流、电话记录信息流、卫星数据流等。由于数据流的数据量无 限、对算法的响应要求很高，而且通常只能对数据访问一次，而传 统的聚类算法对快速变化的数据流进行在线分析的支持存在着很多 限制，因此急需开发适应数据流环境的聚类算法。一计算机工作者们 面临着新的挑战。 本文针对时态数据流进行了研究，给出了时态数据流的概念和 定义，同时在s u b s p a c ea - c l u s t e r 的基础上提出了t m s c ( t e m p o r a l m u l t i p l e d i m e n s i o ns u b s p a c ec l u s t e r ) 聚类算法来查找聚类，该算法采 用了滑动窗口的形式，使得算法能保证无须针对所有时间点的数据 同时进行聚类，减少了算法所需空间开销；同时有增量保持阶段， 增量阶段无须重复计算之前的数据，只需处理新到达的相关数据， 因此增量处理快；最后把算法用j a v a 实现后，应用到了股票数据中， 通过不同的参数设置，找到了不同时间段的聚类，有其一定意义。 l 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 t m s c 算法的主要创新之处为：1 ) 从只能处理单维数据流扩展 到了多维数据流；2 ) 改进了聚类剪枝标准；3 ) 对从m 1 e v e l 查找 m + 1 1 e v e l 的聚类给出了明确的定义和证明；4 ) 发现了原先算法在 增量更新阶段将会漏掉的聚类结果，通过保留所有聚类结果，解决 了这一问题。 关键词多数据流，聚类分析，数据挖掘，时态数据流，州s c 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 t h e a p p l i c a t i o na n dr e s e a r c ho f i n c r e m e n t a lc l u s t e r i n go nt e m p o r a ld a t a s t r e a m s a bs t r a c t c l u s t e ra 1 1 a l y s i si s 锄i m p o r t a l l ta r e ao fd a t am i n i n g i nr e c e n ty e a r s ，惭t 1 1t h e 1 1 i 曲s p e e dd e v e l o p m 锄to fc o m p u t e rt e c h n 0 1 0 9 y ，t l l ea b i l i t yt 0a c c e s st 0t h ed a t ah 嬲 伊e a n yi m p r 0 v e d t h e r ea r em o r ea l l dm o r e 印p r o a c ht oa c c e s st 0d a t a d a _ t as 仃e 锄， 邪as p e c i a ls o u r c eo fd a 魄h a sc a u s e d 如i n c r e a s i n gc o n c e m t h e r ea r em a l l yl 【i n d s o fd a t as t e 锄s ，s u c ha sw e bc l i c k 蛐r e a m ，w e a _ t 1 1 e ri n f o r n l a t i o n ，t e l e p h o n er e c o r d s i o m l a t i o n ，s a t e l l i t e 胁s 乜e 锄s b e c a u s et h ed a t a 昀陀锄h a sa j lu i l l i m i t e d 锄o u i l t o fd a 锄dy o ua r en o ta l l o 、e dt oa c c e s st l l ed a t as e v e r a jt i m e s ，t h e 缸a d i t i o n a l a 崦o r i t l l m sc a i l td e a l 、析t ht 1 1 ep r o b l e m w en e e dt od e v e l o pn e wa l g o r i t h mt 0d e a l 、柝mt l l ed a t as t r e 锄a sar e s u l t ，c o m p u t e r 、o r k e r sa r ef a c i n gn e w c h a l l e n g e s i nm i sp a p t e m p o r a ld a t as 讹a n l sh a v eb e e ns t i l d i e d t h ec o n c e p t 锄d d e f i l l i t i o no fd a t as 臼e a ma r eg i v e ni nt h ep a p e r a tt h es 锄et i m e ，w ep r o p o s ea t m s c ( t e m p o r a lm u l t i p l e d i m e n s i o ns u b s p a c e 仅- c l u s t e r ) c l u s t e r i n ga l g o r i t l l mt 0 f i n dc l u s t e d n gb a s e do nas u b s p a c e0 【一c l u s t e r t h et m s ca j g o r i t u l lu s e ss l i d i n g 、访n d o wt oe n s u r em a tw ed o n tn e e dt od e a l 诵t 1 1a l lt h ed a t aa tt h es 锄et i m e a tt 1 1 e 鼢m et i m e ，t h e r ei sas t a g eo fm a i n t 撕nt h ea l g o r i t h mw h i c hi sc a l l e di n c r e m e n t a l s t a g e i nt l l ei n c r e m e n t a ls t a g e ，t 1 1 e r ei sn on e e dt or e c a l u t et h eo l dd a t a t h en e w 枷v a ld a t ai st h eo n l yp a r t 也a tw es h o u l dc o n c e m a sar e s u l t ，t l l ei n c r e m e n t a lt i m e a r el e s st 1 1 柚t r a d i t i o n a la l g o r i t h m s t h el a s tp a no ft h ep a p e ri st h ea p p l i c a t i o no ft h e a l l g o r i t l l i i lt os t o c kd a t a w eu s ed i a e r e ms e to fp a r a m e t e r st of i n dan u m b e ro f d i f r e r e n tc l u s t e r si nt l l es t o c kd a t a t h er e s u l t ss e n s em e a l l i n g 如1 t h em 面ni 肋o v a t i o l l so ft m s ca 】g 硎t h mi n c j u d e ： 1 )e x p a n d i n g疔o m o n e - d i m e n s i o n a ld a t as t e 锄t ot l l em u l t i - d i m e n s i o n a ld a _ t as t r e 锄；2 ) i m p r o v i n gt h e c l u s t e rp 枷n g ；3 ) g i v i n gac l e a rd e n n i t i o nf 而mm - l e v e lt of i n dt t l em + 1 一l e v e l i i l 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 c l u s t e r i n ga n dp r o v i n gi t ；4 ) t h eo r i g i n a la l g o r i t h mi nt h ei n c r e m e n t a lu p d a t es t a g e 、析nm i s sc l u s t e r s ，w es o l v et h ep r o l e mt h r o u g l lr e s e r v ea l lt h ec l u s t e r s 1 皿yw o l m s ：d a t as 仃e a m s ；c l u s t e r i n ga i l a l y s i s ；d a 协m i n i n g ；t e m p o r a ld a t a s t r e 锄s ；t m s c 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均己在文中以明确方式标明。本人承担本声明的 法律责任。 储虢夯啤垮 吼m 年嘲；f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 强牌锄 立矫 日期：占；，年( 2 ，月，1 日 日期乏- 中年f 2 - 月 1 日 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 l 绪论 本章阐述了数据流挖掘以及时序( 态) 数据挖掘的研究背景以及有关的技 术，分析了其研究现状，探讨了在数据流挖掘方面的研究，引出了本文所要研 究的内容。 1 1 选题的目的和意义 由于数据收集、数据库系统技术以及万维网的迅速发展，使得各种数据有 了爆炸性地增长。因此，数据挖掘面临的一个重要的课题就是流数据、时间序 列数据的挖掘。 想像一下一颗人造卫星在天空中，他通过传感器不断的接收数据，然后发 送到地面，这个数据就是海量的、按照时间排序的、快速变化并且应该是无限 的。 所谓数据流就是大量连续到达的、潜在无限的数据的有序序列，这些数据 或其摘要信息只能按照顺序存取并被读取一次或有限冽。 对于静止的数据，数据挖掘过程可以分成两个部分：先把数据收集起来存 储在数据库中，然后在数据库上应用各种挖掘技术进行挖掘。而对于数据流， 它的收集过程和挖掘过程是同时进行的，我们必须以最快的速度，从不断到来 的数据中挖掘出感兴趣的模式( i m e r e s t i n gp a n e m ) ，来响应用户的实时查询， 一数据流挖掘的特点决定了它比传统的数据挖掘要复杂，因此一般我们在数 据流挖掘中要解决以下一些主要问题： ( 1 ) 必须设计高效算法，具有较快的响应时间；因为数据流到达迅速，如果 响应时间太慢，新的数据已经来临，该算法就失去了有效性； ( 2 ) 算法对内存的要求不能太高，由于流数据本身就是连续不断产生的大量 数据，本身读取的数据流就很大，所以必须对内存的要求不能太高，同时要充 分利用内存； ( 3 ) 尽可能采用一遍扫描算法； ( 4 ) 挖掘应该是一个在线的、连续的过程，而不是随机的过程【l 】。 目前，数据流挖掘的成果主要集中在数据流的聚类、分类及频繁模式挖掘 上，已经出现了一些典型的数据流挖掘算法，其中聚类问题是流数据挖掘中的 热点。 但是，针对多数据流的挖掘，特别是在子空间方面的文章一直较少，所以 本文希望针对多数据流进行在线子空间聚类，该算法必须是动态的、增量的， 同时运算效率必须够高。 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 孟志青在2 0 0 0 年对时态数据采掘中的时态型与时间粒度进行了研究1 2 1 ，提 出时态型、时间粒度等概念，使得对时间的刻画有了理论依据和标准。在数据 流中引入时态的概念以后，会使得算法更加清晰、明了。 本文结合时态数据以及数据流的概念，提出了时态数据流。同时问题集中 在多条时态数据流的问题上，采用多维子空间口一d “s f p ，方法和滑动窗口的形 式进行聚类，同时也将对其时间属性进行一定形式的变形。之前有很多数据流 的挖掘1 3 “5 j ，都是把整个滑动窗口内部的一条数据流作为聚类对象进行聚类。 也就是说，一旦滑动窗口确定，小于滑动窗口这个时间段之内的相似类可能就 无法发现。这样子的聚类算法其实意义不大，因为很多时候，聚类的分布时间 长度是不确定的，a 和b 在1 月份可能属于同一个类别，在2 月份上半个月属 于不同类别，下半个月又属于同一个类别了。如果采取以1 个月为标准的滑动 窗口，那么2 月份就很难发现其中的类别规律了。因此，应该查找一个更好的 聚类方法，当我们把滑动窗口放大，他可以查找到滑动窗口内部任意长度的聚 类，本文将要采取的聚类方法就是这么一种方法，称之为聊s c ( t e m p o r a l m u l t i p l e d i m e n s i o ns u b s p a c ec l u s t e r ) 方法。 1 2 相关概念 1 2 1 数据挖掘 一卜竺竺! 竺写 图1 1 数据挖掘作为k d d 的一个步骤 简单地说，数据挖掘( d a t am i n i n g ) 是指从大量数据中提取或“挖掘”知识。 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 实际上数据挖掘这个词有点用词不当，在砂石和砂子中挖掘黄金称作黄金挖掘， 而不是砂石挖掘，所以，数据挖掘应该被命名为“从数据中挖掘知识”，遗憾的 是这个词有点长。但是如果说是“知识挖掘 呢，又不能体现挖掘是从大量的 数据中。但是因为挖掘这个词很生动的表现了从大量的、未加工的材料中发现 少量宝贵“金块”这一过程特点。这样，数据挖掘就成了流行术语1 6 j 。 许多人把数据挖掘视为另一个常用的术语数据库中的知识发现或l d ( k n o w l e d g ed i s c o v e d ，i nd a k 出a s e ) 的同义词，而另一些人只是把数据挖掘当作 知识发现过程的一个基本步骤。知识发现的过程如图1 1 所示。 在产业界、媒体和数据库研究界，术语数据挖掘比长术语数据库中的知识 发现更流行，所以一般都是以数据挖掘来代替数据库中的知识发现。 1 2 2 时序( 态) 数据挖掘 传统的数据挖掘很少考虑到时间适用性。而事实上，每个数据挖掘结果都 有其成立的时间范围，因此，在进行数据挖掘时，如果能把时间因素考虑进去， 将会更有价值。一 一 一 现实世界是随着时间不断演化的，时间是事件的基本属性。现在，大多数 数据库应用程序都有时态的特性，例如电话公司的记录，张三在2 0 0 8 年9 月1 日早上8 点打了一个长途电话给李四，在同一天1 0 点又打了个电话给王五，这 些事件按照时间发生前后组合在一起就是时间序列数据。时间序列数据是一组 观测的数据序列，通常是按时间顺序排列，而时态数据是在观察到的时间序列 进一步加工变形的包含时间属性的数据，时间序列数据可以作为时态数据的特 例。股市每日指数、交换机每小时的业务量、某一患者的脑电波和w e b 页的 日访问量、年太阳黑子数等等，这些都是比较常见的时间序列的例子。 如果直接对时间序列数据进行分析，可能难以得到很好的结果，因此我们 都会对时间序列数据进行变形，转化为时态数据。对时态数据进行分析，从中 获取所蕴含的关于生成时间序列的系统的演化规律，以完成对系统的观测及其 未来行为的预测，这在工程应用中具有重要的价值和意义。最早的时态数据挖 掘可以追溯到时间序列分析。天气预报、财经或股票市场的预测是最老的、研 究最多的时间序列数据。时态数据挖掘是在时间序列分析之后产生的。比较有 名的时间序列分析是由博克思( b o x ) 和詹金斯( j e i l l 【i n s ) 于7 0 年代初提出自回归 滑动平均模型a i w a 和差分自回归滑动平均模型a 融m a ，这两个模型的主要 作用是做出预测。时间序列分析和时态数据挖掘的第一个主要区别是时态数据 挖掘必须能够处理大量的数据集合。他们的第二个区别在于我们希望从数据中 得到的信息。舢m 队模型是希望得到每个决策变量的系数或者是权重，而时态 数据挖掘则远远不止这些。时态数据挖掘不仅希望得到预测信息，有时也希望 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 得到描述信息。 1 2 3 数据流 在应用中，人们遇到大量的、源源不断的数据，这些数据往往是动态的、 连续的、有序的、无限的数据集合，他们只能被按顺序访问，且仅能被扫描一 次或有限的几次，我们把这种数据集合称作数据流【7 l 。 时间序列数据流s 是由s 【1 】，s 【2 】，组成的，随着时间增加，新的值不断 增加到序列的尾部。举个例子，用来监控温度的传感器每五分钟会出产生一个 新的值，由这些值组成的就是一个时间序列数据流。想象一下，一辆装着g p s 设备和通讯工具的汽车，他每l o 分钟向服务器传送一次他的位置，那么由两个 维度( x 和y 代表他的位置) 组成的时间序列流立即产生了。注意，时间序列 数据流是根据到达时间顺次排序的，后到达的值总是放在时间序列的尾部。 没有数据的时候，人们希望得到数据来进行研究，可是现在面对排山倒海 的数据，人们又开始束手无策。正由于此，众多学者纷纷开始对数据流算法进 行深入研究。由于数据流本身的特点使得传统的算法不能直接应用于数据流。 传统的数据挖掘算法根本不能处理如此庞大的数据量很大，因此需要一种动态 的增量式的算法来处理数据流。并且，数据流到来的速度很快，多数应用要求 在数据到来的同时进行分析决策，这对算法的处理时间提出了更高的要求。 要想对数据流进行处理，首先必须建立相应的数据流模型。令t 表示任一 时间戳，a t 表示在该时间戳到达的数据，数据流可以表示成 ，a i 1 ，a i ，a i + l ，) 。根据a i 的不同特点，数据流模型可分为以下3 类瞵j ： ( 1 ) 时间序列数据流。用来描述时间序列数据，如每分钟纳斯达克 ( n a s d a q ) 成交量、每2 分钟所观测到的i p 流量。a i 与历史数据无关，他 只跟当前的值相关。令c i 为最新一个时刻产生的值，这里的a i 可以定义为： a i 2 c i o ( 2 ) c a s hr e 西s t e r 数据流。这种模型应用非常普遍，如超市的收银机记录、 对i p 地址的流量监控等。当前的值总是在前一时刻的值的基础上，加上最新 时刻产生的值。这里的a i 可以定义为：a i = a i 1 + c i ，且c i = 0 。 ( 3 ) t u m s t i l e 数据流。这种模型可以记录动态的插入和删除操作，如记录拥 挤的地铁站中乘客的人数。这里的a i 可以定义为： a i = a i l + c i ，c i 可以大于 0 ，也可以小于0 。 在本文中研究的是时间序列数据流。 4 浙江t 业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 1 2 4 数据流挖掘 数据流挖掘是数据挖掘的组成部分，只是数据流挖掘有了特定的对象 数据流。由于数据流有很多特性，所以要对数据流进行挖掘就存在很多注意事 项。 1 2 4 1 大纲数据结构 为了有效地处理数据流，需要建立新的数据结构、技术和算法。因为我们 没有无限大的空间去存储数据流，就需要在正确性和存储空间之间进行平衡。 大纲( s ) r 1 1 0 p s e s ) 是指算子内部一种特殊的数据结构，用于保存有状态算子的 状态信息。大纲可以提供数据的概要描述，可以为查询提供近似结果。大纲使 用大纲数据结构，是比基本的数据集合( 数据流) 小得多的数据结构。 常用的大纲数据结构和技术有1 9 j ： ( 1 ) 随机抽样 抽样作为一个经典的统计学方法，通过一定概率来决定一个数据元素是否 被处理。这样可以避免处理整个数据流。但是在数据流模型中，抽样技术的问 题是不可能预先知道流的长度。可以使用水库抽样( r e s e o i rs 锄p l i n g ) 的技术 来解决这个问题：在“水库”中维护s 个候选的样本，形成目i j 看到的流的随 机样本集，随着数据流的流动，新的数据元素都有一定的概率替代水库中的元 素。在数据流中使用抽样技术的另一个问题是数据流的流动速率是不稳定的。 所以，对于那些需要监测不规则且上下浮动的数据流的应用，抽样技术并不是 一个很好的选择。 ( 2 ) 滑动窗口 可以使用滑动窗口模型对数据流进行分析，而不是对数据流进行随机抽样。 其基本思想是：仅仅基于最近的数据做出决策，而不是对目前为止看到的所有 数据或对某个样本进行计算。 ( 3 ) 直方图 直方图是一种大纲数据结构，可用来近似数据流中元素值的频率分布。直 方图把数据划分为一系列相邻的桶。依照使用的划分规则，宽度( 桶的值域) 和深度( 每桶里的元素个数) 可以是不同的。 ( 4 ) 多分辨率方法 处理大数量数据的一种常用方法是使用数据规约的方法。一种流行的数据 规约方法是采用分治策略，如多分辨率数据结构。这些方法允许程序在准确性 和存储之间进行权衡，同时也提供在多层细节理解数据流的能力。 平衡二叉树就是一个具体的例子。离树的根部越远，这一层的分辨率就越 浙江工业大学硕十学位论文时态数据流的增量聚类算法研究及其虑用 细。同理，离根部越近，分辨率就越粗。 在多分辨率方法中，经常采用小波技术。小波是一种信号处理技术，可以 用来构建输入信号的多分辨率层次结构。 ( 5 ) 梗概 梗概是一个将数据流中的数据向量做一个随机投影的过程。它建立这些分 布向量( 如直方图) 的小空间汇总。梗概广泛用于不同数据流的比较和聚集查 询。梗概是对精度和存储空间进行折衷的极佳范例，但是同时，精度问题是它 的主要缺陷。 ( 6 ) 随机算法 随机算法以随机抽样和梗概的形式，常常用来处理海量、高维数据流。与 确定算法相比，随机选择的算法往往使算法更简单、更有效。 如果一个算法总是返回正确的回答，但是运行时间不确定，则称他为拉斯 维加斯( l a sv e g a s ) 算法。相反，蒙特卡洛( m o n t ec 矾o ) 算法的原型时间有 上界，但是可能无法返回正确的结果。可以把随机算法看成是一系列确定算法 的概率分布。 数据流的主要处理方法到此为止，如果读者有兴趣，可以查看文献【9 】，该 书本中有很多关于数据流处理方法更细节的东西，下面开始对数据流立方体的 介绍。 1 2 4 2 数据流立方体 从概念上讲，对于多维分析，可以将数据流看成一个虚拟数据立方体，由一 一个或多个度量和维集合组成，包括一个时间维和几个其他维，如位置、用户 类别等等。实际上，物化这样的数据立方体根本不可能，因为需要计算和存储 海量数据。为了系统地分析这种数据，必须开发有效的方法。 数据流分析与关系数据仓库分析的根本不同在于数据流大量产生、动态流 入流出、并且快速变化。由于有限的内存、硬盘空间和处理能力，不可能完全 记录细节层数据和计算完全物化的立方体。一个现实的做法是利用多种数据压 缩技术，包括在时间维上倾斜时间框架、仅在某些关键层存储数据、利用部分 物化的数据立方体的有效计算【9 j 。这样构造的数据流立方体比原始的数据流构 造的立方体要小得多，但对于多维流数据的分析仍然十分有效。 ( 1 ) 倾斜时间框架 在数据流分析中，通常人们对细尺度上的当前变化感兴趣，但在粗尺度上 对长期变化感兴趣。自然地，人们可以在不同粒度层上记录时间。最近的时间 在最细的力度上记录；较远的时间在较粗的力度上记录；粗略程度取决于应用 需求和时间点是有多老( 从当前时间点算起) 。这样的倾斜时间维模型叫做倾斜 6 浙江工业人学硕七学位论文时态数据流的增量聚类算法研究及其应用 时间框架( t i l t e dt i m ef - 姗e ) 。有很多方法用于涉及倾斜时间框架。比如：自然倾 斜时间框架模型，对数尺度倾斜时间框架模型，渐进对数倾斜时间框架模型。 这些具体的东西可以参见文献【9 】。 ( 2 ) 关键层 即使使用倾斜时间框架模型，对于数据流挖掘所需的空间仍然很大。由于 流数据分析受内存空间的限制，又需要快速的响应时间，因此，需要其他策略 和倾斜时间框架模型进行配合，其中一种方法就是关键层。关键层就是仅计算 和存储整个数据立方体中与任务相关的方体桫j 。 在许多应用中，动态增量地计算和存储两个关键方体( 或层) 是有好处的， 这是由他们在数据流分析中的概念和计算重要性决定的。第一层叫做最小兴趣 层，是分析人员想要研究的最小兴趣层。考察数据流中的微小细节既没有成本 效率，也没有实际意义。第二层是观察层，是分析人员希望不断研究数据的层。 基于这种设计，不需要计算低于最小兴趣层的任何方体，因为他们不在用 户的兴趣范围之内。 ( 3 ) 流立方体的部分物化 如果用户需要介于两个关键层之间的层次怎么办? 一个有用的方法是常用 路径立方体计算( p o p u l a r p a t l lc u b i n g ) ，它通过一条常用的下钻路径，从最小兴 趣曾到观察层执行上卷操作，仅仅物化该路径中的层次，其它层仅在需要的时 候计算。这种方法在空间，计算时间和灵活性上取得了适度平衡，并具有快速 增量聚集时间、快速下钻时间，并且空间需求最小1 9 】。 1 3 国内外研究现状 1 3 1 数据挖掘 国际上第一次关于数据挖掘与知识发现的研讨会于1 9 8 9 年8 月在美国的 底特律召开，在此会议( 第1 1 届国际联合人工智能学术会议) 上第一次提出了 “知识发现一词。到目前为止，由美国人工智能协会主办的k d d 国际研讨 会已经召开了1 7 次，规模由原来的专题讨论会发展到国际学术大会，研究重点 也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种 学科之间的相互渗透。最近的一次是在2 0 0 8 年1 月份在澳大利亚召开的。 目前，世界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e 印r i s e m i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i i l e r 、s p s s 公司的 c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 、 还有c o v e r s t o 巧、e x p l o r a 、k n o w l e d g ed i s c o v e r yw 6 r k b e n c h 、d b m i n e r 、q u e s t 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 等。可以说国外的数据挖掘已经发展称为一个产业，很多厂家、研究人员都在 做数据挖掘的工作。 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国 家自然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单位和 高等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大学、 中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京 系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大 学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、 中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算 法的优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究 了非结构化数据的知识发现以及w 曲数据挖掘。 1 3 2 时态数据挖掘 时态数据不仅只是在传统的数据上加上时间维，同时也描述了不同数据之 间相互转换的时间过程。时态数据的特点决定了时态数据挖掘以及挖掘所发现 的只是都具有自身的特点。目前，国内外对时态数据挖掘的研究比较零散，没 有形成系统的理论框架，因此要对时态数据挖掘做出十分系统、细致的分类还 很难做到。目前，对时态数据挖掘的主要研究方向有： ( 1 )时态关联 某事件在时间上紧随另一事件发生并不_ 定就意味着这两者之间存在某种 因果关系，但它们之间又存在一定的关联关系，例如股票的涨跌模式。时态关 联定义的是事件间的继发关系，例如顾客在超市在购买了牛奶后又购买了面包。 对于关联的研究己有很多，如单维的关联、多维的关联、单层次的关联、 多层次的关联、量化的关联、基于距离的关联等等。当前的时态关联研究大多 将已有的关联分析运用到时态数据中，主要研究了关联规则成立的时间范围 【1 0 】【1 1 】【1 2 1 ，提出了一些时间区间的合并与延展技术【13 1 ，提出的一些时态关联挖掘 的算法，大都是基于a 研o r i 算法的变形。 文献【1 4 】提出了时态关联规则挖掘的若干性质。在文献【2 】提出了时态数据 挖掘中的时态型和时间粒度，使得时态数据挖掘的时间属性得以规范。 ( 2 )周期性挖掘【i 副 目前周期模式挖掘问题可以分为3 类：( 1 ) 挖掘全周期模式，它是指每一时 间点都影响着时序上的循环行为。例如数学上的正弦函数，是由每一个点来确 定周期的。( 2 ) 挖掘部分周期模式，它描述部分时间点的时序周期。例如小李每 天早晨7 ：0 旺7 ：3 0 读人民日报，而其他时间没有什么规律。( 3 ) 挖掘周期 关联规则，这种规则是周期出现的事件的关联规则。例如，设时间单位t 为小 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 时的关联规则：牛奶一面包具有周期c ( 2 4 ，7 ) ，即每天早上7 ：0 0 一8 ：0 0 有 关联规则牛奶叶面包成立。第三种周期模式挖掘可以在找到时态关联规则后， 很方便的查找到。 ( 3 ) 趋势性挖掘 趋势性时态数据挖掘与传统的时间序列分析比较类似，甚至可以说就是时 间序列分析。但它已经不在只是根据经济学的模型进行研究，而是加上了数据 挖掘的部分，这里采用的比较多的数据挖掘技术是神经网络。 趋势性挖掘是对各种变化的分析，有长期趋势变化、循环变化、季节性变 化、随机变化。 ( 4 ) 序列模式挖掘 序列模式挖掘的目的是发现蕴含于有序事务序列中的频繁序列模式。一个 典型的序列模式的例子是：两个月前购买了i b m 一电脑的顾客，现在很有可能 购买h p 打印机。令x 代表“购买i b m 电脑，y 代表“购买h p 打印机， 则上述序列模式可形式化为x y ，注意x ，y 的顺序是十分重要的，因为y x 则代表一个意义完全不同的模式，即“两个月前购买h p 打印机的顾客，现 在很有可能购买i b m 电脑1 1 6 1 。 序列模式( s e q u e n t i a lp a t t e m ) 挖掘算法的研究始于a g r a 、v a l 对超市数据的 分析【1 7 】。早期的绝大多数序列模式挖掘算法都采用一种宽度优先的搜索模式， 如a 皿o r i a l l 【1 刀，g s p 【1 8 1 等，这些都是基于a p r i o n 的水平格式的序列模式挖掘 或者与时间相关的频繁模式挖掘。后来，z a ki 提出了一种基于垂直格式存储 的序列模式挖掘方法s p a d e 算澍1 9 1 ，该算法由基于垂直格式的频繁项挖掘演 化而来。近几年，乩气n 等人又提出一种基于投影的模式增长算法f r e e s p 髓 算法【2 0 】【2 1 】，该算法改进后为p r e 做s p 锄算法【2 2 1 ，性能进一步提高。 ( 5 ) 时态约束问题 在现实中，用户关心的往往是某一时间区域的数据而不是整个数据。通过 加上时态约束，可以使我们从大量的数据中解脱出来，从而关注那些真正重要 的数据。在数据挖掘中加上时态约束可以起到过滤数据、聚焦用户目标以及加 速知识模式生成等作用。 文献【2 3 】给出了时态区间代数的概念，定义了时态区间变量交与并操作， 挖掘用户给定时态区间内的时态约束规则。 时态数据挖掘的综述部分到此为止，下面开始讲述数据挖掘中最常用的聚 类方法。 1 3 3 数据流挖掘 国外在数据流挖掘方面有两个比较有影响的研究小组：一个是s t a n f o r d 大 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 学的r m o t 、a n i 教授领导的研究小组，另一个是u l u c 的c a g g a n a l 和j h a i l 教授领导的研究小组。前者的研究侧重在数据流管理、数据流的连续查询和数 据流的聚类方面【2 帕7 1 。提出了不同于传统d b m s 的d s m s ( d a t as t r e 锄 m 锄a g e m e n ts y s t e m ) 概念，他们的研究得到了美国国家自然科学基金的资助。 后者的研究侧重在数据流分析方面，对于数据流的在线分析，从聚类、分类、 频繁项集挖掘以及可视化等角度做了大量研究工作【2 8 】【2 9 】【3 0 】【3 1 1 ，提出了倾斜时间 窗口( t i l t e dt i m e 诚n d o w ) 策略，采用不同时间粒度保存数据流的信息，他们的研 究得到了美国军方和国家自然科学基金的资助。 目前数据流挖掘方面的研究成果主要有1 7 】： ( 1 ) 聚类 尽管聚类问题在数据库、数据挖掘和统计等领域得到了广泛研究，流数据 的分析仍为聚类算法提出了前所未有的挑战，由于完整甚至部分地存储过去数 据的方法不可行，需要能够只使用新数据就能够追踪聚类变化的算法，这就要 求算法必须是增量式的，对聚类表示要简洁，对新数据的处理要快速，对噪音 和异常数据是稳健的。因为数据流可看成是随时间不断变化的无限过程，其隐 含的聚类可能随时问动态地变化而导致聚类质量降低。近年来，有学者提出了 应用于大规模数据集的一趟扫描聚类算法，如s q u e e z e r 算法和b i r c h 算法， 它们可以应用于某些数据流问题，也有学者提出了针对流数据的聚类算法，典 型的有s t r e a m 算法和c l u s 仃e 锄算法。 ( 2 )分类 在数据流分类方面主要是p d o m i n g o s 和g h u l t e n 的研究成果。在文献 【3 2 】中他们提出了一种改进的h o e f d i n g 决策树分类算法v f d t ( v e 珂f a s t d e c i s i o nt r e e ) ，使用恒定的内存大小和时间处理每个样本，有效地解决了时间、 内存和样本对数据挖掘，特别是高速数据流上的数据挖掘的限制。v f d t 使用 信息熵选择属性，通过建立h o e f d i n g 树来进行决策支持，并使用h o e 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 在文献3 4 1 中引入了滑动窗口技术，对v f d t 算法进行改进，提出了c v f d t ( c o n c 印t a d a p t i n g v e r y f a s t d e c i s i o n l r e e ) 算法， 除了保留v f d t 算法在速度和精度方面的优点外，增加了对数据产生过程中变 化趋势的检测和响应，使得算法更好地适应对高速时变流数据的分类。 c v f d t 利用样本窗口来有效维护决策树的更新和模式的一致性，然而它 l o 浙江工业大学硕十学位论文时态数据流的增量聚类算法研究及其应用 并不需要在每个新样本到来的时候都学习新的模式，而是通过增加相应新样本 的总数来更新统计量，相应地减少滑动窗口中旧的节点数量。如果基本概念是 静态的，将不会产生影响；然而，如果概念是动态变化的，因为一个可替换的 属性有更高的增益，使得某些先前通过h o e f d i n g 测试的分支不再起作用。在这 种情况下，c v f d t 开始在根节点用新的更好属性生成一棵用于替换的子树， 当这棵替换的子树在新的数据上比旧的子树更精确时，就用新的子树代替旧的 子树。 ( 3 )频繁模式挖掘 频繁模式挖掘无论在理论还是应用方面均得到了广泛的研究并取得了非常 多的成果，出现了许多经典算法，如a 研o r i 、f pg r o 、砒、c l o s e t 、c h 删算 法，但这些算法难以增量式更新，不适合数据流挖掘。因为挖掘频繁模式是一 系列连接操作的集合，在看到所有过去和将来的数据之前，任何项集的计算不 可能完整地完成，使得在数据流环境中挖掘和更新频率模式变得困难。与对静 态数据集的挖掘相比，数据流有更多信息要追踪和更复杂的情况要处理，频率 项集会随时间而变化( 或者说是时间敏感的) ，非频率项在后来可能成为频繁项 而不容忽视，存储结构需要动态调整以反映频繁项集随时间演化的情况。在很 多情况下模式的改变和它们的趋势比模式本身更令人感兴趣，希望找出频繁模 式髓时间变化或进化的情况。 针对数据流的频繁模式挖掘，文献【2 9 】提出了基于f p 讹e 模型的有效算法 f p s 仃e 锄，采用倾斜时间窗口技术来维护频繁模式以解决时间敏感问题。在文 中，研究子在数据流中构造、维护和更新f p s 仃e 锄结构的有效算法，提出了一 计算和维护所有频率模式并动态更新它们。同时，它还建立一个框架来挖掘带 近似支持度的时间敏感模式，为每个模式在多时间粒度上增量维护一个倾斜时 间窗口，在这种框架下可以构建和回答感兴趣的查询。 f p s 讹a n l 结构由两部分组成：一个用来捕获频繁和准频繁项信息的频 繁模式树；为每个频繁模式提供的倾斜时间窗口表。文献【3 5 提出了一种利 用有限存储空间通过一趟扫描来估计数据流中最大频繁项集的算法，该算法采 用了一种特殊的数据结构使得可在流中可靠地估计频繁项集的频率。 文献【3 6 】中提出的算法是近似算法，对数据进化不能很好地体现，特别是 当模式变化较快时，准确性受到极大影响。 1 4 研究动机 众所周知，聚类已经是一份十分重要的工作了。对于挖掘时态数据流来说， 聚类就是一个更大的挑战了。新的数据随时都会到来，聚类结果就必须随着时 间的演进而更新。所以，必须采用增量聚类算法来处理时态数据流。 浙江工业大学硕士学位论文时态数据流的增量聚类算法研究及其应用 滑动窗口机制是指在指定长度的窗口内部，可以任意的访问窗口内部的数 据进行聚类。滑动窗口的大小定义的是时间序列时间维度的长度。如果滑动窗 口增大，那么聚类很可能失败，因为随着滑动窗口的增大，两个不同的数据流 属于同一个类的可能性也将降低。可以想象一下，以两个同学的考试成绩为例， 在几个月内，两个人的成绩可能都属于同一个类别，比如a ，但是随着时间增 长，很多外界因素加上去以后，肯定会有这种情况发生，一个考好了，一个考 差了。如果考虑到这种情况，在一次考好，一次考差的时候，肯定不能把他们 作为同一个类别来看待。那么，大多数情况是怎么样的呢? 是这样的：两个人 在一段时间内，可能考试成绩是属于同一个类别的，然后一段时间不是，过了 一段时间，可能又属于同一个类别了。回到数据流上，就是：两个或者多个数 据流虽然在整个滑动窗口不属于同一个类，但是在滑动窗口的内部某个时间段 却是属于同一个类别的。 一 什么是聚类? 聚类就是把对象分成相似的组的过程。如何判断是否相似 呢? 通常都是采用相异度的概念。而对于区间标度变量，采用的最多的就是欧 几里得距离d ( f ，) = ( 薯l x ，1 ) 2 + ( 2 一x ，2 ) 2 + ( 一x 加) 2 。 聚类过程就是为了使距离小的数据在同一个集合中，距离大的在不同集合 中。但有些时候会出现这样的问题：虽然有些数据最后聚集到了一个类别，但 是，他们之间的相异度还是很大，即有些数据之间差异很大，如果人工进行分 类时，肯定不会把他们分为同一个类别中。我们可以看一下下面这个例子。 假设有1 6 个数据，分别是1 到1 6 ，顺序输入，采用k 均值聚类方法后， 输入参数k 为3 ，即有3 个集合。得出的结果是集合为3 个 1 ，2 ，3 ，4 ，5 ) ， 6 ，7 ，8 ，9 ，1 0 ) ， 1 l ，1 2 ，1 3 ，1 4 ，1 5 ，1 6 ) 。可以看到，l 和5 属于同一个集合，而5 、6 却属于不同的集合。这样聚集出来的聚类似乎不大符合人们的正常思维。很多 时候，我们可以这么做：把距离小于等于某个特定的数值的点作为一个类别。 只是，这个时候与之前有一个区别，就是一个数据点不一定只属于一个