ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇


杨蓓1,2 黄厚宽2   

  1. 1(郑州大学信息工程学院 郑州 450001) 2(北京交通大学计算机与信息技术学院 北京 100044) (
  • 出版日期: 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

摘要: 数据流频繁项集挖掘是目前数据挖掘与知识发现领域的热点研究课题,在许多领域有重要应用.然而支持度阈值的设定需要一定的领域知识,设置不当会给后续的分析处理带来很多困难和不必要的负担,因此挖掘数据流top-K频繁项集有重要意义.提出一个挖掘数据流界标窗口top-K频繁项集的动态增量近似算法TOPSIL-Miner,为此设计了存储流数据摘要信息的概要结构TOPSIL-Tree以及动态记录挖掘相关信息的树层最大支持度表MaxSL、项目序表OIL,TOPSET 和最小支持度表MinSL等,并分析了与这些概要结构相关的挖掘特性.在此基础上研究算法的3种优化措施:1)剪枝当前数据流的平凡项集;2)挖掘过程中启发式自适应提升挖掘阈值;3)动态提升剪枝阈值.对算法的误差上界进行了分析研究.最后通过实验验证了算法的可行性、精确性和时空高效性.

关键词: 数据挖掘, 数据流, 界标窗口, 频繁项集, 概要数据结构

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.

Key words: data mining, data stream, landmark window, frequent itemset, synopsis data structure