Abstract
The aim of this paper is to present a strategy by which a new philosophy for pattern classification, namely that pertaining to Dissimilarity-Based Classifiers (DBCs), can be efficiently implemented. This methodology, proposed by Duin and his co-authors (see [3], [4], [5], [6], [8]), is a way of defining classifiers between the classes, and is not based on the feature measurements of the individual patterns, but rather on a suitable dissimilarity measure between them. The problem with this strategy is, however, the need to compute, store and process the inter-pattern dissimilarities for all the training samples, and thus, the accuracy of the classifier designed in the dissimilarity space is dependent on the methods used to achieve this. In this paper, we suggest a novel strategy to enhance the computation for all families of DBCs. Rather than compute, store and process the DBC based on the entire data set, we advocate that the training set be first reduced into a smaller representative subset. Also, rather than determine this subset on the basis of random selection, or clustering etc., we advocate the use of a Prototype Reduction Scheme (PRS), whose output yields the points to be utilized by the DBC. Apart from utilizing PRSs, in the paper we also propose simultaneously employing the Mahalanobis distance as the dissimilarity-measurement criterion to increase the DBC’s classification accuracy. Our experimental results demonstrate that the proposed mechanism increases the classification accuracy when compared with the “conventional” approaches for samples involving real-life as well as artificial data sets.
The work of the second author was done while visiting at Myongji University, Yongin, Korea. The second author was partially supported by NSERC, the Natural Sciences and Engineering Research Council of Canada and a grant from the Korean Research Foundation. This work was generously supported by the Korea Research Foundation Grant funded by the Korea Government (MOEHRD-KRF-2005-042-D00265).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fukunaga, K.: Introduction to Statistical Pattern Recognition, 2nd edn. Academic Press, San Diego (1990)
Jain, A.K., Duin, R.P.W., Mao, J.: Statistical pattern recognition: A review. IEEE Trans. Pattern Anal. and Machine Intell. PAMI-22(1), 4–37 (2000)
Duin, R.P.W., Ridder, D., Tax, D.M.J.: Experiments with a featureless approach to pattern recognition. Pattern Recognition Letters 18, 1159–1166 (1997)
Duin, R.P.W., Pekalska, E., de Ridder, D.: Relational discriminant analysis. Pattern Recognition Letters 20, 1175–1181 (1999)
Pekalska, E., Duin, R.P.W.: Dissimilarity representations allow for buillding good classifiers. Pattern Recognition Letters 23, 943–956 (2002)
Pekalska, E.: Dissimilarity representations in pattern recognition. Concepts, theory and applications, Ph.D. thesis, Delft University of Technology, Delft, The Netherlands (2005)
Horikawa, Y.: On properties of nearest neighbor classifiers for high-dimensional patterns in dissimilarity-based classification. IEICE Trans. Information & Systems J88-D-II(4), 813–817 (2005) (in Japanese)
Pekalska, E., Duin, R.P.W., Paclik, P.: Prototype selection for dissimilarity-based classifiers. Pattern Recognition 39, 189–208 (2006)
Bezdek, J.C., Kuncheva, L.I.: Nearest prototype classifier designs: An experimental study. International Journal of Intelligent Systems 16(12), 1445–11473 (2001)
Dasarathy, B.V.: Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society Press, Los Alamitos (1991)
Hart, P.E.: The condensed nearest neighbor rule. IEEE Trans. Inform. Theory IT-14, 515–516 (1968)
Fukunaga, K., Mantock, J.M.: Nonparametric data reduction. IEEE Trans. Pattern Anal. and Machine Intell. PAMI-6(1), 115–118 (1984)
Chang, C.L.: Finding prototypes for nearest neighbor classifiers. IEEE Trans. Computers C-23(11), 1179–1184 (1974)
Bezdek, J.C., Reichherzer, T.R., Lim, G.S., Attikiouzel, Y.: Multiple-prototype classifier design. IEEE Trans. Systems, Man, and Cybernetics - Part C SMC-28(1), 67–79 (1998)
Burges, C.J.C.: A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery 2(2), 121–167 (1998)
Kohonen, T.: Self-Oganizing Maps. Springer, Berlin (1995)
Kim, S.-W., Oommen, B.J.: On Optimizing Dissimilarity-based Classification Using Prototype Reduction Schemes (unabridged version of this paper)
Kim, S.-W., Oommen, B.J.: Enhancing prototype reduction schemes with LVQ3-type algorithms. Pattern Recognition 36(5), 1083–1093 (2003)
Kim, S.-W., Oommen, B.J.: A Brief Taxonomy and Ranking of Creative Prototype Reduction Schemes. Pattern Analysis and Applications Journal 6(3), 232–244 (2003)
Kim, S.-W., Oommen, B.J.: Enhancing Prototype Reduction Schemes with Recursion: A Method Applicable for “Large” Data Sets. IEEE Trans. Systems, Man, and Cybernetics - Part B SMC-34(3), 1384–1397 (2004)
Kim, S.-W., Oommen, B.J.: On using prototype reduction schemes to optimize kernel-based nonlinear subspace methods. Pattern Recognition 37(2), 227–239 (2004)
Kim, S.-W., Oommen, B.J.: On using prototype reduction schemes and classifier fusion strategies to optimize kernel-based nonlinear subspace methods. IEEE Transactions on Pattern Analysis and Machine Intelligence 27(3), 455–460 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, SW., Oommen, B.J. (2006). On Optimizing Dissimilarity-Based Classification Using Prototype Reduction Schemes. In: Campilho, A., Kamel, M.S. (eds) Image Analysis and Recognition. ICIAR 2006. Lecture Notes in Computer Science, vol 4141. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11867586_2
Download citation
DOI: https://doi.org/10.1007/11867586_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44891-4
Online ISBN: 978-3-540-44893-8
eBook Packages: Computer ScienceComputer Science (R0)