（计算机软件与理论专业论文）数据流聚类算法的研究.pdf

数据流聚类算法的研究 摘要 网络等信息技术的迅速发展和广泛应用产生了大量的数据流，如：超市交 易记录，网络搜索请求，电信通话记录，卫星探测和天文观测科学研究数据等， 这些数据流中隐含着丰富的有价值的知识亟待挖掘。聚类算法研究作为数据挖 掘的一个重要分支，在处理具有快速性、无限性、连续性、多变性等特征的流 数据时，面临着巨大的挑战。 传统的聚类算法大多需要多遍扫描数据库以及存储全部数据，构建的模型 或方法不再适宜处理流数据环境中的数据，而针对丰富的流数据源探索新的聚 类模型和方法，进行有效的预测和聚类具有重要的现实意义。本文的主要研究 内容如下： 1 本文提出一种有效的数据流二次聚类算法( t c l u s a ) ，以提高对数据分 布不规则和含有噪音时的数据流聚类的质量。t c l u s a 是基于分区思想，使用 d b s c a n 方法对每块分区数据聚类删除离群点以每个簇的均值点作为其代表 点，得到局部聚类结果，再用k m e a n s 方法对所获得的代表点进行聚类获得最 终结果。 2 现实世界中的数据流往往是混合属性，但现有算法往往局限于仅处理一 种属性，而对其它类型的属性采取简单舍弃的办法，降低了算法的精度。为此， 本文提出一种针对混合属性的基于网格的数据流聚类算法，使用一种基于几何 邻接和信息增益的混合类型数据相似度量方法，可以有效的对混合属性进行处 理。 关键词：数据流；聚类；混合属性；网格 i i t h er e s e a r c ho nc l u s t e r i n ga l g o r i t h mo fd a t as t r e a m a bs t r a c t w i t ht h er a p i dd e v e l o p m e n ta n db r o a da p p l i c a t i o n so fi n f o r m a t i o nt e c h n o l o g i e s ， s t r e a m i n gd a t ah a v eb e c o m eu n i v e r s a l ，s u c ha ss u p e r m a r k e tt r a n s a c t i o n s ，i n t e r n e t s e a r c hr e q u e s t s ，t e l e p h o n ec a l lr e c o r d s ，d a t af r o ms a t e l l i t e sa n da s t r o n o m ye t c b e c a u s es t r e a m i n gd a t aa r ec o n t i n u o u s ，h i g h - v o l u m ea n do p e n e n d e d ，t r a d i t i o n a l m i n i n ga l g o r i t h m sc a n n o tm i n ed a t a b a s e sf r o mt h e s ed a t ae n v i r o n m e n t si nr e a l t i m e ， w h i c hl e a dt ot h el o s so fu s e f u li n f o r m a t i o n c l u s t e r i n gi so n eo ft h em o s ti m p o r t a n t b r a n c h e so fd a t am i n i n g ，b u ti ti sac h a l l e n g et op e r f o r mc l u s t e r i n gi nd a t as t r e a m s w i t ht r a d i t i o n a lc l a s s i f i c a t i o nm o d e l s m o s to ft r a d i t i o n a lc l u s t e r i n ga l g o r i t h m sn e e ds c a n n i n gt h ed a t a b a s e sm u l t i p l e t i m e sa n dn e e ds t o r i n gt h ee n t i r ed a t a ，w h i c ha r en o ts u i t a b l ef o rt h es t r e a m i n g e n v i r o n m e n t s h o w e v e r , i ti sv e r ys i g n i f i c a n ta n dv a l u a b l et oe x p l o r et h en e w m o d e l so fc l u s t e r i n ga n dm e t h o d sf o rp r e d i c t i o na n dc l u s t e r i n gi nr e a l w o r d a p p l i c a t i o n s t h em a i nc o n t e x t sa r ea sf o l l o w s ( 1 ) i no r d e rt oe n h a n c et h ep e r f o r m a n c eo fn o i s ya n du n b a l a n c e dd a t as t r e a m s c l u s t e r i n g ，a ne f f e c t i v ed o u b l e - c l u s t e r i n gc l u s t e r i n ga l g o r i t h m ( t c l u s a ) b a s e do n t h ep a r t i t i o nm e t h o di sp r o p o s e d t c l u s a ，w h i c he m p l o y sd b s c a nt oa c h i e v e s u b c l u s t e r i n gr e s u l t sb yu s i n gt h em e a n so f e a c hb l o c ka f t e rd e l e t i n go u t l i e r s t h e n ， t h ef i n a lr e s u l t sw i l lb ea v a i l a b l ew i t hk m e a n sm e t h o db a s e do nf o r m e rb l o c k s ( 2 ) m a n yd a t as t r e a m s i np r e s e n tw o r l dh a v em i x i n ga t t r i b u t e s ，w h i c hh a v e b o t hn u m e r i c a la t t r i b u t e sa n dd i s c r e t ea t t r i b u t e s h o w e v e r , t h ee x i s t i n gm e t h o d sa r e o f t e no n l yo r i e n t e dt oo n ek i n do fa t t r i b u t e ，a n do t h e ro n e sa r es i m p l yg i v e nu p ， w h i c hd e c r e a s et h ep r e c i s i o n t h i sp a p e rp r e s e n t sad a t as t r e a mc l u s t e r i n g a l g o r i t h m f o rm i x i n ga t t r i b u t e sb a s e do nt h eg r i d ，u s i n gak i n d o fg e o m e t r i c a a ja c e n e ya n di n f o r m a t i o ng a i n f o u n do nm i x i n gd a t as i m i l a r i t y , w h i c hc a n e f f e c t i v e l yd e a lw i t ht h em i x i n ga t t r i b u t e s k e y w o r d s ：d a t as t r e a m s ；c l u s t e r i n g ； h e t e r o g e n e o u sa t t r i b u t e ； g r i d i 插图清单 图5 1a d u l t 数据集上h g s t r e a m 和e l u s t r e a m 算法的聚类精度比较3 3 图5 2p o k e r h a n d 数据集上h g s t r e a m 和e l u s t r e a m 算法的聚类精度比较3 3 图5 3k d d e u p 9 9 数据集上h g s t r e a m 和c l u s t r e a m 算法的聚类精度比较3 4 图5 4a d u l t 数据集上h g s t r e a m 和e l u s t r e a m 算法的运行时间比较3 4 图5 5p o k e r h a n d 数据集上h g s t r e a m 和e l u s t r e a m 算法的运行时间比较3 4 图5 - 6k d d e u p 9 9 数据集上h g s t r e a m 和c l u s t r e a m 算法的运行时间比较3 5 v i i 表格清单 表4 - 1 算法k s c d c 和t c l u s a 的时间性能和聚类质量比较2 5 表5 1h g s t r e a m 和c l u s t r e a m 算法在不同数据集上的平均聚类精度比较3 3 v i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究j ：作及取得的研究 成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得合肥工业大学或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 一酶誓穆期：沙广午月莎日 学位论文版权使用授权书 本学位论文作者完全了解 合肥工业大学有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借 阅。本人授权合肥工业大学可以将学位论文的全部或部分论文内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：带】江哆 菩字日期：沙1 年够月矿日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 1 u 影 形 口“_纠，门计幼， l ：期名日签字 巾 峄聊签 致谢 两年半的硕士研究生生活即将划上句号，在这三年的学习和生活中，老师、 同学、亲人、朋友们给予我的关心和帮助将永远珍藏在我心灵最深处。 首先，我要感谢我的导师胡学钢教授。胡老师治学严谨、工作踏实、知识 渊博、思维开阔，学术见解新颖独到。我在硕士期间所取得的成绩，离不开胡 老师的悉心指导和鼓励。胡老师在这两年半中以他在数据挖掘领域深厚的理论 基础和对研究方向前瞻的把握，指引我从事科学研究，让我的科研之路少了很 多的荆棘与曲折。此外，胡老师一直以来不断教导我们做人的真谛，要热爱生 活、热心工作，并身体力行，这种耳濡目染的熏陶和教化无疑将是我一生受用 无穷的宝贵财富。 另外，我要感谢吴信东教授。吴老师作为国际数据挖掘领域的知名专家， 对该领域有着极其深刻且高瞻的理解和领悟，其高屋建瓴地指点和教导，让我 对学术科研之思路、方法有了更加深刻地认识。另外，吴老师严谨治学的态度 和真诚朴实的作风使我更加明晰了为人之道。 还有，我要感谢吴共庆老师、张晶老师和张玉红老师，他们的谆谆教导和 倾力相授让科研阶段的沟壑变成坦途；另外，感谢谢亮、薛峰、李星华、谭拮、 郑锦良、朱珠、潘春香和尹倩，与他们的交流和讨论拓宽了我的视野和思路。 感谢0 7 级与0 8 级的师弟师妹们，与他们一起学习生活的点点滴滴都是愉快而 难忘的。 最后，我要感谢我的家人，感谢他们这么多年来一如既往的无私关怀，不 仅从物质上给予鼎力支持，更从精神上赋予无尽的关爱，鼓舞我战胜困难、不 断前行。没有他们，就没有我的全部。 i v 作者：曹永照 2 0 0 9 年2 月15 日 第一章绪论 数据收集和数据存储技术的快速进步使得各组织机构可以积累海量数据。 然而，提取有用的信息已成为巨大的挑战。通常，由于数据量太大，无法使用 传统的数据分析工具和技术处理他们。有时，即使数据集相对较小，由于数据 本身的非传统特点，也不能使用传统的方法处理。在另外一些情况下，需要回 答的问题不能使用已有的数据分析技术来解决。这样，就需要开发新的方法。 数据挖掘是一种技术，它将传统的数据分析方法与处理大量数据的复杂算 法相结合。数据挖掘为探查和分析新的数据类型以及用新方法分析旧有数据类 型提供了令人振奋的机会。 1 1 数据挖掘 1 1 1k d d 的定义 数据库知识发现的定义几经变化，其中比较公认比较完整、深刻和全面的 一个定义是由德国人f a y y a d z 等在1 9 9 6 年发表在会议论文( ( f r o md a t am i n i n gt o k n o w l e d g ed i s c o v e r y ) ) 一文【l 】中将k d d 定义为： ”t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e lp o t e n t i a l l yu s e f u l ，a n d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a 即k d d 是从大量数据中提取出有效的、新颖的、有潜在作用的、可信的、 并能最终被人理解的模式的非平凡的处理过程。 k d d 过程是交互的、重复的，包括大量由用户决策的阶段【4 4 1 。一般地， 将k d d 中进行知识发现的阶段称为数据挖掘( d a t am i n i n g ，d m ) 雎】，某些应用 领域对数据挖掘与k d d 不加区分地使用，而在某种意义上二者可看作同一个 概念。 1 1 2 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和 决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪 声的；发现的是用户感兴趣的知识；发现的知识是要可接受、可理解、可运用 的；并不要求发现放之四海皆准的知识，仅要求其支持特定的发现问题p j 。 1 1 3 数据挖掘面临的挑战 正如前面所提到的，当面临新的数据集提出的挑战时，传统的数据分析技 术常常遇到实际困难。下面是一些特定的挑战，它们引发了对数据挖掘的研究。 可伸缩：由于数据产生和收集技术的进步，数吉字节、数太字节甚至数拍 字节的数据集越来越普遍。如果数据挖掘算法要处理这些海量数据集，则算法 必须是可伸缩的。许多数据挖掘算法使用特殊的搜索策略处理指数性搜索问题。 可伸缩可能还需要实现新的数据结构，以有效的方式访问个别记录。例如，当 要处理的数据不能放进内存时，可能需要非内存算法。使用抽样技术或开发并 行和分布算法也可以提高可伸缩程度。 高维性：现在，常常遇到具有数以百计或数以千计属性的数据集，而不是 数十年前常见的只具有少量属性的数据集。在生物信息学领域，微针列技术的 进步已经产生了涉及数千特征的基因表达数据。具有时间或空间分量的数据集 也趋向于具有很高的维度。例如，考虑包含不同地区的温度测量的数据集。如 果温度在一个相当长的时间周期内重复地测量，则维度( 特征数) 的增长正比 于测量的次数。为低维数据开发的传统的数据分析技术通常不能很好地处理这 样的高维数据。此外，对于某些数据分析算法，随着维度( 特征数) 的增加， 计算复杂性迅速增加。 异种数据和复杂数据：通常，传统得的数据分析方法只处理包含相同类似 属性的数据集，或者是连续的，或者，是分类的。随着数据挖掘在商务、科学、 医学和其他领域的作用越来越大，越来越需要能够处理异种属性的技术。今年 来，已经出现了更复杂的数据对象。这些非传统的数据类型的例子包含含有半 结构化文本和超链接的w e b 页面集、具有序列和三维结构的d n a 数据、包含 地球表面不同位置上的时间序列测量值( 温度、气压等) 的气象数据。为挖掘 这种复杂对象而开发的技术应当考虑数据中的联系，如时间和空间的自相关性、 图的连通性、半结构化文本和x m l 文档中元素之间的父子联系。 数据的所有权与分布：有时，需要分析的数据并非存放在一个站点，或归 属一个单位，而是地理上分布在属于多个机构的资源中。这就需要开发分布式 数据挖掘技术。分布式数据挖掘算法面临的主要挑战包括：a 如何降低执行分 布式计算所需的通信量? b 如何有效地统一从多个资源得到的数据挖掘结果? c 如何处理数据安全性问题? 非传统的分析：传统的统计方法基于一种假设检验模式。换句话说，提出 一种假设，设计实验来收集数据，然后针对假设分析数据。但是，这一过程劳 力费神。当前的数据分析任务常常需要产生和评估数以千计的假设，因此希望 自动地产生和评估假设导致了一些数据挖掘技术的开发。此外，数据挖掘所分 析的数据集通常不是精心设计的实验的结果，并且它们通常代表数据的时机性 样本，而不是随机样本。而且，这些数据集常常涉及非传统的数据类型和数据 分布【3 1 。 2 1 1 4 数据挖掘任务 通常，数据挖掘任务分为下面两大类： 预测任务。这些任务的目标是根据其他属性的值，预测特定属性的值。被 预测的属性一般称为目标变量或因变量，而用来做预测的属性称说明变量或自 变量。 描述任务。这里，目标是导出概括数据中潜在联系的模式( 相关、趋势、 聚类、轨迹和异常) 。本质上，描述性数据挖掘任务通常是探查性的，并且常 常需要后处理技术验证和解释结果。 这两大类可分为四种主要数据挖掘任务。 预测建模：涉及以说明变量函数的方式为目标变量建立模型。有两类预测 建模任务：分类，用于预测离散的目标变量；回归，用于预测连续的目标变量。 例如，预测一个w e b 用户是否会在网上书店买书是分类任务，因为该目标变量 是二值的。另一方面，预测某股票的未来价格是回归任务，因为价格具有连续 值属性。两项任务目标都是训练一个模型，使目标变量预测值与实际值之间的 误差达到最小。预测建模可以用来确定顾客对产品促销活动的反应，预测地球 生态系统的扰动，或根据检查结果判断病人是否患有某种特定的疾病。 关联分析：用来发现描述数据中强关联特征的模式。所发现的模式通常用 蕴含规则或特征子集的形式表示。由于搜索空间是指数规模的，关联分析的目 标是以有效的方式提取最有趣的模式。关联分析的应用包括找出具有相关功能 的基因组、识别一起访问的w e b 页面、理解地球气候系统不同元素之间的联系 在占 i 宁。 聚类分析：旨在发现紧密相关的观测值组群，使得与属于不同簇的观测值 相比，属于同一簇的观测值相互之间尽可能类似。聚类可用来对相关的顾客分 组、找出显著影响地球气候的海洋区域以及压缩数据等。 异常检测：是识别其特征显著不同于其他数据的观测值。这样的观测值称 为异常点或离群点。异常检测算法的目标是发现真正的异常点，而避免错误地 将正常的对象标注为异常点。换言之，一个好的异常检测器必须具有高检测率 和低误报率。异常检测的应用包括检测欺诈、网络攻击、疾病的不寻常模式、 生态系统扰动等。 1 2 数据挖掘中的聚类问题 传统聚类算法主要是针对静态数据库进行设计的，这类算法处理的数据多 是存储在磁盘或其它存储介质中的静态数据，算法可以对这些数据进行随机操 作，多次扫描，计算量往往都是很大的，i o 开销随着数据量的增多也会增大。 3 1 2 1 聚类分析简介 聚类分析是一种“物以类聚的方法，是按照属性值把一组对象划分成一 系列有意的子集的描述性任务。 聚类的目的就是要将一组数据分组，而这种分组要基于以下原理：即满足最 大的组内相似性和最小的组间相似性，使得不同聚类中的数据尽可能地不同， 而同一聚类中的数据尽可能地相似。 目前，聚类分析已成为数据挖掘领域的主要课题之一。一个重要的原因就 是聚类越来越多地应用在海量数据中，对于这些海量数据，单纯的统计的方法 无法实现有效的处理、从中得出有用的信息，必需要和数据库管理、人工智能 等计算机技术结合在一起提出集成的解决方案，而聚类分析正好为解决这些问 题提供了一个有力工具。 近年来，随着硬件技术的发展，有越来越多的应用产生数据流，数据流不 同于传统的存储在磁盘上的静态数据，而是一类新的数据对象，它是无限的、 连续的、有序的、快速变化的、海量的数据。典型的数据流包括网络与道路交 通监测系统的监测信息数据、电信部门的通话记录数据、由传感器传回的各种 监测数据、股票交易所的股票价格信息数据以及环境温度的监测数据等。数据 流本身的这些特点决定了对数据流进行处理时只能对数据作一到两遍的扫描， 并只能临时存储少量的数据。因此原来很多成熟的数据挖掘、数据分析和数据 查询技术在数据流上变得不适用了，需要提出新的解决方法。因此，数据流的 问题一出现马上引起了研究者的重视，出现了很多研究成果，对数据流从管理、 查询、分析与挖掘算法等多个方面进行了研究。 数据流挖掘技术作为数据挖掘领域的新问题，很多挖掘算法需要针对数据 流进行改造数据流聚类分析作为数据流挖掘的一个重要研究方向，同样面临着 巨大的挑战，也引起了研究者们的广泛关注，目前出现了不少相关的研究成果， 并应用到了实践中。 1 2 2 聚类的实际应用 目前，聚类分析已经成为数据挖掘和知识发现领域中的主要课题之一。聚 类分析作为一种基本的数据挖掘方法已经广泛地应用于相似搜索、顾客划分、 模式识别、趋势分析、金融投资、地理信息系统、卫星图象和医疗卫生等领域， 并取得了一定成效。 比较有代表性的应用实例如：( 1 ) 在交易数据库中，对顾客一次购买商品 的情况进行聚类分析，根据聚类结果来布置商品摆放位置，从而提高销售利润。 ( 2 ) 类似地，在电子商务中，每天的日常业务会产生大量数据，用聚类算法分 析这些数据信息能帮助销售商确定相对固定的顾客群，便于商家有针对性的制 定销售方案、开展有效的促销活动，以保证在赢得更大利润的同时又发展了新 4 顾客群、保留住了旧顾客群。( 3 ) 在信息检索领域中，聚类分析对文档进行分 类，改善信息检索的效率，从而提高人们的工作效率。( 4 ) 在气象预测中，通 过对由传感器传来的空气的温度、湿度、可见度等信息进行聚类，可以预测未 来几天气候的变化。( 5 ) 在医疗分析中，通过对一组新型疾病聚类，得到每类 疾病的特征描述，就可以对这些疾病进行识别，提高治疗的功效。聚类还能帮 助医生发现不正常类别的特殊病例，例如识别组织结构的病变细胞。旬聚类还 用于发现空间趋势，即空间数据库中一个或多个非空间属性的变化模式。乃在 天文学上，研究人员利用聚类分析宇宙仿真系统得到的数据，更好地理解黑洞 形成和进化的物理过程等等。 1 3 本文的研究内容与组织 作为一种新的数据形态，流数据对数据挖掘提出了诸多挑战。学者们已提 出大量处理流数据的挖掘算法。本文在对数据挖掘进行概述的基础上引入数据 流聚类分析技术及方法的相关介绍，客观分析现有算法的优劣性，并结合现实 世界数据特性及实际应用情况，提出面向含有噪音数据以及面向混合属性数据 的数据流聚类算法研究，全文由六章组成，具体组织方式如下： 第一章绪论，首先简介了k d d 及数据挖掘的概念、任务及挑战；概述了 数据挖掘中的聚类问题，提及了数据流环境中的聚类问题。 第二章主要介绍了数据流问题研究的相关工作和进展，包括数据流的基 本概念、应用背景、理论基础及采用的技术方案。 第三章概要描述了有关传统聚类算法和数据流聚类算法的相关工作和进 展。 第四章本章提出一种有效的数据流二次聚类算法( t c l u s a ) ，以提高对数 据分布不规则和含有噪音时的数据流聚类的质量。t c l u s a 是基于分区思想， 使用d b s c a n 方法对每块分区数据聚类删除离群点以每个簇的均值点作为其 代表点，得到局部聚类结果，再用k m e a n s 方法对所获得的代表点进行聚类获 得最终结果。 第五章现实世界中的数据流往往是混合属性，但现有算法往往局限于仅 处理一种属性，而对其它类型的属性采取简单舍弃的办法，降低了算法的精度。 为此，本章提出一种针对混合属性的基于网格的数据流聚类算法，使用一种基 于几何邻接和信息增益的混合类型数据相似度量方法，可以有效的对混合属性 进行处理。 第六章是对全文的总结与展望，对本文的主要研究工作进行简要地阐述， 展望未来可以进一步研究的问题。 第二章数据流挖掘概述 本章首先介绍了数据流的研究背景、定义及特点，然后介绍了针对对数据 流的特点提出来的处理数据流的新的方法，最后介绍了根据已有的方法开发出 来的处理数据流的系统。 随着信息技术的高速发展，人类积累了大量数据。数据挖掘技术旨在从大 量数据中挖掘出有用的知识提供给人们，辅助人们进行科学分析和决策。短短 的十儿年里，数据挖掘得到了迅速发展，已提出很多有用的算法和框架。然而， 近年来大量应用中产生了大量的、源源不断的数据，如网络监控日志、电子商 务记录、电话通信记录。这些数据适合用数据流模型进行描述。在数据流模型 中，数据流算法只能对数据进行一次顺序扫描。并且，与数据量相比，内存空 间大小非常有限，只能保存数据的概要( s y n o p s i s ) 而不是全体。传统的数据挖 掘算法针对的是静态的数据库，因此不能直接应用于数据流，这促使人们设计 新的数据挖掘算法来适应数据流模型。 2 1 数据流的研究背景及基本概念 2 1 1 研究背景 现代计算机网络和传感器网络技术的快速发展引发了一类具有广阔发展前 景的新数据库一数据流一应用，从环境和天文监测、计算机网络监控、金融股 票交易到网页搜索日志分析等。该类应用中，海量数据以实时方式快速到达。 下面列举了几个数据流常见的应用场景。 ( 1 ) 传感器网络( s e n s o rn e t w o r k ) 目前已经广泛分布于各种地理环境中， 如热带雨林、江河流域以及高速公路等，用于地理信息监测、生命信号检测、 车辆运动跟踪和交通拥塞检测等。在传感器网络中，大量传感器每时每刻不断 感应出大量监测数据，并通过无线网络传输到集站。集站中的数据分析服务器 必须及时地对这些监测数据进行分析和处理。 ( 2 ) 计算机网络实时交互着大量的及时通讯消息、电子邮件、在线视频等 数据。这些数据被封装为各种i p 数据包通过局域网( 或广域网) 从源地址传送到 目标地址。作为网络连接节点的路由器、交换机等设备需要极快地传输这些i p 数据包，例如c i s c o 公司的w s c 6 5 0 3 交换机最高背板带宽高达7 2 0 g b p s 。因 特网服务提供商( 例如中国网通) 需要从交换机设备中获取这些实时i p 数据包并 进行分析挖掘，从而实现对计算机网络的监控和维护。 ( 3 ) 金融股市交易着成千上万种价格瞬息万变的股票和基金。与此同时， 世界各地各种政治、经济、文化新闻和突发事件不断涌现。它们直接或间接影 响着这些股票和基金的价格仅据美国n y s e 、a m s e 、n a s d a q 和s m a l l c a p 6 四个股票交易所的不完全统计信息，上市股票的日常交易数据和报价数据以每 月1 0 c b 的速率增长。股票交易所、证券公司需要不断实时获取各种股票和基 金的价格以及各种新闻信息，并在此基础上进行大量的复杂实时分析挖掘，如 股票关联关系的发现、股价趋势分析、走势预测等。更快地获取更多信息就意 味着更好的财富机会和更小的金融风险。 ( 4 ) 网页搜索目前己形成了一种新兴产业。例如百度公司每天都需要对8 亿多中文网页完成上亿次搜索，c o o g l e 公司每天需要对全球6 0 多亿网页完成2 亿次搜索。( ( 2 0 0 5 年度中国搜索引擎市场报告显示2 0 0 6 年中国网页搜索用户 数比2 0 0 5 年增长2 2 6 ，并还将以每年1 1 以上的速度递增。这些不断增长的 页面搜索请求为网络搜索公司带来了巨大网络流量的同时，给公司网站的事务 日志留下大量的搜集记录。如何对这些搜索记录进行实时分析处理，以带来更 好的用户体验和更为强大的搜索功能，是每个网络搜索公司不断追求的目标。 可以看到，上述各种应用场景的共同特点是海量数据实时快速到达。学术 界把具有这种特征的新兴数据库称为数据流数据流相对于传统数据库( 例如基 于磁盘的数据库) 己成为一种新兴且日益主流的数据存在方式。人们迫切需要从 这些包含有大量数据的数据流中提取有价值的信息和知识。因而，数据流的分 析和挖掘日益成为一个热点问题。 2 1 2 数据流的定义及特点 数据流是实时的，连续的，有序项的序列( 由到达的时间隐含地表示或显式 地以时间戳指定) ，可形式化地表示为： x i ，x 2 ，x n ) 有序点的集合，n - e o 。 一般来说，数据流具有快速性、连续性，多变化，无限性等特点，这些特 点使得传统的处理静态数据的技术和算法面临挑战。 2 1 3 理论基础 使用所制定的统计和计算方法可以解决数据流挖掘中不断面临的研究难题 和挑战。这些方法一般分为两大类：一类是基于数据的解决方案，另一类则是 基于任务的解决方案。基于数据的解决方案的基本思想是：每次只检查整个数 据集中的一个子集，以纵向或横向的方式将数据变换成具有代表性的近似的小 数据集；而基于任务的解决方案则是采用计算理论的技术，从而实现时间和空 间性能的优化。 2 2 数据流处理方法和流数据系统 2 2 1 数据流处理方法 为了有效地处理流数据，需要建立新的数据结构、技术和算法。因为我们 没有无限大的空间去存储流数据，就需要在正确性和存储空间之间进行平衡。 也就是说，我们通常愿意得到近似而不是精确的答案。大纲可以提供数据的概 要描述，可以为查询提供近似结果。大纲使用大纲数据结构，是比基本的数据 集合( 这里指流数据) 小得多的任何数据结构。从算法的角度来看，我们希望 算法在空间和时间上都是有效的。通常，我们希望使用多次对数空间复杂度 o ( 1 0 9 k n ) ( 其中n 为流数据中的元素个数) ，而不是用o ( n ) 空间复杂度来存储 所有或者大部分元素。我们可以放宽准确答案的要求，寻找具有高概率的小误 差率范围内的近似答案。这就是说，许多基于数据流的算法都以高概率，在因 子e 范围内计算实际回答近似结果。一般来说，随着近似因子( 1 + ) 变小， 空间需求上升。下面我们将考察些常用的大纲数据结构和技术。 ( 1 ) 随机抽样 不是处理整个数据流，可以考虑对流进行周期区间抽样。如果预先知道流 的长度，可以得到数据的无偏抽样。如果预先不知流的长度，则可以使用一种 称作水库抽样的技术无放回地选取s 个元素的无偏随机样本。水库抽样的基本 思想相对简单。维护一个大小至少为s 的随机样本。然而，从水库中产生样本 可能代价很大，特别是当水库很大时。为了避免这一步，在水库中维护s 个候 选的集合，形成到目前看到的流元素的真正随机样本。随着数据流的流动，每 个新元素都有一定的可能性取代水库中的旧元素。假定我们已经看到了流中的 n 个元素。随机样本，一个新元素取代旧元素的可能性为s n 。这就一直保持 水库中s 个候选的集合形成一个到目前看到的数据流元素的随机样本。 ( 2 ) 滑动窗口 可以使用滑动窗口模型对流数据进行分析，而不是对数据流进行随机抽样。 其基本思想是：仅仅基于最近的数据流做出决策，而不是对目前为止看到的所 有数据或对某个样本进行计算。更形式化地，在每个时刻t ，一个新的数据元 素到来。该元素在时刻t + w “过期 ，其中w 为窗口的“大小”或长度。滑动窗 口模型对于股票或传感器网络很有用，那里只有最近的事件才可能是重要的。 由于只需要存储小的数据窗口，所以它也可减少对内存的需求。 ( 3 ) 直方图 直方图是一种大纲数据结构，可用来近似数据流中元素值的频率分布。直 方图把数据划分为一系列相邻的桶。依照使用的划分规则，宽度( 桶的值域) 和深度( 每桶里的元素个数) 可以是不同的。等宽划分规则是一种构造直方图 的简单方法，其中每个桶的值域是相同的。尽管这种方法容易实现，但是不能 对概率分布函数进行很好的抽样。较好的方法是使用v 最优直方图。与聚类类 似，v 最优直方图定义的桶尺寸，最小化每个桶的频率方差，可以较好地体现 数据分布。然后，可以使用这些直方图而不是使用抽样技术来产生近似的查询 回答。 8 ( 4 ) 多分辨率方法 处理大数量数据的一种常用方法是数据规约方法。一种流行的数据规约方 法是此采用分治策略，如多分辨率数据结构。这些方法允许程序在准确性和存 储之间进行权衡，同时也提供在多层细节理解数据流的能力。 ( 5 ) 梗概 大纲技术的主要不同点在于如何正确地在准确性和存储之间进行权衡。抽 样技术和滑动窗口模型关注小部分数据，而其他大纲方法试图对所有的数据进 行汇总，通常是在多个细节层上。一些技术( 直方图和小波) 需要扫描数据多 遍，而其他方法( 如梗概) 可以在一遍完成。 理想地，假设我们想在数据流的对象或元素的全域上维护完全的直方图， 其中全域为u = 1 ，2 ，v ) ，数据流为a = a h a 2 ，a n 。也就是说，对全域 中的每个值i ，维护i 在序列中a 出现的频率和次数。如果全域很大，这个结构 也同样很大。因此，我们需要更小的表述方式。 让我们考虑a 的频率矩。这些是数f k ，定义为 f k = 群 i = l 其中，v 是全域或定义域的大小( 同上) ，m i 是i 在序列中出现的频率，并 且k 0 。特殊地，f o 是序列中不同元素的个数。f 1 是序列的长度( 也就是n ) ， f 2 自连接的大小、重复率或同源的g i n i 指标。对于数据库应用，数据集的频 率矩提供了数据的有用信息，如回答查询。此外，它们指示数据的倾斜或非对 称的程度。在并行数据库应用中，对于确定如何为数据选择合适的划分算法， 这些量是有用的。 当可用内存小于v 时，需要使用大纲。可使用称作梗概的大纲对频率矩进 行估计。使用数据向量的随机线性投影，这些梗概建立分布向量( 如直方图) 的一个小空间汇总。梗概对近似答案的质量提供概率保证( 例如，给定查询的 回答为1 2 1 的可能性为0 9 0 ) 。给定n 个元素和具有v 个值的全域u ，这些 梗概可在o ( 1 0 9 v + l o g ) 空间中近似f o ，f l ，f 2 。其基本思想是，将每个元素均匀 随机地散列到z ie - 1 ，+ 1 ) ，然后维护一个随机变量x = ；z f 。x 2 是f 2 的一个 很好的估计。为了解释为什么这样做可行，可想像将元素散列为1 或+ 1 就像将 每个元素值指派到拔河赛的两边。求和得到x 是，可以看作测量绳子从中间点 的移位。对x 取平方就是对移位值取平方，体现了数据的倾斜量f 2 。 为了得到更好的估计，可以维护多个随机变量x i 。然后，通过选择这些变 量的平方值的中位数，可以提高估计值的置信度接近f 2 。 从数据库角度来看，梗概划分旨在改善数据流查询优化梗概的性能。梗概 划分以可保证的误差，使用基本数据的粗略统计信息来智能地划分属性的定义 域。 9 ( 6 ) 随机算法 随机算法以随机抽样和梗概的形式，常常用来处理海量、高维数据流。与 已知的确定算法性相比，随机选择的使用常常导致更简单、更效的算法。 如果一个随机算法总是返回正确的回答，但是运行时间不确定，则称它是 拉斯维加斯算法。相反，蒙特卡洛算法的运行时间有上界，但是可能无法返回 正确的结果。这里主要考虑蒙特卡洛算法。可以把随机算法简单地看作一系列 确定算法的概率分布。 假定一个随机算法的返回随机变量作为结果，我们希望有该随机变量的尾 概率的界。这告诉我们随机变量偏离它的期望值的概率很小。一个基本的工具 是切比雪夫不等式。设x 为一个随机变量，具有均值为，标准差6 ( 方差艿2 ) 。 对于任意给定的正实数k ，以下切比雪夫不等式成立 尸( i x 刊 哪詈 这个不等式可用来限定随机变量的方差的界。 在许多情况下，可使用大量随机变量来提升结果的置信水平。只要这些随 机变量是完全独立的，就可使用切尔诺夫界。设x l ，x 2 ，x n 是独立的泊 松实验。在不同的泊松实验中，成功的概率是不同的。如果x 是x l 到x n 的和， 则一个较弱的切尔诺夫界表明 p r x 每个对象必须属于且仅属于一个组 其中，在某些模糊划分技术中第二个要求可以根据实际情况于放宽。给定k ， 即要构建的划分的数目，划分方法首先创建一个初始划分。然后采用一种迭代 的重定位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般 1 4 准则是：在同一个类中的对象之间的距离尽可能小，而不同类中的对象之间的 距离尽可能大。还有许多其他划分质量的评判准则。为了达到全局最优，基于 划分的聚类会要求穷举所有可能的划分。 实际上，绝大多数应用采用了以下两个比较流行的启发式方法：k 平均 算法首先由m a c q u e e n 在文【4 】中提出，在该算法中，每个簇用该簇中对象的平均 值来表示；k 中心点算法p a m 和c l a r a 由k a u f m a n 和r o u s s e e u w 在文【5 】中提 出，该算法中的每个簇用接近聚类中心的一含对象来表示。这些启发式聚类方 法对在中小规模的数据库中发现球状簇很适用，为了对大规模的数据集进行聚 类、处理复杂形状的聚类以及改进聚类结果对参数k 的过分依赖等，基于划分的 方法需要进一步的扩展。 ( 2 )层次方法( h i e r a r c h i c a lm e t h o d s ) 层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成， 层次的方法可以被分为凝聚的、分裂的方法。其中，凝聚的方法，也称为自底 向上的方法，一开始将每个对象作为单独的一个组，然后继续地合并相近的对 象或组，直到所有的组合并为一个( 层次的最上层) ，或者达到一个终止条件。 分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在 迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个 簇中，或者达到一个终止条件。 层次的方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被 撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算代价 会较小。但是，该技术的一个主要问题是它不能更正错误的决定。有两种方法 可以改进层次聚类的结果：在每层划分中，仔细分析对象间的联接，例如 c u r e 6 】和c h 锄e l e o n 7 】中的做法；综合层次凝聚和迭代的重定位方法，首先 用自底向上的层次算法，然后用迭代的重定位来改进结果，例女| b i r c h 8 】中的 方法。 ( 3 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d s ) 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球 状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类 聚类方法，其主要思想是：只要临近区域的密度( 对象或数据点的数目) 超过 某个阈值，就继续聚类；也就是说，对给定类中的每个数据点，在一个给定范 围的区域中必须包含至少某个数目的点。这样的方法可以用来过滤“噪音数 据并发现任意形状的簇。 d b s c a n 9 】是一个有代表性的基于密度的方法，它根据一个密度阈值来控 制簇的增长。o p t i c s 1 0 】是另一个基于密度的方法，它为自动的，交互的聚类 分析计算一个聚类顺序。然而，算法的高时空消耗以及参数等问题的缺陷，仍 有较大的改进和提升空间。 ( 4 ) 基于网格的方法( g r i d b a s e dm e t h o d s ) 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。 所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要 优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间 中每一维的单元数目有关。 基于网格方法的代表性例子如s t i n g t l l 】，它采用基于网格的多分辨率聚类 技术，将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级 别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个 低一层的单元。关于每个网格单元属性的统计信息( 例如平均值，最大值，和 最小值) 被预先计算和存储，这些统计变量可以方便后续的查询处理。尽管该 技术有快速的处理速度，但发现簇的质量和精确性难以得到保证。 另外，w a v e c l u s t e r 1 2 】用一种小波转换方法来聚类对象，是一种多分辨率的 聚类算法；算法首先通过在数据空间上强加一个多维网格结构来汇总数据，然 后采用一种小波变换来变换原始的特征空间，在变换后的空间中找到密集区域。 还有如c l i q u e t l 3 】聚类算法，其综合了基于密度和基于网格的聚类方法，具备 对大型库中的高维数据聚类有效性。 ( 5 )基于模型的方法( m o d e l b a s e dm e t h o d s ) 基于模型的