Discovery of closed high utility itemsets using a fast nature-inspired ant colony algorithm

摘要

Mining high utility itemset (HUIM) from an extensive database is a crucial descriptive task in data mining, which considers both the quantity and unit profit factor in revealing the ultimately profitable items. However, it may discover a vast number of HUIs which can be challenging to interpret by a user and also reduce the efficiency of the mining process. A solution to this problem is to mine a Closed high utility itemset, a more compact and lossless form of HUIs. In this paper, a fast nature-inspired meta-heuristic approach CHUI-AC (Closed high utility itemset mining using ant colony algorithm) has been introduced to mine CHUIs. This is the first work on mining CHUI using a nature-inspired ant colony algorithm. CHUI-AC maps the feasible solution space to a directed graph with quadratic space complexity to guide the searching efficiently. Several experiments on real-world datasets show that the proposed algorithm outrun the state-of-the-art algorithms in terms of execution time and rate of convergence. Moreover, the scalability experiments demonstrate that CHUI-AC is linearly scalable with respect to the number of transaction and number of items.