Effective algorithms to mine skyline frequent-utility itemsets. (November 2022)

• Record Type: Journal Article
• Authors: Liu, Xuan; Chen, Genlang; Zuo, Wanli
• Is Part Of: Engineering applications of artificial intelligence. Volume 116(2022)
• Publication Date: 2022-11
• Subjects: Skyline frequent-utility itemsets -- Utility-list structure -- Tighter utility upper bounds -- Breadth-first search -- Depth-first search; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2022.105355
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: Skyline frequent-utility itemset mining is used to discover itemsets that are non-dominated by considering both support and utility factors. It is an extension of high-utility itemset mining. Most existing algorithms are based on the utility-list structure to mine skyline frequent-utility itemsets. A major limitation of utility-list based algorithms is that numerous join operations consume a huge amount of time and memory. To address this issue, two algorithms named EMSFUI-D and EMSFUI-B are proposed to mine skyline frequent-utility itemsets. EMSFUI-D performs the depth-first search to explore the search space of all itemsets. EMSFUI-B discovers itemsets based on the breadth-first search. Both algorithms utilize two pruning strategies to limit the search space. Moreover, in order to further facilitate the mining performance, the ISU -1 and ISU -2 structures are presented in EMSFUI-D to provide tighter utility upper bounds. These structures maintain the support and utility information of all 1-itemsets and 2-itemsets, respectively. Thus, there is no need to use these structures to prune search space in the breadth-first search algorithm. An extensive experimental study on real and synthetic datasets shows that our proposed algorithms outperform the state-of-the-art SKYFUP-D and SKYFUP-B algorithms in terms of execution time, memory consumption and pruning performance. Moreover, our designed algorithms are scalable for handling a large number of distinct items and transactions.