Efficient Skyline Itemsets Mining
Vikram Goyal, Ashish Sureka, Dhaval J. Patel · 2008
Utility Mining (UM) in context of Market Basket Analysis consists of mining itemsets from a transaction database guided by optimizing utility. For example, UM consists of extracting all itemsets in a transaction database having utility above a user-defined minimum threshold or mining Top-K high utility itemset. Similarly, Frequent Itemset Mining (FIM) finds frequent patterns using a frequency threshold. However, none of these pattern mining methods determine patterns that are interesting in both the aspects of utility and frequency. In addition these methods require a user to specify respective thresholds. In this paper, we present a novel framework for mining a new pattern called as Utility-Frequency Skyline Pattern. We formalize our problem as a pattern search problem and propose an efficient technique on recently proposed popular data structure called as UP Tree (Utility-Pattern Tree). The proposed algorithm consists of two phases called as Filter and Refine. In the Filter phase, a set of candidate itemsets are mined, which are then verified finally in the Refine phase. We study the effectiveness of our proposed algorithm along with two heuristics and conclude that our proposed method is efficient.