Binary Classification Tree with Tuned Observation-based Clustering
Authors: Maythapolnun Athimethphat, Boontarika Lerteerawong
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.1057485Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1601
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 A. Frank and A. Asuncion, UCI Machine Learning Repository, 2010. (Online) http://archive.ics.uci.edu/ml.