This article presents a novel approach based on the use of novel patterns called k-relaxed frequent patterns for conceptual clustering. To enumerate these patterns, we use a translation to the SAT problem. Subsequently, we adopt an ILP approach to identify the set of disjoint clusters. Finally, we demonstrate the effectiveness of our approach through several experiments on well-known real transactional datasets.