On the efficient stability computation for the selection of interesting formal concepts

Abstract The lattice theory under the framework of formal concept analysis has brought mathematical thinking to knowledge representation and discovery. In this respect, this mathematical framework offers a conceptual knowledge representation through the Galois lattice . This hierarchical conceptual structure has been beneficial within the task of knowledge discovery in databases. However, its effective use in large datasets is always limited by the overwhelming number of extracted formal concepts. To select interesting formal concepts, the stability measure can be of valuable help. The dedicated literature has highlighted non-scalable approaches to compute such a stability measure. In an effort to tackle this issue, we introduce the Dfsp algorithm dedicated to efficiently compute the quality measure of the stability of formal concepts. We also show that the stability computation is an instantiation of a larger issue: locating minimal generators given the closed pattern as a reference point. The guiding idea of the Dfsp algorithm is to maximize as far as possible the quantity of the useless search space through the swift localization of maximal non-generator cliques. The experiments performed demonstrate the efficiency of the Dfsp algorithm.