본 포스팅에서는 기본적인 의사결정나무 알고리즘에 대한 설명은 제외하고 ID3에 대한 특이점만 다룰 것이다.
Taeyang Yang님의 블로그의 글을 대부분 참조하였다.
ID3 알고리즘
ID3 알고리즘은 Iterative Dichootomiser 3의 약자이다. Dichotomiser는 "이분하다"는 뜻의 프랑스어로, 반복적으로 이분하는 알고리즘이라고 할 수 있다.
이 전 포스팅에서 의사결정 나무의 분기는 불순도(impurity) 값이 작은 방향으로 이루어진다고 설명했다. ID3 알고리즘은 불순도 값으로 엔트로피(entropy)를 사용한다. 이는 독립변수가 모두 범주형일때만 가능하다는 단점이 있다.
(연속형 변수도 가능하도록 발전한것이 C4.5 알고리즘이다.)
ID3의 impurity : 엔트로피(Entropy)
흔히 무질서도라고 불리우는 엔트로피는 사건의 집합 $S$에 대한 불확실성의 양을 나타낸다.
정보량 (Information)
정보이론 측변에서 사건 $X_i$가 갖는 정보량은 다음과 같이 계산된다.
$$information = I(x) = log_2{1\over p(x)}$$
정보량은 놀람의 정도라고 이해할 수 있는데, 자주 관찰할 수 없는 사건일 수록 더 많은 정보를 내포하고 있음을 의미한다. 확률량에 따른 정보량의 관계는 위 그림을 통해 확인할 수 있다.
엔트로피(Entropy)
$$Entropy = -\Sigma_{i=1}^c p_i log2 p_i$$
Information Gain
ID3알고리즘에서는 entropy 값의 변화량을 나타내기 위해 information gain이라는 개념을 사용한다.
- $H(S)$ : 분기 전 엔트로피
- $H(S, True)$: 분기 후 True에 해당하는 그룹의 엔트로피
- $H(S, False)$: 분기 후 False에 해당하는 그룹의 엔트로피
Information Gain은 아래 수식과 같이 분기 전후 엔트로피의 차이값으로 계산된다. 이 때 분기 후 엔트로피는 양쪽 가지로 나뉘는 확률 $p(t_i)$를 가중치로 곱해 합쳐진다.
최적의 Decision Tree를 만들기 위해, 여러 지표 중 분기 후 엔트로피 가 작아지는 지표를 선택해야 합니다. 분기 전 엔트로피 $H(S)$는 동일하니, 이 말은 Information Gain이 가장 큰 지표를 선택하라는 말과 동일하다.
Reference
'Machine Learning' 카테고리의 다른 글
| 배깅 앙상블 (Bagging Ensemble): Random Forest (0) | 2022.04.04 |
|---|---|
| 앙상블 (Ensemble)의 개념 (0) | 2022.04.04 |
| 의사결정나무, Decision Tree (0) | 2022.04.04 |
| 분산과 편향 차이 이해하기 (bias vs variance) (0) | 2022.04.04 |
| 선형회귀(Linear Regression), Lasso, Ridge 이해하기 (0) | 2022.03.31 |
댓글