ID3 알고리즘 - information gain을 통한 데이터 분류
ID3 알고리즘: 정보 이득 기반 결정 트리 학습
결정 트리를 효율적으로 구축하기 위한 다양한 알고리즘이 존재하며, 그 중 하나가 ID3 알고리즘이다. ID3 알고리즘은 Iterative Dichotomiser 3의 약자로, 정보 이득(Information Gain)을 기반으로 데이터를 반복적으로 분할하여 결정 트리를 생성하는 알고리즘이다.
ID3 알고리즘은 이전 시간에 배운 바 있는 정보 이득 개념을 통해 각 노드에서 어떤 설명 변수를 기준으로 데이터를 분할할지 결정한다. 정보 이득이 가장 높은 설명 변수, 즉 데이터를 가장 효과적으로 분류하는 변수를 선택하여 트리를 구축해 나간다.
데이터 분할: 정보 이득 극대화
ID3 알고리즘은 각 노드에서 가능한 모든 설명 변수에 대해 정보 이득을 계산하고, 정보 이득이 가장 높은 변수를 선택하여 데이터를 분할한다. 이 과정을 반복(iteration)하여 트리를 성장시키면, 최종적으로 모든 잎 노드(leaf node)가 순수해질 때까지 분할이 진행된다.
(순수 노드는 해당 노드에 속하는 모든 데이터가 같은 클래스에 속하는 노드를 의미한다.)
ID3 알고리즘 의사 코드 (Pseudocode)
ID3 algorithm Require : set of descriptive feature d Require : set of training instance D1. if all the instance in D have the same target level C then 2. return a decision tree consisting of a leaf node with label C 3. else if d is empty then 4. return a decision tree consisting of a leaf node with the label of the majority target level in D 5. else if D is empty then 6. return a decision tree consisting of a leaf node with the label of the majority target level of the dataset of the immediate parent node 7. else 8. d[best] ← arg max IG (d, D)d ∈ d9. make a new node, Node_{d[best]}, and label it with d[best]10. partition D using d[best] 11. remove d[best] from d 12. for each partition D_{i} of D do 13. grow a branch from Node_{d[best]} to the decision tree created by rerunning ID3 with D = D_{i}
1. 정지 조건 (Stopping Criteria)
- 1-2번 라인: 모든 인스턴스가 같은 클래스 레이블을 가지면 (즉, 더 이상 분류할 필요가 없으면) 현재 노드를 leaf 노드로 만들고 해당 클래스 레이블을 할당
- 3-4번 라인: 더 이상 사용할 설명 변수(feature)가 없으면 현재 노드를 leaf 노드로 만들고, 데이터셋에서 가장 많은 클래스 레이블을 할당
- 5-6번 라인: 현재 분할된 데이터셋에 인스턴스가 없으면 현재 노드를 leaf 노드로 만들고, 부모 노드의 데이터셋에서 가장 많은 클래스 레이블을 할당
2. 확장 조건 (Expansion Criteria)
- 7-8번 라인: 정지 조건에 해당하지 않으면, 정보 이득 (Information Gain)이 가장 큰 설명 변수를 선택
- 9번 라인: 선택된 설명 변수를 기준으로 새로운 노드를 생성
- 10번 라인: 선택된 설명 변수를 사용하여 데이터셋을 분할
- 11번 라인: 사용된 설명 변수는 제거
- 12-13번 라인: 분할된 각 데이터셋에 대해 ID3 알고리즘을 재귀적으로 실행하여 결정 트리를 확장
기본 경우 (Base Case)의 중요성
재귀 알고리즘에서 기본 경우는 재귀 호출을 멈추고 결과를 반환하는 조건이다. ID3 알고리즘에서 기본 경우에서 고려해야 할 점은 다음과 같다.
- 내부 node의 dataset은 그 부모 node의 dataset의 일부다
- 특정 path에서 feature은 딱 한번만 선택할 수 있다
기본 경우를 제대로 처리하지 않으면 무한 루프에 빠지거나 잘못된 결과를 생성할 수 있다.
따라서 의사 코드의 정지 조건에서 보았듯, ID3 알고리즘은 다음 세 가지 경우에 재귀 호출을 멈추고 잎 노드를 생성한다.
- 현재 노드의 모든 데이터가 같은 클래스에 속하는 경우
- 더 이상 사용할 수 있는 설명 변수가 없는 경우
- 특정 변수 값에 대한 데이터가 없는 경우
결론: 정보 기반 결정 트리 구축
지난 시간에 Shannon 엔트로피 모델을 통해 정보 이득을 구하는 방법을 알아보았다면, 이번 시간에는 이를 이용한 decision tree에 대해 소개해 보았다. ID3 알고리즘은 각 노드에서 정보 이득이 가장 높은 설명 변수를 선택하여 분할하고, 재귀적으로 트리를 성장시킨다는 특징이 있다. 이때 기본 경우를 명확하게 정의하고 과적합을 방지하기 위한 가지치기 기법을 적용하면, 예측 성능이 우수한 결정 트리 모델을 얻을 수 있다. 다음 시간에는 구체적인 예시를 들어보고자 한다.
[인공지능개론] information based learning - Shannon's entropy model
(https://hyeondev.blogspot.com/2024/10/information-based-learning-shannons.html)