Abstract
Traditional Frequent Item Set Mining (FIM) often results in a "pattern explosion," where algorithms return an overwhelming number of redundant or statistically insignificant results. This paper proposes a shift from frequency-based mining to similarity-based mining. By evaluating item sets based on the similarity of their transaction covers—specifically using the Jaccard index and related measures—the authors introduce a framework that identifies strongly associated items while significantly reducing noise. The proposed JIM (Jaccard Item set Mining) algorithm leverages the anti-monotone property of these measures to ensure computational efficiency.
Introduction
In data mining, identifying sets of items that frequently co-occur in transactions is a foundational task. However, standard metrics like "support" (the frequency of occurrence) are often blunt instruments. Two items may appear together frequently simply because they are individually common, leading to a "sea of irrelevant rules." Conversely, highly correlated but niche items may be missed because they do not meet a global frequency threshold.
Marc Segond and Christian Borgelt address this by proposing Cover Similarity Based Item Set Mining. Instead of asking how often items appear together, this approach asks how similarly they behave across the database.
Methodology
Covers and Carriers
The framework relies on two fundamental concepts regarding a set of items:
- Cover: The set of all transactions containing all items in the set (the intersection).
- Carrier (or Extent): The set of all transactions containing at least one of the items in the set (the union).
The Jaccard Item Set
The primary measure used is the Generalized Jaccard Index. For any given item set, the similarity is calculated as the size of the Cover divided by the size of the Carrier. A high Jaccard index indicates that the items almost always appear together and rarely appear without one another.
Beyond Jaccard, the authors provide a generalized parametric formula that extends to twelve different similarity measures, including Dice, Kulczynski, and Sokal & Sneath coefficients. Notably, they demonstrate that standard frequent item set mining is a special, restricted case of this framework (specifically the Russel & Rao measure).
The JIM Algorithm
To implement this efficiently, the authors developed the JIM (Jaccard Item set Mining) algorithm. JIM is modeled after the vertical mining style of the Eclat algorithm but introduces a novel "extra set" approach. While Eclat uses "diffsets" to track missing transactions, JIM uses "extra sets" to recursively calculate the union (the denominator of the similarity index) as it traverses the search tree.
Crucially, the authors prove that the generalized Jaccard index is anti-monotone. This property is vital for performance: if a set of items fails to meet the similarity threshold, all of its supersets can be safely pruned from the search space.
Experimental Evaluation
The authors evaluated JIM using standard benchmarks (BMS-Webview-1, T10I4D100K, and UCI repository sets) and a real-world text dataset derived from the Wikipedia Selection for Schools (approx. 4,800 pages and 60,000 terms).
Key Findings
- Noise Reduction: On the Wikipedia dataset, traditional FIM produced over 83,000 frequent item sets. By applying a modest Jaccard threshold of 0.1, the JIM algorithm reduced the output to just 5,116 sets—a 94% reduction. The remaining sets represented highly meaningful semantic associations, such as
{phylum, chordata, animalia}. - Discovery of Niche Associations: In the BMS-Webview-1 clickstream data, the method identified highly correlated item sets with support as low as 0.04%. Such patterns are typically impossible to extract with standard FIM, as lowering the support threshold that far would result in millions of junk candidates.
- Computational Efficiency: While JIM tracks two transaction lists per item (increasing overhead compared to Eclat), the experiments show the runtime penalty is manageable. Interestingly, in sparse datasets, JIM performs better when processing items in descending order of frequency, as it allows for more efficient construction of the carrier sets.
Conclusion
Cover similarity-based mining offers a robust alternative to traditional frequency-based methods. By focusing on the Jaccard index and its variants, researchers can filter out statistically expected coincidences and focus on genuine associations. While the computational cost is slightly higher than traditional Eclat, the dramatic reduction in output size and the increased relevance of the discovered patterns make JIM a powerful tool for analyzing complex, sparse datasets.
Summary updated