在线挖掘数据流滑动窗口中最大频繁项集  

Online Mining Maximal Frequent Itemsets in Sliding Window over Data Streams

作　　者：敖富江[1] 颜跃进[2] 刘宝宏[1] 黄柯棣[1] 

机构地区：[1]国防科技大学机电工程与自动化学院,长沙410073 [2]国防科技大学计算机学院,长沙410073

出　　处：《系统仿真学报》2009年第4期1134-1139,共6页Journal of System Simulation

基　　金：国家自然科学基金资助项目(60573057;60704038)

摘　　要：相对于频繁项集,最大频繁项集的数目较少,挖掘最大频繁项集的算法具有较高的时空效率。提出了一种新的基于文法顺序FP-Tree的最大频繁项集单遍挖掘算法FPMFI-DS。该算法采用了一种混合搜索空间项顺序策略,并利用我们所提出的一种新的剪枝技术—"子集等价剪枝技术",有效缩小搜索空间的大小。基于该算法,提出了一种能够在线更新挖掘数据流滑动窗口中最大频繁项集的算法FPMFI-DS+。FPMFI-DS+算法能够在任意时刻都维护数据流当前窗口中的最大频繁项集。仿真实验表明,FPMFI-DS算法的效率接近于多遍挖掘算法FPMax*,并具有良好的可扩展性,FPMFI-DS+算法更新挖掘速度快。For the number of maximal frequent itemsets （MFIs） is less than that of frequent itemsets, the efficiency of algorithm for mining MFIs is higher. A novel single-pass lexicographical-order FP-Tree based algorithm, FPMF1-DS was proposed. FPMFI-DS uses a kind of mixed item. ordering policy and imports a new pruning technique, subset equivalence pruning technique. These two techniques effectively decrease the size of searching space. Based on FPMFI-DS, another algorithm, FPMFI-DS＋ was proposed, which＇could mine MFls in sliding window over data streams in an online updating fashion. FPMFI-DS＋ can maintain MFIs in current sliding window over data streams at any time. The experiments show that FPMFI-DS is comparable with multi-pass algorithm FPMax^＊ regarding with the efficiency, and has good scalability, and FPMFI-DS＋ has high updating-miningspeed.

关 键 词：数据流 最大频繁项集 在线挖掘 滑动窗口 文法顺序FP-Tree 

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