[논문]지역 기반 분류기의 앙상블 학습

최성하; 이병우; 양지훈

doi:10.3745/kipstb.2007.14-b.4.303

지역 기반 분류기의 앙상블 학습
Ensemble Learning of Region Based Classifiers 원문보기

정보처리학회논문지. The KIPS transactions. Part B. Part B, v.14B no.4, 2007년, pp.303 - 310

최성하 (서강대학교 대학원 컴퓨터학과) , 이병우 (서강대학교 대학원 컴퓨터학과) , 양지훈 (서강대학교 컴퓨터학과)

초록
AI-Helper

기계학습에서 분류기틀의 집합으로 구성된 앙상블 분류기는 단일 분류기에 비해 정확도가 높다는 것이 입증되어왔다. 본 논문에서는 새로운 앙상블 학습으로서 데이터의 지역 기반 분류기들의 앙상블 학습을 제시하여 기존의 앙상블 학습과의 비교를 통해 성능을 검증하고자 한다. 지역 기반 분류기의 앙상블 학습은 데이터의 분포가 지역에 따라 다르다는 점에 착안하여 학습 데이터를 분할하여 해당하는 지역에 기반을 둔 분류기들을 만들어 나간다. 이렇게 만들어진 분류기들로부터 지역에 따라 가중치를 둔 투표를 적용하여 앙상블 방법을 이끌어낸다. 본 논문에서 제시한 앙상블 분류기의 성능평가를 위해 단일 분류기와 기존의 앙상블 분류기인 배깅과 부스팅 등을 UCI Machine Learning Repository에 있는 11개의 데이터 셋으로 정확도 비교를 하였다. 그 결과 새로운 앙상블 방법이 기본 분류기로 나이브 베이즈와 SVM을 사용했을 때 다른 방법보다 좋은 성능을 보이는 것을 알 수 있었다.

Abstract ▼ AI-Helper

In machine learning, the ensemble classifier that is a set of classifiers have been introduced for higher accuracy than individual classifiers. We propose a new ensemble learning method that employs a set of region based classifiers. To show the performance of the proposed method. we compared its performance with that of bagging and boosting, which ard existing ensemble methods. Since the distribution of data can be different in different regions in the feature space, we split the data and generate classifiers based on each region and apply a weighted voting among the classifiers. We used 11 data sets from the UCI Machine Learning Repository to compare the performance of our new ensemble method with that of individual classifiers as well as existing ensemble methods such as bagging and boosting. As a result, we found that our method produced improved performance, particularly when the base learner is Naive Bayes or SVM.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

다른 앙상블 방법인 배징과 부스팅과의 정확도 비교를 살펴보자. 표에서 보는 바와 같이 나이브 베이즈와 SVM을 기본 학습알고리즘으로 사용한 앙상블들의 비교에서는 RBE가 대체적으로 정확도가 높음을 알 수 있다.
이는 데이터를 분할해나가면서 얻는 이점이 되고 앙상블을 하는 근거가 된다. 우선 첫 번째 이슈에 대해 논해보자.
그러므로 자식 노드의 분류기들의 집합이 부모 노드의 분류기보다 학습데이터에 대해서 충분히 적은 에러를 보일 것이라고 예상된다. 이를 Theorem 1으로 제시하고 증명해보자.
이제 두 번째 이슈에 대해 살펴보자. RBE에서는 데이터를 분할해 나감에 따라 데이터의 클래스 분포가 단순화되기 때문에 하단 노드로 갈수록 분류하기 쉽게 된다.
지금까지 RBE의 데이터 분할에 대한 의미에 대해서 살펴보았다. 이제 이러한 데이터 분할에 의한 분류기 생성이 앙상블 학습의 측면에서 볼 때 어떠한 의미가 있는지 살펴보자. 2장에서 좋은 앙상블의 조건으로서 기본 학습알고리즘으로부터 생성되는 분류기들이 서로 다양성을 가져야하고 정확도가 높아야한다고 하였다[11].
eoWq+e?이 성립함을 보이기 위해서 e01 > ex A e02 > e2 를 보이는 것으로 충분하다. 이제 이를 보이도록 하겠다. 주어진 학습알고리즘 乙이 표현할 수 있는 가설 공간에서 扁의 Q에 대한 결과와 같은 값을 내는 가설들의 집합을 7希I이라 하자.
. 지금까지 RBE의 데이터 분할에 대한 의미에 대해서 살펴보았다. 이제 이러한 데이터 분할에 의한 분류기 생성이 앙상블 학습의 측면에서 볼 때 어떠한 의미가 있는지 살펴보자.

가설 설정

9%로 단일 분류기의 10%보다 10분의 1로 줄었다. 더불어, 오분류 확률은 분류기가 늘어남에 따라 더욱더 줄어들 것이다. 하지만 실제로는 분류기들 사이에 같은 분포에서 샘플링된 데이터로 하기 때문에 완벽한 다양성을 유지할 수 없다.

제안 방법

알고리즘인 Adaboost.Ml[9]으로 7개의 분류기를 생성시킨 앙상블 분류기, 배깅 기법으로 역시 7개의 분류기를 생성시킨 앙상블 분류기 그리고 3장에서 논의된 바 있는 RBC를 비교 대상으로 하여 분류 정확도를 비교하였다. 본 논문에서 RBE로 학습하여 3레벨까지 데이터를 분할하여 7개의 분류기를 생성시켰기 때문에 공정한 비교를 위해 부스팅과 배깅도 7개의 분류기를 생성하였다.
RBE에서는 데이터를 분할해 나감에 따라 데이터의 클래스 분포가 단순화되기 때문에 하단 노드로 갈수록 분류하기 쉽게 된다. 그러므로 Theorem 1에서 증명한 것처럼 말단 노드의 분류기들이 다른 상위노드의 분류기들보다 학습데이터에 대해서 적은 에러를 보이는 것을 알 수 있고 실제의 실험으로도 대부분 그러한 결과가 나오는 것을 살펴보았다. 이러한 결과에 의하면 분류할 패턴이 특정 지역에 속할 때 해당하는 말단 노드의 분류기만으로 클래스를 결정을 하는 것이 더 높은 성능을 보일 것이라고 기대할 수 있다.
첫째, 데이터를 분할해 나갈수록 분류기의 성능이 더 좋아진다. 둘째, 분할하기 전의 데이터로 부터 학습한 분류기가 분할한 후의 데이터로부터 학습한 분류기들을 보완해준다. 이는 데이터를 분할해나가면서 얻는 이점이 되고 앙상블을 하는 근거가 된다.
Ml[9]으로 7개의 분류기를 생성시킨 앙상블 분류기, 배깅 기법으로 역시 7개의 분류기를 생성시킨 앙상블 분류기 그리고 3장에서 논의된 바 있는 RBC를 비교 대상으로 하여 분류 정확도를 비교하였다. 본 논문에서 RBE로 학습하여 3레벨까지 데이터를 분할하여 7개의 분류기를 생성시켰기 때문에 공정한 비교를 위해 부스팅과 배깅도 7개의 분류기를 생성하였다.
본 논문에서 제시한 RBE가 학습 알고리즘에 독립적으로 작동하는 기법임을 보이기 위해 기본 학습 알고리즘으로서 나이브 베이즈 분류기뿐만 아니라, SVM을 구현한 선형커널을 가진 SMO[14]와 C4.5H6]를 통한 결정트리를 사용하였다. 실험에 쓰일 데이터는 UCI Machine Learning Repository[2] 에 있는 실제 데이터를 가져왔으며 실험은 11개의 데이터셋에서 수행하였다.
본 논문에서는 RBE가 데이터 분할단계로 3단계까지만 진행하여 각 말단 노드의 깊이가 같은 3단계의 전 이진 트리 (Complete Binary Tree)로 구성하여 총 7개의 분류기로 실험하였다. 전 이진 트리로 구성된 이유는 앙상블 분류기의 개수에 대한 파라메타로서 데이터를 몇 등분 할 것인지, 몇 단계로 분할할지를 지정해 놓았기 때문이다(그림 1 참조).
이는 재귀(Recursive) 호출에 의해 구현될 수 있다. 본 논문에서는 지역 분할의 단계를 3회로 설정하여 총 7개의 분류기(%, 弓1, …, 를 생성하였다. 이렇게 생성된 분류기로 새로운 패턴이 들어올 때의 클래스를 결정하기 위하여 그 패턴이 속한 지역에 따라 분류기들을 선택해 투표한다.
본 논문에서는 지역 분할의 단계를 3회로 설정하여 총 7개의 분류기(%, 弓1, …, 를 생성하였다. 이렇게 생성된 분류기로 새로운 패턴이 들어올 때의 클래스를 결정하기 위하여 그 패턴이 속한 지역에 따라 분류기들을 선택해 투표한다.
를 한 표이다. 정확도가 더 높은 곳에 굵은 글씨로 표시하였고 그 차이가 두드러지게 RBE가 좋은 곳에는 O 표시를 하였고 나쁜 곳에는 X표시를 하였다.

대상 데이터

5H6]를 통한 결정트리를 사용하였다. 실험에 쓰일 데이터는 UCI Machine Learning Repository[2] 에 있는 실제 데이터를 가져왔으며 실험은 11개의 데이터셋에서 수행하였다. 데이터 셋에 대한 설명은<표 3>을 참고한다.

이론/모형

기본 학습 알고리즘은 공개 데이터마이닝 소프트웨어인 Weka3[18]을 사용하였고 기타 앙상블 기법에 사용된 프로그램은 자체 구현하였다.
예외적인 경우는 굵은체로 표시하였다. 이 실험은 기본 학습 알고리즘으로 나이브 베이즈와 SMO[14]를 선택하여 실험하였다. SVMe Theorem 1에 주어진 조건을 만족한다고 알려져 있지만 SVMe 매우 많은 시간을 소비하기 때문에 실제로는 이를 근사화하여 구현한 SMO를 많이 사용한다.

성능/효과

5를 기본 학습알고리즘으로 실험한 결과를 살펴보자. C4.5를 기본 학습알고리즘으로 선택하였을 때는 부스팅과 배징의 앙상블 기법이 RBE보다 성능이 대체적으로 좋은 것으로 나타났다. 이는 단일 분류기와의 실험에서 살펴본 것처럼 RBE도 정확도가 상승했지만 부스팅과 배깅이 정확도를 그보다 더 상승시켰기 때문에 이와 같은 결과가 나타난 것이다.
두 번째로 말단 노드의 분류기들만 가지고 분류를 했을 때 학습데이터에 대해서는 높은 적응성(fitting)을 갖지만 새로운 데이터 패턴이 들어왔을 때 잘한다는 보장을 할 수 없다. 왜냐하면 학습 데이터의 부족으로 인해 분류기를 생성하는 데 있어서 어려움이 있을 수 있고 또한 학습데이터에 과잉적응 되는 현상이 발생할 수 있기 때문이다.
5) 와 같은 불안정한 (Unstable)한 알고리즘에서 큰 정확도 상승을 보이는 것을 알 수 있다. 위의 실험 결과들을 종합하여 볼 때, 나이브 베이즈와 SVM과 같은 안정적인 알고리즘에서는 RBE가 성능이 더 좋았음을 알 수 있고 C4.5와 같은 불안정한 알고리즘에서는 기존의 앙상블 방법인 부스팅과 배깅이 더 좋다는 것을 알 수 있다.
학습을 제시하였다. 이 방법은 기존의 앙상블 방법과 비교했을 때 안정적인 알고리즘(Stable Algorithm)을 기본 학습기로 사용한 경우에 더 뛰어난 정확도를 보였다. 이는 좋은 앙상블의 조건 중에 하나인 분류기간에 서로 독립적으로 입력공간의 다른 곳에서 에러를 가져야 한다는 것과 관련하여 정보획득에 의해 속성을 선택하여 그 속성을 기준으로 데이터를 분할하여 데이터 사이의 분포를 최대한 다르고 쉽게 만든다.
이제 RBC와의 비교를 살펴보면 표에서 보는 바와 같이 기본 학습알고리즘과 상관없이 대부분의 데이터 셋에서 RBE가 정확도가 더 높았으며, 일부 데이터에 대해서는 주목할 만한 정확도 차이를 보였다. 이 결과는 3.
" data-before="있다" data-ocr-fix="">있다. 첫째, 기본 학습 알고리즘이 분류하기 어려운 데이터일 경우 데이터를 재추출하더라도 역시 어려운 데이터일 수 있다. 이런 경우에는 특히 배깅 방법을 사용할 경우 에러를 갖는 지역이 집중되어 있으며 이는 좋은 앙상블의 조건인 분류기의 다양성에 위배된다.
측면에서 살펴보자. 첫째, 데이터를 분할해 나갈수록 분류기의 성능이 더 좋아진다. 둘째, 분할하기 전의 데이터로 부터 학습한 분류기가 분할한 후의 데이터로부터 학습한 분류기들을 보완해준다.

후속연구

둘째, 각 지역에 따라 분포가 틀리지만 어떤 분류기가 그 지역에 대해 높은 정확도를 보이는지 알지 못한다. 예를 들어, 부스팅의 경우 선행되는 분류기가 잘못된 분류를 하는 인스턴스에 대해 가중치를 두기 때문에 선행되는 분류기가 분류하지 못한 부분을 잘 분류하도록 학습한다.
하지만 실제로 분류할 때 그 부분이 어딘지는 알지 못한다. 만약, 각 분류기 별로 잘 분류하는 인스턴스가 어떠한 것인지 안다면 보다 정확하게 분류할 수 있을 것이라 기대된다.
그러므로 Theorem 1에서 증명한 것처럼 말단 노드의 분류기들이 다른 상위노드의 분류기들보다 학습데이터에 대해서 적은 에러를 보이는 것을 알 수 있고 실제의 실험으로도 대부분 그러한 결과가 나오는 것을 살펴보았다. 이러한 결과에 의하면 분류할 패턴이 특정 지역에 속할 때 해당하는 말단 노드의 분류기만으로 클래스를 결정을 하는 것이 더 높은 성능을 보일 것이라고 기대할 수 있다. 그럼에도 불구하고 상위노드의 분류기들이 하위노드의 분류기들을 보완해 준다는 두 번째 이슈를 다시 두 가지 측면에서 보이겠다.
이는 좋은 앙상블의 조건 중에 하나인 분류기간에 서로 독립적으로 입력공간의 다른 곳에서 에러를 가져야 한다는 것과 관련하여 정보획득에 의해 속성을 선택하여 그 속성을 기준으로 데이터를 분할하여 데이터 사이의 분포를 최대한 다르고 쉽게 만든다. 이렇게 데이터를 분할해 나가면서 데이터의 일부만 보고 학습을 하기 때문에 분류기의 다양성 측면에서 다른 앙상블 방법보다 더 좋을 것이라고 기대된다. 또한, 또 다른 좋은 앙상블의 조건인 각 분류기는 정확해야 한다는 것과 관련해서 데이터를 분할하여 학습을 하면 그 지역을 제외한 다른 데이터에 대해서는 성능이 떨어지기 때문에 그 분류기가 정확하게 분류할 수 있는 지역에만 투표를 참여함으로써 분류를 결정하게 된다.

참고문헌 (18)

Bauer, E. & Kohavi, R., 'An Empirical Comparison of Voting Classification Algorithm: Bagging, Boosting, and Variants', Machine Learning, 36(1-2), pp. 105-142, 1999
Blake, C. & Merz, C., UCI Repository of Machine Learning Database, http//www.ics.uci.edu /~mlearn/MLRepository.html, 1998
Breiman, L., 'Bias, Variance, and Arcing Classifiers', Technical Report TR, 460, UC Berkeley, 1996
Breiman, L., 'Bagging Predictors', Machine Learning, 24(2), pp. 123-140, 1996

상세보기
Dietterich, T., 'An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization', Machine Learning , 40(2), pp. 139-157, 2000
Dietterich, T., 'Ensemble method in Machine learning', In J. Kittler and F. Roli (Ed.) First International Workshop on Multiple Classifier Systems, Lecture Notes in Computer Science, pp. 1-15, 2000

상세보기
Dietterich, T., 'Ensemble Learning', In The Handbook of Brain Theory and Neural Networks, Second edition, The MIT Press, pp. 405-408, 2002
Freund, Y. & Schapire, R., 'Experiments with a new boosting algorithm', In Proc. of the Thirteenth International Conference on Machine Learning, pp. 148-156, 1996
Freund, Y. & Schapire, R., 'A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting', Journal of Computer and System Science, 55, pp. 119-139, 1997

상세보기
Friedman, J., Hastie, T. & Tibshirani, R., 'Additive Logistic Regression: a Statistical View of Boosting', Annals of Statistics, 28(2), pp. 337-374, 2000

상세보기
Hansen, L. & Salamon, P., 'Neural Network Ensembles', IEEE Transaction on Pattern Analysis and Machine Intelligence, 12, pp. 993-1001, 1990

상세보기
L.I. Kuncheva and C.J. Whitaker. 'Measures of diversity in classifier ensembles', Machine Learning, 51, pp. 181-207, 2003
Opitz, D. & Maclin, R., 'Popular Ensemble Methods: An Empirical Study', Journal of Artificial Intelligence Research, 11, pp. 169-198, 1999

상세보기
Platt, J. Fast Training of Support Vector Machines using Sequential Minimal Optimization, chapter 12, pp. 185-208, The MIT Press, 1999
Quinlan, J., 'Induction of Decision Tree', Machine Learning, 1(1), pp. 81- 106, 1986

상세보기
Quinlan, J., C4.5: Programs for Machine Learning, Morgan Kaufmann, 1993
Quinlan, J., 'Bagging, Boosting, and C4.5.', In Proc. of the Thirteenth National Conference on Artificial Intelligence, pp. 725-730, 1996
Witten, I. & Frank, E., Data Mining: Practical Machine Learning Tools and Techniques with Java Implementation, Second edition, Morgan Kaufmann, 2005

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증