HAOP-Miner: Self-adaptive high-average utility one-off sequential pattern mining. (1st December 2021)

• Record Type: Journal Article
• Authors: Wu, Youxi; Lei, Rong; Li, Yan; Guo, Lei; Wu, Xindong
• Is Part Of: Expert systems with applications. Volume 184(2021)
• Publication Date: 2021-12-01
• Subjects: Sequential pattern mining -- Self-adaptive -- High average utility -- Apriori property -- One-off condition; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115449
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Address self-adaptive HAOP mining which can discover extremely important patterns. We propose the HAOP-Miner algorithm that contains two key steps. HAOP-Miner employs an online Reverse filling strategy to calculate the support. HAOP-Miner adopts Apriori-like strategy to prune the candidate patterns. HAOP-Miner has a high level of efficiency and it is easier to find valuable patterns. Abstract: One-off sequential pattern mining (SPM) (or SPM under the one-off condition) is a kind of repetitive SPM with gap constraints, and has been widely applied in many fields. However, current research on one-off SPM ignores the utility (can be price or profit) of items, resulting in some low-frequency but extremely important patterns being ignored. To solve this issue, this paper addresses self-adaptive High-Average utility One-off sequential Pattern (HAOP) mining which has following three characteristics. Any two occurrences cannot share any letter in the sequence. The support (number of occurrences), utility and length of the pattern are considered simultaneously. The HAOP mining discovers patterns with a self-adaptive gap which means that users do not need to set the gap constraints. We propose an effective algorithm called HAOP-Miner that involves two key steps: support calculation and candidate pattern generation. For the support calculation, we propose a heuristic algorithm named the Reverse filling (Rf) algorithm that can effectively calculate the support by avoiding creating redundant nodes and pruning the redundant and useless nodes after finding an occurrence. Since HAOP mining does not satisfy the Apriori property, a support lower bound method combined with the pattern growth strategy is adopted to generate the candidate patterns. The experimental results first validate the effectiveness of HAOP-Miner, and then demonstrate that HAOP-Miner has better performance than other state-of-the-art algorithms. More importantly, HAOP-Miner is easier to mine valuable patterns. The algorithms and datasets are available at https://github.com/wuc567/Pattern-Mining/tree/master/HAOP-Miner .