The discovery of patterns that accurately discriminate one class label from
another remains a challenging data mining task. Subgroup discovery (SD) is one
of the frameworks that enables to elicit such interesting hypotheses from
labeled data. A question remains fairly open: How to select an accurate
heuristic search technique when exhaustive enumeration of the pattern space is
infeasible? Existing approaches make use of beam-search, sampling and genetic
algorithms for discovering a pattern set that is non-redundant and of high
quality w.r.t. a pattern quality measure. We argue that such approaches produce
pattern sets that lack of diversity: Only few patterns of high quality, and
different enough, are discovered. Our main contribution is then to formally
define pattern mining as a game and to solve it with Monte Carlo tree search
(MCTS). It can be seen as an exhaustive search guided by random simulations
which can be stopped early (limited budget) by virtue of its best-first search
property. We show through a comprehensive set of experiments how MCTS enables
the anytime discovery of a diverse pattern set of high quality. It outperforms
other approaches when dealing with a large pattern search space and for
different quality measures. Thanks to its genericity, our MCTS settings can be
used for SD but also for many other pattern mining tasks.

通过 Monte Carlo 树搜索算法解决模式挖掘的多样性问题，该算法具有高效性和通用性。