의사 결정 트리

1. 정의

  - 대표적인 지도학습 모델

  - 주로 불연속 데이터를 다움

2. 장점

  - 강건한 모델이다 (중단되거나 에러가 나올 확률이 적다)

  - 알고리즘 이해가 쉽다

  - 수치형 자료, 범주형 자료 모두 적용 가능

3. 구조

  의사결정 트리의 알고리즘은 루트(Root)로 부터 시작하여, 줄기(Branch), 잎(Leaf)의 순서로 하향식 의사결정 구조를 띈다. 각 의사결정 노드(node)에서 인스턴스의 속성이 결정된다.

  예를 들어 오늘 저녁에 먹을 음식을 고른다고 하자. 첫번째 질문을 '양식인가?'로 시작하여 Yes/No로 구분한다. 다음 질문은 '채소인가 고기인가?'와 같이 연속적으로 의사결정 분기를 만들게 되면 최종적으로 잎에서는 내가 오늘 먹을 음식이 나오게 된다. 좋은 의시결정 트리는 노드 수를 최소화해야한다. 이파리로 가는 경로가 짧아야 신속하게 의사 결정을 할 수 있다.

4. 정보 함수

  정보 함수는 어떤 사건이 나한테 얼마만큼의 정보의 가치를 주는지를 확률적으로 결정하는 것이다. 발생 확률이 작은 사건일수록 정보 값이 크고 반대로 발생할 확률이 높을 수록 정보 값은 작다. 즉 진리에 대한 정보 값인 0이다.(발생확률 100%) 정보 함수의 기본 함수는 아래와 같이 표현된다.

  사건 x가 일어난 확률이 1에 가까우면 정보값은 0에 수렴한다. 반대로 일어날 확률이 0에 가까우면 정보의 가치는 무한대로 커진다.

5. 엔트로피

  정보 함수를 이용하여 엔트로피를 구할 수 있다. 엔트로피는 평균적으로 결과 값에 도달 하기 위해서 얼만큼의 질문이 필요한지를 의미한다. 

  예를 들어 루트에서 2개의 분기가 있고 2차 분기에 있는 각각의 노드에서도 2개의 분기가 있어서 잎에 도달하는 의사결정 트리가 존재한다고 가정해보자. 각 분기에서도 아래에 도달할 확률은 0.5이다. 그렇다면 각각의 잎에 도달할 확률은 모두 0.25이다. (0.5*0.5) 이 확률을 이용하여 엔트로피를 구하면 2가 나오고, 이 값은 결과값에 도달하기 위해서 평균적으로 2번의 질문을 거쳐야 함을 의미한다.

6. 정보 획득

  엔트로피를 이용하여 정보획득을 알 수 있다.

 

  여기서, S는 모든 사건의 집합을 의미하고, E(S)는 모든 사건에 대한 엔트로피이다. A는 속성이고, a는 속성값이다. |S|와 |S_a|는 각각 모든 사건의 경우의 수와 속성값 a를 갖는 경우의 수를 의미한다. 정보 획득 G값이 클수록 분류 해야 하는 경우가 많다는 것을 의미한다.

7. 의사결정 트리 예시

  의사 결정 트리를 만드는 과정을 설명하기 위해서 한가지 예를 들어서 설명하고자 한다. 조금 식상할지도 모르겠지만, 이번에도 야구를 소재로 사용하도록 하겠다. 8월 30일 경기까지 넥센의 타자 용병인 마이클 초이스는 총 6개의 홈런을 쳤다. 여러가지 경우의 수에 따라 그가 홈런을 칠 확률을 계산해보도록 하자.

  아래는 마이클 초이스의 8월 출장과 홈런 일지이다.

 

 

  마이클 초이스는 24번의 경기에서 총 6번의 홈런을 쳤다. 그가 8월 동안 상대한 팀들은 SK, 롯데, KIA, 두산, 한화, NC, 삼성으로 총 7개 팀이고, 경기마다 얻은 타수는 2,3,4,5번이다. 그리고 구장에 대한 효과도 알아보기 위해 홈과 원정으로 구분하였다. 상대한 팀, 타수, 홈/원정 여부에 따라 그가 홈런을 칠 확률을 알아보는 의사결정트리를 만들어보자.

  초이스가 홈런을 치는 것을 '목표 속성(Target Attribute)'이라고 하고, 그렇지 않은 속성들을 '후보 속성(Candidate Attribute)'으로 정한다. 우선 목표 속성에 대한 엔트로피를 계산한다.

 

  다음 각 후보 속성들의 엔트로피를 계산한다. 너무 많은 계산과정이 발생하므로, 초기 몇개에 대해서만 계산 과정을 설명하겠다.

 

  결과에 대해 조금 부연 설명을 하자면, 롯데의 엔트로피의 경우 총 7번이나 상대를 한 표본이 있고, 홈런도 3개나 때렸기 때문에 의사결정 트라에서 정보적 가치가 크다. 반면 초이스는 기아에서 단 한번도 홈런을 때려내지 못했다. 의사결정트리는 확정적 모델이므로, 기아전에서 한개의 홈런도 때려내지 못해 정보적 가치는 0으로 나오게 되는 것이다.

  위와 같은 방식으로 모든 후보 속성에 대한 엔트로피와 정보 획득의 결과는 아래와 같이 나올 것이다.

 

  여기서 정보 힉득 값이 가장 큰 상대구단이 루트노드가 된다. 그 다음 단계의 의사결정 노드는 다음과 같이 만들면 된다.

• 속성값마다 가지를 생성(각 가지에 속성값 하나씩 할당)
• 속성값별 엔트로피가 0이면 이파리 노드 생성
• 속성값별 엔트로피가 0이 아니면 현재 속성을 목표 속성으로 정하고 위의 과정을 반복

  완성된 의사결정 트리에서는 오버피팅 문제가 발생할 수 있다. 이를 해결하기 위해서 2가지 방법이 존재한다. 첫번째 방법은 의사결정 트리가 충분히 학승 데이터를 분류했다고 판단할 때 더는 노드를 생성하지 않는 방법이고, 두 번쨰는 의사결정 트리가 오버피팅을 감수하고 트리를 완성한 후 나중에 정확도를 떨어뜨리는 의사결정 노드를 없애는 가지치기 방법을 이용해 트리를 조정하는 방법이다.

- 에러감소 프루닝

  모든 노드를 대상으로 고려하여, 노드 아래 부분을 제거하거나, 이파리로 만들거나, 노드가 속해있는 상위의 유사한 의사결정 노드에 결합 시키는 방법이다. 노드를 제거한 후 항상 검증을 통해 제거 전,후의 정확도를 비교해야한다.

- 룰 포스트 프루닝

  모든 학습 데이터를 가지고 ID3 알고리즘을 기반을 의사결정 트리를 완성한다. 학습된 의사결정 트리를 룰 세트로 변환한다. 그리고 각 룰의 일련의 속성 중 정확도를 떨어뜨리는 것을 제거한다. 프루닝이 완려되면 정확도 순으로 정렬하고, 이 순서대로 판별식에 활용한다.