数据流中基于滑动窗口的最大频繁项集挖掘算法  

Mining maximal frequent itemsets over data streams using sliding window

作　　者：杨路明[1] 刘立新[1] 毛伊敏[1] 谢东[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机应用研究》2010年第2期519-522,共4页Application Research of Computers

基　　金：湖南省教育厅科研资助项目(08B040)

摘　　要：挖掘数据流中最大频繁项集是从数据流中获得信息的一种有效手段,是数据流挖掘研究的热点之一。结合数据流的特点,提出了一种新的基于滑动窗口的最大频繁项集挖掘算法。该算法用位图来存储数据流中流动的数据;采用直接覆盖的方法存储和更新数据流上的数据;在深度优先搜索挖掘最大频繁项集时,除采用经典的剪枝策略外,还提出了与父等价原理相对应的子等价剪枝策略;最后将挖掘结果存储在索引链表中以提高超集检测效率,进一步减少挖掘最大频繁项集的时间。理论分析和实验结果证实了该算法在时间和空间上的有效性。Mining maximal frequent itemsets over streaming data is one of the most important issues in mining data stream. This paper proposed an efficient algorithm to mine maximal frequent itemsets in sliding window. First, used bitmap to deal with the streaming data. Second, adopted depth first to find maximal frequent itemsets when mining. Moreover, besides typical pruning strategies, this paper developed a new pruning strategy corresponding to the parent equivalency pruning to prune. Third, used index structure to store the maximal frequent itemsets, which could speed up the speed of superset test. Theoretical analysis and experimental results show that the proposed method is efficient.

关 键 词：数据流 数据挖掘 最大频繁项集 滑动窗口 位图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]