DSM-FI: an efficient algorithm for mining frequent itemsets in data streams
DSM-FI: an efficient algorithm for mining frequent itemsets in data streams
复制标题
DOI：
10.1007/s10115-007-0112-4
复制
发表时间：
2008-10-01
影响因子：
2.7
通讯作者：
Lee, Suh-Yin
中科院分区：
文献类型：
--
作者：
Li, Hua-Fu;Shan, Man-Kwan;Lee, Suh-Yin
数据流的在线挖掘是数据挖掘的一个重要问题，具有广泛的应用前景。然而，由于流数据具有一些固有的特性，这也是一个难题。在本文中，我们提出了一种新的单通道算法，称为 DSM-FI（频繁项集数据流挖掘），用于在连续的在线交易流上对频繁项集进行在线增量挖掘。根据所提出的算法，流的每个事务被投影为一组子事务，并且这些子事务被插入到一个新的内存中摘要数据结构中，称为SFI森林（摘要频繁项集森林），用于维护迄今为止生成的事务数据流中嵌入的所有频繁项集的集合。最后，从当前的 SFI 森林中确定所有频繁项集的集合。理论分析和实验研究表明，所提出的DSM-FI算法使用稳定的内存，仅对在线事务数据流进行一次传递，并且优于现有的频繁项集一次性挖掘算法。
Online mining of data streams is an important data mining problem with broad applications. However, it is also a difficult problem since the streaming data possess some inherent characteristics. In this paper, we propose a new single-pass algorithm, called DSM-FI (data stream mining for frequent itemsets), for online incremental mining of frequent itemsets over a continuous stream of online transactions. According to the proposed algorithm, each transaction of the stream is projected into a set of sub-transactions, and these sub-transactions are inserted into a new in-memory summary data structure, called SFI-forest (summary frequent itemset forest) for maintaining the set of all frequent itemsets embedded in the transaction data stream generated so far. Finally, the set of all frequent itemsets is determined from the current SFI-forest. Theoretical analysis and experimental studies show that the proposed DSM-FI algorithm uses stable memory, makes only one pass over an online transactional data stream, and outperforms the existing algorithms of one-pass mining of frequent itemsets.