• 본 글은 서울대학교 산업공학과 DSBA 연구실 강필성 교수님의 "다변량데이터분석" 학부강의의 review이다.

---

1. Classification Tree

---

종속변수가 범주형(이진 또는 다중 클래스)일 때 사용하는 분류용 의사결정나무이다.

$\to$ 자료구조의 트리와 용어가 매우 유사하므로, 따로 설명하지는 않고 ppt 슬라이드 속 설명으로 대체한다.

1.1 Impurity

분류 트리를 구축할 때 각 노드(데이터 집합)의 불순도(impurity)를 측정하여, 이를 최소화하는 방향으로 노드를 분할(split)한다. 대표적인 불순도 척도로 지니 지수(Gini Index)와 디비언스(Deviance)가 있다.

1.1.1. 지니 지수(Gini Index)

• 정의
  $\text{Gini}(A) = 1 - \sum_{k=1}^K (p_k)^2$

  $\quad\text{(이진 분류 시 }0 \le \text{Gini} \le 0.5\text{)}$

  • $A$는 특정 노드(영역)
  • $K$는 가능한 클래스(범주) 수
  • $p_k$는 노드 $A$ 내에서 클래스 $k$가 차지하는 비율

• 특징

  • 노드 내 클래스 분포가 한쪽으로 치우칠수록(즉 대부분이 단일 클래스일수록) $\sum_{k=1}^K (p_k)^2$가 커지므로 지니 지수가 작아진다.
  • 지니 지수가 0이면 해당 노드에 단일 클래스만 존재(순도 100%), 0.5(이진 분류 기준)에 가까울수록 혼합도가 높아짐(불순도가 큼).

1.1.2. 디비언스(Deviance)

• 정의(엔트로피 기반)
  분류 트리 구현체(특히 통계 패키지 R 등)에서는 엔트로피(Entropy)를 사용한 디비언스(Deviance)를 측정하기도 한다.

  $\text{Deviance}(A) = -2 \sum_{k=1}^K p_k \log p_k$

  이때 $\log$는 보통 자연로그 $ln$를 사용하며, 범주 확률 $p_k$가 0이면 $0 \log 0 = 0$이라 가정한다(극한 처리).

• 특징

  • 디비언스가 낮을수록 순도가 높다(한두 개 클래스가 대부분을 차지).
  • $\log$를 쓰므로, 클래스 비율이 $\to 0$인 부분에 대한 페널티가 큰 편이라 지니 지수 대비 분류 경계가 조금 다르게 형성될 수 있다.

정리:

• 지니 지수와 디비언스 모두 Classification Tree 에서 널리 사용되며, 보통 결과가 크게 달라지지 않는 경우가 많다.
• 불순도(impurity)가 작아질수록 해당 노드의 순도가 높아지고, 모델은 “잘 분류된” 상태에 가까워진다.

1.2. Recursive Partitioning

분류 트리를 만드는 핵심 알고리즘은 재귀적 분할이다. 간단히 말해, 루트 노드(전체 데이터)에서 시작해 “불순도 감소(Information Gain)”가 가장 큰 방법으로 데이터를 분할하고, 그 자식 노드에서도 동일 과정을 반복해 나무가 확장된다.

아래는 지니 지수를 사용하는 경우를 예로 들어, 단계별로 상세히 살펴본다.

1.2.1. Process of Recursive Partitioning

1) 루트 노드 설정

1. 전체 학습 데이터 $N$개를 하나의 노드로 둔다(루트 노드)이다.
2. 루트 노드의 불순도(예: 지니 지수 $\text{Gini}(\text{Root})$) 를 계산한다.

2) 첫 번째 분할

1. 후보 분할 찾기

   • 각 독립변수(특징)에 대하여, 가능한 모든 분할 기준(예: 연속형 변수의 분할점, 범주형 변수의 부분집합 분할 등)을 탐색한다.
   • 이진 분할(Binary Split) 가정 시,
     • 연속형: 값이 정렬된 상태에서 연속된 두 관측값 사이 중간점을 후보로 한다.
     • 범주형: 각 범주를 왼·오른쪽(혹은 yes/no)로 나누는 모든 조합이 후보가 된다.

2. 정보획득량(Information Gain) 계산

   • 분할 전 불순도 $\text{Impurity}_{\text{before}}$ 와, 분할 후(두 자식 노드로 나뉜 뒤) 불순도 $\text{Impurity}_{\text{after}}$ 간 차이로 Information Gain을 구한다.

   • $\text{Information Gain} = \text{Impurity}_{\text{before}} - \sum_{j} \bigl(\frac{N_j}{N}\bigr) \times \text{Impurity}(\text{Child}_j)$

     여기서 $N_j$는 자식 노드 $j$에 속한 관측치 수이고, $N$은 부모 노드(분할 전) 관측치 수이다.

3. 분할 기준 선택

   • Information Gain이 가장 큰 분할을 선택하여 실제로 노드를 나눈다.
   • 이렇게 해서 첫 번째 분할이 만들어진다 (루트 노드 → 2개의 자식 노드).

3) 두 번째 분할

1. 각 자식 노드에 대해 다시 분할 가능성을 평가한다.

   • 이제 2개 자식 노드 각각을 새로운 “부모”로 간주하고, 위와 같은 후보 분할 절차(각 변수, 가능한 split 후보, 정보획득량 계산)를 반복한다.
   • 중요: “한 번 사용한 변수가 다시 사용되면 안 된다”는 제한은 없다고 한다. 즉, Information Gain이 충분히 크다면, 동일 변수가 연속된 분할(split)에 여러 번 사용될 수 있다.
     • 예) $X_1 \leq 10$으로 첫 분할 후, 자식 노드에서도 $X_1 \leq 5$라는 추가 분할을 할 수도 있다.

2. 가장 큰 정보획득량이 발생하는 노드와 해당 분할 기준을 적용한다.

   • 모든 노드(현재 리프 후보인 노드들)에 대해 분할 후보를 평가하고, 그중 Information Gain이 최고인 분할을 찾아 실행한다(한꺼번에 혹은 순차적으로 진행).
   • 자식 노드가 더 이상 분할로 인한 불순도 감소가 크지 않다면(Information Gain이 0에 가깝거나 작다면), 그 노드는 그대로 리프(terminal node)가 된다.

4) 반복(Recursion)

• 모든 자식 노드에서 위 과정을 재귀적으로 반복한다.
• “더 이상 유의미한 불순도 감소가 없음” 또는 “노드 크기가 너무 작음(사전 가지치기 기준)” 등 중지 조건에 도달하면, 해당 노드는 분할이 멈추고 리프 노드가 된다.

1.3. Pruning And Overfitting

1.3.1. Full Tree와 Overfitting

• 위 과정을 제한 없이 수행하면, 학습 데이터 상에서 분류 정확도 100%(또는 지니 지수=0에 가까움)를 달성하는 Full Tree가 만들어질 수 있다.
• 그러나 이는 노이즈까지 학습해, 새 데이터 예측력이 떨어지는 과적합을 야기한다.

1.3.2. Pruning

1. Pre-pruning

   • 일정 조건(예: 노드 최소 크기, 트리 최대 깊이 등)이 충족되면 더 이상 분할을 허용하지 않는 기법이다.
   • 분할이 멈추는 지점에서 트리를 완성하므로, 복잡도가 자동으로 제어된다.

2. Post-pruning

   • 먼저 Full Tree까지 자라게 한 뒤, 코스트 복잡도(Complexity Cost) 기반으로 분할을 되돌리는(리프 노드를 병합) 방법이다.
   • 대표적으로 코스트-컴플렉시티 가지치기

   $\text{CCP}: CC(T) = \text{Err}(T) + \alpha \times |\text{LeafNodes}|$

   • $CC(T)$: Tree의 Cost complexty를 뜻한다.
   • $\text{Error}(T)$: 검증셋(Validation set)에서의 분류 에러율이다.
   • $\alpha$: 리프 수가 많아지면 페널티가 증가한다.
   • $\alpha$를 조정해, 에러율과 모델 복잡도 사이 Trade-Off 를 찾는다.

1.4. Example and Data interpretation

1. 데이터 예시:
   • 변수: 소득, 교육수준, 가족 수, (Y=대출이용 여부) 등이다.
2. 결과 트리:
   • “소득 ≤ 92.5?”, “교육수준 ≤ 1.5?” 형태로 분기한다.
   • 각 리프 노드에서 Yes/No 비율이 높으면 그 범주로 분류한다.
   • 새로운 데이터가 들어오면, 해당 경로를 따라가 도달한 리프의 범주(또는 확률)로 분류한다.

해석 장점

• 규칙 기반(“왜 이 사람이 대출을 썼다고 분류되는가?”)을 간단한 if-then 형태로 설명할 수 있다.

2. Regression Tree

---

종속변수가 연속형일 때 사용하는 회귀용 의사결정나무이다. 회귀모형에서의 최종 예측값은 그 영역에 해당하는 객체들의 종속변수의 평균값이다! 아래에서 자세히 살펴보자.

2.1. 개념과 특징

1. 정의

   • 분류 트리와 동일한 “재귀적 분할” 아이디어를 적용하되, 노드의 불순도를 회귀(잔차) 기준으로 측정한다.
   • 예측값은 리프 노드에 속한 학습 데이터의 평균 혹은 중앙값 등을 사용한다.

2. Impurity 측정

   • 일반적으로 $\sum (y_i - \bar{y})^2$ (SSE) 등을 사용한다.
   • 분할 전후 SSE 감소 폭(Information Gain에 대응)이 가장 큰 스플릿을 선택한다.

2.2. 생성 과정

1. Root Node: 전체 데이터의 평균 $\bar{y}$을 예측값으로 초기 설정하고, SSE를 계산한다.
2. pre-partitioning: 각 변수의 분할점 후보마다 분할 후 두 자식 노드에서의 SSE 합을 구하고, 감소 폭 최대 지점을 선택한다.
3. Recursive Partitioning: 자식 노드들에 대해서도 동일 절차를 반복한다.
4. Pruning: 과적합 방지를 위해 사전/사후 가지치기(또는 매개변수로 최대 깊이 제한 등)를 적용한다.

2.3. 예시

• 중고차 가격 예측: “주행거리 ≤ 50,000” vs “> 50,000” 식으로 분할한다.
• 리프 노드 예: “(주행거리>70,000) AND (연식≥5년)”인 자동차들의 평균 중고가격을 예측값으로 사용한다.

3. Pros and Cons of decision tree

---

3.1. 의사결정나무의 장점

1. 사용과 이해가 용이함

   • 의사결정나무는 직관적인 규칙(Rule-based approach) 을 기반으로 하므로 쉽게 해석 가능하다.
   • 트리 구조는 사람이 이해하기 쉬우며, 전문적인 통계 지식 없이도 모델을 해석할 수 있다.

2. 간단한 규칙을 생성하여 해석 가능성 제공

   • 트리는 If-Then 형태의 규칙(Decision Rules) 을 자동으로 도출하며, 이를 통해 모델이 데이터를 학습하는 과정을 쉽게 추적할 수 있다.
   • 예를 들어, 대출 승인 모델에서 "고객의 신용 점수가 700 이상이면 승인"과 같은 명확한 의사결정 기준을 생성할 수 있다.

3. 자동 변수 선택 및 차원 축소 기능

   • 의사결정나무는 데이터에서 중요한 변수를 자동으로 선택하고, 덜 중요한 변수를 배제할 수 있다. 따라서 차원 축소(Dimensionality Reduction) 기능을 수행하며, 불필요한 변수로 인한 성능 저하를 방지한다.

4. 통계적 가정이 필요 없음

   • 선형 회귀나 로지스틱 회귀와 달리, 독립 변수와 종속 변수 간의 선형 관계를 가정하지 않는다. 따라서 비선형적인 관계를 포함하는 데이터에서도 적용 가능하다.

5. 결측치(Missing Data)에 강함

   • 일부 기법(Like CART)은 결측값이 있어도 모델이 동작할 수 있도록 설계되어 있다.
   • 결측치가 있는 경우, 특정 규칙을 설정하거나, 대체(split surrogate) 를 통해 예측 가능하다.

3.2. 의사결정나무의 단점

1. 데이터의 구조적 관계를 완전히 반영하지 못할 수 있음

   • 의사결정나무는 수직(Straight Cut) 또는 수평(Horizontal Cut) 방식으로 데이터를 분할하는 방식이므로, 특정한 데이터 패턴(예: 비선형적인 곡선 형태)을 제대로 학습하지 못할 수 있다.
   • 따라서 데이터가 복잡한 다차원적 관계를 갖는 경우, 단순한 분할 방식으로는 적절한 예측이 어려울 수 있고, 설령 가능하더라도 대각선 하나를 긋는 것보다 비효율적이게 되는 경우가 존재한다.

2. 변수 간 상호작용(Correlation) 반영 어려움

   • CART는 한 번에 하나의 변수만 고려하여 데이터를 분할하기 때문에, 변수 간 상관관계를 효과적으로 학습하지 못할 수 있다.
   • 예를 들어, 두 개의 변수가 서로 같이 작용할 때만 의미가 있는 경우, 이들간의 관계는 학습하기 어려울 수 있다.

3. 과적합(Overfitting) 가능성이 높음

   • 트리의 깊이가 깊어질수록 데이터를 지나치게 잘 맞추려는 경향이 발생할 수 있다. 특히 데이터가 많지 않거나 잡음(Noise)이 많을 경우, 작은 변화에도 민감하게 반응하여 일반화 성능이 저하될 수 있음.
   • 해결 방법:
     • Pruning 기법을 적용하여 불필요한 분할을 줄이고 트리의 크기를 제한.

4. 데이터 균형 문제에 취약함

   • 데이터의 특정 클래스(예: 소수 클래스)가 매우 적을 경우,
     트리가 특정 클래스만 강조하여 학습할 가능성이 있음.
   • 불균형 데이터 처리 방법:
     • 가중치 부여(Class Weight 조정)
     • 언더샘플링(Under-sampling) 및 오버샘플링(Over-sampling) 기법 활용

4. Reference

---

[1] Korea University - Multivariate Data Analysis 05

• https://www.youtube.com/watch?v=w6eCV1GzsLs&list=PLetSlH8YjIfWKLpMp-r6enJvnk6L93wz2&index=20

[2] 머신러닝 - 4. 결정트리(Decision Tree)

• https://bkshin.tistory.com/entry/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-4-%EA%B2%B0%EC%A0%95-%ED%8A%B8%EB%A6%ACDecision-Tree