Direct Discovery of High Utility Itemsets without Candidate Generation
Authors:
- Junqiang LiuJLJunqiang Liu
- Ke WangKWKe Wang
- Benjamin C.M. FungBenjamin C.M. Fung
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 984-989
Abstract
Utility mining emerged recently to address the limitation of frequent itemset mining by introducing interestingness measures that reflect both the statistical significance and the user's expectation. Among utility mining problems, utility mining with the itemset share framework is a hard one as no anti-monotone property holds with the interestingness measure. The state-of-the-art works on this problem all employ a two-phase, candidate generation approach, which suffers from the scalability issue due to the huge number of candidates. This paper proposes a high utility itemset growth approach that works in a single phase without generating candidates. Our basic approach is to enumerate itemsets by prefix extensions, to prune search space by utility upper bounding, and to maintain original utility information in the mining process by a novel data structure. Such a data structure enables us to compute a tight bound for powerful pruning and to directly identify high utility itemsets in an efficient and scalable way. We further enhance the efficiency significantly by introducing recursive irrelevant item filtering with sparse data, and a lookahead strategy with dense data. Extensive experiments on sparse and dense, synthetic and real data suggest that our algorithm outperforms the state-of-the-art algorithms over one order of magnitude.Keywords
This publication has 15 references indexed in Scilit:
- UP-Growth2010
- Efficient Mining of High Utility Itemsets from Large Datasets2008
- Isolated items discarding strategy for discovering high utility itemsetsData & Knowledge Engineering, 2008
- Interestingness measures for data miningACM Computing Surveys, 2006
- A fast high utility itemsets mining algorithm2005
- Selecting the right objective measure for association analysisInformation Systems, 2004
- A Foundational Approach to Mining Itemset Utilities from Databases2004
- Depth first generation of long patterns2000
- Mining frequent patterns without candidate generation2000
- MINING ASSOCIATION RULES FROM MARKET BASKET DATA USING SHARE MEASURES AND CHARACTERIZED ITEMSETSInternational Journal on Artificial Intelligence Tools, 1998