標題: EFIM: a fast and memory efficient algorithm for high-utility itemset mining
作者: Zida, Souleymane
Fournier-Viger, Philippe
Lin, Jerry Chun-Wei
Wu, Cheng-Wei
Tseng, Vincent S.
資訊工程學系
Department of Computer Science
關鍵字: Pattern mining;Itemset mining, High-utility mining;Fast Utility Counting, High-utility database merging and projection
公開日期: 1-May-2017
摘要: In recent years, high-utility itemset mining has emerged as an important data mining task. However, it remains computationally expensive both in terms of runtime and memory consumption. It is thus an important challenge to design more efficient algorithms for this task. In this paper, we address this issue by proposing a novel algorithm named EFIM (EFficient high-utility Itemset Mining), which introduces several new ideas to more efficiently discover high-utility itemsets. EFIM relies on two new upper bounds named revised sub-tree utility and local utility to more effectively prune the search space. It also introduces a novel array-based utility counting technique named Fast Utility Counting to calculate these upper bounds in linear time and space. Moreover, to reduce the cost of database scans, EFIM proposes efficient database projection and transaction merging techniques named High-utility Database Projection and High-utility Transaction Merging (HTM), also performed in linear time. An extensive experimental study on various datasets shows that EFIM is in general two to three orders of magnitude faster than the state-of-art algorithms HUP, HUI-Miner, HUP-Miner, FHM and UP-Growth+ on dense datasets and performs quite well on sparse datasets. Moreover, a key advantage of EFIM is its low memory consumption.
URI: http://dx.doi.org/10.1007/s10115-016-0986-0
http://hdl.handle.net/11536/145377
ISSN: 0219-1377
DOI: 10.1007/s10115-016-0986-0
期刊: KNOWLEDGE AND INFORMATION SYSTEMS
Volume: 51
起始頁: 595
結束頁: 625
Appears in Collections:Articles