Optimal discovery of data groups balancing size and difference
Optimal Subgroup Discovery at Every Support Threshold
Machine Learning
Summary
Finding interesting groups in data is hard because small groups can look very different but might not be meaningful, while big groups are stable but less surprising. The paper explains how to find the best groups that stand out at any chosen size by breaking the problem into manageable parts. The authors show that you only need to consider whole or partial small parts of the data called atoms to find the best groups. They also provide a practical method that works well on many datasets and can improve existing group-finding methods.
What this means in practice
- •For marketing analysts: Identify customer groups that show unusual buying patterns reliably at different group sizes to tailor marketing strategies.
- •For healthcare data teams: Detect patient subpopulations that differ significantly in outcomes within specified minimum group sizes for targeted interventions.
Authors
Lincen Yang, Qi Huang, Niki van Stein, Thomas Bäck, Matthijs van Leeuwen, Zhong Li
Abstract
Subgroup discovery aims to identify regions of the feature space where a target variable deviates from its marginal distribution. A fundamental challenge in this problem is the trade-off between a subgroup's deviation and its support: small subgroups can be highly deviating but statistically meaningless, while large ones cannot deviate much by construction. Existing methods tackle this challenge by collapsing the two into a single scalar quality measure, implicitly committing to one particular trade-off and making it difficult to recover the most deviating subgroup under a user-specified support constraint. We instead provide the first theoretical and structural characterization of optimal subgroups with maximum Kullback-Leibler (KL) divergence under arbitrary support constraints. Under a partition-based generative model, where the feature space decomposes into regions of homogeneous conditional distributions of the target variable called atoms, we prove that every point on the deviation-support Pareto front is a union of whole atoms together with at most one fractional atom. This reduces an uncountable search to a finite combinatorial problem. Guided by this theory, we propose a simple two-step recipe: learn a homogeneous partition, then select atoms greedily. Across 19 benchmark datasets, it finds the most deviating subgroups at a range of support thresholds, and reliably improves subgroups returned by existing methods when applied as a post-processing step. These results empirically validate the sufficiency and necessity of our theoretical contributions.