Search

High utility itemset mining is an emerging data mining task, which consists of discovering highly profitable itemsets (called high utility itemsets) in very large transactional databases. Many algorithms have been proposed to efficiently discover high utility itemsets but most of them assume that items may only have positive unit profits. However, in real-world transactional databases, items (products) often have positive or negative unit profits. Mining high utility itemsets in a transactional database where items have positive or negative unit profits is a computationally expensive task, and it is thus desirable to design more efficient algorithms. To address this issue, we propose an efficient algorithm named FHN (Faster High-Utility itemset miner with Negative unit profits). It relies on a novel PNU-list structure (Positive-and-Negative Utility-list) structure to efficiently mine high utility itemsets, while considering both positive and negative unit profits. Moreover, several pruning strategies are introduced in FHN to reduce the number of candidate itemsets, and thus enhance the performance of FHN. Extensive experimental results on both real-life and synthetic datasets show that the proposed FHN algorithm is in general two to three orders of magnitude faster and can use up to 200 times less memory than the state-of-the-art algorithm HUINIV-Mine. Moreover, it is shown that FHN performs especially well on dense datasets. [ABSTRACT FROM AUTHOR]

High-utility itemset mining (HUIM) is a major contemporary data mining issue. It is different from frequent itemset mining (FIM), which only considers the frequency factor. HUIM applies both the quantity and profit factors to be used to reveal the most profitable products. Several previous approaches have been proposed to mine high-utility itemsets (HUIs) and most of them have to handle the exponential search space for discovering HUIs when the number of distinct items and the size of the database are both very large. Therefore, two evolutionary computation (EC) techniques, genetic algorithm (GA) and particle swarm optimization (PSO), were previously proposed to mine HUIs. In these studies, GAs and PSOs also could obtain the huge amount of high-utility items in a limitation time. In this paper, a novel algorithm based on the other evolutionary computation technique, ant colony optimization (ACO), is proposed to resolve this issue. Unlike GAs and PSOs, ACOs produce a feasible solution in a constructive way. They can avoid generating unreasonable solutions as much as possible. Thus, a well-defined ACO approach can always obtain suitable solutions efficiently. An ant colony system (ACS), which is extended from ACO and consists of high-utility itemset mining by ACS (HUIM-ACS), is proposed to efficiently find HUIs. In general, an EC algorithm cannot make sure the provided solution is the global optimal solution. But the designed HUIM-ACS algorithm maps the completed solution space into the routing graph and includes two pruning processes. Therefore, it guarantees that it obtains all of the HUIs when there is no candidate edge from the starting point. In addition, HUIM-ACS does not estimate the same feasible solution again in its process in order to avoid wasting computational resource. Substantial experiments on real-life datasets show that the proposed algorithm outperforms the other heuristic algorithms for mining HUIs in terms of the number of discovered HUIs, and convergence. [ABSTRACT FROM AUTHOR]