[BDA 데이터 분석 모델링반 (ML 1) 14회차] 의사결정 트리(DT)
Decision Tree의 정의와 ML에서의 엔트로피와 지니계수 개념을 알아본다.
Decision Tree
tree 구조를 활용하여 entropy가 최소화되는 방향으로 데이터를 분류하거나 원하는 어떤 결과값을 예측하는 분석 방법
루트노드(Root Node) : 나무가 시작되는 노드
자식노드(Child Node) : 상위의 노드에서 분리된 하위 노드
부모노드(Parent Node) : 자식 노드의 상위 노드
중간노드(Internal Node) : 나무 중간에 위치한 노드로 루트노드 또는 최하위 노드가 아닌 모든 노드
가지(Branch) : 하나의 노드로부터 잎사귀 노드까지 연결된 일련의 노드들
잎사귀 노드, 끝노드(Leaf Node, Terminal Node) : 각 가지 끝에 위치한 노드
순수노드(Pure Node) : 해당 노드의 목표변수가 동일한 값이나 종류만 가지는 노드
깊이(Depth) : 가지를 이루고 있는 노드의 분리 층수
| 회귀 트리 | 기준 | 의사결정 나무 |
| 예측 | 목적 | 분류 |
| 앞노드의 변동 (분산/표준편차) 최소화 | 나무를 나누는 기준 | 최대한 동종의 클래스가 되도록 (불순도가 낮도록) |
| RMSE | 가지치기 기준 | 일반화 오차의 추정값 기준 |
Decision Tree 알고리즘 종류
| CART | C4.5 | CHAID | |
| 분류나무(분류) | O | O | O |
| 회귀나무(예측) | O | O | X |
| 예측변수 | 범주, 수치 | 범주, 수치 | 범주형만 가능 |
| 불순도 알고리즘 | Gini 지수 | Entropy | Chi-square 통계량 |
| 분리 | 이진분리 | 다지분리 | 다지분리 |
| 나무성장(멈추기) | 완전 모형 개발(가지치기) | 최적모형 개발 | |
| 가지치기(교차검증) | 학습데이터 → 검증데이터 | 학습데이터 | X |
Entropy
$$Entropy(A) = -\sum_{k=1}^{m}p_klog_2(p_k)$$
확률분포가 가지는 정보의 확신도 혹은 정보량을 수치로 표현한 것으로, 모두 동일한 카테고리라면 불확실성은 최소이므로,
엔트로피값은 0이 되며, 두 개의 카테고리가 정확히 절반씩 있다면, 불확실성이 최대이므로 엔트로피값이 1이 된다.
Gini Index
$$G.I(A) = \sum_{i=1}^{d}(R_i(1-\sum_{k=1}^{m}p_{ik}^2))$$
지니계수는 통계적 분산 정도를 정량화해서 표현한 값으로, 0과 1사이의 값을 가진다.
0에서 가장 평등하고, 1에서 가장 불평등하며, 지니계수가 낮을수록 데이터 균일도가 높다.
Recursive partitioning
트리에서 branch를 최대한 많이 만들어서 maximum homogeneity를 달성한다.
즉 데이터의 상태가 최대한 pure 한 상태가 되도록 가지를 생성한다.
미리 지정하는 사전 가지치기와 전체 Full Tree 생성 후 적절한 수준에서 결합하는 사후 가지치기가 있다.
Cost-Complexity Pruning
성능과 복잡도 사이에서의 균형을 찾는 것이 중요하다. 복잡도가 증가하면, 과적합될 가능성이 생기고, 단순하면, 데이터를 분류할 수 없다. 다양한 $\alpha$ 을 가지고 가지치기를 진행하고, 교차검증을 활용하여 $\alpha$ 을 선택한다.
$$CC(T) = Err(T) + \alpha \times L(T)$$
$CC(T)$ : 의사결정나무의 비용 복잡도(오류가 적으면서 terminal node 수가 적은 단순한 모델일수록 작은 값)
$Err(T)$ : 검증데이터에 대한 오분류율
$L(T)$ : terminal node의 수(구조의 복잡도)
$\alpha$ : Err(T)와 L(T)를 결합하는 가중치(보통 0.01 ~ 0.1)