Explainable Data Decompositions

Sebastian Dalleiger, Jilles Vreeken

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:

  1. 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.
  2. 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.

Quantitative comparison of DESC against state-of-the-art methods across 17 datasets.

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.

Geographical mapping of components discovered by DISC in the Mammals dataset.

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

Abstract

Our goal is to discover the components of a dataset, characterize why we deem these components, explain how these components are different from each other, as well as identify what properties they share among each other. As is usual, we consider regions in the data to be components if they show significantly different distributions. What is not usual, however, is that we parameterize these distributions with patterns that are informative for one or more components. We do so because these patterns allow us to characterize what is going on in our data as well as explain our decomposition.We define the problem in terms of a regularized maximum likelihood, in which we use the Maximum Entropy principle to model each data component with a set of patterns. As the search space is large and unstructured, we propose the deterministic DISC algorithm to efficiently discover high-quality decompositions via an alternating optimization approach. Empirical evaluation on synthetic and real-world data shows that DISC efficiently discovers meaningful components and accurately characterises these in easily understandable terms.
BibTeX
@inproceedings{dalleiger2020explainable,
  author = {Sebastian Dalleiger and Jilles Vreeken},
  title = {{Explainable Data Decompositions}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5780},
}
Figure