资源描述:
《基于滑动窗口的进化数据流聚类》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.18,No.4,April2007,pp.905−918http://www.jos.org.cnDOI:10.1360/jos180905Tel/Fax:+86-10-62562563©2007byJournalofSoftware.Allrightsreserved.∗基于滑动窗口的进化数据流聚类+常建龙,曹锋,周傲英(复旦大学计算机科学与工程系,上海200433)ClusteringEvolvingDataStreams
2、overSlidingWindows+CHANGJian-Long,CAOFeng,ZHOUAo-Ying(DepartmentofComputerScienceandEngineering,FudanUniversity,Shanghai200433,China)+Correspondingauthor:Phn:+86-21-65643503,E-mail:ayzhou@fudan.edu.cn,http://www.fudan.edu.cnChangJL,CaoF,ZhouAY.Clusteringevolvingdatastreamsoversliding
3、windows.JournalofSoftware,2007,18(4):905−918.http://www.jos.org.cn/1000-9825/18/905.htmAbstract:Toaddresstheslidingwindowbasedclustering,twotypesofexponentialhistogramofclusterfeatures,falsepositiveandfalsenegative,areintroducedinthispaper.Withthesestructures,aclusteringalgorithmbase
4、donslidingwindowsisproposed.Thealgorithmcanpreciselyobtainthedistributionofrecentrecordswithlimitedmemory,thusitcanproducetheclusteringresultoverslidingwindows.Furthermore,itcanbeextendedtodealwiththeclusteringproblemoverN-nwindow(anextendedmodeloftheslidingwindow).Theevolvingdatastr
5、eamsintheexperimentsincludeKDD-CUP’99andKDD-CUP’98realdatasetsandsyntheticdatasetswithchangingGaussiandistribution.Theoreticalanalysisandcomprehensiveexperimentalresultsdemonstratethattheproposedmethodisofhighquality,littlememoryandfastprocessingrate.Keywords:evolvingdatastream;clust
6、ering;slidingwindow摘要:提出了纳伪(falsepositive)和拒真(falsenegative)两种聚类特征指数直方图分别来支持纳伪误差和拒真误差窗口的聚类分析;然后,提出一种基于滑动窗口的数据流聚类方法.该方法在占用窗口大小的次线性内存空间前提下,及时保存最近数据记录的分布状况,从而实现对滑动窗口内的数据进行聚类.此外,它还可被扩展用于N-n窗口(滑动窗口的扩展模型)的数据聚类.实验采用KDD-CUP’99和KDD-CUP’98真实数据集以及变换高斯分布的人工数据集构造进化数据流.理论分析和实验结果表明,该方法具有良好的聚类质量、较小的
7、内存开销和快速的数据处理能力.关键词:进化数据流;聚类;滑动窗口中图法分类号:TP311文献标识码:A现代计算机网络和传感器网络技术的快速发展引起了一类具有广阔发展前景的数据流应用,从金融股票交易、天气和环境监测到计算机网络监控.在该类应用中,海量流式数据以实时方式快速到达,对在线数据分析和挖掘提出了新的挑战.作为一种基础且重要的数据挖掘手段——聚类分析也越来越多地在数据流环境下被重新考虑.与传统数据聚类不同,在数据流环境下,各个簇(数据流的分布特征)往往随时间而不断进化(evolving).∗SupportedbytheNationalNaturalScien
8、ceFoundation