Hierarchical Decomposition of Multiclass Problems

Summary

---

Several popular Machine Learning techniques are originally designed for the solution of two-class problems. However, several classification problems have more than two classes. One approach to deal with multiclass problems using binary classifiers is to decompose the multiclass problem into multiple binary sub-problems disposed in a binary tree. This approach requires a binary partition of the classes for each node of the tree, which defines the tree structure. This paper presents two algorithms to determine the tree structure taking into account information collected from the used dataset. This approach allows the tree structure to be determined automatically for any multiclass dataset.

See the full content of this document

Extract

---

Hierarchical Decomposition of Multiclass Problems

(ProQuest: ... denotes formulae omitted.)

1. Introduction

Multiclass classification using Machine Learning (ML) [1] techniques consists of inducing a function ... from a dataset composed of pairs ... where ... is a training data and y^sub i^ represents its class. The labels y^sub i^ are in the set {1 , . . . , k}, where k is the number of classes in the problem. A large number of learning techniques, like the Support Vector Machines (SVMs) [2], are originally restricted to binary classification problems, where k = 2.

Two approaches have been adopted in the literature to deal with multiclass problems using binary classifiers: adaptation of the internal operations of the classifier training algorithm and decomposition of the multiclass problem into a set of two-class classification problems. This paper follows the second approach.

Among the decomposition approaches, the most frequently used are one-against-all (OAA), which generates k binary problems, each discriminating one class from the remaining classes, one-against-one (OAO) [3, 4], which produces ... binary classification problems, discriminating between all pairs of classes and error correcting output codes (ECOC) [5], which encodes the classes by error correcting binary vectors.

Alternative strategy is to construct a hierarchical binary decomposition of the problem. The idea is to perform general discriminations first, which are successively refined until the final classification.

According to this strategy, the binary predictors and the problem classes are represented as nodes in a graph or tree. In this representation, the root node usually contains a predictor that divides all problem classes into two groups. These groups are recursively divided into two parts each, until one unique class remains. In the end, the classes are contained in leaf nodes.

The hierarchical structure adopted may influence the quality of the solution obtained for the multiclass problem. Therefore, the selection of the binary parti...

See the full content of this document

---