ItemListFCI:An Algorithm for Mining Closed Frequent Itemsets Based on Bit Table


Article Preview

Mining closed frequent itemsets in data streams is an important task in stream data mining. Most of the traditional algorithms for mining closed frequent itemsets are Apriori-based which find the frequent itemsets from large amount of candidates, and needs a great deal of time and space. In this paper, an algorithm ItemListFCI for mining closed frequent itemsets in data stream is proposed. The algorithm is based on the sliding window model, and uses a ItemList where the transactions and itemsets are recorded by the column and row vectors respectively. The algorithm first builds the ItemList for the first sliding window. Frequent closed itemsets can be detected by pair-test operations on the binary numbers in the Table. After building the first ItemList, the algorithm updates the ItemList for each sliding window. The frequent closed itemsets in the sliding window can be identified from the ItemList. Algorithms are also proposed to modify ItemList when adding and deleting a transaction. The experimental results on synthetic and real data sets indicate that the proposed algorithm needs less CPU time and memory than other similar methods.



Edited by:

Ran Chen






K. M. Tang et al., "ItemListFCI:An Algorithm for Mining Closed Frequent Itemsets Based on Bit Table", Applied Mechanics and Materials, Vols. 44-47, pp. 3159-3163, 2011

Online since:

December 2010




[1] J.W. Han, J. Pei, Y.W. Yin, R.Y. Mao. Mining frequent patterns without candidate generation: frequent-pattern tree approach, Data Mining and Knowledge Discovery8, 2004,. pp.53-87.

DOI: 10.1023/b:dami.0000005258.31418.83

[2] Zhu Y, Shasha D. StatStream: statistical monitoring of thousands of data streams in real time [A]. Proceedings of the 20th International Conference on Very Large Data Bases[C]. Hong Kong, China: Morgan Kaufmann, 2002, pp.358-369.

[3] H.F. Li, C.C. Ho and S.Y. Lee. Incremental updates of closed frequent itemsets over continuous data streams, Expert Systems with Applications 36, 2009, pp.2451-2458.

DOI: 10.1016/j.eswa.2007.12.054

[4] Chi Y, Wang H, Yu P, and Muntz R. MOMENT: Maintaining closed frequent Itemsets over a stream sliding window [A] . Proceedings of the 2004 IEEE International Conference on Data Mining[C]. Brighton, UK: IEEE Computer Society Press, 2004, pp.59-66.

DOI: 10.1109/icdm.2004.10084

[5] N. Jiang and L. Gruenwald. Research issues in data stream association rule mining, SIGMOD Record 35 (1), 2006, pp.14-19.

DOI: 10.1145/1121995.1121998

[6] Y. Chi, H. Wang, P.S. Yu and R.R. Muntz. Catch the moment: Maintaining closed frequent itemsets over a data stream sliding window, Knowledge and Information Systems 10 (3), 2006, pp.265-294.

DOI: 10.1109/icdm.2004.10084

[7] F.J. Ao, J. Du, Y.J. Yan, B.H. Liu, K.D. Huang. An Efficient Algorithm for Mining Closed Frequent Itemsets in Data Streams, IEEE 8th International Conference on Computer and Information Technology Workshops, 2008, pp.37-42.

DOI: 10.1109/cit.2008.workshops.52

[8] J.Y. Wang, J.W. Han, Ying Lu, Petre Tzvetkov. TFP: An Efficient Algorithm for Mining Top-K Frequent Closed Itemsets, IEEE TRANSACTION ON KNOWLEDGE AND DATA ENGINEERING, 2005, vol. 17, pp.652-664.

DOI: 10.1109/tkde.2005.81

[9] J. Dong, M. Han. BitTableFI: An efficient mining frequent itemsets algorithm. Knowledge -Based Systems 20, 2007, pp.329-335.

DOI: 10.1016/j.knosys.2006.08.005

[10] Dataset available at http: /fimi. cs. helsinki. fi.

In order to see related information, you need to Login.