[ML] Decision Tree

Reference

💻 딥러닝의 깊이 있는 이해를 위한 머신러닝 강의 2-1
🔗 Decision Tree Concept of Purity
🔗 What is a Decision Tree?

저는 해당 강의를 듣고 greedy recursive splitting 전략을 사용한다는 부분에서 이해가 명확히 되지 않아,

머신러닝 지도학습의 가장 기본적인 알고리즘인 Decision tree를 다시 한 번 정리하려고 합니다.

해당 포스팅의 내용과 이미지는 위의 강의와 아래 포스팅을 참고했음을 밝힙니다.

위 이미지를 살펴봅시다.

은행에서 대출을 받으려면 고려해야 할 점들이 잇습니다.

수입이 어느 정도인지, 직장을 얼마나 오래 다녔는지, 신용카드로 결제를 하는지 등의 여부를 말이죠.

이건 가장 기본적인 형태의 decision tree입니다.

decision tree

decision tree는 regression 및 classification 문제에 주로 사용되는 non-parametric 기계학습 모델입니다.

decision tree는 예측한 변수 데이터를 기반으로 결과 변수에 대해 순차적이고 계층적인 결정을 내립니다.

그래서 종류가 매우 다양하며, 적용되는 응용 분야에 따라 사용자가 마음대로 변환해서 사용할 수 있는 알고리즘이기도 합니다.

non-parametric은 error 또는 data distribution에 대한 기본 가정이 없음을 의미합니다.

기본적으로 관찰된 데이터를 기반으로 model을 구성합니다.

그래서 decision tree의 특징으로

• feature type에 따라 종류가 달라짐
• threshold 값 결정에 따라 종류가 달라짐
• stop criterion에 따라 종류가 달라짐

이 있습니다.

결국은 학습 데이터를 가장 잘 표현하는 decison tree를 찾아내는 과정입니다.

학습하는 방법으로

1. 주어진 데이터를 두 개의 나뉜 데이터의 개수가 서로 비슷하도록 하는 방법
2. 나눴을 때 정확도가 가장 높은 방향으로 나누는 방법
3. 나눴을 대 단 한 개의 sample만 한쪽 방향으로 가고 나머지 sample은 반대쪽으로 빠지게 하는 방법

등이 있습니다.

3번째 방법은 tree의 높이가 길어지고, 한쪽으로 쏠리고, split을 많이 해야한다는 단점이 있는데요.

이는 sample의 개수 n개, feature type d개, k개의 threshold에 따라 $n*d*k$개의 계산으로 이루어집니다.

sample이 많으면 자연스럽게 학습 시간이 길어지며, feature type이 많거나 threshold를 너무 세세하게 나누면 계산량이 늘어납니다.

그래서 각각의 노드를 계산할 때 feature type의 경우를 random하게 결정하는 방법과 threshold를 나누는 기준을 2~3개 정도로 적게 해서 계산량을 줄이는 방법을 사용합니다.

split node는 많은 조합이 나올 가능성이 있고, 완벽한 decision tree를 학습하는 것은 불가능합니다.

그런 의미에서 decision tree는 일반적으로 greedy recursive splitting 전략을 사용합니다.

Splitting Algorithm

decision tree의 목표는 각 노드의 끝에서 최선의 선택을 하는 것입니다.

이 관점에서 이를 수행하는 알고리즘이 탐욕적(greedy)이며 재귀적(recursive)하다고 볼 수 있는 것입니다.

Greedy는 가장 최적의 결정을 내리는 것을 의미하고 재귀적 의미는 더 큰 질문을 더 작은 질문으로 나누고 같은 방식으로 해결한다는 의미입니다.

각 노드에서 splitting 하는 decision은 purity이라는 metric에 이루어집니다.

만약 노드가 50:50 비율로 균등하게 분할되면 노드는 100% 순수하지 않고, 모든 데이터가 단일 클래스에 속할 때 100% 순수하다고 표현합니다.

모델을 최적화하기 위해 최대 purity에 도달해야 합니다.

decision tree에서 purity 개념은 하위 집단에 속하는 그룹의 데이터 요소 비율을 기반으로 결정하는데요.

예를 들어 세트가 클래스 A의 항목 60%, 클래스 B의 30%, 클래스 C의 10%로 구성된 경우 purity는 60%입니다.

decision tree는 행을 자식 노드로 나누는 분할로 구성되기 때문에, tree가 binary로 간주되는 경우 해당 노드에는 두 개의 자식이 있게 됩니다.

이런 동일한 절차로 하위 그룹을 분할하며, 이 과정을 앞에 나왔던 recursive하다고 볼 수 있는 것입니다.

spliting은 대상 변수의 값을 예측하는데 사용할 수 있는 tree를 구성하기 위해 선택되며,

training set에서 decision tree를 유도하기 위한 기본 알고리즘이 greedy인 것입니다.

그리고 이 하위 집단의 가장 purity함, 즉 분기 노드의 가장 명확한 분할을 목표로 학습이 진행됩니다.

purity와 gni 계수 등에 대한 개념 설명은 위키백과에서 더 자세히 볼 수 있습니다.