Targeted Mining of Top-k High Utility Itemsets

Shan Huang, Wensheng Gan, Jinbao Miao, Xuming Han, Philippe Fournier-Viger

Introduction

High Utility Itemset Mining (HUIM) is a critical task in data science, focused on identifying patterns that yield the highest value—such as profit—rather than those that simply occur most frequently. While traditional frequent pattern mining might identify common but low-value item combinations, HUIM uncovers the "hidden gems" in transactional data. However, standard HUIM algorithms suffer from two primary limitations: the "threshold dilemma," where users must guess an optimal minimum utility value, and a "lack of focus," where algorithms return all profitable patterns regardless of their relevance to a specific business query.

To address these issues, this paper introduces TMKU (Targeted Mining of top-$k$ high Utility itemset), an algorithm designed to find the top-$k$ most profitable itemsets that contain a specific user-defined "target" pattern. By combining targeted querying with top-$k$ ranking, the researchers eliminate the need for users to guess complex profit thresholds, making high-utility data mining both more efficient and more user-friendly.

The Targeted Top-k Problem

The authors redefine the mining task as a "Targeted Top-$k$" problem. Instead of requiring a static minimum utility threshold, the user specifies two parameters:

  1. $k$: The number of high-utility itemsets to retrieve.
  2. Target Pattern: A specific item or set of items that must be present in every returned result.

This approach allows business analysts to ask specific questions, such as "What are the top 10 most profitable bundles that include a specific high-end smartphone?" without needing to understand the underlying distribution of profit values in the database.

Methodology: The TMKU Algorithm

The TMKU algorithm integrates several innovative components to optimize the search process:

1. TP-tree (Target-Pattern tree)

The algorithm utilizes a specialized prefix tree structure called the TP-tree. This structure efficiently stores high-utility itemsets and facilitates rapid querying of patterns that share common prefixes, significantly reducing the computational overhead of scanning the database.

2. Dynamic Thresholding with TopKMap

To solve the threshold dilemma, TMKU employs a TopKMap data structure. This map tracks the $k$ highest utility itemsets found during the mining process. The utility of the $k$-th itemset serves as a dynamic threshold ($\eta$). As the algorithm discovers more profitable patterns, $\eta$ is raised in real-time, allowing the system to prune unpromising branches of the search space earlier.

3. Pruning Strategies

TMKU introduces several strategies to enhance efficiency:

  • Strategy 1 (SUR) & Strategy 2 (RIU): These strategies focus on raising the threshold $\eta$ as quickly as possible during the initial phases of the search.
  • Target-Based Pruning (Strategy 5): This is the "secret sauce" for targeted mining. By employing a bottom-up traversal within the TP-tree, the algorithm checks if a branch contains the target pattern. If the Transaction Weighted Utilization (TWU) of a node is lower than the current threshold or if the branch cannot contain the target, the entire sub-tree is discarded.

Experimental Evaluation

The researchers evaluated TMKU across six diverse datasets from the SPMF library, including real-world retail data (foodmart, retail, chainstore) and dense/synthetic data (mushroom, ecommerce, T10I4D100K).

Performance and Efficiency

TMKU consistently outperformed its sub-variants (TMKU$_{v1}$ and TMKU$_{v2}$) that lacked the full suite of pruning strategies. On the massive chainstore dataset, which contains over 1.1 million transactions, TMKU demonstrated superior execution times. For instance, with $k=210$, TMKU completed the task in 1,010 seconds, while variants without optimized pruning took significantly longer.

Memory and Scalability

Despite the memory requirements of tree-based structures, TMKU exhibited stable memory usage. As $k$ increases, memory consumption grows initially but reaches an equilibrium, making it viable for large-scale industrial use. Furthermore, the algorithm showed linear scalability; tripling the size of the chainstore database resulted in a predictable, linear increase in execution time, proving its readiness for "Big Data" scenarios.

Conclusion and Future Work

TMKU represents a significant advancement in making high-utility data mining more accessible and efficient. By treating the user's target pattern as a mathematical constraint rather than a simple filter, the algorithm can ignore vast swaths of irrelevant data.

Future research directions include the development of distributed or parallel versions of TMKU for web-scale datasets, the creation of visualization tools to help users interpret profitable bundles, and the investigation of tighter mathematical bounds to further optimize performance in dense datasets.

Summary updated

BibTeX
@article{huang2023targeted,
  author = {Shan Huang and Wensheng Gan and Jinbao Miao and Xuming Han and Philippe Fournier-Viger},
  title = {{Targeted Mining of Top-k High Utility Itemsets}},
  journal = {Engineering Applications of AI},
  year = {2023},
  doi = {10.1016/j.engappai.2023.107047},
}
Figure