※ 이 포스팅은 아래 도서를 공부하며 정리한 글입니다.

<An Introduction to Statistical Learning (ISL)>, <Data Mining for Business Analytics (DMBA)>, <Applied Predictive Modeling>

Decision Trees, Bagging, Random Forests, Boosting
( 의사결정나무, 배깅, 랜덤 포레스트, 부스팅 알고리즘 )

#. Idea

의사결정나무의 가장 큰 아이디어는, 위에서 언급한 내용과 같이 입력변수의 공간을 서로 겹치지 않는 다차원의 직사각형들로 반복 분할하는 것이다.

결과적으로 위의 나무 그림처럼 기둥으로 시작해서 가지가 점점 얇아지고, 잎사귀까지 가서 예측 값이 산출되는 형태가 된다.

범주형은 뒤에서 다루고, 우선 수치형 출력변수에 대한 모형을 적합하는 문제를 생각해보자.

쉬운 예시를 위해, 입력변수가 2개(X1, X2)만 있는 상황을 가정하면 의사결정나무는 아래 그림과 같이 모형을 형성한다.

위 그림에서 R은 입력변수의 분할된 공간으로, 아래 수식과 같다.

수식에서 j와 s는 출력변수의 Residual Sum of Squares(RSS, 아래 수식) 를 최소화하는 특정 값으로 결정한다.

출력변수의 예측값(y_hat)은, 해당 분할된 입력변수 공간(R)에 대응되는 출력변수 훈련데이터의 평균을 이용한다.

여기에 입력변수를 3개로 확장하면, 다음 그림과 같이 분할되는 공간을 3차원으로 표현할 수 있다.

( 출처 : ISL )

입력변수가 범주형인 경우에는, 하나의 값과 나머지 값의 경우로 나누되 가장 낮은 RSS를 산출하는 것을 선택하면 된다.

예를 들어, 4개의 범주 {a, b, c, d}를 갖는 입력변수가 있다고 하자. 이를 두 하위집합으로 나눌 수 있는 7가지 방법이 존재한다.

{a} 와 {b,c,d} / {b} 와 {a,c,d} / {c} 와 {a,b,d} / {d} 와 {a,b,c} / {a,b} 와 {c,d} / {a,c} 와 {b,d} / {a,d} 와 {b,c}

( 참고로, 의사결정나무의 알고리즘 중 C4.5 는 범주의 종류만큼 분할하여 덤불나무와 유사한(bushlike) 구조를 만든다. )

출력변수가 범주형인 경우, 평균 대신 최빈값을 예측값(y_hat)으로 산출한다.

문제는 RSS인데, 분류 오차(classification error) 대신 아래 2가지 '순도(purity)'에 관한 지표를 사용한다.

(1) Gini Index

(2) Cross-entropy

위 수식에서 는 m번째 입력변수 공간 내에서 k번째 분류에 대한 훈련 데이터의 비율(proportion)이다.

두 수식을 잘 살펴보면, 가 0이나 1에 가까울수록 두 지표는 줄어들도록 정의되어 있어 '불순도(비동질성 척도)'라는 의미를 갖게 된다.

두 지표와 분류 오차의 차이점을 다음 그림을 통해 시각적으로 살펴보자.

( 출처 : http://blog.princehonest.com )

초록색은 Cross-entropy를, 붉은색은 Gini Index를, 파란색은 분류 오차다.

모두 분류 비율(x축)에 따른 변화의 양상에 차이는 없으나, 분류 오차보다 순도의 변화에 감도가 더 높기 때문에 사용한다고 알려져 있다.

#. 나무 가지치기 (Tree Pruning)

문제는 의사결정나무에서 입력변수의 공간을 언제까지 분할할 것인가에 있다.

극단적으로 더 이상 나눌 수 없을 때까지 반복적으로 입력변수의 공간을 분할하면, 주어진 훈련 데이터에만 성능이 좋게 되는 과적합(overfit) 문제가 발생한다.

아래 그림을 통해 자세히 알아보자.

( 출처 : 위키피디아 )

위 그래프에서, 붉은색 곡선은 검증 데이터셋에 대한 모형의 오류이고 파란색은 훈련 데이터셋에 대한 오류이다.

이처럼 검증 데이터셋에 대해서는 실제 입력과 출력변수간의 구조를 학습하는 단계까지만 오류가 감소한다.

그러나, 훈련(모델링) 단계에서는 훈련 데이터의 잡음들까지 학습하게 된다.

따라서, 훈련 데이터셋에 대해서는 지속적으로 오류가 감소하지만 어느정도 모형의 복잡도가 오르면 검증 데이터셋의 오류도 높아질 수 밖에 없다.

그렇기 때문에, 적절한 정도까지 나무를 성장(적합, 또는 입력변수 공간의 분할)시키는 것이 좋다.

적절한 분할의 정도를 결정하는 직관적 방법은, 모든 분할의 경우들을 개별 모형으로 산정하여 평가(validation) 데이터셋을 활용해 가장 성능이 좋은 것을 채택하는 것이다.

그러나 입력변수의 수가 많거나 데이터의 구조가 복잡할수록 그 경우의 수도 매우 다양해진다.

따라서 의사결정나무를 최대로 적합(더 이상 나눌 수 없을 때까지)한 다음, 모형의 복잡도를 비용으로 처리하여 의사결정나무의 결과물을 결정하는데 이를 '가지치기'라고 한다.

(입력변수의 공간을 분할할 때마다 가지가 하나 더 생기기 때문에, 가지치기라는 직관적인 이름으로 명명한 것 같다.)

구체적으로, 모형의 복잡도를 비용삼아 최적의 의사결정나무를 정하는 수식은 아래와 같다.

위 수식에서 |T| 는 최대로 적합한 의사결정나무에 존재하는 잎(끝마디, terminal node)의 수로서, 모형의 복잡도를 의미한다.

Rm은 m번째 잎에 대응하는 분할된 입력변수 공간이다.

알파(alpha)는 가지치기를 조정하는 매개변수(tuning parameter)이다.

의사결정나무 알고리즘에서, 잎의 개수별로 위 수식을 계산하여 가장 낮은 값을 산출하는 잎의 개수를 선택한다.

주목할 것은 알파인데, 알파 값이 클수록 수식의 결과도 커져서 최적의 잎 개수가 줄게 된다.

알파가 작아지는 반대의 경우는 수식의 값이 떨어져 최적 잎의 개수가 많아진다.

#. 최적의 가지치기 조정 매개변수 찾기 (find optimal tuning parameter of tree pruning)

알파 값은 어떻게 정할까? 의사결정나무 알고리즘은 K-fold 교차검증법을 활용한다.

방법은 다음과 같다.

(1) 조정 매개변수의 범위를 산정하고, 그 범위에 따라 특정(constant)한 값을 알파 값의 후보로 둔다.

(2) 훈련 데이터셋을 K개 fold 만큼 무작위로 관측수(observation)를 균등하게 나눈다.

(3) 각 k = 1, ... K 에 대해...

(a). k 번째 데이터셋을 훈련 데이터로 삼고 의사결정나무를 최대한으로 적합한다.

(b). 주어진 알파 값마다 위 수식을 활용하여 최적의 의사결정나무를 산출한다.

(c). 각 의사결정나무에 대해, 나머지 K-1개 데이터셋을 평가 데이터로 삼아 예측 오차를 구한다.

(4) 각 알파 값에 따른 예측 오차의 평균을 구한다.

(5) 가장 낮은 평균 예측 오차를 보이는 알파 값을 최적의 조정 매겨변수로 삼는다.

참고로, K는 훈련 데이터 갯수의 배수로 산정 수 있다.

가령 훈련 데이터의 관측(observation) 수가 132 면 K=6 이다. (ISL 310p.)

#. 분류 나무에서, 하나의 가지(branch)에 있는 두 끝마디(잎)의 값이 같은 경우

범주형 의사결정나무 즉, 분류 나무를 적합하다 보면 하나의 가지에 같은 예측 값으로 산출되는 때가 있다.

아래 예제 그림을 살펴보자.

( 출처 : ISL )

가장 왼쪽의 가지와 가장 오른쪽의 가지로 입력변수의 범위가 분할됐지만, 예측 값은 둘 다 같다.

그렇다면 이 가지는 쓸모 없는 것이 아닌가?

예측의 측면에서는 그렇다. 결국 모형의 예측 오차는 그 가지가 있으나 없으나 같기 때문이다.

하지만 이는 분할에 따라 '순도는 달랐으나 최빈값은 같았기 때문'에 발생한 결과임을 참고할 수 있다.

#. 의사결정나무의 장단점

예측력의 측면에서, 같은 훈련 데이터와 검증 데이터에 대해 모형의 예측 오차가 낮은 모형을 선택할 수 있다.

입력변수와 출력변수의 관계에 대한 해석의 측면에서는 두 모형 모두 적합한 후 더 직관적인 모형을 선택할 수 있다.

아래 그림을 살펴보자.

( 출처 : ISL )

윗줄에 해당하는 데이터셋의 경우, 예측력은 물론 해석의 측면 모두 의사결정나무보다 선형모형이 적합하다.

아랫줄은 의사결정나무가 더 나은 경우라고 볼 수 있다.

사실, 위 그림의 예와 같이 극단적인 경우는 드물다.

일반적으로 선형 모형보다는 의사결정나무가 해석이 용이하고 시각화하기 좋은 반면, 예측력은 떨어진다고 볼 수 있다.

나무 기반의 모형은 시스템적으로 자동화하기 매우 간편하며, 결측치를 하나의 경우(case)로 다루기 때문에 결측치에 대한 큰 부담이 없다는 장점이 있다.

더 나아가, 의사결정나무의 상단 부분에서 나타나는 변수들이 예측에 중요한 입력변수들이기 때문에 차원축소나 변수선택에도 활용할 수 있다.

또한, 나무 모형은 관측값(observation)의 절대적 '크기'가 아닌 '순서'를 활용하여 학습하므로 변수변환이 무의미하며 이상치에 대해 강건(robust)하다.

그러나, 이러한 특성은 반대로 데이터의 작은 변화에 따라 완전히 다른 분할 결과를 초래하기도 한다.

나무 모형은 모든 변수들에 대한 모든 가능한 분할을 순서에 따라 계산하기 때문에, 계산량 측면에서 상대적으로 많은 비용이 든다 할 수 있다.

#. Idea

배깅의 기본 아이디어는 각 관측값 집합(set of obs.)이 가진 분산에 평균을 취하면 최종 분산은 줄어드는 점에서 출발한다.

이를 통해 학습 결과의 분산을 줄일 수 있다면, 자연스럽게 학습 모형의 정확도 또한 올라갈 수 있다.

즉, 배깅은 모집단에서 다수의 학습 데이터셋을 취하고 각 학습 데이터셋마다 예측모형을 수립하여 평균을 취하는 아이디어를 활용한다.

이를 수식으로 표현하면 다음과 같다.

위 수식에서 함수(f)는 예측모형을, B는 학습 데이터셋의 총 개수, b는 각 데이터셋을 의미한다.

그러나, 일반적으로 학습 데이터셋을 여러개 얻는 것은 불가능하므로 여기에 부트스트랩을 활용하여 아이디어를 확장한다.

다시말해, 다수의 학습 데이터셋 대신 주어진 학습 데이터셋을 여러번 복원추출(sampling with replacement)하여 활용한다.

이를 다시 수식으로 표현하면 다음과 같다.

위 수식에서 *b는 부트스트랩한 훈련 데이터셋(bootstrapped training data set)을 의미한다.

추가로, 평균을 취할 수 없는 범주형 출력변수의 경우에는 '투표'의 의미로 평균 대신 최빈값을 취하면 된다.

이제 배깅을 의사결정나무에 적용해보자.

지금까지 설명한 것처럼, B개의 부트스트랩한 훈련 데이터셋을 만들고 각 *b의 데이터에 의사결정나무를 수립한다.

이 때, 각 의사결정나무는 가지치기 하지 않는데, 이는 각 모형의 분산을 의도적으로 높게 함과 동시에 편향성(bias)을 낮게 만들기 위함이다.

왜냐하면 배깅의 마지막 단계에서 각 모형에 평균을 취하기 때문에 분산이 낮아지기 때문이다.

참고로 배깅은 부트스트랩을 사용하기 때문에, 예측력 측정을 위해 따로 검증(validation) 데이터셋을 만들거나 cross-validation을 수행하지 않아도 된다.

#. B의 값은 어떻게 정하는가?

정확도의 측면에서 B는 크면 클 수록 좋다. B는 과적합(overfitting)과 상관 없는 부트르스랩 횟수이기 때문이다.

(그러나 실제 비즈니스 등에 배깅을 활용하는 경우 B가 클수록 모형 학습에 필요한 시간이 증가한다는 사실에 주의해야 한다.)

#. 결과의 해석 - Variable Importance Measures

배깅은 여러 나무를 적합(fitting)함으로써 예측력을 높이지만, 반대로 복잡하기 때문에 해석하기 어렵다.

하지만 RSS(Sum of Squared Residuals)나 분류의 경우 Gini index를 활용하여 예측의 측면에서 입력변수의 중요성을 확인할 수 있다.

구체적으로, 각 변수에 대한 나무의 가지로 인해 줄어든 RSS(또는 Gini index) 총 합을 B(부트스트랩한 훈련 데이터셋의 개수)로 나눈다.

이를 입력변수의 중요도(Variable Importance)로 삼아 값이 클 수록 해당 변수가 예측에 중요하다고 해석할 수 있다.

( 위 예시에서는 입력변수 'Thal' 가 예측에 가장 중요하다. 출처 : ISL )

그러나, 배깅 알고리즘에는 나무 상관성(tree correlation)이라는 한계점이 존재하며 이를 보완한 방법이 랜덤포레스트이다.

배깅의 한계점을 포함하여 랜덤포레스트를 정리해보자.

Random Forests, 랜덤포레스트

랜덤포레스트(Random Forests, 직역하면 무작위 숲들)는 나무들간의 관계성을 줄임(decorrelate)으로써 배깅보다 더 나은 성능을 제공한다.

나무들간의 관계성을 줄이는 방법은, 배깅에서 각 *b의 나무를 적합할 때 총 입력변수의 개수보다 적은 입력변수를 무작위로 추출해 활용하는 것이다.

#. Idea

왜 랜덤포레스트는 모든 입력변수를 사용하지 않는가?

예측에 중요한 소수의 입력변수들에 의해 각 *b 나무들의 결과가 서로 비슷해지면, 예측성능이 크게 향상될 수 없기 때문이다.

몇 개(가령 10개)의 입력변수가 있다고 가정해보자. 이 중, 하나의 입력변수 'A'가 예측에 매우 중요하고 나머지는 미미한 역할을 한다.

이 경우 각 *b 배그된(bagged) 나무들 대다수에서 입력변수 'A'가 최상위 가지 분할에 사용될 것이다.

결국 성능 향상을 위해 여러개의 나무를 적합했음에도 불구하고, 대부분의 나무들이 비슷한(correlated) 형태를 갖게 된다.

여러 나무들의 평균을 취하는 배깅의 특성상, 각 예측모형(나무)의 결과가 비슷하면 평균을 취해도 결과가 비슷할 것이다.

즉, 기본적인 의사결정나무 알고리즘 방법보다 높은 성능 향상을 기대하기 어렵다는 뜻이다.

랜덤포레스트는 배깅의 이러한 한계점을 극복하고자 모든 입력변수를 사용하지 않고 적은 수의 입력변수를 무작위로 선택한다.

(아마 Random Forests(직역하면 무작위 숲들) 라는 이름에는 이러한 속성의 의미가 담겨져 있다고 생각한다.)

이를통해 확률적으로 다른 변수들에게 예측에 활용될 기회를 줌으로써 나무들의 다양성을 확보할 수 있게 된다.

입력변수를 무작위로 선택한다는 점에서, 랜덤포레스트는 다중공선성(입력변수끼리 상관관계)이 존재할때 상대적으로 유리한 알고리즘이다.

#. Parameters

랜덤포레스트에서 분석가가 정하는 매개변수는 나무의 수(B)와 각 나무에 사용할 입력변수의 수(*p)이다.

아래 그림을 통해 살펴보자.

( 출처 : http://blog.princehonest.com )

위 그래프에서 연두색은 모든 입력변수를 사용한 경우(결국 배깅 알고리즘이다),

붉은색은 절반을 채택한 경우, 파랑색은 입력변수의 수에 제곱근을 취한 값으로 설정한 결과이다.

즉, 두 매개변수의 설정값에 따라 개별 모형으로 산정하고 모형의 예측력을 비교하여 최적의 값을 찾아내는 것이 하나의 방법이다.

일반적으로 출력변수가 수치형이면 p/3 을, 범주형이면 sqrt(p) 를 사용한다.

#. 결과의 해석 - Variable Importance Measures

랜덤포레스트 또한 마찬가지로 여러 나무를 적합하기 때문에 해석이 어렵지만, 배깅과 같은 방법으로 각 변수별 예측 중요도를 계산할 수 있다.

Boosting, 부스팅

배깅은 각 *b개마다 독립된 나무를 생성하지만, 부스팅은 이전에 적합된 나무의 정보를 활용하면서 생성해 나아간다. (the trees are grown sequentially)

또한 부스팅은 배깅에서 사용하는 부트스트랩 대신, 본래 데이터셋을 변형하여 모형을 적합한다.

#. Idea

부스팅은 모형을 순차적으로 만들어 나아가며 예측 성능을 향상해보자는 아이디어에서 출발한다.

즉, 모형을 적합하고, 여기서 실제 값과 예측 값의 차이인 잔차(residual)를 가지고 다시 모형을 재적합하는 방식을 반복하는 방법을 말한다.

이를 알고리즘적으로 정리하면 다음과 같다.

1. 으로, 그리고 훈련 데이터셋의 모든 개별 관측치에 대해 로 둔다. (r은 residual을, y는 출력변수를 의미한다.)

2. 총 횟수 B에 대해 b=1,2,...B 를 반복 수행한다.

(1) 출력변수를 y가 아닌 r로 삼고, d+1 개의 잎(끝마디, terminal node)를 가진 의사결정나무 를 적합한다.

(2)

(3) 

3. 결과적으로 부스팅 모형의 결과(output)는,  이 된다.

아이디어를 확장하면 부스팅 또한 배깅과 마찬가지로 다양한 학습 알고리즘에 활용할 수 있다.

참고로, 나무 기반의 부스팅을 부스트 나무(Boosted Tree)라고 부르기도 한다.

#. Parameters

부스팅은 B가 클수록 과적합의 문제가 야기될 수 있다. 따라서, 일반적으로 cross-validation을 통해 최적의 B를 추정한다.

부스팅은 랜덤포레스트보다 더 작은 B(smaller trees)로도 예측 성능상 충분한 경우가 많다.

이는 이전에 생성된 나무로부터 결과를 향상시켜 나아가는 부스팅의 알고리즘 때문이다.

람다는 수축 매개변수(shrinkage parameter)로서, 일반적으로 0.01이나 0.001로 설정한다.

아래 그림을 참고해보자.