의사결정나무(Decision Trees)

의사결정나무분석은 예측과 분류를 위해 보편적이고 강력한 툴이다. 신경망구조 분석과는 달리 나무구조로 규칙을 표현하기 때문에 이해하기가 쉽다. 어떤 적용에서는 얼마나 잘 분류하거나 예측하는냐만이 문제화되기도 한다. 즉, DM발송회사는 모델이 어떻게 구성되었는지 보다는 얼마나 자신의 메일에 잘 대답을 해줄 수 있는 집단을 분류해줄 수 있는지에 관심을 가지고 있다. 하지만, 어떤 경우에는 왜 이런 결정을 하게 되었는지 설명하는 것도 중요하며 의사결정나무분석은 이러한 경우에 유용하다. 예를 들면, 카드신청자의 카드 발급을 거절해야 하는 경우 그것의 결과를 설명할 수 없는 이 신경망구조분석보다 이유를 설명해줄 수 있는 의사결정나무분석이 더 유용하다.

의사결정나무분석의 나무형성 알고리즘은 다양하지만, 가장 보편적인 것으로 CART (classification and regression trees)와 CHAID(chi-squared automatic interaction detection)이고, 좀 더 새로운 알고리즘은 C4.5 을 들 수 있다.

 

How a decision tree works

스무고개 게임을 해본 사람이라면 의사결정나무분석의 분류과정을 이해하기가 쉬울 것이다. 이 게임은 한 사람이 다른 사람들이 알고 있는 특정한 장소나 물건, 사람 등을 마음속에서 결정한다. 그러나 그 사람은 그것에 대한 힌트는 주지 않는다. 단지, 다른 사람들의 질문에 대하여 YES와 NO로 대답을 할 뿐이다. 잘 하는 사람은 20개의 질문을 모두 사용하지 않고서도 답을 맞춘다. 의사결정나무도 이러한 질문의 과정이라고 볼 수 있다. 게임에서 첫번째 질문이 다음에 가야할 경로(해야 할 질문)를 결정하게 된다. 질문이 잘 선택되면, 짧은 시간에 들어온 들어온 레코드를 잘 분류시킬수 있다.

의사결정나무분석은 위쪽에 뿌리노드를 그리고 밑으로 가지를 치면서 끝마디를 형성시킨다. 레코드가 뿌리마디에 놓여지고 그것이 다음의 어떤 자식마디에 속해지는 지가 결정된다.처음에 어떤 분류기준을 선택할 것인가를 결정하는 것은 여러 알고리즘이 있다. 들어온 레코드가 끝마디에 갈 때까지 이러한 과정이 반복된다.

 

Trees Grow In Many Forms

나무구조 형성의 형태 중 하나는 이진트리구조를 들 수 있다. 이 구조는 각각의 노드가 두개의 자식노드를 만들어 yes-no-질문에 답함으로써 터미널노드까지 진행해 나가는 방법이다.단순한 이진트리모양만 있는 것이 아니라 혼합된 형태의 모형도 있다.

 

Some Rules are better than others

구축된 모형에 테스트 자료를 적용시켜 그것의 예측률을 살펴봄으로써 그 모형의 효과를 측정한다. 이 때 우리는 각각의 경로를 잘 살펴보아야 한다. 즉, 여러 경로 중 더 효과적인 경로가 있기 마련이다. 이런 경우 우리는 비효과적이 가지를 치는 가지치기(pruning)방법을 적용해야 한다. 즉, 각 마디의 다음을 측정해 본다.

마디에 들어오는 레코드의 수

터미널마디가 포함하고 있는 레코드 수

마디에서 올바르게 레코드를 분리한 퍼센트

 

의사결정나무분석은 제일 먼저 자료를 가장 잘 분리할 수 있는 분리 변수로 분리기준을 찾는 것을 시작으로 한다. 그리고 나서 다음 마디에서 또한 이러한 것들을 찾아서 더 이상 잘 분리할 수 없을 때까지 나무를 형성한다.

 

CART

CART알고리즘은 의사결정나무분석을 형성하는데 있어서 가장 보편적인 알고리즘이라고 할 수 있다. 1984년 L.Briemen에 의해 발표되어 machine-learning 실험의 시초가 되고 있다.

 

*첫번째 분리기준 찾기

모형의 형성은 training data set을 가지고 한다. 목표변수는 이미 그 분류가 알려져 있으며, 우리는 나머지 설명변수를 가지고 이 목표변수를 잘 분류할 수 있는 모형을 만들어 새로운 데이터 세트에 적용시킨다.

CART알고리즘은 이진트리구조로 모형을 형성하는데 첫번째 과제는 목표변수를 가장잘 분리하는 설명변수와 그 분리시점을 찾는 것이다. 이 측도의 하나를 다양성(diversity)라고 하는데, 노드의 다양성을 가장 많이 줄이는 설명변수를 선택한다. 그리고, 분리기준은 다음 값을 가장 크게 하는 곳을 선택한다. 즉 diversity(before split)-(diversity(left child)+ diversity(right child))를 크게 하는 곳을 분리 기준을 정한다.

 

* Growing the Full tree

처음 분리기준으로 두 개의 마디를 형성하면, 목표변수를 한쪽의 값으로 분류시킬수 있는 기준을 찾아서 계속 나무를 형성해 나간다. 그래서 더 이상의 분리가 이루어지지 않고 다양성이 효과적으로 줄었을 때 끝 노드를 형성한다. 이렇게 완전히 Full tree를 형성하는 것은 주어진 데이터는 잘 맞추겠지만, 새로운 데이터가 들어오면 잘 분류하지 못할 수 있다.

 

* 각 노드의 에러율 측정

Full 모형으로 모형을 구축했더라도 모든 경우가 100%을 맞는 경우는 없다. 즉, 원래는 yes인데 no라고 분류할 수도 있다 이런 것을 에러율이라고 하는데, 즉, 확률적으로 정의하면 11개중 9개를 맞추었을 경우 맞춘 확률은 0.818이 되고, 그것의 에러율은 1-0.818로 0.182가 된다.

 

* 가지치기

앞의 단계에서 살펴보았듯이 Full모형 형성은 주어진 데이터를 잘 분류하기 위해서 분리기준과 분리를 형성했기 때문에 주어진 데이터 분류에는 잘 맞는다. 따라서, 단순히 평가를 위해서 주어진 데이터를 사용한 것이라면, 가지치기 과정은 에러율만 높일 뿐이다. 하지만 ,이렇게 형성된 모형이 새로운 데이터에서도 잘 분류할 수 있을까? 대답은 No이다. 따라서 우리는 일반적으로, 즉 새로운 데이터 셋이 들어와도 그 예측을 일반적으로 잘 할 수 있도록 적절한 가지치기를 해주어야 한다. 문제는 어느 정도까지 가지를 쳐주어야 하는 것이다.

 

* Identifying Candidate Subtrees

어느 정도까지 가지치기를 해야 할까를 결정하기 위해서 우리는 먼저 반복적인 가지치기 과정을 통해서 candidate subtrees을 결정해야 한다. 우리의 목표는 각 잎 노드에서 예측에 가장 덜 영향을 기치는 가지를 제거하는 것이다. 이러한 가지들을 정의하기 위해 여기서 “ adjusted error rate “ 라는 개념을 소개하고자 한다.

 

AE(T)=E(T) +alpha*leaf_count(T)

 

(가 0이면 adjusted error rate는 에러율과 같다. 첫번째 subtree를 찾기 위해, (를 증가 시키면서 뿌리노드를 포함하고 있는 모든 가능한 subtrees에 대한 adjusted error rate를 측정한다. 어떤 subtree의 adjusted error rate이 완전한 나무의 adjusted error rate보다 적거나 같으면 우리는 첫번째 후보 subtree를 찾은 것이다. 그리고 이 나무에 포함되어 있지 않는 가지들은 제거된다. 이러한 방법으로 가지치기를 한다.

 

Evaluating Subtrees

마지막 작업은 이렇게 선택된 subtrees로부터 새로운 데이터를 잘 분류할 수 있는 트리를 찾는 것이다. 이러한 작업을 위해 우리는 test set을 이용한다.

 

C4.5

C4.5는 J. Ross Quinlan에 의해 오랫동안 정립된 의사결정나무 알고리즘의 유용한 단편이다. 이것은 machine learning 분야의 효력 있는 ID3알고리즘과 유사하다.

 

나무형성

C4.5가 CART와 다른 점은 CART는 이진분리를 하지만 C4.5는 가지의 수를 다양화 할수 있다. 이 알고리즘은 연속변수에 대해서는 CART와 비슷한 방법을 사용하지만 범주형에서는 좀 다른 방법을 사용한다. 마약 “색깔”이 분리변수로 선택되면 나무의 다른 레벨은 각 색깔별로 노드를 형성한다.

 

가지치기

가지치기 방법도 CART와는 조금 다르다. C4.5의 가지치기는 training dataset과 멀리 떨어져있는 데이터에 대해서는 언급하지않고 가지치기를 한다. 가지치기를 할 때도 같은 데이터를 적용한다.

 

 

Chaid

CHAID는 1975년 J.A. Hartigan에 의해 소개되어진 오래된 알고리즘이다. 또한 SPSS나 SAS 통계 package에 가장 보편적인 프로그램이다. 이 알고리즘의 기원은 automatic interaction detection system AID에 기원을 두고 있다. 이것은 두 변수간의 통계적 관계를 찾는 것이다. 의사결정나무 형성을 위해 이 알고리즘을 사용한다. CART 와 다른 점은 CHAID는 데이터를 overfitting 하기 전에 나무 형성을 멈춘다는 것이다.

CHIAD(Chi-squared Automatic Interaction Detection)는 카이제곱-검점(이산형 목표변수) 또는 F-검정(연속형 목표변수)을 이용하여 다지 분리(multiway split)를 수행하는 알고리즘이다.

CHIAD는 각 설명변수의 범주들이 자료를 반응변수의 각 범주들로 구분하는 판별력의 크기에 따라 설명변수의 범주들을 이용하여 나무구조를 만드는 분석방법으로 전체 자료를 둘 이상의 하위노드(child node)로 반복적으로 분할한다. 이 과정에서 설명변수의 범주의 쌍에 대한 반응변수의 유의한 차이가 없으면 설명변수의 범주들을 병합하며, 유의적이지 않은 쌍들이 없을 때까지 과정을 계속한다. 각 설명변수에 대한 최고의 분할을 찾고, 모든 설명변수에 대한 유의성을 조사하여 가장 유의적인 설명변수를 선택한다. 선택된 설명변수의 범주들의 그룹을 사용해 자료를 상호 배반인 부분집합으로 분할하며 각 부분집합에서 정지규칙중의 하나가 만족될 때까지 이 과정을 독립적으로 순환, 반복한다.

 

이산형 목표변수에 대한 분리기준

CHIAD는 목표 변수가 이산형일 때, Pearson의 카이제곱 통계량 또는 우도비카이제곱 통계량(likelihood ratio Chi-square statistic)을 분리기준으로 사용한다. 여기서 목표 변수가 순서형 또는 사전그룹화된 연속형인 경우에는 우도비카이제곱 통계량이 사용된다. 카이제곱 통계량이 자유도에 비해서 매우 작다는 것은, 예측변수의 각 범주에 따른 목표변수의 분포가 서로 동일 하다는 것을 의미하며, 따라서 예측변수가 목표변수의 분류에 영향을 주지 않는 다고 결론지을 수 있다. 즉, p-value 값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성시킨다.

 

각 예측변수에 대한 최적 분리 탐색

단계1: 둘 이상의 범주를 가진 반응변수와 둘 이상의 범주를 가진 각 설명변수에 대한 이차원 교차표를 생성한다.
단계2: 각 설명변수의 분할표로부터 통계량을 계산한다. 계산된 p-value값이 지정된 유의수준보다 크면, 그 설명변수는 목표변수의 분류에 영향을 주지 않는 것으로 간주하여 자식 마디 형성에 제외시키며, p-value값이 가장 작은 변수를 자식마디 형성 변수로 제일 먼저 선택한다.
단계 3: 설명변수에 대하여 병합할 두 범주를 찾는다. 선택된 예측변수의 측도에 따라 가능한 모든 경우에 대해서 가장 병합될 가능성이 큰 두 범주를 찾아낸다. 두 범주의 병합에 따른 카이제곱값을 계산하고, p-value값이 지정된 유의수준보다 작다면, 두 범주에 따른 목표변수의 분포가 동일하지 않다는 것을 의미하므로 병합할 대상에서 제외된다.
단계 4: 분할표로부터 시작하여 더 이상 병합할 두 범주가 없을 때까지 단계 3를 계속하여 최종적으로 분할표를 얻는다.

 

연속형 목표변수에 대한 분리기준

목표변수가 연속형인 경우에는 두 개 이상의 그룹에 대해서 평균치 차를 검정하는 분산분석표(ANOVA )의 F 통계량을 분리기분으로 이용한다. F 통계량이 자유도에 비해서 매우 작다는 것은 예측변수의 각 범주에 따른 목표변수의 평균치 차가 존재하지 않다는 것을 의미하며, 따라서 예측변수가 목표변수의 예측에 영향을 주지 않는다고 결론지을 수 있다. 카이제곱 통계량과 마찬자지로 자유도에 대한 F 통계량의 크고 작음은 p-value으로 표현될 수 있는데 F 통계량이 자유도에 비해서 작으면 p-value은 커지게 된다.

CHIAD에서는 이와 값이 계산된 F통계량의 p-value을 기본으로 이산형 목표 변수인 경우와 유사하게 병합과 분리를 계속하여, p-value가 가장 작은 예측 변수와 그때의 최적 분리에 의해서 자식 마디가 형성된다.

 

의사결정나무분석의 장점

이해하기 쉬운 규칙을 형성
많은 컴퓨팅 작업 없이 분류과정 형성
연속변수 와 범주형 변수에 모두 사용가능
예측과 분류부분에서 가장 효과적인 방법

 

의사결정나무분석의 약점

1. 몇몇 의사결정나무 알고리즘이 이진분리를 하기 때문에 분리 가지의 수가 너무 많고 error-prone 발생
2. 나무형성 시 컴퓨팅 비용이 많이 든다. 가지치기 시, 분리기준 설정 시 각각의 경우를 다 고려해야 되므로 각 조합의 경우를 모두 고려할 경우 그리고 가지치기를 할 경우 상당한 컴퓨팅이 제공되어야 한다.

 

의사결정나무분석의 적용

이 기법은 데이터마이닝과정에서 결과를 예측하거나 자료를 분류하고자 할 때 매우 효과적인 기법이다.
Prune here / Unseen data / Training data