一种有效的数据流最大频繁模式挖掘算法  

An efficient algorithm for mining maximal frequent itemsets over data streams

作　　者：毛伊敏[1,2] 杨路明[1] 李宏[1] 陈志刚[1] 刘立新[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083 [2]江西理工大学应用科学学院,赣州341000

出　　处：《高技术通讯》2010年第3期246-252,共7页Chinese High Technology Letters

基　　金：国家自然科学基金(60573127)资助项目

摘　　要：针对频繁项集挖掘存在数据和模式冗余的问题,对数据流最大频繁项集挖掘算法进行了研究。针对目前典型的数据流最大频繁模式挖掘算法DSM-MFI存在消耗大量存储空间及执行效率低等问题,提出了一种挖掘数据流界标窗口内最大频繁项集的算法MMFI-DS,该算法首先采用SEFI-tree存储包含在不断增长的数据流中相关最大频繁项集的重要信息,同时删除SEFI-tree中大量不频繁项目,然后使用自顶向下和自底向上双向搜索策略挖掘界标窗口中一系列的最大频繁项集。理论分析与实验表明,该算法比DSM-MFI算法具有更高的效率,并能节省存储空间。The paper focuses attention on the study of mining of maximal frequent itemsets from data streams to solve the problem of data and pattern redundance in frequent itemset mining, and in consideration of the problem of bad performance in operating time and memory space of the DSM-MFI, a typical algorithm for mining maximal frequent itemsets over data streams, presents an algorithm, called MMFI-DS. Firstly, the algorithm uses a new compressed tree, called the surmnary extended frequent item tree （SEFI-tree）, to maintain the essential information about maximal frequent itemsets embedded in the stream so far, at the same time, a lot of infrequent items are deleted by pruning the tree. Then, it employs a top- bottom and bottom-top method to mine the set of all maximal frequent itemsets in landmark windows over the data stream. The theoretical analysis and experimental results show that the algorithm performs much better than the previous approaches.

关 键 词：数据挖掘 数据流 界标窗口 频繁项集 最大频繁项集 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]