The PM-M prototype selection system

• Autorzy: Grudziński K.
• Języki publikacji: EN

Abstrakty

EN

In this paper, the algorithm, realizing the author’s prototype selection method, called PM-M (Partial Memory - Minimization) is described in details. Computational experiments that have been carried out with the raw PM-M model and with its majority ensembles indicate that even for the system, for which the average size of the selected prototype sets constitutes only about five percent of the size of the original training datasets, the obtained results of classification are still in a good statistical agreement with the 1-Nearest Neighbor (IB1) model which has been trained on the original (i.e. unpruned) data. It has also been shown that the system under study is competitive in terms of generalization ability with respect to other well established prototype selection systems, such as, for example, CHC, SSMA and GGA. Moreover, the proposed algorithm has shown approximately one to three orders of magnitude decrement of time requirements with respect to the necessary time, needed to complete the calculations, relative to the reference prototype classifiers, taken for comparison. It has also been demonstrated that the PM-M system can be directly applied to analysis of very large data unlike most other prototype methods, which have to rely on the stratification approach.

Słowa kluczowe

EN

selection of reference instances; prototype selection; k-Nearest Neighbors algorithm; classification of data

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2016
• Tom: Vol. 45, no. 4
• Strony: 539--561
• Opis fizyczny: Bibliogr. 33 poz., tab.

Twórcy

autor

Grudziński K.

• Department of Physics, Kazimierz Wielki University, Aleja Powstan´cw Wielkopolskich 2, 85-090 Bydgoszcz, Poland grudzinski

Bibliografia

• [1] Aha, D., Kibler, D. and Albert M. (1991) Instance-based learning algorithms. Machine Learning, 6, 37-66.
• [2] Alcala-Fdez, J., Sanchez, L., Garcıa, S., del Jesus, M. J., Ventura, S., Garrell J. M., Otero, J., Romero, C., Bacardit, J., Rivas, V. M., Fernandez, J. C., Herrera, F. (2009) KEEL: A Software Tool to Assess Evolutionary Algorithms to Data Mining Problems. Soft Computing 13:3 307-31.
• [3] Alcala-Fdez, J., Fernandez, A., Luengo, J., Derrac, J., Garcıa, S., Sanchez, L., Herrera, F. (2011) KEEL Data-Mining Software Tool: Data Set Repository, Integration of Algorithms and Experimental Analysis Framework. Journal of Multiple-Valued Logic and Soft Computing 17:2-3, 255-287.
• [4] Bauer, E., Kohavi, R. (1999) An empirical comparison of voting classification algorithms:bagging, boosting and variants. Machine Learning 36, 105-142.
• [5] Bhattacharya, B., Poulsen, R. and Toussaint, G. (1981) Application of proximity graphs to editing nearest neighbor decision rule. In: IEEE International Symposium on Information Theory, Santa Monica. IEEE.
• [6] Brighton, H. and Mellish, C. (2002) Advances in instance selection for instance-based learning algorithms. Data Mining and Knowledge Discovery 6, 153-172.
• [7] Cameron-Jones, R. (1995) Instance selection by encoding length heurystic with random mutation hill climbing. In: Xin Yao, ed., Proceedings of the Eighth Australian Conference on Artificial Intelligence, Canberra. World Scientific Publishing, River Edge, 99–106.
• [8] Cano, J. R., Herrera, F. and Lozano, M. (2005) Stratification for scaling up evolutionary prototype selection. Pattern Recognition Letters, 26, 7, 953–963.
• [9] Duch, W., Blachnik, M. (2004) Fuzzy rule-based systems derived from similarity to prototypes. Lecture Notes in Computer Science, 3316, 912-917.
• [10] Duch, W., Grudzinski, K. (2001) Prototype based rules - new way to understand the data. IEEE International Joint Conference on Neural Networks, Washington D.C., 1858–1863.
• [11] Garca, S., Derrac, J., Cano, J. R. and Herrera, F. (2012) Prototype Selection for Nearest Neighbor Classification: Taxonomy and Empirical Study. IEEE Transactions on Pattern Analysis and Machine Intelligence 34:3 417– 435.
• [12] Gates, G. (1972) The reduced nearest neighbor rule. IEEE Transactions on Information Theory 18, 665–669.
• [13] Grochowski, M. and Jankowski, N. (2004) Comparison of Instances Selection Algorithms II: Results and Comments. Lecture Notes in Artificial Intelligence, LNAI 3070, 580–585.
• [14] Grudzinski, K. (2004) SBL-PM-M: A System for Partial Memory Learning. Lecture Notes in Artificial Intelligence, LNAI 3070, 586–591.
• [15] Grudzinski, K. (2006) Prototype-Based-Committees. In: A. Cader, L. Rutkowski, R. Tadeusiewicz, J. Zurada, eds., Artificial Intelligence and Soft Computing. Academic Pblishing House Exit, Warsaw, 237-244.
• [16] Grudzinski, K. (no date) SuperWeka: A modified Weka version developed by Karol Grudzinski. Grudzinski, K. (2010) Selection of Prototypes with the EkP System. Control and Cybernetics, 39, 2, 487–503.
• [17] Grudzinski, K. (no date) Further Experiments with the EkP and PM-M Prototype Selection Systems. In preparation. Grudzinski, K. and Duch, W. (1996-2017) SBL: Similarity Based Learner: Software developed by Karol Grudzinski and Wlodzislaw Duch.
• [18] Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P. and Witten I. H. (2009) The WEKA Data Mining Software: An Update. SIGKDD Explorations, 11, 1.
• [19] Hart, P. (1968) The condensed nearest neighbor rule. IEEE Transactions on Information Theory 14, 515–516.
• [20] Jankowski, N. (2000) Data regularization. In: L. Rutkowski, R. Tadeusiewicz, eds., Proc. of the Fifth Conference: Neural Networks and Soft Computing, Zakopane, Poland, 209–214.
• [21] Jankowski, N. and Grochowski, M. (2004) Comparison of Instances Selection Algorithms I: Algorithms Survey. Lecture Notes in Artificial Intelligence, LNAI 3070, 598–603.
• [22] Kittler,J., Hatef, M., Duin, R. P. W., Matas J. (1998) On combining classifiers. IEEE Transactions on Pattern Analysis and Machine Intelligence 20, 3, 226–239.
• [23] Kohonen, T., Hyninen, J., Kangas, J., Laaksonnen, J., and Torkolla, K. (1995) LVQ PAK: The Learning Vector Quantization Program Package. Version 3.1. Helsinki University of Technology, Laboratory of Computer and Information Science.
• [24] Kohonen, T. (2001) Self-Orgainizing Maps. 3rd ed. Springer-Verlag, Berlin, Heidelberg.
• [25] Kuncheva,L. (2004) Combining Pattern Classifiers: Methods and Algorithms. John Wiley and Sons, Inc..
• [26] Lampton M. (2004) neldermead.java: an implementation of the Nelder & Mead simplex method. www.ssl.berkeley.edu/∼mlampton/neldermead.java Lichman, M. (no data) UCI Machine Learning Repository [http://archive. ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science.
• [27] Nelder, J. and Mead, R. (1965) A simplex method for function minimization. Computer Journal 7, 308-313.
• [28] Skalak, D. (1994) Prototype and feature selection by sampling and random mutation hill climbing algorithms. In: Proceedings of the Eleventh International Conference on Machine Learning. Morgan Kaufman, 293–301.
• [29] Tomek, I. (1976) An experiment with the edited nearest neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics 6, 448–452.
• [30] Triguero, I., Derrac, J., Garca, S. and Herrera, F. A Taxonomy and Experimental Study on Prototype Generation for Nearest Neighbor Classification. IEEE Transactions on Systems, Man, and Cybernetics–Part C: Applications and Reviews, 42. 1., 86-100.
• [31] Wilson, D. (1972) Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems, Man, and Cybernetics 2, 408-421.
• [32] Wilson, D. and Martinez, T. (1997) Instance Pruning Techniques. In: D. Fisher, ed., Machine Learning: Proceedings of the Fourteenth International Conference. Morgan Kaufmann Publishers, San Francisco, CA., 404-417.
• [33] Wilson, D. and Martinez T. (2000) Reduction Techniques for Instance-Based Learning Algorithms. Machine Learning, 38, 257-286.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).