Genetic algorithms have been utilized in many complex optimization and simulation tasks because of their powerful search method. In this research we studied whether the classification performance of the attribute weighted methods based on the nearest neighbour search can be improved when using the genetic algorithm in the evolution of attribute weighting. The attribute weights in the starting population were based on the weights set by the application area experts and machine learning methods instead of random weight setting. The genetic algorithm improved the total classification accuracy and the median true positive rate of the attribute weighted k-nearest neighbour method using neighbour’s class-based attribute weighting. With other methods, the changes after genetic algorithm were moderate. 1. Introduction One of the most commonly used simple classification methods is the nearest neighbour (NN) method that classifies a new case into the class of its nearest neighbour case [1]. The nearest neighbour method is an instance-based learning method that searches for the most similar case of the test case from the training data by some distance measure, usually with the Euclidean distance. A natural extension to NN is the k-nearest neighbour (k-NN) method that assigns the majority class of the k nearest training cases for the test case [2]. Different refinements and extensions have been proposed for k-NN in order to improve classification results and overcome classification problems, for example, distance-weighting of neighbours [2], extensions using properties of the data set [3], weighting of attributes [2, 4, 5], and attribute weight optimization with genetic algorithms (GA) [6–11]. Genetic algorithms [12, 13] and other evolution algorithms [14, 15] have been utilized in various complex optimization and simulation problems because of their powerful search and optimization capabilities. A search method of a genetic algorithm is a combination of directed and stochastic search and the search can be done multidirectionally because GA maintains a population of potential solutions from the search space [14]. The basics of the search method of GA underlie in natural selection and genetic inheritance [12]; individuals of the population are used in the reproduction of new solutions by means of crossover and mutation. Genetic algorithms have been used with various machine learning methods to optimize weighting properties of the method. Since our research is based on the nearest neighbour search applying machine learning methods, we concentrate on related works
References
[1]
T. M. Cover and P. E. Hart, “Nearest neighbor pattern classification,” IEEE Transactions on Information Theory, vol. 13, no. 1, pp. 21–27, 1967.
[2]
T. Mitchell, Machine Learning, McGraw-Hill, New York, NY, USA, 1997.
[3]
Z. Voulgaris and G. D. Magoulas, “Extensions of the k nearest neighbour methods for classification problems,” in Proceedings of the 26th IASTED International Conference on Artificial Intelligence and Applications (AIA '08), pp. 23–28, ACTA Press, Anaheim, Calif, USA, February 2008.
[4]
J. M. Sotoca, J. S. Sánchez, and F. Pla, “Estimating feature weights for distance-based classification,” in Proceedings of the 3rd International Workshop on Pattern Recognition in Information Systems (PRIS '03), Angers, France, 2003.
[5]
E. Marchiori, A. Ngom, E. Formenti, J.-K. Hao, X.-M. Zhao, and T. van Laarhoven, “Class dependent feature weighting and k-nearest neighbor classification,” in Proceedings of the 8th IAPR International Conference on Pattern Recognition in Bioinformatics (PRIB '13), vol. 7986 of LNBI, pp. 69–78, Springer, Berlin, Germany, 2013.
[6]
J. D. Kelly and L. Davis, “A hybrid genetic algorithm for classification,” in Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI '91), vol. 2, pp. 645–650, Morgan Kaufmann, San Franciso, Calif, USA, 1991.
[7]
W. F. Punch, E. D. Goodman, M. Pei, L. Chia-Shun, P. Hovland, and R. Enbody, “Further research on feature selection and classification using genetic algorithms,” in Proceedings of the 5th International Conference on Genetic Algorithms (ICGA '93), pp. 557–564, University of Illinois, Champaign, Ill, USA, 1993.
[8]
F. Hussein, N. Kharma, and R. Ward, “Genetic algorithms for feature selection and weighting, a review and study,” in Proceedings of the 6th International Conference on Document Analysis and Recognition (ICDAR '01), pp. 1240–1244, Seattle, Wash, USA, 2001.
[9]
H. Lee, E. Kim, and M. Park, “A genetic feature weighting scheme for pattern recognition,” Integrated Computer-Aided Engineering, vol. 14, no. 2, pp. 161–171, 2007.
[10]
D. Mateos-García, J. García-Gutiérrez, and J. C. Riquelme-Santos, “Label dependent evolutionary feature weighting for remote sensing data,” in Proceedings of the 5th International Conference on Hybrid Artificial Intelligence Systems, pp. 272–279, Springer, 2010.
[11]
D. Mateos-García, J. García-Gutiérrez, and J. C. Riquelme-Santos, “On the evolutionary optimization of k-NN by label-dependent feature weighting,” Pattern Recognition Letters, vol. 33, no. 16, pp. 2232–2238, 2012.
[12]
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, Mass, USA, 1989.
[13]
M. Mitchell, An Introduction to Genetic Algorithms, MIT Press, Cambridge, Mass, USA, 1996.
[14]
Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, Berlin, Germany, 1992.
[15]
A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, Springer, Berlin, Germany, 2003.
[16]
K. Varpa, K. Iltanen, M. Juhola et al., “Refinement of the otoneurological decision support system and its knowledge acquisition process,” in Proceedings of the 20th International Congress of the European Federation for Medical Informatics (MIE '06), pp. 197–202, Maastricht, The Netherlands, 2006.
[17]
K. Varpa, K. Iltanen, M. Siermala, and M. Juhola, “Attribute weighting with scatter and instance-based learning methods evaluated with otoneurological data,” International Journal of Computational Medicine and Healthcare, 2013.
[18]
E. Kentala, I. Pyykk？, Y. Auramo, and M. Juhola, “Database for vertigo,” Otolaryngology—Head and Neck Surgery, vol. 112, no. 3, pp. 383–390, 1995.
[19]
K. Viikki, Machine learning on otoneurological data: decision trees for vertigo diseases [Ph.D. thesis], Department of Computer Sciences, University of Tampere, Tampere, Finland, 2002, http://urn.fi/urn:isbn:951-44-5390-5.
[20]
K. A. De Jong, Analysis of the behaviour of a class of genetic adaptive systems [Ph.D. thesis], Computer and Communication Sciences Department, The University of Michigan, Ann Arbor, Mich, USA, 1975, http://hdl.handle.net/2027.42/4507.
[21]
M. Siermala, M. Juhola, J. Laurikkala, K. Iltanen, E. Kentala, and I. Pyykk？, “Evaluation and classification of otoneurological data with new data analysis methods based on machine learning,” Information Sciences, vol. 177, no. 9, pp. 1963–1976, 2007.
[22]
M. Juhola and M. Siermala, “A scatter method for data and variable importance evaluation,” Integrated Computer-Aided Engineering, vol. 19, no. 2, pp. 137–139, 2012.
[23]
M. Juhola and M. Siermala, “Scatter Counter program and its instructions,” 2014, http://www.uta.fi/sis/cis/research_groups/darg/publications/scatterCounter_2_7_eng.pdf.
[24]
D. W. Aha, “Tolerating noisy, irrelevant and novel attributes in instance-based learning algorithms,” International Journal of Man-Machine Studies, vol. 36, no. 2, pp. 267–287, 1992.
[25]
E. Kentala, Y. Auramo, M. Juhola, and I. Pyykk？, “Comparison between diagnoses of human experts and a neurotologic expert system,” Annals of Otology, Rhinology and Laryngology, vol. 107, no. 2, pp. 135–140, 1998.
[26]
Y. Auramo and M. Juhola, “Modifying an expert system construction to pattern recognition solution,” Artificial Intelligence in Medicine, vol. 8, no. 1, pp. 15–21, 1996.
[27]
E. Kentala, Y. Auramo, I. Pyykk？, and M. Juhola, “Otoneurological expert system,” Annals of Otology, Rhinology and Laryngology, vol. 105, no. 8, pp. 654–658, 1996.
[28]
R. D. Wilson and T. R. Martinez, “Improved heterogeneous distance functions,” Journal of Artificial Intelligence Research, vol. 6, pp. 1–34, 1997.
[29]
M. Galar, A. Fernández, E. Barrenechea, H. Bustince, and F. Herrera, “An overview of ensemble methods for binary classifiers in multi-class problems: experimental study on one-vs-one and one-vs-all schemes,” Pattern Recognition, vol. 44, no. 8, pp. 1761–1776, 2011.
