Binary Classication Tree for Multiclass Classication with Observation-based Clustering

Abstract

Many classification techniques are originally designed to solve a binary problem, but practically many classification problems involve more than two classes. A multiclass problem can be decomposed into binary sub-problems, each solved by a binary classifier. Aside from using one-against-one (OAO) or one-against-all (OAA) decomposition scheme, an ensemble of binary classifiers can be constructed hierarchically. In this study, we focus in multiclass classification with a binary classification tree and propose a new approach in splitting a top-down tree by grouping observations into two clusters with k-mean clustering. Unlike a traditional class-clustering approach, this observation-based algorithm allows one class to appear in two meta-classes so it can be examined in both sub-trees. A data cleaning process is also performed to avoid insignificant tree splits. The experiment shows how our proposed algorithm (BCTOB) performed on different data sets, compared with other binary classification tree algorithms. Then advantages and disadvantages of the algorithm are discussed.