의사결정나무(Decision Tree)

의사결정나무(Decision Tree)

 

의사결정나무(Decision Tree)는 의사결정규칙(Decision Rule)을 나무구조로 도표화하여 분류와 예측을 수행하는 분석 방법이다.

 

분류 또는 예측의 과정이 나무구조에 의한 추론규칙에 의해서 표현되기 때문에 다른 방법(신경망, 판별분석, 회귀분석 등)에 비하여 연구자가 그 과정을 쉽게 이해하고 설명할 수 있다는 장점을 가지고 있다.

 

장점	단점
해석의 용이성 교호효과의 해석 비모수적 모형	비연속성 선형성 또는 주효과의 결여 비안정성

 

데이터마이닝에서의 의사결정나무는 탐색과 모형화라는 두 가지 특성을 모두 가지고 있다고 할 수 있다. 판별분석 또는 회귀분석등과 같은 모수적 모형을 분석하기 위하여 사전에 이상치를 검색하거나 분석에 필요한 변수 또는 모형에 포함되어야 할 교호호과를 찾아내기 위하여 사용 될 수도 있고 그 자체가 분류 또는 예측 모형으로 사용 될 수도 있다.

 

[의사결정나무 구조]

의사결정 나무는 하나의 나무 구조를 이루고 있으며 마디(node)라 불리는 구성요소들로 이루어져 있다.

 

• 의사결정나무의 마디는 기능에 따라서 다음과 같이 분류 할 수 있다.
• 뿌리마디(Root Node) : 나무구조가 시작되는 마디로써 전체 자료로 이루어져 있다.
• 자식마디(Child Node) : 하나의 마디로부터 분리되어진 2개이상의 마디들을 의미
• 부모마디(Parent Node) : 자식마디의 상위마디를 의미
• 끝마디(Terminal Node) 또는 잎(Leaf) : 각 나무줄기의 끝에 위치하고 있는 마디를 의미
• 중간마디(Internal Node) : 나무구조의 중간에 있는 끝마디가 아닌 마디들을 의미
• 가지(Branch) : 하나의 마디로부터 끝마디까지 연결된 일련의 마디들을 의미하며 이 때 가지를 이루고 있는 마디의 개수를 깊이(Depth)라 한다.

 

[의사결정나무 분석 단계]

의사결정나무 분석은 아래 순서로 이루어지며 아래 과정에서 분리기준, 정지규칙, 평가기준 등을 어떻게 적용하느냐에 따라 서로 다른 의사결정나무가 형성된다.

 

• 의사결정나무의 형성 : 분석의 목적과 자료구조에 따라 적절한 분리기준(Split)과 정지규칙(Stopping Rule)을 지정하여 의사결정나무를 얻는다.
• 가지치기 : 분류오류(Classification Error)를 크게 할 위험(Risk)이 높거나 부적절한 추론규칙(Induction Rule)을 가지고 있는 가지(Branch)를 제거한다.
• 타당성 평가 : 이익도표(Gains Chart)나 위험도표(Risk Chart)또는 검증용 자료(Test Data)에 의한 교차타당성(Cross Validation) : 등을 이용하여 의사결정나무를 평가
• 해석 및 예측 : 의사결정나무를 해석하고 예측 모형을 설정

 

실제로 분석을 수행함에 있어서 반드시 이러한 순서를 지켜야 하는 것은 아니지만 단 한번에 분석이 끝나지도 않는다. 분석가는 반복적으로 수행하여 다양한 의사결정나무를 얻고 연구적 목적이나 자료구조 또는 실제의 적용에 따르는 문제점 등에 의해서 이들을 비교하고 검토하여 가장 적절한 모델을 얻을 수 있도록 노력해야 한다.

 

 

[분리기준]

분리기준은 하나의 부모마디로부터 자식마디들이 형성될 때 입력 변수(Input Value)의 선택과 범주(Category)의 병합이 이루어 질 기준을 의미한다. 즉 어떤 입력변수를 이용하여 어떻게 분리하는 것이 목표변수의 분포를 가장 잘 구별해 주는지 파악하여 자식마디가 형성되는데 목표변수의 분포를 구별하는 정도를 순수도(Purity) 또는 불순도(Impurity)에 의해서 측정하는 것이다. 이때 순수도란 목표변수의 특정 범주에 개체들이 포함되어 있는 정도를 의미한다.

 

의사결정나무는 순수도를 나타내는 어떠한 것도 분리기준으로 사용될 수 있은 일반적으로는 목표변수의 측도에 따라 다음과 같이 분리 기준을 사용한다.

 

이산형 목표 변수에 사용되는 분리기준

• 카이제곱 통계량의 P 값 : P 값이 갖아 작은 예측 변수와 그 때의 최적분리에 의해서 사직마디를 형성
• 지니 지수(Gini IndeX) : 불순도를 측정하는 하나의 지수로서 지니지수를 가장 감소시켜주는 예측변수와 그 때의 최적 분리에 의해서 자식마디를 선택
• 엔트로피 지수(Entropy Index) : 다항분포에서의 우도비 검정 통계량을 사용하는 것과 같은 것으로 알려져 있음. 이 지수가 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성.

 

연속형 목표 변수에 사용되는 분리기준

• 분산분석에서의 F 통계량 : P값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디가 형성
• 분산의 감소량 : 예측오차를 최소화하는 것과 동일한 기준으로 분산의 감소량을 최대화하는 기준의 최적분리에 의해서 자식마디가 형성

 

 

그다음 정지규칙과 가지치기 과정이 있다. 정지규칙은 더 이상 분리가 일어나지 않고 현재의 마디가 끝마디가 되도록 하는 규칙이며 가지치기는 형성된 의사결정나무에서 적절하지 않은 마디를 제거하여 적당한 크기의 부나무(Subtree)구조를 가지는 의사결정나무를 최종적인 예측모형으로 선택하는 것이다.