[Data Science] 의사결정 트리 (Decision Tree) (2)

정보 이득 (Information Gain)

 

 

엔트로피를 사용하여 속성별 분류 시 데이터가 얼마나 순수한지 (impurity)를 측정하는 지표를 말한다.

 

속성별 엔트로피

 

 

속성 A로 데이터를 분류했을 때 속성 A가 가진 모든 클래스의 각 엔트로피를 계산한 후, 데이터의 개수만큼 가중치를 준다.

 

속성별 정보 이득

 

 

정보 이득이 크면 클수록 A를 기준으로 데이터를 분류했을 때 얻을 수 있는 정보량이 많다는 뜻이다. A를 기준으로 데이터를 나눌 때 엔트로피가 작다면 해당 속성을 기준으로 데이터를 나누기 좋다고 볼 수 있다.

 

ID3 알고리즘

 

성장 (grow) : 일반적으로 의사결정 트리를 생성하는 방법을 성장이라고 부른다. 트리 (나무)를 성장시키는 개념이다. ID3 (Iterative Dichotomiser 3) : 반복적으로 데이터를 나누는 알고리즘 (반복 이분법), 톱다운 (top-down) 방식으로 데이터를 나누면서 탐욕적 (greedy)으로 현재 상태에서 최적화를 추진하는 방법을 선택한다.

# 기본적인 ID3 알고리즘
if 데이터 집합에 있는 모든 항목이 같은 레벨:
	분류 항목 표시를 반환 (ex: buy_yes)
    
else:
	Find Best Split_branch_attribute (ex: attribute - age)
	해당 속성(attribute)을 기준으로 데이터셋 분할
	가지 노드 (branch node) 생성

	for each branch:
    	branch_node.add (Recursive branch split)
        
	return branch node

 

의사결정 트리 알고리즘 특징

 

재귀적 작동	가지가 되는 속성을 선택한 후 해당 가지로 데이터를 나누면, 이전에 적용되 었던 알고리즘이 남은 데이터에 적용된다. 남은 데이터에서만 최적의 모델을 찾는 방법으로 작동한다.
속성 기준으로 가지치기 수행	가장 불확실성이 적은 속성을 기준으로 가지치기를 수행한다.
중요한 속성 정보 제공	이 속성 때문에 ‘해석 가능한 머신러닝’이라고 부른다. 처음 분리 대상이 되는 속성이 가장 중요한 속성이다.

 

의사결정 트리는 모델의 예측 과정을 볼 수 있다.

 

장점	단점
• 쉽고 직관적이다 (시각화로 표현 가능). • D.T가 Rule이 매우 명확하다. • 특징의 스케일링이나 정규화 등의 사전 가공 영향도가 크지 않다. • 전처리 단계없이 사용가능하다.	• 과적합으로 정확도가 떨어진다. • 이를 극복하기 위해 트리의 크기를 사전에 제한하는 튜닝 필요하다.

 

정보 이득의 문제점

 

 

수식의 특성상 속성의 값이 다양할수록 선택의 확률이 높아지는 문제가 발생한다. 데이터가 매우 많고 속성이 다양할 때 가중치의 값이 작아진다. 해당 속성의 엔트로피가 낮아져 단순히 속성 안에 있는 값의 종류를 늘리는 것만으로 정보 이득이 높아진다.

 

C4.5 알고리즘

 

정보 이득을 측정하는 방식을 좀 더 평준화시켜 단순한 정보 값을 대신 사용한다. 기존 정보 이득의 분모에 평준화 함수 SplitInfo를 추가한다.

 

 

클래스가 많을수록 가중치 값이 작아지고 log 가중치 값은 커져 정규화된다. SplitInfo값이 분모에 들어가면서 클래스 불균형에 의해 생기는 불합리한 속성 분류를 보정한다.

 

지니 지수

 

https://www.researchgate.net/figure/Relation-among-Entropy-Gini-Index-and-Misclassification-error_fig1_339471092

 

경제학에서 소득의 불평등도를 측정할 때 사용하는 지표인데, 의사결정 트리에서 각 속성의 불순도를 측정하는 방법으로 사용한다.

 

이진 분할

 

CART 알고리즘의 핵심은 불확실성을 측정하는 기준 값이 엔트로피에서 지니 지수로 바뀐 것이다. 각 속성별 지니 지수 정보는 다음과 같다.