Towards Polynomial Subgroup Discovery by Means of FCA
The goal of subgroup discovery is to find groups of objectsthat are significantly different than “average” object w.r.t. some super-vised information. It is a computational intensive procedure that tra-verses a large searching space corresponding to the set of formal con-cepts. It was recently found that a part of formal concepts, called stableconcepts, can be found in polynomial time. Accordingly, in this paper anew algorithm, calledSD-SOFIA, is presented.SD-SOFIAfits subgroup dis-covery process in the framework of stable concept search. The proposedalgorithm is evaluated on a dataset from UCI repository. It is shown thatits practical computational complexity is polynomial.