[이론]Study on Decision Tree

출처 : https://www.kaggle.com/code/prashant111/decision-tree-classifier-tutorial

의사결정나무 알고리즘

의사결정나무 알고리즘은 가장 널리 사용되는 기계학습 알고리즘 중 하나입니다. 특정 문제를 해결하기 위해 트리와 같은 구조를 사용합니다. 분류 및 회귀 목적으로 사용할 수 있는 지도 학습 알고리즘 클래스에 속합니다.
의사결정나무 알고리즘은 루트 노드, 분기 및 리프 노드를 포함하는 구조입니다. 각 내부 노드는 특성에 대한 테스트를 나타내고, 가 분기는 테스트 결과를 나타내며, 각 리프 노드는 분류나 회귀된 클래스 레이블을 포함합니다. 트리의 최상위 노드는 루트 노드이고 분류 또는 회귀를 바라는 데이터셋 전체를 포함합니다.

/ 분류 및 회귀 트리(CART, Classification And Regression Tree)

의사결정나무 알고리즘 용어

루트 노드(root node) : 전체 모집단 또는 표본을 나타냄, 이것은 두 개 이상의 동종 세트로 더 나뉨

Splitting : 노드를 두 개 이상의 하위 노드로 나누는 과정

결정 노드(decision node) : 자식 노드가 추가 하위 노드로 분할되면 결정 노드라고 함

리프/터미널 노드(leaf/ terminal node) : 분할되지 않는 노드를 리프 또는 터미널 노드라고 함

가지치기(pruning) : 결정 노드의 자식 노드를 제거하는 것을 가지치기라고 함

분기/서브 트리(branch/sub-tree) : 전체 트리의 하위 섹션을 분기 또는 하위 트리라고 함

부모 및 자식 노드(parent and child node) : 자식 노드로 분할된 노드를 자식 노드의 부모 노드라고 하고 자식 노드는 부모 노드의 자식입니다.

의사결정 트리 용어 다이어그램

의사결정나무 알고리즘의 장점

• 전처리 필요하지 않음
• 주요 속성 파악 가능
• 해석이 용이함, 가지의 흐름을 따라 이해
• 지식 추출이 쉬움, 의사결정나무에 생성된 룰을 변환하여 사용

의사결정나무 알고리즘의 단점

• 경계면(분할 기준)에 근접한 데이터 분류 시 오류가 발생
• 비 안정성, 테스트 데이터를 이용할 경우 분류 오류 발생
• 이진 분리만 사용, 깊이가 깊어져 필요한 컴퓨터 자원이 큼 

가지치기 기준(속성 선택 기준)

• Information gain(정보 획득량) : 속성을 범주형으로 가정
• gini 불순도(Gini index) : 속성을 연속형으로 가정

Information gain(정보 획득량)

Entropy

엔트로피는 주어진 데이터 세트의 불순물을 측정합니다. 물리학 및 수학에서 엔트로피는 확률 변수 X의 무작위성 또는 불확실성이라고 합니다. 정보 이론에서 엔트로피는 예제 그룹의 불순물을 나타냅니다. 정보 이득은 엔트로피의 감소입니다. 정보 이득은 주어진 속성 값을 기반으로 데이터 세트의 분할 전 엔트로피와 분할 후 평균 엔트로피 간의 차이를 계산합니다.

 

엔트로피 공식

 

Entropy = \(∑_{i=1}^c\)\(-p_i\) * \(log_2\)(\(p_i\))

# 여기서 c는 클래스의 수이고 \(p_i\)는 i번째 클래스와 관련된 확률입니다.

 

ID3(반복 이분법) 결정트리 알고리즘은 엔트로피를 사용하여 정보 이득을 계산합니다. 따라서 각 속성의 엔트로피 측정하고 감소를 계산하여 정보 이득을 계산할 수 있습니다. 정보 획득량이 가장 높은 속성이 노드에서 분할 속성으로 선택됩니다.

gini 불순도(Gini index)

CART(Categorical and Regression Trees)가 사용하는 또 다른 속성 선택 측정은 Gini 인덱스입니다.
하나의 노드에 있는 샘플이 모두 같다면 순수하다(Gini = 0)라고 합니다.

 

Gini 불순도 공식

 

Gini = 1- \(∑_{i=1}^c\)(\(-p_i\)\()^2\)
# 여기서 다시 c는 클래스의 수이고 \(p_i\)는 i번째 클래스와 관련된 확률입니다.

 

불연속 값 속성의 경우 선택된 속성에 대한 최소 지니 인덱스를 제공하는 하위 집합이 분할 속성으로 선택됩니다. 연속 값 속성의 경우 전략은 인접한 값의 각 쌍을 가능한 분할점으로 선택하고 분할점으로 선택된 더 작은 지니 인덱스를 갖는 점을 선택하는 것입니다. 최소 지니 인덱스가 있는 속성이 분할 속성으로 선택됩니다.

의사결정나무 알고리즘의 과적합

과적합은 의사결정나무 모델을 구축하는 동안 발생하는 실질적인 문제입니다. 과적합의 문제는 알고리즘이 훈련 세트 오류를 줄이기 위해 계속 더 깊어지지만 결과적으로 테스트 세트 오류 증가로 이어집니다. 다시 말해 모델의 예측 정확도가 떨어집니다. 일반적으로 데이터 이상치 및 불규칙성으로 인해 많은 분기가 구축되는 것을 원인으로 발생합니다.

의사결정나무 알고리즘의 과적합 방지

사전 가지치기(Pre-Pruning)

 

의사결정나무를 진행할 때 사전에 모델의 깊이 제한에 대한 설정을 하고 모델링을 진행합니다. 그러나 적절한 깊이 제한 설정이 어렵습니다.

 

사후 가지치기(Post-Pruning)

 

완전한 의사결정나무 모델을 만들기 위해 모델은 점점 깊어집니다. 교차 검증 데이터를 사용하여 가지치기의 효과를 확인합니다. 노드를 확장할 경우 모델의 기능이 개선되는지 여부를 테스트합니다. 개선 사항이 표시되면 해당 노드를 확장하고, 그렇지 않다면 리프 노드로 변환합니다.