Recent work in supervised learning has shown that a surprisingly simple Bayesian classifier with strong assumptions of independence among features, called naive-Bayes, is competitive with state of the art classifiers such as C4.5. This fact raises the question of whether a classifier with less restrictive assumptions can perform even better. In this paper we examine and evaluate approaches for inducing classifiers from data, based on recent results in the theory of learning Bayesian networks. Bayesian networks are factored representations of probability distributions that generalize the naive-Bayes model and explicitly represent statements about independence. Among these approaches we single out a new method, Tree Augmented Naive-Bayes (TAN), which outperforms naive-Bayes, yet at the same time maintains the computational simplicity (no search involved) and robustness which are characteristic of naive-Bayes. We experimentally tested these approaches using benchmark problems from the Irvine repository, and compared them against C4.5, naive-Bayes, and wrapper-based feature selection methods.