ID3  Approach

Adaptive Pattern Recognition and Neural Networks : Yoh-Han Pao , Addison-Wesley, 1989, Page 85~93

General considerations   ID3 의 복잡성   ID3 의 장점   ID3 의 단점

패턴인식과 분류에 대한 ID3 접근은 비수치 속성이나 변수값 (nonnumeric attributes or feature values) 을 가지는 패턴들을 분류하기 위한 효율적인 식별 트리 (discrimination tree) 를 생성하기 위한 과정이다. 식별 트리는 규칙들을 모아놓은 (a body of rules) 형태로서 표현될 수 있기 때문에, ID3 는 기계학습이나 규칙획득을 위한 귀납추론으로 생각되기도 한다.

ID3 는 어떤 조건에서는 매우 효율적일 수 있지만, 그 효용성 범위를 넘어서서 사용되어서는 안된다. ID3 는 많은 수의 패턴들이 있고, 각 패턴들이 긴 길이의 비수치 변수값 (속성값) 으로 구성되어 있을 때 유효하게 사용될 수 있다. 이러한 패턴들의 일부의 클래스의 종류 (class membership) 는  주어진다. 그 작업은 황당하게 많은 데이터를 검사하고, 변수값들의 최소 조합이 클래스의 종류를 결정하기에 충분하다는 것을 발견하는 것이다.

ID3 에서는, 문자로 된 예들이 정확하게 분류될 때까지 변수들이 어떻게 순서대로 검사되는 지를 결정한다. 예를들면, 변수들의 단지 아주 작은 부분만이 분류 목적을 위해서 사용될 필요가 있다는 것을 알게 될 것이다. 문자로 된 예들에 대해 얻어진 이러한 결과가, 만일 원래의 데이터를 포함하는 훨씬 더 큰 패턴들을 대표한다면, ID3 를 사용함으로써 매우 큰 이득 (gain) 이 얻어지게 될 것이다. 덧붙여서, 식별트리를 발견한 결과로서, 클래스의 종류는 변수값들의 어떤 조화에 의존한다는 사실은, 검사가 이루어지는 과정을 결정하는 기본 메카니즘에 대한 통찰력을 제공하게 될 것이다.

다음에 Quinlan (1983) 의 예로서 그 과정을 실증하고, 더 일반적인 과정을 표현할 것이다.

예제) 물리적 특성에 따라 개인들을 구분함

패턴의 집합을 라고 하고, 신장, 머리색깔, 눈색깔 같은 변수가 각각 {short, tall}, {dark, red, blond}, {blue, brown} 같은 변수값을 가진다. 클래스의 종류는   와 이다. 이때 는 다음과 같다.

여기서 는 모든 가능한 변수값의 조합을 나타내지 않는다는 것을 알 것이다. 즉 12 개의 가능한 조합중에서 8 개만을 나타낸 것이다. ID3 방법의 목적은 의 모든 패턴들을 구분하기에 충분한 테스트의 순서를 찾아낼 수 있다는 것이다. 그래서 에서는 나타나지 않지만 같은 문제나 현상을 대표하는 다른 패턴들에서도 위와 같은 과정이 잘 응용될 것이다.

ID3 는 정보 이론적 접근 (information-theoretic) 접근을 사용한다. 그 과정은 정보에서는 가장 큰 이득 (gain) 을 얻고, 엔트로피에서는 가장 큰 감소를 나타내는 변수를 검사한다.

엔트로피는  로서 정의되며, 거기서 확률  는 발생빈도의 기초로서 결정된다.

테스트의 다양한 단계에서의 엔트로피를 평가해 보자. 먼저, 어떠한 정보도 없는 상태에서, 패턴이 어떤 클래스에 속하는지를 추측하려면, 클래스  는 0.5 의 확률, 클래스 는 똑같이 0.5 의 확률이 부여될 것이다. 즉 사전 확률로서 같은 값을 부여하며, 어떤 정보로 없을 경우의 엔트로피는 다음과 같다.

그러나, 만일 5 개는  클래스에 속하는 패턴이고 3 개는   클래스에 속하는 패턴이라면 엔트로피는 다음과 같다.

달리말하면, 정보 내용 (information content)에서 0.046 bit 증가하였다.

이때에, 어떤 변수가 클래스 종류를 구분하는데 가장 효율적인가 하는 의문이 생긴다. 3 개의 변수 신장, 머리색깔, 눈색깔 을 모두 고려하여, 각 변수를 테스트 했을 때 얼마만한 정보 이득이 있는지를 평가한다. 명확하게 의 어떤 부분을 구분할 수 있어서 효율적인 것으로 나타나는 변수를 찾는것이 아니라, 전체적으로 정보 내용에서 최대 이득 (maximum gain) 을 찾는다는 것이 중요하다.

3 개의 변수 각각에 대해 테스트한 상황이 다음 그림에 보인다.  이 단계에서는 모든 자료구조가 1 level decision tree 이다.

그림 1. 변수 "신장" 을 테스트하여 얻은 정보 이득 

그림 2. 변수 "머리색깔" 을 테스트하여 얻은 정보 이득 

그림 3. 변수 "눈색깔" 을 테스트하여 얻은 정보 이득 

그림 1에서 신장을 테스트할 때 모집단을 클래스 구분없이 섞어서 2 집단으로 나는다. "tall" 가지의 엔트로피는 0.917 이고 "short" 는 0.918 이다. 각 가지의 엔트로피로서 시스템 (전체 모집단) 엔트로피를 구하면 0.951 이다. 달리말하면, 신장을 테스트 해서는 많은 정보이득이 얻어지지는 않는다. 반면에 그림 2 와 3 에서는 머리색깔과 눈색깔 을 테스트하여 0.454 와 0.347 이 구해졌다. 따라서 ID3 메카니즘에서는 정보내용에서의 이득이 가장 컸기 때문에 머리색깔을 테스트 해야한다는 결론이 나온다.

유사하게, decision tree 의 두 번째 level 에서는 눈색깔을 테스트하는 것이 더 큰 정보내용 이득을 얻는다. 이러한 결과가 2 level tree 로서 다음 그림에 표현된다. 두 번째 level 에서 만일 하나의 노드 (subpopulation) 이상으로 확장되어야 한다면, 같은 변수가 동시에 모든 노드에 사용되어, 시스템에서 그 변수를 테스트 해서 정보 이득을 추정하게 될 것이다.

그림 4. ID3 two-level decision tree.

General Considerations

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

Step 1. 엔트로피의 초기값을 계산한다. 훈련 집합에서 모든 패턴들에 대해 어떤 클래스에 속하는 지 표시된다. 그러므로 개의 패턴으로 구성된 시스템을 위한 초기 엔트로피는 다음과 같다.

Step 2. decision tree 의 root node 가 될 변수를 선택한다.

a. 각 변수 에 대해, , 개의 변수값들의 값 에 따라 원래의 모집단을 1 level 모집단으로 분할한다. 개의 가지에서 개의 패턴들이 있지만, 이러한 패턴들이 모두 같은 클래스일 필요는 없다.

b. 하나의 가지의 모집단 , 클래스  에 속하는 패턴의 수 . 각 가지의 엔트로피가 계산된다.



변수 를 테스트 한후에 시스템 엔트로피는 다음과 같다.



c. 변수 를 테스트 한 결과로서 엔트로피의 감소는 다음과 같다.



d. 엔트로피가 가장 크게 감소하는 변수 를 선택한다. (모든   에 대해   일 때)

e. 변수 는 decision tree 의 root 가 되고 1 level 은 그림 5 와 같이 된다.  

그림 5. decision tree 의 구조 : root 와 level-1 populations.

Step 3. decision tree 의 다음 level 을 만든다. 모든 가지들에 대해 나머지 변수  상에서 테스트 하여,  정보내용에서 최대의 이득을 얻거나 엔트로피가 최대 감소하는 변수를 level-1 노드로서 사용할 변수로 선택한다.

Step 4. Step 1에서 3 까지 반복한다. 모든 하위 모집단 (subpopulation) 이 하나의 클래스로 통일되고 시스템 엔트로피가 0 이 될 때까지 위의 과정을 반복한다.

그림 6. decision tree on basis of steepest descent in entropy.

ID3 의 복잡성

ID3 방법에서 기본적인 작업은 각 가지에 대해 엔트로피를 계산하는 것이다. 여기서는 개의 변수 각각이 개의 값을 가지는 것으로 가정해왔다. 그때에, decision tree 의 root 에서, 각 변수 에 대해 번의 그런 계산을 하게 된다. 다음 레벨에서는 개의 노드 각각이 개의 가지를 가지므로, 개의 변수 각각이 번의 계산을 하게 된다.

그러나, 트리의 레벨이 증가하면서, 여러개의 가지들이 하나의 클래스로 되어가면서, 계산의 부담은 감소하게 될 것이다. 추정하여 보면, 의 트리는 의 완전히 확장된 decision tree 정도의 복잡성을 보이는 것으로 추정된다. 그러므로, 계산의 부담은 약  만큼  증가한다. 즉 그것은 decision tree 의 깊이에 비교하여 지수적으로 (exponentially) 증가하지만, 변수의 수와 각 변수값의 수와 비교하여 보면 다항식적으로 (polynomially) 증가한다. 그 양   은 문제에 따라 다르다 (problem-dependent).

ID3 의 장점

ID3 과정의 주요한 잇점은 자동화하기가 쉽다는 것일 것이다. 경험적으로, ID3 는 변수들의 조합이 어떤 클래스에 속하는 지를 결정하기에 충분하다는 것을 발견하는데 도움이 될 수 있다는 것을 알 수 있다.

Quinlan 은 계산 부담을 다소 다르게 서술한다. 그는 다음과 같은 예를 들었다. (Quinlan 1983, p. 464)

ID3 는 많은 대상을 다루기 위해 특별히 고안된 것이며, 사실 문제의 어려움과 함께 계산 시간이 선형적으로 증가하는 것은 다음과 같은 것 때문이다.

• 예를드는 대상의 수 (즉 여기서는 )
• 대상을 서술하기 위해 사용되는 속성의 수 (즉 여기서는 )
• decision tree 상의 노드의 수로 측정되는, 개발되는 개념의 복잡성 (즉 )

계산의 요구에 대한 그와 우리들의 서술은 근본적으로는 같다.

ID3 의 단점

ID3 방법의 주요한 단점은 전체 트리를 재구축하지 않고는 decision tree 를 쉽게 업데이트 할 수 없다는 것이다. 즉 새로운 패턴이 부정확하게 분류되었을 때, 트리를 수정하여 새로운 패턴을 적응시킬 수 있어야 한다. 이러한 수정을 patchwork 로서 수행할수 있는데, 그 경우에는 어떤 중요한 개념들을 가장 효율적이고 대표적으로 수행한다는 트리의 역할을 점차로 상실하게 된다. 그렇지 않으면 새 트리를 만들기 위해 처음부터 다시 시작할 수 있다. 후자의 경우에, 바람직하지 않은 방법이지만 접했던 모든 패턴들을 메모리에 유지할 필요가 있다.

또한, ID3 는 일반화와 특화 (generalization and specialization) 라는 주제로 쉽게 접근하지 않는다. 이러한 약점은 또한 ID3 트리가 수정하기가 쉽지 않다는 사실 때문이다.