Feature Reduction of Nearest Neighbor Classifiers using Genetic Algorithm
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:55514", author = "M. Analoui and M. Fadavi Amiri", title = "Feature Reduction of Nearest Neighbor Classifiers using Genetic Algorithm", 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).", volume = "2", number = "5", pages = "1482-4", }