IGSD: a multi-criteria approach for subgroup discovery using information gain and odds ratio

Abstract The discovery of patterns that accurately discriminate one class label from another remains a challenging data mining task. Subgroup discovery is a technique that tries to find groups of individuals who are statistically different from others in a large data set. Existing approaches make use of beam-search, sampling, and genetic algorithms in order to discover non-redundant pattern sets of high quality with respect to a single pattern quality measure, typically WRAcc (Weighted Relative Accuracy). Additionally, existing approaches require hand tuning of each algorithm’s parameters for each dataset mined. In this work, we propose Information Gained Subgroup Discovery (IGSD), a new SD algorithm for pattern mining that combines Information Gain (IG) and Odds Ratio (OR) as a multi-criteria for non-redundant pattern selection. The proposed method avoids hand tuning of search parameters by automatically and dynamically adjusting threshold values of the multi-criteria search procedure based on the statistical characteristics of an input data set. The combination of IG and OR enables to provide patterns with optimal length and high quality, ensuring in this way, a high diversity and interest of the patterns. Performance has been evaluated comparing patterns found by the proposed method and state-of-the-art algorithms following main paradigms for search space exploration: beam-search, heuristic and genetic algorithm. Performance evaluation indicates that IGSD provides better IG and OR values showing better diversity of each pattern set and a higher dependence between patterns and targets, without degrading other SD metrics, like WRAcc or accuracy. Finally, patterns obtained for one dataset, related with lung cancer patients and treatments, have been validated by a group of domain experts. Thus, patterns provided by IGSD show better agreement with experts than patterns obtained by the rest of methods. The results presented demonstrate the suitability of the proposed IGSD algorithm as a method for high quality pattern discovery.