×

Nearest prototype classifier designs: An experimental study. (English) Zbl 0997.68125

Summary: We compare eleven methods for finding prototypes upon which to base the nearest prototype classifier. Four methods for prototype selection are discussed: Wilson + Hart (a condensation + error-editing method), and three types of combinatorial search – random search, genetic algorithm, and tabu search. Seven methods for prototype extraction are discussed: unsupervised vector quantization, supervised learning vector quantization (with and without training counters), decision surface mapping, a fuzzy version of vector quantization, \(c\)-means clustering, and bootstrap editing. These eleven methods can be usefully divided two other ways: by whether they employ pre- or postsupervision; and by whether the number of prototypes found is user-defined or “automatic.” Generalization error rates of the 11 methods are estimated on two synthetic and two real data sets. Offering the usual disclaimer that these are just a limited set of experiments, we feel confident in asserting that presupervised, extraction methods offer a better chance for success to the casual user than postsupervised, selection schemes. Finally, our calculations do not suggest that methods which find the “best” number of prototypes “automatically” are superior to methods for which the user simply specifies the number of prototypes.

MSC:

68T10 Pattern recognition, speech recognition
68P10 Searching and sorting

Software:

PRTools
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fuzzy models and algorithms for pattern recognition and image processing. Norwell, MA: Kluwer; 1999. · Zbl 0998.68138 · doi:10.1007/b106267
[2] Domingos, Artificial Intelligence Review 11 pp 227– (1997) · Zbl 05469231 · doi:10.1023/A:1006508722917
[3] Krishnapuram, IEEE Trans Fuzzy Systems 1 pp 98– (1998) · doi:10.1109/91.227387
[4] Introduction to artificial neural systems. St. Paul, MN: West Publ. Co.; 1992.
[5] Kuncheva, Int J Uncertainty, Fuzziness Knowledge-based Systems 6 pp 437– (1998) · Zbl 1087.68626 · doi:10.1142/S0218488598000355
[6] Kuncheva, IEEE Trans Systems, Man, and Cybernet C28 pp 160– (1998) · doi:10.1109/5326.661099
[7] Kuncheva, IEEE Trans Neural Networks 10 pp 1142– (1999) · doi:10.1109/72.788653
[8] Improved versions of learning vector quantization. Proc Int Joint Conf Neural Networks, San Diego, CA, 1990, p I-545-550.
[9] Self-organizing maps. Germany: Springer; 1995. · doi:10.1007/978-3-642-97610-0
[10] Diamantini, IEEE Trans Neural Networks 9 pp 174– (1998) · doi:10.1109/72.655039
[11] Diamantini, IEEE Trans CAS-1: Fundamental Theory and Applications 43 pp 425– (1996) · doi:10.1109/81.502216
[12] Odorico, Neural Networks 10 pp 1083– (1997) · Zbl 0930.68001 · doi:10.1016/S0893-6080(97)00012-9
[13] Geva, IEEE Trans Neural Networks 2 pp 318– (1991) · doi:10.1109/72.80344
[14] Hart, IEEE Trans Inform Theory IT-14 pp 515– (1968) · doi:10.1109/TIT.1968.1054155
[15] Nearest neighbor (NN) norms: NN pattern classification techniques. Los Alamitos, CA: IEEE Computer Society Press; 1991.
[16] Another move towards the minimum consistent subset: A tabu search approach to the condensed nearest neighbor rule (submitted).
[17] Dasarathy, IEEE Trans Systems Man Cybernet 24 pp 511– (1994) · doi:10.1109/21.278999
[18] Wilson, IEEE Trans Systems Man Cybernet SMC-2 pp 408– (1972) · Zbl 0276.62060 · doi:10.1109/TSMC.1972.4309137
[19] On the edited nearest neighbor rule. In: Proc 5th Int Conf on Pattern Recognition. Los Alamitos, CA: IEEE Computer Society Press; 1980. p 72-80.
[20] Pattern recognition: A statistical approach. Englewood Cliffs, NJ: Prentice-Hall, Inc.; 1982. · Zbl 0542.68071
[21] Ferri, Kybernetika 34 pp 405– (1998)
[22] Prototype and feature selection by sampling and random mutation hill climbing algorithms. In: Proc 11th Int Conf on Machine Learning, New Brunswick, NJ. Los Alamitos, CA: Morgan Kaufmann; 1994. p 293-301.
[23] Using genetic algorithms to improve pattern classification performance. In: editors. Advances in neural information processing systems 3. San Mateo, CA: Morgan Kaufmann; 1991. p 797-803.
[24] Kuncheva, Pattern Recognition Letters, Special Issue on Genetic Algorithms 16 pp 809– (1995) · Zbl 05478998 · doi:10.1016/0167-8655(95)00047-K
[25] Kuncheva, Pattern Recognition 30 pp 1041– (1997) · Zbl 05468642 · doi:10.1016/S0031-3203(96)00134-3
[26] Some methods for classification and analysis of multivariate observations. In: editors. Proc Berkeley Symp Math Stat and Prob 1. Berkeley: Univ of California Press; 281-297.
[27] Hamamoto, IEEE Trans Pattern Analysis and Machine Intelligence 19 pp 73– (1997) · Zbl 05110540 · doi:10.1109/34.566814
[28] Xie, IEEE Trans on Pattern Analysis and Machine Intelligence 15 pp 1326– (1993) · Zbl 05112948 · doi:10.1109/34.250849
[29] Karayiannis, IEEE Trans Neural Networks 7 pp 1062– (1996) · doi:10.1109/72.536304
[30] Bezdek, IEEE Trans Systems Man Cybernet C28 pp 67– (1998) · doi:10.1109/5326.661091
[31] PRTOOLS, Version 2. A Matlab toolbox for pattern recognition. Pattern Recognition Group, Delft University of Technology, June, 1997.
[32] Pattern recognition and neural networks. Cambridge, UK: University Press; 1996. · Zbl 0853.62046 · doi:10.1017/CBO9780511812651
[33] Holmstrom, IEEE Trans Neural Networks 8 pp 5– (1997) · doi:10.1109/72.554187
[34] Pattern classification and scene analysis. New York: John Wiley & Sons; 1973. · Zbl 0277.68056
[35] Logistic discrimination. In: editors. Classification, pattern recognition of dimensionality, Handbook of Statistics Series, 2. North Holland; 1982. p 169-191. · doi:10.1016/S0169-7161(82)02010-0
[36] Operations research, applications and algorithms, 3rd ed. Belmont, CA: Duxbury Press; 1994. · Zbl 0867.90079
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.