본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

재귀분할을 이용한 새로운 점진적 인스턴스 기반 학습기법
A New Incremental Instance-Based Learning Using Recursive Partitioning

한진철   (명지대학교 산업기술연구소UU0000539  ); 김상귀   (명지대학교 컴퓨터공학과UU0000539  ); 윤충화   (명지대학교 컴퓨터공학과UU0000539  );
  • 초록

    인스턴스 기반 학습의 대표적인 알고리즘인 k-NK(K-Nearest Neighbors)은 단순히 전체 학습패턴을 메모리에 저장한 다음, 분류할 때 학습 패턴들과의 거리를 계산하여 가장 가까운 학습패턴의 클래스로 테스트 패턴을 분류한다. K-NN 기법은 만족할 만한 분류성능을 보여주지만, 학습패턴의 개수가 늘어나면 메모리와 분류 시간이 증가하는 문제점을 가지고 있다. 그러므로, 메모리의 효율적 사용과 분류 시간을 단축시키기 위한 다양한 연구들이 발표되었으며, 그 대표적인 예로 NGE(Nested Generalized Exemplar) 이론을 들 수 있다. 본 논문에서는 학습패턴의 집합으로부터 대표패턴을 생성하는 RPA(Recursive Partition Averaging)기법과 점진적으로 대표패턴을 추출하는 IRPA(Incremental RPA)기법을 제안하였다. RPA기법은 전체 학습패턴의 공간을 재귀적으로 분할하면서 대표패턴을 생성하며, IRPA 기법은 RPA 기법의 특성상 패턴의 특징 개수가 많은 경우, 과도한 분할로 인하여 생성되는 많은 개수의 대표패턴을 줄이기 위하여 점진적으로 대표패턴을 추출하는 알고리즘이다. 본 논문에서 제안한 기법은 기존의 k-NN 기법과 비교하여 현저하게 줄어든 대표패턴을 이용하석 유사한 분류 성능을 보여주며, NGE 이론을 구현한 EACH 시스템과 비교하여 탁월한 분류 성능을 보여준다.


    K-NN (k-Nearest Neighbors), which is a well-known instance-based learning algorithm, simply stores entire training patterns in memory, and uses a distance function to classify a test pattern. K-NN is proven to show satisfactory performance, but it is notorious formemory usage and lengthy computation. Various studies have been found in the literature in order to minimize memory usage and computation time, and NGE (Nested Generalized Exemplar) theory is one of them. In this paper, we propose RPA (Recursive Partition Averaging) and IRPA (Incremental RPA) which is an incremental version of RPA. RPA partitions the entire pattern space recursively, and generates representatives from each partition. Also, due to the fact that RPA is prone to produce excessive number of partitions as the number of features in a pattern increases, we present IRPA which reduces the number of representative patterns by processing the training set in an incremental manner. Our proposed methods have been successfully shown to exhibit comparable performance to k-NN with a lot less number of patterns and better result than EACH system which implements the NGE theory.


  • 주제어

    메모리기반 추론 .   인스턴스 기반 학습 .   점진적 학습 알고리즘.  

  • 참고문헌 (13)

    1. T. Dietterich, 'A Study of Distance-Based Machine Learning Algorithms', Ph. D. Thesis, computer Science Dept., Oregon State University, 1995 
    2. D. Wettschereck and T. Dietterich, 'Locally Adaptive Nearest Neighbor Algorithms', Advances in Neural Information Processing Systems 6, pp.184-191, Morgan Kaufmann, San Mateo, CA. 1994 
    3. D. Wettschereck, 'Weighted k-NN versus Majority k-NN A Recommendation'. German National Research Center for Information Technology, 1995 
    4. D. Aha, 'A Study of Instance-Based Algorithms for Supervised Learning Tasks: Mathematical, Empirical, and Psychological Evaluations', Ph. D. Thesis, Information and Computer Science Dept., University of California, Irvine, 1990 
    5. D. Aha, 'Instance-Based Learning Algorithms, Machine Learning', Vol. 6, No.1, pp, 37-66, 1991 
    6. D. Wettschereck and T. Dietterich, 'An Experimental Comparison of the Nearest-Neighbor and NearestHyperrectangle Algorithms', Machine Learning, Vol.19, No. 1, pp.1-25, 1995 
    7. S. Salzberg, 'A Nearest hyperrectangle learning method, Machine Learning', No.1, pp.251-276, 1991 
    8. D. Wettschereck, et al., 'A Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms', Artificial Intelligence Review Journal, 1996 
    9. 심범식, 정태선, 윤충화, '최근접 초월평면 학습법에서 시드개수의 영향에 대한 분석' 한국정보처리학회 '98 춘계학술대회, 1998 
    10. 이형일, 정태선, 윤충화, 강경식, '재귀 분할 평균법을 이용한 새로운 메모리기반 추론 알고리즘' 한국정보처리학회논문지,Vol.006, No.007, pp.1849-1857, 1999     
    11. Ian H. Witten, Eibe Frank, 'Data Mining', Morgan Kaufmann, pp.89-94, 1999 
    12. http://www.ics.uci.edu/-mlearn 
    13. O. L. Mangasarian and W. H. Wolberg: 'Cancer diagnosis via linear programming', SIAM News, Vol.23, No.5, pp.1 & 18, September, 1990 

 저자의 다른 논문

  • 한진철 (1)

    1. 2007 "재귀적 분할 평균에 기반한 점진적 규칙 추출 알고리즘" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 34 (1): 11~17    
  • 김상귀 (1)

  • 윤충화 (9)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기