数据流中频繁闭项集的近似挖掘算法

An Algorithm to Approximately Mine Frequent Closed Itemsets from Data Streams

在数据流中挖掘频繁项集得到了广泛的研究,传统的研究方法大多关注于在数据流中挖掘全部频繁项集.由于挖掘全部频繁项集存在数据和模式冗余问题,所以对算法的时间和空间效率都具有更大的挑战性.因此,近年来人们开始关注在数据流中挖掘频繁闭项集,其中一个典型的工作就是Moment算法.本文提出了一种数据流中频繁闭项集的近似挖掘算法A-Moment.它采用衰减窗口机制、近似计数估计方法和分布式更新信息策略来解决Moment算法中过度依赖于窗口和执行效率低等问题.实验表明,该算法在保证挖掘精度的前提下,可以比Moment获得更好的效率.

Mining frequent itemsets from data streams has extensively been studied, and most of them focus on finding complete set of frequent itemsets in a data stream. Because of numerous redundant data and patterns in main memory, they cannot get very good performance in time and space. Therefore,mining frequent closed itemsets in data streams becomes a new important problem in recent years, where algorithm Moment was regarded as a typical method of them. This paper presents an algorithm, called AMoment, which uses the damped window technique, approximate count method and distributed updating strategy to get higher mining efficiency. Experimental results show that our algorithm performs much better than the previous approaches.