Abstract
Attribute Value Taxonomies (AVT) 
Introduction
An important goal of inductive learning is to generate accurate and compact classifiers from data. In a typical inductive learning scenario, instances to be classified are represented as ordered tuples of attribute values. However, attribute values can be grouped together to reflect assumed or actual similarities among the values in a domain of interest or in the context of a specific application. Such a hierarchical grouping of attribute values yields an attribute value taxonomy (AVT). For example, Figure 1 shows a human-made taxonomy associated with the nominal attribute 'Odor' of the UC Irvine AGARICUS-LEPIOTA mushroom data set [5] . Hierarchical groupings of attribute values (AVT) are quite common in biological sciences. For example, the Gene Ontology Consortium is developing hierarchical taxonomies for describing many aspects of macromolecular sequence, structure, and function [1] . Undercoffer et al. [24] have developed a hierarchical taxonomy which captures the features that are observable or measurable by the target of an attack or by a system of sensors acting on behalf of the target. Several ontologies being developed as part of the Semantic Web related efforts [4] also capture hierarchical groupings of attribute values. Kohavi and Provost [15] have noted the need to be able to incorporate background knowledge in the form of hierarchies over data attributes in electronic commerce applications of data mining.
There are several reasons for exploiting AVT in learning classifiers from data, perhaps the most important being a preference for comprehensible and simple, yet accurate and robust classifiers [18] in many practical applications of data mining. The availability of AVT presents the opportunity to learn classification rules that are expressed in terms of abstract attribute values leading to simpler, easier-tocomprehend rules that are expressed in terms of hierarchically related values. Thus, the rule (odor = pleasant) → (class = edible) is likely to be preferred over
by a user who is familiar with the odor taxonomy shown in Figure 1 .
Another reason for exploiting AVTs in learning classifiers from data arises from the necessity, in many application domains, for learning from small data sets where there is a greater chance of generating classifiers that over-fit the training data. A common approach used by statisticians when estimating from small samples involves shrinkage [7] or grouping attribute values (or more commonly class labels) into bins, when there are too few instances that match any specific attribute value or class label, to estimate the relevant statistics with adequate confidence. Learning algorithms that exploit AVT can potentially perform shrinkage automatically thereby yielding robust classifiers. In other words, exploiting information provided by an AVT can be an effective approach to performing regularization to minimize over-fitting [28] .
Consequently, several algorithms for learning classifiers from AVTs and data have been proposed in the literature. This work has shown that AVTs can be exploited to improve the accuracy of classification and in many instances, to reduce the complexity and increase the comprehensibility of the resulting classifiers [6, 11, 14, 23, 28, 30] . Most of these algorithms exploit AVTs to represent the information needed for classification at different levels of abstraction.
However, in many domains, AVTs specified by human experts are unavailable. Even when a human-supplied AVT is available, it is interesting to explore whether alternative groupings of attribute values into an AVT might yield more accurate or more compact classifiers. Against this background, we explore the problem of automated construction of AVTs from data. In particular, we are interested in AVTs that are useful for generating accurate and compact classifiers.
Learning attribute value taxonomies from data

Learning AVT from data
We describe AVT-Learner, an algorithm for automated construction of AVT from a data set of instances wherein each instance is described by an ordered tuple of N nominal attribute values and a class label.
Let 
. ., T n } denote a set of AVT such that T i is an AVT associated with the attribute A i , and Leaves(T i ) denote a set of all leaf nodes in T i . We define a cut δ i of an AVT T i to be a subset of nodes in T i satisfying the following two properties: (1) For any leaf l ∈ Leaves(T i ), either l ∈ δ i or l is a descendant of a node n ∈ δ i ; and (2) for any two nodes f, g ∈ δ i , f is neither a descendant nor an ancestor of g [12] . For example, {Bad, a, l, s, n} is a cut through the AVT for odor shown in Figure 1 . Note that a cut through T i corresponds to a partition of the values in V i . Let ∆ = {δ 1 , δ 2 , . . .δ n } be a set of cuts associated with AVTs in
The problem of learning AVTs from data can be stated as follows: given a data set
and a measure of dissimilarity (or equivalently similarity) between any pair of values of an attribute, output a set of AVTs T = {T 1 , T 2 , . . ., T n } such that each T i (AVT associated with the attribute A i ) corresponds to a hierarchical grouping of values in V i based on the specified similarity measure.
We use hierarchical agglomerative clustering (HAC) of the attribute values according to the distribution of classes that co-occur with them. Let DM (P (x) ||P (y)) denote a measure of pairwise divergence between two probability distributions P (x) and P (y) where the random variables x and y take values from the same domain. We use the pairwise divergence between the distributions of class labels associated with the corresponding attribute values as a measure of the dissimilarity between the attribute values. The lower the divergence between the class distributions associated with two attributes, the greater is their their similarity. The choice of this measure of dissimilarity between attribute values is motivated by the intended use of the AVT, namely, the construction of accurate, compact, and robust classifiers. If two values of an attribute are indistinguishable from each other with respect to their class distributions, they provide statistically similar information for classification of instances.
The algorithm for learning AVT for a nominal attribute is shown in Figure 2 . The basic idea behind AVT-Learner is to construct an AVT T i for each attribute A i by starting with the primitive values in V i as the leaves of T i and recursively add nodes to T i one at a time by merging two existing nodes. To aid this process, the algorithm maintains a cut δ i through the AVT T i , updating the cut δ i as new nodes are added to T i . At each step, the two attribute values to be grouped together to obtain an abstract attribute value to be added to For each class label c k : estimate the probability p c k |v j i
5.
Let P C|v
be the class distribution associated with value . 6 .
Merge v Calculate probability distribution P (C|v
Update T i by adding nodes v and v In the case of continuous-valued attributes, we define intervals based on observed values for the attribute in the data set. We then generate a hierarchical grouping of adjacent intervals, selecting at each step two adjacent intervals to merge using the pairwise divergence measure. A cut through the resulting AVT corresponds to a discretization of the continuous-valued attribute. A similar approach can be used to generate AVT from ordinal attribute values.
Pairwise divergence measures
There are several ways to measure similarity between two probability distributions. We have tested thirteen divergence measures for probability distributions P and Q. In this paper, we limit the discussion to Jensen-Shannon divergence measure.
Jensen-Shannon divergence [21] is weighted information gain, also called Jensen difference divergence, information radius, Jensen difference divergence, and SibsonBurbea-Rao Jensen Shannon divergence. It is given by: Jensen-Shannon divergence is reflexive, symmetric and bounded. Figure 3 shows an AVT of 'odor' attribute generated by AVT-Learner (with binary clustering).
Evaluation of AVT-Learner
The intuition behind our approach to evaluating the AVT generated by AVT-Learner is the following: an AVT that captures relevant relationships among attribute values can result in the generation of simple and accurate classifiers from data, just as an appropriate choice of axioms in a mathematical domain can simplify proofs of theorems. Thus, the simplicity and predictive accuracy of the learned classifiers based on alternative choices of AVT can be used to evaluate the utility of the corresponding AVT in specific contexts.
AVT guided variants of standard learning algorithms
It is possible to extend standard learning algorithms in principled ways so as to exploit the information provided by AVT. AVT-DTL [26, 30, 28] and the AVT-NBL [29] which extend the decision tree learning algorithm [20] and the Naive Bayes learning algorithm [16] respectively are examples such algorithms.
The basic idea behind AVT-NBL is to start with the Naive Bayes Classifier that is based on the most abstract at- The experiments reported by Zhang and Honavar [29] using several benchmark data sets show that AVT-NBL is able to learn, using human generated AVT, substantially more accurate classifiers than those produced by Naive Bayes Learner (NBL) applied directly to the data sets as well as NBL applied to data sets represented using a set of binary features that correspond to the nodes of the AVT (PROP-NBL). The classifiers generated by AVT-NBL are substantially more compact than those generated by NBL and PROP-NBL. These results hold across a wide range of missing attribute values in the data sets. Hence, the performance of Naive Bayes classifiers generated by AVT-NBL when supplied with AVT generated by the AVTLearner provide useful measures of the effectiveness of AVT-Learner in discovering hierarchical groupings of attribute values that are useful in constructing compact and accurate classifiers from data. Figure 4 shows the experimental setup. The AVT generated by the AVT-Learner are evaluated by comparing the performance of the Naive Bayes Classifiers produced by applying
Experiments

Experimental setup
• NBL to the original data set
• AVT-NBL to the original data set (See Figure 4) .
For the benchmark data sets, we chose 37 data sets from UCI data repository [5] .
Among the data sets we have chosen, AGARICUS-LEPIOTA data set and NURSERY data set have AVT supplied by human experts. AVT for AGARICUS-LEPIOTA data was prepared by a botanist, and AVT for NURSERY data was based on our understanding of the domain. We are not aware of any expert-generated AVTs for other data sets.
In each experiment, we randomly divided each data set into 3 equal parts and used 1/3 of the data for AVT construction using AVT-Learner. The remaining 2/3 of the data were used for generating and evaluating the classifier. Each set of AVTs generated by the AVT-Learner was evaluated in terms of the error rate and the size of the resulting classifiers (as measured by the number of entries in conditional probability tables). The error rate and size estimates were obtained using 10-fold cross-validation on the part of the data set (2/3) that was set aside for evaluating the classifier. The results reported correspond to averages of the 10-fold cross-validation estimates obtained from the three choices of the AVT-construction and AVT-evaluation. This process ensures that there is no information leakage between the data used for AVT construction, and the data used for classifier construction and evaluation.
10-fold cross-validation experiments were performed to evaluate human expert-supplied AVT on the AVT evaluation data sets used in the experiments described above for the AGARICUS-LEPIOTA data set and the NURSERY data set.
We also evaluated the robustness of the AVT generated by the AVT-Learner by using them to construct classifiers from data sets with varying percentages of missing attribute values. The data sets with different percentages of missing values were generated by uniformly sampling from instances and attributes to introduce the desired percentage of missing values.
Results
AVT generated by AVT-Learner are competitive with human-generated AVT when used by AVT-NBL.
The results of our experiments shown in Figure 5 indicate that AVT-Learner is effective in constructing AVTs that are competitive with human expert-supplied AVTs for use in classification tasks with respect to the error rates and the size of the resulting classifiers.
AVT-Learner can generate useful AVT when no humangenerated AVT are available.
For most of the data sets, there are no human-supplied AVT's available. Figure 6 shows the error rate estimates for Naive Bayes classifiers generated by AVT-NBL using AVT generated by the AVT-Learner and the classifiers generated by NBL applied to the DERMATOLOGY data set. The results shown suggest that AVT-Learner, using JensenShannon divergence, is able to generate AVTs that when used by AVT-NBL, result in classifiers that are more accurate than those generated by NBL.
Additional experiments with other data sets produced similar results. Table 1 shows the classifier's accuracy on original UCI data sets for NBL and AVT-NBL that uses AVTs generated by AVT-Learner. 10-fold cross-validation is used for evaluation, and Jensen-Shannon divergence is used for AVT generation. The user-specified number for discretization is 10. Thus, AVT-Learner is able to generate AVTs that are useful for constructing compact and accurate classifiers from data.
AVT generated by AVT-Learner, when used by AVT-NBL, yield substantially more compact Naive Bayes Classifiers than those produced by NBL Naive Bayes classifiers constructed by AVT-NBL generally have smaller number of parameters than those from NBL (See Figures 7 for representative results) . Table 2 shows the classifier size measured by the number of parameters on selected UCI data sets for NBL and AVT-NBL that uses AVTs generated by AVT-Learner.
These results suggest that AVT-Learner is able to group attribute values into AVT in such a way that the resulting AVT, when used by AVT-NBL, result in compact yet accurate classifiers.
Summary and discussion

Summary
In many applications of data mining, there is a strong preference for classifiers that are both accurate and compact [15, 18] . Previous work has shown that attribute value taxonomies can be exploited to generate such classifiers from data [28, 29] . However, human-generated AVTs are • AVT-Learner is effective in generating AVTs that when used by AVT-NBL, a principled extension of the standard algorithm for learning Naive Bayes classifiers, result in classifiers that are substantially more compact (and often more accurate) than those obtained by the standard Naive Bayes Learner (that does not use AVTs).
• The AVTs generated by AVT-Learner are competitive with human supplied AVTs (in the case of benchmark data sets where human-generated AVTs were available) in terms of both the error rate and size of the resulting classifiers.
Discussion
The AVTs generated by AVT-Learner are binary trees. Hence, one might wonder if k-ary AVTs yield better results when used with AVT-NBL. Figure 8 shows an AVT of 'odor' attribute generated by AVT-Learner (with quaternary clustering). Table 3 shows the accuracy of AVT-NBL when k-ary clustering is used by AVT-Learner. It can be seen that AVT-NBL generally works best when binary AVTs are used. It is because reducing internal nodes in AVT-Learner will eventually reduce the search space for possible cuts in AVT-NBL, which leads to generating a less compact classifier.
Related work
Gibson and Kleinberg [10] introduced STIRR, an iterative algorithm based on non-linear dynamic systems for clustering categorical attributes. Ganti et. al. [9] designed CACTUS, an algorithm that uses intra-attribute summaries to cluster attribute values. However, both of them did not make taxonomies and use the generated for improving classification tasks. Pereira et. al. [19] described distributional clustering for grouping words based on class distributions associated with the words in text classification. Yamazaki et al., [26] described an algorithm for extracting hierarchical groupings from rules learned by FOCL (an inductive learning algorithm) [17] and reported improved performance on learning translation rules from examples in a natural language processing task. Slonim and Tishby [21, 22] described a technique (called the agglomerative information bottleneck method) which extended the distributional clustering approach described by Pereira et al. [19] , using Jensen-Shannon divergence for measuring distance between document class distributions associated with words and applied it to a text classification task. Baker and McCallum [3] reported improved performance on text classification using a technique similar to distributional clustering and a distance measure, which upon closer examination, can be shown to be equivalent to Jensen-Shannon divergence [21] .
To the best of our knowledge, there has been little work on the evaluation of techniques for generating hierarchical groupings of attribute values (AVTs) on classification tasks using a broad range of benchmark data sets using algorithms such as AVT-DTL or AVT-NBL that are capable of exploiting AVTs in learning classifiers from data.
Future work
Some directions for future work include:
• Extending AVT-Learner described in this paper to learn AVTs that correspond to tangled hierarchies (which can be represented by directed acyclic graphs (DAG) instead of trees).
• Learning AVT from data for a broad range of real world applications such as census data analysis, text classification, intrusion detection from system log data [13] , learning classifiers from relational data [2] , and protein function classification [25] and identification of protein-protein interfaces [27] .
• Developing algorithms for learning hierarchical ontologies based on part-whole and other relations as opposed to ISA relations captured by an AVT.
• Developing algorithms for learning hierarchical groupings of values associated with more than one attribute.
Acknowledgments


{'paper_id': '1673470', 'title': 'Generation of attribute value taxonomies from data for data-driven construction of accurate and compact classifiers', 's2_url': 'https://api.semanticscholar.org/CorpusID:1673470', 'source': 'S2ORC'}