ISSN 1000-1239 CN 11-1777/TP

• 论文 •

### 挖掘数据流界标窗口Top-K频繁项集

1. 1(郑州大学信息工程学院 郑州 450001) 2(北京交通大学计算机与信息技术学院 北京 100044) (yangbei@zzu.edu.cn)
• 出版日期: 2010-03-15

### Mining Top-K Significant Itemsets in Landmark Windows over Data Streams

Yang Bei1,2 and Huang Houkuan2

1. 1(School of Information Engineering, Zhengzhou University, Zhengzhou 450001) 2(School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044)
• Online: 2010-03-15

Abstract: Frequent itemset mining over data streams becomes a hot topic in data mining and knowledge discovery recently, which has been applied to different areas. However, the setting of a minimum support threshold needs some domain knowledge. It will bring many difficulties or much burden to users if the support threshold is not set reasonably. It is interesting for users to find top-K significant itemsets over data streams. A dynamic incremental approximate algorithm, TOPSIL-Miner, is presented to mine top-K significant itemsets in landmark windows. A new data structure, TOPSIL-Tree, is designed to store the potential significant itemsets, and other data structures of maximum support list, ordered item list, TOPSET and minimum support list are devised to maintain the information about mining results. Moreover, three optimization strategies are exploited to reduce the time and space cost of the algorithm: 1) pruning trivial nodes in the current data stream; 2) promoting mining support threshold during mining process heuristically and adaptively; and 3) promoting pruning threshold dynamically. The accuracy of the algorithm is also analyzed. Extensive experiments are performed to evaluate the good effectiveness, the high efficiency and precision of the algorithm.