Skip to main content
Back

OCCM Slashes Explainable Clustering Time by 3x Without Losing Accuracy

A new filtering strategy for explainable clustering cuts redundant symbolic patterns, slashing ILP solve times by up to 5x while preserving or improving cluster quality.

Paper, Full Access
  • OCCM filters redundant k-Relaxed Frequent Patterns that induce identical covers in explainable clustering.
  • Formal proof: distinct k-RFPs sharing a cover number exactly binomial(|R|, k) for a specific structure.
  • Pattern reduction reaches 26.67% on Tic-tac-toe; ILP solve time on Vote drops from 1206s to 234s.
  • F1-score on Mushroom jumps from 0.34 to 0.73 by keeping the largest representative pattern per cover.
  • New Shapley-based SVV and ACS measures quantify item contribution and cluster robustness under item removal.
  • Extends prior ECAI 2024 CCA-k-RFP-M1 pipeline; no public code released with the paper.

Explainable clustering promises something classic k-means never delivers: partitions that come with a human-readable rulebook. Each cluster is described by an actual set of features, not a centroid floating in high-dimensional space. Building those descriptions is combinatorially painful, and a new paper called OCCM (Optimized Conceptual Clustering Method) targets a specific, expensive form of waste in the pipeline: symbolic patterns that look different on paper but describe the exact same cluster.

Conceptual clustering represents each data point with Boolean-valued items and partitions the dataset into disjoint groups, where each group is explicitly described by an itemset rather than an implicit similarity measure or centroid. That symbolic description is what makes the approach appealing for knowledge discovery, but it also forces the algorithm to enumerate candidate patterns and then pick a covering subset, which is NP-hard.

Where the redundancy sneaks in

The state-of-the-art pipeline from ECAI 2024 introduced k-Relaxed Frequent Patterns (k-RFPs), which loosen strict coverage by allowing a transaction to be covered by a pattern even when up to k of the pattern's items are missing from that transaction. Candidates are enumerated with a SAT solver, then an Integer Linear Program picks the final partition.

The catch: with classical closed itemsets, two distinct patterns always cover different transactions. Once you relax to k-covers, that guarantee dies. Multiple distinct k-RFPs can share the same k-cover, and when that happens often, a large number of unnecessary itemsets get generated and processed by the ILP solver, inflating computational time.