TechPrufer
Get started
Two Sigma
Two Sigma logoTwo Sigma · Feature trail

Subgroup Mining Algorithm

2 posts · Jul 2018 – Oct 2018

What this trail covers

Two Sigma developed MiSoSouP, a scalable algorithm for identifying interesting subgroups within datasets. It leverages statistical learning theory, specifically the concept of pseudodimension, to efficiently approximate subgroup distributions from a small random sample of the data. This approach significantly improves runtime and scalability compared to existing methods, enabling high-quality approximations with a fraction of the data. The algorithm was presented at ACM KDD'18 and invited for submission to the ACM Transactions on Knowledge Discovery from Data (TKDD) journal. This post details the algorithm's formulation, pseudodimension analysis, and empirical evaluation, demonstrating its superiority over state-of-the-art algorithms in terms of speed and quality of subgroup discovery.

All Two Sigma trails
  1. MiSoSouP: Extracting the Most “Flavor” from a DatasetIntroduced MiSoSouP, a novel algorithm for mining interesting subgroups in datasets by leveraging statistical learning theory, specifically pseudodimension, to approximate subgroup distributions from a small random sample. This method significantly improves scalability and runtime compared to existing algorithms, enabling high-quality approximations with reduced data.
  2. MiSoSouP: Mining Interesting Subgroups with Sampling and PseudodimensionThis 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.