Methods of strong reduction and edition of a reference set for the nearest neighbour rule

• Autorzy: Raniszewski M.

Warianty tytułu

PL

Metody silnej redukcji i edycji zbioru odniesienia dla reguły typu najbliższy sąsiad

• Języki publikacji: EN

Abstrakty

EN

The article summarises a doctoral dissertation proposing new methods of a reference set reduction and edition for the Nearest Neighbour Rule (NN).The presented methods are designed to accelerate NN and to improve its classification quality. The algorithms use the concept of the object representativeness. The obtained results were compared with the results provided by well-known and popular reduction and editing procedures.

PL

W artykule zaprezentowano tezy i podstawowe wyniki rozprawy doktorskiej dotyczącej nowych metod redukcji i edycji zbioru odniesienia dla reguły typu najbliszy sąsiad (NN). Przedstawione metody mają na celu przyspieszenie działania reguły NN i poprawę jej jakości klasyfikacji. Zaprezentowane algorytmy w większości wykorzystują pojęcie reprezentatywności obiektu. Wyniki ich działania zostały porównane z wynikami działania innych popularnych algorytmów redukcji i edycji.

Słowa kluczowe

EN

NN Rule; nearest neighbour rule; reduction of reference set; edition of reference set

PL

reguła NN; reguła najbliższy sąsiad; redukcja zbioru odniesienia; edycja zbioru odniesienia

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Zeszyty Naukowe. Elektryka / Politechnika Łódzka
• Rocznik: 2010
• Tom: z. 122
• Strony: 37--46
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Raniszewski M.

• Faculty of Electrical, Electronic, Computer and Control Engineering Technical University of Łódź

Bibliografia

• [1] Frank A., Asuncion A.: UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science, 2010.
• [2] Cerveron V., Ferri F.J.: Another move towards the minimum consistent subset: A tabu search approach to the condensed nearest neighbor rule. IEEE Trans. On Systems, Man and Cybernetics, Part B: Cybernetics, Vol. 31(3), 2001, pp. 408-413.
• [3] Cover T.M., Hart P.E.: Nearest neighbor pattern classification. IEEE Trans. Inform. Theory, Vol. IT-13, 1967, pp. 21-27.
• [4] Dasarathy B.V.: Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design. IEEE Transactions on Systems, Man, and Cybernetics 24(3), 1994, pp. 511-517.
• [5] Devijver P.A., Kittler J.: On the edited nearest neighbor rule. Proc. 5th International Conf. on Pattern Recognition, 1980, pp. 72-80.
• [6] Duda R.O., Hart P.E., Stork D.G.: Pattern Classification - Second Edition. John Wiley & Sons, Inc, 2001.
• [7] Gates G.W.: The reduced nearest neighbor rule. IEEE Transactions on Information Theory, Vol. IT 18, No. 5, 1972, pp. 431-433.
• [8] Gowda K.C., Krishna G.: The condensed nearest neighbor rule using the concept of mutual nearest neighborhood. IEEE Transaction on Information Theory, Vol. IT-25, 4, 1979, pp. 488-490.
• [9] Hart P.E.: The condensed nearest neighbor rule. IEEE Transactions on Information Theory, Vol. IT-14, 3, 1968, pp. 515-516.
• [10] Kohavi R.: A study of cross-validation and bootstrap for accuracy estimation and model selection. Proc. 14th Int. Joint Conf. Artificial Intelligence, 1995, pp. 338-345.
• [11] Ko_la P., Raniszewski M.: Nowe metody selekcji cech i redukcji zbiorów odniesienia dla klasyfikatora typu 1-NN. Automatyka, Vol. 12(3), 2008, pp. 805-820.
• [12] Kuncheva L.I.: Editing for the k-nearest neighbors rule by a genetic algorithm. Pattern Recognition Letters, Vol. 16, 1995, pp. 809-814.
• [13] Kuncheva L.I.: Fitness functions in editing k-NN reference set by genetic algorithms. Pattern Recognition, Vol. 30, No. 6, 1997, pp. 1041-1049.
• [14] Kuncheva L.I., Bezdek J.C.: Nearest prototype classification: clustering, genetic algorithms, or random search? IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, Vol. 28(1), 1998, pp. 160-164.
• [15] Raniszewski M.: Reference Set Reduction Algorithms Based on Double Sorting. Computer Recognition Systems 2, Advances in Soft Computing, Vol. 45, Springer Berlin/Heidelberg, 2007, pp. 258-265.
• [16] Raniszewski M.: Double Sort Algorithm resulting in reference set of the desired size. Biocybernetics and Biomedical Engineering, Vol. 28(4), 2008, pp. 43-50.
• [17] Raniszewski M.: The Sequential Reduction Algorithm for Nearest Neighbor Rule Based on Double Sorting. Computer Recognition Systems 3, Advances in Intelligent and Soft Computing, Vol. 57, Springer Berlin/Heidelberg, 2009, pp. 221-229.
• [18] Raniszewski M.: The Edited Nearest Neighbor Rule Based on the Reduced Reference Set and the Consistency Criterion. Biocybernetics and Biomedical Engineering, Vol. 30(1), 2010, pp. 31-40.
• [19] Raniszewski M.: Sequential Reduction Algorithm for Nearest Neighbor Rule. Computer Vision and Graphics, Second International Conference, ICCVG 2010, Proceedings, Part II, Lecture Notes in Computer Science Vol. 6375, Springer-Verlag Berlin Heidelberg, 2010, pp. 219-226.
• [20] Skalak D.B.: Prototype and feature selection by sampling and random mutation hill climbing algorithms. 11th International Conference on Machine Learning, New Brunswick, NJ, USA, 1994, pp. 293-301.
• [21] The ELENA Project Real Databases [http://www.dice.ucl.ac.be/neural-ets/Research/Projects/ELENA/databases/REAL/].
• [22] Theodoridis S., Koutroumbas K.: Pattern Recognition - Third Edition. Academic Press - Elsevier, USA, 2006.
• [23] Tomek I.: An Experiment with the edited nearest-neighbor rule. IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-6, No. 6, 1976a, pp. 448-452.
• [24] Tomek I.: Two modifications of CNN. IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-6, No. 11, 1976b, pp. 769-772.
• [25] Wilson D.L.: Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions On Systems, Man and Cybernetics, Vol. 2, 1972, pp. 408-421.
• [26] Wilson D.R., Martinez T.R.: Reduction techniques for instance-based learning algorithms. Machine Learning, Vol. 38, No. 3, 2000, pp. 257-286.