下载此文档

在数据流中挖掘频繁.doc


文档分类:IT计算机 | 页数:约7页 举报非法文档有奖
1/7
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/7 下载此文档
文档列表 文档介绍
在数据流中挖掘频繁.DOC在数据流中挖掘最频繁的K个元素李建朱洪复旦大学计算机科学与工程系摘要:本文提出了一种在数据流中挖掘最频繁的K个元素的方法,该方法可以近似的找出数据流中出现最频繁的K个元素,并且估算这K个元素的出现次数。我们的算法应用了推广了的BloomFilter的数据结构来实现对频繁元素出现个数的估算。实验证明,我们的算法用的空间很小,而且给出的估计精度比较高。尤其是对于现实中的Zipf分布的数据,我们的算法需要非常少的空间就可以给出很高的精度。前言最近的十几年,工业界和研究者都意识到了对历史数据的统计和分析,并从中挖掘有用信息的重要性。而历史数据经常可以被看成数据流,其规模非常巨大,按一定的时序产生,我们的可用内存无法保存所有数据,因此算法在读取一些数据进入内存的同时,同时要从内存中丢弃一些数据,并且这些丢弃的数据是不可恢复的。数据流中的一个最基本的问题就是找出数据流中最频繁出现的K个元素,并且给出这K个元素出现的频率。数据流模型的特点就是输入数据的规模非常的庞大,我们无法将整个数据流放入内存,另外我们只能顺序的读取一遍数据[5,12]。因此传统的对每个出现元素统计其频率,再将频率排序找出前K个的方法,在数据流模型中,其空间和时间消耗都是不现实的。因此,在数据流上的信息发现是数据挖掘领域面对的一个巨大挑战。 找出数据流中最频繁的K个元素在现实中有很多应用,如检测点击流,电话呼叫记录,网络数据包记录[2]和检测网络欺诈行为[1]等。相关工作及我们的结果最早的也是最直接的解决数据流中最频繁的K个元素的是简单的取样统计,两个取样统计的变种是由Gibbons和Matias[9]提出的。[10]中提出了基于计数器的stickysampling算法,这个算法将数据流S分成长度不减的若干段,每一段中元素以递减的概率被监测。[11]中提出的Frequent算法可以保证找到出现频率大于的元素。[5]中提出的Countsketch算法解决了如下问题,FindApproxTop,即找出K个元素,这K个元素的出现频率至少是,这里是实际的出现频率第K大的元素的频率。Metwally等在[2]中提出了一种简单的Space-Saving算法,使用了的空间,找到K个元素,且算法记录的出现频率第i大的元素的出现频率在范围内。我们的算法基于推广的BloomFilter的数据结构,使用的空间为,其中B是BloomFilter数组的大小,由我们自己设定,B越大,算法的效果越好。对数据流中的一个数据,我们的更新数据结构的时间为。实验表明,对于大部分分布的数据,的规模的IP地址数据流,我们设B的大小约为的规模,算法记录的出现频率第i大的元素的出现频率在范围,其中。研究表明,很多实际数据可以模型化为zipf分布[13]。对于zipf分布的数据,规模的数据,一般我们只需要B的大小约为5000,就可以保证如上的误差。并且当zipf分布的参数越大,我们需要的空间就越小。我们在第三节介绍本文用的符号,必须的预备知识,如zipfian分布,和原始的BloomFilter算法。在第四节我们介绍我们的挖掘最频繁的K个元素的算法。我们将在第五节讨论我们算法的实现的一些细节,这些细节保证了我们能达到我们想要的时间空间复杂度。我们在第六节列出了我们的实验结果,并以第七节的结论结束全文。预备知识和原始的BloomFilter给定

在数据流中挖掘频繁 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数7
  • 收藏数0 收藏
  • 顶次数0
  • 上传人282975922
  • 文件大小443 KB
  • 时间2019-05-21