Decision Tree:의사결정나무

Decision Tree

Decision Tree: 의사결정나무, 결정트리라고 부르며, 대표적인 non-parametric 모델이다. 또한 화이트박스(White-box)모델로 설명가능하다.  아래와 같이 모델이 어떤 기준으로 분류하였는지를 확인할 수 있다. 

기본적인 Decision tree 모델인 `CART(Classification And Regression Tree)`에 대해서 알아볼 것이다.

이 모델은 여러 결정트리모델중 하나로 대부분이 이 CART 알고리즘을 사용한다. 

우선 트리는 다음과 같은 용어들로 정의된다.

Impurity(불순도)

CART는 노드마다 feature하나를 골라서 최적의 기준으로 나눌 수 있도록 기준을 정하는데, 이 최적의 기준을 `불순도(Impurity)`라는 개념으로 정한다. 불순도란 불순한 정도 즉 섞여있는 정도를 의미한다. 따라서 불순도가 낮은 경우가 제일 안섞여있다는 의미로 잘 분류되어 있는 상태를 말한다. 따라서 CART는 분기 기준을 설정할 때 현재노드의 불순도보다 자식노드의 불순도가 감소하도록 정해야 하며, 이러한 현재노드와 자식노드 불순도의 차이를 `Information Gain(정보획득)`이라 한다. 이러한 불순도를 수치적으로 나타내는 방법에는 2가지가 있는데, `Gini index`와 `Entropy index`다.

Gini index(지니 지수)

Gini 지수는 CART알고리즘의 tree에서 사용된다. 

Gini지수는 $ \bf{Gini(D) = 1 - \sum_{i=1}^{J} p_i^2} $ 로 나타내며 최댓값은 0.5이다. 또한 다음과 같이 계산한다.

Entropy index(엔트로피 지수)

두 번째 방법으로는 Entropy 지수인데, 이는 ID3이라는 tree알고리즘에서 사용되며, 이는 수식으로 $ \bf{H(D) = -\sum_{i=1}^{J} p_i \log_2(p_i)} $이다. 동일한 예제에서 엔트로피지수는 다음과 같다. 

두 불순도 수치 모두 줄어드는 방향으로 트리를 구성해나가야한다. 

 

decision tree 학습 방식

그러나 최적의 input feature이 실수값인 경우에는 범위가 무한대이기 때문에 최적의 tree를 찾는 게 힘들다. 따라서 heuristic 한 방법을 사용한다. 아래와 같이 feature 1과 feature 2를 이용하여 target을 예측한다고 해보자.

feature1	feature 2	target
42	18	1
45	27	0
48	22	0
60	26	1
72	29	0

1) 우선 feature 1에 대하여 정렬한다. (현재 위 표는 정렬된 상태)

이제 heuristic한 방법을 사용하는데, target이 바뀌는 지점을 candidate split으로 지정한다. 예를 들어 42와 45에서 바뀌기 때문에 43.5를 그다음은 48과 60 사이 54를 이런 식의 후보 기준을 선정한다. 

2) 다음으로 위 표를 feature 2기준으로 정렬한다.

1번과 동일하게 후보 기준을 찾는다.

3) 위 과정을 진행했다면 여러 후보 기준들이 생길 텐데 (ex feature  1>43.5일 경우는 target이 1 아닐 경우 target이 0 이런 후보 기준. ) 이러한 모든 기준을 이용하여 target을 분류한 다음 를 Information gain을계산한다. 이후 Information Gain이 가장 작게 나올 경우의 기준을 분기 기준으로 선정한다. 위 과정을 계속하여 반복한다. 

4) 특별한 제약조건이 없다면 leaf node가 모두 순수한 상태가 되면  멈춘다.

 

Pruning(가지치기)

그러나 위와 같이 모든 경우들을 반복하면서 자주 쪼개개되면서 gini 지수가 0이 될 때까지 반복한다면 training data에 과적합이 되기 때문에 pruning(가지치기)를 통해서 이런 것들을 조절해줘야 한다. 이들은 보통 파라미터로 사용할 수 있다. 

 

장/단점

이러한 결정트리의 장단점은 아래와 같다.

장점: 데이터의 전처리를 하지 않아도 된다.(정규화, 결측치, 이상치 등) / 수치형과 범주형을 모두 다룰 수 있다.

단점: 샘플의 사이즈가 크면 효율성이 떨어진다 / 과적합이 될 수 있다. / 한번에 하나의 변수만 고려하므로 변수간 상호작용을 파악하기 어렵다 / 데이터가 약간이라도 달라지면 트리의 모양이 크게 변한다.