5장 정형 데이터 마이닝

3절 의사결정나무

(1) 의사결정나무 (중요)

정의

• 의사결정나무(Decision tree)는 분류함수를 의사결정 규칙으로 이뤄진 나무 모양으로 그리는 방법
• 나무 구조는 연속적으로 발생하는 의사결정 문제를 시각화해 의사결정이 이뤄지는 시점과 성과를 한눈에 볼 수 있게 함
• 계산 결과가 의사결정나무에 직접 나타나게 돼 분석이 간편함
  
• 의사결정나무는 주어진 입력값에 대하여 출력값을 예측하는 모형
  • 분류나무와 회귀나무모형이 있음
  • 의사결정나무라는 이름은 그 결과를 나무형태의 그래프로 표현할 수 있다는 사실에 기인
• 최종모형의 예측력과 해석력이 중요
  • 기대 집단의 사람들이 가장 많은 반응을 보일 고객 유치 방안을 예측하고자 하는 경우에는 예측력에 치중
  • 신용평가에서는 심사 결과 부적격 판정이 나온 경우 고객에게 부적격 이유를 설명해야 하므로 해석력에 치중
• 의사결정나무 구조
  • 뿌리마디(root node) : 시작되는 마디로 전체 자료를 포함
  • 자식마디(child node) : 하나의 마디로부터 분리되어 나간 2개 이상의 마디들
  • 부모마디(parent node) : 주어진 마디의 상위 마디
  • 끝마디(terminal node) : 자식마디가 없는 마디
  • 중간마디(internal node) : 부모마디와 자식마디가 모두 있는 마디
  • 가치(branch) : 뿌리마디로부터 끝마디까지 연결된 마디들
  • 깊이(depth) : 뿌리마디부터 끝마디까지의 중간마디들의 수

활용

• 세분화(segmentation) : 데이터를 비슷한 특성을 갖는 몇 개의 그룹으로 분할해 그룹별 특성을 발견
• 분류(classification) : 관측 개체를 여러 예측변수들에 근거해 목표변수의 범주를 몇 개의 등급으로 분류하고자 하는 경우
• 예측(prediction) : 자료에서 규칙을 찾아내고 이를 이용해 미래의 사건을 예측하고자 하는 경우
• 차원 축소 및 변수 선택(data reduction and variable selection)
  : 매우 많은 수의 예측변수 중에서 목표변수에 큰 영향을 미치는 변수들을 골라내고자 하는 경우
• 교호작용 효과의 파악(interaction effeact identification)
  : 여러 개의 예측변수들이 결합해 목표변수에 어떻게 작용하는지를 파악하고자 하는 경우
• 범주의 병합 또는 연속형 변수의 이산화(binning)
  : 범주형 목표변수의 범주를 소수의 몇 개로 병합하거나 연속형 목표변수를 몇개의 등급으로 이산화하고자 하는 경우

장단점

• 결과를 누구에게나 설명하기 용이함
• 모형 분류 정확도가 좋음
• 모형을 만드는 방법이 계산적으로 복잡하지 않음
• 대용량 데이터에서도 빠르게 만들 수 있음
• 비정상 잡음 데이터에 대해서도 민감함이 없어 분류할 수 있음
• 한 변수와 상관성이 높은 다른 불필요한 변수가 있어도 크게 영향받지 않음
  -> 불필요한 변수가 많아지면 의사결정나무가 커지므로 가능한 불필요한 변수를 제거하고 작업하는 것이 좋음
  

분석 과정

• 의사결정나무의 형성 과정은 크게 성장(growing), 가지치기(pruning), 타당성 평가, 해석 및 예측으로 이루어짐
• 나무의 성장(growing), 가지치기(pruning) 내용 중요
  

나무의 성장

• 의사결정나무 분석 과정
  • 반복적 분할 : 훈련용 데이터를 이용하여 독립변수의 차원 공간을 반복적으로 분할
  • 가지치기 : 평가용 데이터를 이용하여 가지치기를 수행
• 분할 기준
  - 부모마디보다 자식마디의 순수도가 증가하도록 분류나무를 형성해 나감
  

1. 재귀적(반복적) 분할(recursive partitioning)

• 목적
  - 모든 공간을 직사각형으로 나누어서 각 직사각형이 가능한 한 '순수(pure)'하게 혹은 동질적(homogenous)이 되도록 하는 것
  - '순수'의 의미 : 최종 직사각형에 포함된 변수가 모둔 동일한 집단에 속하는 것
  

• 훈련 자료를 (x_i, y_i), i=1,...,n로 나타내자, 여기서 x_i = (x_i1, ...,x_ip)이다

  • x는 독립변수, y는 종속변수

• 나무 모형의 성장 과정은 x들로 이루어진 입력 공간을 재귀적(반복적)으로 분할(recursive partitioning)하는 과정
  (1)각 분할 단계에서는 보통 두 영역으로 분할하는데 이를 분할과정(split)이라 함

  $R_1(j, A) = \{ x_j \in A \}, \quad R_2(j, A^c) = \{ x_j \in A^c \}$

(2)다시 변수를 선택하여 같은 방식으로 나눔
(3)원하는 순수도에 도달할 때까지 반복 수행

2. 분할(분리) 규칙(splitting rule)

• 분리 변수(split variable)가 연속형인 경우 :

  $A = \{ x_j \leq s \}$

• 분리 변수가 범주형인 경우 :
  예)전체범주가 {1,2,3,4}일 때, A = {1,2,4}와 A^c = {3}로 나눔

• 최적 분할의 결정은 불순도 감소량을 가장 크게 하는 분할

  $\Delta i(t) = i(t) - p_L i(t_L) - p_R i(t_R), \quad i(t) = \sum_{i \in \tau} (y_i - \bar{y}_t)^2$

• 각 단계에서 최적 분리 기준에 의한 분할을 찾은 다음 각 분할에 대하여도 동일한 과정을 반복

3. 분리 기준(splitting criterion) (중요)

• 이산형 목표변수
  • 카이제곱 통계량 p값 : p값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성
  • 지니 지수 : 지니 지수를 감소시켜주는 예측변수와 그 때의 최적분리에 의해서 자식마디를 선택
  • 엔트로피 지수 : 엔트로피 지수가 가장 작은 예측 변수와 이 때의 최적분리에 의해 자식마디를 형성
• 연속형 목표변수
  • 분산분석에서 F 통계량 : P값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성
  • 분산의 감소량 : 분산의 감소량을 최대화하는 기준의 최적분리에 ㅢ해서 자식마디를 형성

4. 정지 기준(stopping criterion)

• 더 이상 분리가 일어나지 않고, 현재의 마디가 끝마디가 되도록 하는 규칙
  • 의사결정나무의 깊이(depth)를 지정
  • 끝마디의 레코드 수의 최소 개수 지정

5. 가지치기(pruning) 기준

• 테스트 데이터 활용 방법
  • 구축된 모형에 테스트 데이터 적용
  • 테스트 데이터를 통해 도출된 모형의 예측률 검토
  • 오분류율을 크게 할 위험이 높거나 부적절한 추론 규칙을 가지고 있는 가지를 제거
• 전문가에 의한 방법
  - 특정 분야의 전문가가 구축된 모형에서 제시되고 있는 규칙들의 타당도 검토
  - 타당성이 없는 규칙 제거
  

---

(2) 불순도의 측도

지니 지수

• 지니 지수를 감소시켜주는 예측변수와 그 때의 최적분리에 의해서 자식마디를 선택

• 자료 세트 T가 k개의 범주로 분할 되고 범주 비율이 p1,...,pk라고 한다면, 다음과 같이 표기됨

  $Gini(T) = 1 - \sum_{i=1}^{k}p_i^2$

• 불순도 : 여기에 나온 동물 중에서 같은 동물과 다른 동물이 많이 포함되어 있느냐
  

엔트로피 지수(Entropy measure)

• 열역학에서 쓰는 개념으로 무질서도에 대한 측도

• 엔트로피 지수가 가장 작은 예측변수와 이 때의 최적 분리에 의해 자식마디를 형성

• 자료 세트 T가 k개의 범주로 분할되고 범주 비율이 p1,...,pk라고 한다면, 다음과 같이 표기됨

  $Entropy(T) = - \sum_{i=1}^{k} p_i log_2 p_i$

• 예) 4개의 범주가 (0.25, 0.25, 0.25, 0.25) 비율로 구성(T0)

  $Entropy(T_0) = -(0.25 log_2 0.25) * 4 = 1.39$

• 예) 4개의 범주가 (0.5, 0.25, 0.25, 0) 비율로 구성(T1)

  $Entropy(T_1) = -(0.5 log_2 0.5 + 0.25 log_2 0.25 + 0.25 log_2 0.25) = 1.04$

• 엔트로피 지수는 엔트로피 지수 = 엔트로피(Left)P(Left) + 엔트로피(Right)P(Right)에서 엔트로피(Left) = -P(Left에서 Good)log2 P(Left에서 Good) -P(Left에서 Bad)log2 P(Left에서 Bad)
  

---

(3) 알고리즘 (중요)

CART(Classification and Regression Tree)

• 앞에서 설명한 방식의 가장 많이 활용되는 의사결정나무 알고리즘으로 불순도의 측도로 출력(목적)변수가 범주형일 경우 지니 기수를 이용, 연속형인 경우 분산을 이용한 이진분리(binary split)를 사용
• 개별 입력변수 뿐만 아니라 입력변수들의 선형결합들 중에서 최적의 분리를 찾을 수 있음

C4.5와 C5.0

• CART와는 다르게 각 마디에서 다지분리(multiple split)가 가능하며 범주형 입력변수에 대해서는 범주의 수만큼 분리가 일어남
• 불순도의 측도로는 엔트로피 지수를 사용

CHAID(Chi-sqared Automatic Interaction Detection)

• 가지치기를 하지 않고 적당한 크기에서 나무모형의 성장을 중지하며 입력변수가 반드시 범주형 변수
• 불순도의 측도로는 카이제곱 통계량을 사용

CART는 범주형, 연속형이 가능하고, C.45와 C5.0, CHAID는 범주형이 가능하다.
C시리즈는 다지분리가 가능하고, 엔트로피 지수를 통해 변수를 선택한다.
CHAID는 카이제곱 통계량을 통해 변수를 선택한다.