An Efficeint Algorithm Based on EFIM for Mining High-Utility Itemsets with Negative Unit Profits

The High Utility Itemset Mining (HUIM) problem is an extension of Frequent Itemset Mining (FIM) problem. Unlike FIM, HUIM allows non-binary appearance of items in transactions and it also takes into account weights and profits of items. Several algorithms have been proposed to efficiently mine HUIs. However, most of which can not deal with negative profits; while, in real word negative profits play an important role. Hence, providing an efficient algorithm for mining high utility itemsets considering negative profits is an essential task. FHN is the most recent algorithm for this purpose, which is based on the FHM algorithm. However, in HUIM problem considering only positive profits, EFIM is more efficient than FHM. EFIM uses merging and projection methods to decrease the dataset size. It also uses two techniques for pruning the search space. In this research, we proposed an efficient algorithm for HUIM problem which supports both negative and positive unit profits. We modified the upper bound definition of itemset utilities and the pruning strategies in order to support negative profits. According to the results, the proposed algorithm is better than the existing algorithms in terms of run time and memory consumption.