ID3 알고리즘

ID3 알고리즘(Iterative Dichotomiser 3)은 결정 트리 학습법에서 로스 퀸란(Ross Quinlan)이 발명한 알고리즘으로 데이터세트에서 의사결정 트리를 생성하는 데 사용된다. ID3은 C4.5 알고리즘의 전신이며 일반적으로 기계 학습 및 자연어 처리 분야에서 사용된다.

다음 중 하나의 경우 하위 집합에 대한 재귀가 중단될 수 있다.

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

알고리즘 전반에 걸쳐 의사결정 트리는 데이터가 분할된 선택된 속성을 나타내는 각 비종단 노드(내부 노드)와 이 분기의 최종 하위 집합의 클래스 레이블을 나타내는 터미널 노드(리프 노드)로 구성된다.

• 결정 트리 학습법
• C4.5 알고리즘
• 결정 트리 학습법

• Seminars – http://www2.cs.uregina.ca/
• Description and examples – http://www.cise.ufl.edu/
• Description and examples – http://www.cis.temple.edu/
• Decision Trees and Political Party Classification