计算机科学2 0 0 2 V 0 1 2 9 - - 8D E O D S ：快速准确的数据流密度估计D E O D S ：Q u i c ka n dA c c u r a t eD e n s i t yE s t i m a t i o no v e rD a t aS t r e a m蔡致远魏藜钱卫宁周傲英 ( 复旦大学计算机科学与工程系上海2 0 0 4 3 3 )A b s t r a c tI nm a n yr e a ll i r ea p p l i c a t i o n ss u c ha sn e t w o r km o n i t o r i n ga n dt e l e c o m m u n i c a t i o nd a t a m a n a g e m e n t ，d a t ac o m ei nt h ef o r mo fc o n t i n u o u ss t r e a m s F i n d i n gv a l u a b l ei n f o r m a t i o nf r o md a t as t r e a mt i m e l ya n de f f e c t i v e l yh a sb e c o m ean e wh o tr e s e a r c ht o p i co fd a t am i n i n gf i e l d D e n s i t ye s t i m a t i o n ，w h i c hc a ng e tt h er o u g hd i s t r i b u t i o no ft h ed a t a ，i sat e c h n i q u eu s e do f t e ni nd a t am i n i n g H o w e v e r ，t r a d i t i o n a ld e n s i t ye s t i m a t i o nm e t h o d sp e r f o r ma w f u l l yo nd a t as t r e a m ，f o rt h e ya r e n o ts u i t a b l et od a t ac h a n g i n gd y n a m i c a l l ya n di nh u g ea m o u n t A f t e rs t u d y i n gt r a d i t i o n a ld e n s i t y e s t i m a t i o nm e t h o d si n t e n s i v e l y ，t h i sp a p e rb r i n g sf o r w a r dt W On o v e lt e c h n i q u e sc a l l e d “i n c r e m e n t a le s t i m a t i o n ”a n d “k e r n e lm e r g e ”a n db a s e do nt h e md e v e l o p saD E O D Sa l g o r i t h mt od od e n s i t y e s t i m a t i o no v e rd a t as t r e a m T h eD E O D Sa l g o r i t h mh a sf o l l o w i n gs t r i k i n gf e a t u r e s ：1 ) i to n l y n e e d saf i x e ds i z eo fm e m o r y ，2 ) t h er u n n i n gt i m ei Si nl i n e a rw i t ht h ed a t as i z e ，3 ) i tc a no u t p u tau s a b l em o d e la ta n yt i m eo fp r o c e s s i n g ，4 ) t h ea c c u r a c yo ft h er e s u l ti Sc o m p a r a b l et ot h a to fs t a t i c k e r n e Id e n s i t ye s t i m a t i o n E x p e r i m e n t ss h o wt h a t 。t h ea l g o r i t h mi sb o t he f f e c t i v ea n de f f i c i e n tt od i v e r s ed a t as t r e a m s K e y w o r d sD a t as t r e a m ，D e n s i t ye s t i m a t i o n ，D E O D S 算法1引言在许多科学与商业应用中，人们都会碰到需要 处理大量源源不断的数据的情况，如银行的交易信 息、电信公司的电话记录、网络服务器的点击日志 等。我们称这种类型的数据为数据流( d a t as t r e a m ) ， 它通常具有数据规模庞大，且不断增长的特点。 数据流中往往蕴含着丰富的、有价值的信息。如 何从数据流中有效地获取有用的信息? 这一问题日益受到了人们的关注 5 8 , 1 0 , 1 1 。密度估计( d e n s i t y e s t i m a t i o n ) 是数据挖掘中一种应用广泛且非常有用的技术 1 Z , 1 3 。如果在数据到来的同时，估计出数据 流的密度函数，就可以掌握数据流的数据分布情况， 从而快速地发现数据集中的稀疏或稠密区域，或获得中位数( q u a r t i l e ) 等统计信息 2 4 9 。因此数据流 上的密度估计是非常重要而且有意义的。根据我们 对大量参考文献的调查，目前国际上还没有这方面的研究。数据流的特点决定了传统的密度估计方法不能 直接应用于数据流。因为数据量很大，而且是持续 的，与数据流的规模相比，内存或缓存等存储空间是 极其有限的。将所有数据存储下来再进行分析显然 是不可行的，需要一种动态的增量式的算法来处理 数据流。而且，多数应用要求在数据到来的同时进行 分析决策，这对处理时间提出了更高的要求。研究表 明，一种算法如果要很好地处理数量巨大、永无止境的数据流，必须满足以下标准 6 ： 对数据流中每条记录的处理必须在很小的固定时间内； 处理过程中对内存的占用必须是有限的，与算法已经读入了的数据量记录无关； 只能对数据进行一次扫描，因为在大多数应用 中，或者数据是无法得到的，或者根本没时间去访问以前的数据； 它必须能在处理的任何阶段输出一个可用的 对数据进行描述的模型； 在任何时间点上，模型都必须是最新的，必须 能实时地反映数据的变化。 核密度估计是一种性能优异的无参数密度估计 方法。但是，当应用于大规模数据集时，它的计算代 价太高，因此并不适用于数据流这种规模大且不间 断的数据。本文研究针对数据流的快速有效的密度 估计方法。通过对传统核密度估计方法的观察，我们 提出了增量估计和核合并两种新技术，用来解决有 限的内存与不断到来的数据之间的矛盾，并在此基 础上给出了对数据流进行密度估计的D E O D S( D e n s i t yE s t i m a t i o nO v e rD a t aS t r e a m ) 算法，它具有以下特点： 算法是有效和高效的，它是一个单遍扫描的算 法，只需要固定大小的内存，运行时间与数据萤成线 性关系，与传统核密度估计相比，其误差率是可接受的； 算法在任何时间点都可输出对已有数据进行描述的模型； 算法能很方便地扩展并集成到其他数据挖掘应用中去。1 3 5 本文其余部分组织如下：在第2 节中，我们给出 了问题的定义；第3 节提出了一种新的在数据流上进 行密度估计的方法；实验结果及分析在第4 节中给 出；最后总结全文。2 核密度估计简介假设z 。，z 。，是从分布F 中随机独立抽出的 变量，密度估计问题就是根据样本( z 。，z 。，z 。) 兰 刀对F 的密度函数厂( z ) 作出估计九( 刀；z ) 。核密 度估计公式如下： 上( z ) 一轰瓢t K ( 芋) 2 吉浆K 一( z X ，) 其中 0 ，并且K ( t ) = _ 1 K ( h 叫) 。 如图1 所示，1 0 条虚线分别表示1 0 个数据点上的 核函数，实线表示将这些核函数累加后得到的密度 函数估计。图1 传统的核密度估计示意对于中小规模的数据集，核密度估计是一个很 好的方法：它不会在高维数据的情况下产生维数灾难，也无需很多的参数来调整算法效率，并且具有较 好的一致渐进特性。但是当应用于超大规模数据集 时，由于其空间复杂度为0 ( 行) 、时间复杂度为O ( 强2 ) ，核密度估计方法的计算效率将大大降低。而 且，由于计算需要对数据点进行多次扫描，因此无法直接应用在数据流上。本文研究的问题就是，如何高效快速地在数据流上估计出数据的密度分布。5 对数据流的处理这一节我们首先提出两个基本传统核密度估计方法的观察，然后给出一种新的密度估计算法，来有效地估计数据流的密度函数。 5 1 增量密度估计根据第2 节的分析，我们知道传统的核密度估计 方法需要对数据集进行多次扫描，计算出每个数据 点上的核函数，再将它们累加得到最终的密度估计 函数，因此计算必须在静态数据集上进行。如果将核 密度估计方法用在数据流环境下，每当有新数据点到达时，都需要重新扫描整个数据集，计算出新的密度估计函数，计算代价很高。通过观察，我们发现有如下公式成立： ( 舻南蚤剐警)13 6 一南( 蚤蹦宰) + K ( 卒) ) 一南五( z ) + 南K 一( 半) 这一公式说明通过五( z ) 和x 川可求得五十，( z ) 。但是，L ( z ) 只能通过前t 个数据点上的核密度 估计函数来得到。假设把用来合成五( z ) 的所有核函数都放在内存中，那么密度函数就可通过增量计算得到。也就是说，整个数据流只需被扫描一遍。 5 2 核合并下面我们讨论如何解决源源不断的数据与有限内存之间的矛盾。通常，每个数据点用一个核函数表示，每个核函数在汇总成密度函数时的权重都是相同的，如果对九个数据点估计密度函数，则需要计算并保留行个核函数。对于数据流，这种做法显然是不 现实的。我们试图为每个核函数赋予不同的权重( w e i g h t ) ，使它可以代表不同数目的数据点，以减少 所需保存的核函数的个数。权重为P 的核函数代表 了P 个不同的数据点，我们称之为广义核函数( M k e r n e l ) 。同时，我们注意到，两个或多个核函数的和通常可以用一个权重较大的M k e r n e l 来近似逼近，我们称之为核合并，合并过程用以下公式表示：士必( 竺；墨) + 丢K ( 三；墨) 兰善x ( 三；墨) r t in ir lJn jH mH “等式左边的两个核函数分别表示数据点i 和J ：， 右边是合并后的M k e r n e l 。大多数情况下，我们无法找到参数z ，和h 。使等式完全成立，但分析和实验表明，通常等式两边的差异是很小的。所以合并带来的误差是可以接受的。根据上述两个公式，经过以一m 次的核合并，我们可以用m 个M k e r n e l 代表原来的押个核函数。这时密度估计量可以改写为： 力( z ) 一丢蚤筹K ( 等) 其中善户，一图2 核合并后的密度估计图3 显示了核合并的过程，k e r n e l l 和k e r n e l 2 是两个核函数，破折线表示两个核函数的和，虚线是我们要找的用来代替k e r n e l l 和k e r