Totally-ordered Sequential Rules for Utility Maximization

• URL: http://arxiv.org/abs/2209.13501v1
• Date: Tue, 27 Sep 2022 16:17:58 GMT
• Title: Totally-ordered Sequential Rules for Utility Maximization
• Authors: Chunkai Zhang, Maohua Lyu, Wensheng Gan, and Philip S. Yu
• Abstract summary: We propose two novel algorithms, called TotalSR and TotalSR+, which aim to identify all high utility totally-ordered sequential rules (HTSRs) TotalSR creates a utility table that can efficiently calculate antecedent support and a utility prefix sum list that can compute the remaining utility in O(1) time for a sequence. There are numerous experimental results on both real and synthetic datasets demonstrating that TotalSR is significantly more efficient than algorithms with fewer pruning strategies.
• Score: 49.57003933142011
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: High utility sequential pattern mining (HUSPM) is a significant and valuable activity in knowledge discovery and data analytics with many real-world applications. In some cases, HUSPM can not provide an excellent measure to predict what will happen. High utility sequential rule mining (HUSRM) discovers high utility and high confidence sequential rules, allowing it to solve the problem in HUSPM. All existing HUSRM algorithms aim to find high-utility partially-ordered sequential rules (HUSRs), which are not consistent with reality and may generate fake HUSRs. Therefore, in this paper, we formulate the problem of high utility totally-ordered sequential rule mining and propose two novel algorithms, called TotalSR and TotalSR+, which aim to identify all high utility totally-ordered sequential rules (HTSRs). TotalSR creates a utility table that can efficiently calculate antecedent support and a utility prefix sum list that can compute the remaining utility in O(1) time for a sequence. We also introduce a left-first expansion strategy that can utilize the anti-monotonic property to use a confidence pruning strategy. TotalSR can also drastically reduce the search space with the help of utility upper bounds pruning strategies, avoiding much more meaningless computation. In addition, TotalSR+ uses an auxiliary antecedent record table to more efficiently discover HTSRs. Finally, there are numerous experimental results on both real and synthetic datasets demonstrating that TotalSR is significantly more efficient than algorithms with fewer pruning strategies, and TotalSR+ is significantly more efficient than TotalSR in terms of running time and scalability.

Related papers

• The Power of Resets in Online Reinforcement Learning [73.64852266145387]
  We explore the power of simulators through online reinforcement learning with local simulator access (or, local planning) We show that MDPs with low coverability can be learned in a sample-efficient fashion with only $Qstar$-realizability. We show that the notorious Exogenous Block MDP problem is tractable under local simulator access.
  arXiv  Detail & Related papers  (2024-04-23T18:09:53Z)
• Discovering Utility-driven Interval Rules [35.917665876992416]
  High-utility sequential rule mining (HUSRM) is a knowledge discovery method that can reveal the associations between events in the sequences. In this work, we propose a utility-driven interval rule mining (UIRMiner) algorithm that can extract all utility-driven interval rules (UIRs) from the interval-event sequence database.
  arXiv  Detail & Related papers  (2023-09-28T01:57:40Z)
• HUSP-SP: Faster Utility Mining on Sequence Data [48.0426095077918]
  High-utility sequential pattern mining (HUSPM) has emerged as an important topic due to its wide application and considerable popularity. We design a compact structure called sequence projection (seqPro) and propose an efficient algorithm, namely discovering high-utility sequential patterns with the seqPro structure (HUSP-SP) Experimental results on both synthetic and real-life datasets show that HUSP-SP can significantly outperform the state-of-the-art algorithms in terms of running time, memory usage, search space pruning efficiency, and scalability.
  arXiv  Detail & Related papers  (2022-12-29T10:56:17Z)
• Towards Correlated Sequential Rules [4.743965372344134]
  High-utility sequential rule mining (HUSRM) is designed to explore the confidence or probability of predicting the occurrence of consequence sequential patterns. The existing algorithm, known as HUSRM, is limited to extracting all eligible rules while neglecting the correlation between the generated sequential rules. We propose a novel algorithm called correlated high-utility sequential rule miner (CoUSR) to integrate the concept of correlation into HUSRM.
  arXiv  Detail & Related papers  (2022-10-27T17:27:23Z)
• Towards Target Sequential Rules [52.4562332499155]
  We propose an efficient algorithm, called targeted sequential rule mining (TaSRM) It is shown that the novel algorithm TaSRM and its variants can achieve better experimental performance compared to the existing baseline algorithm.
  arXiv  Detail & Related papers  (2022-06-09T18:59:54Z)
• TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
  We propose a generic framework namely TaSPM, based on the fast CM-SPAM algorithm. We also propose several pruning strategies to reduce meaningless operations in mining processes. Experiments show that the novel targeted mining algorithm TaSPM can achieve faster running time and less memory consumption.
  arXiv  Detail & Related papers  (2022-02-26T17:49:47Z)
• US-Rule: Discovering Utility-driven Sequential Rules [52.68017415747925]
  We propose a faster algorithm, called US-Rule, to efficiently mine high-utility sequential rules. Four tighter upper bounds (LEEU, REEU, LERSU, RERSU) and their corresponding pruning strategies are proposed. US-Rule can achieve better performance in terms of execution time, memory consumption and scalability.
  arXiv  Detail & Related papers  (2021-11-29T23:38:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.