의사결정나무, Decision Tree

분류(classification)과 회귀(regression)문제를 풀기 위한 다양한 종류의 머신러닝 모델이 존재한다. 이 때, 단일 모델을 사용하는 대신 여러 모델을 특정 방식으로 조합하면 성능이 더 나아지는 경우가 있다.

1. 배깅(bagging)
2. 부스팅(boosting)
3. 여러 모델 중 하나의 모델을 선책해서 예측을 시행 ex) decision tree(의사결정나무)

오늘은 이 중에서 decision tree(의사결정나무)에 대해 알아볼 것이다.

모델 소개

의사결정 나무는 데이터를 분석하여 이들 사이에 존재하는 패턴을 예측 가능한 규칙들의 조합으로 나타내며, 그 모양이 '나무'와 같다고 해서 의사결정나무라 불린다. 질문을 던져서 대상을 좁혀 나가는 스무고개 놀이와 비슷한 개념이다.

초기 지점은 root node라고 하고 leave node(=terminal node)의 데이터 개수를 합하면 root node의 데이터 수와 일피한다. 바꾸어 말하자면 terminal node간 교집합이 없다는 뜻이다. 또한 terminal node의 개수가 분리된 집합의 개수로서 위 그림에서는 8개의 부분집합으로 나누어진 셈이다.

 

의사결정나무는 분류(classification)와 회귀(regression) 모두 가능하다. 범주나 연속형 수치 모두 예측할 수 있으며 feature로서 범주형 또는 연속형 자료를 모두 가질 수 있다. 의사결정 나무의 분류 과정은 다음과 같다.

 

1. 여러가지 독립 변수 중 하나의 독립 변수를 선택하고 그 독립 변수에 대한 기준값(threshold)을 정한다.
2. 전체 학습 데이터 집합(부모 노드)을 해당 독립 변수의 값이 기준값보다 작은 데이터 그룹(자식 노드 1)과 해당 독립 변수의 값이 기준값보다 큰 데이터 그룹(자식 노드 2)으로 나눈다.
3. 각각의 자식 노드에 대해 1~2의 단계를 반복하여 하위의 자식 노드를 만든다. 단, 자식 노드에 한가지 클래스의 데이터만 존재한다면 더 이상 자식 노드를 나누지 않고 중지한다.

 

회귀의 경우 해당 terminal node의 종속변수(y)의 평균을 예측값으로 반환하게 되는데, 이 때 예측값의 종류는 terminal node 개수와 일치한다. 만약 terminal node 수가 3개 뿐이라면 새로운 데이터가 여러 주어진다 해도 3종류의 답만을 출력하게 될 것이다.

 

출처: https://tyami.github.io/machine%20learning/decision-tree-1-concept/

의사결정나무는 어떠한 attribute를 사용하느냐에 따라 여러가지 모델을 만들 수 있다. 그렇다면 여러 decision tree 중 더 좋은 모델은 무엇일까?

답은 "변별력이 좋은 질문부터 먼저 정한다" 이다.

 

불순도 / 불확실성 (impurity)

출처: https://tyami.github.io/machine%20learning/decision-tree-1-concept/

의사결정나무는 구분 후 각 영역의 순도(homogeneity)가 증가하고, 불순도(impurity) 혹은 불확실성(uncertainty)이 최대한 감소하도록 하는 방향으로 학습을 진행한다. 순도 증가/불순도 감소를 두고 정보이론에서는 정보획득(information gain)이라고 한다. 이 불순도를 어떤 지표를 사용하느냐에 따라 알고리즘의 방향이 갈리게 되는데, 크게는 아레와 같이 엔트로피(entropy)와 지니계수(gini index) 기반의 알고리즘으로 나눌 수 있다.

엔트로피(Entropy) 기반 알고리즘

• ID3
• C4.5
• C5.0

지니계수(Gini Index) 기반 알고리즘

• CART(Classification And RegressionTree)

 

 A 영역에 속한 모든 레코드가 동일한 범주에 속할 경우(=불확실성 최소=순도 최대) 엔트로피는 0이다. 반대로 범주가 둘뿐이고 해당 개체의 수가 동일하게 반반씩 섞여 있을 경우(=불확실성 최대=순도 최소) 엔트로피는 1의 값을 갖는다. 

 

엔트로피(Entropy)

출처: https://ratsgo.github.io/machine%20learning/2017/03/26/tree/

m개의 레코드가 속하는 A영역에 대한 엔트로피는 아래와 같은 식으로 정의된다.($p_k = $ A영역에 속하는 레코드 가운데 k범주에 속하는 레코드의 비율)

$$Entropy(A) = -\Sigma_{k=1}^m p_k log_2 (p_k)$$

오렌지색 박스로 둘러쌓인 A 영역의 엔트로피를 구해보자. 전체 16개(m=16) 가운데 빨간색 동그라미(범주=1)는 10개, 파란색(범주=2)은 6개이고, A 영역의 엔트로피는 다음과 같다.

$$Entropy(A) = -{10\over16} log_2({10\over16}) - {6\over16}log_2({6\over16}) \approx 0.95$$

 

여기서 A영역에 빨간 점선을 그어 두개의 부분집합(R1, R2)로 분할했을 때, 두개 이상의 엔트로피 공식은 가중평균을 통해 구할 수 있다.($R_i = $ 분할 전 레코드 가운데 분할 후 i 영역에 속하는 레코드 비율)

$$Entropy(A) = \Sigma_{i=1}^d R_i (-\Sigma_{k=1}^m p_k log_2 (p_k))$$

$$Entropy(A) = 0.5 \times (-{7\over8} log_2({7\over8}) - {1\over8}log_2 ({1\over8})) + 0.5 \times (-{3\over8} log_2({3\over8}) - {5\over8}log_2 ({5\over8})) \approx 0.75$$
그러면 분기 전과 분기 후 0.2 만큼 엔트로피가 감소(=불확실성 감소=순도증가=정보획득)하게 되어 분할 후가 낫다는 판단하에 의사결정 나무는 데이터를 두 개의 부분집합으로 나누게 된다. 

 

지니계수(Gini Index)

$$G.I(A) = \Sigma_{i=1}^d(R_i(1-\Sigma_{k=1}^m p_{ik}^2))$$

 

*엔트로피(Entropy) vs 지니계수(Gini Index)

출처:https://quantdare.com/decision-trees-gini-vs-entropy/

• Computationally, 엔트로피는 logarithms를 사용하기 때문에 더 복잡하고, 결과적으로 지니계수의 계산속도가 훨씬 빠르다. 
• 정확도는 엔트로피가 조금 더 나음
• 그러나, 결과가 매우 유사하기 때문에 엔트로피 계산에 투입되는 시간의 가치가 미미(?)하다.

 

모델 학습

의사결정 나무의 학습 과정 두 가지 과정으로 나뉜다.

1. 재귀적 분기(recursive partitioning) : 입력 변수 영역을 두 개로 구분
2. 가지치기(pruning) : 너무 자세하게 구분된 영역을 통합

 

재귀적 분기

한 변수를 기준으로 두고 가능한 모든 분기점에 대해 엔트로피/지니 계쑬르 구해 분기 전과 비교해 정보획득량을 조사한다. 

출처: https://sanghyu.tistory.com/8

여기서 가장 information gain이 큰 outlook을 가장 root노드로 둔다.

출처: https://sanghyu.tistory.com/8

그다음 이제 분류된 데이터들의 entropy를 구하고 overcast의 경우 entropy가 0이므로 stop! 나머지 sunny와 rain은 또 그다음 노드의 attribute를 어떤 것으로 정할 지 information gain을 구해본다. 그래서 sunny같은 경우 위의 그림에서 볼 수 있듯이 가장 information gain이 큰 hummidity로 다음 노드의 attribute를 정한다.

이 방식을 쭉해서 처음에 봤던 이 decision tree를 완성할 수 있다. key idea of tree learning은 가장 큰 information gain을 가지는 attribute를 가장 root에 가깝게 하는 것이다.

 

그렇다면 1회 분기를 위해 계산해야 하는 경우의 수는 총 몇 번일까? 개체가 $n$개, 변수가 $d$개라고 할 때 경우의 수는 $d(n−1)$개가 됩니다. 분기를 하지 않는 경우를 제외하고 모든 개체와 변수를 고려해 보는 것이다.

 

가지치기 : overfitting 방지

decision tree의 분기수가 증가할 때, 처음에는 새로운 데이터에 대한 오분류율이 감소하나 일정수준 이상이 되면 오분류율이 되레 증가하는 현상이 발생한다. 이를 과적합(overfitting)되었다고 표현한다.(generalize 능력이 떨어짐) 이를 방지하기 위해 가지치기를 진행하게 되는데 가지치기는 두 가지 방법이 존재한다.

1. 사전 가지치기: 트리의 최대 depth, 각 노드에 있어야 할 최소 관측값 수 등을 미리 지정하여 트리를 만드는 도중에 stop하는 것
2. 사후 가지치기: 모든 terminal node의 순도가 100%인 상태를 Full tree라고 할 때. Full tree를 생성한 뒤 적절한 수준에서 terminal node를 결합하는 것

 

가지치기는 데이터를 버리는 개념이 아닌 분기를 합치는(merge) 개념으로 이해해야 한다.사후 가지치기진행했을 때 오른쪽 같을 결과가 나오는 것을 확인할 수 있다.

출처: https://ratsgo.github.io/machine%20learning/2017/03/26/tree/

 

비용함수(cost function)

의사결정나무는 이 비용함수를 최소로 하는 분기를 찾아내도록 학습된다.

• $$CC(T) = Err(T) + \alpha \times L(T)$$
• $CC(T)$=의사결정나무의 비용 복잡도(=오류가 적으면서 terminal node 수가 적은 단순한 모델일 수록 작은 값)
• $ERR(T)$=검증데이터에 대한 오분류율
• $L(T)$=terminal node의 수(구조의 복잡도)
• $\alpha$=$ERR(T)$와 $L(T)$를 결합하는 가중치(사용자에 의해 부여됨, 보통 0.01~0.1의 값을 씀)

 

 

의사결정나무는 계산복잡성 대비 높은 예측 성능을 내고, 변수 단위로 설명력을 지닌다는 강점을 가지고 있다. 다만 의사결정나무는 결정경계(decision boundary)가 데이터 축에 수직이어서 특정 데이터에만 잘 작동할 가능성이 높다.

 

이같은 문제를 극복하기 위해 등장한 기법이 앙상블이다. (e.g. random forest)

 

Reference

• https://ratsgo.github.io/machine%20learning/2017/03/26/tree/
• https://tyami.github.io/machine%20learning/decision-tree-1-concept/
• https://datascienceschool.net/03%20machine%20learning/12.01%20%EC%9D%98%EC%82%AC%EA%B2%B0%EC%A0%95%EB%82%98%EB%AC%B4.html#id2
• https://sanghyu.tistory.com/8
• https://quantdare.com/decision-trees-gini-vs-entropy/
• https://zephyrus1111.tistory.com/124