Decision Tree란? 개념, 작동 원리, 예제, 장단점

1. Decision Tree의 개념과 예시

Decision Tree(의사 결정 나무)는 데이터를 특정 조건에 따라 여러 단계로 분류하거나 특정 결과 값을 예측하는 머신러닝 알고리즘의 일종입니다. 말 그대로 나무(Tree) 형태의 구조를 가지고 있기 때문에 Decision Tree라고 불립니다.

예시를 통해 쉽게 알아보겠습니다.

이 Decision Tree는 직장인 여부를 예측하는 데 사용됩니다. 먼저, 스마트폰을 소유한 사람(스마트폰 소유 여부 - 예)이라면 나이를 확인합니다. 나이가 30세 미만(<30)이면 비직장인으로 예측합니다. 왜냐하면 스마트폰을 소유한 30세 미만 170명 중 150명이 비직장인이고 20명만 직장인이기 때문입니다. 반면, 스마트폰을 소유하지 않은 사람(스마트폰 소유 여부 - 아니오) 중에서 독립적으로 사는 사람(주거 형태 - 독립)은 직장인으로 예측합니다. 스마트폰을 소유하지 않고 독립적으로 사는 50명 중 40명이 직장인이고 10명만 비직장인이기 때문입니다.

각 분기(branch)는 특정 조건을 나타내며(예, 아니오 같은 조건), 각 노드(node)는 데이터가 특정 조건에 따라 나누어지는 지점(네모 박스)을 의미합니다.

Decision Tree의 핵심 아이디어

Decision Tree의 핵심 아이디어는 데이터를 순수한 상태로 분류하는 것(또는 말단 노드의 entropy 최소화)입니다. '순수한 상태'란, 하나의 노드 안에 여러 범주가 섞이지 않고 최대한 한 가지 범주만 들어있는 상태를 의미합니다.

이를 좀 더 구체적으로 이해하기 위해 위의 사례를 살펴봅시다.

처음에는 데이터가 뒤섞여 있어 entropy(불순도)가 매우 높은 상태입니다. 즉, 직장인과 비직장인이 함께 섞여 있습니다.

• 첫 번째 분할: 스마트폰 소유 여부라는 기준을 통해 데이터를 나누면 entropy가 줄어듭니다. 하지만 여전히 하위 노드에서는 데이터가 완벽하게 분류되지 않고 혼합된 상태가 존재합니다.

• 두 번째 분할: 이 혼합된 데이터를 다시 명확히 분류하기 위해 추가로 나이와 주거 형태라는 기준을 적용하여 데이터를 나눕니다. 이를 통해 각 하위 노드의 데이터는 더욱 순수한 상태, 즉 특정 범주에 가깝게 됩니다.

이런 방식으로, Decision Tree는 각 말단 노드(Terminal Node)의 entropy가 최소화되거나 완벽히 순수해질 때까지 분할을 반복하며 데이터를 최대한 명확하게 분류하는 방향으로 진행됩니다.

2. Decision Tree의 구성 요소

Decision Tree에서 맨 처음 분기하는 곳(스마트폰 소유 여부)을 루트 노드, 중간에서 분기하는 곳(나이, 주거 형태)을 중간 노드, 마지막 결과(직장인/비직장인)를 말단 노드라고 부릅니다.

구성 요소	설명
Root Node (루트 노드)	첫 번째로 분기가 시작되는 최상위 노드입니다.
Intermediate Node (중간 노드)	중간에서 데이터를 추가로 나누는 노드입니다.
Terminal Node (단말 노드)	최종적으로 데이터가 분류되어 결과를 보여주는 끝단 노드입니다.

3. Decision Tree의 작동 원리

Decision Tree는 데이터를 나눌 때 impurity(불순도)를 최소화하는 방향으로 작동합니다. 즉, 특정 기준으로 데이터를 나누었을 때 각 부분집합(subset)이 최대한 순수(pure)하도록 만드는 것이 목표입니다.

3-1. Impurity란?

Impurity(불순도)는 특정 노드에 있는 데이터가 얼마나 혼합되어 있는지를 나타냅니다. 혼합도가 낮을수록 노드가 순수하며, 혼합도가 높을수록 불순도가 높습니다. Decision Tree에서 많이 사용하는 Impurity 척도로는 Entropy와 Gini index가 있는데, 이 포스트에서는 Entropy에 초점을 맞추어 설명드리겠습니다.

3-2. Entropy (엔트로피)

Entropy는 데이터를 얼마나 잘 구분했는지를 측정하는 지표로, 다음과 같은 공식으로 정의됩니다.

\[ Entropy = -\sum_{i=1}^{n}{p_i \log_2 p_i} \]

여기서, \( p_i \)는 노드 내에서 특정 클래스가 차지하는 비율을 의미하며, n은 클래스의 개수입니다.

예시:

위의 이미지와 같은 노드를 예로 들어보겠습니다.

색깔	개수	비율
파랑	5	0.5
노랑	5	0.5

이 노드의 Entropy는 다음과 같이 계산됩니다.

\[ Entropy = -(0.5\log_2 0.5 + 0.5\log_2 0.5) = 1 \]

Entropy가 1로, 가장 높은 상태이며 데이터가 매우 혼합된 상태임을 나타냅니다.

3-3. Information Gain (정보 획득량)

Information Gain은 특정 조건으로 데이터를 나누었을 때 얻을 수 있는 Entropy의 감소량입니다. 다음과 같은 공식으로 정의됩니다.

\[ Information\ Gain = Entropy(분할 전) - \sum{\frac{노드의\ 데이터수}{전체\ 데이터수} \times Entropy(각 노드)} \]

즉, Information Gain이 클수록 해당 조건이 데이터를 명확하게 구분한 것입니다.

4. Decision Tree 만드는 방법

다음의 예제를 통해 Decision Tree를 단계적으로 만들어 보겠습니다.

예제 데이터

이름	운동 좋아함?	혼자 시간 보내는 것을 선호?	성격
A	예	아니오	외향적
B	아니오	예	내향적
C	예	아니오	외향적
D	아니오	예	내향적
E	예	예	외향적
F	아니오	아니오	외향적
G	예	아니오	외향적
H	아니오	예	내향적

• 총 데이터: 8개
• 외향적: 5개 (A, C, E, F, G)
• 내향적: 3개 (B, D, H)

---

Step 1: 초기 Entropy 계산

\[ Entropy(S) = -\left( \frac{5}{8} \log_2 \frac{5}{8} + \frac{3}{8} \log_2 \frac{3}{8} \right) \] \[ = -\left( 0.625 \cdot (-0.678) + 0.375 \cdot (-1.415) \right) \] \[ = -(-0.424 + -0.531) = 0.955 \] 초기 Entropy ≈ 0.955

---

Step 2: 각 변수에 따른 Entropy 및 Information Gain 계산

변수 1: "운동 좋아함?"

• "예" 그룹: A, C, E, G (총 4개)

  • 외향적: 4 (A, C, E, G)
  • 내향적: 0
  • Entropy 계산: \[ Entropy(\text{예}) = -\left( \frac{4}{4} \log_2 \frac{4}{4} + \frac{0}{4} \log_2 \frac{0}{4} \right) = 0 \]

• "아니오" 그룹: B, D, F, H (총 4개)

  • 외향적: 1 (F)
  • 내향적: 3 (B, D, H)
  • Entropy 계산: \[ Entropy(\text{아니오}) = -\left( \frac{1}{4} \log_2 \frac{1}{4} + \frac{3}{4} \log_2 \frac{3}{4} \right) \] \[ = -\left( 0.25 \cdot (-2) + 0.75 \cdot (-0.415) \right) = -(-0.5 - 0.311) = 0.811 \]

• 가중 평균 Entropy: \[ Entropy(\text{운동 좋아함?}) = \frac{4}{8} \cdot 0 + \frac{4}{8} \cdot 0.811 = 0 + 0.4055 = 0.4055 \]

• Information Gain: \[ Gain(\text{운동 좋아함?}) = 0.955 - 0.4055 = 0.5495 \]

변수 2: "혼자 시간 보내는 것을 선호?"

• "예" 그룹: B, D, E, H (총 4개)

  • 외향적: 1 (E)
  • 내향적: 3 (B, D, H)
  • Entropy 계산: \[ Entropy(\text{예}) = -\left( \frac{1}{4} \log_2 \frac{1}{4} + \frac{3}{4} \log_2 \frac{3}{4} \right) = 0.811 \]

• "아니오" 그룹: A, C, F, G (총 4개)

  • 외향적: 4 (A, C, F, G)
  • 내향적: 0
  • Entropy 계산: \[ Entropy(\text{아니오}) = 0 \]

• 가중 평균 Entropy: \[ Entropy(\text{혼자 시간 선호?}) = \frac{4}{8} \cdot 0.811 + \frac{4}{8} \cdot 0 = 0.4055 \]

• Information Gain: \[ Gain(\text{혼자 시간 선호?}) = 0.955 - 0.4055 = 0.5495 \]

---

Step 3: Decision Tree 분할 조건 선택

• "운동 좋아함?": Information Gain = 0.5495
• "혼자 시간 보내는 것을 선호?": Information Gain = 0.5495

Information Gain이 동일하므로, 여기서는 "운동 좋아함?"을 첫 번째 분기 조건으로 선택하겠습니다 (임의 선택).

Decision Tree

---

Step 4: 추가 분할

• "예" → Entropy = 0 (추가 분할 불필요)
• "아니오" → Entropy = 0.811 (추가 분할 필요)

"아니오" 노드에서 "혼자 시간 선호?"로 분할:

• "예": B, D, H (총 3개)
  • 외향적: 0
  • 내향적: 3 (B, D, H)
  • Entropy = 0
• "아니오": F (총 1개)
  • 외향적: 1 (F)
  • 내향적: 0
  • Entropy = 0
• 가중 평균 Entropy: \[ Entropy = \frac{3}{4} \cdot 0 + \frac{1}{4} \cdot 0 = 0 \]
• Information Gain: \[ Gain = 0.811 - 0 = 0.811 \]

최종 Decision Tree

5. Decision Tree의 장단점

장점	단점
직관적이고 해석이 쉽습니다.	과적합(overfitting) 가능성이 높습니다.
데이터 전처리가 많이 필요하지 않습니다.	작은 변화에도 민감할 수 있습니다.
시각적으로 표현 가능합니다.	일부 조건에 편향될 수 있습니다.

Decision Tree는 이해하기 쉬운 머신러닝 알고리즘으로, 분류 및 예측 문제에 널리 활용됩니다. 그러나 성능을 높이기 위해서는 과적합 방지 등의 추가적인 주의가 필요합니다.