ID3 알고리즘
의사결정 트리(Decision Tree)는 다양한 알고리즘을 통해 발전되어 왔습니다.
다양한 알고리즘의 첫걸음은 바로 ID3 (Iterative Dichotomiser 3) 알고리즘입니다.
1980년대 Ross Quinlan에 의해 개발된 ID3는 머신러닝 분야에 정보 이론(Information Theory)의 개념을 도입하여 데이터를 분류하는 강력하고 직관적인 방법을 제시했습니다.
즉 ID3는 "어떻게 질문을 던져야 데이터를 가장 효율적으로 나눌 수 있을까?"라는 질문에 대한 수학적인 해답을 제시한 알고리즘입니다.
1. 🎯 엔트로피 (Entropy)
ID3의 모든 것은 엔트로피에서 시작합니다. 엔트로피는 원래 물리학에서 '무질서도'를 측정하는 개념이었지만, 정보 이론에서는 데이터 집합의 '불확실성' 또는 '불순도'를 측정하는 지표로 사용됩니다.
- 엔트로피가 높다 (High Entropy): 데이터가 마구 섞여 있다. (예: 한 상자에 파란 구슬 50개, 빨간 구슬 50개가 섞여 있어, 하나를 뽑을 때 결과를 예측하기 어렵다.)
- 엔트로피가 낮다 (Low Entropy / Purity): 데이터가 한쪽으로 치우쳐져 순수하다. (예: 상자에 파란 구슬 100개만 들어있어, 불확실성이 0이다.)
ID3의 최종 목표는 데이터를 계속 쪼개나가서, 각 리프 노드(최종 노드)의 엔트로피가 0이 되도록(즉, 완벽하게 순수해지도록) 만드는 것입니다.
엔트로피 수식 정의
데이터 집합 S가 총 C개의 고유한 클래스(범주)를 가질 때, 엔트로피 H(S)는 다음과 같이 계산됩니다.
H(S) = - [ (p1 * log2(p1)) + (p2 * log2(p2)) + ... + (pC * log2(pC)) ]
즉, 각 클래스(i)에 대해 [ (클래스 i의 비율) × log2(클래스 i의 비율) ]을 계산하여 모두 더한 값에 마이너스를 붙인 값.
- pi: 전체 데이터 집합 S 중에서 클래스 i에 속하는 샘플의 비율(확률)을 의미합니다.
(예: S에 [Yes 9개, No 5개]가 있다면, pYes = 9/14 이고 pNo = 5/14 입니다.)
엔트로피 값의 의미
- H(S) = 0 (최소값):
- 엔트로피가 0이라는 것은 불확실성이 전혀 없다는 뜻입니다.
- 해당 노드의 모든 데이터가 하나의 동일한 클래스로만 구성된 "순수한(pure)" 상태입니다. (예: [Yes 14개, No 0개])
- (pi가 1 또는 0이 되어 log2(1)=0, 0*log2(0)=0 (근사)이 됩니다.)
- H(S) = 1 (최대값, C=2일 경우):
- 엔트로피가 최대라는 것은 불확실성이 가장 높다는 뜻입니다.
- 데이터가 모든 클래스에 걸쳐 균등하게 분포되어 있을 때 발생합니다. (예: [Yes 7개, No 7개])
- 이 경우 pYes = 0.5, pNo = 0.5 이며, 엔트로피는 -(0.5 * log2(0.5) + 0.5 * log2(0.5)) = 1이 됩니다.
ID3 알고리즘은 이 엔트로피 값을 정보 이득(Information Gain) 계산에 사용하여, 분기 후 엔트로피가 가장 많이 감소하는(가장 순수해지는) 속성을 찾아냅니다.
2. 💡 정보 이득 (Information Gain)
정보 이득은 "특정 속성(질문)으로 데이터를 나눴을 때, 엔트로피(불확실성)가 얼마나 많이 줄어들었는가?"를 수치화한 값입니다.
정보 이득 (Attribute) = 부모 노드의 엔트로피 - (자식 노드들의 가중 평균 엔트로피)
ID3 알고리즘은 질문할 수 있는 모든 속성에 대해 이 정보 이득을 각각 계산한 뒤, 그 값이 가장 큰 속성을 최적의 분기 기준으로 선택합니다.
정보 이득이 가장 크다는 것은 분기를 통해 불확실성을 가장 크게 줄여주는 베스트 질문인 셈이죠.
[예시]
10명의 학생 데이터(5명 합격, 5명 불합격)가 있다고 가정해 봅시다. 이 데이터는 합격과 불합격이 정확히 반반 섞여있어 현재 엔트로피가 1.0입니다.
| 속성 A. 공부 여부 | 속성 B. 수면 시간 | 결과 |
| 공부함 | 8시간 이상 | 합격 |
| 공부함 | 8시간 이상 | 합격 |
| 공부함 | 8시간 이상 | 합격 |
| 공부 안 함 | 8시간 이상 | 불합격 |
| 공부 안 함 | 8시간 이상 | 불합격 |
| 공부함 | 8시간 미만 | 합격 |
| 공부함 | 8시간 미만 | 합격 |
| 공부함 | 8시간 미만 | 불합격 |
| 공부 안 함 | 8시간 미만 | 불합격 |
| 공부 안 함 | 8시간 미만 | 불합격 |
- 질문 1 (속성 A: 공부 여부)로 나눴을 때:
- "공부함" 그룹(6명): [합격 5, 불합격 1] (매우 순수함, 엔트로피 낮음)
- "공부 안 함" 그룹(4명): [합격 0, 불합격 4] (완벽히 순수함, 엔트로피 0)
➡️ 자식 노드들이 매우 순수해졌으므로(불확실성이 크게 줄었으므로) 정보 이득이 높습니다."공부함" 그룹 (6명)
공부 여부 수면 시간 결과 공부함 8시간 이상 합격 공부함 8시간 이상 합격 공부함 8시간 이상 합격 공부함 8시간 미만 합격 공부함 8시간 미만 합격 공부함 8시간 미만 불합격 "공부 안 함" 그룹 (4명)
공부 여부 수면 시간 결과 공부 안 함 8시간 이상 불합격 공부 안 함 8시간 이상 불합격 공부 안 함 8시간 미만 불합격 공부 안 함 8시간 미만 불합격
- 질문 2 (속성 B: "수면 시간")로 나눴을 때:
- "8시간 이상 잠" 그룹(5명): [합격 3, 불합격 2] (여전히 섞여 있음, 엔트로피 높음)
- "8시간 미만 잠" 그룹(5명): [합격 2, 불합격 3] (여전히 섞여 있음, 엔트로피 높음)
➡️ 자식 노드들이 별로 순수해지지 않았으므로(불확실성이 별로 줄지 않았으므로) 정보 이득이 낮습니다."8시간 이상 잠" 그룹 (5명)
공부 여부 수면 시간 결과 공부함 8시간 이상 합격 공부함 8시간 이상 합격 공부함 8시간 이상 합격 공부 안 함 8시간 이상 불합격 공부 안 함 8시간 이상 불합격 "8시간 미만 잠" 그룹 (5명)
공부 여부 수면 시간 결과 공부함 8시간 미만 합격 공부함 8시간 미만 합격 공부함 8시간 미만 불합격 공부 안 함 8시간 미만 불합격 공부 안 함 8시간 미만 불합격
이 경우 ID3 알고리즘은 정보 이득이 더 높은 공부 여부를 분기 질문으로 선택합니다.
3. ⚙️ ID3 알고리즘의 작동 단계 (재귀적 방식)
ID3는 다음과 같은 재귀적인(recursive) 방식으로 트리를 구축합니다.
- 시작 (루트 노드): 전체 훈련 데이터셋으로 루트 노드를 만듭니다.
- 엔트로피 계산: 현재 노드의 엔트로피를 계산합니다.
- 만약 엔트로피가 0이면 (모든 데이터가 같은 클래스), 현재 노드를 리프 노드로 만들고 종료합니다.
- 만약 더 이상 나눌 속성이 없으면, 현재 노드에서 가장 많은 클래스를 리프 노드의 예측값으로 정하고 종료합니다.
- 정보 이득 계산: 사용 가능한 모든 속성(Feature)에 대해 각각 정보 이득을 계산합니다.
- 최적 속성 선택: 정보 이득이 가장 큰 속성을 이번 노드의 분기 기준으로 선택합니다.
- 분기 (Split): 선택된 속성의 고유한 범주(예: 날씨가 '맑음', '흐림', '비')에 따라 데이터를 나누어 자식 노드를 생성합니다. (속성이 3개 이상의 경우 ID3 알고리즘은 다지 분할을 택합니다. 즉 속성이 가지는 범주의 개수 만큼 자식 노드를 분할하여 생성합니다.)
- 재귀 (Recurse): 생성된 각 자식 노드에 대해, 1번 단계부터 다시 반복 수행합니다.
4. ⚖️ ID3 알고리즘의 장단점
ID3는 혁신적이었지만, 태생적인 한계점 역시 명확했습니다.
👍 장점
- 직관성 (White-Box):
트리의 구조가 시각적으로 명확하여 왜 그런 예측이 나왔는지 이해하고 설명하기 쉽습니다. - 결정론적 (Deterministic):
동일한 데이터셋이 주어지면, 몇 번을 실행해도 항상 동일한 트리(모델)를 생성합니다.
👎 단점
- 범주형 속성만 처리 (Categorical Only):
오리지널 ID3는 날씨 (맑음, 흐림)처럼 값이 구분되는 범주형 데이터만 처리할 수 있었습니다.
온도 (25.5℃) 같은 연속적인 수치형 데이터는 처리하지 못했습니다. - 과적합 (Overfitting)에 매우 취약:
ID3의 가장 치명적인 단점입니다. ID3는 엔트로피가 0이 될 때까지, 즉 훈련 데이터에 100% 완벽하게 들어맞을 때까지 트리를 쪼갭니다. 가지치기(Pruning) 기능이 없어서 훈련 데이터의 노이즈까지 모두 학습해버리고, 이로 인해 새로운 데이터에 대한 예측 성능(일반화 성능)이 매우 떨어졌습니다. - 정보 이득의 편향성 (Bias):
정보 이득은 '고객 ID'나 '주민등록번호'처럼 고유한 값(Unique value)이 많은 속성을 선호하는 경향이 있습니다. (왜냐하면 이 속성으로 나누면 모든 자식 노드가 순수해져(샘플 1개씩) 정보 이득이 최대가 되기 때문입니다.) 하지만 이런 분기는 예측에 아무런 도움이 되지 않습니다.
5. 🚀 ID3의 의의
사실 ID3 알고리즘은 현대 머신러닝에서 거의 사용되지 않습니다.
하지만 우리가 의사결정 트리를 배울 때 ID3를 가장 먼저 공부하는 이유는 명확합니다.
ID3는 정보 이득(Information Gain)이라는 강력한 척도를 사용해, 수학적 근거에 기반하여 데이터를 탐욕적(Greedy)으로 분할하는 개념을 증명해낸 첫걸음이기 때문입니다.
또 오히려 ID3의 명확한 단점들을 해결하는 방향으로 머신러닝이 발전해왔습니다.
- 정보 이득의 편향성을 해결할 순 없을까?
- 수치형 데이터는 어떻게 다루고, 이진 분할(Binary Split)로 통일할 순 없을까?
- 과적합을 근본적으로 막을 방법은 없을까?
결국 ID3를 이해하는 것은, 그 자체로 완결된 모델을 배우는 것이 아니라 의사결정 트리의 거대한 진화 과정을 이해하기 위한 가장 중요한 첫 단추를 꿰는 일이라고 할 수 있습니다.