[Data Mining] 11. Classification - Ensemble

Ensemble(앙상블)

앙상블(Ensemble)기법은 회귀나 예측모형을 만들때, 1개의 모델을 쓰지 않고 여러개의 모델을 융합해서 쓰는 기법이다. 다른 표현으로는 성능이 약한 여러개의 모델(weak learner)을 활용해 성능이 높은 모델(strong learner)을 도출한다고 한다.

앙상블 기법은 sampling 하는 방법이나 최종 의사결정을 내는 방법 등에 따라 아래 3가지 기법이 있다.

• Bagging : 전체 sample로 모형을 만드는 것이 아니라 k 개의 Bootstrap sample을 통해 k개의 모형을 학습하고, 새로운 sample이 들어왔을 때, k개의 예측결과의 다수결(분류문제의 경우) 혹은 가중평균(회귀문제의 경우)을 최종 예측결과로 도출(Aggregating)한다. 

• Boosting : sequential 하게 모델링 하면서 i-1번째 모델에서 잘 예측하지 못한 sample들이 i번째 모델의 학습데이터로 활용 될 수 있게 weight를 조정하는 방식으로 sampling 한다. 그리고 새로운 sample이 들어오면 k개의 예측결과를 살펴보고, 각 모델의 중요도(α)의 합이 큰 결과를 최종 예측 결과로 도출한다.

• Stacking : 전체 데이터로 모형을 k개 만들고, k개의 예측 결과를 입력으로 받는 모델을 추가로 학습한다. 다른 앙상블 알고리즘들에 비해 학습에 필요한 시간이 많은 편이다. (본 챕터에서 stacking은 다루지 않는다.)

Bagging(Bootstrap aggregation)

1) Bootstrap

Bagging은 Bootstrap과 Aggregating의 합성어이다. 때문에 Bootstrap의 의미부터 알아보자.

Bootstrapping이란 모집단의 통계량을 추정하기 위해 표본을 sampling하는데, 이 때「중복을 허용」하고 random하게 여러번 sampling 하는 기법이다. 이렇게 Bootstrapping 된 표본들의 통계량을 각각 구하면 모집단의 평균, 분포, 평균의 분포 등을 높은 확률로 추정할 수 있게 된다. 모집단의 분포를 모르거나, 측정된 샘플이 부족한 경우에 효과적인 일종의 over sampling 방법이다.

예를 들어 1000개의 데이터만 주어졌을 때 500개씩 충분히 많이 n번 bootstrapping (중복 허용 random sampling)하면 충분히 많은 n개의 데이터셋을 만들 수 있고, 이 bootstrap sample들의 통계량을 활용하면 다소 표본이 부족했던 모집단의 통계량을 추정할 수 있다.
※ 통계에서 말하는 복원추출(sampling with replacement)과 동일한 개념이다.

Out of Bag(OOB)

bootstrapping을 아무리 많이해도 1/3의 관측치는 선택되지 못한다. 예를 들어 900개의 원데이터가 있으면 300개는 학습에 쓰이지 않는다. 왜 그럴까? sample 한개가 뽑힐 확률은 1/900이고, 안 뽑힐 확률은 899/900이다. 이 확률에 따라 무한대로 sample을 하더라도, 뽑히지 않을 확률이 exp(-1) = 0.368 확률을 가진다. 이렇게 선택되지 못한 sample을 Out of Bag(OOB) 샘플이라 한다.

이렇듯 Bootstrap을 적용하는 Bagging 기법은 필연적으로 OOB 샘플이 전체 데이터의 33% 수준으로 존재한다. 그래서 많은 알고리즘들이 OOB 샘플을 validation sample로 활용해서 성능평가용 test sample로 쓴다. (대게 모델의 error = OOB error로 자동 도출된다.)

2) Aggregating

Bagging은 bootstrap sample을 만든 후(Resample1, 2 ... N) 각각의 예측모형(Model 1, 2, ... N)을 만들고, 모든 모델의 예측결과를 투표(vote)를 통해  최종 결과를 도출(Aggregating)하는 앙상블 기법이다. 이 때 각각의 모델은 ANN(Artificial Neural Network), Regression, Decision Tree 등 서로다른 다양한 모델이 적용될 수 있다.(통상 라이브러리로 구현되어 있는 것은 단일 모델을 셋팅하게끔 준비되어 있기도 하다.) 이렇게 다양한 sample으로부터 만들어진 여러 종류의 모델을 참고하기 때문에 어느 한쪽으로 편향되지 않는 효과(variance를 낮춰주는 효과 = overfitting 방지 효과)를 가진다.

※ 투표를 하는 방법은 여러가지가 있을 수 있고, 사용자가 직접 지정할 수 있다. 분류모형의 경우 통상 다수결로 선택하는데, 회귀문제의 경우는 가중평균을 사용하기도 한다. (앙상블 기법은 주로 분류기법에 사용된다.)

※ 만약 25개의 분류모형이 있고 error rate ε = 0.35(35%)의 낮은 확률을 갖는다고 가정하자. 이 25개 모델을 앙상블 시켰을 때, 절반 이상이 잘못 예측할 경우는 0.06 (6%)에 불과하다. 그만큼 앙상블 기법의 기대효과는 큰 편이지만, 경험상 실제로 이론처럼 극명한 발전을 보이지는 않는다.

※ Bagging을 적용하면 무조건 성능향상이 있을 것 같지만, 1개의 모델로 충분히 설명가능한 데이터에 대해 Bagging을 적용하면 시간만 오래 소비하거나, 오히려 성능이 낮아질 수도 있다. (ex. Bagging의 하이퍼파라미터를 잘못 선택했을 경우)

3) Bagging 사례 : Random forest

Random forest는 Bagging 기법의 대표적인 사례이다.

Random forest는 bootstrap sampling에 random 확률이 적용된다. 쉽게 말하면, k개의 독립변수가 있는 original 데이터를 bootstrapping 하는데, m개의 독립변수를 random하게 선택한다. 그렇기 때문에 'Random'이라는 키워드가 붙었다. (통상 m = √k)

그럼 'forest'란 키워드는 왜 사용할까? 바로 weak model에 해당하는 각각의 모델로 Decision tree를 사용하기 때문이다.(tree의 집단 = forest란 개념으로 이름이 붙었다.) 이 때 각각의 Decision tree는 fully grown tree로 만들어진다.

※ 사실 fully grown tree는 굉장히 높은 variance를 가진다.(나눠질 수 있는 최대한 나누기 때문에 overfitting 경향이 있다.) 하지만 각 모델의 학습데이터가 random하게 선택됐고(bootstrap), 여러 규칙의 모델이 복합적으로 작용했기 때문에 개별 모델의 variance를 낮춰주는 효과를 가진다.

[ Random forest의 장/단점 ]

• 어떤 변수가 중요한지(변수중요도)를 계산해주는 부가 기능이 있다. 

• missing 데이터에도 잘 맞고, unbalanced data에서도 balancing 효과를 보인다.
  → Random Bootstrapping의 효과

• 해석이 안된다. 변수중요도는 나올지 몰라도 어떤 규칙에 의해 예측되었는지는 알기 어렵다.
  ※ Random Bootstrapping의 효과로 모델을 학습할 때 마다 예측성능이나 변수중요도가 계속 변해서 사실 도출되는 장점이라 언급한 변수중요도도 믿기가 힘들다. 

[ 변수중요도를 도출방법 ]

• overall importance : 우리가 통상 알고 있는 개념이다. 부모노드에서 자식노드로 갈 때 감소하는 impurity를 보고 그 impurity가 큰 변수가 중요도가 높은 것으로 판단하는 개념이다. (가장 상위 분지를 담당하는 변수가 가장 중요도가 높다.)

• permutation importance : 특정한 변수의 값을 무작위로 shuffle했을 때 accuracy를 살펴보고, accuracy가 많이 변하는 변수는 중요도가 높다고 판단하는 것이다. shuffle의 의미는 다른 것이 아니라, 원래 값과 다른 임의의 값을 넣는 효과를 가진다. 만약 전혀 다른 값이 들어갔는데도 예측 성능에 변화가 없다면 그 변수의 중요도는 낮은 것.

Boosting

Bootstrap을 sampling 전략으로 가지는 Bagging과는 달리 Boosting은 다른 전략으로 sampling한다.

처음에는 전체 sample로 모델을 만들고 예측을 한다. 그럼 분명 예측에 실패한 sample들이 있을 것이다. 그럼 틀린 sample에 대해서 weight를 줘서 다음 sampling에 다시 뽑힐 수 있게 한다. 이 과정을 반복하면 예측을 잘 못한 샘플들을 더 자주 학습함으로써 bias를 낮춰줄 수 있다. 이처럼 Boosting은 sequential 하게 weighted sampling 하는 것을 확인할 수 있다.
※ 병렬적인 Bagging과 달라 직선적으로 sequential하게 팍팍 치고 나간다고 해서 Boosting이라 이름이 붙었다는 소리가 있다.

1) Adaboost (Adaptive boosting)

Adaboost는 대표적인 Bagging 기법 중 하나다. 각 단계별로 작동 원리를 알아보자.

[Step.1 initialize sample]

N개의 데이터(X1Y1 ... XNYN)가 있고, 각 샘플의 weight는 1/N으로 초기화 되어 있다.
※ weight가 높으면 sampling될 확률이 높다는 뜻이다. 처음에는 동일확률로 초기화.

[Step.2 initial model C0(x)]

그 뒤로는 일단 모형을 만들어서 예측해본다. 그리고 예측하여 잘 예측 한 것은 weight를 낮춰주고, 예측에 실패한 sample의 weight를 상승시킨다. 즉, 예측에 실패한 샘플이 다음 sampling때 한번 더 선택 될 가능성을 상승시킨다. weight를 조절 하는 방법을 수식으로 확인해 보자.

[Step.3 update sample's weight]

i번째 모델의 에러(εi)를 구할 때, 각 샘플의 weight까지 함께 고려(error의 weighted sum)한다. 즉, weight가 높은 sample이 틀린 경우 에러를 더 크게 판단한다.

에러(εi)로 부터 i번째 모델의 중요도가 계산(αi)될 수 있는데, α는 ε에 따라 우측과와 같은 curve를 가진다. 그래프를 해석하면 에러가 낮을수록 중요도가 높고, 에러가 0.5(50%)라면 중요도 = 0. 50%보다 에러가 크면 음(-)의 중요도를 가진다.

에러(εi)와 모델의 중요도(αi)가 계산 됐으니 이제 i+1번째 모델을 위한 sampling을 준비해야 한다. 즉, 예측에 실패한 sample들의 weight를 상승시켜야 하는데, 이 때 exp(±αi) 의 비율에 따라 update 해준다. 
※ 적중했을 때는 weight를 낮추고(exp(-α) < 1), 잘 적중하지 못했을 때는 weight가 커질 수 있게(exp(+α) > 1) update 해준다.
※ Zi =  normalization factor

[Step.4 iteration]

Step 2~3을 반복한다는 것은 매번 모델을 만들고(Ci) 예측한 다음, 예측에 실패한 sample의 weight 조정해서 또 새로운 모델(Ci+1)을 만드는 과정이며, 사용자가 지정한 T만큼 반복한다. 

위 과정에서 예측에 실패했던 sample들이 재차 학습데이터로 선택된다. 이 의미는, weak 모델이 잘 예측하지 못하는 경우를 보강하기 위해, 또 다른 weak 모델이 한번 더 학습한다는 뜻이다. 현실에 비유하자면 틀린문제를 몇 번이고 반복해서 풀어보는 것이다. 이렇게 틀린 문제를 반복학습하는 방식은 weak모델이 가진 높은 bias를 낮춰줄 수 있는 효과가 있다. (당연히 variance는 trade-off 효과로 상승한다.)

[Step.5 prediction]

사용자가 지정한 횟수(T)만큼 반복했거나, 더 이상 조정할 weight가 없게 되면 iteration이 종료된다. 여기까지오면 T개의 weak 모델과 각 모델의 중요도 αi가 도출되었을 것이다. 이제 이 정보를 토대로 새로운 샘플에 대한 예측을 해야하는데, 아래 예측식을 먼저 살펴보자.

최종 의사결정을 하는 strong 모델 C*는 범주별로 Σ(각 모델의 중요도 x 각 모델의 예측 결과)를 알아본 다음 가장 큰 값을 갖는 범주를 최종 예측값으로 선택한다. 보다 쉬운 이해를 위해 예제를 살펴보자.

Step.1 초기에는 모든 sample의 weight는 1/8로 초기화되어 있다.

Step.2 각 분류기는 Decision tree를 사용하였고, 초기 모형 C1을 만들었다. 1개의 sample이 틀렸고 (ε1 = 1/8), 이로부터 모델의 중요도 α1=0.973이 도출되었다.

Step. 3 다음은 틀린 sample에 대해 weight를 높혀줘야 한다.
이전 weight값에 exp(α1)을 적용하여 1/8=0.12 → 0.331 로 update한다.
적중한 sample 7개에 대해서는 exp(-α1)을 적용하여 0.12 → 0.047로 update한다.

Step.4 다음 sampling때는 weight가 높은(이전에 틀렸던) sample이 여러번 선택된 것을 확인할 수 있다. C2는 이전에 틀렸던 sample을 많이 가지는 데이터셋으로 학습했기 때문에 틀렸던 sample에 더 잘 적중하는 모델이 만들어질 것이다. 이렇게 6번을 반복해서 C6까지 도출한다.

Step.5 새로운 샘플이 들어왔을때 4개 모델은 Positive, 2개 모델은 Negative로 예측했다. 그래도 Adaboost는 다수결이 아니라 모델 중요도(α) x 예측확률의 weighted sum이 높은 것을 택한다. 

2) Gradient boosting

Gradient boosting은 Adaboost보다 좀 더 최근에 나온 boosting 기법이다. (1997)

Adaboost에서는 예측에 실패한 sample에 weight를 높혀 다음 sampling에 또 선택될 수 있게 해 주는 방법이었다면, Gradient boosting은 원리가 완전 다르다.

나이/키/성별로 몸무게를 예측하는 예제를 생각해보자.

처음에는 변수들간의 관계를 모르기 때문에 대충 모든 사람의 몸무게는 64라고 예측한 뒤 평가해보자. 평가를 해보면 첫번째 sample은 +9, 두번째는 -10, 세번째는 +1 의 잔차가 목격된다.

Gradient Boosting의 핵심 아이디어는 weak 모델이 잘못 예측했을 때 발생하는 잔차를 학습하는 것이다. 즉 y를 label로 하는 것이 아니라 잔차값들(h(x))을 label로 학습하는 것이다.

위 아이디어를 실현하기 위해서는 전체 잔차를 최소화 하는 목적함수가 필요하다. 다만 잔차는 부호가 있기 때문에 아래와 같이 OLE(Ordinary Least Square, 최소자승법) 모형을 사용할 수 있다.

사실 위 최소자승법 문제를 푸는 것은 단순회귀때와 마찬가지로 잔차로 미분해서 0이 되는 지점을 찾으면 된다. 

하지만 이렇게 풀지 않고 iterative하게(반복적으로) 잔차를 확인하는 방법으로 풀 수 있는데, 이 같은 원리를 Gradient decent(경사하강법) 라 한다.

결국 위 Gradient Decent 식은 위 그림과 같이 최소화 하는 방향으로 f(x)를 update하는 역할을 한다. 실제로 A지점에서 기울기 δJ/δF(xA) < 0 임으로 F(x)가 우측으로 증가(A→B)한다. 이렇게 경사를 타고 내려오는 행위(Gradient Decent)를 반복하다 보면 언젠가 잔차 J를 최소화 하는 f(xc)에 도달 할 수 있게 된다. 
※ 위 그림에서는 기울기( δJ/δF(x) )만큼 우측으로 이동했지만, 실제로는 0-1사이 값을 갖는 learning rate를 곱해줘서 조금씩 이동할 수 있게 한다.

위와 같은 학습원리를 일반화하여 Step별로 정리하면 아래와 같다.

• Step. 1 모델을 임의로 상수로 초기화 한다. (성능을 보장 못하는 상태)

• Step. 2 아래 행위를 반복한다.
   - 현재 모델로 예측을 수행한 후 잔차를 구한다.
   - 잔차를 terminal node로 가지는 regression tree를 학습한다.
   - 현재 잔차의 상태(기울기)를 파악한다.
   - 현재 잔차의 상태에 learning rate(0<ρ<1)를 적용하여 F(x)를 update한다. 

• Step. 3 지정한 횟수만큼 반복했거나, 잔차가 충분히 작아졌으면 반복을 멈춘다.

※ 교재에는 아래와 같이 멋진 수식으로 정리했지만, 해석하면 위의 절차와 동일하다. 수식을 외운다기 보다는 컨셉을 이해하자.

간단한 예제를 통해 Gradient Boosting의 원리를 복습하고 마치도록 한다.

• Step 1 : 임의의 상수로 모델을 초기화 하자. 여기서는 F(x) = 64로 초기화 했다.

• Step 2-1 : 당연히 오차가 날 수 밖에 없다. 잔차(h(x))를 계산하고 기억해두자.

• Step 2-2 : 잔차를 terminal node로 하는 regression tree를 학습한다.

• Step 2-3 : 잔차-f(x) 함수의 기울기(γ)를 파악한다.

• Step 2-4 : 기울기(γ) x 학습률(0.2)를 적용해서 원래값에서 빼준다.

1번 반복했더니 기존에는 모두 64로 예측했었는데, 실제값 쪽으로 조금씩 이동했다. 

이렇게 여러번 반복하면 F(x)-y가 0에 가깝게 수렴하면서 F(x)가 y에 가까워진다.