[Data Mining] Ensemble : Bagging, Random Forest and Boosting

아 이제 Ensemble을 공부해보도록 하자. 참 이거 포스팅 순서가 엉망 진창이다. 그런데 이해해주시길 바란다. 공부하느라 요즘 만신창이가 되어가고 있다. Ensemble이 무엇인지 부터 설명해보자. 

영어 단어 Ensemble은 여러 가지를 합친다는 의미이다. data mining에서 ensemble이라고 하면 여러가지 model을 합친다는 것이다. 조금 더 정교한 결과를 얻기 위해서 합치는 것이다. 가령 아래의 경우 하나의 model으로는 정교한 classifier를 찾을 수 없다.

자 그럼 여기서부터 Bagging부터 조금 자세하게 이야기해보도록 하자. Bagging은 Bootstrap Aggreggating의 준말이라고 한다. 여기서 중요한 것은 sampling을 한다는 것이다.(sampling을 할 때 sampled data는 최대한 random해야된다.) 전체의 data로 하는 것이 아니고 sampling된 data로 classifier를 돌린다는 것이다. 아래와 같이 간단하게 두가지 sample을 가지고 이야기해보자. (sampling된 data는 테두리선을 빨간색으로 해놨다)

# sample1

# sample2

# sample3

sample1과 sample2 sample3를 놓고 보자. 저렇게 sampling하고 classifier를 돌리면 당연히 다른 결과가 나올 수 밖에 없다. 이것을 대략 합쳐보자.

각 영역이 어떻게 분류가 되는지 각각의 model 별로 봐보자.

이것을 majority voting bagging이라고 한다. 왜 majority voting인지는 위의 table을 보면 쉽게 이해할 수 있을 것이다. 이제 이렇게 나온 결과를 각각의 model1, model2, model3과 비교해보자. 합친 것이 더 error rate이 적다.

흠.. 세보니까 model1과 ensemble error개수는 같네... -_- 그런데 model 개수를 조금 더 늘리고 데이터를 조금 더 분산시키고 하면 분명히 ensemble error가 더 적을 것이다. 참고로 각 영역을 정하는 방법은 majority voting말고도 probability를 기반으로 정할 수 있다. 여기서 이것에 대한 자세한 이야기는 안 하련다.(나도 모르므로)

그 다음 해야할 이야기는 Random Forest이다. Random Forest는 위와 비슷한 개념인데 Tree에 특별히 더 잘 적용되는 것이라고 보면 된다. 우선 tree 기반의 classifier 하나를 정하자. Decision Tree로 정해보자. 그리고 sampling을 한다. random forest는 모든 feature를 다 사용하지 않는다. 특정 feature만 골라서 사용한다. 몇 개를 고르냐? 그건 자유다.(select n features) 몇 개를 하든 상관없다. 이렇게 몇 개 골라진 feature를 가지고 data를 classifier로 돌린다.

random forest를 통해서 영향력 있는 feature를 골라줄 수 있다. 

위의 source code와 그 밑의 결과는 아래의 링크에서 capture해왔다.

http://blog.datadive.net/selecting-good-features-part-iii-random-forests/

위의 결과를 보면, 각 feature가 얼마나 영향력이 있는 feature인지 ranking을 알 수 있다.

자 마지막으로 Boosting이다. 아 이거 생각하면 아오 맥주먹고 스트레스 풀고 싶어지는 그런 느낌이 든다고 할까? 공부할 때 Bagging, Random Forest는 1시간 반만에 끝냈는데 Boosting만 4시간 걸렸다. 왜 그렇게 걸렸는지 Boosting 설명하면서 이야기 해보려고 한다.

-------------------------------------------------------------------------------------------

Boosting 관련 내용은 아래의 포스팅에서 더 잘 설명해두었다. 너무 허접해서 다시 했다. (2016.09.11)

http://operatingsystems.tistory.com/entry/Adaptive-Boosting-Algorithm

-------------------------------------------------------------------------------------------

Boosting은 기본적으로 sampling을 하지 않는다. 기본적인 개념은 이렇다. weak learner로 strong learner를 만드는 것이다. weak learner가 뭐냐? 아주 simple한 classifier. 가령,

- 어른과 어린이를 구분할 때 키가 160 이상이면 어른 이하면 아이.

- 남자와 여자를 구분할 때, 머리카락 길이가 20센치 이상이면 여자 이하면 남자.

- 좋은 컴퓨터와 나쁜 컴퓨터를 구분할 때, 크기가 크면 나쁜 컴퓨터 작으면 좋은 컴퓨터. 

누가 봐도 제대로 잘 동작할 것 같지 않은 저런 weak한 learner들을 말한다. 위와 같은 대충대충의 기준으로는 제대로된 machine learning이 이루어지지 않는다. 그런데 저런거 한 100개 가져다 놓으면 꽤나 잘 동작한다는 것이 boosting의 원리이다. 그거를 어떻게 구현하냐?? weight을 통해 구현한다.

weak learner1를 통해서 대충 data를 classify 해보자. 그러면 맞은 것이 있고, 틀린 것이 있을 것이다. boosting은 여러 개의 weak learner를 사용한다고 했으므로, weak learner2를 사용해서 또 data를 classify 하는 것이다. 그런데 이때 처음에 weak learner1을 돌렸을 때 틀렸던 data들에 대해서는 조금 더 높은 weight을 두고 weak learner1에서 맞았던 data들에 대해서는 조금 더 낮은 weight을 두는 것이다. 

무슨 말이여? 싶을 것이다. 예제를 보자.

(단, a < 0.1 and b > 0.1, 최초 weak learner1을 돌릴 때의 weight은 1/datasize(10) = 0.1로 같게 설정한다.)

위의 예제는 아래의 링크에서 확인 가능하다.

http://www.csie.ntu.edu.tw/~b92109/course/Machine%20Learning/AdaBoostExample.pdf

그러면 0.1보다 작은 값 a와 0.1보다 큰 값b는 어떻게 만들어줄까? 틀린 개수/전체 개수, 즉 error rate(e)을 구해서(3/10 = 0.3) 아래의 식에 적용시켜주면 된다.

위의 식을 구하는 방법도 있지만, 그냥 그 부분은 생략하려고 한다. 그런데 왜 이거 공부하는데 오래 걸렸냐? 바로 weight을 어떻게 classifier에 적용시키냐는 것이다. 이거를 설명해둔 책이나 blog가 전혀 없었다. 결국 답은 stack overflow 사이트에서 찾았다. 답은... 참 어이없게도... "알아서" 이다. 적당히 알아서 적용하라는거다. 예를 들어, count-base classifier algorithm을 사용한다면, 1을 세지 말고 1*weight을 세라는 것이다. 혹은 sampling을 할 때 weight이 큰 것이 더 sampling이 잘 되도록 한다던지. 즉 "알아서" 이다. "고작?" 이거 찾으려고 4시간 걸린거다...

아무튼 이번 포스팅 여기서 마치려고 한다. 다음 포스팅은 아마도 classifier evaluation & cross validation이 되지 않을까 싶다.