Abstract
Traditional clustering methods often lack interpretability, providing groupings without explaining the underlying features that define them. This paper presents DISC, an algorithm for explainable data decomposition that simultaneously partitions datasets and identifies succinct, characteristic pattern sets for each component. By leveraging the Maximum Entropy principle and the Bayesian Information Criterion (BIC), DISC discovers statistically significant data structures and their associated explanations. Empirical evaluations on synthetic and real-world datasets demonstrate that DISC is orders of magnitude faster than existing methods while providing more concise and interpretable results.
Introduction
Clustering is a fundamental task in data science, yet popular algorithms like k-means or DBSCAN often operate as "black boxes," offering little insight into why specific data points are grouped together. Explainable Data Decomposition aims to bridge this gap by jointly discovering data partitions and the "pattern composition"—the sets of informative patterns that describe both the similarities and differences between groups.
For instance, in a retail context, such a method would not only group customers but also identify that one group is characterized by "pasta and ketchup" purchases while another favors "fresh ingredients," even if both share a common interest in "pizza and beer." The goal is to provide a "why" behind data clusters, offering a more interpretable alternative to traditional distance-based clustering methods.
Methodology
The proposed approach frames data decomposition as a regularized maximum likelihood task based on two main pillars:
- The Maximum Entropy Principle: This principle is used to model the distribution of data components, ensuring the model satisfies observed pattern frequencies without introducing additional bias.
- Model Selection via BIC: The Bayesian Information Criterion (BIC) is employed to penalize complexity, favoring the most succinct set of patterns that accurately describes the data to ensure results are human-readable.
To navigate the computationally intensive search space (which is NP-hard and PP-hard), the authors introduce two intertwined algorithms:
- DESC: A fast heuristic-driven method to find high-quality informative patterns for a fixed partitioning. It uses a clever lower-bound heuristic to avoid expensive calculations.
- DISC: A top-down "master" algorithm that iteratively splits the dataset into components based on significant differences in pattern distributions, measured via Jensen-Shannon (JS) divergence.
Results and Discussion
Quantitative analysis across 17 real-world datasets shows that DESC is remarkably efficient. On average, it requires less than 16% of the runtime of SLIM and only 0.24% of the runtime of MTV (a previous state-of-the-art method), while achieving comparable or superior likelihood scores.
Crucially, while older methods often return thousands of patterns, DESC and DISC typically find only tens of patterns, significantly enhancing human readability. This conciseness is achieved without sacrificing the statistical rigor of the model, which incorporates Bonferroni correction to avoid discovering spurious noise-based components.
In a qualitative case study using the Mammals dataset (presence records of 124 European mammals in 50x50km grid cells), DISC discovered 9 components. When mapped geographically, these components aligned almost perfectly with known ecological habitats—such as Scandinavian and Iberian regions—despite the algorithm having no access to spatial coordinates. It identified these regions purely by analyzing which species co-occurred.
Conclusion
While currently optimized for binary transactional data, DISC represents a significant step toward interpretable unsupervised learning. By explicitly identifying shared versus unique patterns, the method provides a nuanced view of data relationships that traditional clustering misses. Future research directions include extending the underlying distribution model to accommodate continuous or categorical data and integrating these algorithms into interactive data exploration tools.
Summary updated