의사결정트리(Decision Tree)

의사결정트리란? 

의사결정트리는 데이터마이닝 분석의 대표적인 분석 방법이다.  인공지능, 기계학습, 통계분석에서도 역시 결정트리 알고리즘은 활용이 많이 되고 있다. '의사 결정 트리'는 간단하게 '결정 트리(Decision Tree)'라고 불리기도 한다. 또는 '결정 나무'라고 불리기도 한다. 

주어진 데이터를 분류(Classification)하는 목적으로 사용된다. 예측(Prediction)하는데는 사용할 수 없다. 즉, 목표 변수가 범주형인 경우 사용되며 목표변수가 수치형인 경우에는 결정트리 알고리즘에 적용할 수 없다. 목표 변수가 수치형인 데이터에 적용하고자 한다면 목표변수를 수치형 변수에서 범주형 변수로 이산화한 후 적용하면 된다. 

의사결정트리 알고리즘 종류 

결정트리 분석을 수행하는 다양한 알고리즘들이 있다. 대표적인 알고리즘들을 아래에 제시하였다. 해당 알고리즘의 동작원리를 자세히 알고싶다면 [상세보기]를 클릭하여 참고하기 바란다. 데이터마이닝에서 가장 많이 언급되고 사용되는 알고리즘은 C4.5 또는 C5.0 이다. ID3 알고리즘을 보완하여 C4.5가 개발되었고, C4.5를 보완하여 C5.0이 개발된 것이므로 ID3 -> C4.5 -> C5.0 의 순서대로 학습해야 한다. 

여러 결정트리 알고리즘이 어떤 차이점이 있는지 먼저 살펴보고 싶다면 참고1, 참고2 를 클릭해보자. 
[상세보기]를 클릭하면 각 알고리즘에 대한 자세한 설명 페이지로 이동한다. 

ID3 알고리즘 [상세보기] 
C4.5 알고리즘 [상세보기] 
C5.0 알고리즘 [상세보기] 
CART 알고리즘 [상세보기] 
CHAID 알고리즘 [상세보기] 

위 알고리즘들 중에서 ID3, C4.5, C5.0 알고리즘들은 인공지능, 기계학습 분야에서 개발되어 발전되어 온 왔다.
반면, CART 및 CHAID 알고리즘은 통계학에 분야에서 개발된 알고리즘들이다. 

두 분류는 그러한 이유로 비슷하면서도 약간 다른 접근 방식을 갖는다. 인공지능 계열의 알고리즘들은 엔트로피, 정보이득 개념을 사용하여 분리기준을 결정하고, 통계학에 기초한 CART 및 CHAID 알고리즘들은 카이스퀘어, T검정, F검정 등의 통계분석법을 사용한다. 

결정트리 알고리즘들은 기본적인 생성 방식은 유사하며 가지를 분리하는 방식(분리에 사용될 변수 및 기준을 선택하는 방식)에서의 약간의 차이를 갖는다. 분리 방식의 차이점을 아래의 표로 설명하였다. 

알고리즘	평가지수(선택방법)	비고
ID3	Entropy	다지분리(범주)
C4.5	Information Gain	다지분리(범주) 및 이진분리(수치)
C5.0	Information Gain	C4.5와 거의 유사 (차이점)
CHAID	카이제곱(범주), F검정(수치)	통계적 접근 방식
CART	Gini Index(범주), 분산의 차이(수치)	통계적 접근 방식, 항상 2진 분리

좀 더 깊이있는 의사결정트리 이해를 위한 내용 정리 

[1] C4.5 Tutorial [상세보기]
[2] [펌-분석] C4.5 와 C5.0 의 차이점 비교 [상세보기]
[3] C4.5 / CART / CHAID 알고리즘들의 비교 [상세보기] 
[4] [펌-번역] Building Classification Models: ID3 and C4.5 [상세보기]
[5] 결정트리를 그래픽으로 보여주는 교육용 툴 [상세보기] 


의사결정트리 분석의 장점

결정트리를 통한 데이터 분석의 결과는 나무(Tree) 구조로 표현되기 때문에 분석가가 결과를 쉽게 이해하고 설명할 수 있는 장점이 있다. 

분류율에 대한 정확도만 따지자면 신경망(Neural Network) 또는 로지스틱 회귀분석 등의 분류 방법들 보다 낮게 평가되기도 하지만 결과를 쉽게 이해하고 설명할 수 있으며 의사결정을 하는데 직접적으로 사용할 수 있는 장점이 있기 때문에 데이터마이닝 적용시 매우 많이 사용되고 있다. 


의사결정트리 분석의 한계

일반적인 결정트리 알고리즘은 갖는 한계, 단점을 아래에 나열하였다. 

[1] 데이터의 특성이 특정 변수에 수직/수평적으로 구분되지 못할 때 분류율이 떨어지고, 트리가 복잡해지는 문제가 발생한다. 신경망 등의 알고리즘이 여러 변수를 동시에 고려하지만 결정트리는 한 개의 변수만을 선택하기 때문에 발생하는 당연한 문제이다. 

[2] 결정트리는 Hill Climbing 방식 및 Greedy 방식을 사용하고 있다. 일반적인 Greedy 방식의 알고리즘이 그렇듯이 이 방식은 최적의 해를 보장하지는 못한다. 

[3] 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.  

관련도서에서의 의사결정트리 설명

[도서] CRM을 위한 데이터마이닝, 대청, p.151-152 (상세보기)


결정트리 분석을 수행하기 위한 프로그램

결정트리를 분석을 수행을 지원하는 다양한 프로그램들을 아래에 소개하였다. 첫번째로 제시된 Weka(웨카) 프로그램은 자바로 구현된 오프소스 프로그램이며, 웨사이트를 통해 공개되어 있다. See5.0 프로그램은 결정트리 분석만을 위해 특화된 프로그램이다. 유료 프로그램이지만 학습용으로 무료로 다운로드 하여 사용할 수 있다.  

SPSS의 클레멘타인(Clemetine) 과 SAS 의 Enterise Miner 프로그램들은 실무에서 가장 많이 사용되는 데이터마이닝 분석툴이다. 두 프로그램 모두 용량의 크며 비싼 유료 프로그램이므로 구입하지 않는다면 설치하여 사용하기가 쉽지 않다. 회사에서 개최하는 세마나에 참여하면 평가용 CD를 받을 수 있다.

[1] Weka 프로그램 [상세보기]
[2] See5. 0 [상세보기] 참고글
[3] SPSS Statistics 또는 Clementine [상세보기] 
[4] SAS Enterprise Miner [상세보기] 
[5] 결정트리를 시각적으로 보여주는 툴 [상세보기] 


의사결정트리를 생성하는 과정 설명 (동영상 포함)

[1] Weahter 데이터를 사용한 의사결정트리 생성 동영상 설명 [상세보기] 
Weka(웨카) 및 Clementine(클레멘타인) 을 사용하여 설명함
 

웨카(Weka)를 사용한 결정트리(분류) 분석

바로 위에서 설명한 바와 같이 결정트리를 사용하기 위한 많은 프로그램들이 존재한다. 
무료이면서 간편하게 사용해볼 수 있는 웨카 프로그램을 사용하여 결정트리 분석을 수행하는 방법을 설명하고자 한다. 이를 위해서 웨카 프로그램을 인터넷에서 다운로드 하고, 설치한 후, 실행하여 기본적으로 제공되는 데이터를 가지고 결정트리 알고리즘을 수행해보도록 하자. 

웨카 프로그램을 설명하는 것은 간단하지 않아서 아래에 별도의 글로 적어서 연결하였다. 
[상세보기]를 클릭하면 자세한 설명을 볼 수 있다. (이전에 사용하던 블로그로 연결됨) 

웨카 다운로드 및 설치 [상세보기] 
웨카 실행 방법 (에러 해결) [상세보기] 
웨카를 사용한 결정트리 분류 수행방법  [상세보기]


결정트리 알고리즘 개발에 도움이 되는 자료들 (소스코드 제공) 

[1] C4.5 Tutorial 이 사이트에서는 C4.5 프로그램에 대한 설명 및 구현된 C 소스를 제공한다. 
[2] WEKA 프로젝트는 자바로 된 소스를 제공한다. 


관련논문 : 의사결정트리 알고리즘을 활용한 사례 

[1] Data Mining 을 이용한 음주 및 음주문제의 위험요인과 취약성요인에 관한 탐색 
김인석(In Seok Kim),현명호(Myoung Ho Hyun),유제민(Jae Min You)
한국심리학회 | 한국심리학회지 건강 | [2001년]
KISS 논문 사이트를 통하여 검색함, [상세보기]

결정트리활용한음주건강문제090822.pdf


도움이 될만한 참고자료들

[1] 데이터마이닝 프로그램의 메뉴얼 중 <의사결정트리> 부분입니다. 웹에서 검색되어 구함. 
Decision_Tree(2009_07_19).doc
[2] SAS를 이용하여 의사결정트리를 설명한 자료. 웹에서 검색됨. 
DecisionTree_충북SAS(090719).pdf
[3] 결정트리에 대한 소개 [CRM을 위한 데이터마이닝 중] http://blog.daum.net/data_mining/21

[4] http://katalog.egloos.com/3191268  [ 여러알고리즘들을 알기쉽게 비교하며 설명함 ]

[5] Machine Learing, p.52 

Decision tree learning is one of the most widely used and practical methods for inductive inferecne. It is a method for approximating discrete-valued functions that is robust to noisy data and capable of learning disjunctive expression!s. this chapter describes a family of decision tree learning algorithms that includes widely used algorithms such as ID3, ASSISTANT and C4.5. These decision tree learning mehtods search a completely expressive hypothesis space and thus avoid the difficulties of restricted hypothesis spaces. Their inductive bias is a presence for small trees over large trees.