출처: Wikimedia Commons
🔗 관련 문서: Wikipedia - 결정 트리 학습법
결정 트리(Decision Tree)는 데이터를 여러 개의 질문(분할 기준)을 통해 가지(branch)를 나누어 나가면서, 최종적으로 예측이나 분류 결과를 도출하는 지도 학습(Supervised Learning) 알고리즘이다. 스무고개처럼 질문을 반복하며 데이터를 나누는 구조를 가지고 있어 직관적으로 이해하기 쉽다.
결정 트리(Decision Tree)는 데이터의 특성(feature)을 기준으로 조건을 만들고, 그 조건에 따라 데이터를 반복적으로 분할해 나가는 트리(tree) 형태의 예측 모델이다. 분류(Classification)와 회귀(Regression) 문제 모두에 사용할 수 있으며, 각각을 분류 트리(Classification Tree), 회귀 트리(Regression Tree)라고 부른다.
예를 들어 "오늘 야외 활동을 할 것인가?"를 결정하는 트리는 "비가 오는가?" → "바람이 부는가?" → "기온이 적당한가?" 와 같은 질문(분할 기준)을 순서대로 거치며 최종 결정을 내린다. 이처럼 결정 트리는 사람이 의사결정을 내리는 과정과 유사하여 결과를 해석하기 쉽다는 장점이 있다.
결정 트리는 다음과 같은 요소들로 구성된다.
결정 트리는 각 단계에서 데이터를 가장 잘 나눌 수 있는 분할 속성(splitting attribute)을 선택해야 한다. 어떤 속성이 "가장 잘 나눈다"고 판단하는 기준에는 여러 가지가 있으며, 대표적으로 엔트로피, 정보 이득, 정보 이득비, 지니 계수가 있다.
엔트로피는 데이터 집합이 얼마나 혼잡(불순)한지를 나타내는 지표이다. 엔트로피 값이 작을수록 데이터가 한쪽 클래스로 쏠려 있어 동질적(순수)이며, 값이 클수록 여러 클래스가 뒤섞여 있어 불순도가 높다.
$$H(S) = -\sum_{i=1}^{n} p_i \log_2 p_i$$
여기서 $S$는 데이터 집합, $p_i$는 집합 $S$에서 클래스 $i$가 차지하는 비율이다. 모든 데이터가 하나의 클래스에 속하면 $H(S)=0$(가장 동질적)이 되고, 클래스들이 균등하게 섞여 있을수록 $H(S)$ 값은 커진다.
즉 "균등한 비율로 섞여 있을수록 엔트로피가 작아진다"는 설명은 실제와 정반대로 서술된 것이므로 틀린 설명이다. 균등할수록 엔트로피는 커지고, 한쪽으로 쏠릴수록 엔트로피는 작아진다는 방향을 정확히 기억해야 한다.
정보 이득은 어떤 속성으로 데이터를 분할했을 때 엔트로피(불순도)가 얼마나 감소하는지를 나타내는 지표이다. 분할 전 엔트로피에서 분할 후 각 하위 집합의 (가중 평균) 엔트로피를 뺀 값으로 계산한다.
$$IG(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)$$
정보 이득이 큰 속성일수록 분할 후 불순도가 크게 줄어드는, 즉 데이터를 더 잘(동질적으로) 나누는 우수한 분할 속성이다. 결정 트리는 각 단계에서 정보 이득이 가장 큰 속성을 분할 기준으로 선택한다.
정보 이득은 범주(값)의 개수가 많은 속성일수록 유리하게 계산되는 편향이 있다. 예를 들어 고유값이 매우 많은 ID와 같은 속성은 정보 이득이 비정상적으로 크게 나올 수 있다. 이러한 편향을 보정하기 위한 지표가 정보 이득비이다.
먼저 속성 $A$ 자체가 얼마나 여러 값으로 데이터를 잘게 나누는지를 나타내는 분할 정보(Split Information)를 정의한다. 분할 정보는 속성 $A$의 값 분포에 대한 엔트로피로 계산된다.
$$SplitInfo(S, A) = -\sum_{v \in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}$$
정보 이득비는 정보 이득을 이 분할 정보(속성 자체의 엔트로피)로 나눈 값으로 정의한다.
$$GainRatio(S, A) = \frac{IG(S, A)}{SplitInfo(S, A)}$$
지니 계수는 엔트로피와 마찬가지로 데이터 집합의 불순도를 측정하는 지표로, CART(Classification and Regression Tree) 알고리즘에서 주로 사용된다. 값이 0에 가까울수록 순수한(동질적인) 집단이다.
$$Gini(S) = 1 - \sum_{i=1}^{n} p_i^2$$
여기서 $p_i$는 집합 $S$에서 클래스 $i$가 차지하는 비율이다. 지니 계수는 임의로 뽑은 데이터 하나에 임의의 클래스 레이블을 잘못 붙일 확률로도 해석할 수 있어, 값이 클수록 클래스가 고르게 섞여 있어(불순도가 높아) 잘못 분류될 가능성이 크다는 의미가 된다.
두 개의 클래스만 있는 경우, 지니 계수는 한쪽 클래스의 비율이 정확히 5:5로 균등할 때 최댓값 0.5를 가지며(불순도가 가장 높은 상태), 한쪽 클래스로 완전히 쏠려 10:0이 되면 최솟값 0이 되어 불순도가 가장 낮아진다(가장 순수한 상태).
비율이 6:4로 5:5에 가까울수록 지니 계수는 최댓값 0.5에 가까워진다. 따라서 이 데이터 세트는 비교적 불순도가 높은(두 클래스가 고르게 섞인) 상태임을 알 수 있다.
결정 트리를 생성하는 대표적인 알고리즘은 다음과 같다.
결정 트리는 끝까지 분할을 계속하면 훈련 데이터에 지나치게 맞춰져 과적합(Overfitting)이 발생하기 쉽다. 이를 방지하기 위해 트리의 크기를 제한하거나 불필요한 가지를 제거하는 가지치기(Pruning)를 수행한다.
장점
단점
Q. 결정 트리 학습 알고리즘에 대한 설명으로 옳지 않은 것은?