Conceptual clustering is a well-studied research area in the field of unsupervised machine learning. It aims to identify disjoint clusters, where each cluster represents a collection of similar transactions described by a common pattern. The first phase of earlier conceptual clustering methods relies on the enumeration of closed patterns. Nevertheless, the extraction of such patterns can be challenging, primarily due to their rigorous nature. Indeed, closed patterns can be not frequent or fail to cover all the transactions within a cluster. To overcome this issue, this paper presents a novel approach based on the relaxation of frequent patterns called k-relaxed frequent patterns. Then, we introduce a propositional satisfiability method for enumerating such patterns. Afterwards, we employ an integer linear programming approach to compute the set of disjoint clusters. Finally, we demonstrate the efficiency of our approach through an extensive experiments conducted on several popular real-life datasets.