A novel fast algorithm for mining k-item High Utility Itemsets from incremental databases

Abstract

Mining High Utility Itemsets (HUIs) discovers itemsets making much profit in business from a transaction database. Therefore, mining HUIs is important for planing business. Previous studies use a tree structure and pruning strategies, or a list structure and generation of promising itemsets to decrease both time and memory for computing. Fast algorithms for mining compact HUIs have proposed to discover close HUIs or maximum HUIs. However, these studies still take a long time and consume much memory because of considering all itemsets of items in a transaction. Moreover, business managers usually make decisions more effectively based on itemsets containing several items. In this paper, we propose a novel fast algorithm for mining k-item HUIs that meets the need of manages and decreases both time and memory for mining HUIs. We use a simple list structure to store k-itemsets appearing during browsing transactions. This list stores items and utility of each itemset. Our algorithm consists of two main steps. First, the current database is vertically segmented into sub-partitions. Each row in a sub-partition contains k items. Then, k-item HUIs are mined from each sub-partition. The proposed algorithm obtains advantages including without candidate generation, without re-scanning database when changing the threshold of utility. Experiments are conducted on dense benchmark databases. Results of experiments show that our algorithm is better than state-of-the-art methods.