A Novel Approach of Mining High Utility Itemsets
摘要
Mining High Utility Itemsets finds itemsets from transaction databases that are usually sold together and their profit overcomes a given threshold. Some popular items for everyday life appear in many transactions. Therefore, itemsets containing all popular items usually are High Utility Itemset (HUI). These HUIs is known for a long time. Therefore, algorithms of mining HUIs do not need to mine them. Previous studies still mine all HUIs. As a result, they consume both CPU time and memory. In this paper, we present a novel effective algorithm of mining HUIs overcomes this disadvantage. It is called npHUIM. We use compact lists to store items and itemsets. First, our algorithm finds popular items, unpopular items, unpromising items, and unpromising 2-itemsets after scanning the database. Next, it scans the database to mine HUIs. It only generates itemsets that contain zero or one popular item and not contain unpromising items or unpromising 2-itemsets. Then, it adds/updates these itemsets to lists. Then, npHUIM presents HUIs based on testing utility of generated itemsets. We use pruning strategies based on utility of transactions to remove both unpromising items and unpromising itemsets. Experiments are conducted on benchmark datasets. Our algorithm is compared with an equivalent algorithm. Experimental results show that the proposed algorithm is better than the compared algorithm. Moreover, npHUIM significantly reduces number of HUIs.