hide
Free keywords:
Computer Science, Databases, cs.DB,Computer Science, Artificial Intelligence, cs.AI
Abstract:
Subgroup discovery is a local pattern mining technique to find interpretable
descriptions of sub-populations that stand out on a given target variable. That
is, these sub-populations are exceptional with regard to the global
distribution. In this paper we argue that in many applications, such as
scientific discovery, subgroups are only useful if they are additionally
representative of the global distribution with regard to a control variable.
That is, when the distribution of this control variable is the same, or almost
the same, as over the whole data.
We formalise this objective function and give an efficient algorithm to
compute its tight optimistic estimator for the case of a numeric target and a
binary control variable. This enables us to use the branch-and-bound framework
to efficiently discover the top-$k$ subgroups that are both exceptional as well
as representative. Experimental evaluation on a wide range of datasets shows
that with this algorithm we discover meaningful representative patterns and are
up to orders of magnitude faster in terms of node evaluations as well as time.
