ID3 (Interactive Dichotomizer 3)   

1. ID3란 무엇인가...  

Quinlan 이 개발한 학습방법으로 어떤 개념에 대한 예와 반례로써 훈련집합(Training Set)이 주어졌을 때 이로부터 개념을 구별할 수 있는 의사결정트리형태의 분류규칙을 형성시키는 것이다.

① 훈련집합으로부터 부분집합 W(윈도우라 부름)를 무작위로 선택한다.

② W에서 의사결정트리를 생성한다.

③ 나머지 사례에서 생성된 규칙을 적용하여 예외적인 사례를 발견한다.

④ 만약 이러한 예외적인 사례가 있다면 이 예외적인 사례를 원래의 W에 포함시키고 다시 ②번 단계 부터 시작한다.

즉, ID3는 두 개의 클래스를 묘사하는 객체들로부터 클래스를 분류하는 규칙을 생성시키는 CLS를 배경으로 하나의 특성을 선택하여 그 특성이 취하는 값에 따라 객체집합 C를 , ,…으로 구분하고 여기서 는 해당특성이 i번째 특성값을 취하는 객체집합 C의 부분집합이다. 이때 선택된 특성을 루트노드로 형성하고 만약, 예외적인 사례가 있다면 그 특성을 선택하여 그 특성이 취하는 값에 따라 객체집합을 구분하여 하위부분집합을 형성한다. 이렇게모든 하위집합들의 클래스가 하나의 클래스에 속하게 되면 분류작업에 의한 의사결정트리의 생성이 끝나게 된다.  

2. Information theoretic 측정치(Measure)  

정보획득을 최대화 한다는 원칙아래 분류규칙을 생성하기 위해서는 각 특성들의 분별력의 정도를 측정하기 위해서 정보의 복잡성 및 단순성을 측정하는 측정치를 사용하는데, 값이 작을수록 객체들의 분별력이 작아져 단일클래스에 속하고 있음을 나타내고 클수록 무질서 상태 또는 정보력이 약한 상태를 나타내어 특성을 선택하는데 있어 객체들의 분별력이 가장 큰 특성을 선택하도록 이용하였다.

다시말하자면 두 개의 클래스가 있다고 가정하고 하나를 +, 다른 하나를 -라고 한다면, 어떤 객체집합C에서 +클래스인 객체들의 비율을 ,  -클래스가 속해있는 비율을 라고 한다면 이 객체집합C가 가지고 있는 정보값M(C)를

M(C)=  

라고 나타낼 수 있다. 즉, 값이 작을수록 어떤 질서상태를 나타내어 단일클래스에 속하고 있음을 나타내고, 클수록 무질서 상태 또는 정보력이 약한 상태를 나타내므로 가장 분별력이 있는 변수(Discriminatory Variable)를 의사결정트리의 루트노드로 선택한다.  

3. ID3의 단점과 보안방법  

① 생성된 규칙은 불확실성을 반영하지 않는 결정적인 규칙이다. 따라서 적용되는 영역이 불확실성을 내포하고 있거나 틀린 사례를 제공하는 경우에는 적합치 않다. 즉, 주어진 훈련집합을 구분하는 의사결정트리가 매우 가지가 많은 큰 트리로 표현되기 때문에 새로운 사례를 올바르게 구분해 주지 못하여 최악의 경우 훈련집합의 사례 하나하나에 대해 트리의 결정노드가 생성될 수 있다.

② 예외적인 사례를 인정하지 않는다. 이것은 ①의 특성의 귀결이라 볼 수 있다. 예외적인 사례가 있다면 그것을 포괄하는 결정노드가 전체 의사결정트리에 새로이 첨가되어 가지를 뻗을 것이다.

③ 똑같은 사례일 경우 그 수가 아무리 많아도 최종적인 트리형성에 영향을 미치지 못한다.

④ 훈련집합의 내용이 약간 변하여도 이에 과민반응하여 전체 의사결정트리의 모양이 달라지게 된다.

위와 같은 단점으로 인해 한 하위트리 내의 사례집합에서 예외가 모두 없어질 때까지 트리를 생성케 하지 않고 어떤 기준을 주어 중간에서 멈추게 하는 방법을 사용하거나 특정값이 수치인 경우, 수치의 범위를 어떤 구간으로 나누어 유한 개의그룹으로 묶는 방법 등을 사용하기도 한다.  

4. ID3와 MDA의 비교  

MDA와 같은 통계적 방법론도 주어진 데이터를 분석하여 가장 데이터를 잘 설명해주는, 즉 가장 적합한(Fitting) 모델(설명력이 높은 결정변수의 선형함수 형태)을 생성하므로 넓은 의미에서 보면 MDA도 학습의 일종이라 볼 수 있지만, 독립변수의 분포가 정규분포임을 가정하고 있고 독립변수와 종속변수간에 선형함수를 가정하고 있어 이러한 가정을 충족시키지 못하는 경우 적용에 한계가 있을 수 있으나 ID3와 같은 귀납적 학습방법은 독립변수의 분포에 아무런 가정을 하지 않고 있다. 또한 MDA에는 생성된 모형에 의한 추론과정에서 설명이 불가능하다.