Decision Tree
A decision tree is a non-parametric supervised learning algorithm, which is utilized for both classification and regression tasks. It has a hierarchical, tree structure, which consists of a root node, branches, internal nodes and leaf nodes.
Reference : https://www.ibm.com/topics/decision-trees
어떠한 데이터셋에 대해 Root node부터 시작해 분류 기준을 정해나가면서 적절한 Subset으로 데이터를 나눠 나가는 것이 Decision Tree 알고리즘의 핵심이라고 할 수 있다.
위의 예시와 같은 방법으로 의사 결정을 진행해 나가게 되는데, 이 과정에서 Tree의 크기가 너무 커지게 되면(깊어지면) 최종 terminal node가 너무 세분화되는 Overfitting이 일어날 수 있고 동시에 Tree가 너무 복잡해져 효율성이 떨어지게 될 수 있다.
반대로 너무 작아지게 되면(얕아지면) 데이터가 거의 나눠지지 않는 Underfitting이 일어날 수 있다.
적절한 크기의 Decision Tree를 만들기 위해서 두가지의 Metric이 존재하는데
Entropy를 활용한 Information gain과 Gini Impurity이다.
Gini Impurity
Gini Impurity란, 데이터를 split하는 특정 기준 가운데 random한 데이터에 대해서 그 데이터가 얼마나 잘못 분류되었는지를 측정하는 개념으로, 즉 Gini impurity가 낮을수록 데이터가 잘 분류된 것으로 볼 수 있다.
위의 예시로 보면, 'Age'라는 feature에 대한 Gini impurity가 0.343으로 가장 낮기 때문에 데이터를 가장 잘 split할 수 있는 feature로 간주할 수 있으며 결국, Root 노드를 split하는 기준을 'Age'로 삼을 수 있게 되는 것이다.
$D$라는 데이터셋 안에서 $k$개의 class가 존재할 때, 어떤 node에서 데이터 샘플들이 class $i$에 속할 확률이 $p_i$라고 하면,
Gini Impurity를 계산하는 수식은 다음과 같다.
$\text{Gini}(D) = 1-\sum_{i}^{k}p^{2}_{i}$
| Count | Probability | Gini Impurity | |||
| $n_1$ | $n_2$ | $p_1$ | $p_2$ | $1-p^2_1-p^2_2$ | |
| Node A | 0 | 10 | 0 | 1 | $1-0^2-1^2 = 0$ |
| Node B | 3 | 7 | 0.3 | 0.7 | $1-0.3^2-0.7^2 = 0.42$ |
| Node C | 5 | 5 | 0.5 | 0.5 | $1-0.5^2-0.5^2 = 0.5$ |
위와 같은 방식으로 계산된다고 이해하면 된다.
이전의 예시로 돌아가서 'Age'를 기준으로 데이터 $D$를 Youth, Middle Age, Senior로 split했다고 하면 나눠진 각 data subset에 대해서 분류 기준에 부합하는지 여부가 Y/N로 주어지게 될 것이다.
그 때 Age에 대한 Gini Impurity는 다음과 같이 구할 수 있다.
$\text{Gini}_{\text{Age}}(D) = \frac{5}{14} \cdot 0.48 + \frac{4}{14} \cdot 0 + \frac{5}{14} \cdot 0.48 = 0.343$
정리해보면, 어떤 feature를 기준으로 데이터를 split했을때 발생되는 각 데이터 subset안에서 제대로 분류가 이뤄졌는지에 대한 지표로서의 gini impurity가 있고
이를 각 subset의 sample수에 비례한 weighted sum을 한 결과가 최종적으로 해당 feature에 대한 split의 Gini Impurity가 되는 것이다.
CART 알고리즘은 위와 같은 Gini Impurity의 특성을 활용해 적절한 split 기준을 정해 Decision Tree를 전개해 나가게 된다.
cf) Gini Impurity를 metric으로 사용하는 Decision Tree 알고리즘은 CART로서 'Classification and Regression Tree'의 약자로
이름과 같이 회귀와 분류 문제 둘다 사용이 가능한 알고리즘이다.
Entropy & Information gain
우선, Entropy란 Gini Impurity와 유사하게 sample value들의 impurity를 측정하는 metric으로서 수식은 다음과 같다.
$\text{Entropy}(S) = -\sum_{c \in C} p(c)log_{2}p(c)$
S는 entropy가 계산되는 dataset을, c는 S안의 class 그리고 p(c)는 데이터가 c에 속할 확률을 의미한다.
2가지의 class 범위가 존재한다고 할때,
데이터가 한 class에만 존재한다면 $\text{Entropy}=0$이 되고
$-(0 \cdot log_2 1 + 1 \cdot log_2 0) = 0$
데이터가 반반씩 나뉜다면 $\text{Entropy}=1$이 되어 가장 큰 값을 갖는다.
$-(\frac{1}{2} \cdot log_2 \frac{1}{2} + \frac{1}{2} \cdot log_2 \frac{1}{2}) = -(\frac{1}{2} \cdot -1 + \frac{1}{2} \cdot -1) = 1$
따라서 데이터를 가장 확실하게 나누기 위해서는 Entropy가 작은 쪽으로 split 기준을 잡게 되는 것이다.
Information Gain은 Entropy를 알고나면 이해하기 쉽다.
A라는 분류 기준이 있다고 할때, A를 적용하기 전의 Entropy에서 적용 후에
A로 인해 분류된 각 클래스의 Entropy에 대한 weighted sum을 뺀 차이를 나타낸다.
$\text{IG}_A = E(S) - \sum_{c \in Class(A)} \frac{\vert S_c \vert}{\vert S \vert} E(S_c)$
여기서 weight값인 $\frac{\vert S_c \vert}{\vert S \vert}$는 dataset S에서 A가 적용된 후 분류된 Class c에 해당되는 data의 비율을 의미한다.
이해가 잘 되지 않는다면 다음 사이트의 예시를 활용하면 좋을 것 같다.
https://www.ibm.com/topics/decision-trees
What is a Decision Tree? | IBM
A decision tree is a non-parametric supervised learning algorithm, which is utilized for both classification and regression tasks.
www.ibm.com
Entropy와 information gain을 척도로 사용하는 Decision Tree 알고리즘은 대표적으로 ID3가 있다.