（计算机软件与理论专业论文）基于核密度估计理论的多数据流聚类研究.pdf

中山大学硕士学位论文基于核密度估计理论的多数据流聚类研究 基于核密度估计理论的多数据流聚类研究 计算机软件与理论 硕士生：谢益煌 指导教师：印鉴教授 摘要 近年来，处理无限的连续数据流的应用日益流行，比如网络日志、传感器网 络等。数据流聚类( d a t as t r e a mc l u s t e r i n g ) 逐渐成为数据挖掘领域的热点研究问 题之，由于数据流的数据量无限、对算法的响应要求很高，而且通常只能对数 据访问一次，而传统的聚类算法对快速变化的数据流进行在线分析的支持存在着 很多限制，急需开发适应数据流环境的聚类算法，计算机工作者们面临着新的挑 战。 本文针对当前比较经典的多数据流聚类c o d ( c l u s t e r i n go nd e m a n d ) 框架， 首先，详细分析了其不足之处：不能过滤独异点、对数据流的压缩保存过于简单 和聚类时计算数据流之间的距离的时间复杂度过高等，然后从核密度估计理论和 基于数据的空间划分网格技术出发，提出了一种多数据流聚类的方法一一 c m o ( c l u s t e r i n gm u l t i s t r e a m su s i n go b s e r v em a t r i x ) 方法。理论和实验结果表 明：c m o 方法提供了一种不损伤数据流的时间、距离特性的刻画方法；具有过 滤独异点的能力；聚类的时间复杂度远小于c o d 框架和聚类的精度优于c o d 框架等优点。 关键词：多数据流 聚类 核密度估计 数据挖掘 中山大学硕士学位论文 基于核密度估计理论的多数据流聚类研究 c l u s t e r i n gi nm u l t i p l ed a t as t r e a m s c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：x i ey i h u a n g s u p e r v i s o r ：p r o f e s s o ry i nj i a n a b s t r a c t t o d a y , d a t as t r e a mi sc o m m o ni nm a n ya p p l i c a t i o n s ，s u c ha sw e bl o g sa n ds e n s o r n e t w o r k m i n i n gd a t as t r e a mh a sg r a d u a l l yb e c o m eav e r yp o p u l a rr e s e a r c hd o m a i ni n c o m p u t e rs c i e n c e ，e s p e c i a l l y , h o wt oc l u s t e ri nd a t as t r e a mi sa ni n t e r e s t i n gp r o b l e m a t t r a c t e dm a n yr e s e a r c h e r s t h ed a t a i t e mi nt h es t r e a m sa r r i v eo n l i n ea n dw i t h u n b o u n ds i z ea n dr a p i dr a t e ，t h i sk i n do fs t r e a m so fi n f o r m a t i o nh a sc h a l l e n g e do u r s t o r a g e ，c o m p u t a t i o na n dc o m m u n i c a t i o nc a p a b i l i t i e si no u rs y s t e m i nt h i sp a p e r , w ea n a l y z et h er e c e n tc l u s t e r i n gm u l t i p l ed a t as t r e a m sa l g o r i t h mc o d ( c l u s t e r i n go nd e m a n d ) f r a m e w o r k ，p o i n to u ti t sd i s a b i l i t y , w h i c hc a n n o td e t e c t o u t l i e r ；t h ed a t as u m m a r yi st o os i m p l et oe x p r e s sd a t as t r e a ma c c u r a t e l ya n dt h e c l u s t e r i n gt i m ec o m p l e x i t yi st o oc o m p l e x ，e r e m o m o v e gw ei n t r o d u c ean e w a l g o r i t h mc m o ( c l u s t e r i n gm u l t i - s t r e a m su s i n go b s e r v em a t r i x ) f r a m e w o r kt os o l v e t h e s ep r o b l e m s k e yw o r d s ： m u l t i p l ed a t as t r e a m sc l u s t e r i n g k e r n e ld e n s i t ye s t i m a t e d a t am i n i n g i i 中山大学硕士学位论文 基于核密度估计理论的多数据流聚娄研究 月| j 舌 近年来，由于硬件技术的高速发展，人们收集数据的能力得到了大大的提高。 在现实生活中，我们经常可以碰到这样的情况：大量需要处理的数据以很快的速 度产生。例如，油井平台的监控系统以每秒1 兆的速率来产生描述当前钻头状态 的信息；美国一条高速公路上的传感器网络每天可以收集到高达几百万条的数 据；美国航天宇航局( n a s a ) 的地球观测系统( e o s ) ，通过陆地卫星7 号( 原 称地球资源技术卫星) 和t e r r a 卫星，平均每天要产生高达3 5 0 g 的数据。由于 所需要处理的数据具有实时性、连续性、有序性( 由到达时间隐含表示或显示地 由时间戳决定) ，那么按照传统的数据库应用模式，将所有数据完整地存储到本 地，再由计算机仔细处理，已成为不可能完成的任务。因此，我们迫切需要一种 新的解决方案。 为了解决如何管理这些具有实时性、连续性、有序性、大量并且快速产生的 数据，以及如何对这些数据进行分析的问题，计算机科学家们提出一种新的计算 机数据处理模型数据流( d a t as t r e a m ) 。这种数据处理模型最大的特点在于， 待处理的数据不再静态、固定地存储在可多次、随机访问的介质中，而是以一种 动态、流式的形式出现，对数据只能顺序、一次或有限次地访问。1 。最近的研究 报告表明，数据流已经成为新一代计算机科学理论和应用的热点之一。 数据流挖掘是数据挖掘在数据流模型上的应用，是当前数据挖掘的前沿研究 方向之一。其中，如何在数据流中进行聚类分析更是数据流挖掘中的一个研究热 点。本文主要考察了当前比较经典的多数据流聚类方法c o d ( c l u s t e r i n go n d e m a n d ) 框架“，详细分析其不足之处，然后从核密度估计理论和基于数据的空 间划分网格技术出发，结合数据流自身的特点，提出了一个新的多数据流聚类方 法c m o ( c l u s t e r i n gm u l t i s t r e a m su s i n go b s e r v em a t r i x ) 方法，并通过理论和 实验证明，该算法相比c o d 框架，能够在不损伤数据流的时间、距离特性的前 提下提供一种数据流的刻画方法：具有独异点过滤的能力；以及聚类的时间复杂 中山大学硕士学位沦文甚于核密度估汁理论的多数据流聚娄研究 度远小于c o d 框架以及聚类的精度优于c o d 框架等。 2 中山大学硕士学位论文基于核密度估计理论的多数据流聚娄研究 1 1 数据挖掘概述 1 1 1数据挖掘简介 第1 章引言 随着计算机技术的飞速发展和应用的不断普及，人们产生和收集数据的能力 迅速提高，利用计算机提供的各种工具来获得他们所感兴趣的信息。一方面在商 业管理、政府办公、科学研究和工程开发等各个领域中，每天都会产生大量的数 据，这些数据阻数字化的形式存储起来，并根据需要以电磁媒介加以传播。另一 方面，支持信息共享和传播的互联网技术近年来在世界范围内发展十分迅速，互 联网加速了信息在世界范围内的流动，形成了信息的海洋。数据的丰富带来了对 强有力的数据分析工具的需求，传统的数据库查询手段已经很难满足人们的需 要，大量的数据被描述为“数据丰富，但信息贫乏”“3 。快速增长的海量数据收 集、存放在大型和大量的数据库中，却由于缺乏将这些数据转换成有价值的信息 和知识的新技术和自动化工具，使得收集在大型数据库中的数据变成了“数据坟 墓”。人们迫切需要一种能够对庞大的数据进行更高层次处理的技术，从中找出 规律和模式，以帮助人们更好地利用数据进行决策管理和研究，而数据挖掘技术 从大量数据中提取或“发掘”知识一的出现，引起了人们广泛的关注，导 致了数据挖掘研究的蓬勃发展。 数据挖掘通常又称为数据中的知识发现，狭义上是指从数据库提取知识，具 体的说应是从数据库中对数据进行处理，从而获得隐含的、事先未知的、潜在的 而又是非常有用的知识：广义上来说，数据挖掘是从存放在数据库、数据仓库或 者其他信息库中的大量数据中挖掘有趣知识的过程。数据挖掘还有很多近似的术 语，如从数据库中发现知识( k d d ) 、数据分析、数据融合( d a t af u s i o n ) 以及 中山大学坝士学位论文 雉于核密度估计理论的多数据流聚类研究 决策支持等。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。 原始数据可以是结构化的，如关系型数据库中的数据，电可以是半结构化的，如 文本、图形、图像数据，甚至足分布在网络上的异构型数据。发现知识的方法可 以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。知识用概念、 规则、模式、规律等方式来表示。发现了的知识可以被用于信息管理、查询优化、 决策支持、过程控制等，还可以用于数据自身的维护。 知识发现是一个多步骤的处理过程，般分为“3 ： ( 1 ) 数据清理：清除噪声或不一致的数据： ( 2 ) 数据集成：多种数据源可以组成在一起； ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据； ( 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操 作； ( 5 ) 数据挖掘：基于步骤，使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式； ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 由此可见，数据挖掘只是知识发现的一个步骤，但又是晟重要的一步。因此， 往往可以不加区别地使用k d d 矛h 数据挖掘。一般在研究领域被称作数据库中知 识发现的，在工程领域则称之为数据挖掘。 数据挖掘是一个多学科交叉领域，涉及多学科技术的集成，包括数据库技术、 人工智能、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、知识库系统、图像与信号处理和空间数据分析。机器学习和数据分析 的理论及实践是数据挖掘研究的基础，极大的| 窨；业应用前景又是数据挖掘研究工 作的巨大推动力。传统的数据库查询和统计、报表的处理方式都是对指定的数据 进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，因此只能 够提供用户想要的信息，而数据挖掘技术则可以发现用户没有意以到的未知的有 价值信息：作为一种在海量数据中发现知识的手段，与传统的数据分析( 如查询、 报表、联机分析处理o l a p 等) 的本质区别在于数据挖掘是在没有明确假设的前 提下去挖掘信息、发现知识的，它可以从大型的数据库或数据仓库中提山隐藏的 预测性信息，从浩如烟海的企业信息资料库t 中挖掘出更有价值的信息，具有广泛 中山大学硕士学位论文 基于核密度估计理论的多数据流聚类研究 的应用前景。 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质 的知识；特征型知识，反映事物各方面的特征知识：差异型知识，反映不同事物 之间属性差别的知识：关联型知识，反映事物之间依赖或关联的知识：预测型知 识，根据历史的和当前的数据推测未来数据：偏离型知识，揭示事物偏离常规的 异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升， 从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家 超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客 几乎也同时购买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对 于商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘所得到的知识应具有先前未知、有效和可实用三个特征。先前未知 是指该知识是预先未曾预料到的，即数据挖掘是要发现那些不能靠直觉发现的信 息或知识，甚至是违背直觉的信息或知识，挖掘得到的知识越是出乎意料，就可 能越有价值。知识的有效性要求挖掘前要对被挖掘的数据进行仔细检查，保证它 们的有效性，才能保证挖掘所得知识的有效性。最为重要的是要求所得的知识有 可实用性，即这些信息或知识对于所讨论的业务或研究领域是有效的，是有实用 价值和可实现的。常识性的结论，早已被人们或竞争对手掌握的或无法实现的事 实都是没有意义的。 数据挖掘起源于二十世纪八- 卜年代后期，是信息技术自然演化的结果，九十 年代有了突飞猛进的发展。自从1 9 9 5 年第一届知识发现和数据挖掘国际会议在加 拿大召开以来，数据挖掘技术已成为机器学习、数据库系统、人工智能等领域内 热门的研究方向。随后，i e e e 、a c m 、a a a i 等国际权威机构纷纷组织专题会议， 共同讨论有关数据挖掘方面出现的问题和所取得的成果。 1 1 2数据挖掘的基本方法 数据挖掘的方法很多，从不同的视角看，数据挖掘有几种分类方法：根据发 现知识的种类分类；根据挖掘的数据库的种类分类和根据采用的技术分类等。 最常用的分类方法是根据发现知识的种类不同来分类，主要有如下的几种分 中山大学硕二匕学位论文 摅十幢密度估计理论的多数据流聚娄研宄 ! l 方法： ( 1 ) 概念类描述 用汇总的、简洁的、精确的方式描述每个类和概念称为类概念描述。这种 描述可以通过下述方法得到：第一、数据特征化，一般地汇总所研究类的数据； 第二、数据区分，将所研究类与一个或多个比较类进行比较：第三、数据特征化 和比较。 ( 2 ) 关联分析 关联分析是指大量数据中项集2 _ 1 司有趣的关联或相关联系。随着大量数据 不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感 兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制 定。如购物篮的例子：在销售食品柜台发现，在购买牛奶的客户中，有8 0 的a 同时也购买了面包和饼干，用规则：“牛奶，面包+ 饼干”表示。发现这样的 规则可以设计方便顾客购物的商品货架、指导商家进货，对于确定市场策略是很 有价值的。关联规则还可以应用到附加邮递、仓储规划以及基于购买模式对用、 进行分类等方面。 ( 3 ) 分类和预测 分类和预测是两种数据分析形式，可以用于提取描述重要数掘类的模酗或 预测未来的数据趋势。其中，分类是预测分类标号( 或离散值) ，而预测是建立 连续值函数模型。例如，可以建立一个分类模型，对银行贷款的安全或风险进行 分类；同时可以建立预测模型，给定潜在顾客的收入和职业，预测它们在计算机 设备卜的花费。 ( 4 ) 聚类分析 聚类与分类的不同之处在于，它要划分的类是未知的。聚类就是将数据对 象分组成为多个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度， 而不i 司簇中的对象差别较大。在许多应用中，可以将一个簇中的数据对象作为一 个整体来看待。聚类分析在市场营销、生物学、交通等领域都有广泛的应用。例 如在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且 用购买模式来刻画不同的客户群的特征；在生物学上，聚类能用于推导植物和动 物的分类对基因进行分类，获得对种群中固有结构的认识。 中山大学硕士学位论文耩于核密度估计理论的多数据流聚类研究 ( 5 ) 孤立点分析 经常存在一些数据对象，它们不符合数据的一般模型，这样的数据对象被 称为孤立点( o u t l i e r ) 。孤立点可能是度量或执行错误所导致的，也可能是固有的 数据变异的结果。许多数据挖掘算法试图使孤立点的影响最小化，或者排除它们。 但是，孤立点本身可能就是非常重要的，孤立点探测和分析是一个有趣的数据挖 掘任务，被称为“孤立点挖掘”。孤立点挖掘有着广泛的应用，例如在欺1 诈监测 中，孤立点可能预示着欺诈行为，可用来探测不寻常的信用卡使用或电信服务。 ( 6 ) 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势，并对其建模。例如你有纽约股票交易所过去几年的主要股票市场数据，并希 望投资于高科技工业公司的股票。股票交易数据的挖掘研究可以识别整个股票市 场和特定公司的股票演变规律。这种规律可以帮助预测股票市场价格的未来走 向，帮助你对股票投资做出决策。 1 1 3数据挖掘的研究现状 数据挖掘技术从一开始就是面向应用的。它不仅仅是面向特定数据库的简单 的检索查询或者调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、 综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已 有的数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新 的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。美国加州 理工学院喷气推进实验室与天文学家合作开发的s k i c a t 系统通过对几百万个 天体进行分类，已帮助天文学家发现了1 6 个新的类星体。美国n b a 篮球队的教 练，利用某公司提供的数据挖掘技术，临场决定替换队员，一度在数据库界被传 为佳话。最近，还有不少d m k d 产品用来筛选i u t e r n e t 上的新闻，保护用户不 受无聊电子邮件的干扰和商业推销，受到极大的欢迎。这样一来，就把人们对数 据的应用，从低层次的末端查询操作，提高到为各级经营决策者提供决策支持。 这种需求驱动力，比数据库查询更为强大。同时需要指出的是，这里所说的知识 中山大学硕一l 学位论义 基于核密度估计理论的多数据流聚娄研究 发现，不是要求发现放之四海而皆准的真理，也不是要去发现崭新的自然科学定 理和纯数学公式，更不是什么机器定理证明。所有发现的知识都是相对的，是有 特定前提和约束条件、面向特定领域的，同时还要能够易于被用户理解，虽好能 用自然语言表达发现结果。 目前，国外数据挖掘的发展趋势主要有：对知识发现方法的研究进一步发展， 如近年来注重对贝叶斯( b a y e s ) 方法以及b o o s t i n g 方法的研究和提高；传统的 统计学回归法在k d d 中的应用：k d d 与数据库的紧密结合等。在应用方面包括： k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤 立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多 计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中 心进行这方面的工作。很多大公司也对数据挖掘应用的研究投入大量精力，经过 十多年的努力，关于数据挖掘技术应用的研究也取得了丰硕的成果。一些公司已 经开发了多种数据挖掘相关的产品，据不完全统计，目前已经有了数百个数据挖 掘软件产品。如i b m 公刊开发的q u e s t 和i n t e l l i o p t tm i n e r ：a n g o s ss o f t w a r e 开发的基于规则和决策树的k n o w l e d g es e e k e r ；a d v a n c e ds o f t w a r e a p p l i c a t i o n 开 发的基于人工神经网络的d bp r o f i l e ；加拿人s i m o nf r a s e r 大学开发的d bm i n e r ； s g i 公司开发的m i n es e t 等。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究，大量的文章已经在各级期刊，各种会议发表，应用数 据挖掘技术开发的产品日渐增多，已经有不少包含数据挖掘功能的产品m 世，如 用于对股票行情进行分析预测的指南针、神光、r m r 等智能股票分析系统。目 前进行的大多数研究项目是由政府资助进行的，如困家自然科学基金、8 6 3 计划、 “九五”计划等。 一份最近的g a r t n e r 报告中列举了在今后三至五年内对工业将产生重要影响 的五项关键技术，其中k d d 和人工智能排名第一。同时，这份报告将并行计算 机体系结构研究和k d d 列入今后5 年内公司应该投资的1 0 个新技术领域。可 以看出，数据挖掘的研究和应用受到了学术界和实业界越来越多的重视，预计在 2 l 世纪还会形成更大的高潮，研究焦点可能会集中到以下几个方面：研究专门 中山大学硕士学位论文基于核密度估计理论的多数据流聚类研究 用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化： 寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解，也便 于在知识发现过程中的人机交互；研究在网络环境下的数据挖掘技术，特别是在 i n t e r n e t 上建立d m k d 服务器，与数据库服务器配合，实现数据挖掘：加强对各 种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据。但是无论怎 样，需求牵引与市场驱动是永恒的，d m k d 将首先满足信息时代用户的急需， 大量基于d m k d 的决策支持软件工具产品将会问世。 1 2 数据流挖掘 随着信息处理在通信、工业生产等领域的广泛应用，数据已不仅拘泥于文件、 数据库等静态形式，连续、无限、不定速的海量数据已经出现在越来越多的应用 领域。这些数据被认为是数据流。1 。 所谓数据流，就是大量连续到达的、潜在无限的数据的有序序列。数据流的 特征。3 可以概括为：时效性：数据流中的数据携带事件的时间特性；实时性： 数据流中数据的处理要求是实时的；无限性：数据流随时间延续而源源不断意 味着数据量无限：瞬时陛：数据流中的数据除非进行特意存储，否则流过后不 可再访问，而无限性决定了数据流是不可能完全存储的。在网络监控、入侵检测、 情报分析、金融服务、股票交易、电子商务、电信、w e b 页面访问和科学研究众 多领域中，广泛存在着这种形式的数据。如何对这些流式数据使用有限存储空间 来进行快速处理以获取有用信息，具有非常重要的意义。 由于众多应用领域的需求，近年来数据流处理问题，特别是数据流挖掘问题 己受到越来越多的研究人员关注。目前数据流挖掘方面的研究成果主要集中在数 据流频繁模式挖掘、数据流分类、数据流聚类等方面。目前，国外在数据流挖掘 方面有两个比较有影响力的研究小组：一个是s t a n f o r d 大学的r m o t w a n i 教授所 领导的研究小组，该小组的研究侧重在数据流管理、数据流的连续查询和数据流 的聚类方面。“”。“，提出了不同于传统的d b m s 的d s m s ( d a t as t r e a m m a n a g e m e n ts y s t e m ) 概念，他们的研究得n t 美国国家自然基金的资助。另一 个研究小组是u i u c 大学的c a g g a r w a l 和j h a n 教授领导的研究小组，他们的研 中山大学顺卜学位论文 基十植密度估汁理论的多数据流聚类研究 究侧重在数据流的分析方面“”“，特别是数据流的在线分析，从聚类，分类以 及可视化的角度做了大量的研究工作，他们的研究得到了美国军方和国家自然科 学基金| e f 勺资助。 1 1 4数据流处理的基本方法 数据流挖掘研究中产生的很多问题和挑战，可以在沿用已久的统计学和可计 算理论中寻找解决方法。我们将这些方法加以分类，划分为基于数据的 ( d a t a b a s e d ) 解决方案和基于任务的( t a s k b a s e d ) 解决方案。在基于数据的解 决方案中，主要思想是只对整个数据集的一个子集进行分析，或者将整个数据集 纵向或横向的转化为个较小规模的原始数据集的近似表示，再进行分析。在基 于任务的解决方案中，主要思想是通过可计算理论的方法与技术，实现具有较好 时空复杂度的解决方案。 基于数据的解决方案是指到对整个数据集进行概括，或者对即将到达的数据 流选择一个子集，以便进行分析。对数据集进行概括的方法主要有采样 ( s a m p l i n g ) 、装载脱落( l o a ds h e d d i n g ) 和概略( s k e t c h i n g ) 技术；为数据流 选择子集的方法主要有大纲数掘结构( s y n o p s i sd a t as t r u c t u r e ) 和聚合方法 ( a g g r e g a t i o n ) 。 ( 1 ) 采样 采样就是一个概率选择的过程，决定一个数据项是否被处理。采样技术是 种传统的统计学技术，采样的边界误差率是由采样率决定的。快速机器学习( v e r y f a s tm a c h i n el e a r n i n g ) 技术根据一些损失函数，采用了h o e f f d i n g 边界来度量样 本的大小。 在对数据流进行上下文分析刚，如果使用采样技术，那我们面临的问题是无 法确定整个数据集的大小。冈此在处理数据流时，! 西须采用特定的分析来确定误 差边界。另一个问题是，对异常点进行监控分析是数据流挖掘应用的一个很重要 的步骤，而采样技术并不适应这样的应用。而且，采样技术并不能解决数据产生 速率不断波动的问题。我们需要认真研究数据产生速率、采样率和误差边界i 个 参数之间的相互关系。 中山大学硕：匕学位论文 基于核密度估计理论的多数据流聚类研究 ( 2 ) 装载脱落 装载脱落叫是指丢弃一部分数据流的过程。装载脱落技术成功地应用在数据 流查询当中，但是跟采样技术一样，装载脱落也面l 临同样的问题。装载脱落技术 很难应用在数据流挖掘算法中，因为装载脱落技术在数据流流速过快时，直接丢 弃一部分数据流，而丢弃的数据流可能包含很重要的信息，这部分信息在模式挖 掘中可能代表着一个人们感兴趣的模式。 ( 3 ) 概略 概略技术。1 是随机投影一个特征子集的过程，是纵向地对数据流采样的过程。 概略技术已经应用在不同数据流之间的比较和聚合查询当中。概略技术的主要缺 点是其精确度有所欠缺。很难将其应用在数据流挖掘当中。 ( 4 ) 大纲数据结构 创建数据大纲是指对数据流保存概要信息以便进行下一步的分析的过程。小 波分析、直方图、分位数和频率矩都可以作为大纲数据结构。由于数据大纲只是 对整个数据集的近似表示，所以当采用大纲数据结构对数据流进行分析时，只能 产生近似的答案。 ( 5 ) 聚合 聚合是对数据流计算其统计度量，例如均值和方差，以概括整个数据流的过 程。聚合数据能够用于数据流挖掘算法，但是当数据分布变动过于频繁时，聚合 方法并不能很好地工作。文献 7 研究了离线的挖掘和在线的数据聚合相结合的 方法。 基于任务的解决方案就是对现有的算法、技术进行修正，或者发明新的方法， 以适应数据流处理过程的时空复杂度。主要的方法有近似算法( a p p r o x i m a t i o n a l g o r i t h m ) 、滑动窗口( s l i d i n gw i n d o w ) 和算法输出粒度( a l g o r i t h mo u t p u t g r a n u l a r i t y ，a o g ) 。 ( 1 ) 近似算法 近似算法在算法设计上有一个根本的出发点，就是为难以计算的问题寻找一 个近似解，即在一定的误差范围内产生一个近似解。由于计算资源的限制，很多 挖掘算法被认为是难以计算的问题。对于数据流挖掘问题来说，近似方法被很多 研究人员队为是一个直接的解决方案。然而，关于可用资源的数据产生速率问题， 中山大学硕士学位论文 基于核密度估训理论的多数据流聚类研究 不能通过近似算法加以解决。为了适应现有计算资源，其他的工具可以跟近似算 法一起使用。 ( 2 ) 滑动窗口 滑动窗口的提出是基于一个事实，用户更加关心的是最近产生的数据流的分 析结果。因此，我们可以对最近产生的数据流进行重点分析，而对过去的数据流 只保存其概要信息。 ( 3 ) 算法输出粒度 算法输出粒度1 首次提出了与计算资源相联系的数据分析方法，它能够根据 可用的内存资源和处理速度( 计算时间要求) 处理产生速率不断变动的数据流问 题。a o g 在资源受限的设备上进行本地数据分析，并产生或接受数据流信息。 a o g 有三个主要阶段：适应计算资源和数据流速率：进行挖掘：合并产 生的信息结构。a o g 已经应用到数据流聚类、分类和频繁模式计数1 当中。 1 1 5数据流应用系统举例 b u r l 等人为n a s a 和j p l 设计了d i a m o n de y e 系统”。该项目的目标在于使 得远程计算机系统和科学家们能够从在实时图像流中的空间物体提取模式。该项 目的成功使得“一个使用高度自动化的宇宙飞船、飞行器和传感器进行探险的时 代的来临”0 1 。该项目代表了数据流分析应用的早期成果。 k a r g u p t a 等人开发了第一个通用的数据流挖掘系统：m o b i m i n e “。该系统基 于客户端i n 务器模式，客户端采用p d a ，是一个股票数据的分布式数据流挖掘 应用。需要指出的是，整个系统的数据挖掘模块是在服务器端而不是在p d a 端， 通过p d a 利服务器的信息交流，将挖捌结果显示在p d a 上。随着手持设备计算 能力的不断加强，未来的趋势是将数据挖掘模块从服务端移到客户端。 k a r g u p t a 等人开发了交通车辆数据流挖掘系统( v e d a s ) ”，该系统通过每 辆汽车上的p d a 设备进行监控，可以连续地监控、获取数据流并从中进行模式 提取。数据挖掘模块是在p d a 端，而不是在服务端。然后采用聚类算法进行驾 驶行为分析。 t a n n e r 等人开发了e v e ( e n v i r o n m e n tf o ro n b o a r dp r o c e s s i n g ) 系统”0 1 ，该 中山大学硕士学位论文基于核密度估计理论的多数据流聚类研究 系统通过收集监控空间应用的传感器网络产生的数据流，并对其进行挖掘。有趣 的模式被传送到地面分站以进行进一步的分析。该系统代表了空间应用的一个典 型例子。大量的数据不断地产生，需要对流信息进行实时分析。 s r i v a s t a v a 和s t r o e v e 为n a s a 开发了随身携带的气象探测系统。，该系统采 用核聚类方法。这些技术用于数据压缩，该项目的出发点在于保存与地面中心发 送图像流的有限带宽。核方法由于其较低的计算复杂度，可以用于资源受限的环 境。 1 3 数据流聚类 1 3 1聚类分析简介 什么是聚类分析( c l u s t e r i n g ) ? 将物理或抽象对象的集合分组成为由类似的 对象组成的多个类的过程被称为聚类“1 。由聚类所生成的簇是一组数据对象的集 合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应 用中，可以将一个簇中的数据对象作为一个整体来对待。 聚类分析是一种重要的人类行为。早在孩提时代，一个人就通过不断地改进 下意识中的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类分析已经广 泛地用于许多应用中，包括模式识别、数据分析、图像处理、以及市场研究。通 过聚类，人能够识别密集的或稀疏的区域，因而发现全局的分布模式，以及数据 属性之间的有趣的相互关系。 “聚类的典型应用是什么? ”在商务上，聚类能够帮助市场分析人员从客户 基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生 物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固 有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的 分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发 挥作用。聚类也能用于对w e b 上的文档进行分类，以发现信息。作为一个数据 挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个 中山大学硕士学位论文 基于核密度估汁理论的多数据流聚粪研究 簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为其他 算法( 如特征和分类等) 的预处理步骤，这些算法再在生成的簇上进行处理。 数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘，统计学，机器学 习，空间数据库技术，生物学，以及市场营销。由于数据库中收集了大量的数据， 聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 作为统计学的一个分支，聚类分析已经被广泛地研究了许多年，主要集中在 基于距离的聚类分析。基于k 平均值( k m e a n s ) 、k 中心点( k m d e d i a n ) 和其 他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中，例如 s - p l u s ，s p s s ，以及s a s 。在机器学习领域，聚类足无指导学习( u n s u p e r v i s e d l e a r n i n g ) 的一个例子。与分类不同，聚类和无指导学习不依赖预先定义的类和 带类标号的训练实例。由于这个原因，聚类是观察式学习，而不是示例式学习。 在概念聚类( c o n c e p t u a lc l u s t e r i n g ) 中，一组对象只有当它们可以被一个概念描 述时才形成一个簇。这不同于基于几何距离来度量相似度的传统聚类。概念聚类 由两个部分组成：( 1 ) 发现合适的簇；( 2 ) 形成对每个簇的描述。在这里，追求 较高类内相似度和较低类问相似度的指导原则仍然适用。 在数据挖掘领域，研究工作已经集中在为大型数据库的有效和实际的聚类分 析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩性，方法对聚类复 杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大型数据库中混合 数值和分类数据的聚类方法。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。 数据挖掘对聚类的典型要求有：可伸缩性、处理不同类型属性的能力、发现任意 形状的聚类、用于决定输入参数的领域知识最小化、处理噪声数据的能力、对于 输入记录的顺序不敏感、高维性( h i g hd i m e n s i o n a l i t y ) 、基于约束的聚类、可解 释性和可用性。 1 3 2数据流聚类的研究现状 但是，尽管聚类问题在数据库、数据挖掘、机器学习，统计分析等领域得到 了广泛地研究，但是对数据流的分析仍为聚类算法提出了前所未有的挑战。由于 中山大学硕士学位论文 基于核密度估计理论的多数据流聚类研究 不可能完整地存储所有的数据，并且对数据是顺序地，一次或有限次地防问，这 就对数据流聚类算法提出了新的要求：算法必须是增量式的、对聚类的表示要简 洁、对新到达的数据处理要快速、对噪音和异常数据要稳健。因为数据流可以看 成是随时间不断变化的无限过程，其隐含的聚类可能随时间动态的变化而导致聚 类质量降低。 g u h a 等人。研究和分析了采用k m e d i a n 方法对数据流进行聚类的问题。 他们提出的聚类算法只需要对数据流进行一遍扫描，并且只需要很小的空间。确 切来说，算法需要o ( n k ) 的时间复杂度和o ( n e ) 的空间复杂度，其中，k 是聚类中 心的个数，n 是数据点的个数，s 1 。他们证明了d ( ”女) 的时间复杂度是任何带 常量系数的k - m e d i a n 算法的下界。算法初始时，先根据可用的内存，将一部分 样本划分成2 尼个聚类；然后，算法不断迭代，将其余的数据划分到这2 t 个聚类 中；最后，将2 个聚类划分成k 个聚类。 b a b c o c k 等人“2 1 使用了指数直方图( e h ) 数据结构改进g u h a 的算法“3 。他 们采用跟g u h a 类似的方法，但是他们通过维护e h 数据结构，解决了当两个聚 类中心的集合归并时相离很远的问题。 c h a r i k a r 等人“3 1 提出了另个k - m e d i a n 算法，克服了当迭代次数增大时近似 系数同时增大的问题。 d o m i n g o s 等人提出了一个通用的可伸缩的机器学习算法，将其称为快速机 器学习( v e r yf a s tm a c h i n el e a r n i n g ，v f m l ) 。该方法根据算法的每一步所 需要分析的数据来度量学习方法误差的上界。d o m i n g o s 等人成功的将该方法跟 k - m e a n s 聚类算法、决策树分类算法结合起来，提出v f k m ( v e r yf a s tk m e a n s ) 算法和v f d t ( v e r y f a s td e c i s i o nt r e e ) 算法，实现并通过人工数据集和w e b 真 实数据集检验其有效性。v f k m 使用h o e f f d i n g 边界来决定k m e a n s 算法每一步 所需要的样本，其他步骤跟k - m e a n s 算法一样，只是每一步使用更多的样本，以 满足h o e f f d i n g 边界条件。 o r d o n e z “”对k m e a n s 算法提出几点改进，以适应对二进制数据流的聚类。 他提出了增量式的k m e a n s 算法，并通过人工数据集和真实数据集的实验表明， 他提出的算法在大部分情况下性能优于其他的k - m e a n s 算法。该算法是一个一次 扫描的算法，时间复杂度为o ( t k n ) ，其中，丁是平均事务的大小，n 是事务的个 中山大学硕二卜学位论文基于核密度估计理论的多数据流聚类研究 数，k 是聚类中心的个数。使用二进制数据，可以简化分类数据的操作，并且不 用对数据进行规范化运算。该算法的主要思想是在分析完- - = t l 事务之后再对聚类 中心和权值进行更新，而不是每分析完一个数据就对其进行更新。 g u h a 等人”提出了l o c a l s e a r c h 算法，算法的甚本思想是基于分治的思 想使用一个不断的迭代过程实现有限空间对数据流进行k - m e a n s 聚类。 0 c h a l l a g h a n 等人“】发展了l o c a l s e a r c h 的思想，提m 了s t r e a m 算法， 并利用s s q 值证明了在许多情况下，s t r e a m 算法的聚类效果都比b r i c h 算 法要好。但是l o c a l s e a r c h 和s t r e a m 算法都有一个缺点，即只能提供对 当前数据流的种描述，而不能反映流数据变化情况”】。 a g g a r w a l 等人“1 提出了一个数据流聚类的框架，称为c l u s t r e a 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 的结果按一种称为金字塔时州桢 ( p y r a m i dt i m ef r a m e ) 的结构存储起来；离线组件( m a c r o c l u s t e r ) 根据用户指 定的时问片和聚类个数，对m i c r o c l u s t e r 收集的信息进行聚类。通过实验证明了 该算法具有很好的精度和效率。他们“提出了h p s t r e a m 算法，对高维数据流进 行先投影再聚类的算法。在很多例子中，h p s t r e a m 的效果优于c l u s t r e a m 算法。 g a b e r 等人。提出了轻量级聚类( l i g h t w e i g h tc l u s t e r i n g ，l w c ) ，这足一种 a o g 算法。a o g 在前面讨论过了。该算法使用一些阀值，代表不同簇之间数据 项的最小距离度量。算法根据预先指定的时问片和可用资源来调整这些阀值。 1 4 多数据流聚类 多数据流聚类是数据流聚类的一种特例。一般的数据流聚类问题，需要研究 的聚类对象是组成数据流的项。但在多数据流聚类中，待研究的对象是多个数据 流。传统的多数据流研究都集中在数字信号传输领域，但事实上多数据流聚类是 现实生活很常见的一类挖掘问题。在现实生活中，数据流往往不是以单一的形式 出现。比如在纽约的证券交易所( n y s e ) ，每秒都存在着成千上万笔证券、股票 的报价和交易。如果将每一支股票的报价看成一个数据流的话，那么成千上万支 股票就构成了一个多数据流的集合；美国航天航空局( n a s a ) 的一次航天飞船 中山大学硕士学位论文基于核密度估计理论的多数据流聚类硎f 究 任务中，每秒就有超过2 万个传感器在不断地运行着，监控整个任务的执行，每 一个传感器连续不断地产生数据，将每个传感器产生的数据看成数据流的话，那 么所有传感器产生的数据就构成了一个数据流的集合；又比如像分布在不同地理 位置的自治设备( 如高速公路交通探测