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

摘要： 随着计算机相关技术在各行业的普及应用，数据采集变得越来越方便。在这 些应用环境中，所要分析的数据不是有限的静止的数据集，而更像数据流一样源 源不断地产生。传统的统计分析、数据挖掘算法已经无法在这种快速变化着的数 据流上进行分析。在数据流上设计相应的数据挖掘算法显得日益重要。本文在归 纳、总结了数据流研究的现状的基础上提出了一个在数据流上的快速有效的密度 估计算法和一个在多数据流之间发现聚类关系的层次聚类算法。 具体地说，本文的贡献有以下几点： 1 提出了一个快速有效的数据流上的密度估计算法，该算法以传统的核密度估 计算法为基础，利用核合并技术，以损失一定精度的代价大幅度减少算法的 时间复杂度和空间复杂度。并对两种核函数的核合并过程进行了分析，计算 出了核合并的误差上界。使得算法在能够有效的处理大规模的数据流的同 时，得到相对准确的密度估计结果。最后通过大量的实验验证了算法的准确 性和有效性。 2 对层次聚类算法作了详细地分析，在数据流研究的环境中，提出了对多个数 据流进行聚类分析的问题，以此发现数据流之间的相关性。这在证券分析、 网络检测的环境中有着一定的实用意义。 3 提出了动态聚类树的数据结构与相应的旋转调整算法，当数据流发生变化的 时候不需要重新构造聚类树，而只需要对相关的节点进行局部的旋转调整就 可以得到更新的聚类结果。并在此基础上提出了一种解决多数据流上聚类问 题的的算法。 关键词：数据流，密度估计，聚类，数据挖掘 v a b s t r a c t ： d a t ag a t h e r i n gg r o w se a s i e ra st h ec o m p u t e ra n dr e l a t e dt e c h n i q u e sa r eu s e di n m o r ea n dm o r ef i e l d s i nt h e s ef i e l d s ，d a t at ob ea n a l y z e da r eg e n e r a t e dc o n t i n u o u s l y l i k ed a t as t r e a mr a t h e rt h a ni i i l i t es t a t i cd a t as e t t r a d i t i o n a ls t a t i s t i c a la n dd a t am i n i n ga l g o r i t h m sc a i nn o tw o r k o ns u c hr a p i d l y - c h a n g i n gd a t as t r e a m s i tb e c o m e sm o r ei m p o r t a n tt od e s i g nc o r r e s p o n d i n ga l g o r i t h m so v e rd a t as t r e a m s t h i st h e s i sp r e s e n t sar a p i da n de f f i c i e n td e n s i t ye s t i m a - t i o na l g o r i t h mo v e rd a t as t r e a m sa n dp r e s e n t sah i e r a r c h yc l u s t e r i n ga l g o r i t h mt o d i s c o v e rc l u s t e r sa m o n g m u l t i p l ed a t a s t r e a m sb a s e do nt h ec o n c l u s i o na n ds u m m a r y o fc u r r e n tr e s e a r c ho fd a t a8 t r e a m t h ec o n t r i b u t i o no ft h et h e s i si sa sf o l l o w s ： 1 p r e s e n t sar a p i da n de f f i c i e n td e n s i t ye s t i m a t i o na l g o r i t h mo v e rd a t as t r e a m s ， w h i c hi sb a s e do nt r a d i t i o n a lk e r n e ld e n s i t ye s t i m a t i o na l g o r i t h ma n do u r a l g o r i t h md i s t i n c t l yd e c r e a s et h et i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t yb y m a k i n gu s eo fk e r n e lm e l 7 百n gt e c h n i q u e st oc o m p r o m i s es o m ep r e c i s i o n s t h e e r r o r su p p e rb o u n do fk e r n e lm e r g i n gi sg i v e nb ya n a l y s i so nt v c od i f f e r e n t t y p ek e r n e lf u n c t i o n s t h ee x p e r i m e n t sp r o v e st h ee f f e c t i v e n e s sa n d e x a c t n e s s o f 0 1 1 i a l g o r i t h m 2 r a i s et h ep r o b l e mo fc l u s t e r i n ga n a l y s i so v e rm u k i p l ed a t as t r e a m s ，w h i c hh a s l o t sp r a c t i c a la p p l i c a t i o n si ns t o c ka n a l y s i s ，n e t w o r km o n i t o r i n g ，e t c 3 c o n s t r u c t st h ed a t as t r u c t u r eo fd y n a m i cc l u s t e r i n gt r e ea n dc o r r e s p o n d i n g r o t a t i o na l g o r i t h m t h ec l u s t e r i n gt r e en e e dn o tb er e c o n s t r u c t e dw h e nt h e d a t as t r e a m sc h a n g e ，i tc a nb ed o n eb yj u s tm a k es o m er o t a t i o no nt h eo l d c l u s t e r i n gt r e e f u r t h e ram e t h o do fr e s o l v i n gc l u s t e r i n gp r o b l e m k e y w o r d s ：d a t as t r e a m ! d e n s i t ye s t i m a t i o n ，c l u s t e r i n g ，d a t am i n i n g v l 第一章 己i 吉 丁l 口 本章一方面阐述本文的研究背景，包括对数据流数据处理、查询、分析的研 究现状：另一方面，本章给出了本文的研究目的、研究内容和组织结构。 1 1 研究背景 随着计算机技术在各行业的广泛应用，对每日产生的大量数据的及时处理变 得越来越重要。并且，在很多应用环境中，数据是源源不断的产生的。如银行的 交易数据、证券交易的行情数据、网站的点击数据、网络监测数据、生产制造业 的实时严控数据等。我们称这种类型的数据为数据流( d a t as t r e a m ) ，它通常具有 数据规模庞大，且不断增长的特点。在这些应用中，大量数据快速地源源不断地 产生，数据量的大小很难准确地估计，而且大多数情况下数据量几乎是无限增大 的。这使得传统的数据库管理系统( d b m s ) 祁i 难有效地管理这种数据流，并对其 进行查询、分析等操作。因为传统的数据库管理系统不是针对快速连续的数据修 改、查询设计的，也不支持如连续查询f c o n t i n u o u sq u e r i e s ) 这种典型的数据流应 用中的操作。另外，传统的数据库管理系统在设计上注重于在稳定的查询计划下 进行查询优化，得到准确的查询结果；而在数据流应用中，需要使用近似和自适 应技术来快速地得到查询结果，而不一定需要完全准确的结果。 在这些应用背景的推动下，对数据流的研究也成为了数据库界近来的一个研 究热点。目前对数据流的研究主要集中在对数据流进行连续查询、模型分析以及 构建数据流管理系统等方面，也有很多理论研究者在讨论如何将随机算法、近似 算法用于数据流的处理分析上。 本节将就目前对数据流研究的各个方向作初步的的阐述。 j 引言 1 1 - 1 数据流的模型 一般我们把具有以下几个特征的数据称作数据流： 1 数据量一般是随时间无限增长的。 2 数据是实时产生的。 3 无法对数据产生的速度和规模进行预测和控制。 4 一项数据处理过后就会被丢弃或者压缩存档，无法对历史数据进行随机访 问。 由于数据流的这些特点，大多数传统的数据处理技术无法有效快速地处理数 据流中的数据。d o m i n g o s 等人认为，一个系统或者算法如果要很好地处理这类数 据量巨大、永无止境的数据流，至少必须满足以下几点要求【18 ： 处理数据流中每条记录必须只使用很短且恒定的时间，否则将会跟不上数据 到来的速度； 只能使用固定大小的内存空间，与已经处理过的数据量的大小无关； 只需要对数据进行一次扫描，因为在大多数应用中，或者无法得到历史数 据，或者根本没时间去访问历史数据； 必须能够在处理的任何阶段输出可用的结果，而不是等到处理完所有的数据 后才输出结果，因为我们可能永远到达不了数据的尽头； 理想情况下，应该能够得到一个与传统算法在没有任何约束条件下在相应的 静态数据集上得到的结果相同或者近似的结果。 当数据流的模型发生变化时，计算的结果必须也要能够及时得到调整，反映 数据的变化。 这些要求看上去很难达到，但是只有这样才能真正有效的处理大规模的数据 流上的数据。在一些特殊的情况下，如果数据流的规模不是很大，产生的速度也 不是很快，而且硬件设备的存储和计算处理能力远远超过数据流中的数据量的时 候，可以放松其中的几点要求。但在时间复杂度和空间复杂度上算法还是要满足 一定的要求：即，时间复杂度最好和数据量的大小呈线性关系；空间复杂度最好 和数据量的大小无关，或者要保持在对数关系之内。 2 1 1 2 数据流上的查询 1 引言 在连续的数据流上进行查询与在传统的数据库管理系统中进行查询有很多相 似的地方。但是，在数据流上进行查询有两个重要的特征与在传统的数据库管理 系统中进行查询不同f 6 1 。首先一点是查询分为单次查询( o n e t i m eq u e r i e s ) 与连续 查询( c o n t i n u o u sq u e r i e s l 。单次查询与在传统的数据库管理系统中的查询类似， 是对某个时刻数据集的快照( s n a p s h o t ) 进行一次查询操作，将查询的结果返回给 用户。而连续查询是数据流上特有的操作，由于数据流环境中的数据集不是静态 的，而是不断有数据插入和更新。用户需要的也不是在某个时刻的静态查询结 果，而是对整个数据流的一个动态监测。连续查询一旦提交入数据流的管理系统 之后，将会注册在系统中，随着数据流的不断变化持续地产生查询结果。而不是 简单的对数据集的快照进行查询。 另一点不同是查询分为预定义查询( p r e d e f i n e dq u e r i e s ) 与即席查询( a dh o c q u e r i e s ) 。预定义查询是指在要查询的相关数据产生之前，查询请求已经进入 数据流管理系统中。预定义查询通常是连续查询，一些计划好的单次查询也 可预先定义。而即席查询通常是在数据流进行的中间发出的查询。它可以是单 次查询，也可以是连续查询。即席查询是数据流管理系统中最复杂的操作，由 于事先不知道查询内容，也很难对查询进行优化处理，并且即席查询所需的数 据也许在查询发出之前就已经在数据流中出现过，并已经被系统丢弃或者存档 了。s t a n d f o r d 的s t r e a m 小组 4 】，【2 6 】，【8 l 以及b e r k e l e y 的e d d y 系统f 5 1 都对连续 查询作了很多的研究。 16 1 ， 3 2 1 ，【1 1 1 ， 3 5 1 、 3 4 1 ， 4 】也对数据流上的连续查询的一 些方面作了很多工作。 1 1 3 数据流上的分析处理 对数据流的分析主要有以下几方面的工作 利用随机算法使用很少的存储空间维护数据流上的结构信息，用这些信息 可以计算出一些常用的统计量，如r ，最等。并能够保证在结构信g a i t 算 出的结果与正确的结果之间的误差在以很大的概率在可控制的范围之中。 女n l n d y ke r e 的 1 2 ， 2 5 】， 2 7 】等研究就是再s k e t c h 技术的基础上开展的。 利用随机抽样技术对数据流进行采样，然后对规模较小的样本数据进行分析 来估计整个数据流上的数据分布。 利用一些特殊的数据结构，通过对数据流的单次扫描，以较小的存储空间保 留数据流上的中位数( m e d i a 璐) 、分位数( q u a 础i l e s ) 等统计信息。f 7 1 f 1 3 利 用指数直方图( e x p o n e n t i a lh i s t o g r 锄) 技术在数据流的滑动窗口上t 计j 算l - - - 统j 计。 3 t 引言 量。f 1 4 ， 2 4 ， 4 4 ， 3 7 】， 1 9 ， 1 9 】， 3 6 ， 2 1 2 0 等也是使用类似的汇总技术在 数据流上计算各种的统计信息。 利用小波变换、富里叶变换等数学工具提取数据流中的主要信号分量，发现 数据流变化的特征，检测数据流的变化 4 8 1 ， 2 3 】。 除此之外， 3 1 ， 1 5 1 ， 2 1 1 ， 2 2 】， 3 3 ， a g l ，【3 1 1 ， 1 7 1 等也是近来在数据流上进行 分析计算和数据挖掘的一些研究。 1 1 4 数据流管理系统 接下来我们对近来出现的几个数据流上的数据管理系统做一个回顾 在t a p e s t r y 系统 4 3 中，为了对不断添加的电子邮件地址和电子公告栏消息数 据库中进行基于内容的过滤，所以要进行连续的查询。为了确保有效的评估并 得到只增的查询结果，查询语言用的是s q l 的一个受限子集。a l e r t 系统( 4 0 使用 了定义在特殊的只增活动表上的持续查询，以提供一种实现传统s q l 数据库中事 件条件行动式触发器的机制。 o p e n c q 和n i a g a r a c q 系统f l l 】可支持连续查询，从而能够监视散布在广域网 上的持久数据集，如互联网上的w e b 站点。o p e n c q 使用了一种基于增加视图 维护的查询处理算法， 丽n i a g a r a c q 提出了能提高评估效率持续的查询分组的技 术，从而更注重查询数量上的可扩展性。在n i a g a r a c q 项目中，s h a n m u g a s u n d a r a m 等人对在数据流的查询计划中支持模块化操作符的问题进行了讨论，v i g l a sa n d n a u g h t o n 4 5 提出了一种数据流查询的基于等级的优化，这是一种基于数据流的 到达和对数据的处理的新的优化方法论。s e s h a d r i ，l i v n y , a n dr a m a k r i s h n a nf 4 1 】 f 4 2 1 为查询有序关系( 序列) 提出了种代数和声明性查询语言。在很多应用 中，持续查询需要引用流的先后顺序，尤其是数据流上的滑动窗口。这方面的相 关工作还包括时间序列数据库，在时间序列数据库中，元组的顺序隐含在时间 中，可以被利用来查询、建立索引和对查询进行优化。 t e l e g r a p h 项目f 3 4 1 使用了数据流管理系统中的一些目标应用系统和些基本 的技术想法。t e l e g r a p h 使用了一个可适应的查询引擎( 基于e d d y 的概念 5 1 ) 以在易 变的和不可预测的环境( 如互联网或传感器网络中自治的数据源) 中有效地处 理查询。m a d d e n 和f r a n k l i n 3 4 1 3 5 1 致力于传感器产生的数据流上的查询执行策 略，m a d d e ne ta i f 3 5 1 对多重持续查询上的可适应处理技术进行了论述。 1 2 关于本文 根据前面几节的分析，我们看到，数据流有着广泛的应用环境，基于数据流 4 i 引言 的研究与分析工作无论在理论研究领域或者是生产应用领域都非常有意义。国际 上很多著名高校和研究机构都已成立了相关的研究小组，并开发了若干个不同的 原型系统，为进一步系统地研究数据流技术打下了良好的基础。国内虽然已经开 始对数据流有了一定的研究工作，但是目前还处于比较落后的阶段，理论研究深 度不够。 1 2 1 研究内容 本文的研究目标为：研究在数据流上进行分析的一些相关技术，并对其中的 一些特定问题，如数据流上快速准确的密度估计，多数据流之间的聚类分析等问 题进行研究。 1 2 2 本文的贡献 本文对数据流上的密度估计问题作了深入的研究，对传统的核密度估计进行 了仔细的分析，提出了通过牺牲一定的精度来降低空间复杂度和时间复杂度的想 法，提出核合并技术实现这个想法，并对核合并造成的精度误差作了分析，对两 种不同的核函数分别计算出了误差的上界。并在此基础上构造了一个快速的数据 流上的密度估计算法。本文对数据流上的聚类分析作了全面的研究，提出了多数 据流上的聚类分析的问题。设计了动态聚类树的数据结构，并通过实际数据的测 试验证了算法的有效性和准确性。 1 2 3 本文结构 本文一共分四章，第一章总体介绍数据流的基本概念和国际上目前的研究状 况。第2 章探讨了在数据流上的密度估计问题，提出了一个快速高效的数据流上的 密度估计算法。第3 章讨论了多数据流上的聚类问题，并提出了个动态聚类树的 数据结构。最后，在第4 章，作者对全文进行了总结，并在此基础上提出对将来工 作的展望。 5 第二章 数据流上的密度估计算法 密度估计是数据分析与挖掘任务中常用的一项基本技术，对大量数据进行密 度估计能够获得数据分布的大致情况，所以此项技术一直得到研究学者的高度重 视。但传统的各种密度估计方法由于空间复杂度和时间复杂度都较高，需要的内 存空间和处理时间都对数据量的大小非常敏感，并且需要对数据流做多次的扫 描。这将不适合于数据流动态变化、数据量大的特点，因此不能直接应用于数据 流。本章深入研究了传统的密度估计方法，提出了核合并的方法，通过牺牲一定 精度，显著的减少算法所需的时间复杂度和空间复杂度，在分析了核合并所造成 的误差的上限之后，给出了一个在数据流快速有效地进行密度估计的算法。 2 1 密度估计简介 根据从一个总体中抽出的样本去估计总体分布的密度函数，在应用上有重要 意义。通过这种估计，可以识别和选定数据的大致模型。设墨，。，五。是从具有 未知的概率密度函数，的总体中抽出的独立同分布( i i d ) 的样本，要根据这些样本 去估计，。确切地说，要对每个指定的茁去估计，( z ) 的值。 假设某个概率空间有着特定的密度函数，( 茁) ，现在从中独立同分布的抽取随 机变量z 1 ，。，z 。密度估计问题就是要基于样本( z ”。z 。) zx n 构造出，( z ) 的一个估计矗( x p ；z ) 。 密度估计方法主要分为两大类：参数( p a r a m e t r i c ) 估计与非参数( n o n p a r a m e t r i c l 估计 1 。参数估计方法需要对数据的分布有一定的先验知识，要基于很特殊的假 定，只有当这些假定至少是近似成立时，方法才有其优越性。而基于直观的非参 数估计方法则有更大的适应性，可以在没有先验知识的前提下获得较好的估计结 果。 常见的非参数估计技术有以下几种： 6 2 数据流上的密度估计算法 多维直方图( m u l t i v a r i a t eh i s t o g r a m ) 最近邻法“h en e a r e s tn e i g h b o rm e t h o d ) 核密度估计( k e r n e le s t i m a t i o n ) 其中，多维直方图的方法只适合于维数低的数据。当数据维数高的时候，直 方图技术所需的空间将随着维数增加成指数级的增加；最近邻法容易受局部噪音 的影响，使得模型的估计变得很难；而核密度估计方法适合于中小规模的数据 集，它可以很快的产生一个渐进无偏的密度估计，有着良好的概率统计性质。 2 1 1 核密度估计 核密度估计的原理和直方图技术有些类似，直方图记录了在每个区间中点的 个数或频率，使得图中的矩形条的高度随着数值个数的多少而变化，但是直方图 很难给出较为精确的密度估计。核估计也是计算某一点周围的点的个数，只不 过是对于近处的点考虑多一些，对于远处的考虑少一些。具体来说，如果数据 为。，2 。，在任意点。处的一种核密度估计为： 厶( z ) = 焘 娄c 竿1 ( 2 1 ) 其中k h ( t ) = h - 1 t c ( a - 1 ) 。这里h 称为带宽( b r a n d w i d t h ) ，般来说，选的 带宽越大，估计的密度函数就越平滑，选得较小则估计的密度曲线和样本 拟合得较好。k ( ) 称为核函数( k e r n e lf u n c t i o n ) ，它通常满足对称性，非负性 及，( z ) 如= 1 。常用的核函数有以下几种： 核函数名称 核函数k ( x ) 均匀( u n i f o r m ) ；z ( i x i 1 ) 三角( t r i a n g l e )( 1 一f x l ) i ( i m is1 ) e p a n e c h i k o v；( 1 一x 2 ) 蚓。1 ) 四次( q u a r t i e l 嚣( 1 一t 4 ) ( i z l 1 ) 高斯( g a u s s ) 去e x p ( 一x 2 ) 余弦( c o s i n u s )詈e 。s ( z ) 蚓。fs1 ) 图2 1 表示了核密度估计的构造过程，1 0 条虚线分别表示1 0 个数据点上的核函 数( 这里采用正态函数作为核函数) ，实线表示将这些核函数累加后得到的密度 7 硷一 z 。 2 数据流上的密度估计算法 图2 1 ：核密度估计的构造( 正态核函数用虚线表示) 函数估计。核密度估计可以被看作是在每个数据点上面放置一个“突起”，然 后在x 坐标上将这些“突起”的高度累加起来，得到最后的密度估计结果。 对于中小规模的数据集，核密度估计是一个很好的方法：它不会在高维数据 的情况下产生维数灾难，也无需很多的参数来调整算法效率。并且当核函数k 满 足一定的性质的时候，核密度估计具有渐进无偏性、均方相合性、依概率一 致收敛性等良好的特性。但是当应用于超大规模数据集时，由于其空间复杂度 为p ( 礼) 、时间复杂度为0 ( n 2 ) ，核密度估计方法的计算效率将大大降低。而且， 由于计算需要对数据点进行多次扫描，所以无法直接应用在数据流上。 2 2 数据流上的密度估计 由于传统和密度估计算法在空间复杂性和时间复杂性上无法满足处理数据流 的要求，我们对算法进行了分析，发现当适当降低对精度的要求的时候，我们可 以通过一定的数据结构和相应的算法，降低核密度估计算法的空间复杂度和时间 复杂度，使之能够处理大规模的数据流。 8 2 。2 1m 一核 2 数据流上的密度估计算法 传统的核密度估计方法中，每个数据点都用一个核函数表示。如果从分布中 抽取出的随机变量的样本大小为n ，那么在按照公式2 1 计算估计五( z ) 的时候也 需要n 个核函数。所以，要能够有效的处理数据流，就必须找出一种办法减少计 算 ( z ) 时所需要用到的核函数的个数。 定理2 1 核函数具有可累加性，即几个参数相同的核函数可以用个有权重的相 同参数的核函数所代替。 证明： 设k 1 ( z ) = k h 。( z x 1 ) ，k 2 ( z ) = k h 。( z x 2 ) h 2 = h 则 并且 1 ( z ) + k 2 ( 。) 若x i = x 2 = cj & h l = = ，( z x 1 ) + 。( z 一x 2 ) = k k z t c ) 4 - k h ( x 2 一c ) = 2 k a ( z c )( 2 2 ) p t k h ( z 1 一c ) + p 2 - k l , ( z 2 一c ) = ( p l + p 2 ) - k x c ) ( 2 3 ) 定理2 1 说明，如果一个或多个数据点有相同的值，那么我们可以用一个有权 重的核函数去代表这些数据点。核函数上的权重的大小就是核函数所代表数据点 的个数。传统的方法中，由于每个核函数只能代表一个数据点，则核函数的个数 与数据点的个数相同。而如果一个核函数可以代表多个数据点的时候，核函数的 个数将小于数据点的个数。 定义2 1 我们称只能代表一个数据点的核函数为简单核( s i m p l ek e r n e l ) ，称能代 表多个数据点的核函数为m 一核f m k e r n e l ) 。 4 m 一核除了简单核有的两个参数：中心( m e a n ) 五和带宽( b a n d w i d t h ) 九外，还 有一个表示权重( w e i g h t ) 的参数p 。公式2 4 表示了一个中心为五，带宽为 ，权重 为p 的m 。核核函数。 ：k ( 宰) ( 2 4 ) 9 2 数据流上的密度估计算法 i n p u t ：d a t as t r e a m 义：= z l 】z 2 ，z n j - 一， o u t p u t ：ad e n s i t yf u n c t i o n ，( z ) o v e rd a t as t r e a m x 1 ：i n i t i a t e ( k e r n e l - l i s t ) ； 2 ：c o u n t = 0 ； 3 ：w h i l es t r e a mn o te n dd o 4 ：r e a dz f r o mt h es t r e a m ； 5 ：i fk e r n e l - l i s t f i n d k e r n e l b y m e a n ( 。：i 1 = = t r u et h e n 6 ： c u r k e r n e l = k e r n e l l i s t g e t k e r n e l b y m e a n ( x t ) ； 7 ： c u r k e r n e l w e i 曲t + + ； 8 ：e l s e 9 ：g o u n e r + + ： 1 0 ：m k e r n e l = n e w k e r n e l ( x l ，1 ) ； 1 1 ： k e r n e l _ l i s t i n s e r t k e r n e ( m k e r n e l ) ； 1 2 ：e n d i f 1 3 ：e n dw h i l e 1 4 ：f o ri = 0t og o u n t e rd o 1 5 ： ，) + = k e r n e l l i s t g e t k e r n e l b y o r d e r ( i ) ； 1 6 ：e n d f o r 算法2 1 ：n a i v e d e n s i t y e s t i m a t e ( x 1 2 2 2 直接的密度估计算法 基于前面引入的公式2 2 和2 3 ，我们可以构造出一个直接的密度估计算法。 在算法2 1 中，有着相同中心的简单核将被合并为一个m 一核( 第5 行一7 行) 。由于 算法2 1 只是简单地将有相同中心的简单核用一个有权重的m - 核所替代，所以这个 算法的结果与传统的核密度估计算法的结果相同。而且如果数据流中有很多数据 点有相同的数值s ，那么这个算法所需的内存空间将比传统的核密度估计算法所需 的内存空间少很多。但是这个算法所需的内存空间与数据流中的数据分布情况又 很大的关系，在极端情况下，如果数据流中的数据点的数值都两两不相同，那么 这个算法与传统的核密度估计算法的效率相同。 2 。2 3 核合并方法 简单地将中心相同的核函数合并起来并不能有效的减少所要保留的核函数的 个数，但是我们从简单的核合并中得到启发，并通过观察发现，可以通过继续合 并中心相近的核函数来进步减少所要保留的核函数的个数。 1 0 2 数据流上的密度估计算法 图2 2 ：核合并的操作 图2 2 表示两个中心不同的核函数合并的操作，k e r n e l1 和k e r n e l2 合并后 并不是一个标准的核函数的形状，我们无法用原来核函数的形式去表示它，但是 我们可以用个核函数去近似它。这时就利用近似的核合并技术，近似的核合并 可以用下面的公式表示。 p k h 。( z x i ) - 4 - 乃砺j 忙一玛) ( 胁+ p d ) k 麓( z 一爿熹)( 2 5 ) w h e n l 五一玛i 5 l a n d 慨一h j j e 2 公式的左边表示两个中心分别为托和玛的核函数尬，玛，他们的带宽分 别是 。和，公式的右边表示用一个中心为j 蛴，带宽为螺的m 一核k 孟去代表他 们。 虽然在大多数情, z 一1 4 一个m ，核能够完全与两个中心不同的核函数的 和相等。它们之间的差就是合并所带来的误差。我们用m _ c o 时来表示这个误差。 直观上看，这种误差就是图2 2 中点线与虚线之间的三- 距离。具体定义如下： 2 数据流上的密度估计算法 m c o s 5 g ( x l ，螺) l p l k h 。q x 矗+ p j k h ，( z x ) l ( 胁+ h ) k h m ( z 一磷) l d x f 2 6 1 我们分析考察了几种核函数合并的具体情况，得出了用这种方法进行核合并 所造成的误差的上限。 定理2 2 若采用均匀函数作为核函数，两个核函数k 1 ，鲍的参数分别为m ，x 1 ，h l 和p 2 ，x 2 ，h 2 ，且i x l 一x 2 1 l ，i p l p 2 s 2 ，则合并后的误差最多为出掣+ p 2 忙l + h i 十0 2 j 1 h l + 5 2 证明：设耳1 ( z ) = 瓜。( z x 1 ) ，k 2 ( 茁) = 风。( 茁一托) ，且l x 。一x 。 = e ，i h 。一h 2 i ： 2a 不失一般性，设x 1 局，h 1 茎h 2 。 m _ c o s t 2 一( p l + p 2 ) k “z 一( x 1 十互1 e 1 ) ) 恤 l p - ( 甄、( z x 。) 一k 。，+ 。( z 一( x ，+ j 乱) ) ) d 。 + f 戌( 。帼一+ 州) _ 玩。峙扣( x ，+ 1 ) ) ) 陋 2 p 1 ( 上h i + e 2 ，( 掣 x i + ；1 x 】+ e 1 + 1 + f ， 2 p 1 置转2 p 2 x z + ；“v i 泛! ，c 忐冲 置一扣；揪i 十e 2 ) p l ( e i + h i ) n 1 p 2 ( 8 ，1 + h i + 8 2 ) l + 2 一 出 碥 一+ 一恐 恐 一 一 舶 晚 + + x x 一 一 壕 嘏儿儿 如 竿身肌 扣0 一 乜+ h 咄 扛 +x 2p 2+ 2 数据流上的密度估计算法 定理2 3 若采用高斯函数作为核函数 和p 2 ，噩，h 2 ，且i 蜀一x 2 l e 1 ，胁一p 2 三卫! ! ( 墅2 主! 型 赫8 两个核函数甄，k 2 的参数分别为p 1 ，x 1 ，h 1 2 ，则合并后的误差最多为豫掣+ 证明：设k 1 ( z ) = k h 。渖一x 1 ) ，k 2 ( z ) = k h ：( 茁一x 2 ) ，且1 x l x 2 1 = l1 h l h 2 j = e 2 。不失一般性，设x l 茎而。 m c o s t = 9 ( 爿而，h m ) 2 i ；1 k h , ( z x 1 ) + p 2 k b ( z x 2 ) 一( p 1 + p 2 ) k h 赢( 。一x 南) l d z 5 5 p - k h 。( + p 。甄。( z 一而) 一( p i + p 2 ) k h 什“z 一( x z + 互1 - ) ) 陋 p - ( k h 小一剐一。砖如一( x ，+ 知) 陋 十lp 2 ( 。帼扛一( 凰+ 1 ) ) 一蚝州e 2 ( z 一( x + ；) i 出 2 p z ( 甄。知一墨) 一州一z 一( x ，+ ；s i ) ) 出 + e ) 一k k ，十 。( 卫一( x l + 百19 1 ) ) 如 x 1 + 日 。p ( 高产( 一； x - ，x 1 ) 2 ) 一而纛卅互1 ( 箐害) 2 ) 1 低 l + j 2 垒! 逛! 型 、瓦8 e x p ( 一百1 ( 专警) 2 ) 唧( 一；( 箐n ) 如 。2 p 2e i ( 9 e 2 + 1 2 ) 2 z8 ( 2 7 ) z 恂 扣0 一 砌 铊 2 数据流上的密度估计算法 定理2 4 按照公式2 5 所定义的核合并操作，在选取特定的核函数形式的时候，核 合并操作所造成的误差是有限的 证明：根据定理2 2 ，2 3 易得 根据定理2 4 我们可以知道在核合并的过程中可以得到最小误差的上限。但如 何使误差达到或者接近这个上限呢? 我们总是希望在每次核合并的时候m z z o s t 都 尽可能的小。在公式2 6 中，可以看到9 ( x ，h ) 是一个有界函数，所以我们是可以找 到全局最小点的。在寻找g ( x ，h ) 的全局最小点的时候，由于我们不知道g ( x ，h ) 的 导数，所以我们采用d o w n h i l ls i m p l e xm e t h o d 方法去寻找函数的最小点。n e l d e r 和m e a d 在f 3 8 1 提出了d o w n h i l ls i m p l e xm e t h o d 的方法，这是个快速的多参数寻 优的个方法，通过反复的迭代可以快速的逼近函数的最小点。而且计算的代价 相对的很小。 根据公式2 5 我们可以看到，在经过( n m ) 次核合并之后，我们得到了m 个m 一 核，它们的参数分别为墨，辩，店( i = 1 m ) 。现在我督j 可以将原来的核密度估计 公式改写为： 舭，= 去，器c 等m 恍砉徊 s ， 与原先的核密度估计的示意图2 1 相比较，图2 3 表示了经过核合并后的密度 曲线的构造，其中原有的些核函数被合并后的m 一核( 点线) 所替代。并且可以看 出，经过合并后只剩下4 个m 一核。但是最终合成的密度曲线与原先的相差不大， 这之间的差异就是这个合并过程带来的绝对误差。经过大量的实验表明，这个核 合并过程所造成的绝对误差是很小的，而且可以由一些参数所控制。 2 2 4 近似的密度估计算法 根据公式2 5 我们可以对前面提出的直接的密度估计算法( 算法2 1 ) 进行修改， 得出一个更有效率的密度估计算法( 算法2 2 ) 。 在处理数据流的过程中，我们在内存中保存一个大小是m 的数组，数组中 每一项都是一个4 元组，( x ，h ，矿，m _ c o s t ) ，数组按照x 。的大小进行排序。4 元 组中前面三个参数是存储一个m - 核所必需的，它们分别表示这个核函数( z 1 的 中心为x ，带宽为h + ，权重为p + ，整个核函数的形式为菇k ( - - z z - ) 。第4 个参 数m _ c o s t 表示当前核函数与数组中下一个核函数的合并代价。从定理22 和23 中 我们可以看出，中心相近的核函数的合并代价小于中心距离大的核函数之间的合 并代价。所以我们只需要计算并保存中心相邻的核函数之间的合并距离就可以 1 4 2 数据流上的密度估计算法 图2 3 ：用带有权重的核函数来对密度曲线进行估计 了。每当处理数据流中新到达的数据的时候，算法首先构造出代表这个数据的核 函数，并放入4 元组中插入数组中，计算出它与相邻核函数的合并代价。假如数组 已经满了，算法就在数组中挑选合并代价最小的一对核函数，对它们进行合并操 作，并将合并后的核函数插入数组，计算新的合并距离，删除原先被合并的两个 核函数，释放出相应的空间。继续处理数据流中下一个数据。 算法中第2 行至第2 l 行是主循环体，其中第5 - 6 行表示将新的数据插入数组并按 照x 进行排序。第8 1 5 行是算法的核心部分，表示了通过合并减少存储空间的主 要操作。第1 6 2 0 行表明算法可以在任何时候输出计算的结果。 2 3 算法分析 2 3 1 算法复杂度分析 可以看出，在算法处理的过程中，数组的大小保持恒定，为m 。因此算法的 空间复杂度为0 ( m ) ，而m 与数据流的大小没有直接的关系。并且，对数据流中到 达的每一个数据，我们仅计算出它与邻近核函数的合并代价，当数组空间满的时 1 5 2 数据流上的密度估计算法 i n p u t d a t as t r e a mx = ( ，z 。，) o u t p u t ：ad e n s i t yf u n c t i o n ，( z ) o v e r d a t as t r e a x nx 1 ：i n i t i a t e ( k e r n e l l i s t ) ； 2 ：k e r n e l l i s t s e t b u f f e r s i z e ( m ) ； 3 ：w h i l es t r e a mn o te n dd o 4 ：r e n dz f r o mt h es t r e a m ； 5 -c u r k e r n e l = n e wk e r n e l ( x t ，1 ) ； 6 ：k e r n e l l i s ti n s e r t k e r n e l ( c u r k e r n e l ) ； 7 ： k e r n e l l i s t r e c a l c u l a t e m e r g e c o s t 0 ； 8 ：i fk e r n e l l i s t i s f u l l ( ) t h e n 9 ：t m p k e r n e l = k e r n e l l i s t f i n d m i n i m a l m e r g e p a i r 0 ； 1 0 ： m k e n r e l = m e r g e k e r n e l ( t m p k e r n e l ，t m p k e r n e l n e x t k e r n e l ) i i ： k e r n e l l i s t d e l e t e k e r n e i ( t m p k e r n e l n e x t k e r n e l ) ； 1 2 ：k e r n e l l i s t d e l e t e k e r n e l ( t m p k e r n e l ) ； 1 3 ： k e r n e l _ l i s t i n s e r t k e r n e l ( m k e r n e l ) ； 1 4 ： k e r n e l l i s t r e c a l c u l a t e m e r g e c o s t 0 ； 1 5 ：e n d i f 1 6 ：i fn e e dr e s u l tt h e n 1 7 f o ri = 0t ok e r n e l l i s t c o u n t ( 1d o 1 8 ： ，( z ) + = k e r n e l _ l i s t g e t k e r n e l b y o r d e r ( i ) ； 1 9 ：e n d f o r 2 0 ：e n d i f 2 】：e n d w h i l e 算法2 2 ：a p p r o x i m a t e d e n s i t y e s t i m a t e ( x ) 候进行一次合并操作。这样，对每一个数据的操作都可以在个恒定的时间内完 成，也