Most Frequent Itemset Optimization

Jonas NüßleinarXiv 2019 · arXiv · OpenReview

Abstract

In this paper, we propose a R-step approximation to solve frequent itemset mining on quantum hardware like quantum annealing or QAOA. The idea is to search for the set of items where the minimal 2-item frequency is maximal. This can be represented as a maximum clique problem.

Introduction

Frequent Itemset Mining (FIM) is a foundational task in data mining, famously applied in "market basket analysis" to identify groups of items that frequently co-occur in transactions. Despite its utility, FIM is NP-hard, presenting significant computational challenges as the number of items and transactions scales. Classical state-of-the-art algorithms, such as FP-Growth, often suffer from high memory consumption due to the complex tree structures required to track item combinations.

This paper introduces Most Frequent Itemset Optimization (MFIO), a method that bridges the gap between traditional data mining and quantum computing. By reformulating FIM as a Maximum Clique problem, we enable the use of quantum hardware—specifically quantum annealers and the Quantum Approximate Optimization Algorithm (QAOA)—to solve optimization-based mining tasks with high efficiency.

Methodology

The MFIO framework simplifies the complexity of multi-item frequencies by focusing on pairwise relationships. The approach follows a four-stage pipeline:

  1. Graph Modeling: The transaction database is represented as a graph where vertices are items. Edges are weighted based on the empirical probability $P(i \cup j)$ that two items appear in the same transaction.
  2. Maximum Clique Reduction: Finding a frequent itemset of size $N$ is treated as finding a "clique" (a subset of vertices where every pair is connected). The objective is to find the clique where the minimum pairwise frequency among all members is maximized.
  3. R-step Approximation: Because the ideal frequency threshold ($\tau$) is unknown, the algorithm uses an iterative "binary search" style adjustment. Starting at $\tau = 0.5$, the algorithm removes edges below the threshold and finds the maximum clique. If the resulting clique is too small, $\tau$ is lowered; if too large, it is raised. This continues for $R$ iterations.
  4. QUBO Formulation: To solve the problem on quantum hardware, it is converted into a Quadratic Unconstrained Binary Optimization (QUBO) matrix. In this format, selecting a vertex provides a reward, while missing edges between selected vertices incur a heavy penalty, guiding the quantum solver toward valid cliques.

Experimental Evaluation

The paper evaluates MFIO using two distinct datasets:

  • Synthetic Dataset: 25,000 transactions containing a "planted" 20-item set hidden within 24,000 random transactions.
  • English Words Dataset: 370,000 English words, where each word is a transaction and its letters are items, used to find frequent letter clusters.

Key Results

  • Performance: In synthetic tests, MFIO identified the correct 20-item set in 34 seconds, significantly outperforming "Bomo" (a fast C implementation of FP-Growth), which took 102 seconds.
  • Memory Usage: The memory disparity was substantial. MFIO required only 122 KB of memory for its internal data structures, while Bomo required 83 MB—representing a reduction of approximately 680x.
  • Real-World Utility: The algorithm successfully identified common English letter clusters, such as {a, e, i, n, o, s, t}, demonstrating its effectiveness on natural data distributions.

Discussion and Insights

The primary innovation of MFIO is the Pairwise Simplification. By approximating complex multi-item frequencies through the maximal "minimal 2-item frequency," the problem can be represented as a simple graph rather than a hypergraph. This leads to extreme memory efficiency, as the algorithm only needs to store the edges of the graph rather than conditional trees.

Furthermore, by reducing FIM to a Maximum Clique problem, the method leverages well-studied QUBO formulations, making FIM accessible to current-generation quantum annealers like the D-Wave 2000Q.

Limitations and Future Work

While MFIO is highly efficient, it is an approximation method. It is designed to find the "most frequent" set rather than enumerating every set above a specific threshold, which may be required for certain traditional FIM applications. Additionally, as the number of items ($K$) increases, the physical constraints of current quantum hardware—such as qubit counts and coupler precision—may become a bottleneck. Future research will focus on refining the R-step balance and scaling the approach for larger industrial datasets.

Summary updated

Abstract

In this paper we propose a R-step approximation to solve frequent itemset mining on quantum hardware like quantum annealing or QAOA. The idea is to search for the set of items where the minimal 2-item frequency is maximal. This can be represented as a maximum clique problem.
BibTeX
@misc{nulein2019most,
  author = {Jonas Nüßlein},
  title = {{Most Frequent Itemset Optimization}},
  year = {2019},
  eprint = {1904.07693},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.07693},
}
Figure