Decision Tree

의사결정나무는 여러 트리 모델의 기반이 되는 모델이다. 

복수의 의사결정나무를 배깅(Bagging) 이나 패이스팅(pasting) 방식으로 앙상블하면 Random forest, Extrea trees 등이 되고,

부스팅(Boosting) 방식으로 앙상블하면 Xgboostm, LGBM, Catboost와 같은 모델이 된다.

 

1. Decision Tree

데이터를 어떤 특성의 임곗값을 기준으로 분류하는 모델로, 가지를 뻗는 나무를 닮아 ‘결정 트리’라고 불린다. (스무 고개와 유사한 개념)

분류, 회귀에 모두 사용 가능하다.

Decision Tree에서 분류 질문과 정답을 담은 상자를 노드(node)라고 정의하며 아래와 같이 구성된다.

• Root node: 깊이 0인 맨 꼭대기의 노드
• Child node: 상위 노드에서 파생된 자식 노드
• Intermediate node: 중간 위치의 노드
• Leaf node: 자식 노드가 없는 노드(마지막 노드)

(참고로, 이 글에서는 붓꽃 분류 문제를 예시로 사용한다. 꽃잎의 너비와 길이를 입력(X)로 하여 3가지의 붓꽃 종류(Y)를 분류하는 문제이다)

 

트리가 분기를 거듭할 수록 Node가 아래로 뻗어가는데, 이를 깊이가 깊어진다고 표현한다.

학습된 모델에 새로운 샘플을 입력으로 넣으면 학습된 분기 기준에 따라 자동으로 분류된다.

예를 들어, 꽃잎 길이가 5cm, 너비 1.5cm인 새로운 샘플 x를 해당 모델에 입력하면 학습된 분기 기준을 따라 초록색 Leaf node에 할당될 것이다.

학습 결과에서 초록색 Leaf node에는 총 54개의 샘플이 할당되었고 그 중 Vesicolor class가 49개로 가장 높은 비중을 차지하므로, 모델은 초록색 Leaf node에 들어온 샘플은 Vesicolor class로 판단하며 그 확률은 90.7%(49/54개)이라고 한다.

즉, 새로운 샘플 x 또한 초록색 Leaf node에 할당되었으므로, Vesicolor class로 판단하며 그 확률은 90.7%(49/54개)로 추론한다.

 

아래 그림은 학습 결과를 그래프로 표현한 그림이다. (원: Setosa, 네모: Vesicolor, 세모: Virginica)

깊이 0: $꽃잎 길이 \leq 2.45$ 분기 기준에 의해 모든 Setosa 학습 샘플이 분류되었다.

깊이 1: $꽃잎 너비 \leq 1.75$ 분기 기준에 의해 대부분의 Vesicolor, Virginica 샘플이 분류되었다.

깊이 2: $꽃잎 길이 \leq 4.9$, $꽃잎 길이 \leq 4.7$ 과 같이 node를 추가한다면 Vesicolor, Virginica 샘플이 그림과 같이 다시 분류될 것이다.

 

Node에 의해 분기해가면서 모델이 생성되는 것을 알았는데, 그렇다면 분기의 기준은 어떻게 결정될까?

 

바로 불순도가 분기 기준이 된다.

여기서 불순도는 어떤 샘플 집합이 얼마나 다양한 클래스의 샘플로 이루어져 있는지를 계산한 것이다.

보통 'Gini 불순도', 'Entropy 불순도'가 있는데 기본적으로는 'Gini 불순도' 를 주로 사용한다.

 

Gini 불순도란?

수식 먼저 보는 게 편할 것 같다. 수식은 아래와 같다.

[0,1]의 범위를 가지며, 어떤 노드의 불순도 값이 0이면 모든 샘플이 같은 클래스에 속하는 것으로 순수하다고 한다.

위의 모델 예시에서, 초록색 노드의 Gini 불순도를 계산하면 아래와 같다.

0.168이면 꽤나 순수하다고 할 수 있겠다(?)

Entropy 불순도란?

한편, Entropy 불순도는 값이 0에 가까울 수록 분자가 안정된다는 열역학의 엔트로피 개념을 빌려왔다. ML/DL에서는 정보이론의 Cross entropy, KL divergence 등 개념까지 확정되어 자주 사용된다.

[0,1] 범위를 같고, 값이 0이면 모든 샘플이 같은 클래스에 속하는 것으로 불확실성이 없다는 의미이다 (즉, 순수하다.)

수식은 아래와 같다. 

(p는 Gini의 p와 같은 의미이다.)

 

CART 훈련 알고리즘

결정 트리는 위와 같이 계산한 각 노드의 불순도를 최소화하는 것을 목표로 학습된다. 그래야 최대한 동일한 클래스끼리 묶어서 분류할 수 있기 때문이다.

그리고 각 노드의 불순도를 최소화하도록 학습하는 알고리즘이 CART 훈련 알고리즘이다.

아래는 CART 비용 함수이다. (G는 불순도)

 

 

CART 알고리즘의 프로세스는 다음과 같다.

1) 우선, 노드를 생성하기 위해 랜덤하게 특성들을 선택한다.

2) 그리고 선택한 특성 k의 임곗값 $t_{k}$를 사용해 학습 데이터를 두 개의 서브셋으로 나눈다. (특정 기준을 만족하는지에 대한 True, False 서브셋)

• 예를 들어, 특성 k > 임곗값$t_{k}$ (잎의 길이 > 2.5cm)

3) 그 다음, 아래 비용함수를 이용하여 현재 노드에서 불순도를 최소화하는 (k, $t_{k}$)를 탐색한다. 

• 깊이 n의 노드를 최적으로 나눈 후에, 그 다음 노드(자식 노드, 깊이 n+1)의 불순도를 최소화하는 식으로 학습된다
• CART 알고리즘은 트리 전체가 아닌 현재 노드만을 고려하여 최적화 하므로 이를 탐욕적 알고리즘이라고 한다.

 

모델 학습 전에 다양한 파라미터를 이용해서 모델의 자유도를 제한할 수 있다. 모델의 매개변수를 조절 후 학습하여 과대, 과소적합을 방지할 수 있다.

아래는 사이킷런에서 제공하는 매개변수 종류이다.

• max_depth: 결정 트리의 최대 깊이
• min_samples_split: 분할되기 위해 노드가 가져야 하는 최소 샘플 수
• min_samples_leaf: 리프 노드가 가지고 있어야 할 최소 샘플 수
• min_weight_fraction_leaf: min_samples_leaf와 같지만 가중치가 부여된 전체 샘플 수에서의 비율
• max_leaf_nodes: 리프 노드의 최대 개수
• max_features: 각 노드에서 분할에 사용할 특성의 최대 개수

Min_으로 시작하는 매개변수를 증가시키거나, max_로 시작하는 매개변수를 감소시키면 모델에 규제가 커진다. 즉, 과대적합을 방지하는 효과가 있다.

 

이제까지 분류 문제를 기준으로 설명했는데, 앞서 언급했듯이 트리 모델은 회귀 문제에도 사용이 가능하다.

분류와 유사하게 학습되나, Leaf node가 특정 값을 예측한다는 점이 주요 차이점이다. 

아래와 같이 CART 알고리즘에서 Gini 불순도 대신 평균제곱오차(MSE) 등 회귀문제 Metric을 최소화하도록 분할된다.

 

또한, 각 Leaf node 구간의 샘플 평균값이 예측값이 된다.

예를 들어, 아래 그림의 모델에서 $x_{1}=0.3$ 이면 왼쪽에서 세번째 Leaf node의 평균값인 0.111이 추론 값이 될 것이고,

 $x_{1}=0.9$ 이면 왼쪽에서 네번째 Leaf node의 평균값인 0.615가 추론 값이 될 것이다.

 

모델의 깊이를 늘리면 각 Leaf node에 해당하는 구간이 더욱 세세하게 나눠진다.

아래 그림에서 Max depth가 2에서 3으로 늘자 구간이 더욱 세세하게 나뉜것을 알 수 있다.

추론 결과가 계단 모양을 띄는 것은 위에서 말했듯이 평균값을 출력으로 하기 때문이다. 

 

또한, 특정 값을 Leaf node로 하기 때문에, leaf node의 최소 데이터 개수를 늘리면 과적합을 방지할 수 있다. 각 Leaf node의 결과가 최소한 n개의 샘플을 반영해야 한다는 의미의 규제이다.

예를 들어, Max depth가 매우 크고, leaf node의 최소 데이터 개수가 매우 작으면 수많은 Leaf node가 생성되면서 아래 왼쪽 그림처럼 과적합된 결과를 보일 수 있다.

하지만, Leaf node의 최소 데이터 개수를 적절한 크기로 조절하면 아래 오른쪽 그림처럼 적당하게 학습될 것이다.

 

 

참고자료

1. 핸즈온 머신러닝