Attribute value taxonomies (AVT) have been shown to be useful in constructing compact, robust, and comprehensible classifiers. However, in many application domains, human-designed AVTs are unavailable. We introduce AVT-learner, an algorithm for automated construction of attribute value taxonomies from data. AVT-learner uses hierarchical agglomerative clustering (HAC) to cluster attribute values based on the distribution of classes that co-occur with the values. We describe experiments on UCI data sets that compare the performance of AVT-NBL (an AVT-guided naive Bayes learner) with that of the standard naive Bayes learner (NBL) applied to the original data set. Our results show that the AVTs generated by AVT-learner are competitive with human-gene rated AVTs (in cases where such AVTs are available). AVT-NBL using AVTs generated by AVT-learner achieves classification accuracies that are comparable to or higher than those obtained by NBL; and the resulting classifiers are significantly more compact than those generated by NBL.

In many application domains, there is a need for learning algorithms that can effectively exploit attribute value taxonomies (AVT) - hierarchical groupings of attribute values - to learn compact, comprehensible, and accurate classifiers from data - including data that are partially specified. This paper describes AVT-NBL, a natural generalization of the naive Bayes learner (NBL), for learning classifiers from AVT and data. Our experimental results show that AVT-NBL is able to generate classifiers that are substantially more compact and more accurate than those produced by NBL on a broad range of data sets with different percentages of partially specified values. We also show that AVT-NBL is more efficient in its use of training data: AVT-NBL produces classifiers that outperform those produced by NBL using substantially fewer training examples.