MiSoSouP: Mining Interesting Subgroups with Sampling and Pseudodimension

This post introduces MiSoSouP, a novel suite of algorithms for extracting high-quality approximations of the most interesting subgroups from a transactional dataset using sampling. It presents a new formulation of interestingness measures that allows for approximation via sampling and leverages pseudodimension from statistical learning theory to establish an upper bound on the required sample size for high-quality approximations. The evaluation on real datasets shows MiSoSouP outperforms state-of-the-art algorithms and significantly speeds up subgroup discovery compared to analyzing the whole dataset.