인공지능개론 | Decision Tree

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

Desicion Tree | 의사결정 트리

초등학교 때나 화살표 방향에 따라서 내가 고른 의사에 따라 결과를 확인하는 심리검사가 유행했는데, 그런 모형이 오늘 알아볼 의사결정 트리, 말 그대로 의사결정하는데 있어서 사용되는 트리에 대해 알아볼 것이다.
여기서 포인트는 큰 범주 즉 heterogenous group을 작은 homogeneous(동일한 목표 값)로 나뉜다. 이 때 나뉠 때는 best split rule에 따라 나뉘게 되는데, 기준은 나누는데 있어서 얼마나 나뉜 값들이 한 목표값만으로 분류되었는지(purity)이다.

Impurity(Diversity) Measure

best split을 결정하기 위해 impurity measure에서 사용되는 아래 두 가지를 소개해본다.

• 엔트로피에 따른 information gain
• Gini (인구 다양성)

impurity degree로 측정하게 되는데, 엔트로피와 information gain은 아래와 같이 계산이 된다.

$p_j\log_2 p_j$ 이 부분은 기댓값이라고 이해하면 된다!($p_j$는 카테고리별 확률)
S는 parent고 S`가 child인데, 이 때 entropy 차이가 클수록 좋은 split이다.

아래는 information gain이 어떻게 이루어지는 지 확인해볼 수 있는 예제이다.

Information Gain

계산하는데 포인트는 무엇을 parent로 둘 것인가? 이다. 한 번 살펴보자.

이런식으로 각 카테고리를 target variable을 transportation으로 두면서 적함한 root node(parent)를 찾는다. Travel cost가 Gain에서 가장 크므로 root node로 설정한다.

별도로 더 나눌 필요 없이 travel cost가 standard면 train으로, expensive하면 car로 순수하게 나뉘어 떨어져 단말노드로 분류된 모습을 확인할 수 있다. 조금 더 분류해보자.

이제 travel cost는 분류가 되었으니, 분류가 되지 않은 부분들 중점으로 다시 계산해보자. transportation을 target variable으로 설정하여 다른 카테고리의 gain을 계산하면 위와 같다.

이런 식으로 계속 계산을 하다보면 아래와 같이 분류 결과가 나오게된다.

Gini Purity

엔트로피와 비슷하나 Gini는 확률 제곱의 합으로 계산된다. 전체적으로 계산하는 방법은 위 information gain 방법과 동일하다.

Advantage? Disadvantage?

Wrap up & Conclusion

의사결정 트리를 heterogenous한 큰 데이터셋에서 homogenous한 작은 분류로 즉, 동일한 목표값(target)을 지닌 값들을 묶어서 분류하는 것이 키포인트였다! 분류하는 방법은 두 개 gain가 gini에 대해서 배웠다.

• Infomration Gain: target variable 중심으로 Gain값이 큰 항목을 parent로 둚으로써 parent가 된 항목을 삭제해나감으로써 Gain을 다시 계산하고 parent로 올려두면서 계산 과정을 반복해나가게 된다.
• Gini: gain과 비슷하나 entropy 대신 확률 제곱의 합으로 계산된다.

이 방법은 직관적이고 쉽고 별도의 사전 지식 없이도 트리를 만들 수 있는 장점이 있으나, local optima에 빠질 수 있어서 불안정한 결과를 보이고 있다. 또한 분기가 많아질 경우, 복잡해지는 단점을 지니고 있다.