Binary Classification Tree with Tuned Observation-based Clustering

Authors: Maythapolnun Athimethphat, Boontarika Lerteerawong

Abstract:

There are several approaches for handling multiclass classification. Aside from one-against-one (OAO) and one-against-all (OAA), hierarchical classification technique is also commonly used. A binary classification tree is a hierarchical classification structure that breaks down a k-class problem into binary sub-problems, each solved by a binary classifier. In each node, a set of classes is divided into two subsets. A good class partition should be able to group similar classes together. Many algorithms measure similarity in term of distance between class centroids. Classes are grouped together by a clustering algorithm when distances between their centroids are small. In this paper, we present a binary classification tree with tuned observation-based clustering (BCT-TOB) that finds a class partition by performing clustering on observations instead of class centroids. A merging step is introduced to merge any insignificant class split. The experiment shows that performance of BCT-TOB is comparable to other algorithms.

Keywords: multiclass classification, hierarchical classification, binary classification tree, clustering, observation-based clustering

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057485

References:

[1] G. Ou, Y. L. Murphey and L. Feldkamp, "Multiclass Pattern Classification Using Neural Networks," in 17th International Conference on Pattern Recognition (ICPR'04), vol. 4, J. Kittler, M. Petrou, and M. Nixon, Eds. Cambridge: IEEE Computer Society Press, 2004, pp. 1051-4651.
[2] D. Tax and R. Duin, "Using Two-class Classifiers for Multiclass Classification," in Proceedings of the 16th International Conference on Pattern Recognition, vol. 2, 2002, pp. 124-127.
[3] S. Kumar, J. Ghosh and M. M. Crawford, "Hierarchical Fusion of Multiple Classifiers for Hyperspectral Data Analysis," in Pattern Analysis & Applications, vol. 5, no. 2. London: Springer London, 2002, pp. 210-220.
[4] A. Beygelzimer, J. Langford and P. Ravikumar, "Multiclass Classification with Filter Trees," June 2007. (Online). Available: http://hunch.net/~jl/projects/reductions/mc_to_b/invertedTree.pdf.
[5] J. C. Platt, N. Cristianini and J. Shawe-Taylor, "Large Margin DAGs for Multiclass Classification," in Advances in Neural Information Processing Systems, vol. 12, S.A. Solla, T.K. Leen, K.R. Muller, Eds. Cambridge: MIT Press, 2000, pp. 547-553.
[6] A. Ramanan, S. Suppharangsan and M. Niranjan, "Unbalanced Decision Trees for Multi-class Classification," in Second International Conference on Industrial and Information Systems (ICIIS 2007), Penadeniya, Sri Lanka, 2007.
[7] L. Dong, E. Frank, and S. Kramer, "Ensembles of Balanced Nested Dichotomies for Multi-Class Problems," in Knowledge Discovery in Databases: PKDD 2005, vol. 3721, A. M. Jorge, et la., Eds. New York: Springer-Verlag, pp.84-95.
[8] H. Lei and V. Govindaraju, "Half-Against-Half Multi-class Support Vector Machines," in Multiple Classifier Systems, vol. 3541, N. C. Oza, et la., Eds. New York: Springer-Verlag, 2005, pp. 156-164.
[9] G. Madzarov, D. Gjorgjevikj and I. Chorbev, "A Multi-class SVM Classifier Utilizing Binary Decision Tree," in Informatica, vol. 33, no. 2, S. Lian, D. Kanellopoulos, and G.J. Ruffo, Eds. Ljubljana, Slovenia: Slovenian Society Informatika, 2008, pp. 233-241.
[10] J. Lee and I. Oh, "Binary Classification Trees for Multi-class Classification Problems," in The Seventh International Conference on Document Analysis and Recognition. A. Antonacopoulos, Ed. Edinburgh, Scotland: IEEE Computer Society Press, 2003, pp. 770-774.
[11] R. Tibshirani, T. Hastie, "Margin Trees for High-dimensional Classification," in Journal of Machine Learning Research, vol. 8, S. Džeroski, P. Geurts, and J. Rousu, Eds. Brookline, MA: Microtome Publishing, 2007, pp. 637-652.
[12] R. Kothari and D. Pitts, "On finding the number of clusters," in Pattern Recognition Letters, vol. 20, no. 4. New York: Elsevier Science, 1999, pp. 405-416.
[13] A. Frank and A. Asuncion, UCI Machine Learning Repository, 2010. (Online) http://archive.ics.uci.edu/ml.