{"title":"Feature Reduction of Nearest Neighbor Classifiers using Genetic Algorithm","authors":"M. Analoui, M. Fadavi Amiri","volume":17,"journal":"International Journal of Computer and Information Engineering","pagesStart":1557,"pagesEnd":1561,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/6432","abstract":"The design of a pattern classifier includes an attempt\nto select, among a set of possible features, a minimum subset of\nweakly correlated features that better discriminate the pattern classes.\nThis is usually a difficult task in practice, normally requiring the\napplication of heuristic knowledge about the specific problem\ndomain. The selection and quality of the features representing each\npattern have a considerable bearing on the success of subsequent\npattern classification. Feature extraction is the process of deriving\nnew features from the original features in order to reduce the cost of\nfeature measurement, increase classifier efficiency, and allow higher\nclassification accuracy. Many current feature extraction techniques\ninvolve linear transformations of the original pattern vectors to new\nvectors of lower dimensionality. While this is useful for data\nvisualization and increasing classification efficiency, it does not\nnecessarily reduce the number of features that must be measured\nsince each new feature may be a linear combination of all of the\nfeatures in the original pattern vector. In this paper a new approach is\npresented to feature extraction in which feature selection, feature\nextraction, and classifier training are performed simultaneously using\na genetic algorithm. In this approach each feature value is first\nnormalized by a linear equation, then scaled by the associated weight\nprior to training, testing, and classification. A knn classifier is used to\nevaluate each set of feature weights. The genetic algorithm optimizes\na vector of feature weights, which are used to scale the individual\nfeatures in the original pattern vectors in either a linear or a nonlinear\nfashion. By this approach, the number of features used in classifying\ncan be finely reduced.","references":"[1] H. Yan, \"Building a robust nearest neighbor classifier containing only a\nsmall number of prototypes,\" International Journal of Neural Systems,\nvol. 3, pp. 361-369, 1992.\n[2] V. Ramos, \"Using principal component analysis and genetic algorithm\ntechniques to optimize learning time on neural network training for\npattern recognition,\" in Proceedings of the RecPad-97, Coimbra, 1997.\n[3] V. Ramos, \"Evolu\u251c\u00baao e cognicao em an de imagem,\" M.Sc. Thesis, ISTUTL,\nLisbon, 1998.\n[4] N. A. Schmid, \"Thresholding method for dimensionality reduction in\nrecognition systems,\" IEEE Trans. Information Theory, vol. 47, no.7,\n2001.\n[5] R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis.\nNew York: John Wiley & Sons, 1973.\n[6] B. V. Dasarathy, Nearest Neighbor (NN) Norms: NN Pattern\nClassification Techniques. IEEE Computer Society Press, 1991.\n[7] Y. Lee, \"Handwritten digit recognition using k nearest neighbor, radial\nbasis function, and back-propagation neural networks,\" Neural\nComputation, vol. 3, pp.440-449, 1991.\n[8] J. Hrbrant, \"Structure learning of Bayesian networks from databases by\ngenetic algorithms,\" in Proceedings of the 1st International Conference\non Enterprise Information Systems, Setubal, Portugal, 27-30 March\n1999, pp. 225-231.\n[9] J. H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor,\nMI: University of Michigan Press, 1975.\n[10] D. E. Goldberg, Genetic Algorithms in Search, Optimization and\nMachine Learning. Mass.: Addison-Wesley Reading, 1989.\n[11] A. S. Fraser, \"Simulation of genetic systems by automatic digital\ncomputers- I: introduction,\" Australian Journal of Biological Sciences,\nvol. 10, pp. 484-491, 1957.\n[12] D. B. Fogel, Evolutionary Computation: The Fossil Record. New York:\nIEEE Press, 1998.\n[13] D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine\nLearning Reading. MA: Addison-Wesley, 1989.\n[14] W. Siedlecki and J. Sklansky, \"A note on genetic algorithms for largescale\nfeature selection,\" Pattern Recognition Letter, vol. 10, pp. 335-\n347, 1989.\n[15] M. L. Raymer, W. F. Punch, E. D. Goodman, L. A. Kuhn, and A. K.\nJain, \"Dimensionality reduction using GA,\" IEEE Trans. Evolutionary\nComputation, vol. 4, no. 2, 2000.\n[16] M. L. Raymer, W. F. Punch, E. D. Goodman, P. C. Sanschagrin, and L.\nA. Kuh, \"Simultaneous feature scaling and selection using a genetic\nalgorithm,\" in Proceedings of the Seventh International Conference on\nGenetic Algorithms (ICGA'97), San Francisco, 1997, pp. 561-567.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 17, 2008"}