[머신러닝] 의사결정트리 (Decision Trees)

지도학습 알고리즘

• 지도학습 관련 알고리즘들로는 

  • 최근접 이웃 (Nearest Neighbor)

  • 나이브 베이즈 (Naive Bayes)

  • 의사결정 트리 (Decision Trees)

  • 분류 규칙 학습자 (Classification Rule Learners)

  • 선형 회귀 (Linear Regression)

  • 회귀 트리 (Regression Trees)

  • 모델 트리 (Model Trees)

  • 신경망 (Neural Networks)

  • 서포트 벡터 머신 (Support Vector Machines)

  • 등 ......

  • 오늘은 스무고개를 연상케하는 알고리즘이며 강건한 모델이라고 불리는 의사결정트리에 대해서 알아보겠습니다.

의사결정트리(Decision Trees) - 이론 

• 의사결정트리는 전형적인 분류 모델이며 매우 직관적인 방법 중 하나입니다. 다른 모델들과는 다르게 결과물이 시각적으로 읽히기 쉬운형태로 나타나는 것이 장점이기 때문에, 대출을 원하는 사람의 신용평가를 하고 싶을 때, 독버섯과 버섯을 분류하고 싶을 때 등 실질적으로 분류하는 경우에 자주 사용됩니다.

• 위의 그림은 의사결정트리의 아주 간단한 예제입니다. 두가지로 나뉘는 부분들을 분기라고 부르며 분기들 중 가장 위에 있는 분기를 루트 노드 라고 부릅니다. 또한 나뉘어 내려가는 선들 (yes, no) 을 결정 노드라고 부르며 맨 밑에 있는 노드를 잎 노드라고 부릅니다.

• 생활하면서도 사람들은 알게모르게 이 과정을 통해 결정을 내리는 일이 많아 매우 익숙하지만 과연 어떤 기준을 노드로 놓아야 하며 어떤 노드를 가장 위에 놓아야 하는지가 문제가 됩니다. 노드들을 가장 효율적으로 선정하고 배치하기 위해선 정보획득량이라는 개념과 엔트로피라는 개념이 필요합니다.

 이론 : 정보획득량과 엔트로피 

• 정보획득량 이라는 것은 어떤 사건이 얼마만큼의 정보를 줄 수 있는지를 수치화한 값입니다. 이를 계산하기 위해선 정보함수와 엔트로피라는 개념을 먼저 이해할 필요가 있습니다. 

• 정보 함수는 정보의 가치를 반환하는데 발생할 확률이 작은 사건일수록 정보의 가치가 크고 반대로 발생할 확률이 큰 사건일수록 정보의 가치가 작습니다. 정보 함수는 다음과 같이 표현합니다.

• 그래프에서 나타나는 것처럼 정보의 가치는 확률이 1에 가까울 수록 즉 무조건 일어날 일일 수록 0에 수렴하고, 확률이 0에 가까울 수록 즉 거의 일어나지 않을 일일 수록 무한대의 값으로 수렴합니다. 예를 들어보면 '아침엔 해가 뜬다.' 라는 사건의 경우에는 항상 일어나는 일이기 때문에 확률은 1에 가깝고 이를 통해 얻을 수 있는 정보는 거의 없다고 할 수 있습니다. 하지만 '아침에 해가 뜨지 않는다.' 라는 사건의 경우에는 확률이 0에 가까워 일어날 가능성이 매우 낮기 때문에 그런 사건의 정보의 가치는 매우 높다고 말할 수 있을 것입니다.

• 엔트로피란 무질서도를 정량화해서 표현한 값입니다. 어떤 집합의 엔트로피가 높을 수록 그 집단의 특징을 찾는 것이 어렵다는 것을 의미합니다. 따라서 의사결정트리의 잎 노드들의 엔트로피가 최소가 되는 방향으로 분류해 나가는 것이 최적의 방법으로 분류한 것이라고 할 수 있습니다. 엔트로피 함수는 다음과 같이 표현합니다.

• 그래프는 사건이 2개일 경우일 때의 엔트로피를 그린 그래프 입니다. 2개의 사건이 50:50 의 확률로 나타날 때 엔트로피, 즉 무질서도가 가장 높은 값을 가지는 것을 알 수 있습니다. 다시 말해 예측할 수 없다는 것을 의미합니다.

• 정보획득량은 전체 엔트로피에서 분류 후 엔트로피를 뺀 값을 의미 합니다. 분류전 무질서도가 1 이었는데 분류 후 엔트로피도 1이라면 정보획득은 전혀 이루어지지 않았다고 볼 수 있겠지요. 하지만 분류전 무질서도가 1 이었는데 분류 후에는 0으로 감소했다면 모든 값들을 분류할 수 있게 되었다는 것을 의미하며 정보획득량은 1이라고 볼 수 있을 것입니다. 정보획득량 함수는 다음과 같이 표현할 수 있습니다.

• G(S) 는 정보획득량 함수를 의미하고 S 는 모든 사건의 집합이며, Sa 는 다른 속성을 갖는 경우의 수들을 의미합니다. 간단한 예제를 통해 계산해서 알아보겠습니다.

• 전체 엔트로피는 1.558 정도로 계산됩니다. 의사결정트리에서 클래스가 2개일 경우에는 최대값이 1이지만, 3개 이상일 경우에는 엔트로피가 1을 넘을 수가 있습니다. 전체 구역을 반으로 나누었을 때 엔트로피는 어떻게 변화하는지 살펴보겠습니다. 만약 전체 엔트로피가 줄어든다면 분할을 잘해다고 볼 수 있겠지요. 최적의 분할은 아닐 수 있지만요.

• 분할 전 1.558 에서 분할 후 1.485 로 0.07 정도 감소한 것을 알 수 있습니다. 정보획득량이 0.07 인 것으로 보아 분할한 것이 더 낫다는 결과를 얻을 수 있었습니다.

• 의사결정트리를 효과적으로 배치하는데 있어서 가장 중요한 부분은 잎 노드들의 엔트로피 합계를 최소화하는 것입니다. 이를 위해선 정보획득량을 최대화 할 수 있는 순서대로 속성들을 배치하는 것이 중요합니다.

이론 : 재귀적 분귀 (Recursive Partitioning) 

• 의사결정트리는 정보획득량을 최대화 하는 순서로 속성을 배치하는 것이 가장 중요하다고 말씀드렸습니다. 그렇다면 최대화 하는 순서로 배치하는 것은 구체적으로 어떤방법을 사용해서 코딩을 해야할까요? 그리고 결정오류가 하나도 없어질때 까지 분류를 하는 것이 옳은 선택일까요? 아니라면 어느정도까지 분류하는 것을 성공적으로 분류했다고 말할 수 있을까요?

• 첫번째 질문, 어떤방법을 사용해서 코딩을 해야하는가에 대한 답이 재귀적 분귀 (Recursive Partitioning) 입니다. 재귀라는 말은 원래의 자리로 되돌아가거나 되돌아 오는 것을 의미합니다. 프로그래밍에서는 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법을 말합니다. 의사결정트리가 어떻게 재귀적으로 속성을 배치해 나가는지 살펴보겠습니다.

• 위의 표는 Car Evaluation 데이터 입니다. 관련데이터는 이곳에서 확인하실 수 있습니다. 평가를 목표속성으로 하며 구매가, 유지비, 문의 수, 탑승 가능인원, 안전이 후보속성인 데이터 입니다. 구매가 부터 안전까지 n = 5 개의 속성에 각각 정보획득량을 구해야 하며, 각 열에서 행별로 각각 정보획득량을 구해야 합니다. 위의 그림은 문의 수와 첫 번째 행까지를 기준으로 하고 있습니다. 이 상태의 정보획득량은 다음과 같습니다.

• 문의 수와 첫 번째 행까지를 기준으로 한 정보획득량을 구한 뒤에는 문의 수와 두 번째 행까지를 기준으로 한 정보획득량을 구합니다. 이후에는 세 번째 행까지를, 네 번째 행까지를... 이렇게 마지막 바로 전 행까지 계산 한 뒤에는 다른 열로 기준을 옮겨 같은 계산을 반복합니다. 이를 통해 가장 큰 정보획득량을 갖는 기준으로 첫 분류를 진행합니다. 첫 분류를 진행 한 뒤에는 분류된 대상을 같은 방법으로 또 분류해나갑니다. 이렇게 같은 방법을 다시, 또 다시 사용해나가면서 분류하는 과정을 재귀적 분귀 (Recursive Partitioning) 이라고 부릅니다. 

01234

• 이 분류는 모든 잎의 엔트로피가 0이 될 때 까지 반복합니다. 하지만 모든 잎의 엔트로피가 0이 될때까지 분류를 반복하면 기존 데이터에는 적합한 분류가 될 수 있지만 새로운 데이터는 제대로 분류하지 못하는 과적합 (Overfitting) 현상을 일으키기 때문에 일정 단계에서 중지 해주거나 분기를 재조정 해주어야 합니다. 

• 일정단계에서 중지해주는 첫번째 방법은 효율적인것 처럼 보이지만 그 단계가 정확히 언제인지 계산하는 것이 쉽지 않아 해결책이 되기 어렵습니다. 하지만 분기를 재조정하는 방식은 여러 기술을 통해 어느정도 의미있는 성과를 내고 있습니다. 분기를 재조정하는 방식이 가지치기 (Pruning) 입니다.

이론 : 가지치기 (Pruning) 

• 재귀적 분귀 (Recursive Partitioning) 을 통해 모든 노드를 분리한 경우의 모델은 일반화 되지 못하는 경우가 많습니다. 왜냐하면 기존 데이터의 이상치도 정상치 인것으로 분류하여 잘못된 모델이 구축되었을 가능성이 높기 때문입니다. 그래서 모든 노드를 분리한 뒤 분기를 적절히 합치는 과정을 거쳐 일반화 (generalization) 를 해줄 필요가 있습니다. 이를 가지 치기라고 부릅니다.

• 이 과정에서 또 한가지 질문이 생깁니다. 가지치기를 한다면 어느 정도까지 하는 것이 옳은가? 

• 가지치기의 정도를 결정하는 방법으로 에러감소 프루닝 (reduced error pruning) 과 룰 포스트 프루닝 (rule post pruning) 이 대표적입니다. 

• 에러감소 프루닝 (reduced error pruning) 은 이름에서 나타나는 것처럼 모든 노드 아래부분을 자르거나 결합한 뒤의 오류와 결합 전의 오류를 비교하여 더이상 오류가 줄어들기 전까지 반복하는 단순하고 직관적인 방법입니다.

• 룰 포스트 프루닝 (rule post pruning) 중 룰 이라는 것은 루트 노드부터 잎 노드 까지의 경로를 의미합니다. 트리를 모두 룰 형태로 변환 한 뒤 각 룰의 정확도를 구하고 정확도가 낮은 순서대로 제거하는 방법입니다.