Experimental study on prototype optimisation algorithms for prototype-based classification in vector spaces. (English) Zbl 1097.68619
Summary: Prototype-based classification relies on the distances between the examples to be classified and carefully chosen prototypes. A small set of prototypes is of interest to keep the computational complexity low, while maintaining high classification accuracy. An experimental study of some old and new prototype optimisation techniques is presented, in which the prototypes are either selected or generated from the given data. These condensing techniques are evaluated on real data, represented in vector spaces, by comparing their resulting reduction rates and classification performance.Usually the determination of prototypes is studied in relation with the nearest neighbour rule. We will show that the use of more general dissimilarity-based classifiers can be more beneficial. An important point in our study is that the adaptive condensing schemes here discussed allow the user to choose the number of prototypes freely according to the needs. If such techniques are combined with linear dissimilarity-based classifiers, they provide the best trade-off of small condensed sets and high classification accuracy.
MSC:
| 68T10 | Pattern recognition, speech recognition |
| 68T05 | Learning and adaptive systems in artificial intelligence |
Keywords:
dissimilarity representation; prototype selection; adaptive condensing; EM algorithm; normal density based classifier; nearest neighbour ruleReferences:
| [1] | Wilson, D. L., Asymptotic properties of nearest neighbor rules using edited data sets, IEEE Trans. Syst. Man Cybern., 2, 408-421 (1972) · Zbl 0276.62060 |
| [2] | Aha, D. W.; Kibler, D.; Albert, M. K., Instance-based learning algorithms, Mach. Learn., 6, 1, 37-66 (1991) |
| [3] | Dasarathy, B. V., Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques (1990), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA |
| [4] | Devijver, P. A.; Kittler, J., Pattern Recognition: A Statistical Approach (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0476.68057 |
| [5] | Wilson, D. R.; Martinez, T. R., Reduction techniques for instance-based learning algorithms, Mach. Learn., 38, 3, 257-286 (2000) · Zbl 0954.68126 |
| [6] | Dasarathy, B. V., Minimal consistent subset (MCS) identification for optimal nearest neighbor decision systems design, IEEE Trans. Syst. Man Cybern., 24, 511-517 (1994) |
| [7] | Hart, P. E., The condensed nearest neighbor rule, IEEE Trans. Inform. Theory, 14, 5, 505-516 (1968) |
| [8] | Tomek, I., Two modifications of CNN, IEEE Trans. Syst. Man Cybern., 6, 769-772 (1976) · Zbl 0341.68066 |
| [9] | Toussaint, G. T.; Bhattacharya, B. K.; Poulsen, R. S., The application of voronoi diagrams to nonparametric decision rules, (Billard, L., Computer Science and Statistics: The Interface (1985), Elsevier Science: Elsevier Science Amsterdam) |
| [10] | M.C. Ainslie, J.S. Sánchez, Space partitioning for instance reduction in lazy learning algorithms, Second Workshop on Integration and Collaboration Aspects of Data Mining, Decision Support and Meta-Learning, 2002, pp. 13-18.; M.C. Ainslie, J.S. Sánchez, Space partitioning for instance reduction in lazy learning algorithms, Second Workshop on Integration and Collaboration Aspects of Data Mining, Decision Support and Meta-Learning, 2002, pp. 13-18. |
| [11] | Chang, C. L., Finding prototypes for nearest neighbor classifiers, IEEE Trans. Comput., 23, 1179-1184 (1974) · Zbl 0292.68044 |
| [12] | Chen, C. H.; Józwik, A., A sample set condensation algorithm for the class sensitive artificial neural network, Pattern Recognition Lett., 17, 819-823 (1996) |
| [13] | Kohonen, T., Self-Organizing Maps (1995), Springer: Springer Berlin |
| [14] | M. Lozano, J.S., Sánchez, F. Pla, Using the geometrical distribution of prototypes for training set condensing, in: R. Conejo, M. Urretavizcaya, J.L. Pérez de la Cruz (Eds.), Current Topics in Artificial Intelligence, Lecture Notes in Artificial Intelligence, vol. 3040, Springer, Berlin, 2004, 618-627.; M. Lozano, J.S., Sánchez, F. Pla, Using the geometrical distribution of prototypes for training set condensing, in: R. Conejo, M. Urretavizcaya, J.L. Pérez de la Cruz (Eds.), Current Topics in Artificial Intelligence, Lecture Notes in Artificial Intelligence, vol. 3040, Springer, Berlin, 2004, 618-627. |
| [15] | M. Lozano, J.M. Sotoca, J.S. Sánchez, F. Pla, An adaptive condensing algorithm based on mixtures of Gaussians, in: J. Vitrià et al. (Eds.), Setè Congrés Català d’Intel.ligencia Artificial, Barcelona (Spain), Frontiers in Artificial Intelligence and Applications, vol. 113, IOS Press, Amsterdam, 2004, pp. 225-232.; M. Lozano, J.M. Sotoca, J.S. Sánchez, F. Pla, An adaptive condensing algorithm based on mixtures of Gaussians, in: J. Vitrià et al. (Eds.), Setè Congrés Català d’Intel.ligencia Artificial, Barcelona (Spain), Frontiers in Artificial Intelligence and Applications, vol. 113, IOS Press, Amsterdam, 2004, pp. 225-232. · Zbl 1069.68085 |
| [16] | Pękalska, E.; Duin, R. P.W.; Paclík, P., Prototype selection for dissimilarity-based classifiers, Pattern Recognition, 39, 2, 189-208 (2006) · Zbl 1080.68646 |
| [17] | Pękalska, E.; Duin, R. P.W., The Dissimilarity Representation for Pattern Recognition. Foundations and Applications (2005), World Scientific: World Scientific Singapore · Zbl 1095.68105 |
| [18] | P. Paclík, R.P.W. Duin, Classifying spectral data using relational representation, Spectral Imaging Workshop, Graz, Austria, 2003.; P. Paclík, R.P.W. Duin, Classifying spectral data using relational representation, Spectral Imaging Workshop, Graz, Austria, 2003. |
| [19] | Paclík, P.; Duin, R. P.W., Dissimilarity-based classification of spectra: computational issues, Real Time Imaging, 9, 4, 237-244 (2003) |
| [20] | Pękalska, E.; Duin, R. P.W., Dissimilarity representations allow for building good classifiers, Pattern Recognition Lett., 23, 8, 943-956 (2002) · Zbl 1015.68160 |
| [21] | Pękalska, E.; Paclík, P.; Duin, R. P.W., A generalized kernel approach to dissimilarity based classification, J. Mach. Learn. Res., 2, 2, 175-211 (2002) · Zbl 1037.68127 |
| [22] | Cover, T. M.; Hart, P. E., Nearest neighbor pattern classification, IEEE Trans. Inform. Theory, 13, 1, 21-27 (1967) · Zbl 0154.44505 |
| [23] | Sánchez, J. S.; Pla, F.; Ferri, F. J., On the use of neighbourhood-based non-parametric classifiers, Pattern Recognition Lett., 18, 1179-1186 (1997) |
| [24] | T. Kohonen, J. Hynninen, J. Kangas, J. Laarksonen, K. Torkkola, LVQ_PAK: the learning vector quantization program package, Helsinki University of Technology, \(1996 \langle;\) http://www.cis.hut.fi/research/som-research/nnrc-programs.shtml \(\rangle;\); T. Kohonen, J. Hynninen, J. Kangas, J. Laarksonen, K. Torkkola, LVQ_PAK: the learning vector quantization program package, Helsinki University of Technology, \(1996 \langle;\) http://www.cis.hut.fi/research/som-research/nnrc-programs.shtml \(\rangle;\) |
| [25] | Chaudhuri, B. B., A new definition of neighbourhood of a point in multi-dimensional space, Pattern Recognition Lett., 17, 11-17 (1996) |
| [26] | Novovičová, J.; Pudil, P.; Kittler, J., Divergence based feature selection for multimodal class densities, IEEE Trans. Pattern Anal. Mach. Intell., 18, 218-223 (1996) |
| [27] | McLachlan, G.; Basford, K., Mixture Models: Inference and Application to Clustering (1988), Marcel Dekker: Marcel Dekker New York · Zbl 0697.62050 |
| [28] | McLachlan, G.; Krishnan, T., The EM Algorithm and Extensions (1997), Wiley: Wiley New York · Zbl 0882.62012 |
| [29] | Dempster, A. P.; Laird, N. M.; Rubin, D. B., Maximum likelihood from incomplete data via the EM algorithm, J. R. Statist. Soc. B, 39, 1-38 (1977) · Zbl 0364.62022 |
| [30] | Figueiredo, M. A.T.; Jain, A. K., Unsupervised learning of finite mixture models, IEEE Trans. Pattern Anal. Mach. Intell., 24, 381-396 (2002) |
| [31] | E. Pękalska, R.P.W. Duin, S. Günter, H. Bunke, On not making dissimilarities euclidean, Structural Syntactic and Statistical Pattern Recognition, Lecture Notes in Computer Science, vol. 3138, Springer, Berlin, 2004, pp. 1145-1154.; E. Pękalska, R.P.W. Duin, S. Günter, H. Bunke, On not making dissimilarities euclidean, Structural Syntactic and Statistical Pattern Recognition, Lecture Notes in Computer Science, vol. 3138, Springer, Berlin, 2004, pp. 1145-1154. · Zbl 1104.68674 |
| [32] | Cristianini, N.; Shawe-Taylor, J., An Introduction to Support Vector Machines (2000), Cambridge University Press: Cambridge University Press Cambridge |
| [33] | R.P.W. Duin, P. Juszczak, D. de Ridder, P. Paclík, E. Pękalska, D.M.J. Tax, PR-tools, a Matlab toolbox for pattern recognition, \(2004 \langle;\) http://www.prtools.org \(\rangle;\); R.P.W. Duin, P. Juszczak, D. de Ridder, P. Paclík, E. Pękalska, D.M.J. Tax, PR-tools, a Matlab toolbox for pattern recognition, \(2004 \langle;\) http://www.prtools.org \(\rangle;\) |
| [34] | Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern Classification (2001), Wiley: Wiley New York · Zbl 0968.68140 |
| [35] | C.J. Merz, P.M. Murphy, UCI Repository of Machine Learning DB, Department of Information and Computer Science, University of California, \(1998 \langle;\) http://www.ics.uci.edu/\( \sim;\rangle;\); C.J. Merz, P.M. Murphy, UCI Repository of Machine Learning DB, Department of Information and Computer Science, University of California, \(1998 \langle;\) http://www.ics.uci.edu/\( \sim;\rangle;\) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
