On k-NN Method with Preprocessing

• Autorzy: Suraj Z. , Delimata P.
• Języki publikacji: EN

Abstrakty

EN

The objective of this study is to introduce a new model of data classification based on preliminary reduction of the training set of examples (preprocessing) in order to facilitate the use of nearest neighbours (NN) techniques in near real-time applications. This study accordingly addresses the issue of minimising the computational resource requirements of NN techniques, memory as well as time. The approach proposed in the paper is a modification of the classical k-Nearest Neighbours (k-NN) method and the k-NN method with local metric induction. Generally, the k-NN method with local metric induction in comparison with the classical k-NN method gives better results in the classification of new examples. Nevertheless, for the large data sets the k-NN method with local metric induction is less time effective than the classical one. The time/space efficiency of classifying algorithms based on these two methods depends not only on a given metric but also on the size of training data. In the paper, we present three methods of preliminary reduction of the training set of examples. All reduction methods decrease the size of a given experimental data preserving the relatively high classification accuracy. Results of experiments conducted on well known data sets, demonstrate the potential benefits of such reduction methods.

Słowa kluczowe

EN

k-NN method; preprocessing; local metric induction; reduction classifier; weighted SVDM

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 69, nr 3
• Strony: 343--358
• Opis fizyczny: tab., bibliogr. 12 poz.

Twórcy

autor

Suraj Z.

autor

Delimata P.

• University of Information Technology and Management, H.Sucharskiego 2, 35-225 Rzeszów, Poland,

Bibliografia

• [1] Bazan, J., Nguyen, H.S., Skowron, A., Szczuka, M.: A view on rough set concept approximations. Lecture Notes in Artificial Intelligence 2639, Springer, 2003, 181-188.
• [2] Bazylevych, R.P., Melnyk, R.A., Rybak, O.G.: Circuit partitioning for FPGAs by the optimal circuit reduction method. VLSI design vol. 11, 3(2000), 237-248.
• [3] Blake, C.L., Merz, C.J.: UCI repository of machine learning databases. Department of Information and Computer Science, University of California, Irvine, CA, 1998. (http://www.ics.uci.edu/ mlearn/mlrepository.html)
• [4] Brighton, H., Mellish, C.: Advances in instance selection for instance-based learning algorithms. Data Mining and Knowledge Discovery 6(2002), Springer, 153-172.
• [5] Dasarathy, B., Sanchez, J., Townsend, S.: Nearest Neighbour Editing and Condensing Tools - Synergy Exploitation. Pattern Analysis and Applications 3(1), 2000, 19-30.
• [6] Domingos, P.: Unifying instance-based and rule-based induction. Machine Learning 24(1996), 141-168.
• [7] Gayar, N.: An Experimental Study of a Self-supervised Classifier Ensemble. In: Proceedings of International Conference on Computational Intelligence (ICCI 2004), Istanbul, Turkey, December 17-19, 2004.
• [8] Góra, G.,Wojna, A.: Riona: a new classification system combining rule induction and instance-based learning. Fundamenta Informaticae 51(2002), 369-390.
• [9] Pawlak, Z.: Rough sets: Theoretical aspects of reasoning about data. Kluwer Academic Publishers, Dordrecht 1991.
• [10] Skowron, A., Wojna, A.: k-nearest neighbours classification with local induction of the simple value difference metric. In: Proceedings of the 4th International Conference on Rough Sets and Current Trends in Computing, Uppsala, Sweeden, June 1-5, 2004, Lecture Notes in Artificial Intelligence 3066, Springer, 2004, pp. 229-234.
• [11] Wilson, D.R.,Martinez, T.R.: Reduction techniques for instance-based learning algorithm.Machine Learning 38(2000), 257-286.
• [12] Wilson, D.R.: Asymptotic properties of nearest neighbour rules using edited data. IEEE Transactions on Systems, Man, and Cybernetics SMC-2(3), 1972, 408-421.