8. 의사 결정 트리 (Decision Tree)

의사 결정 트리는 학습 데이터에 내재되어 있는 데이터의 패턴을 통해 데이터를 예측, 분류하는 모델이다.
개념적으로, 우리가 흔히 하는 스무 고개 놀이와 비슷하다.

If ~ Then 규칙으로 모델이 구현되기 때문에 모델의 판단에 대한 설명이 용이하며(Explainable), 데이터의 통계적 가정이 필요하지 않다.

그러나 의사 결정 트리를 생성하기 위해 많은 데이터가 필요하고, 시간이 많이 소요된다는 단점이 있다. 또한, 모델이 데이터에 민감하여, 학습 데이터와 테스트 데이터 간의 차이가 적어야 좋은 결과를 얻을 수 있다.

의사 결정 트리의 학습과 추론

모델의 학습은 다음 과정의 반복으로 이루어진다.

1. 설명 변수의 데이터를 2개 이상의 부분 집합으로 분리한다.
2. 분리된 집합을 다른 변수를 활용해 또 다시 분리한다.
3. 분리된 집합들의 데이터 순도가 균일해질 때까지(분류가 잘 될 때까지) 1,2를 반복한다.

추론은 분류 문제의 경우, 끝 노드의 데이터 중 가장 빈도가 높은 클래스로 분류하고, 회귀 문제의 경우 끝 노드 데이터의 평균으로 회귀한다.

분류를 수행하는 의사 결정 트리를 분류 트리, 회귀의 경우는 회귀 트리라 한다.

재귀적 분할 알고리즘

학습 단계 중, 분할을 담당하는 알고리즘은 다음과 같다.

• CART (Classification And Regression Tree)
• C4.5, C5.0
• CHAID (Chi-squared Automatic Interaction Detection)

분류 트리의 불순도 알고리즘

불순도 알고리즘은 각 재귀적 분할 알고리즘에서, 분할의 기준으로 사용된다.

• CART: 지니 지수 (Gini Index)
• C4.5: 엔트로피 (Entropy Index), 정보 이익 (Information Gain), 정보 이익율 (Information Gain Ratio)
• CHAID: 카이 제곱 통계량 (Chi-Squared Statistics)

회귀 트리

회귀 트리는 이름대로 회귀를 위한 트리이다.

CART 알고리즘으로 구현된 회귀 트리에서, 불순도 지표로 F 통계량과 분산 감소량이 사용된다. 이는 끝 노드의 평균과 예측값의 차가 최대한 작도록 한다.

불순도의 측정은 제곱 오차 합(Sum of Squared Error)로 측정하며, 성능 평가에는 RMSE를 사용한다.

그러나 회귀 문제에서는 대부분 신경망이나 회귀 분석이 더 유용하므로, 본 글에서 회귀 트리를 자세히 다루지는 않겠다.

트리 알고리즘에 따른 분할 방법

CART는 항목을 기준에 따라 2개의 집합으로 분리한다. 반면, C4.5, C5.0, CHAID는 2개 이상의 기준으로 분류한다.
이를 각각 이진 분할^{Binary Split}, 다중 분할^{Multi-way Split}이라 한다.

트리 알고리즘 비교

	CART	C4.5	CHAID
분류 트리	O	O	O
회귀 트리	O	O	X
예측변수	범주, 수치	범주, 수치	범주
불순도 알고리즘	Gini Index	Entropy	Chi-square, 통계량
분리	Binary	Multi-way	Multi-way
트리 생성	완전 트리 생성 후, 가지치기		최적 모형 개발
교차 검증	학습 데이터와 검증 데이터 분리	학습 데이터만 사용	X
개발연도	1984	1993	1980

CART (Classification And Regression Tree)

CART는 완전 트리를 생성한 후, 검증 데이터를 이용해 가지 치기 과정을 가진다. 불순도 알고리즘은 아래 지니 지수를 이용하는데, 낮을 수록 좋다.

$$G.I(A) = \sum^d_{i=1} (R_i(1-\sum^m_{k=1}p^2_{ik}))$$

$R$은 분할된 집단의 가중치를 의미하고, $p$는 각 집단에 속한 클래스의 비율이다. 예시를 보면 이해가 빠르다.

예시

어떤 쇼핑몰에서, 충성고객(LC)과 탈퇴고객(CC)를 구분하는데, 기준으로 성별을 사용한 트리가 있다고 하자. 이 트리의 지니 지수는 다음과 같이 구한다.

전체 고객은 $(LC: 5, CC: 5)$와 같이 존재하는데, 남성은 $(LC:5, CC:1)$, 여성은 $(LC:0, CC4)$ 존재한다고 하자.

남성과 여성 항목의 $1-\sum^m_{k=1}p^2_{ik}$는 다음과 같다.

남성: $1- (\frac{5}{6})^2 - (\frac{1}{6})^2 = 0.278$

여성: $1-0^2 - (\frac{4}{4})^2 = 0 $

이제 이 트리의 지니 지수는 다음과 같다.

$$ G.I(T) = (\frac{6}{10})(0.278)+(\frac{4}{10})(0) = 0.167$$

C4.5, C.5.0

C4.5는 정보이론에 기반한 불순도 알고리즘을 사용한다.

$$Entropy(A) = \sum^d_{i=1}R_i(-\sum^m_{k=1}p_k\log_2(p_k))$$

$\log$는 음수가 되기 때문에 마이너스를 붙여준다.

C4.5는 트리 수정 이후에 트리 수정 이전에 비하여 얻은 정보 이익을 높이는 방향으로 트리의 가지치기를 진행한다.

$$IG = E(Before)-E(After)$$

정보 이익율

정보 이익은 가지 수가 많아질 수록 높아지는 경향이 있는데, 이를 해결하기 위해 C4.5에서는 추가로 일종의 규제인 IV(Intrinsic Value)를 도입하여 가지가 많아질 수록 패널티를 부여했다.

$$IV(A) = -\sum^n_{k=1} \frac{1}{n}\log_2(\frac{1}{n})$$

$$IGR(A) = \frac{IG(A)}{IV(A)}$$

의사 결정 트리의 과적합

의사 결정 트리는 과적합에 취약한 단점이 있다. 

과적합 방지 기법으로 학습 중단과 가지치기 방법이 있는데, 학습 중단은 트리의 최대 깊이를 설정하거나, 노드 내의 최소 관측치 수를 설정하거나(너무 많이 분리되지 않도록), CHAID에서는 불순도 최소 감소량이라는 기법을 사용한다.

한편, 일단 모델을 완성시키고 필요없는 가지를 제거하는 가지 치기 방법도 있다. 이 방법은 학습 중단보다 성능이 우수하다.

랜덤 포레스트 (Random Forest)

랜덤 포레스트는 여러 개의 의사 결정 트리를 앙상블한 모델이다.

같은 데이터를 가지고는 항상 같은 의사 결정 트리가 생성되는데, 랜덤 포레스트는 이를 막기 위해 데이터에서 랜덤하게 표본을 추출하여, 여러 개의 트리를 모두 다르게 학습시킨다.

이후, 해당 트리들의 결과를 분류 문제라면 투표 방법, 회귀 문제라면 평균을 취하여 최종 결과로 사용한다.