流式数据上关联规则挖掘研究综述.docVIP

流式数据上关联规则挖掘研究综述 第27卷第9期 2010年9月 计算机应用研究 ApplicationResearchofComputers Vo1.27No.9 Sep.2010 流式数据上关联规则挖掘研究综述 朱小栋,沈国华 (1.上海理工大学管理学院信息管理与电子商务研究所,上海200093;2.南京航空航天大学信息科学与技术 学院,南京210016) 摘要:当前许多工程领域产生大量高速实时的流式数据,基于流式数据的关联规则挖掘应用广泛,与传统的 静态数据相比,流式数据上关联分析面临极大的资源挑战.提出了流式数据上关联规则的形式化定义和基本挖 掘算法,系统地回顾了近年来流式数据上关联规则挖掘的研究进展,详细分析了目前挖掘算法研究中存在的主 要问题和解决途径,阐述了未来的研究方向. 关键词:数据挖掘;数据流;关联规则;频繁项集;频繁模式;知识发现 中图分类号:TP311文献标志码:A文章编号:1001—3695(2010)09—3201—05 doi:10.3969/j.issn.1001—3695.2010.09.001 Reviewofassociationrulesminingindatastreams ZHUXiao.dong. SHENGuo.hua (1.InstituteofInformationManagementamp;ElectronicB~incss,ManagementSchool,UniversityofShanghaiforScienceamp;Technology,Shang- hai200093,China;2.Col妇eofInformationScienceamp;Technology,NangUniversityofAeronauticsamp;Astronautics,Nanjing210016,Chi- ua) Abstract:Vastreal—timehighspeedstreamsdatagenerateuponmanyengineeringfields.Comparedwithtraditionalstaticda— ta,streamsdataanalysisfacesgreatchallengeintermsofresources.Associationrulesminingindatastreamsattractmuchat— tentionduetoitssignificantapplicationinindustries.Thispaprpresentedrelatedformaldefinitionsofassociationrulesandthe basicalgorithmforassociationrulesminingindatastreams.Basedonsystematicinvestigationofassociationrulesminingre— searchesonstreamsdata.analyzedissuesandhowtheywereresolvedincurrentliteratures.Alsodiscussedthefuturedirec— tionsinassociationrulesmining. Keywords:datamining;datastreams;associationrules;frequentitemsets;frequentpatterns;knowledgediscovery 0引言 近年来,数据流在金融,股市,电子商务网络交易,无线传 感器网络以及计算机网络监视等许多领域中的广泛存在,带来 数据流挖掘的研究热潮.不仅因为传统的静态数据挖掘技术 不能适应这种新的数据形式,而且对数据流进行数据挖掘已成 为这些领域的迫切需要.数据流里的数据称为流式数据,是一 个随着时间推移不断出现的项目序列,与传统的静态数据相 比,数据流是连续,潜在无边界的,通常高速地出现.面向数据 流的数据采集与数据挖掘给计算机的存储空间,处理器,能源 供应带来新的挑战. 关联规则分析是数据挖掘的核心课题,起源于20世纪90 年代…,与基于统计回归等数学分析方法不同,关联规则的发 现显得隐蔽而难以发现.基于数据流的关联规则挖掘可应用 到估计传感器网络中丢失的数据,评估互联网数据包的频 繁模式],监视制造业数据流],发现数据流中的异常事件 等.基于Web日志数据流关联规则挖掘可预测失效或产生错 误报告.. 与传统的静态数据不同,数据流有许多新的特征:a)进行 数据流处理的输入数据不是固定在磁盘或者存储器上的,而是 连续的,大量的随机出现的数据流;b)数据流的大小是潜在的 无限大的,相比大量的数据流来说,主存或者磁盘空间的容量 太小,不