（计算机应用技术专业论文）数据流挖掘若干问题的研究.pdf

摘要 曼量曼曼曼曼曼皇蔓曼曼曼曼皇皇曼i i m-o 曼曼曼量曼曼曼曼曼皇曼量曼曼曼曼曼曼曼曼曼曼曼量曼曼曼曼曼曼曼曼曼曼 摘要 随着计算机网络、数据库、多媒体等技术的飞速发展和日益普及，数掘流模型 在传感器网络、金融证券分析、数据挖掘、制造业和天文等领域得到了广泛的应用。 和传统的数据模型相比，数据流模型具有截然不同的特点：数据量无穷：对问题要 求快速响应；数据概念随时间变化。传统的数据挖掘技术主要是针对静态和有限的 数据，很难被应用到数据流这种新的模型中去，这促使越来越多的研究人员深入研 究数据流模型，设计出新的数据处理方案。 本文分析了当前数据流挖掘中的频繁元素挖掘、数据流分类、卸载处理和特征 选择等关键技术，并针对其中的一些问题提出了改进方案和算法。论文的主要工作 和创新点有： 1 提出了h c o u n t + 算法来挖掘数据流上的频繁元素。h c o u n t + 算法采用了一 个辅助的措施来改进h c o u n t 算法，虽然增加了有限的空间丌销，但较大地 提高了h c o u n t 算法的准确率。h c o u n t + 算法仅需要( 1 + a ) 詈i n ( - 盖) 位 1 ) 个计数器，就能够估算每个元素的值，且最大误差不超过s 。在此基础之上，本 文还提出了s l h c o u n t + 算法来挖掘数据流上最近出现的所有频繁元素，而不 仅仅是传统算法所挖掘的t o p k 的频繁元素。理论证明h c o u n t + 算法和 s l h c o u n t + 算法在挖掘频繁元素上具有较好的时间复杂度和空间复杂度，实 验结果证实了这两种算法有较高的查询精度。 2 提出了基于逻辑回归的e l r c l a s s 算法来处理数据流的分类问题。逻辑回归有一 些优良的特点：运行效率高；能在小样本上获得很高的分类准确率；能非线性 处理离散的和连续的数据。e l r c i a s s 算法使用逻辑回归到滑动窗1 2 1 中的数据， 持续监测和更新当前的分类器。如果分类器性能的变坏是由于突发噪声而引起， 则保持原有的分类器。如果检测到概念发生漂移，则构建和使用新的分类器。 实验结果验证了e l r c i a s s 算法的有效性。 3 提出了几个基于支持向量机的算法来处理数据流的多分类问题。本文首先分别 为一对一算法、对多算法和d b 2 算法提出了一个增量式的改进算法o n e 2 0 n e ， 捅要 o n e 2 r e s t 和l d b 2 ，这些算法有对大容量数据进行多分类的能力。在每个增量 步骤仅仅保留支持向量，这些支持向量加到下一个批次数据作为训练样本，构 建若干个二分类器。在测试阶段，l d b 2 算法平均使用l o g ：”个分类器，o n e 2 a l l 算法使用个分类器，o n e 2 0 n e 算法使用n ( n 一1 ) 2 个分类器，所以l d b 2 算 法比o n e 2 a l l 算法和o n e 2 0 n e 算法的测试速度都要快。实验结果显示l d b 2 算 法比o n e 2 0 n e 算法和o n e 2 r e s t 算法的分类交叉准确率都要高。本文还提出了 一个能实时检测局部概念漂移并随之自适应调整的数据流分类算法i n c r e d b 2 。 当局部概念漂移出现时，i n c r e d b 2 算法不是重新构造一个全新的d b 2 层次分类 树，而是仅更新漂移所影响的局部结点，具有较好时间运行效率。实验结果表 明该算法可以有效解决数据流分类中出现的局部概念漂移的问题。 4 提出了r l s 算法来进行数据流管理系统的卸载处理。本文指出查询操作符的选 择率会由于卸载操作的执行而改变，在卸载操作前后可能会有突变。而传统的 卸载算法在确定卸载地点时候，通常假定选择率在卸载前和卸载后保持不变， 这使传统算法得到的卸载地点并不是最合适的。与传统卸载算法不同的是，r l s 算法使用卸载操作后的选择率，而不是卸载操作前的选择率来确定最合适的卸 载地点。实验结果表明r l s 算法具有较好的查询准确率。 5 提出了两个基于o c f s 算法的特征选择算法p o c f s 和p o c f s + 。大部分的特征 选择算法是贪婪算法，不能提供最优解，而最近提出的基于j 下交中心思想的最优 特征选择算法( o c f s 算法) 能依据正交中心函数获得最优解。与o c f s 算法为 所有的类选择相同特征不同的是，p o c f s 算法和p o c f s + 算法为不同的类对选 择不同的特征，从而可以分类算法选择更合适的特征。另外，除了采用能量函 数外，p o c f s + 算法还定义了特征分数的递减比率来加速确定最优特征数量的选 择过程。实验结果表明分类算法中采用p o c f s 算法能获得与采用o c f s 算法相 似的分类准确率，但是有更好的时间开销，而采用p o c f s + 算法能进一步提高 数据流分类的运行效率和分类效果。 关键词：频繁模式，分类，支持向量机，卸载处理，特征选择，数据流挖掘 英文摘要 a b s 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 dw i d e s p r e a du s eo fc o m p u t e rn e t w o r k ，d a t a b a s ea n d m u l t i m e d i at e c h n o l o g y , d a t as t r e a mm o d e lh a sb e e nw i d e l ya p p l i e di nag r o w i n gn u m b e r o fi n f o r m a t i o np r o c e s s i n ga p p l i c a t i o n s ，s u c ha ss e n s o rn e t w o r k ，f i n a n c i a la n a l y s i s ，d a t a m i n i n g ，m a n u f a c t u r i n g ，c h r o n o m e t e re ta 1 c o m p a r e dw i t ht r a d i t i o n a ld a t am o d e l s ，d a t a s t r e a mm o d e lo w n ss e v e r a ld i s t i n g u i s h e dc h a r a c t e r i s t i c s ：t h ev o l u m eo fas t r e a mi s u n b o u n d e d ；ar a p i dr e s p o n s es h o u l db ep r o d u c e di nd a t a s t r e a ms y s t e m s ；t h ed a t a d i s t r i b u t i o no fs t r e a mm a yb ec h a n g e dc o n t i n u a l l y t r a d i t i o n a ld a t am i n i n gt e c h n i q u e s c a l lh a r d l yb ea p p l i e dt op r o c e s sd a t as t r e a m sd i r e c t l y t h i sm a k er e s e a r c h e r st r yh a r dt o w o r ko u tn o v e lq u e r y i n ga n dp r o c e s s i n g t e c h n i q u e so v e rd a t as t r e a m s i nt h i sd i s s e r t a t i o n , s o m ep r i n c i p a lt e c h n i q u e sf o rd a t as t r e a mm i n i n gh a v eb e e n s t u d i e d ：f r e q u e n tc o u n tm i n i n g ，d a t as t r e a mc l a s s i f i c a t i o n ，l o a ds h e d d i n ga n df e a t u r e s e l e c t i o n t h ec o n t r i b u t i o n so ft h i sd i s s e r t a t i o ni n c l u d e ： 1 t h eh c o u n t + a l g o r i t h mi sp r o p o s e dt om i n ef r e q u e n ti t e m so v e rd a t as t r e a m s t h e h c o u n t + a l g o r i t h ma d o p t sa i d e dm e a s u r e st og r e a t l yi m p r o v et h ep r e c i s i o no f t h e h c o u n ta l g o r i t h ma n di tc a l le s t i m a t et h ef r e q u e n c yo fe a c he l e m e n tw i t he r r o rn o m o r et h a n 占w i t h ( 1 + a ) 詈h l ( 一茜) c o u n t e r s i na d d i t i o n ，h c o u n t + i s i n t r o d u c e dt ot i m ec r i t i c a la p p l i c a t i o n sa n dan o v e ls l i d i n gw i n d o w s b a s e da l g o r i t h m s l h c o u n t + i sp r o p o s e dt om i n et h em o s tf r e q u e n ti t e m so c c u r r i n gr e c e n t l y i n s t e a do fo n l yt h o s et o p ki t e m s t h e o r ya n a l y s i sa n de x p e r i m e n t sd e m o n s t r a t e t h a t h c o u n t + a l g o r i t h ma n ds l - h c o u n t + a l g o r i t h m h a v eal o wt i m e c o m p l e x i t ya n ds p a c ec o m p l e x i t y b o t ha l g o r i t h m sa r ev e r i f i e dt oh a v eh i g hq u e r y p r e c i s i o ni ne x p e r i m e n t a lr e s u l t s 2 t h ee v o l u t i o n a r yl o g i s t i c a lr e g r e s s i o nc l a s s i f i e ra l g o r i t h m ( e l r c i a s s ) i sp r o p o s e d t os o l v et h ec l a s s i f i c a t i o np r o b l e m so fe v o l v i n gd a t as t r e a m s l o g i s t i cr e g r e s s i o ni s af a s tc l a s s i f i e ra n dc a na c h i e v eh i g h e ra c c u r a c yo ns m a l lt r a i n i n gd a t a m o r e o v e r , i t c a nw o r ko nb o t hd i s c r e t ea n dc o n t i n u o u sa t t r i b u t e sw i t hn o n l i n e a rp a t t e r n s t h e i i i 英文摘要 e l r c l a s sa l g o r i t h ma p p l i e sl o g i s t i cr e g r e s s i o nc o n t i n u a l l yt oas l i d i n gw i n d o wo f s a m p l e s i no r d e rt o u p d a t et h ee x i s t i n gc l a s s i f i e r , k e e p t h i sc l a s s i f i e ri fi t s p e r f o r m a n c ei sd e t e r i o r a t e db yt h eb u r s t i n gn o i s eo rc o n s t r u c tan e wc l a s s i f i e ri fa m a j o rc o n c e p td r i f ti sd e t e c t e d i n t e n s i v ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h e e f f e c t i v e n e s so ft h i sa l g o r i t h m 3 s e v e r a la l g o r i t h m sb a s e do ns u p p o r tv e c t o rm a c h i n ea r ep r o p o s e df o rm u l t i c l a s s c l a s s i f i c a t i o no fd a t as t r e a m s t h i sp a p e rf i r s t l yp r o p o s eo n ei n c r e m e n t a lv e r s i o nf o r e a c ho ft h eo n e - a g a i n s t o n e ，o n e - a g a i n s t - r e s ta n dd b 2 a l g o r i t h m s ，c a l l e do n e 2 0 n e ， o n e 2 a l la n dl d b 2r e s p e c t i v e l y , w h i c ha l ee n a b l e dt h e a b i l i t y o fm u l t i 1 a b e l c l a s s i f i c a t i o nf o rl a r g ed a t a s e t s t h e yw o u l dp r e s e r v eo n l yt h es u p p o r tv e c t o r sa te a c h i n c r e m e n t a ls t e p ，a d dt h e mt ot h et r a i n i n gd a t af o rt h en e x ts t e p ，a n dc o n s t r u c ts e v e r a l b i n a r yc l a s s i f i e r sa f t e rt h ep r o c e s s i n go ft h el a s tb a t c hd a t a i nt h et e s t i n gp h a s e ，t h e a v e r a g en u m b e ro fc l a s s i t i e r su s e db yl d b 2i sl o g ，w h i c hi sl e s st h a nnu s e db y o n e 2 a l la n dm u c hl e s st h a n n ( n - 1 ) 2u s e db yo n e 2 0 n e h e n c e ，l d b 2i sf a s t e r t h a no n e 2 a l la n do n e 2 0 n ei nt e r m so ft e s t i n gt i m e e x p e r i m e n t a lr e s u l t ss h o wt h a t l d b 2h a sh i g h e rc r o s s v a l i d a t i o na c c u r a c yt h a no n e 2 0 n ea n do n e 2 r e s t t h e na n a d a p t i v em e t h o dc a l l e di n c r e d b 2 ，b a s e do nt h ed b 2m e t h o d ，i sp r o p o s e dt od e t e c t a n da d a p tt ol o c a lc o n c e p td r i f tc o n t i n u o u s l yi nd a t as t r e a mc l a s s i f i c a t i o n t h i s m e t h o dd y n a m i c a l l ym a i n t a i n sah i e r a r c h i c a lc l a s s i f i c a t i o nt r e e w h e nl o c a lc o n c e p t d r i f ti sd e t e c t e d ，i n c r e d b 2o n l yu p d a t e st h en o d e st h a ta f f e c t e db yt h i sd r i f tr a t h e r t h a nr e b u i l d san e wc l a s s i f i c a t i o nt r e ef r o ms c r a t c h ，w h i c hm e a n st h a ti th a sb e t t e r t i m ee f f i c i e n c y e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h ev a l i d i t ya n de f f i c i e n c yo ft h i s m e t h o d 4 t h er a t e - s e n s i t i v el o a ds h e d d i n ga l g o r i t h m ( r l s ) i sp r o p o s e dt od e t e r m i n et h e o p t i m u md r o pl o c a t i o n t r a d i t i o n a ll o a ds h e d d i n ga l g o r i t h m sf o rd a t as t r e a ms y s t e m s c a l c u l a t ec u r r e n to p e r a t o rs e l e c t i v i t yo v e rs e v e r a lr u np e r i o d sa n du s et h e mt o d e t e r m i n ew h e r et os h e dl o a dd u r i n gt h en e x tr u n p e r i o d t h i sp a p e rf i r s t l yp o i n to u t t h a tt h ec u r r e n ts e l e c t i v i t ym a yc h a n g ed u et ot h ei m p l e m e n t a t i o no fl o a ds h e d d i n g 英文摘要 t h e n ，t h er l sa l g o r i t h mi si n t r o d u c e dt od e t e r m i n et h eo p t i m u md r o pl o c a t i o nb y t h e s ec h a n g e ds e l e c t i v i t yr a t h e rt h a nt h o s ep r e c a l c u l a t e dv a l u e s s i m u l a t i o nr e s u l t s d e m o n s t r a t et h a tr l sa c h i e v e sh i g h e ra c c u r a c yt h a nt r a d i t i o n a la l g o r i t h m s 5 t w of e a t u r es e l e c t i o nm e t h o d sc a l l e dp r o j e c t e do c f s ( p o c f s ) a n dp r o j e c t e d o c f s + ( p o c f s + ) a r ep r o p o s e df o rd a t a s t r e a mc l a s s i f i c a t i o n t h eo r t h o g o n a l c e n t r o i df e a t u r es e l e c t i o n ( o c f s ) m e t h o dc a ne n s u r eo p t i m a ls o l u t i o n sa c c o r d i n g t ot h eo r t h o g o n a lc e n t r o i dc r i t e r i o n ( o c ) b o t hp o c f sa n dp o c f s + e x t e n do c f s t os e l e c td i f f e r e n tf e a t u r e sf o re a c hc l a s sp a i ri n d i v i d u a l l yi n s t e a do fs e l e c t i n gt h e s a m ef e a t u r e s f o ra l lt h ec l a s s e ss i m u l t a n e o u s l y t h e yc a ns e l e c tm o r es u i t a b l e f e a t u r e sf o rc l a s s i f i e rc o n s t r u c t i o nt h a no c f s i na d d i t i o n ，p o c f s + i n t r o d u c e s d e c r e m e n tr a t i o so ff e a t u r es c o r e st oa c c e l e r a t et h es p e e do fd e t e r m i n i n gt h en u m b e r o ff e a t u r e st ob es e l e c t e d a sar e s u l t ，p o c f s + s e l e c t sf e a t u r e sf a s t e rt h a no c f sa n d p o c f s e x p e r i m e n t a lr e s u l t s i n d i c a t et h a tp o c f sa n dp o c f s + s i g n i f i c a n t l y i m p r o v et h ec l a s s i f i c a t i o ne f f i c i e n c ya n dp o c f s + o u t p e r f o r m so c f si nt e r m so f e f f e c t i v e n e s sa n de f f i c i e n c y k e y w o r d s ：f r e q u e n tc o u n tm i n i n g ，c l a s s i f i c a t i o n ，s u p p o r tv e c t o rm a c h i n e ，l o a d s h e d d i n g ，f e a t u r es e l e c t i o n ，d a t as t r e a mm i n i n g v 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名：尹志武 日期：2 0 0 7 年1 月1 0 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 不保密。 ( 请在以上方框内打“4 ) 学位论文作者签名：尹志武指导教师签名：黄上腾 日期：2 0 0 7 年1 月10 日日期：2 0 0 7 年1 月1 0 日 第一章绪论 随着计算机、网络和通信技术的迅猛发展，许多应用领域出现了海量、高速和动 态的数据，如商业交易分析、传感器网络瞳1 、入侵检测口1 、金融信息监控n 3 和工业 过程控制畸3 等。区别于传统数据库中相对静态的数据，这类全新的大量连续到达的、 潜在无限的数据有序序列称之为数据流。 数据挖掘、联机分析处理、内存数据库、实时数据库、主动查询处理技术和数 据库近似查询等技术是数据库领域中当前最为活跃的研究方向。这些技术大都依然 以传统数据库，7 1 为研究基点，适用于持久稳固的数据存储。在数据库管理系统中， 插入、更新、删除等操作没有查询发生频繁，查询结果反映了当前的数据库状态。 但是这样的存储方式以及对基于时间的数据非常有限的管理能力无法满足数据流 应用的需求。数据流系统中的数据有量大、快速和时变的特点，所以不能仅仅采用 传统方式来处理它们。简单地将数据放到传统的数据库中并对其进行操作是不切实 际的，因为大量的数据会造成数据库无法正常使用，而且大部分数据可能很快就会 被删除，不需要永久保存，数据更新和查询的效率也非常低，因此如何对数据流进 行有效的管理与挖掘是当前亟待解决的问题。 1 1 数据流的特点 通常只有在数据中的大部分会被反复查询且只存在不频繁更新的情况下，传统 的存储型数据集才是合适的。然而数据流系统中，数据随时问不断变化而且大部分 数据无法进行多次操作，这使得引入新的数据处理模型显得非常重要。 数据流有以下一些主要特点： 1 数据连续不断到达。数据的总量是无限的，存储所有数据的代价极大。 2 数据到达速率很快。数据的速度处理要求有时会超出系统的负载能力。 3 数据到达顺序不受应用系统控制。系统无法控制数据载入和被处理的顺序。 4 数据单遍处理。数据一经处理，除非特意保存，否则不能被再次取出处理。 卜海交通大学博十学位论文 由于内存的限制，数据处理后，一般只是采用概要数据结构保留其有用的 信息。 5 数据动态变化。数据的到达速率和数据分布时刻会发生改变。 1 2 数据流研究的挑战 数据流模型和传统数据模型相比具有截然不同的特性，这对数据流处理技术提 出了新的挑战。 1 低的时间复杂度( 1 0 wt i m ec o m p l e x i t y ) 。数据流应用系统中，一般都要求实时响 应用户要求，连续输出查询结果。数据流的速度很快，这要求数据流算法对于 数据流上到达的任一元组能很快地完成处理。否则，数据不断到达，延时不断 积累，最终导致服务质量显著降低。 2 低的空间复杂度( 1 0 ws p a c ec o m p l e x i t y ) 。数据流的长度是无界的，由于存储空 间的限制，不可能将所有的数据存储下来。为保证算法持续稳定运行，数据流 算法的空间复杂度要非常小。假设当前时刻数据流的长度为，数据流的空间 复杂度一般要求在o ( 1 0 9 n ) 之内，这种情况下数据流算法空间占有量的增长速 度就远远小于数据流自身规模增长的速度。 3 近似的结果( a p p r o x i m a t ea c c u r a c y ) 。数据流的数据规模大且速率快，在存储有 限时，对于一些复杂问题不能一次遍历就能得到准确答案。虽然数据流算法只 能返回近似查询结果，但是大部分算法都需要将其误差限制在一个预定义的小 范围之内，高质量的近似回答在很多场所是可以接受的。这些能够在理论上保 证误差范围的数据流算法可以分为确定性算法和非确定性算法两种。确定性算 法所得到的查询结果在任何情况下都是可信的；非确定性算法只能保证结论j 下 确的概率很高，给定足够的空间，其概率值可以接近于1 。 4 自适应的调整( a d a p t i v i t y ) 。数据流算法应该能够及时监测到数据流的动态变化， 并可以根据变化来进行自适应的调整。当数据流的流速超过系统处理能力的时 候，需要进行负载平衡以及查询操作调度方法进行处理。如果这两种方法仍然 2 第一帝绪论 不能降低系统负载，则必须采用卸载技术来卸掉过多的负载。当数据流的数据 分布发生改变的时候，必须重新更新当前的数据模式或者生成新的数据模式。 1 3 数据流研究的背景 目前数据流已经应用在很多领域：如金融管理、网络日志、商品销售分析、交 通、每同天气变化、安全防御、电信数据管理、传感器网络、情报分析、股票交易、 电子商务、卫星遥感和科学研究等。本节通过详细介绍一些典型的数据流应用实例 来说明数据流研究的重要性。 股票报价数据是一种动态时变数据，可以看作是数据流的一种。股票价格在线 分析涉及到发现相关性，识别趋势，套汇时机和未来价格预测等。股票相关性分 析能够定量说明股票与股票、股票与指数之间的相关性，以此得到相似的股票板块， 创建投资组合，还能够发现时间错位情况下各个项目之问的相关性。典型的查询如 下：最近成交量震荡的最高变更率；所有价格在$ 1 0 0 一$ 1 0 0 0 的股票：哪些股票最近 5 分钟内平均成交量以1 0 0 的幅度震荡。 传感器网络乜j 0 5 1 已经成为国内外公认的研究热点，被广泛地应用在空间探索、 国防、智能家居、大型车间管理和安全监测等领域。传感器网络是由部署在监测区 域内大量的微型传感器节点形成的一个多跳自组织系统。这些节点协作地感知、采 集和处理感知对象的信息，并发送给观察者。传感器网络所采集的数据持续到达， 速度快而且规模大。用户可以观察这些信息并依此来进行相应的处理。传感器网络 面临的主要挑战是：电源能量有限、通信能力有限、计算和存储能力有限。 事务同志阳1 是用来记录事务发生的频度。很多情况下，会在很短的时间内产生 大量的事务，例如：w e b 访问记录、信用卡交易记录、电话记录等。如何根据用户 的访问日志对用户进行区分是w e b 使用记录挖掘的一个关键问题。由用户与网站交 互行为而产生的点击流通常会遵循各自的模式。通过对点击流的聚类可以达到对用 户聚类，从而网站可以为用户提供个性化服务。对事务日志的分析涉及到数据流模 型下的关联规则、分类和聚类等算法的研究。 t - 海交通大学博十学伊论文 在网络数据包高速到达的情况下，实时对网络数据流进行监测阳川是极具挑战性 的工作，同时在对网络流量统计、监控，查询管理及异常和入侵检测等方面都具有 重大的意义。传统的入侵检测系统安装在主机或者低端路由器上，只能够检测应用 层或系统层的同志和捕获到的局部网络报文。但是当今影响网络性能的事件多具有 突发性，例如分布式拒绝攻击和各种蠕虫的爆发等。网络病毒和蠕虫的快速散播几 乎可以在1 0 分钟之内感染因特网范围内的所有脆弱机器，如何在它们爆发的初期 及早发现对于进一步的阻止和保护工作显得至关重要。 1 4 主要贡献 数据流挖掘算法是当前数据库界的研究热点。本文分析了当前数据流挖掘中的 频繁元素挖掘、数据流分类、卸载处理和特征选择等关键技术，并针对其中的一些 问题提出了改进方案和算法。本文有以下的主要贡献： 1 提出了h c o u n t + 算法来挖掘数据流上的频繁元素。h c o u n t + 算法采用一个 辅助的措施来改进h c o u n t 算法，虽然此措施增加了一定的空间开销，但大 大提高了h c o u n t 算法的准确率。h c o u n t + 算法仅需要 ( 1 + a ) 詈l n ( - 羔) ，) 。该方法可以大大地节约空间开销。 第：章数据流研究进展 曼量曼曼曼皇鼍i l 一 - n i 曼曼曼曼皇曼曼曼曼曼曼曼曼曼舅曼曼曼! ! 曼 在计数抽样方法啪1 中，当样本集合溢出时，首先将概率参数丁提高到乃。对于其中 的任意个元素，首先以概率r t ，之后以概率l 正，判断是否减去l 。一旦该计数