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

논문 상세정보

프로토타입 선택을 이용한 최근접 분류 학습의 성능 개선
Performance Improvement of Nearest-neighbor Classification Learning through Prototype Selections

황두성    (단국대학교 컴퓨터과학과  );
  • 초록

    최근접 이웃 분류에서 입력 데이터의 클래스는 선택된 근접 학습 데이터들 중에서 가장 빈번한 클래스로 예측된다. 최근접분류 학습은 학습 단계가 없으나, 준비된 데이터가 모두 예측 분류에 참여하여 일반화 성능이 학습 데이터의 질에 의존된다. 그러므로 학습 데이터가 많아지면 높은 기억 장치 용량과 예측 분류 시 높은 계산 시간이 요구된다. 본 논문에서는 분리 경계면에 위치한 학습 데이터들로 구성된 새로운 학습 데이터를 생성시켜 분류 예측을 수행하는 프로토타입 선택 알고리즘을 제안한다. 제안하는 알고리즘에서는 분리 경계 영역에 위치한 데이터를 Tomek links와 거리를 이용하여 선별하며, 이미 선택된 데이터와 클래스와 거리 관계 분석을 이용하여 프로토타입 집합에 추가 여부를 결정한다. 실험에서 선택된 프로토타입의 수는 원래 학습 데이터에 비해 적은 수의 데이터 집합이 되어 최근접 분류의 적용 시 기억장소의 축소와 빠른 예측 시간을 제공할수 있다.


    Nearest-neighbor classification predicts the class of an input data with the most frequent class among the near training data of the input data. Even though nearest-neighbor classification doesn't have a training stage, all of the training data are necessary in a predictive stage and the generalization performance depends on the quality of training data. Therefore, as the training data size increase, a nearest-neighbor classification requires the large amount of memory and the large computation time in prediction. In this paper, we propose a prototype selection algorithm that predicts the class of test data with the new set of prototypes which are near-boundary training data. Based on Tomek links and distance metric, the proposed algorithm selects boundary data and decides whether the selected data is added to the set of prototypes by considering classes and distance relationships. In the experiments, the number of prototypes is much smaller than the size of original training data and we takes advantages of storage reduction and fast prediction in a nearest-neighbor classification.


  • 주제어

    Prototype Selection .   Nearest Neighbor Rule .   Tomek Link.  

  • 참고문헌 (15)

    1. Christopher M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006. 
    2. X. Wu and V. Kumar, Eds, The Top Ten Algorithms in Data Mining, Chapman & Hall/CRC Data Mining and Knowledge Discovery, 2009. 
    3. S. Garcia, J. Derrac, J.R. Cano, F. Herrera, "Prototype Selection for Nearest Neighbor Classification: Taxonomy and Empirical Study," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 34, No. 3, pp. 417-435, 2012. 
    4. K. Yu, L. Ji, and X. Zhang, "Kernel nearest-neighbor algorithm", Neural Processing Letters, Vol.15, pp.147-156, 2002. 
    5. P. Jeatrakul, K.W. Wong and C.C. Fung, "Data cleaning for classification using misclassification analysis," Journal of Advanced Computational and Intelligent Informatics, Vol.14, No.3, pp. 297-302, 2010. 
    6. T.M. Cover and P. E. Hart, "Nearest neighbor pattern classification," IEEE Trans. on Information Theory, Vol. 13, No. 1, pp. 21-27, 1967. 
    7. F. Angiulli, "Fast nearest neighbor condensation for large data sets classification," IEEE Trans. Knowledge and Data Engineering, Vol.19, pp. 1450-1464, 2007. 
    8. H. A. Fayed and A. F. Atiya, "A Novel Template Reduction Approach for the K-Nearest Neighbor Method," IEEE Trans. on Neural Networks, Vol.20, No. 5, pp.890-896, 2009. 
    9. H. J. Shin and S. Z. Cho, "Response modeling with support vector machines," Expert Systems with Applications, Vol.30, No.4, pp.746-760, 2006. 
    10. J. Wang, P. Neskovic, and L. N. Cooper, "Neighborhood size selection in the k-nearest-neighbor rule using statistical confidence," Pattern Recognition, Vol.39, No.3, pp.417-423, 2006. 
    11. UCI machine learning repository, http://archive.ics.uci.edu/ml/. 
    12. Ian H. Witten and Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, 2nd edition, Elsevier, 2005. 
    13. C. Ferri, P. Flach and J. Hernndez-Orallo, "Learning Decision Trees Using the Area Under ROC Curve," Proceedings of the 19th International Conference on Machine Learning(ICML-2002), pp. 139-146, 2002. 
    14. Jin Huang and Charles X. Ling, "Using AUC and Accuracy in Evaluating Learning Algorithms," IEEE Trans. on Knowledge and Data Engineering, Vol. 17, No. 3, pp. 299-310, 2005. 
    15. Jesse Davis and Mark Goadrich, "The relationship between Precision-Recall and ROC curves," Proceedings of the 23th International Conference on Machine Learning(ICML-2006), pp. 233-240, 2006. 

 저자의 다른 논문

  • 황두성 (11)

    1. 2005 "웹 기반 데이터베이스로부터의 유용한 데이터 추출 기법의 설계 및 응용" 한국산학기술학회논문지 = Journal of the Korea Academia-Industrial cooperation Society 6 (4): 309~314    
    2. 2005 "단백질 기능 예측을 위한 그래프 기반 모델링" 정보처리학회논문지. The KIPS transactions. Part B. Part B b12 (2): 209~214    
    3. 2006 "단위 신경망을 이용한 단백질 기능 예측" 정보처리학회논문지. The KIPS transactions. Part B. Part B b13 (1): 1~6    
    4. 2008 "클래스 불균형 문제에서 베이지안 알고리즘의 학습 행위 분석" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 45 (6): 179~186    
    5. 2008 "지지벡터기계를 이용한 다중 분류 문제의 학습과 성능 비교" 멀티미디어학회논문지 = Journal of Korea Multimedia Society 11 (7): 1035~1042    
    6. 2010 "불균형 데이터 학습을 위한 지지벡터기계 알고리즘" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 15 (7): 11~17    
    7. 2015 "최근접 이웃 규칙 기반 프로토타입 선택과 편의-분산을 이용한 성능 평가" Journal of the Institute of Electronics and Information Engineers = 전자공학회논문지 52 (10): 73~81    
    8. 2016 "Guitar Tab Digit Recognition and Play using Prototype based Classification" 韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information 21 (9): 19~25    
    9. 2016 "클래스 초월구를 이용한 프로토타입 기반 분류" 정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학 5 (10): 483~488    
    10. 2019 "타브 숫자 인식을 위한 기계 학습 알고리즘의 성능 비교" 정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학 8 (1): 19~26    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

이 논문과 함께 출판된 논문 + 더보기