2008 DTreesForHMC

(Vens et al., 2008) ⇒ Celine Vens, Jan Struyf, Leander Schietgat, Sašo Džeroski, Hendrik Blockeel. (2008). “Decision Trees for Hierarchical Multi-label Classification..” In: Machine Learning, 73(2) doi:10.1007/s10994-008-5077-3

Subject Headings: Hierarchical Classification, Multi-label Classification, Decision Trees, Functional Genomics, Precision-recall Analysis

Notes

Cited By

Quotes

Abstract

Hierarchical multi-label classification (HMC) is a variant of classification where instances may belong to multiple classes at the same time and these classes are organized in a hierarchy. This article presents several approaches to the induction of decision trees for HMC, as well as an empirical study of their use in functional genomics. We compare learning a single HMC tree (which makes predictions for all classes together) to two approaches that learn a set of regular classification trees (one for each class). The first approach defines an independent single-label classification task for each class (SC). Obviously, the hierarchy introduces dependencies between the classes. While they are ignored by the first approach, they are exploited by the second approach, named hierarchical single-label classification (HSC). Depending on the application at hand, the hierarchy of classes can be such that each class has at most one parent (tree structure) or such that classes may have multiple parents (DAG structure). The latter case has not been considered before and we show how the HMC and HSC approaches can be modified to support this setting. We compare the three approaches on 24 yeast data sets using as classification schemes MIPS’s FunCat (tree structure) and the Gene Ontology (DAG structure). We show that HMC trees outperform HSC and SC trees along three dimensions: predictive accuracy, model size, and induction

Introduction

Classification refers to the task of learning from a set of classified instances a model that can predict the class of previously unseen instances. Hierarchical multi-label classification (HMC) differs from normal classification in two ways: (1) a single example may belong to multiple classes simultaneously; and (2) the classes are organized in a hierarchy: an example that belongs to some class automatically belongs to all its superclasses (we call this the hierarchy constraint).

Examples of this kind of problems are found in several domains, including text classification (Rousu et al. 2006), functional genomics (Barutcuoglu et al. 2006), and object recognition (Stenger et al. 2007). In functional genomics, which is the application on which we focus, an important problem is predicting the functions of genes. Biologists have a set of possible functions that genes may have, and these functions are organized in a hierarchy (see Fig. 1 for an example). It is known that a single gene may have multiple functions. In order to understand the interactions between different genes, it is important to obtain an interpretable model.

A first approach transforms an HMC task into a separate binary classification task for each class in the hierarchy and applies an existing classification algorithm. We refer to it as the SC (single-label classification) approach. This technique has several disadvantages. First, it is inefficient, because the learner has to be run |C| times, with |C| the number of classes, which can be hundreds or thousands in some applications. Second, it often results in learning from strongly skewed class distributions: in typical HMC applications classes at lower levels of the hierarchy often have very small frequencies, while (because of the hierarchy constraint) the frequency of classes at higher levels tends to be very high. Many learners have problems with strongly skewed class distributions (Weiss and Provost 2003). Third, from the knowledge discovery point of view, the learned models identify features relevant for one class, rather than identifying features with high overall relevance. Finally, the hierarchy constraint is not taken into account, i.e. it is not automatically imposed that an instance belonging to a class should belong to all its superclasses.

A second approach is to adapt the SC method, so that this last issue is dealt with. Some authors have proposed to hierarchically combine the class-wise models in the prediction …

…

References

Rousu, J., Saunders, C., Szedmak, S., & John Shawe Taylor (2006). Kernel-based learning of hierarchical multilabel

classification models. Journal of Machine Learning Research, 7, 1601–1626.

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 DTreesForHMC	Hendrik Blockeel Leander Schietgat Jan Struyf Sašo Džeroski Celine Vens			Decision Trees for Hierarchical Multi-label Classification		Machine Learning (ML) Subject Area	http://www.cs.kuleuven.be/~jan/papers/HMCJRNL.pdf	10.1007/s10994-008-5077-3		2008