adaboost

Top 10 Algorithms in Data Mining  중 하나인 adaboost 에 대해 알아본다. 이후 가능하다면 adaboost를 적용한 논문인 defuse에 대한 요약을 하도록 하겠다 (아래 내용은 책 "Machine Learning in Action" 을 기반으로 한다).

다양한 classifier를 결합하는 방법을 ensemble method 혹은 meta algorithm이라 한다.
이런 meta algorithm 에는 bagging, random forests, boosting 방법등이 있다. 
adaboost 는 adaptive boost의 줄임말로 boosting 의 한가지 유형이다. 

stumpClassify는 데이터(dataMatrix)를 특정 feature (dimen), threshold value (threshVal) 그리고 그 threshold 를 기준으로 큰 값 혹은 작은 값인지를 판단하는 threshIneq를 가지고 분류하는 기능을 한다.

buildStump 는 data array (dataArr), classLabels와 가중치 벡터 (D) 를 받아서 분류를 가장 잘하는 feature (dim) 와 특정 값 (thresh)과 그것에 대한 기준(ineq) 을 찾는 역할(stump 생성)을 한다.

adaBoostTrainDS 는 data array (dataArr), classLabels와 iteration 횟수 (numIt) 를 받아서 numIt 횟수만큼(혹은 errorRate가 0일 때까지) 반복을 하면서 가중치 벡터 (D)를 갱신해가며 buildStump를 이용해서 얻은 최적의 stump 들을 리스트 weakClassArr 에 쌓아 놓는다.

위에서 D를 어떻게 갱신해가는가를 보면 buildStump가 만든 stump가 맞으면 D를 줄이고 틀리면 D 를 늘리는 방향으로 갱신하는데 이때 줄이고 늘리는 정도가 그 stump의 정확도에 비례한다. 곧 정확도가 높을 수록 맞춘 예의 D는 크게 줄이고 틀린 예의 D는 크게 늘린다. 

adaClassify는 datToClass는 분류하고자 하는 새로운 데이터, classifierArr는 adaBoostTrainDS 통해 얻은 weak classifier array (weakClassArr) 를 인자로 받는다.
 adaBoostTrainDS 통해 얻은 weak classifier array (weakClassArr)를 이용하여 데이터(dataToClass) 를 분류한다. 이 때 weakClassArr에 있는 classifier를 하나씩 이용해서 분류한 값과 alpha 값의 곱을 누적시켜서 최종적인 분류를 하게 된다.


정리를 하자면 adaboost는 weak classifier 들의 집합을 만들고 그 weak classifier들의 분류값을 그 classifier의  정확도에 기반한 가중치(alpha) 의 곱의 합으로 새로운 데이터를 분류하게 된다.