ID3 (Iterative Dichotomiser 3 : 반복적 이분법 3)

일반적인 경우, (N) 개의 문자로 표현된 패턴들이 클래스 (c_i, i = 1, 2, 3, ..., C) 에 속하는 패턴 집합으로 분할됩니다. 클래스 (c_i) 에서의 모집단은 (N_i) 입니다. 각 패턴은 (K) 개의 변수를 가지며, 각 변수는 (J_k) 개의 값들을 가집니다. (여기서는 단순화시켜서, 모든 변수들이 (J) 개의 값들을 가지는 것으로 합니다). 효율적인 decision tree 를 생성하기 위한 ID3 방법은 다음과 같은 단계를 거칩니다.

[그림 1] ID3 알고리즘이 훈련 데이터로부터 생성하는 의사결정 트리 (Decision Tree) 구조

1986년 로스 퀸란(J. Ross Quinlan) 교수가 제안한 ID3(Iterative Dichotomiser 3)는 '반복적 이분기'라는 이름 그대로, 복잡한 데이터 집합을 엔트로피(Entropy) 기준에 따라 반복적으로 쪼개어 가장 순수한(Pure) 하위 노드들로 분할해 나가는 하향식(Top-Down) 탐욕적(Greedy) 알고리즘입니다.

(1) 섀넌 엔트로피 (Shannon Entropy) : 데이터의 무질서도 측정

엔트로피(Entropy)는 물리학의 열역학 개념을 클로드 섀넌(Claude Shannon)이 정보이론으로 가져온 것으로, 데이터 집합 내에 존재하는 불확실성(Uncertainty) 또는 무질서도(Impurity)의 크기를 수치화합니다.

(2) 정보 이득 (Information Gain) : 최적의 분기 질문 선택 기준

어떤 속성(Attribute, A)으로 데이터를 분할했을 때, 분할 전의 엔트로피에서 분할 후 하위 부분집합들의 가중 평균 엔트로피를 뺀 값을 정보 이득(Information Gain)이라고 합니다. 즉, "이 질문을 던짐으로써 불확실성이 얼마나 감소했는가?"를 뜻합니다.

기계학습 교과서(Tom Mitchell의 Machine Learning 등)에서 가장 널리 인용되는 로스 퀸란의 전설적인 '테니스 플레이(Play Tennis)' 데이터셋을 통해 ID3의 작동 절차를 분해해 봅니다.

• 1

  Step 1. 전체 데이터의 초기 엔트로피 H(S) 계산

  14일의 날씨 데이터 중 테니스를 친 날(Yes: 9일), 안 친 날(No: 5일)의 초기 불확실성을 계산합니다 :
  H(S) = - (9/14) log_2(9/14) - (5/14) log_2(5/14) = 0.940

• 2

  Step 2. 모든 후보 속성의 정보 이득(Information Gain) 비교

  날씨 속성들(날씨전망: Outlook, 온도: Temperature, 습도: Humidity, 바람: Wind)로 데이터를 쪼갰을 때의 정보 이득을 각각 계산합니다 :
  • IG(S, Outlook) = 0.246  |  • IG(S, Humidity) = 0.151  |  • IG(S, Wind) = 0.048  |  • IG(S, Temperature) = 0.029

• 3

  Step 3. 최고 정보 이득 속성을 노드로 선택하고 가지(Branch) 분기

  정보 이득이 0.246으로 가장 높은 'Outlook(날씨전망)'을 최상위 루트 노드로 결정하고, 그 하위 값들인 [맑음(Sunny), 흐림(Overcast), 비(Rain)]의 3갈래 가지를 생성합니다. 'Overcast'인 날은 모두 Yes(4개)이므로 즉시 순수 잎 노드가 됩니다.

• 4

  Step 4. 순수 노드가 될 때까지 하위 집합에 대해 재귀적(Recursive) 반복

  'Sunny' 가지 아래에서는 남은 속성 중 'Humidity'가, 'Rain' 가지 아래에서는 'Wind'가 최고 정보 이득을 보여 차례로 분기되며 완벽한 의사결정 트리가 완성됩니다.

ID3는 인공지능 역사에 큰 획을 그었지만, 현실 세계의 복잡한 데이터셋에 적용하기에는 몇 가지 치명적인 태생적 한계를 안고 있었습니다. 이를 보완하며 현대 머신러닝의 표준 트리들이 탄생했습니다.

📊 결정 트리 알고리즘의 진화 계보

ID3는 단순한 통계적 분류기를 넘어, 인공지능이 "인간이 손수 코딩한 지식 주입"에서 벗어나 "데이터로부터 스스로 지식 규칙을 캐내는 데이터 주도형 머신러닝"으로 대전환을 이루게 한 기념비적 전환점이었습니다.

• 1

  지식 획득의 병목(Knowledge Acquisition Bottleneck) 해소

  1980년대 기호주의 전문가 시스템(Expert Systems)의 최대 약점은 인간 도메인 전문가를 일일이 인터뷰하여 수만 개의 If-Then 규칙을 사람이 손으로 작성해야 한다는 점이었습니다. ID3는 방대한 사례 데이터만 밀어 넣으면 컴퓨터가 스스로 최적의 규칙(Rule Base)을 자동으로 귀납 추출(Rule Induction)할 수 있음을 완벽하게 증명했습니다.

• 2

  설명 가능한 인공지능(XAI, Explainable AI)의 위대한 원형

  신경망(Neural Network)이나 딥러닝과 달리, ID3가 도출한 의사결정 트리는 루트에서 잎 노드까지의 모든 경로가 "IF 나이 > 30 AND 소득 > 5000 THEN 대출 승인"과 같은 명확한 논리 기호로 1:1 변환됩니다. 이는 의료 진단, 금융 심사, 법률 판결 등 투명성과 감사 가능성(Auditability)이 절대적인 고위험 의사결정 산업의 표준이 되었습니다.

• 3

  현대 최강 머신러닝 '앙상블(Ensemble)'의 토대

  ID3를 출발점으로 진화한 단일 결정 트리들은 오늘날 수백 개의 트리를 결합하는 랜덤 포레스트(Random Forest)와 잔차를 점진적으로 줄여나가는 그래디언트 부스팅(GBDT : XGBoost, LightGBM, CatBoost)으로 만개했습니다. 이들은 현재도 정형 테이블 데이터(Tabular Data) 분야에서 딥러닝을 압도하는 세계 최강의 머신러닝 알고리즘으로 군림하고 있습니다.

• 4

  데이터 마이닝(Data Mining) 혁명의 기폭제

  기업의 CRM 데이터, 신용카드 부정 사용 탐지, 고객 이탈 예측 등 대규모 상업 데이터베이스에서 숨겨진 고객 패턴을 발굴해내는 데이터 마이닝 산업의 폭발적 성장을 견인한 엔진이 바로 ID3 트리 기반 분류 기술이었습니다.

📖 ID3 핵심 고전 논문 및 저서 (Key References) :

• Quinlan, J. R. (1986). "Induction of Decision Trees". Machine Learning, 1(1), 81–106. (ID3 알고리즘이 최초로 공식 발표된 역사적 논문)
• Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers.
• Yoh-Han Pao. (1989). Adaptive Pattern Recognition and Neural Networks. Addison-Wesley, pp. 85–93.
• Tom M. Mitchell. (1997). Machine Learning. McGraw-Hill. (Chapter 3: Decision Tree Learning)
• 이재규 외. (1997). 인공지능과 전문가시스템. 법영사.

🌐 aistudy 내부 및 외부 연구 아카이브 링크 :

• ID3 approach : Yoh-Han Pao — 적응 패턴인식 관점에서의 ID3 이론 해설
• ID3 설명 — aistudy 고전 ID3 상세 설명 문서
• 의사결정 트리 (Decision Tree) — 의사결정 트리의 전반적 구조와 원리 총괄
• 기계학습 : 이재규 교수 — 귀납 학습과 개념 형성