TL;DR
This paper introduces "dense itemsets," a generalization of frequent itemsets that allows for some missing attributes, making it more robust to noise and better at capturing real-world data structures. They propose levelwise and top-k algorithms to efficiently mine these dense itemsets and demonstrate their utility in data exploration and generating succinct descriptions of large datasets.
What Problem Does This Paper Address?
Traditional frequent itemset mining, a cornerstone of association rule discovery, relies on finding sets of items that perfectly co-occur in a significant number of transactions. This strict requirement often fails to capture meaningful patterns in real-world data, where perfect co-occurrence is rare due to noise or incomplete information. For instance, an itemset might be conceptually important, but if even one attribute is missing in a transaction, that transaction doesn't contribute to its frequency. This paper addresses this limitation by introducing "dense itemsets," which relax the perfect co-occurrence requirement, allowing for a certain proportion of missing attributes while still demanding a high density of present attributes within a chosen subset of transactions. This aims to find more robust and meaningful patterns that might be missed by traditional methods.
Methods
The core contribution is the definition of dense itemsets. Unlike "weakly dense" itemsets (which allow for partial co-occurrence but can suffer from "free-riders" – items that benefit from the density of others without contributing much themselves), dense itemsets introduce a recursive definition. An itemset is considered dense if all of its non-empty subsets also meet a "weak density" criterion over a specific subset of transactions. This recursive property ensures a more uniform density and avoids the free-rider problem.
To mine these dense itemsets, the authors propose two main algorithms:
- Levelwise Algorithm (DENSE-SETS): This algorithm follows the familiar Apriori principle. It starts by finding dense itemsets of size 1, then uses these to generate candidate dense itemsets of size 2, and so on. This level-by-level approach leverages the antimonotonicity property that arises from the dense itemset definition.
- Top-k Dense Itemsets Algorithm: This algorithm addresses the challenge of parameter selection (density threshold
dand support thresholdσ). Given a support thresholdσand a desired numberkof itemsets, it efficiently finds thekdensest itemsets. This is achieved using a heap to manage candidate itemsets and their densities.
A key component for efficiency is the WEAK-DENSITIES subroutine, which computes the weak density of an itemset at a given support level by performing a single pass over the database and calculating "intersection profiles."
Datasets
The paper evaluates their methods on two datasets:
- Retail data: A publicly available dataset from the FIMI repository, preprocessed to select the 1998 most frequent attributes.
- Course data: A dataset from the University of Helsinki Computer Science Department, containing enrollment information for 1739 students and 102 courses.
No new benchmarks were introduced; existing, well-known datasets were used for evaluation.
Key Insights and Ideas
- Dense itemsets are more robust to noise: By allowing for a controlled proportion of missing attributes, dense itemsets can uncover patterns that are obscured by noise or incomplete data, which traditional frequent itemsets might miss.
- Recursive definition prevents "free-riders": The requirement that all subsets of a dense itemset must also be dense is crucial. It prevents itemsets from appearing dense simply because one or two items are highly frequent, while the rest are not.
- Parameter selection is simplified with top-k: The top-k algorithm is a practical solution for explorers who may not know the ideal density and support thresholds beforehand, allowing them to discover interesting patterns without extensive parameter tuning.
- Dense itemsets can provide succinct data descriptions: The authors demonstrate that dense itemsets can be used in a set-cover-like approach to create intuitive reorderings of data matrices, highlighting key relationships and structures.
- The "support" threshold (
σ) controls pattern resolution: The choice ofσdictates the granularity at which patterns are observed. A lowerσallows for more noise and potentially larger, less specific patterns, while a higherσfocuses on denser, more specific co-occurrences.
Key Results
- Experimental validation: The algorithms were tested on the Retail and Course datasets, showing that dense itemsets can be found in reasonable time, even with a moderate number of parameters.
- Practical utility: On the Course dataset, dense itemsets revealed meaningful patterns, such as students pursuing programming without having completed the theory course, which were not discoverable by traditional frequent itemset mining (frequency 0).
- Efficiency: The levelwise and top-k algorithms are shown to be efficient enough for practical use, with the database pass for density calculation requiring only a single scan.
- Set cover application: A greedy set-cover approach using dense itemsets successfully generated an intuitive reordering of the Course data matrix, highlighting underlying structures.
Limitations and Future Work
- Parameter tuning: While the top-k algorithm helps, selecting appropriate
σandkvalues still requires some domain knowledge or iterative exploration. - Scalability: The paper acknowledges that Python's interpreted nature limits performance, and optimized implementations would be faster. Further research into scaling these algorithms to massive datasets is implied.
- Generalizations: The authors suggest exploring generalizations of the density definition, such as "external intersection counts" and applying the concept to topic models and query approximation.
- Filtering and reordering techniques: Developing more sophisticated filtering and reordering techniques for large collections of patterns is identified as an important area for future work.
Summary updated