PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Utility-Oriented Pattern Mining

Wensheng Gan, Jerry Chun-Wei Lin, Philippe Fournier-Viger, Han-Chieh Chao, Vincent S. Tseng, Philip S. Yu

arXiv:1805.10511v2cs.DB

TL;DR

Existing pattern-mining frameworks often select frequent or support-based patterns while treating items equally, even though real applications attach different importance to items and patterns. This survey systematically reviews UPM concepts, applications, algorithms, advanced topics, software, and challenges. It provides a comprehensive synthesis of more than 150 studies and organizes methods into a taxonomy while discussing their advantages and disadvantages.

  • Problem

    Frequency- and support-based mining can overlook item or pattern importance, and UPM previously lacked a comprehensive survey and systematic comparison of state-of-the-art methods.

  • Method

    The paper conducts a systematic survey of UPM, introducing concepts and applications, presenting a taxonomy of mining approaches, and reviewing advanced topics, software, datasets, and challenges.

  • Results

    The survey investigates more than 150 UPM papers from the last 15 years and comprehensively reviews methods for high-utility itemsets, rules, sequences, and episodes.

  • Takeaways & Limitations

    UPM provides a framework for discovering patterns using utility measures tied to user preferences and domain objectives such as profit, cost, quantity, satisfaction, or risk.

  • Takeaways & Limitations

    Tree-based approaches may require trees that do not fit in memory, expensive construction, recursive processing, and sensitivity to the minimum utility threshold.

Abstract

from arXiv · show

The main purpose of data mining and analytics is to find novel, potentially useful patterns that can be utilized in real-world applications to derive beneficial knowledge. For identifying and evaluating the usefulness of different kinds of patterns, many techniques and constraints have been proposed, such as support, confidence, sequence order, and utility parameters (e.g., weight, price, profit, quantity, satisfaction, etc.). In recent years, there has been an increasing demand for utility-oriented pattern mining (UPM, or called utility mining). UPM is a vital task, with numerous high-impact applications, including cross-marketing, e-commerce, finance, medical, and biomedical applications. This survey aims to provide a general, comprehensive, and structured overview of the state-of-the-art methods of UPM. First, we introduce an in-depth understanding of UPM, including concepts, examples, and comparisons with related concepts. A taxonomy of the most common and state-of-the-art approaches for mining different kinds of high-utility patterns is presented in detail, including Apriori-based, tree-based, projection-based, vertical-/horizontal-data-format-based, and other hybrid approaches. A comprehensive review of advanced topics of existing high-utility pattern mining techniques is offered, with a discussion of their pros and cons. Finally, we present several well-known open-source software packages for UPM. We conclude our survey with a discussion on open and practical challenges in this field.

1 Introduction

Traditional pattern mining often prioritizes frequency or co-occurrence, while utility-oriented pattern mining incorporates user-defined importance such as profit, cost, quantity, satisfaction, or risk. The survey addresses the lack of a comprehensive, systematic overview by reviewing more than 150 UPM studies, organizing state-of-the-art methods, and discussing applications and advanced topics.

  • Motivation: Traditional pattern-mining algorithms often overlook implicit factors such as utility, interestingness, or risk that matter in real-world situations.UPM addresses this gap by considering the relative importance of items.
  • Utility-Oriented Pattern Mining: UPM assigns item utilities from user knowledge or preferences and measures pattern importance through risk, profit, cost, quantity, satisfaction, or related values.Utility values may represent subjective domain-specific preferences.
  • Research Gap: After more than 15 years of theoretical development, UPM lacked a comprehensive survey and systematic comparison of state-of-the-art algorithms.The survey aims to address the gap between theory and application.
  • Survey Scope: The survey investigates more than 150 UPM papers from the last 15 years and summarizes them systematically.It also compares developments with earlier work and introduces concepts, examples, applications, and evaluation measures.
  • Survey Organization: The article presents a taxonomy covering Apriori-based, tree-based, projection-based, vertical/horizontal-data-format-based, and hybrid UPM approaches.It further reviews advanced topics, open-source software, datasets, and practical challenges.

2 Basic Concept: Utility-Oriented Pattern Mining

UPM extends pattern mining by evaluating user-relevant utility across itemsets, rules, sequences, and episodes rather than relying only on frequency or support. The framework combines utility theory with mining techniques to discover high-utility patterns for applications where statistical occurrence and practical importance differ.

  • High-Utility Itemsets: A high-utility itemset has total utility at least equal to the user-specified minimum utility threshold.Item utility is based on quantity multiplied by profit, and itemset utility sums utilities across relevant transactions.
  • Sequential Patterns: High-utility sequential pattern mining considers both itemset utilities and sequence order, making it more complex than traditional UPM or sequential pattern mining.A HUSP satisfies u(s) ≥ minutil.
  • UPM Definition: UPM uses utility theory and mining techniques to discover high-utility itemsets, rules, sequences, and episodes.Its framework includes data structures, pruning strategies, and upper bounds.
  • Comparisons with Related Concepts: UPM differs from frequency-based mining because it considers both statistical significance and profit significance, whereas FPM selects patterns by support.Frequent patterns may lack business value when item importance differs.
  • Evaluation Measures: Utility measures include general, average, expected or potential, affinitive, and utility-occupancy measures for different data and mining settings.General utility combines external factors such as profit or risk with internal factors such as quantity.

3 Basic Approaches for High-Utility Itemset Mining

The survey organizes high-utility itemset mining into Apriori-based, tree-based, projection-based, data-format-based, and hybrid approaches. These methods progressively address candidate-generation, database-scan, memory, and efficiency limitations through upper bounds, compressed structures, projections, and utility lists.

  • Apriori-based Approaches: Early Apriori-like methods may generate many nonexistent candidates, require multiple database scans, and consume substantial time and memory.MEU may overestimate and produce incomplete results, while early approaches generally rely on loose utility upper bounds.
  • Apriori-based Approaches: Apriori-based algorithms use upper bounds such as TWDC to prune candidate itemsets because utility lacks support’s downward-closure property.Two-Phase introduces TWDC: if an itemset is not a high transaction-weighted utility itemset, none of its supersets is a high-utility itemset.
  • Tree-Based Pattern-Growth Approaches: Tree-based methods replace level-wise candidate generation with pattern growth, compressing the database and typically requiring only two or three scans.Their disadvantages include expensive construction, recursive conditional-tree processing, memory pressure, and sensitivity to the minimum-utility parameter.
  • Projection-Based Pattern-Growth Approaches: Projection-based approaches reduce candidate-generation effort by mining projected sub-databases, with prefix, bi-level, and pseudo-projection improving processing efficiency.CTU-PRO and CTU-PROL use compressed utility trees and independently mined projected subdivisions; CTU-PROL avoids rescanning to calculate actual HTWUI utilities.
  • New Data-Format-Based Approach: Single-phase vertical or horizontal data-format methods, including HUI-Miner, FHM, d2HUP, HUP-Miner, and EFIM, target greater efficiency than tree-based approaches.HUI-Miner introduced utility lists and remaining utility; HUP-Miner added PU-Prune and LA-Prune, although selecting its partition number K is difficult empirically.
  • Hybrid Approaches: Hybrid methods combine utility lists, remaining utility, and tree guidance to avoid expanding itemsets absent from the database without complex pruning overhead.mHUIMiner was reported to perform well on sparse datasets.

4 Advanced Topic of UPM

Advanced UPM research addresses large search spaces and the need to mine utility patterns from dynamically changing databases. These efforts include high-average-utility mining and incremental methods for record insertion, deletion, and modification.

  • High-average-utility itemset mining addresses HUIM’s exponential search space and the tendency of longer itemsets to receive inflated utility estimates.The survey motivates HAUIM because large itemsets may have unreasonable estimated profits compared with their actual values.
  • Dynamic UPM handles databases whose transactions are inserted, deleted, or modified rather than remaining static.Most algorithms process static databases, while real-world records can change over time.
  • HUIM with record insertion: Incremental insertion methods reuse prior data structures and mining results to continuously analyze updated data.Early FUP-HUI-INS and PRE-HUI-INS methods use utility-oriented dynamic maintenance strategies derived from FUP and pre-large concepts.
  • HUIM with record insertion: FUP-HUI-INS and PRE-HUI-INS require an additional database rescan, whereas HUI-list-INS and EIHI reduce runtime and memory usage using utility-lists and utility properties.The two-phase methods also compute high-transaction-weighted utility upper bounds through pattern growth.
  • HUIM with record deletion: Record deletion is addressed through updated-itemset concepts and separate support thresholds that delay rescanning the original database.The supplied passage identifies FUP2 and pre-large as approaches for deletion, but does not describe their complete procedures.
  • HUIM with record modification: Record modification is treated as a separate dynamic-database operation, with FUP-HUP-tree-MOD proposed to handle changed or invalid information.The motivation includes typographical errors and other changes introduced while periodic transaction data is entered.

4.3 Concise Representations of Utility Patterns

Concise utility-pattern representations aim to reduce redundancy and user overload while preserving as much high-utility information as possible. Maximal representations are compact but lossy, whereas closed high-utility itemsets are designed to be lossless and complete.

  • Low utility thresholds can produce too many high-utility patterns and candidates, increasing execution time, memory consumption, and user-analysis burden.The survey notes that returning the entire HUI set is often impractical when resources or interpretability are limited.
  • Maximal high-utility pattern: Maximal high-utility itemsets reduce output size by retaining HUIs that are not subsets of other HUIs.This representation is not lossless because subset utilities cannot be recovered without rescanning the database.
  • Maximal high-utility pattern: Recovering all HUIs from maximal HUIs is inefficient because many subsets of a maximal HUI may have low utility.
  • Closed high-utility pattern: Closed high-utility itemsets provide a lossless, compact representation intended to preserve complete information while reducing redundancy.The survey describes AprioriHC, AprioriHC-D, and CHUID as algorithms for mining this representation.
  • Closed high-utility pattern: EFIM-Closed mines closed HUIs using closure checking and local-utility and sub-tree-utility upper bounds to prune the search space.The stated strategies are closure jumping, forward closure checking, and backward closure checking.

4.4 Mining High-Utility Quantitative Itemsets/Rules

High-utility quantitative itemset mining extends utility mining by incorporating item quantities, which standard high-utility itemset mining overlooks. The resulting quantitative rules can support product packaging and inventory estimation.

  • High-utility quantitative itemset mining incorporates item quantities that standard high-utility itemset mining ignores.HUQI and the vertical utility-list-based VHUQI were developed for this setting.
  • A rule such as (bread, 3, 4) ⇒ (milk, 2, 3) represents customers purchasing three or four breads together with two or three milks.
  • Quantitative utility rules can guide product packaging and estimate inventory requirements based on associated item quantities.

4.5 High-Utility Sequential Pattern Mining

High-utility sequential pattern mining extends sequence analysis by incorporating utility, with successive methods improving generality, pruning, correctness, scalability, and application scope.

  • Early models: HUSPM integrates utility with sequential patterns, but early UWAS-tree and IUWAS-tree models cannot represent sequence elements containing multiple items.UL and US were designed to address this limitation, while their problem definition remained specific.
  • Generic frameworks: USpan formalized HUSPM through an LQS-tree, I-Concatenation and S-Concatenation, and SWDC-based pruning, but its utility-matrix representation is memory-costly.The framework provides a generic search space and pruning mechanism for high-utility sequences.
  • Pruning strategies: Projection-based methods improve pruning: PHUS uses SUUB, HuspExt uses CRoM and PBCG, and ProUM uses SEU with utility arrays.HuspExt cannot discover complete HUSPs because of an incorrect upper bound, whereas ProUM’s SEU guarantees correctness and completeness.
  • Recent methods: HUSP-ULL uses utility-linked lists, look-ahead, and irrelevant-item pruning, and experiments identify it as the fastest among compared HUSPM algorithms.These methods represent continued optimization of high-utility sequential pattern discovery.
  • Applications: The survey also reports the first work combining mobility patterns with utility to mine high-utility mobile sequential patterns.This extends HUSPM beyond conventional sequence settings to mobile data mining.

4.6 High-Utility Episode Mining

High-utility episode mining extends frequent episode mining to complex event sequences by incorporating utility, while subsequent work improves efficiency and studies additional application settings.

  • Motivation: High-utility episode mining addresses the loss of utility, importance, and risk information in frequent episode mining over complex event sequences.UP-Span was the first attempt but had low runtime and memory efficiency and used a loose EWU upper bound.
  • Advances: TSpan improves UP-Span by saving considerable search space and runtime, while later studies address complex event sequences, stock investment, and top-k high-utility episode mining.These developments broaden both efficiency and application coverage.

4.7 UPM in Big Data

UPM for big data develops distributed, parallel, and approximation-based methods for large itemset and sequence datasets, including memory-adaptive stream-oriented processing.

  • Motivation: Big-data UPM requires more efficient frameworks to handle large-scale mining problems.The survey discusses models for big itemset and big sequence data.
  • Big itemset data: PHUI-Growth uses Hadoop MapReduce for parallel high-utility itemset mining, while PHUI-Miner uses sampling to extract approximate high-utility itemsets.These approaches distribute mining tasks or trade exactness for scalability.
  • Big sequence data: BigHUSP uses multiple MapReduce steps for distributed high-utility sequential pattern mining, and MAHUSP adapts memory usage for high-utility sequence mining over streams.MAHUSP guarantees discovery of all HUSPs under certain circumstances and adapts memory allocation without sacrificing much discovered-pattern quality.

4.8 UPM in Stream Data

Stream-data UPM addresses continuously arriving data under memory constraints through temporal, window-based, incremental, and interactive mining models.

  • Motivation: Data streams are infinite sequences of elements arriving continuously and rapidly, but few stream-mining methods incorporate utility.This motivates specialized high-utility stream-mining models.
  • Temporal mining: THUI-Mine identifies temporal high-utility itemsets with fewer temporal 2-itemsets, reducing execution time and candidate generation across time windows.The method operates with limited memory space while mining high-utility itemsets from streams.
  • Stream models: MHUI-BIT, MHUI-TID, and GUIDE provide stream-mining models, with GUIDE supporting landmark, sliding, and time-fading windows.HUS-tree and HUPMS support incremental and interactive UPM with a sliding window.

4.9 UPM with Various Interesting Constraints

UPM has evolved beyond efficiency-focused mining toward effectiveness under diverse constraints and applications. Privacy preservation for high-utility patterns is also identified as an important extension.

  • 4.9 UPM with Various Interesting Constraints: Constraint-based UPM algorithms target effectiveness across diverse problems, data, constraints, and applications.The survey notes that effectiveness relates to usefulness in varied settings, alongside efficiency improvements.
  • 4.9 UPM with Various Interesting Constraints: UPM with various interesting constraints remains an active research topic.
  • 4.9 UPM with Various Interesting Constraints: Privacy-preserving high-utility pattern mining is considered more realistic and critical than privacy-preserving frequent-pattern or sequence mining.The survey mentions preliminary models for hiding sensitive high-utility itemsets.

5 Open-Source Software and Datasets

Open-source systems reduce barriers to reproducing and comparing UPM algorithms, while released real, semi-authentic, and synthetic datasets support evaluation.

  • 5 Open-Source Software and Datasets: Few released implementations force researchers to reimplement UPM algorithms, potentially introducing unfair experimental comparisons.
  • 5 Open-Source Software and Datasets: UP-Miner provides Java implementations of 13 algorithms for multiple utility-oriented pattern types and concise pattern representations.It is described as a cross-platform utility mining system.
  • 5 Open-Source Software and Datasets: SPMF is a Java library offering 170 data-mining algorithms, a large pattern-mining collection, and a graphical interface.The library has been cited in more than 700 research papers since 2010.
  • 5 Open-Source Software and Datasets: Common UPM datasets include released real datasets, semi-authentic datasets with synthetic utilities, and IBM Quest synthetic datasets.
  • 5 Open-Source Software and Datasets: Foodmart contains 21,556 customer transactions and 1,559 distinct items with quantity and unit-profit information.
  • 5 Open-Source Software and Datasets: Semi-authentic datasets assign internal utilities uniformly from and external utilities using a Gaussian distribution.
  • 5 Open-Source Software and Datasets: Examples of IBM Quest synthetic datasets include T10I4D100K, T40I10D100K, and C8S6T4I3D|X|K.

6 Open Challenges and Opportunities

The survey identifies open challenges spanning application relevance, computational efficiency, unified modeling, complex and large-scale data, and real-time mining.

  • 6 Open Challenges and Opportunities: Application-driven UPM must better reflect real-life problems across diverse fields, data, constraints, and applications.
  • 6 Open Challenges and Opportunities: Computational costs in execution time and memory remain problematic for dense or large databases and long transactions.
  • 6 Open Challenges and Opportunities: A generic UPM framework should emphasize general principles and modeling rather than specific implementations.
  • 6 Open Challenges and Opportunities: Current UPM techniques are poorly suited to heterogeneous structured, unstructured, semi-structured, dynamic, uncertain, and high-dimensional data.
  • 6 Open Challenges and Opportunities: Large-scale data requires incremental or dynamic processing that incorporates results from prior analyses instead of repeated batch mining.
  • 6 Open Challenges and Opportunities: Scalable online mining for e-commerce streams should use algorithms sub-linear to the input or, at minimum, linear.

7 Conclusions

The survey presents UPM as a broad, application-relevant field centered on subjective utility and encompassing multiple high-utility pattern-mining tasks. It synthesizes state-of-the-art methods, advanced topics, software, and future directions.

  • 7 Conclusions: UPM uses subjective utility to extract useful knowledge for applications including cross-marketing, e-commerce, finance, medical, and biomedical domains.
  • 7 Conclusions: The survey reviews high-utility itemset, association rule, sequential pattern, sequential rule, and episode mining.
  • 7 Conclusions: The survey covers common and state-of-the-art approaches, advanced topics with pros and cons, open-source software, and practical challenges.
Loading 1805.10511v2…