Affiliations: [a] School of Computer Science and Technology, Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian, Liaoning, China | [b] School of Innovation and Experiment, Dalian University of Technology, Dalian, Liaoning, China
Correspondence:
[*]
Corresponding author: Bo Jin, School of Innovation and Experiment, Dalian University of Technology, Dalian 116024, Liaoning, China. Tel.: +86 133 5225 3961; Fax: +86 411 8470 7111; E-mail: lelewater@gmail.com.
Abstract: High utility itemsets mining is a hot topic in data stream mining. It is essential that the mining algorithm should be efficient in both time and space for data stream is continuous and unbounded. To the best of our knowledge, the existing algorithms require multiple database scans to mine high utility itemsets, and this hinders their efficiency. In this paper, we propose a new data structure, called UT-Tree (Utility on Tail Tree), for maintaining utility information of transaction itemsets to avoid multiple database scans. The UT-Tree is created with one database scan, and contains a fixed number of transaction itemsets; utility information is stored on tail-nodes only. Based on the proposed data structure and the sliding window approach, we propose a mining algorithm, called HUM-UT (High Utility itemsets Mining based on UT-Tree), to find high utility itemsets from transactional data streams. The HUM-UT algorithm mines high utility itemsets from the UT-Tree without additional database scan. Experiment results show that our algorithm has better performance and is more stable under different experimental conditions than the state-of-the-art algorithm HUPMS in terms of time and space.
Keywords: Data mining, data streams, frequent itemsets, high utility itemsets
