Feature Reduction of Nearest Neighbor Classifiers using Genetic Algorithm

Authors: M. Analoui, M. Fadavi Amiri

Abstract:

The design of a pattern classifier includes an attempt to select, among a set of possible features, a minimum subset of weakly correlated features that better discriminate the pattern classes. This is usually a difficult task in practice, normally requiring the application of heuristic knowledge about the specific problem domain. The selection and quality of the features representing each pattern have a considerable bearing on the success of subsequent pattern classification. Feature extraction is the process of deriving new features from the original features in order to reduce the cost of feature measurement, increase classifier efficiency, and allow higher classification accuracy. Many current feature extraction techniques involve linear transformations of the original pattern vectors to new vectors of lower dimensionality. While this is useful for data visualization and increasing classification efficiency, it does not necessarily reduce the number of features that must be measured since each new feature may be a linear combination of all of the features in the original pattern vector. In this paper a new approach is presented to feature extraction in which feature selection, feature extraction, and classifier training are performed simultaneously using a genetic algorithm. In this approach each feature value is first normalized by a linear equation, then scaled by the associated weight prior to training, testing, and classification. A knn classifier is used to evaluate each set of feature weights. The genetic algorithm optimizes a vector of feature weights, which are used to scale the individual features in the original pattern vectors in either a linear or a nonlinear fashion. By this approach, the number of features used in classifying can be finely reduced.

Keywords: Feature reduction, genetic algorithm, pattern classification, nearest neighbor rule classifiers (k-NNR).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062904

References:

[1] H. Yan, "Building a robust nearest neighbor classifier containing only a small number of prototypes," International Journal of Neural Systems, vol. 3, pp. 361-369, 1992.
[2] V. Ramos, "Using principal component analysis and genetic algorithm techniques to optimize learning time on neural network training for pattern recognition," in Proceedings of the RecPad-97, Coimbra, 1997.
[3] V. Ramos, "Evoluçao e cognicao em an de imagem," M.Sc. Thesis, ISTUTL, Lisbon, 1998.
[4] N. A. Schmid, "Thresholding method for dimensionality reduction in recognition systems," IEEE Trans. Information Theory, vol. 47, no.7, 2001.
[5] R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis. New York: John Wiley & Sons, 1973.
[6] B. V. Dasarathy, Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. IEEE Computer Society Press, 1991.
[7] Y. Lee, "Handwritten digit recognition using k nearest neighbor, radial basis function, and back-propagation neural networks," Neural Computation, vol. 3, pp.440-449, 1991.
[8] J. Hrbrant, "Structure learning of Bayesian networks from databases by genetic algorithms," in Proceedings of the 1st International Conference on Enterprise Information Systems, Setubal, Portugal, 27-30 March 1999, pp. 225-231.
[9] J. H. Holland, Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press, 1975.
[10] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Mass.: Addison-Wesley Reading, 1989.
[11] A. S. Fraser, "Simulation of genetic systems by automatic digital computers- I: introduction," Australian Journal of Biological Sciences, vol. 10, pp. 484-491, 1957.
[12] D. B. Fogel, Evolutionary Computation: The Fossil Record. New York: IEEE Press, 1998.
[13] D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning Reading. MA: Addison-Wesley, 1989.
[14] W. Siedlecki and J. Sklansky, "A note on genetic algorithms for largescale feature selection," Pattern Recognition Letter, vol. 10, pp. 335- 347, 1989.
[15] M. L. Raymer, W. F. Punch, E. D. Goodman, L. A. Kuhn, and A. K. Jain, "Dimensionality reduction using GA," IEEE Trans. Evolutionary Computation, vol. 4, no. 2, 2000.
[16] M. L. Raymer, W. F. Punch, E. D. Goodman, P. C. Sanschagrin, and L. A. Kuh, "Simultaneous feature scaling and selection using a genetic algorithm," in Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA'97), San Francisco, 1997, pp. 561-567.