[ML] Decision Tree, 의사결정트리

Decision Tree는 의사결정트리라고도 불리며 흔한 White box 계열의 모델이기에 실무에서 많이 쓰이는 모델 중 하나이다. 

정의는 아래와 같다. 

기계학습(machine learning) 중 지도학습(supervised learning)의 한 종류로 의사 결정규칙(decision rule)을 도표화하여 관심대상이 되는 집단을 몇 개의 소집단으로 예측(prediction) 혹은 분류(classification)을 수행하는 방법. 모형의 구조가 tree 형태를 지니기에 Decision tree라고 불린다.

Decision tree 예시: titanic - ADX 2주차 수업자료 중 일부

위 그림은 Decision tree의 예시이다. 

보면 특정 질문에 따라 기준을 세우고, 그 기준에 따라 그룹을 분할 하는 것을 알 수 있다. 

한번의 분기 때 마다 변수 영역은 두개로 구분되며, 해당하는 정답은 node라고 한다(tree에서 나오는 용어, node or vertex  edges or link )

• 맨 처음 시작을 Root Node

  

• 중간 노드를 Intermediate Node
• 분기가 끝난 노드를 Terminal Node 혹은 Leaf Node라고 한다

 

 

 

 

 

Cost function

Decison tree의 기본 아이디어 또한 다른 ML과 마찬가지로 특정 값을 maximize하거나 minimize하는 것이다. 이번에는 impurity, 즉 불순도를 최소화 하는 것 목적이다. 

불순도란 분류된 node안에 서로 다른 데이터가 얼마나 섞여있는지를 나타내는 지표이다. 

분기기준을 설정 시 현재 노드의 불순도에 비해 자식노드의 불순도는 감소시켜야 모델이 잘 작동하고 있는 것일 것이다. 

 

이런 불순도를 측정하는 방법은 크게 3가지이다. 

Miss classification rate, Gini Index, entropy이다. 

Miss classification rate

miss classifiation rate은 가장 기본적인 불순도 함수로, 식은 위와 같다. 

식을 보면 원소 i가 group g에 맞게 분할 되었다면 1 아니면 0을 한 값을 sum하여 G의 cradinality 즉 group의 총 원소 수로 나누는 것을 확인 가능하다. 

Gini Index

gini idex는 위와 같이 정의된다. 보면 1-p의 제곱이며, p 는 위와 같이 동일하게 node에서의 Pass/Total이다.

최댓값은 0.5이다. 

Entropy(Cross-entropy)

수식을 보면 그냥 entropy식이지만(확률분포 하나에 관해 비교) 몇몇 교재에서는 cross-entropy라고도 한다. 

해당 수식으로 값을 구한 예제는 아래를 보자. 

출처: https://wooono.tistory.com/104

세 cost funtion을 비교한 그림은 아래와 같다. 

즉, missclassification은 조금 더 엄격하게 그 값을 설정하고, gini와 cross-entropy는 확률을 조금 더 보정해주는 개념이다(틀릴 확률이 매우 큰 상황이라면 값을 보정)

Information Gain 

Information gain은 위에서 정한 손실함수가 얼마나 개선되었는가를 판단하는 것이다. 즉, 자식노드로 분할 했을 때 얼마나 개선이 되었는지를 정하는 식이다. 

그럼으로 수식은 아래와 같을 것이다. 

하지만, Child는 여러개이기에 이를 가중합 해주어야한다. 

이때 가중합의 가중치는 바로 해당 자식노드로 분할 되는 확률이다. 

예시를 들면 아래와 같다. 

위와 같이 Gini index를 기준으로 가지치기를 했다고 하자. 

그러면 Inforamtion gain은 아래와 같이 계산된다. 

수식을 보면 10/20이 가중치로 들어가는데, 이는 전체 부모 노드의 element의 개수인 20과 해당하는 자식노등의 element의 개수인 10의 비율임을 확인 가능하다. 

이렇게 구한 Information gain이 주요한 이유는 

어떤 분기를 선택해다 information gain이 최대화되는지를 기준으로 분기가 선택되기 때문이다. 

즉, Feature selction의 기준으로 Information gain은 사용된다. 

Generalization & Pruning

가지치기라고 불리는 Pruning은 Decision tree의 하위 트리를 일부 제거함으로서 일반화 성능을 높이는 것을 의미한다.

보통은 Decision tree를 생성시 option으로 최대 깊이, leaf의 노드의 최대개수 등을 제한할 수 있다. 

또한 생성 이후에도 Pruning이 가능하나 sklearn에서는 사전 가지치기. 즉, 생성 때 노드의 최대개수를 제한하는 방법을 선택한다. 

 

Code implementation

 code는 사이킷런을 쓰면 쉽게 사용가능하다. 

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# Iris 데이터 로드
iris = load_iris()
X = iris.data
y = iris.target

# 데이터를 학습용과 테스트용으로 분할
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 의사 결정 트리 모델 생성
clf = DecisionTreeClassifier()

# 모델 학습
clf.fit(X_train, y_train)

# 테스트 데이터에 대한 예측
y_pred = clf.predict(X_test)

# 정확도 평가
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)

 

 

Code From Scratch 

Code from scratch는 아래와 같다. 작성에  해당 링크와 sklearn의 공개코드를 참조했다. 

https://github.com/zinhyeok/-Breadcrumbsmachine_learning_from_scratch.git

zinhyeok/-Breadcrumbsmachine_learning_from_scratch

자세한 과정은 아래의 다른 게시글을 참고해주면 감사하겠다  😁