결정트리에 대한 소개 자료입니다. 아래의 도서에서 몇 단락을 발췌하였으니 참고바랍니다. 좀 더 자세한 학습을 원하는 경우는 아래의 도서를 준비하여 공부하시기 바랍니다.

[도서] CRM을 위한 데이터마이닝, 대청, 알렉스 버슨 외 지음 / 홍성완 외 옮김 / p.151-152

차세대 기법

이 장에서는 지난 20여년 간 학계나 연구소 등을 통해 개발되어 현재 널리 사용되고 있는 데이터마이닝 기법 중에서 정보기술 관련 서적이나 매체에서 자주 회자되는 대표적인 기법들 몇 가지를 소개하려고 한다. 이들 기법들은 주로 대용량의 데이터베이스로부터 과거에 인지하지 못했던 가치있는 정보를 추출하거나 새로운 자료/정보에 대한 예측 모델을 만드는데 사용되곤 한다. 또한 새로운 기법들을 지속적으로 개발하여 기존의 기법들을 대체하거나 보완하고 있는데, 예를 들어 의사결정나무 기법 중에서도 CHAID 와 같이 오래 전부터 사용되어 오던 기법보다는 CART 와 같은 새로운 기법을 선호하는 추세이다.

의사결정나무

의사결정나무란?

용어에서 의미하는 바와 같이 의사결정나무는 나무의 구조에 기반한 예측 모델로 나무의 가지는 데이터를 분류하기 위한 질문이며, 잎은 분류 결과에 따라 분리된 데이터 세트라고 할 수 있다. 그림 7-1은 한 이동통신 회사가 계약이 만료된 후 재계약을 하지 않은 고객(이탈고객)의 특성을 파악하기 위하여 만든 의사결정나무 모델의 일부인데, 여기에서 우리는 다음과 같은 특징을 발견할 수 있다.

  • 의사결정나무의 가지는 단 하나의 레코드도 빠짐없이 모두 분할한다. (부모마디에 속해 있는 레코드의 수는 두 개의 자식마디에 속한 레코드의 수의 합과 같다.)
  • 전체 이탈고객 및 잔류 고객의 수는 동일하며 나무의 상단 또는 하단으로 이동함에 따라 마디별 이탈고객및 잔류 고객의 수를 파악할 수 있다.
  • 신경망이나 전통적인 통계기법에 비해 모델의 구조를 이해하기 쉽다. 
     
  • 이탈 가능성이 높은 집단을 파악한 후, 그들을 상대로 마케팅 활동을 전개하는 것이 목적이라면 이 모델을 사용하는 것이 바람직하다.

  • 고객군별 특성(예, 수년간 우리의 고객이었으며 현재 최신형 단말기를 가지고 있으면 최우량 고객이다.)을 만들어 낼 수도 있다.  

 

 

 

by 에이아이 2009. 8. 12. 00:35

의사결정트리란?

의사결정트리는 데이터마이닝 분석의 대표적인 분석 방법이다.  인공지능, 기계학습, 통계분석에서도 역시 결정트리 알고리즘은 활용이 많이 되고 있다. '의사 결정 트리'는 간단하게 '결정 트리(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 논문 사이트를 통하여 검색함, [상세보기]




도움이 될만한 참고자료들

[1] 데이터마이닝 프로그램의 메뉴얼 중 <의사결정트리> 부분입니다. 웹에서 검색되어 구함.

[2] SAS를 이용하여 의사결정트리를 설명한 자료. 웹에서 검색됨.

[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.


 


 

by 에이아이 2009. 8. 2. 14:31

출처 : http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html

위의 웹페이지 에서는 ID3 및 C4.5  알고리즘에 대해서 설명하고 있습니다.
내용의 구성은 아래와 같습니다.
영어로 된 원문을 한글로 부분 부분 번역하였으니 참고하시기 바랍니다.

  • Introduction
  • Basic Definitions
  • The ID3 Algorithm
  • Using Gain Ratios
  • C4.5 Extensions
  • Pruning Decision Trees and Deriving Rule Sets
  • Classification Models in the undergraduate AI Couse
  • References

Introduction

ID3 and C4.5 are algorithms introduced by Quinlan for inducing Classification Models, also called Decision Trees, from data.
We are given a set of records. Each record has the same structure, consisting of a number of attribute/value pairs. One of these attributes represents the category of the record. The problem is to determine a decision tree that on the basis of answers to questions about the non-category attributes predicts correctly the value of the category attribute. Usually the category attribute takes only the values {true, false}, or {success, failure}, or something equivalent. In any case, one of its values will mean failure.
ID3 및 C4.5 알고리즘은 <Quinlan>에 의해 데이터로부터 <결정트리라고 분리는 분류 모델을 생성하기 위한 자료>로 소개되었다. 우리가 레코드들의 집합을 가지고 있다고 하자. 각 레코드들은 같은 구조들을 가지고 있고, 여러개의 속성/값의 쌍으로 구성된다. 이 여러개의 속성들 중에서 한 속성은 레코드의 <카테고리>를 표현하고 있다. 문제는 입력 속성(non-category attributes)들을 사용하여 <카테고리>속성의 값을 올바로 예측할 수 있는 질문의 구조인 <결정 나무>를 생성하는 것이다. 일반적으로 속성의 범주는 몇 개의 값 만들 갖는다. 예를 들어, {참, 거짓} 또는 {성공, 실패} 등의 형태를 띤다. 어떤 경우에는 그 값들의 하나는 실패를 의미할 수 있다(?).

For example, we may have the results of measurements taken by experts on some widgets. For each widget we know what is the value for each measurement and what was decided, if to pass, scrap, or repair it. That is, we have a record with as non categorical attributes the measurements, and as categorical attribute the disposition for the widget.
예를 들어, 우리는 어떤 장치의 전문가에 의해서 얻어진 측정에 의한 결과를 얻을 것이다. 각각의 장치에 대해서, 우리는 각 평가의 값이 무엇인지를 알고 있고, 무엇이 결정되었는지를 알고있다. 만약, 통과도거나, 조각내거나, 수리하거나 한다면 우리는 각 측정의 비용이 얼마이고 어떤 것이 선택되었다는 것을 안다(?). 이것은 우리가 측정에 대한 <비-카테고리> 속성들로 된 레코드들을 가지고 있고, <카테고리> 속성으로 장치의 처분을 <카테고리> 속성으로 사용하는 것이다.
( 분류에 대한 하나의 예를 든 것인데, 좋은 예는 아닌 것 같다. 차라리 이 예는 그냥 무시하고 아래의 두번째 예를 살펴보자. 본 문서에서 categorial 속성은 <범주형> 속성을 의미하는 것이 아니라 <목표> 속성을 의미하는 것이다. 물론, 목표 속성은 범주형이어야 한다.)  

Here is a more detailed example. We are dealing with records reporting on weather conditions for playing golf. The categorical attribute specifies whether or not to Play. The non-categorical attributes are:
좀더 자세한 예를 들어보자. 우리는 골프 경기를 위하여 날씨 조건에 대한 레코드들을 다룬다고 하자. 여기서 <카테고리> 속성은 경기여부 {경기함, 경기안함} 이 될 것이다. <비-카테고리> 속성들은 아래의 표와 같습니다. (즉, outlook, temperature, humidity, windy 입니다.)

	ATTRIBUTE   |	POSSIBLE VALUES
	============+=======================
	outlook	    | sunny, overcast, rain
	------------+-----------------------
	temperature | continuous
	------------+-----------------------
	humidity    | continuous
	------------+-----------------------
	windy       | true, false
	============+=======================

 

and the training data is:

	OUTLOOK | TEMPERATURE | HUMIDITY | WINDY | PLAY
	=====================================================
	sunny   |      85     |    85    | false | Don't Play
	sunny   |      80     |    90    | true  | Don't Play
	overcast|      83     |    78    | false | Play
	rain    |      70     |    96    | false | Play
	rain    |      68     |    80    | false | Play
	rain    |      65     |    70    | true  | Don't Play
	overcast|      64     |    65    | true  | Play
	sunny   |      72     |    95    | false | Don't Play
	sunny   |      69     |    70    | false | Play
	rain    |      75     |    80    | false | Play
	sunny   |      75     |    70    | true  | Play
	overcast|      72     |    90    | true  | Play
	overcast|      81     |    75    | false | Play
	rain    |      71     |    80    | true  | Don't Play

Notice that in this example two of the attributes have continuous ranges, Temperature and Humidity. ID3 does not directly deal with such cases, though below we examine how it can be extended to do so. A decision tree is important not because it summarizes what we know, i.e. the training set, but because we hope it will classify correctly new cases. Thus when building classification models one should have both training data to build the model and test data to verify how well it actually works.

A simpler example from the stock market involving only discrete ranges has Profit as categorical attribute, with values {up, down}. Its non categorical attributes are:

	ATTRIBUTE   |	POSSIBLE VALUES
	============+=======================
	age	   | old, midlife, new
	------------+-----------------------
	competition | no, yes
	------------+-----------------------
	type        | software, hardware
	------------+-----------------------

   and the training data is:

	AGE	| COMPETITION | TYPE	| PROFIT
	=========================================
	old	| yes	      | swr	| down
	---------+--------------+------------+--------
	old	| no	      | swr 	| down
	---------+--------------+------------+--------
	old	| no	      | hwr	| down
	---------+--------------+------------+--------
	mid	| yes	      | swr	| down
	---------+--------------+------------+--------
	mid	| yes	      | hwr	| down
	---------+--------------+------------+--------
	mid	| no	      | hwr	| up
	---------+--------------+------------+--------
	mid	| no	      | swr	| up
	---------+--------------+------------+--------
	new	| yes	      | swr	| up
	---------+--------------+------------+--------
	new	| no	      | hwr	| up
	---------+--------------+------------+--------
	new	| no	      | swr	| up
	---------+--------------+------------+--------
	

For a more complex example, here are files that provide records for a series of votes in Congress. The first file describes the structure of the records. The second file provides the Training Set, and the third the Test Set.

The basic ideas behind ID3 are that:

  • In the decision tree each node corresponds to a non-categorical attribute and each arc to a possible value of that attribute. A leaf of the tree specifies the expected value of the categorical attribute for the records described by the path from the root to that leaf. [This defines what is a Decision Tree.]
  • In the decision tree at each node should be associated the non-categorical attribute which is most informative among the attributes not yet considered in the path from the root. [This establishes what is a "Good" decision tree.]
  • Entropy is used to measure how informative is a node. [This defines what we mean by "Good". By the way, this notion was introduced by Claude Shannon in Information Theory.]

C4.5 is an extension of ID3 that accounts for unavailable values, continuous attribute value ranges, pruning of decision trees, rule derivation, and so on.

Definitions

If there are n equally probable possible messages, then the probability p of each is 1/n and the information conveyed by a message is -log(p) = log(n). [In what follows all logarithms are in base 2.] That is, if there are 16 messages, then log(16) = 4 and we need 4 bits to identify each message.

In general, if we are given a probability distribution P = (p1, p2, .., pn) then the Information conveyed by this distribution, also called the Entropy of P, is:

	I(P) = -(p1*log(p1) + p2*log(p2) + .. + pn*log(pn))

For example, if P is (0.5, 0.5) then I(P) is 1, if P is (0.67, 0.33) then I(P) is 0.92, if P is (1, 0) then I(P) is 0. [Note that the more uniform is the probability distribution, the greater is its information.]

If a set T of records is partitioned into disjoint exhaustive classes C1, C2, .., Ck on the basis of the value of the categorical attribute, then the information needed to identify the class of an element of T is Info(T) = I(P), where P is the probability distribution of the partition (C1, C2, .., Ck):

	P = (|C1|/|T|, |C2|/|T|, ..., |Ck|/|T|)

In our golfing example, we have Info(T) = I(9/14, 5/14) = 0.94,
and in our stock market example we have Info(T) = I(5/10,5/10) = 1.0.

If we first partition T on the basis of the value of a non-categorical attribute X into sets T1, T2, .., Tn then the information needed to identify the class of an element of T becomes the weighted average of the information needed to identify the class of an element of Ti, i.e. the weighted average of Info(Ti):

					      |Ti|
	Info(X,T) = Sum for i from 1 to n of  ---- * Info(Ti)
					      |T|

In the case of our golfing example, for the attribute Outlook we have

	Info(Outlook,T) = 5/14*I(2/5,3/5) + 4/14*I(4/4,0) + 5/14*I(3/5,2/5)
			= 0.694

Consider the quantity Gain(X,T) defined as

	Gain(X,T) = Info(T) - Info(X,T)

This represents the difference between the information needed to identify an element of T and the information needed to identify an element of T after the value of attribute X has been obtained, that is, this is the gain in information due to attribute X.

In our golfing example, for the Outlook attribute the gain is:

	Gain(Outlook,T) = Info(T) - Info(Outlook,T) = 0.94 - 0.694 = 0.246.

If we instead consider the attribute Windy, we find that Info(Windy,T) is 0.892 and Gain(Windy,T) is 0.048. Thus Outlook offers a greater informational gain than Windy.

We can use this notion of gain to rank attributes and to build decision trees where at each node is located the attribute with greatest gain among the attributes not yet considered in the path from the root.

The intent of this ordering are twofold:

  • To create small decision trees so that records can be identified after only a few questions.
  • To match a hoped for minimality of the process represented by the records being considered(Occam's Razor).

The ID3 Algorithm

The ID3 algorithm is used to build a decision tree, given a set of non-categorical attributes C1, C2, .., Cn, the categorical attribute C, and a training set T of records.

   function ID3 (R: a set of non-categorical attributes,
		 C: the categorical attribute,
		 S: a training set) returns a decision tree;
   begin
	If S is empty, return a single node with value Failure;
	If S consists of records all with the same value for 
	   the categorical attribute, 
	   return a single node with that value;
	If R is empty, then return a single node with as value
	   the most frequent of the values of the categorical attribute
	   that are found in records of S; [note that then there
	   will be errors, that is, records that will be improperly
	   classified];
	Let D be the attribute with largest Gain(D,S) 
	   among attributes in R;
	Let {dj| j=1,2, .., m} be the values of attribute D;
	Let {Sj| j=1,2, .., m} be the subsets of S consisting 
	   respectively of records with value dj for attribute D;
	Return a tree with root labeled D and arcs labeled 
	   d1, d2, .., dm going respectively to the trees 

	     ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
   end ID3;

In the Golfing example we obtain the following decision tree:

			Outlook
		       / |     \
		      /  |      \
            overcast /   |sunny  \rain
                    /    |        \
	         Play   Humidity   Windy
		       /   |         |  \
                      /    |         |   \
		<=75 /  >75|     true|    \false
		    /      |         |     \
                 Play   Don'tPlay Don'tPlay Play


   In the stock market case the decision tree is:


			 Age
		       / |    \
		      /  |     \
		  new/   |mid   \old
		    /    |       \
		  Up  Competition Down
                       /      \
		      /        \
		   no/          \yes
		    /            \
		  Up             Down

 

Here is the decision tree, just as produced by c4.5, for the voting example introduced earlier.

Using Gain Ratios

The notion of Gain introduced earlier tends to favor attributes that have a large number of values. For example, if we have an attribute D that has a distinct value for each record, then Info(D,T) is 0, thus Gain(D,T) is maximal. To compensate for this Quinlan suggests using the following ratio instead of Gain:

			 Gain(D,T)
	GainRatio(D,T) = ----------
			 SplitInfo(D,T)

   where SplitInfo(D,T) is the information due to the split of T on the basis
   of the value of the categorical attribute D. Thus SplitInfo(D,T) is

		 I(|T1|/|T|, |T2|/|T|, .., |Tm|/|T|)

   where {T1, T2, .. Tm} is the partition of T induced by the value of D.

   In the case of our golfing example SplitInfo(Outlook,T) is 

	-5/14*log(5/14) - 4/14*log(4/14) - 5/14*log(5/14) = 1.577

   thus the GainRatio of Outlook is 0.246/1.577 = 0.156. And 
   SplitInfo(Windy,T) is 

	-6/14*log(6/14) - 8/14*log(8/14) = 6/14*0.1.222 + 8/14*0.807 
					 = 0.985

   thus the GainRatio of Windy is 0.048/0.985 = 0.049

You can run PAIL to see how ID3 generates the decision tree [you need to have an X-server and to allow access (xhost) from yoda.cis.temple.edu].

C4.5 Extensions

C4.5 introduces a number of extensions of the original ID3 algorithm.

In building a decision tree we can deal with training sets that have records with unknown attribute values by evaluating the gain, or the gain ratio, for an attribute by considering only the records where that attribute is defined.

In using a decision tree, we can classify records that have unknown attribute values by estimating the probability of the various possible results. In our golfing example, if we are given a new record for which the outlook is sunny and the humidity is unknown, we proceed as follows:

   We move from the Outlook root node to the Humidity node following
   the arc labeled 'sunny'. At that point since we do not know
   the value of Humidity we observe that if the humidity is at most 75
   there are two records where one plays, and if the humidity is over
   75 there are three records where one does not play. Thus one
   can give as answer for the record the probabilities
   (0.4, 0.6) to play or not to play.

We can deal with the case of attributes with continuous ranges as follows. Say that attribute Ci has a continuous range. We examine the values for this attribute in the training set. Say they are, in increasing order, A1, A2, .., Am. Then for each value Aj, j=1,2,..m, we partition the records into those that have Ci values up to and including Aj, and those that have values greater than Aj. For each of these partitions we compute the gain, or gain ratio, and choose the partition that maximizes the gain.
In our Golfing example, for humidity, if T is the training set, we determine the information for each partition and find the best partition at 75. Then the range for this attribute becomes {<=75, >75}. Notice that this method involves a substantial number of computations.

Pruning Decision Trees and Deriving Rule Sets

The decision tree built using the training set, because of the way it was built, deals correctly with most of the records in the training set. In fact, in order to do so, it may become quite complex, with long and very uneven paths.

Pruning of the decision tree is done by replacing a whole subtree by a leaf node. The replacement takes place if a decision rule establishes that the expected error rate in the subtree is greater than in the single leaf. For example, if the simple decision tree

			Color
		       /     \
		   red/       \blue
		     /         \
		  Success     Failure

is obtained with one training red success record and two training blue Failures, and then in the Test set we find three red failures and one blue success, we might consider replacing this subtree by a single Failure node. After replacement we will have only two errors instead of five failures.

Winston shows how to use Fisher's exact test to determine if the category attribute is truly dependent on a non-categorical attribute. If it is not, then the non-categorical attribute need not appear in the current path of the decision tree.

Quinlan and Breiman suggest more sophisticated pruning heuristics.

It is easy to derive a rule set from a decision tree: write a rule for each path in the decision tree from the root to a leaf. In that rule the left-hand side is easily built from the label of the nodes and the labels of the arcs.

The resulting rules set can be simplified:

Let LHS be the left hand side of a rule. Let LHS' be obtained from LHS by eliminating some of its conditions. We can certainly replace LHS by LHS' in this rule if the subsets of the training set that satisfy respectively LHS and LHS' are equal.

A rule may be eliminated by using metaconditions such as "if no other rule applies".

You can run the C45 program here [you need to have an X-server and to allow access (xhost) from yoda.cis.temple.edu].

Classification Models in the Undergraduate AI Course

It is easy to find implementations of ID3. For example, a Prolog program by Shoham and a nice Pail module.

The software for C4.5 can be obtained with Quinlan's book. A wide variety of training and test data is available, some provided by Quinlan, some at specialized sites such as the University of California at Irvine.

Student projects may involve the implementation of these algorithms. More interesting is for students to collect or find a significant data set, partition it into training and test sets, determine a decision tree, simplify it, determine the corresponding rule set, and simplify the rule set.

The study of methods to evaluate the error performance of a decision tree is probably too advanced for most undergraduate courses.

References

   Breiman,Friedman,Olshen,Stone: Classification and Decision Trees
	Wadsworth, 1984

   A decision science perspective on decision trees.

   Quinlan,J.R.: C4.5: Programs for Machine Learning
	Morgan Kauffman, 1993

   Quinlan is a very readable, thorough book, with actual usable programs 
   that are available on the internet. Also available are a number of 
   interesting data sets.

   Quinlan,J.R.: Simplifying decision trees
	International Journal of Man-Machine Studies, 27, 221-234, 1987

   Winston,P.H.: Artificial Intelligence, Third Edition
	Addison-Wesley, 1992

   Excellent introduction to ID3 and its use in building decision trees and,
   from them, rule sets.

ingargiola@cis.temple.edu

by 에이아이 2009. 8. 2. 02:52

소개하는 자료에서는 결정트리를 생성하는 과정을 비주얼하게 보여주는 교육용 프로그램을 설명하고 있습니다. 프로그램을 다운로드 할 수 있으며, 프로그램을 사용하는 방법을 동영상으로 제공하고 있습니다.

출처 : http://gladtosee.tistory.com/7 

 

 

by 에이아이 2009. 8. 2. 02:43

데이터마이닝의 여러가지 분석 기법들 중에서 결정트리는 매우 많이 사용되고 있습니다.
데이터마이닝의 대표적인 분석 방법이라고 해도 괜찮을 것 같습니다.

결정트리 분석을 수행하는 알고리즘들은 여러가지가 있습니다.
널리 알려져있는 대표적인 결정트리 알고리즘은 ID3, C4.5, CART, CHAID 등이 있습니다. 

각 방법들의 역사 및 차이점을 설명한 자료를 아래의 <출처>에서 발췌하였습니다.
출처 : http://katalog.egloos.com/3191268

CART

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

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


C4.5
C4.5는 J. Ross Quinlan에 의해 오랫동안 정립된 의사결정나무 알고리즘의 유용한 단편이다. 이것은 machine learning 분야의 효력 있는 ID3 알고리즘과 유사하다.
(정확하게 얘기하면 ID3와 유사하다기 보다는 ID3 를 보완하여 발전시킨 알고리즘입니다.)

C4.5가 CART와 다른 점은 CART는 이진분리를 하지만 C4.5는 가지의 수를 다양화 할수 있다. 이 알고리즘은 연속변수에 대해서는 CART와 비슷한 방법을 사용하지만 범주형에서는 좀 다른 방법을 사용한다. 마약 “색깔”이 분리변수로 선택되면 나무의 다른 레벨은 각 색깔별로 노드를 형성한다.
(C4.5는 속성이 갖는 범주값의 수만큼 분리를 수행합니다. 실 데이터의 분석에서 가지가 매우 잘게 나눠지는 문제가 있습니다. 반면, CART는 딱 2개로만 분리합니다. 지나치게 단순하되는 상황으로 문제가 될 수 있습니다.) 

가지치기 방법도 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 값이 가장 작은 예측변수와 그 때의 최적분리에 의해서 자식마디를 형성시킨다.

by 에이아이 2009. 8. 2. 02:35

CART 알고리즘은

1984년 스탠포드와 버클리 대학의 Leo Breiman, Jerome Friedman, Richard Olshen, Charles Stone 등에 의해 제안된 알고리즘이다. (저서: Classification And Regression Trees)

ID3 와 접근 방식은 동일하지만,
차이점은 속성 선택을 위한 기준으로 엔트로피의 변화를 사용한 것이 아니라
엔트로피 매트릭스를 사용한다.  

엔트로피 메트릭스는 1949년 Claude Shannon과 Warren Weaver의 정보이론 연구에서 제시된 개념이다.

또한 CART 알고리즘의 최대 강점은
후보 나무들을 여러 개 생성하고 그 중에서 최적의 나무를 찾아내는 방법을 사용하는 것이다.

데이터를 훈련용, 테스트 용으로 내부적으로 구분하여 사용함을 통해 과잉맞춤 문제를 해결한다.

Classification and Regression Trees (1984, Bresiman et al.)
CART 알고리즘은 지니 지수(Gini Index) 또는 분산의 감소량을 사용하여 나무의 가지를 이진(Binary) 분리한다. (범주형 변수에 대해서는 지니 지수를 사용하고, 연속형 변수에 대해서는 분산의 감소량을 사용한다.)
참고자료 : 사례로 배우는 데이터마이닝 [자유아카데미, 최종후/소선하] p.28


[의사결정트리 알고리즘의 성과 비교에 관한 연구] 논문의 설명
(광운대학교 경영정보학과 김신곤, 동양시스템즈 박성용 저)

2.2 CART(Classification And Regression Tree)

CART 알고리즘은 의사결정 트리 방법론 중 가장 잘 알려진 방법론 가운데 하나이다. 1984년 Brieman et. al 이 CART 기법을 발표한 이래로 기계 학습 실험의 필수기법이 되어왔다 [Berry and Linoff, 1997]. CART 기법은 전체 데이터셋을 갖고 시작하여 반복해서 두 개의 자식 노드(Child Node)를 생성하기 위해 모든 예측 변수(Predictor variables)를 사용하여 데이터 셋의 부분집합을 쪼갬으로써 의사결정트리를 생성한다 [Berry and Linoff, 1997, SPSS, 1998].

그 순수성은 다음과 같은 원리에 의하여 계산된다. 남자 500명중 응답자와 비응답자가 각각 100, 400 이라고 하자. 2번에 걸쳐 고객을 뽑을 때, 2번 모두 응답자일 확률은 (100/500)^2 = (1/5)^2 이고 마찬가지로 비응답자일 확률은 (400/500)^2 = (4/5)^2 이다. Gini Index는 최종적으로 다음과 같이 계산이 된다. [SAS, 1998].

Gini Index = 1 - (1/5)^2 - (4/5)^2

위에서 계산된 Gini Index는 모든 카테고리(응답/비응답)에 대하여 임의로 두개의 원소(고객)을 뽑을 때, 두 개의 원소가 각각 다른 카테고리에서 뽑힐 확률로 해석할 수 있다. 의사결정나무는 Gini Index 가 작아지는 방향으로 움직이며 Gini Index 값을 가장 많이 감소시켜 주는 변수가 영향을 가장 많이 끼치는 변수가 된다. 그리고 이 변수를 기준으로 의사결정나무의 가지가 만들어 진다. [SAS, 1998].

위 논문에서는 계속하여 CART 알고리즘의 진행 절차를 설명한다. (p.373-374)






by 에이아이 2009. 7. 29. 19:06
| 1 |