[머신러닝/딥러닝] 3. Decision Trees

Decision Trees

[데이터마이닝, 트리기반모형]과 상당부분 내용이 겹치지만, 또 다른 시점으로 Decision Tree를 볼 수 있는 기회가 될 것 같다.

Decision Tree는 분류문제에 많이 쓰는 대표적인 모형 중 하나다.

그리고 독립변수 공간을 한번에 한개 변수의 경계치를 기준으로 분지(Axis-aligned partitioning) 하는 것을 기본으로 한다. (위 그림을 보면 뿌리노드에서는 X1을 기준으로 분지되었고 다음으로는 X2를 기준으로 분지되었다.)

결국 Decision Tree형에서 가장 중요한 것은 분지기준을 잘 찾아서 샘플을 분류하는 것인데, 이 목적을 달성하기 위해 분지기준은 불순도(impurity)가 감소하는 방향으로 분지한다. 

그리고 또다른 특징으로는 Tree모형은 Classification과 Regression 모두에 적용될 수 있다는 것이다. (CART : Classification and Regression Tree)

Classification Tree

Decision Tree의 가장 큰 특징은 Axis-aligned partitioning 기법이란 것이다. 

Axis-aligned라는 것은 "축에 수직한 기준으로 데이터를 나눈다."는 뜻인데, 위 그림처럼 x1=a를 기준으로 partitioning하고, 아직 완벽히 분류되지 않았다면 x2=b를 기준으로 partitioning 하는 방식으로 두 범주를 나눌 수 있다. 

위 예제와 같은 분류문제는 linear한 함수로 두 분류를 완벽히 분리할 수 없기 때문에 linear model로는 절대 풀 수 없다. 반면, Tree 모형은 비록 axis-aligned라는 제약이 있긴 하지만 이런 비선형 분류 문제도 쉽게 풀 수 있다는 아주 강력한 장점을 가지고 있다.

핵심기술은 당연히 분지(split)를 어떻게 할 지 결정하는 것이다. 

Decision tree는 분지를 했을 때 최대한 pure(순수)한 상황이 연출되도록 한다.

그럼 pure한 상황이란 것은 뭘까? 위 사례를 예로 들면 T1이 T2보다 purity(순도)가 높다고 표현한다. 즉, Terminal(종점) 노드에 다른 범주의 데이터가 섞여있지 않을 수록 pure한 것이다. 

반대로 표현하면 다른 범주의 데이터가 섞여 있으면 Impurity(불순도)가 높은 것이다. 즉, Decision tree는 Impurity를 최소화 하는 분지 조건을 찾는 것이다. 

그럼 가장 먼저 할 일은 바로 Impurity를 정량화 하는 것이다.
Tree의 Impurity를 측정하는 대표적인 방법으로는 Gini Impurity와 Entropy Impurity가 있다.

1. Gini Impurity

위 정의와 같이 (x, y)쌍으로 된 데이터 S가 있다고 가정하자.

S는 전체 데이터셋이며, y는 K개의 discrete한 값 즉, K개의 class 중 1개의 값을 가진다.
Sk는 y=k인 부분 데이터를 의미하고, 모든 부분 데이터의 합집합은 S이다. 

위 정의를 따를 때 데이터 S의 Gini Impurity는 아래와 같다.

식으로는 확 와닿지가 않는데 간단한 예제를 보자.

확실히 pure할수록 Impurity가 낮게 계산 되는 것을 알 수 있다.

위 예제에서 S2, S3의 Impurity를 구할 때 공통적으로 나타나는 특징이 있다.
즉, K=2일때 Impurity는 아래와 같이 계산할 수 있다.

지금까지 데이터 자체의 Impurity를 구해봤는데, 이번에는 Tree의 Impurity를 구해보자.

Decision tree는 어떤 임계값을 기준으로 T/F로 나뉘기 때문에 부모노드는 항상 둘로 나눠진다. 이때 왼쪽으로 나눠진 노드의 데이터를 SL, 오른쪽은 SR이라고 표현하면 아래와 같이 Tree의 Impurity를 계산할 수 있다.

마찬가지로 예제를 볼텐데, binary case를 가정해보자.

역시 상대적으로 pure한 Tree 1의 Gini Impurity가 더 낮게 측정된다.

※ 참고로 가장 Impurity가 높을 때는 Terminal node에 모든 class 데이터가 골고루 들어간 경우다. 위 경우 G(T3) = 0.5

2. Entropy Impurity

두 벡터간의 유사도를 알고 싶을때 우리는 두 벡터간의 거리를 구한다.
즉, 두 벡터간의 거리가 가까울수록 유사하다고 판단하는 것이고, 통상 Euclidean 거리를 많이 사용한다.

그럼 만약에 두 분포의 유사도를 알고 싶을때는 어떻게 구할까?
※ 아래 예제는 K = 4, 즉, class가 4개인 경우로 가정한 것이다.

가장 직관적으로 드는 생각은 pk와 qk끼리 각각 비교하면 될 것 같다.

그 기능을 구현한 것이 KL-divergence인데(분포는 거리라고 표현하기 어려워 divergence로 지칭)
p분포와 q분포의 비유사성을 측정하는 KL-divergence를 구하는 식은 아래와 같다.

여기서 한 가지 가정을 해보자.

우리가 Gini Impurity에서 경험했듯 가장 Impure(불확실)한 경우는 아래와 같은 경우다.
(Terminal node에 남은 샘플이 각 class 별로 동일한 갯수가 있는 경우)

만약 p와 비교대상인 q가 worst case를 만족한다면?

위와 같은 가정에서는 p와 q간의 KL-divergence가 클수록 p는 pure하다고 할 수 있다.
(Impure한 경우와 유사하지 않을 수록 Pure하다. 참고로 KL-divergence가 클수록 유사하지 않다.)

위 가정에 의한 KL-divergence를 구해보자.

위 가정에 의해 -Σlog(q)는 log(K)와 같고 Σ(p) = 1 인 것을 적용해서 위와 같이 divergence를 구할 수 있다. 그리고 이렇게 구한 divergence가 크면 클수록 q는 pure하다고 할 수 있다.

p를 최대한 pure하게 만들기 위해 max 함수를 취하면 상수항 log(K)가 날라가게 되는데, 

이 조건은 바로 entropy H(p)를 최소화 하는 것과 완전히 동일하다.
결론적으로 entropy function을 decision tree의 impurity function으로 사용할 수 있다.

하지만 사실상 Gini impurity를 쓰나 entropy impurity를 쓰나 성능에 엄청난 영향을 주지 않기 때문에 어떤 impurity function을 쓰든 크게 상관은 없다. 

우리가 기억할 것은 Decision tree는 Impurity를 최소화 하는 sub tree를 결정하면서 split하는 모델이고, Impurity는 Gini나 Entropy function으로 정량적 산출이 가능하다는 것이다.

실제로 가장 처음 선보인 예제를 다시 한번 보면, Impurity를 가장 빨리 낮출 수 있는 방향으로 분지하기 때문에 a→b→c→d 순으로 분지하는 것을 확인할 수 있다. 

Regression Tree

Tree로 Regression하는 방법은 다소 다르다. 결론부터 말하자면 Gini나 Entropy Impurity를 쓰지 못하고 Squared loss impurity를 사용한다.

즉, 분지(split)했을 때 분지된 각각의 노드에서의 평균값을 예측값으로 사용한다. 그럼 어떤 모양으로 fitting 되는지 알아보자.

• Tree의 깊이 = 1일때, ①에서 분지됐다고 하자. 만약 여기서 멈춘다면 왼쪽구역과 오른쪽구역은 각각의 평균값을 예측하는 모델이 된다. (회색)

• Tree의 깊이 = 2일때, ②를 기준으로 좌우측의 평균값을 예측하는 모델이 된다 (파란색)

• Tree의 깊이 = 3일때, ③을 기준으로 또 모든 노드가 반으로 갈라지며 초록색 선과 같은 회귀 모델이 만들어 진다.

확실히 Tree의 깊이가 깊어질수록 분지구역이 작아지면서 정밀한 회귀모형이 될 수 있다. 실제로 위 가정을 Python에서 구현했을 때, 아래와 같이 유사한 결과를 얻을 수 있다. 

import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

# Create a dataset
rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()

# Fit regression model
dtr = DecisionTreeRegressor(max_depth=3)
dtr.fit(X, y)

# Predict
X_test = np.arange(0.0, 8.0, 0.01)[:, np.newaxis]
y = dtr.predict(X_test)

# Plot the results
plt.figure()
plt.scatter(X, y, s=20, edgecolor="black",
            c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue",
         label="max_depth=3", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

regression의 원리를 살펴보니 depth를 깊게준다면 복잡한 비선형 패턴도 예측 할 수 을 것 같다. 실제로 regression tree는 높은 성능과 빠른 속도를 자랑한다.

반면, 가장 큰 단점은 extrapolation한 경우에는 성능을 전혀 보장하지 못한다. 왜냐하면, regression tree는 데이터를 discrete하게 구역화해서 discrete한 값을 갖게 하는 모형이기 때문이다. 다르게 표현하면, regression tree는 사실 continuous real number를 아주 작은 단위로 class를 쪼개서 classification 한다고 할 수 있다. 

그렇기 때문에 학습하지 않은 영역에서는 전혀 예측할 방도가 없고, 위 Python 예제에서도 5이상의 영역에서는 전혀 실력을 발휘하지 못한다.

참고로 이런 특징 때문에 Tree를 기반으로 한 앙상블 모델들, 엄청난 성능을 보이는 Random Forest, XGBoost도 regression 문제를 풀때 extrapolation 영역에서는 매우 약한 모습을 보인다.

Bagging & Random Forests

※ Bagging과 RF에 대해서는 [데이터마이닝:앙상블] 수업에서 훨씬 더 자세하고 알기 쉽게 설명해서 해당 글을 참고하는 것이 더 좋을 듯 하다. 아래는 데이터마이닝 수업 중 Bagging과 RF에 대한 본문을 복사한 것이다. 

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 set로 활용해서 성능평가용 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의 의미는 다른 것이 아니라, 원래 값과 다른 임의의 값을 넣는 효과를 가진다. 만약 전혀 다른 값이 들어갔는데도 예측 성능에 변화가 없다면 그 변수의 중요도는 낮은 것.