Journal of KIISE:Software and Applications (한국정보과학회논문지:소프트웨어및응용)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

Calculating Attribute Weights in K-Nearest Neighbor Algorithms using Information Theory

정보이론을 이용한 K-최근접 이웃 알고리즘에서의 속성 가중치 계산

  • Published : 2005.09.01
Download PDF
⟨ Previous Next ⟩

Abstract

Nearest neighbor algorithms classify an unseen input instance by selecting similar cases and use the discovered membership to make predictions about the unknown features of the input instance. The usefulness of the nearest neighbor algorithms have been demonstrated sufficiently in many real-world domains. In nearest neighbor algorithms, it is an important issue to assign proper weights to the attributes. Therefore, in this paper, we propose a new method which can automatically assigns to each attribute a weight of its importance with respect to the target attribute. The method has been implemented as a computer program and its effectiveness has been tested on a number of machine learning databases publicly available.

최근접 이웃(k nearest neighbor) 알고리즘은 새로운 개체의 목표값을 예측하기 위하여 과거의 유사한 데이타를 이용하여 그 값을 예측하는 것이다. 이 방법은 기계학습의 여러 분야에서 그 유용성을 검증받아 널리 사용되고 있다. 이러한 kNN 알고리즘에서 목표값을 예측할 때 각 속성의 가중치를 동일하게 고려하는 것은 좋은 성능을 보장할 수 없으며 따라서 kNN에서 각 속성에 대한 가중치를 적절히 계산하는 것은 kNN 알고리즘의 성능을 결정하는 중요한 요소중의 하나이다. 본 논문에서는 정보이론을 이용하여 kNN 에서의 속성의 가중치를 효과적으로 계산하는 새로운 방법을 제시하고자한다. 제안된 방법은 각 속성이 목표 속성에 제공하는 정보의 양에 따라 가중치를 자동으로 계산하여 kNN 방법의 성능을 향상시킨다. 개발된 알고리즘은 다수의 실험 데이타를 이용하여 그 성능을 비교하였다.

Keywords

References

  1. Quinlan, J. R. 'C4.5: Programs for Machine Learning,' San Mateo, CA:Morgan Kaufmann, 1993
  2. L. Breiman, J. Friedman, R. Olshen, and C. Stone, 'Classification and Regression Trees,' Monterey, CA: Wadsworth International Group, 1984
  3. S. Haykin, 'Neural Networks: A Comprehensive Foundation,' Prentice Hall, 1999
  4. T. M. Cover and P. E. Hart, 'Nearest Neighbor Pattern Classification,' IEEE Transactions on Information Theory, Vol. 13, 1967
  5. E. E. Smith and D. L. Medin, 'Categories and Concepts,' Cambridge, MA: Harvard University Press, 1981
  6. D. Aha, D. Kibler and M. Albert, 'Instance-based Learning Algorithms,' Machine Learning, 6(1) pp. 37-66, 1991 https://doi.org/10.1007/BF00153759
  7. J. Zhang, 'Selecting typical instances in instance-based learning,' Proceedings of the Ninth Int. Machine Learning Conference, pp. 470-479, Aberdeen, Scotland: Morgan Kaufmann, 1992
  8. S. Romaniuk, 'Efficient Storage of Instances: The Multi-pass Approach,' Proc. of the Seventh Int. Conf. on Industrial and Engineering Applications of Artificial Intelligence and Expert systems, Austin, TX, 1994
  9. D. Skalak, 'Prototype and Feature Selection by Sampling and Random Mutation Hill Climbing Algorithms,' Proc. of the 11th International Conference on Machine Learning, New Brunswick, NJ, 1994
  10. S. Salzberg, 'A Nearest Hyperrectangle Learning Method,' Machine Learning, 6, pp. 251-276, 1991 https://doi.org/10.1007/BF00114779
  11. D. Aha, 'Tolerating noisy, irrelevant, and novel attributes in instance-based learning algorithms,' Int'l Journal of Man-Machine Studies, 36, pp. 267-287, 1992 https://doi.org/10.1016/0020-7373(92)90018-G
  12. R. Creecy, B. Masand, S. Smith, and D. Waltz 'Trading MIPS and Memory for Knowledge Engineering,' Communications of the ACM, 35, pp. 48-64, 1992 https://doi.org/10.1145/135226.135228
  13. S. Cost and S. Salzberg, 'A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features,' Machine Learning, 10, pp. 57-78, 1993 https://doi.org/10.1007/BF00993481
  14. J. D. Kelly and L. Davis, 'A Hybrid Genetic Algorithm for Classification,' Proc. of the 12th Int. Joint Canf. on Artificial Intelligence, pp. 645-650, Sydney, Australia: Morgan Kaufmann, 1991
  15. van den Bosch, A. and Daelemans, W. 'Data Oriented-Method for Grapheme-to-Phoneme Convertsion' Technical Report, Tilburg, Netherlands, Tilburg University: Institute for Language Technology and Artificial Intelligence, 1993
  16. C. Stanfill and D. Waltz, 'Toward Memory-based Reasoning,' Communications of the ACM, 29(12), pp. 1213-1228, 1986 https://doi.org/10.1145/7902.7906
  17. R. J. Beran, 'Minimum Hellinger Distances for Parametric Models,' Ann. Statistics, Vol. 5, pp. 445-463, 1977 https://doi.org/10.1214/aos/1176343842
  18. Z. Ying, 'Minimum Hellinger Distance Estimation for Censored Data,' Annals of Statistics, Vol. 20, No. 3, pp. 1361-1390, 1992 https://doi.org/10.1214/aos/1176348773
  19. P. Murphy and D. Aha, UCI Repository of Machine Learning Databases, Irvine, CA:University of California Irvine, Department of Information and Compter Science, 1993