# Robust subgroup discovery

arXiv: https://arxiv.org/abs/2103.13686 · HTML: https://mlsanity.com/paper/2103.13686/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 112 references that are in the map.
- First posted on arXiv 25 Mar 2021.

## Builds on (most cited first, 15 of 15)

- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Scalable Bayesian Rule Lists](https://mlsanity.com/paper/1602.08610/) (2016)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Minimum Description Length Revisited](https://mlsanity.com/paper/1908.08484/) (2019)
- [Interpretable multiclass classification by MDL-based rule lists](https://mlsanity.com/paper/1905.00328/) (2019)
- [The Minimum Description Length Principle for Pattern Mining: A Survey](https://mlsanity.com/paper/2007.14009/) (2020)
- [Identifying Consistent Statements about Numerical Data with Dispersion-Corrected Subgroup Discovery](https://mlsanity.com/paper/1701.07696/) (2017)
- [A Tutorial on Statistically Sound Pattern Discovery](https://mlsanity.com/paper/1709.03904/) (2017)
- [Better Short than Greedy: Interpretable Models through Optimal Rule Boosting](https://mlsanity.com/paper/2101.08380/) (2021)
- [Anytime Discovery of a Diverse Set of Patterns with Monte Carlo Tree Search](https://mlsanity.com/paper/1609.08827/) (2016)
- [Discovering Reliable Causal Rules](https://mlsanity.com/paper/2009.02728/) (2020)
- [Subjectively Interesting Subgroup Discovery on Real-valued Targets](https://mlsanity.com/paper/1710.04521/) (2017)
- [Discovering outstanding subgroup lists for numeric targets using MDL](https://mlsanity.com/paper/2006.09186/) (2020)
- [Mint: MDL-based approach for Mining INTeresting Numerical Pattern Sets](https://mlsanity.com/paper/2011.14843/) (2020)
- [Specious rules: an efficient and effective unifying method for removing misleading and uninformative patterns in association rule mining](https://mlsanity.com/paper/1709.03915/) (2017)

## Built on by (most cited first, 4 of 4)

- [EsmamDS: A more diverse exceptional survival model mining approach](https://mlsanity.com/paper/2109.02610/) (2021)
- [Using Constraints to Discover Sparse and Alternative Subgroup Descriptions](https://mlsanity.com/paper/2406.01411/) (2024)
- [A new algorithm for Subgroup Set Discovery based on Information Gain](https://mlsanity.com/paper/2307.15089/) (2023)
- [Data is Moody: Discovering Data Modification Rules from Process Event Logs](https://mlsanity.com/paper/2312.14571/) (2023)

## Abstract (arXiv)

We introduce the problem of robust subgroup discovery, i.e., finding a set of interpretable descriptions of subsets that 1) stand out with respect to one or more target attributes, 2) are statistically robust, and 3) non-redundant. Many attempts have been made to mine either locally robust subgroups or to tackle the pattern explosion, but we are the first to address both challenges at the same time from a global modelling perspective. First, we formulate the broad model class of subgroup lists, i.e., ordered sets of subgroups, for univariate and multivariate targets that can consist of nominal or numeric variables, including traditional top-1 subgroup discovery in its definition. This novel model class allows us to formalise the problem of optimal robust subgroup discovery using the Minimum Description Length (MDL) principle, where we resort to optimal Normalised Maximum Likelihood and Bayesian encodings for nominal and numeric targets, respectively. Second, finding optimal subgroup lists is NP-hard. Therefore, we propose SSD++, a greedy heuristic that finds good subgroup lists and guarantees that the most significant subgroup found according to the MDL criterion is added in each iteration. In fact, the greedy gain is shown to be equivalent to a Bayesian one-sample proportion, multinomial, or t-test between the subgroup and dataset marginal target distributions plus a multiple hypothesis testing penalty. Furthermore, we empirically show on 54 datasets that SSD++ outperforms previous subgroup discovery methods in terms of quality, generalisation on unseen data, and subgroup list size.