의사결정나무(Decision Tree) :: CART 알고리즘, 지니계수(Gini Index)란?

이전 포스팅에서 의사결정나무란 무엇인지, 어떤 기준으로 모델을 만들어가며 불순도가 무엇인지와 ID3 알고리즘에 대해 소개했다.

 

지난 포스팅 바로가기

https://leedakyeong.tistory.com/entry/Decision-Tree%EB%9E%80-ID3-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

Decision Tree란? :: ID3 알고리즘, 엔트로피란?

이번에는 의사결정나무의 또 다른 알고리즘인 CART 알고리즘에 대해 소개하겠다.

---

CART 알고리즘은 불순도를 지니계수(Gini Index)로 계산한다. 

 

지니계수란?

 

지니계수란? 불순도를 측정하느 지표로서, 데이터의 통계적 분산정도를 정량화해서 표현한 값

 

이를 식으로 나타내면 다음과 같다.

 

$$ G(S) = 1-\sum_{i=1}^c p_i^2 $$

S : 이미 발생한 사건의 모음, c : 사건의 갯수

 

즉, Gini Index가 높을 수록 데이터가 분산되어있음을 의미한다.

---

CART 알고리즘

 

CART 알고리즘은 지니계수로 불순도를 계산한다 했다.

그렇다면, 다음 그림에서 A와 B중 O와 X를 더 잘 구분하는 기준은 무엇일까? 

 

이를 지니계수로 계산해보면 다음과 같다.

 

1) A를 기준으로 분할했을 때 지니계수

 

2) B를 기준으로 분할했을 때 지니계수

 

지니계수는 불순도를 의미하기 때문에 불순도가 더 적은 B로 먼저 분할하는 것이 좋다.

---

나이, 수입, 학생 여부, 신용등급에 따른 컴퓨터 구입 여부를 CART 알고리즘으로 분류해보겠다.

 

 

* 단, CART 알고리즘은 앞서 소개한 ID3 알고리즘과 달리, Binary Split 형태를 따른다.

예를들어, 위 데이터에서 age 의 경우 youth, middle_aged, senior를 ID3는 가지를 3개로 뻗어냈지만, CART는 youth와 그 외, middle_aged와 그 외, senior와 그 외의 경우를 각각 계산하여 2개의 가지만 뻗는다.

 

 

Approach1) 각 속성에 대해 분할 후 지니계수 계산

1-1) age

 

age = youth

 

 

1-2) income

 

...

 

 

같은 방식으로 다른 속성들에 대해서도 지니계수를 계산해주면 다음과 같은 결과를 얻을 수 있다.

 

 

즉, 나이, 수입, 신용, 학생 중 나이(나이에서도 middle_age와 그 외) 로 나눴을때 불순도가 가장 낮아짐을 알 수 있다.

따라서 나이 = middle_age와 그 외로 가장 먼저 분할한다.

 

 

이후, 각 terminal node에 대해서도 위 계산을 반복한다. 

"age = middle" 일 때는 yes 에 대해 순도 100%로 나뉘었기 때문에, youth, senior에 대한 데이터만 가지고와서 

또 다시 각 속성에 대해 분할 후 Gini Index를 계산한다.

 

---

다음 포스팅에서는 독립변수 즉, X가 범주형이 아니라 연속형일 때 계산하는 방법에 대해 소개하겠다.