Entropy와 Gini Impurity에 대하여: Decision Tree는 어떻게 만들어질까, Classification

📄 Intro

Decision Tree (CART)라는 머신러닝 모델은 데이터를 Root Node에 전달하면서 수많은 Node를 거치며 여러 조건들로 필터링하여 Terminal Node(Leaf Node)에 도착하고, '어떤 Class인지 (Classification)', '어떤 값인지 (Regression)'을 판별합니다. 정확도를 높이기 위해서는 조건들이 많기도 해야겠지만 판별하는 기준(Criterion)이 명확해야 합니다.

 

아래 Decision Tree Visualization에서 그 기준은 Root Node에 있는 petal width <= 0.75나 Right-Child Node에 있는 petal length <= 4.75와 같은 텍스트들을 말합니다.

출처: Data Analytics (https://vitalflux.com/visualize-decision-tree-python-sklearn-library/)

그래서 이번 포스트에서 알아볼 것은 'Decision Tree Node에 있는 조건들은 무슨 기준으로 만들어지는가?'에 대해 알아봅니다.

---

📄 불순도, 불확실성

좋은 기준으로 판별되기 위해서는 그 기준이 '데이터를 어떻게 나누었는가'에 대해 집중해야 합니다. 트리의 관점에서 말하자면, Parent Node로부터 분할된 Child Node에서 데이터는 더 명확해졌는가?를 알아보면 됩니다.

 

'더 명확해졌는가'에 대한 의미는 예를 들어 설명하겠습니다.

Class가 A, B가 있고, 그에 대한 각 데이터가 10개씩 존재하고, Decision Tree를 통해 학습을 한다고 가정하겠습니다.

Parent Node: {A = 10, B = 10}

그리고, 특정한 Criterion에 의해 아래와 같이 Split 되었다고 합시다.

Left Child Node: {A = 5, B = 5}, Right Child Node: {A = 5, B = 5}

잘 나누어진 게 맞나요? 아닙니다. 잘 나누어졌다면 Child Node에서 이 Node는 어떠한 정보를 담고 있는지에 대한 선명도가 뚜렷했어야 합니다. 아래와 같은 경우의 Node가 어떤 정보성을 가지고 있는지 명확해 보이죠.

Left Child Node: {A = 8, B = 2}, Right Child Node: {A = 2, B = 8}

 

• 이처럼 Node가 어떤 정보성을 가졌는지 모르겠거나, Node가 가진 Class 비율이 균등해 보일 때 해당 Node의 불순도가 높다고 하고,
• 특정하게 어떤 Class의 비율이 높아 보인다, 이 Node는 이 정보를 가지고 있다고 할 수 있을 때 해당 Node의 불순도가 낮다고 합니다.

그래서, Decision Tree는 Node를 Split 하여 하위 Node들에 대한 불순도를 줄여가면서 하위 Node들의 정보의 불확실성을 줄이는 것이 목표입니다. 아래에서는 정보의 불확실성을 나타낼 수 있는 2가지 척도 Entropy와 Gini Impurity에 대해 알아봅시다.

---

📄 Entropy

위에서 말했듯이 정보의 불확실성이 높은 경우는 노드가 가지고 있는 데이터가 거의 균등한 경우입니다. 즉, 반대로 낮은 경우를 생각하면 극과 극으로 거의 Proportion을 차지하지 않거나, 대부분의 Proportion을 차지하는 Distribution이 불확실성(= 불순도)이 낮은 경우라고 볼 수 있습니다.

그러한 불확실성을 잘 나타낼 수 있는 Criterion 중 하나는 Entropy입니다. 함수에 대해서 바로 알아보면 아래와 같이 생겼습니다.

$$ Entropy = -\sum_{i=1}^{n}p_{i}\log_{2}p_{i} $$

• \(p_{i}\) = 현재 Node에서 가지고 있는 데이터 집합에 대해 i-th class의 비율을 나타냅니다.
• \(n\) = class의 개수

 

위 2가지 케이스를 그대로 사용해 봅시다.

• {A = 5, B = 5}

$$ -(\frac{5}{10}\log_{2}(\frac{5}{10}) + \frac{5}{10}\log_{2}(\frac{5}{10})) = -(-0.5 -0.5) = 1 $$

• {A = 8, B = 2}

$$ -(\frac{8}{10}\log_{2}(\frac{8}{10}) + \frac{2}{10}\log_{2}(\frac{2}{10})) = -(-0.2568 - 0.4642) = 0.721 $$

 

클래스의 비율이 극적일수록 엔트로피가 낮게 나옵니다. 이게 가능한 이유는 Geogebra를 통해 \(-x\log_{2}{x} (0 \leq x \leq 1)\)을 구현해 봤습니다.

0과 1에 근접할수록 0에 가까워지는 것을 보아 데이터에서 클래스의 비율이 극명할수록 불확실성이 줄어든다는 것을 알 수 있습니다.

---

📄 Gini Impurity

그다음은 Gini Impurity라는 Criterion입니다. Entropy와 마찬가지로 낮을수록 정보의 불순도가 낮고, Node의 순수성이 높은 뜻을 가집니다.

$$ \sum_{i=1}^{n}p_{i}(1-p_{i}) $$

• 변수에 대한 설명도 엔트로피와 같습니다.
• \(p_{i}\) = 현재 Node에서 가지고 있는 데이터 집합에 대해 i-th class의 비율을 나타냅니다.
• \(n\) = class의 개수

함수도 Entropy와 비슷하게 생겼는데 Geogebra로 그려보았습니다. 마찬가지로 0과 1에 근접할수록 Impurity가 낮아짐에 따라 불확실성이 줄어든다는 특징이 있습니다.

---

📄 Information Gain

이러한 척도를 통해 각 노드의 데이터 집합에 대한 클래스의 비율을 통해 Entropy와 Gini Impurity를 구할 수 있었습니다.

그럼 Criterion을 가지고서 무엇을 통해 Node를 Split 하냐면, Parent Node의 불순도와 Child Node(Left and Right)의 불순도 차이를 구합니다. 이 차이 값을 Information Gain(정보 이득)이라고 합니다. 우리의 목표는 이 Information Gain이 최댓값을 갖도록 하는 것인데 이는 상위 Node에서 하위 Node로 Split 될 때, 하위 노드의 불순도를 많이 줄였다는 것과 같습니다. (= 하위 노드의 클래스 비율이 조금 더 극적으로 나뉘었다.)

$$ Information\,Gain =
(Parent's\,\,Impurity)
-
(\frac{N_{left}}{N_{parent}}\times(Left\,\,child's\,\,Impurity)+\frac{N_{right}}{N_{parent}}\times(Right\,\,child's\,\,Impurity)
) $$

하지만, 아직 풀리지 않은 궁금점이 남습니다.

Parent Node와 Child Node의 불순도를 계산하기 전에 Split은 무슨 기준으로 한 것인가?

-> Data의 Feature를 이용합니다.

 

여기서 인지하고 있어야 할 점은 데이터는 여러 Feature를 가진다는 것입니다. 예시를 간단하게 들기 위해 Feature의 언급은 없었지만, 모든 Feature를 기준으로 Split 되어 불순도를 측정한 것을 기반으로 Information Gain이 가장 큰 값을 가지는 Feature와 해당 Feature의 기준 값을 Node를 Split 하는 Criterion으로 채택합니다.

 

(아래 예시에서는 petal width라는 feature와 기준 값이 0.75로 채택되었습니다.)

 

 

즉, Information Gain을 구하기 위해서는 한 Feature마다 Information Gain의 최댓값을 가지도록 하는 기준 값을 찾고, 모든 기준 값들로부터 Information Gain의 최댓값 중의 최댓값을 구하는 게 Information Gain을 구하는 방법입니다.

 

+ 여러 웹에서 Information Gain에 대한 Formula를 언급할 때, Child Node의 불순도 평균을 구하는데 평균이 아닌 Split 된 후에 (Child Node Sample 개수)/(Parent Node Sample 개수)의 Proportion을 각 Child Node에 곱하여 Child Node의 전체적인 불순도로 사용됩니다.

 

이제 위의 Decision Tree를 다시 보면 이런 해석이 가능합니다.

1. Gini Impurity를 통해 Root Node의 불순도를 확인하였다. -> 0.687
2. 이 Gini Impurity는 (35/105)(1 - 35/105) * 3 = 0.667이 맞다.
3. 현재 여기서 발생하는 Information Gain은 0.667 - ((35/105)*0.0 + (70/105)*0.5) = 0.334이다.
4. 0.334라는 가장 큰 Information Gain이 만들어지게 된 Feature는 'petal width'와 기준 값은 0.75이다.

---

📄 Entropy와 Gini Impurity의 차이

그렇다면, Entropy와 Gini Impurity는 둘 다 노드의 불순도를 측정하는 공통점이 있는데 구하는 방법이 다른 거 외에는 차이점이 보이지 않습니다. 하지만, Entropy가 log를 사용함으로써 생기는 미묘한 차이가 있습니다.

1. Entropy는 조금 더 미세한 차이를 감지한다. -> 로그 함수를 사용하기 때문에 Gini Impurity보다 미세한 차이를 감지하여 노드의 순수성을 정확하게 평가할 수 있다. 또한, 불균형한 데이터셋에도 Gini보다는 Entropy가 더 좋은 효과를 보인다.
2. Gini Impurity는 Entropy에 비해 상대적으로 간결하다. -> Entropy보다 간결하다는 것은 Entropy가 적용되어도 될 문제에 Gini Impurity를 적용함으로써 간결하고 더 빠르고, 직관적으로 불순도를 처리할 수 있다. 그래서 일반적으로 Gini Impurity를 Binary Classification 문제, Entropy를 Mulit Classification 문제에 적용이 되는 게 일반화되어가고 있다.