Binary partition for itemsets expansion in mining high utility itemsets

Article type: Research Article

Authors: Song, Wei^* | Wang, Chunhua | Li, Jinhong

Affiliations: College of Computer, North China University of Technology, Beijing, China

Correspondence: [*] Corresponding author: Wei Song, College of Computer, North China University of Technology, Beijing 100144, China. Tel.: +86 10 88802798; Fax: +86 10 8880279; E-mail:songweidm@gmail.com

Abstract: High utility itemset mining has recently emerged to address the limitations of frequent itemset mining. It entails relevance measures to reflect both statistical significance and user expectations. Whether breadth-first or depth-first search algorithms are employed, most methods generate new candidates by 1-extension of existing itemsets (i.e., by adding only one item to verified itemsets to generate new potential candidates). As an alternative to 1-extension, we introduce an expansion method based on binary partition. We then define the transaction utility list and key support count and discuss a new pruning strategy. Based on the new itemset expansion method and pruning strategy, we propose an efficient high utility itemset mining algorithm called BPHUI-Mine (Binary Partition-based High Utility Itemsets Mine). Tests on publicly available datasets show that the proposed algorithm outperforms other state-of-the-art algorithms.

Keywords: Data mining, high utility itemsets, binary partition, transaction utility list, key support count

DOI: 10.3233/IDA-160838

Journal: Intelligent Data Analysis, vol. 20, no. 4, pp. 915-931, 2016