의사결정나무(Decision Tree) 특징 및 동작 원리 - 불순도 알고리즘

이 글에서는 의사결정나무 알고리즘에 대해 설명해 보도록 하겠습니다. Tree 모델 중에 가장 기본이 되는 모델이기 때문에 원리를 알아 놓으면 다른 모델들의 동작원리를 유추할 수 있습니다. 우리가 많이 사용하고 있는 XGBoost, LightGBM, CatBoost 등도 모두 Tree 모델들입니다. 

『 '데이널'의 컨텐츠에 포함된 정보는? 』

 

Decision Tree의 특징은?

의사결정나무 알고리즘은 데이터 사이에 존재하는 패턴을 찾아 예측 가능한 규칙들의 조합으로 나타냅니다. 한마디로 잘게 분해한다는 이야기죠. 그 분해하는 모양이 ‘나무’와 같아서 Decision Tree라고 불립니다. 패턴을 찾아 동작하는 방식은 질문을 던져 대상을 좁혀나가는 ‘스무고개’ 놀이와 비슷한 개념으로 이해하면 좋습니다.

 

이러한 방식은 프로그래밍에서 이진트리(binary tree), 데이터베이스에서 B-tree 인덱스에서도 비슷하게 차용하는 원리입니다. 답을 찾기 위한 결정을 위해 ‘예’ 또는 ‘아니오’ 답변을 받을 질문을 이어 나가면서 학습을 하게 됩니다. 어떻게 보면 심플한 원리에 의해 동작한다고 할 수 있습니다.

 

의사결정나무는 분류(clasification)와 회귀(regression) 모두 사용할 수 있는 알고리즘입니다. 이 말을 타겟변수가 범주형이나 연속형  모두 예측 가능하다는 의미입니다. 

• Classification Tree : 범주형 변수(분류)
• Regression Tree : 수치형 변수(예측)

Decision Tree는 탐욕적 알고리즘(greedy algorithm)이라는 별칭이 있습니다. 그 순간의 최적이라고 생각되는 것을 선택해 나가는 방식이기 때문입니다. 아마도 순간적으로 최선의 이득을 취한다는 부분이 탐욕스럽다(?)고 표현한 걸로 보이네요.

 

Regression Tree 기준은 구분 이후 각 영역의 순도(homogeneity)가 증가, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행합니다.

 

이런 방식을 Tree and Rules 구조라고 합니다. 결과는 규칙으로 표현됩니다. 이런 방식으로 분할 영역이 한 개의 타깃 값을 가질 때까지 반복합니다. 최종적으로 타깃 하나로만 이뤄진 리프 노드를 pure node(순수 노드)라고 합니다. 결국 마지막에는 특정 노드에 분리되게 됩니다.

 

그렇다면 회귀 모델에서는 어떻게 할까요? 회귀 모델도 분류와 동일한 방식으로 진행됩니다. 단지 리프 노드의 훈련 데이터의 평균값으로 예측 결과를 내면 됩니다.

 

예를 들어, 날씨에 대해 분류 모델에서는 '따뜻하다', '춥다' 로 분류한다고 하면 여러 패턴 분석을 통해 두개 중에 하나를 선택할 것입니다. 회귀 모델에서는 날씨 온도를 예측한다고 하면 온도들의 평균값으로 결과값이 나옵니다.   
 

Decision Tree

Decision Tree 구조

Decision Tree는 Root node, Intermediate node, Leaf node로 구성되어 있습니다. 그리고 중간 마디(Intermediate node) 깊이는 로직에 따라 다릅니다. Leaf node에 속하는 데이터개수를 합하면 Root node의 데이터수와 일치합니다. 이것은 교집합(서로 겹치는 부분)이 없다는 의미입니다. 

• Root node(뿌리 마디) : 가장 중요한 분류 기준으로 feature(속성)에 해당됩니다. 
• Intermediate node(중간 마디) : 뿌리와 끝마디가 아닌 나머지 마디를 말합니다. 
• Leaf node or Terminal node(끝마디) : 최종 분리된 부분집합을 의미합니다. 

 

동작 원리(분할 기준)

의사결정나무의 분할 기준은 그룹이 최대한 동질 하도록 반복적으로 레코드 하위를 분리합니다. 다시 말해서 불순도 알고리즘을 이용한 계산식에 의해 Tree를 구성합니다.

• Purity : 한쪽 데이터만 존재할수록 높음, 더 깨끗한 데이터를 의미합니다. 
• Entropy : 무질서도로 Purity의 반대의 개념입니다. 

각 영역의 순도가 증가, 분순도가 최대한 감소하도록 하는 방향으로 학습 진행합니다. Information gain(정보이득)은 정보 이론에서 순도가 증가 또는 불확실성 감소하는 것을 의미합니다. 부모 노드보다 자식 노드의 순수도가 증가하도록 분류나무를 형성해 나갑니다. 여기서 불순도 알고리즘을 사용합니다. 

 

불순도(Impurity) 알고리즘

불순도 알고리즘은 해당 범주 안에 서로 다른 데이터가 얼마나 섞여 있는지를 기준으로 결정트리의 불순도를 최소화하는 알고리즘을 말합니다. 불순도 알고리즘 종류는 지니 지수(Gini index), 엔트로피 지수(Entropy index), 카이제곱 통계량(Chi-square Statistic)이 있습니다.

 

지니와 엔트로피 어떤 걸 사용해도 큰 차이는 없습니다. 이 내용의 근거는 핸즈온 머신러닝 237page를 참고하시면 나와 있습니다. 지니 지수가 조금 더 계산이 빠릅니다. 기본값으로 이용하기에 좋습니다. 지니 지수는 가장 빈도 높은 크래스를 한쪽 가지로 고립시키는 경향이 있습니다. 반면 엔트로피는 좀 더 균형 잡힌 트리를 만드는 특성이 있습니다. 

 

1. 지니 지수

지니 지수는 어떤 노드의 구성이 얼마나 순수한지를 계산하여 나온 값입니다. 예를 들어, 지니계수가 ‘0’ 이면, 모든 데이터가 균일하다는 것입니다. 동일한 데이터만 있다는 말이 됩니다. 

2. 엔트로피 지수

엔트로피 지수는 불순도를 수치적으로 나타낸 척도입니다. 얼마나 무질서했는지를 나타냅니다. 엔트로피 높으면 불순도 높다는 것을 의미합니다. 지니 지수와 비슷하지만 log를 취함으로써 정규화 거친 지수라고 이해하면 됩니다. 예를 들어, 엔트로피 1이면, 불순도가 최대입니다.   

3. Information Gain(정보획득)

Information Gain은 전체 엔트로피와 분할 후 엔트로피의 차이 대한 값입니다. 

• 정보획득량 = Entropy(T) – Entropy(A)

예를 들어, 불순도가 1인 상태에서 0.7인 상태로 바뀌면, 정보획득은 0.3이 됩니다. 정보획득량을 이용해 더 이상의 정보획득이 없을 때까지 트리를 생성합니다. IG(정보이득) 값은 클수록 좋다고 판단할 수 있습니다.

Information Gain ratio(정보이득 비)의 수식은 다음과 같습니다. 여기서 $ 𝐼_{𝑟𝑒𝑠} $는 특정 속성으로 분할한 후의 각 부분집합의 정보량의 가중평균을 말합니다. 

 

마치며

지금까지 의사결정 나무의 특징과 알고리즘의 동작 원리에 대해 자세히 알아보았습니다. 추가적으로 의사결정 나무(Decision Tree)의 종류와 장단점에 대해 더 궁금하시면 아래 글을 참고하시기 바랍니다. 

 

* 함께 읽으면 좋은 글

의사결정나무(Decision Tree) 종류 및 학습 - 장단점