의사 결정 트리는 각 내부 노드가 속성에 대한 테스트를 나타내고, 각 부서가 테스트 결과를 정의하고, 리프 노드가 클래스 또는 클래스 분포를 설명하는 순서도와 같은 트리 메커니즘입니다. 트리에서 가장 높은 노드가 루트 노드입니다.
의사결정 트리 학습을 위한 알고리즘
알고리즘 − 주어진 교육 정보에서 의사 결정 트리를 만듭니다.
입력 - 이산 값 속성으로 설명된 훈련 샘플, 샘플; 학생 속성 세트, 속성 목록.
출력 − 의사 결정 트리.
방법
-
노드 생성 N;
-
샘플이 모두 같은 클래스이면 C 다음
-
클래스 C로 레이블이 지정된 리프 노드로 N을 반환
-
속성 목록이 null이면
-
샘플에서 가장 일반적인 클래스로 레이블이 지정된 리프 노드로 N을 반환합니다. // 다수결
-
속성 목록 중에서 정보 이득이 가장 높은 속성인 test-attribute를 선택합니다.
-
테스트 속성으로 노드 N에 레이블을 지정합니다.
-
test-attribute의 알려진 값 ai 각각에 대해 // 샘플을 분할합니다.
-
test-attribute=ai 조건에 대해 노드 N에서 분기 성장 .
-
하자i test-attribute=ai인 샘플의 샘플 세트입니다. .
-
si가 비어 있으면
-
샘플에서 가장 일반적인 클래스로 레이블이 지정된 리프를 연결할 수 있습니다.
-
그렇지 않으면 의사 결정 트리 생성( si,attribute-list - test-attribute)에서 반환된 노드를 연결합니다.
의사결정 트리 유도
예를 들어 결정 규칙의 자동 생성을 규칙 유도 또는 자동 규칙 유도라고 합니다. 의사 결정 트리의 암시적 설계에서 의사 결정 규칙을 생성할 수 있으며 규칙 유도라고도 하지만 트리 유도 또는 의사 결정 트리 유도라는 용어는 지속적으로 선택됩니다.
의사 결정 트리 유도의 기본 알고리즘은 탐욕 알고리즘입니다. 하향식 재귀 분할 정복 방식으로 의사 결정 트리를 생성하는 데 사용됩니다. 의사결정나무 학습을 위한 기본 알고리즘은 유명한 의사결정나무 유도 알고리즘인 ID3의 한 형태입니다.
기본적인 방법은 다음과 같습니다 -
-
트리는 훈련 샘플을 정의하는 개별 노드로 시작합니다.
-
샘플이 모두 유사한 클래스이면 노드가 리프로 바뀌고 해당 클래스로 레이블이 지정됩니다.
-
알고리즘은 정보 이득이라고 하는 엔트로피 기반 측정을 샘플을 단일 클래스로 나눌 속성을 선택하기 위한 경험적 방법으로 적용합니다. 이 속성은 노드에서 "테스트" 또는 "결정" 속성으로 발전합니다. 이 형태의 알고리즘에서 모든 속성은 범주형입니다. 즉, 불연속 값입니다. 연속 값 속성은 이산화되어야 합니다.
-
테스트 속성의 알려진 값마다 부서가 생성되고 샘플이 적절하게 나뉩니다.
-
알고리즘은 유사한 프로세스 루핑을 사용하여 각 분리에서 샘플에 대한 의사 결정 트리를 형성합니다. 속성이 노드에 나타났기 때문에 노드의 일부 자손에서 처리되지 않아야 합니다.