ID3 알고리즘

의사결정 트리 학습에서 ID3(Reterative Dichotomiser 3)는 데이터 집합에서 의사결정 트리를 생성하는 데 사용되는 Ross^[1] Quinlan에 의해 발명된 알고리즘이다.ID3는 C4.5 알고리즘의 선구자로 일반적으로 기계학습 및 자연어 처리 도메인에서 사용됩니다.

알고리즘.

ID3 알고리즘은 원래 $(\displaystyle$ S$)$에서 루트노드로 시작합니다.알고리즘의 각 반복에서는 $세트S의$$$미사용 Atribut을 모두 반복하여 $엔트로피{\displaystyle \mathrm{}}$ H(S$)\$ 또는$$ 그 Atribute의 정보 $게인{\displaystyle }$ G$)\displaystyle$($S)$를 계산합니다.그런 다음 엔트로피(또는 정보 게인) 값이 가장 작은 속성을 선택합니다.다음으로 선택한 Atribute에 의해$세트S{\displaystyle }$(\$displaystyle$S)가$$ 분할 또는 분할되어 데이터의 서브셋이 생성됩니다(예를 들어 50세 미만, 50세 이상, 100세 미만인 모집단의 서브셋에 따라 노드를 자노드로 분할할 수 있습니다).알고리즘은 이전에 선택되지 않은 속성만을 고려하여 각 서브셋에서 반복됩니다.

다음 중 하나의 경우 서브셋의 재귀가 정지될 수 있습니다.

• 서브셋 내의 모든 요소는 같은 클래스에 속합니다.이 경우 노드는 리프 노드로 변환되어 예의 클래스로 라벨이 붙여집니다.
• 더 이상 선택할 속성이 없지만 예제는 여전히 같은 클래스에 속하지 않습니다.이 경우 노드는 리프 노드로 되어 서브셋 내의 가장 일반적인 예시로 라벨이 붙여집니다.
• 서브셋에는 예가 없습니다.이것은 선택한 Atribute의 특정 값에 일치하는 부모 세트의 예가 발견되지 않았을 때 발생합니다.예를 들어 100세 이상 인구 중 사람이 없을 수 있다.그런 다음 리프 노드가 생성되고 상위 노드 집합에서 가장 일반적인 예제 클래스로 레이블이 지정됩니다.

알고리즘 전체에서 결정 트리는 데이터가 분할된 선택된 속성을 나타내는 각 비단말 노드(내부 노드)와 이 분기의 최종 서브셋의 클래스 라벨을 나타내는 단말 노드(리프 노드)로 구성됩니다.

요약

1. $데이터$ $세트{\displaystyle }$ S$(\displaystyle$ S$)$의 모든 $속성{\displaystyle }$ a$(\displaystyle$ a$)$의 엔트로피를 계산합니다.
2. 분할 후 엔트로피가 최소화되는 속성을 사용하여 $S$를 서브셋으로 분할("$분할$")하거나, 이에 상응하는 정보 게인을 최대화합니다.
3. 해당 속성을 포함하는 Decision Tree 노드를 만듭니다.
4. 나머지 속성을 사용하여 하위 집합에서 반복됩니다.

유사 코드

ID3(예, Target_Attribute, Attributes) 트리의 루트 노드를 만듭니다. 모든 예제가 양수이면 레이블 = +와 함께 단일 노드 트리 루트를 반환합니다. 모든 예제가 음수이면 레이블 = -와 함께 단일 노드 트리 루트를 반환합니다. 예측 속성 수가 비어 있으면 단일 노드 루트에 레이블을 반환합니다.l = 예제에서 대상 속성의 가장 일반적인 값.그렇지 않으면 시작 A ← 예를 가장 잘 분류하는 속성입니다.루트 = A에 대한 Decision Tree 특성입니다.가능한 각 값에 대해i A의 v/A에 대해 A = vi 테스트에 해당하는 루트 아래에 새 트리 분기를 추가합니다. 예제(vii)가i 비어 있는 경우 예제(v)를 예제의 하위 집합으로 가정합니다. 그런 다음 이 새 분기 아래에 레이블 = 가장 일반적인 목표 값을 가진 리프 노드를 추가합니다.그렇지 않으면 이 새로운 브랜치 아래에 서브트리 ID3(예(vi), Target_Attribute, Attributes – {A}) End Return Root를 추가합니다.

특성.

ID3는 최적의 솔루션을 보장하지 않습니다.로컬 옵티마에 수렴할 수 있습니다.로컬에서 가장 적합한 속성을 선택하여 반복할 때마다 데이터 집합을 분할하는 탐욕스러운 전략을 사용합니다.알고리즘의 최적성은 최적의 의사결정 트리를 검색하는 동안 백트래킹을 사용함으로써 개선될 수 있지만 시간이 더 걸릴 수 있습니다.

ID3는 트레이닝 데이터를 오버핏할 수 있습니다.과적합을 방지하려면 큰 ^{[further explanation needed]}결정 트리보다 작은 결정 트리를 선호해야 합니다.이 알고리즘은 보통 작은 트리를 생성하지만 가능한 한 가장 작은 Decision Tree를 생성하는 것은 아닙니다.

ID3은 요인 데이터보다 연속 데이터에 사용하기 어렵습니다(요인 데이터는 가능한 값의 이산 개수를 가지므로 가능한 분기점이 감소합니다).특정 Atribute 값이 연속적인 경우 이 Atribute의 데이터를 분할할 수 있는 장소가 많아 분할에 가장 적합한 값을 찾는 데 시간이 걸릴 수 있습니다.

사용.

ID3 알고리즘은 메모리에 $저장$된 Decision Tree를 $생성$하기 위해 데이터 세트$$$$S(\$displaystyle$ S$)$에 대한 교육을 통해 사용됩니다.런타임에 이 결정 트리는 리프 노드에 도달하기 위해 기준의 특징을 사용하여 결정 트리를 횡단함으로써 새로운 테스트 케이스(특징 벡터)를 분류하기 위해 사용된다.

ID3 메트릭

엔트로피

$엔트로피{\displaystyle \mathrm{}}$ H${\displaystyle (}$ ${\displaystyle S}$)(\$displaystyle \mathrm {H}${($S)})$는 (데이터) $세트{\displaystyle }$ S$($$즉$, 엔트로피는 (데이터) $세트{\displaystyle }$S(\$displaystyle$ S$)$의 불확실성의 양을 측정한 것입니다.

$\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}$

어디에,

• $\displaystyle$S $$– 엔트로피가 계산되는 현재 데이터 세트
  • 이는 ID3 알고리즘의 각 단계에서 변경됩니다.속성에 따라 분할하는 경우에는 이전 세트의 서브셋으로, 재귀가 이전에 종료된 경우에는 부모의 "sibling" 파티션으로 변경됩니다.
• $(\displaystyle$ X$)$ – S$(\displaystyle$ S$)$ $클래스{\displaystyle }$ 세트
• ${\displaystyle p}$(${\displaystyle x}$) { $displaystyle$p ($x$ ) $$:$세트{\displaystyle }$S의 요소 수에 대한 $클래스{\displaystyle }$x의 요소 수(\$displaystyle$ x$)$의 비율(\$displaystyle$ S$)$

H${\displaystyle (S)}$ $=$ $(\displaystyle \mathrm {H}${(S)}=$0$일 때 $세트{\displaystyle }$S(\$displaystyle$ S$)$는 완벽하게 분류됩니다(즉$,$ S(\$displaystyle$ S$)$의 모든 요소가 동일한 클래스입니다).

ID3에서는 나머지 속성별로 엔트로피가 산출된다.엔트로피가 가장 작은 속성은 이 반복에서 세트 S를 $분할하기$위해 $사용됩니다$$.$정보 이론에서 엔트로피는 랜덤 변수를 측정할 때 얻을 것으로 예상되는 정보의 양을 측정합니다. 따라서, 양의 값의 분포를 알 수 없는 양을 정량화하는 데 사용될 수도 있습니다.일정량의 분포는 완벽하게 알려져 있기 때문에 엔트로피가 0입니다.반대로 균일하게 분포된 랜덤 변수(구체적으로 또는 연속적으로 균일한 변수)는 엔트로피를 최대화합니다.따라서 노드의 엔트로피가 클수록 트리의 이 단계에서 데이터 분류에 대해 알려진 정보가 적어지고, 따라서 여기서 분류를 개선할 가능성이 커집니다.

따라서 ID3는 국소적으로 최적의 엔트로피 값을 가장 먼저 검색하는 탐욕적 휴리스틱이다.데이터의 전처리를 통해 정확성을 높일 수 있습니다.

정보 획득

정보 $게인{\displaystyle }$ $A)$ {$displaystyle$IG($A)}$는 $설정{\displaystyle }$S {{$displaystyle$ S$}$를 속성$$A {\$displaystyle$ A$\}$로 분할하기 전과 후의 엔트로피 차이를 나타내는 수치입니다. 즉$,$ $설정{\displaystyle }$$$S {$displaystyle$ S$}$의 불확실성이 어느 정도 감소되었는지를 나타냅니다.$te{\displaystyle }$ A$(표시 스타일$ A$)$

${\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(S)}-\mathrm {H} {(SA)}.$

어디에,

• ${\displaystyle \mathrm{H}}$( ${\displaystyle S}$) \ $displaystyle$$$\ $mathrm${$H$} $$( $S$)– $S의$엔트로피
• ${\displaystyle T}${\$displaystyle$ T$}$ – 집합$S{\displaystyle }$ {\$displaystyle$ S$}$를 $속성{\displaystyle }$A {\$displaystyle$ A$}$로 분할하여 작성된 서브셋으로, S ${\displaystyle =\underset{t}{}}$ t$$ ${\displaystyle \underset{}{}}$ \ $displaystyle$ S = \ $bigcup$_ {$t$ \ $in$ T$}t$
• ${\displaystyle p}$(${\displaystyle t}$ )$${ $displaystyle$p ($t$ ) :$$세트$S$의 요소 수에 대한 t$${ $displaystyle$t$$}의 요소 수의 비율.
• ${\displaystyle H}$( t$$) { $displaystyle$$$\ $mathrm${ $H$} $$($t$ )– $서브셋t의$엔트로피

ID3에서는 나머지 속성별로 (엔트로피 대신) 정보 게인을 계산할 수 있다.정보 게인이 가장 큰 Atribut은 이 반복에서 세트$S를 분할$하기 위해 사용됩니다.

「 」를 참조해 주세요.

• 분류 및 회귀 트리(CART)
• C4.5 알고리즘
• 의사결정 트리 학습
  • 의사결정 트리 모델

레퍼런스

추가 정보

• Mitchell, Tom Michael (1997). Machine Learning. New York, NY: McGraw-Hill. pp. 55–58. ISBN 0070428077. OCLC 36417892.
• Grzymala-Busse, Jerzy W. (February 1993). "Selected Algorithms of Machine Learning from Examples" (PDF). Fundamenta Informaticae. 18 (2): 193–207 – via ResearchGate.

외부 링크

• 세미나 – http://www2.cs.uregina.ca/
• 설명 및 예시– http://www.cise.ufl.edu/
• 설명 및 예시– http://www.cis.temple.edu/
• 의사결정 트리 및 정당 분류