资源描述：
《流数据挖掘综述new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机科学2007Vol134l11*)流数据挖掘综述孙玉芬卢炎生(华中科技大学计算机科学与技术学院武汉430074)摘要作为一种新的数据形态,流数据对数据挖掘提出了诸多挑战。学者们已提出大量处理流数据的挖掘算法。本文对这些算法进行了综述。首先介绍了多个不同的数据流模型,这些模型对算法设计有着不同的要求。然后,总结了流数据挖掘算法的特点,并给出了算法中常用的技术。最后,分析了各个流数据挖掘任务中的代表性算法。关键词数据流,数据挖掘,时空复杂度,滑动窗口AnOverviewofStreamDataMiningSUNYu-Fe
2、nLUYan-Sheng(ComputerDepartmentofHuazhongUniversityofScienceandTechnology,Wuhan430074)AbstractDatastreamsposegreatchallengestodatamining.Manystreamdataminingalgorithmshavebeenproposed.Inthispaper,wegiveanoverviewofthesealgorithms.Firstly,thedatastreammodelsareintr
3、oduced.Thenthechar-actersofstreamdataminingalgorithmsaresummarizedandseveraltechniquesthatareusedinthesealgorithmsarein-troduced.Atlast,therepresentativealgorithmsofeveryminingtaskareanalyzed.KeywordsDatastream,Datamining,Time-spacecomplexity,Slidingwindow1引言2数据流模
4、型通信领域中的电话记录数据流、Web上的用户点击数据数据流是一个以一定速度连续到达的数据项序列x1,流、网络监测中的数据包流、各类传感器网络中的检测数据,,xi,,,xn,,,这个数据项序列只能按下标i的递增顺序[1]流、金融领域的证券数据流、卫星传回的图像数据流以及零售读取一次。数据流是现象驱动的,其速度与数据项到达的业务中的交易数据流等形成了一种与传统数据库中静态数据次序无法被控制。数据流通常具有潜在无限的体积,且数据可能的取值是无限的,处理数据流的系统无法保存整个数据不同的数据形态。这些数据流产生的数据量在多个应用领
5、域流。而数据流的在线处理要求又使系统无法进行代价昂贵的中快速增长,小型无线传感设备的广泛使用将进一步使数据磁盘存取。因此,数据流中的数据项在被读取一次之后,就被流体积的增长速度提高几个数量级。而且,产生数据流的应丢弃,以后不可能再读到。在实际应用中,某些超大型的静态用通常要求在线实时处理。如何及时有效地处理数据流,从数据集要求处理算法只能进行一次线性扫描以降低算法的处中挖掘出有用的知识,将对多个应用领域产生重大意义。[1,7]理代价。此时,算法的输入也可看作是一种数据流。Henzinger等人于1998年在论文/Compu
6、tingonData目前,在数据流研究领域中存在多种数据流模型。不同[1]Stream0中首次将数据流作为一种数据处理模型提出来。的数据流模型具有不同的适用范围,需要设计不同的处理算从2000年开始,数据流作为一个热点研究方向出现在数据挖法。可以分别按照数据流中数据描述现象的方式和算法处理掘与数据库领域的几大顶级会议中,如VLDB、SIGMOD、数据流时所采用的时序范围对这些模型进行划分。SIGKDD、ICDE、ICDM等会议每年都有多篇有关数据流处理设数据流中的数据项x1,,,xi,,,xn依次按下标顺序的文章。目前,数
7、据流研究大致可分为两个方面:数据流管理到达,它们描述了一个信号A。按xi描述信号A的方式,数系统(DataStreamManagementSystems,DSMS)和流数据挖据流模型可分为以下几类[8]:[2]掘。其中,建立数据流管理系统方面的研究主要集中在数(1)时序(TimeSeries)模型:A[i]=xi。此时,数据流中据流查询。已有多个研究机构进行了DSMS的研究,并构建的每个数据项都代表一个独立的信号。[3][4][5]出一些系统,如STREAM,TelegraphCQ,Aurora等。(2)现金登记(Cash
8、Register)模型:令xi=(j,Ii),且Ii流数据挖掘方面的研究主要包括多数据流挖掘和单数据流挖0,则Ai[j]=Ai-1[j]+Ii。此时,数据流中的多个数据项增掘。目前学者们已提出了大量流数据挖掘算法,并开发出流量式地表达一个A[j]。数据挖掘系统。如UIUC的MAIDS(MiningAl
