在线挖掘数据流闭合频繁项集及应用探究.docVIP

在线挖掘数据流闭合频繁项集 CMNL-SW算法的研究 汤春明1，王培义1，曲英涛2 （1．哈尔滨工程大学信息与通信工程学院，哈尔滨 150001； 2．哈尔滨工程大学网络信息中心，哈尔滨，150001） 摘 要：数据流快速无限的特点及其应用领域的不断扩增，使数据流的挖掘技术越来越具有挑战性。本文提出了一种新的CMNL-SW(Closed Map and Num List-Sliding Window)挖掘算法。具体使用数据结构Closed Map存储挖掘到的闭合项集和Num List存储所有不同项的序号，通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口，使之能够根据用户任意指定的支持度阈值在线输出数据流上闭合频繁项集信息。通过理论分析和对真实数据集Mushroom、Retail-chain和人工合成数据集T40I10D100K的挖掘结果表明，提出的算法在时空效率上明显优于同类经典算法Moment和CFI-Stream，并且随着数据流上处理事务数的递增和快速改变有很好的稳定性。 关键词：CMNL-SW挖掘算法；闭合频繁项集；滑动窗口；数据流 CMNL-SW Algorithm Study on Online Mining Closed Frequent Itemsets over Data Stream TANG Chunming1，WANG Peiyi1，QU Yingtao2 (1. College of Information and Communication Engineering, Harbin Engineering University, Harbin, 150001; 2. Center of Network Message, Harbin Engineering University, Harbin, 150001) Abstract: The speedy and unbounded characteristic of data stream, whose application domain is unceasing increasing, enables mining technology to have a higher challenging more and more. In this paper, we propose a new online mining algorithm called CMNL-SW (Closed Map and Num List-Sliding Window) which uses two data structures, Closed Map stores closed itemsets mined and Num List stores the number of all different items. Via the simple union of item number contained within a new arriving or an old deleting transaction and intersection with certain previous closed itemsets once, it incrementally updates the current sliding window that makes the closed frequent itemsets can be output in real time based on any user’s specified thresholds. Theoretical analysis and the experimental results of the real datasets Mushroom、Retail-chain and artificially synthesized datasets T40I10D100K show that the proposed method is superior to that of state-of-the-art algorithm Moment and CFI-Stream in terms of time and space efficiency, and has good scalability as the number of transactions processed increases and adapts very rapidly to the change in data streams. Keywords: CMNL-SW