ID3 알고리즘

2. 알고리즘

ID3 알고리즘은 각 단계에서 아직 사용하지 않은 속성들의 엔트로피 또는 정보 획득을 계산하고, 이 중 엔트로피가 가장 낮은 (또는 정보 획득이 가장 큰) 속성을 선택하여 데이터를 분할하는 방식으로 작동한다.

존 로스 퀸란이 1979년에 제안한 ID3는 오컴의 면도날 원리에 기반하여 최소한의 가설로 사건을 결정한다. 각 독립 변수에 대해 변수 값을 결정했을 때의 평균 정보량 기대값을 구하고, 그 중 최댓값을 선택하여 트리의 노드로 만드는 연산을 재귀적으로 수행한다.

ID3는 학습 효율이 좋고 다수의 예제로부터 학습할 수 있지만, 예제를 일괄적으로 처리해야 하므로 학습 결과의 순차적인 개선이 불가능하고, 입력 변수가 연속값을 갖는 경우에는 사용할 수 없다는 단점이 있다. 퀸란은 이러한 문제점을 보완한 C4.5 알고리즘을 제안했다.

ID3 알고리즘의 진행 과정은 다음과 같다.

1. 루트 노드를 생성하고 모든 예제를 루트 노드에 포함시킨다.

2. 루트 노드의 예제가 모두 같은 결과를 가지면 해당 결과로 라벨을 붙이고 종료한다.

3. 예제 집합의 평균 정보량을 계산한다.

4. 각 독립 변수의 값에 따라 예제 집합을 분할한다.

5. 분할된 집합들의 평균 정보량을 계산한다.

6. 계산된 평균 정보량으로부터 독립 변수의 평균 정보량 기대값을 구한다.

7. 평균 정보량 기대값이 최대가 되는 독립 변수를 선택한다.

8. 선택된 독립 변수를 노드의 라벨로 지정하고, 자식 노드를 생성하여 분할된 집합들을 각각 소속시킨다.

9. 각 자식 노드에 대해 위 과정을 재귀적으로 반복한다.

다음은 동물의 분류를 결정하는 예시이다.

log의 밑은 기본적으로 무엇이든 상관없지만, 출력은 포유류, 파충류, 조류의 세 종류이므로 평균 정보량의 최댓값이 1.0, 최솟값이 0.0이 되도록 여기서는 3을 밑으로 사용한다.

전체 평균 정보량을 계산하면, 이 예제에서의 출력은 포유류 = 2, 파충류 = 1, 조류 = 2이므로,

:$M(C)\; =\; -\backslash frac\{2\}\{5\}\backslash log\_3\backslash frac\{2\}\{5\}\; -\backslash frac\{1\}\{5\}\backslash log\_3\backslash frac\{1\}\{5\}\; -\backslash frac\{2\}\{5\}\backslash log\_3\backslash frac\{2\}\{5\}\; \backslash simeq\; 0.960$

이 된다. 먼저 독립 변수로 식성(''a₁'')을 사용한다. 이 변수는 "초식"과 "육식"의 두 가지 값을 가질 수 있으므로, 먼저 예제 집합을 다음 두 가지로 나눈다.

• $C\_\{11\}\; =\backslash \{$펭귄, 사자, 도마뱀$\backslash \}$ (식성 = 육식)
• $C\_\{12\}\; =\backslash \{$소, 문조$\backslash \}$ (식성 = 초식)

2. 1. 작동 원리

• 하위 집합의 모든 요소가 동일한 클래스에 속하는 경우; 이 경우 노드는 리프 노드로 변환되고 예제의 클래스로 레이블이 지정된다.
• 더 이상 선택할 속성이 없지만 예제가 여전히 동일한 클래스에 속하지 않는 경우; 이 경우 노드는 리프 노드로 만들어지고 하위 집합의 예제에서 가장 일반적인 클래스로 레이블이 지정된다.
• 하위 집합에 예제가 없는 경우; 이는 부모 집합의 예제가 선택한 속성의 특정 값과 일치하는 것으로 발견되지 않을 때 발생한다. 예를 들어, 100세 이상인 사람 중 부재가 있을 수 있다. 그런 다음 리프 노드가 생성되고 부모 노드의 집합에 있는 예제의 가장 일반적인 클래스로 레이블이 지정된다.

2. 2. 재귀 중단 조건

• 하위 집합의 모든 요소가 동일한 클래스에 속하는 경우, 노드는 리프 노드로 변환되고 예제의 클래스로 레이블이 지정된다.^[1]
• 더 이상 선택할 속성이 없지만 예제가 여전히 동일한 클래스에 속하지 않는 경우, 노드는 리프 노드로 만들어지고 하위 집합의 예제에서 가장 일반적인 클래스로 레이블이 지정된다.^[1]
• 하위 집합에 예제가 없는 경우, 이는 부모 집합의 예제가 선택한 속성의 특정 값과 일치하는 것으로 발견되지 않을 때 발생한다. 예를 들어, 100세 이상인 사람 중 부재가 있을 수 있다. 그런 다음 리프 노드가 생성되고 부모 노드의 집합에 있는 예제의 가장 일반적인 클래스로 레이블이 지정된다.^[1]

2. 3. 속성 선택 기준

2. 3. 1. 엔트로피 (Entropy)

• $S$ – 엔트로피를 계산하려는 현재 데이터 집합^[1]
• * ID3 알고리즘의 각 단계에서 속성에 따라 분할되는 경우, 이전 집합의 하위 집합으로 변경되거나, 재귀가 이전에 종료된 경우 상위 항목의 "형제" 분할로 변경된다.^[1]
• $X$ – $S$에 있는 클래스의 집합^[1]
• $p(x)$ – 클래스 $x$의 비율을 집합 $S$의 원소 수로 나눈 값^[1]

ID3을 사용하여 식성, 발생 형태, 체온에서 분류를 결정하는 경우를 고려한다.^[1]

ID3에서 log의 밑은 기본적으로 무엇이든 상관없지만, 출력은 포유류, 파충류, 조류의 세 종류이므로 평균 정보량의 최댓값이 1.0, 최솟값이 0.0이 되도록 여기서는 3을 밑으로 사용한다.^[1]

전체 평균 정보량을 계산하면, 이 예제에서의 출력은 포유류 = 2, 파충류 = 1, 조류 = 2이므로,^[1]

:$M(C)\; =\; -\backslash frac\{2\}\{5\}\backslash log\_3\backslash frac\{2\}\{5\}\; -\backslash frac\{1\}\{5\}\backslash log\_3\backslash frac\{1\}\{5\}\; -\backslash frac\{2\}\{5\}\backslash log\_3\backslash frac\{2\}\{5\}\; \backslash simeq\; 0.960$

이 된다. 먼저 독립 변수로 식성(''a₁'')을 사용한다. 이 변수는 "초식"과 "육식"의 두 가지 값을 가질 수 있으므로, 먼저 예제 집합을 다음 두 가지로 나눈다.^[1]

• $C\_\{11\}\; =\backslash \{$예제 1, 예제 2, 예제 4 $\backslash \}$ (식성 = 육식) 클래스.^[1]
• $C\_\{12\}\; =\backslash \{$ 예제 3, 예제 5 $\backslash \}$ (식성 = 초식) 클래스.^[1]

2. 3. 2. 정보 획득량 (Information Gain)

• $\backslash Eta(S)$ – 집합 $S$의 엔트로피
• $T$ – 속성 $A$에 의해 집합 $S$를 분할하여 생성된 부분 집합, $S\; =\; \backslash bigcup\_\{t\; \backslash in\; T\}\; t$를 만족한다.
• $p(t)$ – 부분 집합 $t$의 원소 개수가 집합 $S$의 원소 개수에서 차지하는 비율
• $\backslash Eta(t)$ – 부분 집합 $t$의 엔트로피

ID3을 사용하여 식성, 발생 형태, 체온에서 분류를 결정하는 경우를 생각해보자.

log의 밑은 기본적으로 무엇이든 상관없지만, 출력은 포유류, 파충류, 조류의 세 종류이므로 평균 정보량의 최대값이 1.0, 최소값이 0.0이 되도록 여기서는 3을 밑으로 사용한다.

전체 평균 정보량을 계산하면, 이 예제에서의 출력은 포유류 = 2, 파충류 = 1, 조류 = 2이므로,

:$M(C)\; =\; -\backslash frac\{2\}\{5\}\backslash log\_3\backslash frac\{2\}\{5\}\; -\backslash frac\{1\}\{5\}\backslash log\_3\backslash frac\{1\}\{5\}\; -\backslash frac\{2\}\{5\}\backslash log\_3\backslash frac\{2\}\{5\}\; \backslash simeq\; 0.960$

이 된다. 먼저 독립 변수로 식성(''a₁'')을 사용한다. 이 변수는 "초식"과 "육식"의 두 가지 값을 가질 수 있으므로, 먼저 예제 집합을 다음 두 가지로 나눈다.

: $C\_\{11\}\; =\backslash \{$예제 1, 예제 2, 예제 4 $\backslash \}$ (식성 = 육식) 클래스.

: $C\_\{12\}\; =\backslash \{$ 예제 3, 예제 5 $\backslash \}$ (식성 = 초식) 클래스.

분할된 ''C₁₁''과 ''C₁₂''에서 평균 정보량을 구하면, ''C₁₁''의 출력은 포유류 = 1, 파충류 = 1, 조류 = 1이므로,

:$M(C\_\{11\})\; =\; -\backslash frac\{1\}\{3\}\backslash log\_3\backslash frac\{1\}\{3\}\; -\backslash frac\{1\}\{3\}\backslash log\_3\backslash frac\{1\}\{3\}\; -\backslash frac\{1\}\{3\}\backslash log\_3\backslash frac\{1\}\{3\}\; =\; 1.0$

마찬가지로 ''C₁₂''의 출력은 포유류 = 1, 파충류 = 0, 조류 = 1이므로,

:$M(C\_\{12\})\; =\; -\backslash frac\{1\}\{2\}\backslash log\_3\backslash frac\{1\}\{2\}\; -\; \backslash frac\{0\}\{2\}\backslash log\_3\backslash frac\{0\}\{2\}\; -\; \backslash frac\{1\}\{2\}\backslash log\_3\backslash frac\{1\}\{2\}\; \backslash simeq\; 0.631$

따라서 평균 정보량의 기대값 ''M₁''은

:$M\_1\; =\; 0.960\; -\; \backslash left(\; 1.0\backslash times\; \backslash frac\{3\}\{5\}\; +\; 0.631\backslash times\backslash frac\{2\}\{5\}\; \backslash right)\; =\; 0.093$

마찬가지로, 발생 형태(''a₂''), 체온(''a₃'')으로부터 ''M₂'', ''M₃''를 계산하면,

:$M\_2\; =\; 0.612$

:$M\_3\; =\; 0.455$

가 되어, 최대값은 ''M₂''이다. 따라서 노드의 레이블은 발생 형태(''a₂'')가 된다.

이상의 과정을 반복하면, 학습 과정에서 불필요한 변수를 삭제하고 최소한의 가설(이 예시에서는 발생 형태와 체온)로 예제와의 관련성을 학습한다.

4. ID3 알고리즘의 활용

ID3 알고리즘은 데이터 집합에 대한 훈련을 통해 결정 트리를 생성하며, 이 트리는 메모리에 저장된다. 실행 시간에 이 결정 트리는 새로운 테스트 사례(특징 벡터)를 분류하는 데 사용된다. 리프 노드에 도달하기 위해 데이터의 특징을 사용하여 결정 트리를 순회하는 방식으로 분류가 이루어진다.

예를 들어, 동물의 식성, 발생 형태, 체온을 바탕으로 분류를 결정하는 경우를 생각해 볼 수 있다.

예제	식성(a1)	발생 형태(a2)	체온(a3)	분류
예제 1 (펭귄)	육식	난생	항온	조류
예제 2 (사자)	육식	태생	항온	포유류
예제 3 (소)	초식	태생	항온	포유류
예제 4 (도마뱀)	육식	난생	변온	파충류
예제 5 (문조)	초식	난생	항온	조류

ID3 알고리즘은 학습 과정에서 불필요한 변수를 삭제하고 최소한의 가설로 예제와의 관련성을 학습한다. 위의 예시에서는 식성, 발생 형태, 체온의 세 가지 입력 변수가 있었지만, 출력되는 결정 트리에서는 발생 형태와 체온 두 종류만 사용되었다.