Improving Parallel Exhaustive Subgroup Discovery with Early Search Space Pruning

In this digital era, vast amounts of data are generated from various applications, necessitating robust data mining algorithms to extract valuable insights. Subgroup discovery (SD) [1] is a widely used supervised descriptive data mining method that aims to find interesting subgroups of individuals (samples, objects) with high associations to a target property of interest. However, SD faces two major challenges. The first is the high computational expense of exploring the combinatorial search space of subgroups. Second, when testing multiple subgroups to identify a few significant associations, ensuring that each subgroup meets a quality threshold is not enough to control the occurrence of false positives. The latter issue has been addressed recently with permutation testing while for the former, exploring the search space of closed subgroups instead of all possible subgroups reduces the search space without loss of information. Pellegrina et al. [2] incorporated both these approaches and provided a sequential implementation TopKWY for discovering the top-k significant subgroups while controlling false discoveries. It is considered state-of-the-art. However, its huge computational requirement of assessing patterns against many permutations raises scalability concerns, while the specific optimizations in its algorithm for computing p-values do not generalize to other quality functions. Jyoti et al. [3] addressed both these concerns in their proposed framework ParaDiS . The algorithm of ParaDiS is parallel and distributed, employs efficient communication mechanisms for load sharing and generalizes to other quality functions. However, ParaDiS uses exhaustive search and therefore, suffers from performance bottlenecks. The existing heuristic techniques in SD neither control false discoveries nor consider the search space of closed subgroups. Further, these heuristics can miss potentially interesting subgroups w.r.t. quality.