In many learning problems, the use of feature discretization (FD) techniques attains adequate and compact representations of the data, using less memory, as compared to the original representation. Often, they lead to lower training time, while improving the classification accuracy. Many FD techniques, either unsupervised or supervised, can be found in the literature. In this paper, we extend and improve on previous work, with a new FD method based on the Linde-Buzo-Gray (LBG) algorithm, guided by a relevance criterion. The key advantage of our approach, as compared to previous ones, is that it can work in unsupervised, supervised, and semi-supervised problems, depending on the relevance criterion used used to perform the feature sorting. Experimental results, on standard benchmark datasets with different types of data and learning problems, show the improvement of our method, as compared to other supervised FD approaches.