In this paper, we present a novel interactive data mining method for extracting classification rules. It combines interactive multi-criteria preference learning based on the Choquet integral with guided exploration of the rule space through an MCMC sampling technique. This approach efficiently identifies pairs of rules with the highest uncertainty, which are then presented to the user for comparison. We investigate the convergence properties of the associated Markov chain and show that, under certain conditions, the probability of sampling a rule increases in proportion to its score. Experiments on UCI datasets demonstrate that our method converges more rapidly to relevant rules when compared to the technique presented in (Vernerey et al., 2024).