[머신러닝] Decison Tree

Decision Tree란?

의사결정나무(Decision Tree)란 지도 학습 알고리즘 중 하나의 알고리즘으로, 데이터를 분석하여 데이터에 존재하는 패턴을 찾아내 예측 가능한 규칙들의 조합으로 분류하는 알고리즘을 말한다.

특히 이 규칙들에 따라 데이터를 분할하는 모양이 나무와 같다 하여 의사결정'나무'라 부르며 이는 분류(Classification) 문제와 회귀(Regression) 문제 모두에서 사용 가능하다.

 

Decision Tree 예시(출처 : https://ratsgo.github.io/machine%20learning/2017/03/26/tree/)

 

위 문제는 Play(O)와 Don't Play(X) 두가지로 나뉘는 binary classification 문제로, 날씨(outlook)과 습도(humidity)와 바람이 부는 정도(windy)에 따라서 분류를 진행했다.

이와 같이 tree의 각 depth에 따라 각각의 분류 기준을 설정해 이에 따라 데이터를 분할하게 된다.

이 때 맨 처음 분류 기준을 Root node라 하고, 중간 분류 기준을 Intermediate node, 최종 분류된 노드를 Terminal node라 한다.

 

위에서 말한 것처럼 Decision Tree는 Classification과 Regression 문제 둘 다에서 사용된다고 설명했다.

Decision Tree의 작동 알고리즘을 요약하면 다음과 같다.

 

1. 데이터 분류 기준 선택 : 각 데이터는 분류 기준에 따라서 분할됨
   • Classification : 이 경우 보통 엔트로피(entropy) 혹은 지니 계수를 통해 분류 기준이 설정된다.
   • Regression : 이 경우 보통 최소제곱오차(Mean Squared Error)가 최소화되는 분류 기준이 설정된다.
2. 이 과정은 재귀적으로 진행되며 학습되고 데이터를 가장 잘 분류하는 규칙을 찾는다.
3. 데이터 분할 진행 : 더 이상 분할되지 않을 때까지(leaf node를 형성할 때까지) 분류가 진행되며 해당 리프 노드들에 class label을 할당한다.
4. 데이터 예측 : 분할된 리프 노드를 통해 예측을 진행한다
   • Classification : 이 경우 리프 노드에 분리된 데이터들 중 가장 많은 데이터를 예측값으로 반환한다.
   • Regression : 이 경우 리프 노드 값들의 평균값을 예측값으로 반환한다.

(좌) Regression의 경우 (우) Classification의 경우 예시

 

Decision Tree의 특징

• 장점
  • 이해하기 쉽고, 직관적이다 : 구조 자체가 직관적이고 시각적으로 표현이 가능해 알고리즘의 동작 방식 해석에 용이하다.
  • 스케일링, 정규화 불필요 : 데이터 스케일링과 정규화 과정이 필요하지 않아 전처리 과정이 간단하다.
  • 빠른 속도 : 이진 분할을 통해 각 예측 class들의 옵션 수를 줄이고 빠르게 예측이 가능하다.
  • Feature Importance 추정 가능 : 트리를 기반으로 각 변수의 중요도를 측정 가능하다. -> sklearn 패키지에서는 각 node의 불순도(impurity)를 나타내는 지니계수(추후 설명 예정)에 따라 변수의 중요도를 측정하며 즉, 더 순수한 결과를 분류해내는 노드의 중요도가 더 높아지는 구조이다.
• 단점
  •  Overfitting 위험 : 데이터의 작은 변화에도 크게 반응하며, 이는 overfitting에 대한 위험도를 높임. 특히 변수의 수가 많아질수록 overfitting의 위험도가 높아지고 이를 단일 tree를 통한 예측이 아닌 다수 tree들의 ensemble 방법인 random forest로 해결 가능
  • 데이터 불균형 : 클래스들 간 데이터 분포가 불균형하면 트리가 편향되어 예측 성능이 저하될 수 있다
  • Greedy함 : 트리는 각 분류 단계에서 최적의 분류를 진행하기 때문에 이는 전체 분류 관점에서 최적해라고 할 수 없을 수도 있음

 

그렇다면 이러한 분류 기준들은 어떻게 찾는 것일까?

 

 

데이터 분할 기준

위에서 설명했듯이, 데이터를 분할하는 기준은 Classification과 Regression에서 다르게 작용한다.

1. Classification

Classification에서 가장 중요한 컨셉은 leaf node에서 분류된 값들이 최대한 섞이지 않은 상태여야 한다는 것이다.

즉, 순도(homogenity)가 높고, 불순도(impurity)가 감소하는 방향으로 학습을 진행하고 데이터를 분류해야 한다.

 

이렇게 순도가 증가하고 불순도가 감소하는 것을 두고 정보이론에서는 '정보획득(information gain)'이라고 한다.

두 경우 중 어떤 경우로 분류해야 하는가?(출처 : https://alex-blog.tistory.com/entry/Machine-Learning-Decision-Tree-%EC%9D%98%EC%82%AC%EA%B2%B0%EC%A0%95%EB%82%98%EB%AC%B4)

위의 그림은 각각의 기준을 통해 분류하여 나온 leaf node의 상태를 나타낸 것이다. 둘 중 어떤 경우가 잘 분류된 상태라고 할 수 있을까?

 

어떤 것이 더 잘 분류된 것인지 각 지표를 활용해서 설명해보자.

 

• 엔트로피(Entropy)
  • 엔트로피란, 정보 이론에서 정보의 불확실성을 나타내는 지표로 사용된다. Decision Tree에서는 노드를 분할할 때 해당 분할이 얼마나 '순수하게' 클래스를 구분하는지를 측정하는 데에 활용되며 엔트로피가 낮을수록 노드가 순수하고 하나의 클래스로 이루어져 있을 가능성이 높다.
  • m개의 레코드가 속하는 A 영역에 대한 엔트로피는 다음과 같다.$$ Entropy(A) = -\sum_{k=1}^{m}p_{k}\log_{2}(p_{k})$$
  • 여기서 $p_{k}$는 데이터셋에 속한 클래스 k의 비율로, 0에 가까울수록 해당 클래스의 비율이 낮으므로 엔트로피는 높아지게 된다.
• 지니 계수(Gini impurity)
  • 지니 계수는 노드를 분할할 때 데이터의 불순도를 측정하는 지표다. 엔트로피와 유사한 목적을 가지지만, 계산 방식이 다르다.
  • 엔트로피가 더 많은 계산을 요구하는 반면, 지니 계수는 간단하게 계산할 수 있어서 속도 면에서 조금 더 효율적이다.
  • 지니 계수는 다음과 같이 계산된다.$$Gini(A) = 1 - \sum_{k=1}^{m}(p_{k})^{2}$$
  • 여기서 $p_{k}$는 데이터셋에 속한 클래스 k의 비율로, 0에 가까울수록 해당 클래스의 비율이 낮으므로 지니 계수는 낮아지게 된다.

 

여기서 중요한 것은 두 지표 모두 0에 가까울수록 노드의 순도가 높아지며, 이는 노드를 더 순수하게 잘 분류했다고 볼 수 있게 된다.

 

그럼 위에서 보여준 두 담배 그림 중 뭐가 더 잘 분류된 것인지 각각의 계산을 통해 알아보자.

 

1. 엔트로피(Entropy)
   • (나누기 전) 엔트로피는, $$- \frac{7}{15}\log_{2}(\frac{7}{15}) - \frac{8}{15}\log_{2}(\frac{8}{15}) \approx 0.99$$
   • (좌) 엔트로피는, $$\frac{7}{15}(-\frac{1}{7}\log_{2}(\frac{1}{7}) - \frac{6}{7}\log_{2}(\frac{6}{7})) -\frac{8}{15}(\frac{7}{8}\log_{2}(\frac{7}{8}) - \frac{1}{8}\log_{2}(\frac{1}{8})) \approx 0.57 $$
   • (우) 엔트로피튼, $$\frac{9}{15}(- \frac{5}{9}\log_{2}(\frac{5}{9}) - \frac{4}{9}\log_{2}(\frac{4}{9})) - \frac{6}{15}(- \frac{3}{6}\log_{2}(\frac{3}{6}) - \frac{3}{6}\log_{2}(\frac{3}{6})) \approx 0.99 $$
   • 따라서, 엔트로피가 더 낮아진 (좌) 경우가 순수도가 더 높아졌고, 이로 인해 분할이 더 잘 되었다고 볼 수 있다.
2. 지니 계수(Gini impurity)
   • (좌) 지니계수는, $$\frac{7}{15}(1-\frac{1}{7}^{2} -\frac{6}{7}^{2}) + \frac{8}{15}(1-\frac{1}{8}^{2} - \frac{7}{8}^{2}) \approx 0.23 $$
   • (우) 지니계수는, $$\frac{9}{15}(1-\frac{5}{9}^{2} -\frac{4}{9}^{2}) + \frac{6}{15}(1-\frac{3}{6}^{2} - \frac{3}{6}^{2}) \approx 0.49 $$
   • 따라서, 지니계수가 더 낮은 (좌) 경우가 순수도가 더 높아졌고, 이로 인해 분할이 더 잘 되었다고 볼 수 있다.

 

이러한 기준들을 통해 왼쪽 그림이 더 순수도가 높고, 불순도가 낮으며, 더 잘 분류된 기준이라고 볼 수 있다.

 

2. Regression

Regression의 경우 연속형 데이터이기 때문에 분할 기준이 약간 다른데, 보통의 regression 분할 기준은 평균제곱오차(MSE)로, 이를 최소화하는 방향으로 노드가 분할되게 된다.

 

여기서 간단하게 언제 회귀 트리가 필요한지부터 알아보자.

 

회귀 트리가 필요한 경우 (출처 : https://lucy-the-marketer.kr/ko/growth/regression-tree-and-model-tree-overview/)

 

다음과 같이 왼쪽 그림에선 하나의 회귀식으로 전체 데이터를 나타나고자 했을 때를 표현했다. 그러나 여기서 데이터 포인트와의 오차가 큼을 확인할 수 있다.

그러니 오른쪽 그림과 같이 데이터를 나눠서 각각의 나눠진 데이터에 대한 회귀식을 세우는 것이 효율적이다. 이렇듯 하나의 회귀식으로 전체 데이터 표현이 어려운 경우가 회귀 트리/모델 트리가 필요한 케이스다.

 

그렇다면 위에 잠깐 언급한 모델 트리는 무엇일까?

 

간단하게 설명하면 leaf node의 값이 특정 값(노드 값들의 평균)으로 떨어진다면 회귀 트리, 함수로 떨어진다면 모델 트리라고 볼 수 있다.

 

회귀 트리와 모델 트리(출처 : https://lucy-the-marketer.kr/ko/growth/regression-tree-and-model-tree-overview/)

 

회귀 트리와 모델 트리에 대해서 알아봤으니 이제 진짜 MSE로 어떻게 데이터가 분할이 되는지 예시를 통해 알아보자.

 

예시 데이터

만약 위의 데이터 중에서 집 크기를 기준으로 회귀 트리를 나눈다고 가정해보자

 

그렇다면, 두 leaf node는 다음과 같이 나뉠 것이다.

 

• Leaf Node 데이터
  • 집 크기(X1) > 1500인 데이터: (1800, 3, 10, 200,000), (2000, 4, 8, 250,000)
  • 집 크기(X1) <= 1500인 데이터: (1500, 2, 5, 150,000), (1200, 2, 2, 120,000)

 

여기서 각각의 MSE를 계산해보자

 

• 집 크기(X1) > 1500
  • 예측값(평균): (200,000 + 250,000) / 2 = 225,000
  • 실제 값: 200,000, 250,000
  • 각 데이터의 차이: (200,000 - 225,000) = -25,000, (250,000 - 225,000) = 25,000
  • 각 데이터 차이의 제곱: (-25,000)^2 = 625,000,000, (25,000)^2 = 625,000,000
  • MSE: (625,000,000 + 625,000,000) / 2 = 625,000,000

• 집 크기(X1) <= 1500
  • 예측값(평균): (150,000 + 120,000) / 2 = 135,000
  • 실제 값: 150,000, 120,000
  • 각 데이터의 차이: (135,000 - 150,000) = -15,000, (135,000 - 120,000) = 15,000
  • 각 데이터 차이의 제곱: (-15,000)^2 = 225,000,000, (15,000)^2 = 225,000,000
  • MSE: (225,000,000 + 225,000,000) / 2 = 225,000,000

 

위와 같이 집 크기(X1)을 분류 기준으로 삼았을 경우 MSE는 다음과 같이 나오게 되며 총 MSE는 850,000,000이 된다.

이렇게 다른 feature에 대해서도 다양한 분류 기준을 정해 MSE를 계산하고, leaf의 MSE가 가장 낮은 분류 기준을 선택하면 된다.

 

 

Reference

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

의사결정나무(Decision Tree) · ratsgo's blog

https://lucy-the-marketer.kr/ko/growth/regression-tree-and-model-tree-overview/

회귀트리와 모델트리(Regression Tree and Model Tree)

https://alex-blog.tistory.com/entry/Machine-Learning-Decision-Tree-%EC%9D%98%EC%82%AC%EA%B2%B0%EC%A0%95%EB%82%98%EB%AC%B4

[Machine Learning] Decision Tree - 의사결정나무

https://wooono.tistory.com/104

[ML] 의사결정트리(Decision Tree) 란?