뽀또12

인공지능을 공부하는 사람들하고 많은 지식을 공유하고, 제가 아는 것을 많이 알려드리고 싶습니다.

정말 하고 싶은게 너무 많아요. 모두들 항상 즐겁고 행복하게 열심히 삽시다! 오늘도 파이팅입니다!

업데이트:

카테고리: , ,

의사결정 트리를 사이킷런을 이용해서 라이브러리로만 배웠지, 수학적 개념이나 방식에 대해선 알지 못했다. 그런데 책에 원리에 대해서 자세히 설명되어있어서 너무 좋았다. 한번 원리에 대해 알아보도록 하자.

의사 결정 트리 분류기

사람들이 길가다가 처음 보는 동물을 만났다. 이 동물이 포유류인지 비포유류인지 구별하는 방법은 종의 특성에 관해서 질문을 하는 것이다. 예를 들면, 냉혈 동물인지 온혈 동물인지? 아니면 새끼를 낳는지, 알을 낳는지? 등과 같이 말이다. 이런 질문들을 계속 만들어 내고 깊이 파고듦으로써 우리는 해당 종의 클래스를 구별하게 된다. 의사 결정 트리는 이처럼 질문의 질문을 잇는 계층적 구조이다.

의결트
그림 1. 의사 결정 트리의 예시

의사결정 트리에서 각 리프 노드에는 하나의 클래스 레이블이 붙는다. 다른 노드들에는 단일 feature의 조건이 들어간다. 예를 들면, 냉혈 동물인가? 온혈 동물인가? 에 대한 답으로 YES,No의 자식 노드들을 갖는다.


3.1 기본적인 의사결정 트리 구축 알고리즘

위에서 아래로 내려오면서 어떤 조건을 선택해서 최적의 의사결정을 내릴지 고민하며 greedy 전략으로 알고리즘을 작성하게 된다.

헌트 알고리즘

헌트 알고리즘에서 의사결정 트리는 재귀적 방식으로 성장한다. 노드가 아래로 확장될 때, 조건에 따라 클래스 레이블들이 나뉘게 된다. 자식 노드들이 각각 단일의 클래스 레이블을 갖지 않고 2개 이상의 레이블들이 섞여있는 경우, 단일 클래스 레이블을 가질 때까지 계속해서 노드가 확장된다.

표 3.3
표 3.3

표 3.3의 데이터를 이용해서 헌트 알고리즘으로 어떤 식으로 진행되는지 그림 3.6을 보자.

그림 3.6
그림 3.6
  • (a): 클래스 레이블의 비율이 No와 Yes가 7:3 이므로 Defaulted = No 라고 설정한다. 이 트리의 training error는 30%이다.
  • (b): 데이터들을 나누기 위해서 Home Owner이라는 feature 항목을 골랐다고 하자. 왼쪽 자식은 Home Owner = Yes이고, 오른쪽은 Home Owner = No이다.
  • (c): Home Owner의 왼쪽 자식 노드는 이미 Defaulted = No로 단일 클래스 레이블이 되었으니 노드 확장을 종료한다. 오른쪽 자식은 아직 분리되지 않았으니, Marital Status를 이용해서 분할한다.
  • (d): 계속해서 자식 노드들이 단일 클래스를 가질 때까지 feature 항목들을 골라 노드를 확장하는 모습이다.

헌트 알고리즘은 다음의 문제들이 있다.

  1. 헌트 알고리즘에 의해 생성된 일부 자식 노드들이 비어있는 노드일 경우가 있다.
  2. 데이터 객체들의 feature가 모두 같은 것들이 다른 클래스를 가질 경우, 더 이상 분할할 수 없다.

의사결정 트리 귀납의 설계관련 문제들

그럼 의사결정 트리를 만들면서 조건으로 어떤 것들을 사용해야하는지 의문이 생긴다. 컴퓨터는 자동으로 시스템되는게 아니기 때문이다. 이제 앞으로 두가지의 궁금증을 해결한다.

  1. 분할 기준이 무엇인가?

    어떤 feature 조건을 선택해서 무슨 기준으로 클래스 레이블들을 2가지로 나눌 수 있을까?
  2. 정지 기준(stopping criterion)은 무엇인가?

    리프 노드에 있는 모든 데이터 객체들이 같은 클래스를 가지면 트리 확장이 종료되지만, 헌트 알고리즘의 문제점 2처럼 feature 조건에 따라 나뉘어서 다 비슷한 feature들을 갖지만 클래스가 분류가 안될 수 있다. 이럴 때, 조기 종료(early termination) 조건을 걸어 놓아서 트리 확장을 더 일찍 끝낼 수 있게 제어한다.


3.2. feature 조건에 대해

데이터들은 다양한 feature들을 가진다.

  • binary feature

    그림 3.7
    그림 3.7

    그림 3.7처럼 2개의 feature 값들을 갖는 것을 얘기한다.

  • 명목형/서열형 특징들(Nominal/Ordinal Attribute)

    그림 3.8
    그림 3.8
    그림 3.9
    그림 3.9

    그림 3.8처럼 여러개의 feature 값들을 갖는 것을 얘기한다. 여러개의 feature들은 그림 3.8의 (a)처럼 여러개로 분할 하거나 그림 3.8의 (b)처럼 feature들을 묶어서 binary화 할 수 있다. 서열형 특징들도 마찬가지이지만, 순서를 고려해야한다. 예를 들면, 그림 3.9의 (a),(b)처럼 순서대로 묶이는건 상관 없지만, (c)처럼 순서없이 분류되면 안된다.

  • 연속형 특징들(Continuous Attribute)

    그림 3.10
    그림 3.10

    그림 3.10은 연속적인 값을 갖는 feature를 분할하는 모습이다. (a)처럼 조건을 범위로 설정해서 이진 분할할 수도 있고, 훈련 집합 안의 모든 데이터를 커버할 수 있는 범위로 다중 분할하면 (b)처럼 된다. 사실, 연속 feature는 데이터 전처리 과정에서 이산화(dicretization)을 해놓고 오는 경우가 있어서 서열형 특징들의 분할 방법처럼 봐도 된다.


3.3. feature 조건을 선택하는 방법

그럼 어떤 feature 조건을 사용해야 클래스들을 빠르게 깨끗한(pure) 노드들로 분할해줄 수 있을까? 깨끗한 노드란, 자식 노드들이 대부분 같은 클래스로 분류됨을 의미한다. 깨끗한 노드로 분류되어야 트리가 빨리 확장을 종료되어 깊이가 증가하지 않는다. 트리의 크기가 크고 깊어지면 overfitting이 일어나 모델의 성능을 떨어뜨리기 때문에, 최상의 feature 조건들을 선택하는 방법에 대해 알아보자.

단일 노드에 대한 불순도(impurity) 척도

노드의 불순도는 해당 노드가 단일 클래스로 얼마나 잘 분류를 하는지 보는 척도라고 보면 될 것 같다. 불순도 평가를 위해 다음의 3가지 방법들이 사용된다.

  • Entropy : $-\sum_{i=0}^{c-1}p_i(t)\log_2 p_i(t)$
  • Gini index : $1-\sum_{i=0}^{c-1} {p_i(t)}^2$
  • Classification error : $1-\max_i[p_i(t)]$

엔트로피는 무질서도를 나타내는데, 가장 클 때는 모든 데이터 객체들이 분류가 제대로 되지 않았을 때이다. 나머지도 전부 비슷한 경향을 보이는데, 그림 3.11을 보면 알 수 있다.

그림 3.11
그림 3.11

클래스의 분포들이 균일할 때, 세가지의 척도 모두 가장 큰 값을 나타내고, 객체들의 클래스들이 잘 분류되어 단일 클래스에 속할 때, 가장 작다.

불순도

위 그림을 보면 분류가 잘 되었을 때, 불순도 값들이 작음을 알 수 있다. 즉, 이제 조건을 설정하기 위해선 불순도가 낮은 것을 선택해야 될거라는 암묵적 이해가 되기 시작할 것이다.

자식 노드들의 불순도 합

N개의 데이터 객체를 갖는 노드에서 조건에 따라 k개의 자식 노드들 ${ v_1,v_2,…,v_k }$로 분할한다고 해보자. 그리고 불순도의 값이 $I(v_j)$인 자식 노드 $v_j$와 연관된 데이터 객체의 개수를 $N(v_j)$라고 하자. 불순도의 값들은 개수에 따른 스케일링이 되어 있지 않기 때문에, weight를 $N(v_j)/N$으로 설정하자. 그러면 자식 노드들의 불순도의 합, 즉 자식 노드들의 무질서도가 얼만큼 되는지 부모 노드의 입장에서 파악하는 식은 다음과 같다.

\[I(parent_{after}) = \sum_{j=1}^K \frac{N(v_j)}{N}I(v_j)\]

자식 노드들이 불순할수록 분할된 부모 노드도 불순하다는 뜻이 된다.

최선의 조건 찾기

그럼 자식 노드를 분할하기 위한 최선의 조건은 무엇일까? 다음의 식을 먼저 보자.

\[Gain\;\Delta = I(parent_{before})-I(parent_{after})\]

분할 이전의 부모 노드의 엔트로피와 분할 후의 부모 노드의 자식노드들의 가중치 합을 빼서 Gain $\Delta$을 측정한다. Gain이 크면 클수록 $I(parent_{after})$가 작다는 것을 의미하기 때문에, 분할된 노드들이 pure하다는 것을 의미하게 되므로, 우리는 Gain이 큰 조건을 찾아야 한다. 여기서 엔트로피가 불순도의 지표로 사용된다면, Gain을 information gain $\Delta_{info}$라고 부른다.

이득 비율(Gain Ratio)

그러나 사실 단순하게 gain이 높다고 해서 무조건적으로 좋은 조건이라고 할 수 없다. 예를 들면, 10명의 고객의 ID feature를 1,2,3,…,10 이라고 하면, $I(parent_{after})$가 0이 되는 아주 좋은 결과를 얻게 되지만 이 feature는 절대로 학습에 사용해선 안되는 데이터이다. 따라서 우리는 분할되는 자식의 수 역시 조건을 선택할 때 고려해야한다.

문제를 극복하는 방법은 2가지가 있다.

  1. 조건을 이진 분할로만 제한함.
  2. 조건에 의해 분할된 수를 고려해서 분할 기준을 수정하는 것

2번의 경우, 아래 식으로 표현되는 이득 비율(gain ratio)를 척도로 사용해 자식 노드가 많은 feature를 보상해준다.

\[\text{Gain ratio} = \frac{\Delta_{info}}{\text{Split info}} = \frac{I(parent_{before})-I(parent_{after})}{-\sum_{i=1}^k \frac{N(v_i)}{N}\log_2\frac{N(v_i)}{N}}\]
  • $N(v_i)$ : 자식 노드 $v_i$에 할당된 객체의 수
  • $k$ : 자식 노드의 수

위 식은 gain을 측정하고 분할이 동일한 크기의 자식 노드들을 더 많이 생성하는지 여부를 평가한다. 즉, 자식 노드들에 각각 같은 수의 데이터 객체가 할당되면, 위 식의 분모에 있는 entropy가 극대화되서 gain ratio가 감소하게 된다.

이렇게 gain ratio를 계산해서 우리는 최선의 조건을 gain ratio가 큰 조건으로 설정하면 되는 것이다.


3.4 의사결정 트리 분류기의 특성

  1. 적용성

    의사결정 트리는 분류 모델을 구축하기 위한 무매개변수 방법(non-parametric approach)이다. 데이터의 클래스와 feature들을 결정하는 확률 분포에 관한 어떤 전제도 필요하지 않아서, 광범위하고 다양한 데이터 집합에 적용 가능하다.

  2. 표현력

    의사결정 트리는 이산값 feature들의 어떤 함수도 코드화 할 수 있다.

  3. 계산의 효율성

    많은 의사결정 트리 알고리즘들은 방대한 가설 공간(hypothesis space)에서의 탐색에 heuristic기반의 접근 방법을 이용한다. 이런 방식은 훈련 집합의 크기가 매우 방대해도 빨리 모델을 구축할 수 있고, 트리가 만들어지면 test 데이터를 분류하는 것은 극히 빨라서 트리의 최대 깊이가 $w$라고 해도 최악의 경우 복잡도가 $O(w)$이다.

  4. 결측값(missing value) 다루기

    테스트 데이터의 feature에 결측 값이 있으면, 다음의 3가지 방식으로 문제를 해결한다.
    • 확률 분할법(probabilistic split method) : 결측 feature가 특정 값을 가질 확률에 따라 분할 노드의 모든 자식에게 데이터 객체를 분배하는 방법
    • 대리 분할법(surrogate split method) : 결측 feature에 의한 분할과 가장 유사한 비결측 대리 feature를 기준으로 자식노드들 중 하나에 분배하는 방법
    • 분리 클래스 방법(separate class methdo) : 결측값 자체를 새로운 노드로 할당하는 방법

  5. 속성들 간의 상호작용 다루기

    feature들이 개별적으로는 클래스를 구분하는데 도움이 못되지만 같이 사용되면 클래스를 구분할 수 있는 경우 서로 intercation하다고 간주한다. 예를 들어 3차원 데이터에서 X,Y,Z 각각의 feature들만을 봤을 땐 구분이 안되지만 X,Y가 같이 사용되면 데이터가 구분이 된다고 하자. 그러나 X,Z나 Y,Z처럼 Z가 같이 있는 경우엔 구분이 안된다고 하면, Z는 무의미한 속성이 된다. 이런 경우 의사결정 트리의 greedy한 성질 때문에 성능이 떨어질 수 있다.

  6. 무의미한 속성 다루기

    분류 작업을 위해 feature가 유용하지 않다면 무의미한 feature이다. 이것은 트리의 성능에 영향을 미칠 수 있기 때문에 전처리 과정에서 제거하자.

  7. 중복 속성 다루기

    어떤 feature가 다른 feature와 강하게 상호작용할 경우, 이것은 중복(redundant)라고 한다.

  8. 직선 분할 사용

    그림 3.20
    서로 다른 클래스인 두 개의 인접 구역 사이의 접경을 decision boundary라고 부르고 위 그림처럼 좌표축과 평행한 직선으로 표현된다.

  9. 불순 척도의 선택

    앞서 gain을 얻기 위해 3가지의 불순도를 측정하는 방법을 얘기했는데, 무엇을 선택하든 트리의 성능에 영향을 주지 않는다.

6 분 소요

참고