참고주소 : http://www.rulequest.com/see5-comparison.html

0. C4.5와 C5.0은 어떻게 다른가?

C4.5 is a widely-used free data mining tool that is descended from an earlier system called ID3 and is followed in turn by See5/C5.0. To demonstrate the advances in this new generation, we will compare See5/C5.0 Release 2.06 with C4.5 Release 8 using three sizable datasets:


Sleep stage scoring data (sleep, 105,908 cases). Every case in this monitoring application is described by six numeric-valued attributes and belongs to one of six classes. C5.0 and C4.5 use 52,954 cases to construct classifiers that are tested on the remaining 52,954 cases. The data are available from here.
Census income data (income, 199,523 cases). The goal of this application is to predict whether a person's income is above or below $50,000 using seven numeric and 33 discrete (nominal) attributes. The data are divided into a training set of 99,762 cases and a test set of 99,761. They can be obtained from the UCI KDD Archive.
Forest cover type data (forest, 581,012 cases); also from UCI. This application has seven classes (possible types of forest cover), and the cases are described in terms of 12 numeric and two multi-valued discrete attributes. As before, half of the data -- 290,506 cases -- are used for training and the remainder for testing the learned classifiers.
Since C4.5 is a Unix-based system, results for the Unix version C5.0 are presented to facilitate comparison. Both were compiled using the Intel C compiler 10.1 with the same optimization settings. Times are elapsed seconds for an unloaded Intel Q9550 (2.8GHz) with 2GB of RAM running 64-bit Fedora Core.
So, let's see how C5.0 stacks up against C4.5.

1. Rulesets: often more accurate, much faster, and much less memory

 These graphs show the accuracy on unseen test cases, number of rules produced, and construction time for the three datasets. Results for C5.0 are shown in blue.

Both C4.5 and C5.0 can produce classifiers expressed either as decision trees or rulesets. In many applications, rulesets are preferred because they are simpler and easier to understand than decision trees, but C4.5's ruleset methods are slow and memory-hungry. C5.0 embodies new algorithms for generating rulesets, and the improvement is dramatic.

Accuracy: The C5.0 rulesets have noticeably lower error rates on unseen cases for the sleep and forest datasets. The C4.5 and C5.0 rulesets have the same predictive accuracy for the income dataset, but the C5.0 ruleset is much smaller.
Speed: The times are almost not comparable. For instance, C4.5 required more than 84 minutes to find the ruleset for income, but C5.0 completed the task in just over 4 seconds.
Memory: C5.0 commonly uses an order of magnitude less memory than C4.5 during ruleset construction. For the forest dataset, C4.5 needs more than 3GB (the job would not complete on earlier 32-bit systems), but C5.0 requires less than 200MB.

2. 기능적인 차이 (C5.0 에서 추가된 기능)

New functionality
C5.0 incorporates several new facilities such as variable misclassification costs. In C4.5, all errors are treated as equal, but in practical applications some classification errors are more serious than others. C5.0 allows a separate cost to be defined for each predicted/actual class pair; if this option is used, C5.0 then constructs classifiers to minimize expected misclassification costs rather than error rates.

The cases themselves may also be of unequal importance. In an application that classifies individuals as likely or not likely to "churn," for example, the importance of each case may vary with the size of the account. C5.0 has provision for a case weight attribute that quantifies the importance of each case; if this appears, C5.0 attempts to minimize the weighted predictive error rate.

C5.0 has several new data types in addition to those available in C4.5, including dates, times, timestamps, ordered discrete attributes, and case labels. In addition to missing values, C5.0 allows values to be noted as not applicable. Further, C5.0 provides facilities for defining new attributes as functions of other attributes.

Some recent data mining applications are characterized by very high dimensionality, with hundreds or even thousands of attributes. C5.0 can automatically winnow the attributes before a classifier is constructed, discarding those that appear to be only marginally relevant. For high-dimensional applications, winnowing can lead to smaller classifiers and higher predictive accuracy, and can even reduce the time required to generate rulesets.

C5.0 is also easier to use. Options have been simplified and extended -- to support sampling and cross-validation, for instance -- and C4.5's programs for generating decision trees and rulesets have been merged into a single program.

The Windows version, See5, has a user-friendly graphic interface and adds a couple of interesting facilities. For example, the cross-reference window makes classifiers more understandable by linking cases to relevant parts of the classifier.

RuleQuest provides free source code for reading and interpreting See5/C5.0 classifiers. After the classifiers have been generated by See5/C5.0, this code allows you to access them from other programs and to deploy them in your own applications.

For more information on See5/C5.0, please see the tutorial.


3. Decision trees: faster, smaller

 For all three datasets, C4.5 and C5.0 produce trees with similar predictive accuracies (although C5.0's are marginally better for the sleep and income applications). The major differences are the tree sizes and computation times; C5.0's trees are noticeably smaller and C5.0 is faster by factors of 6.5, 4.6, and 21 respectively.

4. Boosting

 Based on the research of Freund and Schapire, this is an exciting new development that has no counterpart in C4.5. Boosting is a technique for generating and combining multiple classifiers to improve predictive accuracy.

The graphs above show what happens in 10-trial boosting where ten separate decision trees or rulesets are combined to make predictions. The error rate on unseen cases is reduced for all three datasets, substantially so in the case of forest for which the error rate of boosted classifiers is more than 40% below that of the corresponding C4.5 classifier. Unfortunately, boosting doesn't always help -- when the training cases are noisy, boosting can actually reduce classification accuracy. C5.0 uses a proprietary variant of boosting that is less affected by noise, thereby partly overcoming this limitation.

C5.0 supports boosting with any number of trials. Naturally, it takes longer to produce boosted classifiers, but the results can justify the additional computation! Boosting should always be tried when peak predictive accuracy is required, especially when unboosted classifiers are already quite accurate.


by 에이아이 2009. 8. 4. 19:19

출처1 : http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html
출처2 : http://www2.cs.uregina.ca/~dbd/ (교수홈페이지)
출처3 : http://www.cs.uregina.ca/ (학과홈페이지)

설명 :

C4.5 알고리즘은 Quinlan 에 의해 디자인된 ID3 알고리즘을 확장한 알고리즘이다. ID3가 가지고 있는 여러가지 한계들을 극복하기 위하여 몇 가지 방법들을 추가한 알고리즘이다.

이 자료는 캐나다의 uregina 대학의 컴퓨터학과 교수님이 제공하고 있는 C4.5 알고리즘에 대한 설명 자료이다. C4.5에 대한 간단한 소개 및 제작한 C언어 소스코드 및 사용방법(매뉴얼)등을 제공하고 있다. 이 자료에서는 C4.5에 대해서 간단히 설명하며, C4.5 프로그램 소스 코드를 제공하고 있다. UNIX 콘솔 상태에서 실행할 수 있도록 만들어진 C언어 로 만들어진 프로그램이며, 설치방법 및 실행방법(매뉴얼)은 아래에 자세히 설명하고 있다.

내용 :  

 

References:

  • P. Winston, 1992.

C4.5 is a software extension of the basic ID3 algorithm designed by Quinlan to address the following issues not dealt with by ID3:

  • Avoiding overfitting the data
    • Determining how deeply to grow a decision tree.
  • Reduced error pruning.
  • Rule post-pruning.
  • Handling continuous attributes.
    • e.g., temperature
  • Choosing an appropriate attribute selection measure.
  • Handling training data with missing attribute values.
  • Handling attributes with differing costs.
  • Improving computational efficiency.

It is installed for use on Grendel (grendel.icd.uregina.ca), but it may be set up on a local machine as follows:

C4.5 Release 8 Installation Instructions for UNIX

  1. Download the C4.5 source code.
  2. Decompress the archive:
    1. Type "tar xvzf c4.5r8.tar" (not universally supported), or, alternatively,
    2. Type "gunzip c4.5r8.tar.gz" to decompress the gzip archive, and then
      Type "tar xvf c4.5r8.tar" to decompress the tar archive.
  3. Change to ./R8/Src
  4. Type "make all" to compile the executables.
  5. Put the executables into a "bin" subdirectory and include it in the path for command-line usage.

Manual Pages

  • c4.5: using the c4.5 decision tree generator.
  • verbose c4.5: interpreting output generated by c4.5.
  • consult: uses a decision tree to classify items.
  • consultr: uses a rule set to classify items.

Examples

Click on the links below for examples of C4.5 usage:

C4.5 소스코드 다운로드

혹시 위의 사이트에서 다운로드가 안될 경우 오른쪽 파일 아이콘을 클릭하여 다운로드 받을 수 있습니다.

 

 

 

 

 

by 에이아이 2009. 8. 4. 18:54

출처 : 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

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

결정트리 분석을 수행하는 알고리즘들은 여러가지가 있습니다.
널리 알려져있는 대표적인 결정트리 알고리즘은 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

본 글에서는 대표적인 데이터마이닝 프로그램인 WEKA를 사용하여 의사결정트리 분류 분석을 수행하는 방법을 설명합니다. 프로그램을 설치하면 기본적으로 제공되는 Weather 데이터를 사용하여 분석을 해보았습니다.

Weka 시작하기

weka 프로그램 설치와 실행을 성공하였으니 간단하게 프로그램을 사용해보도록 하자.
첫 화면에서 하단에 4개의 버튼이 보이는데 그 중 [Explorer]를 클릭한다.
그러면 아래의 오른쪽 그림과 같은 화면이 생성된다.



* 전처리 부분에서 첫 번째 메뉴인 [Open file...]을 클릭한 후, [iris.arff] 파일을 선택한다.
  ( arff 파일은 weka 프로그램의 입력 형식을 따르는 데이터 파일이다. )



선택한 데이터에 대하여 아래와 같이 데이터의 기본 속성 및 분포가 표시된다.
( weka는 텍스트 파일 뿐 아니라 DB를 통해서도 사용할 수 있도록 지원하고 있다. )



오른쪽 중간 위치의 [Visualize All] 버튼을 클릭하면 데이터의 각 속성에 대한 분포를 그림으로 보여준다.
( 데이터를 처음 이해할 때 챠트 분석을 통해 이해하는 것은 쉬우면서도 필수적인 과정이다. )

5개의 속성에 대하여 챠트가 그려진다. 챠트의 색상은 타겟 클래스 값으로 구분된 것이다.




Weka 분류(J48/C4.5) 분석 해보기

이번에는 날씨에 관련된 다른 데이터를 선택하고 분석을 수행해보도록 하자.

이 데이터는 날씨에 따라 Play 여부를 기록한 데이터이다. 날씨의 어떠함에 따라 운동경기를 했는지, 안했는지의 과거 정보들을 기록해둔 데이터이다. 이 데이터를 분석하면 어떤 날씨 조건에서 운동을 하는 것이 좋은 가에 대한 유용한 지식을 얻을 수 있을 것이다.

먼저 데이터를 이해하기 위해 설명한다. wether.nomial.csv 파일은 메모장으로 열면 아래와 같다.

Excel 프로그램으로 파일을 열면 오른쪽 그림과 같이 볼 수 있다.



csv 파일 형식은 각 데이터의 요소들을 콤마(,)로 구분한 텍스트 파일이다. 따라서 위와 같이 메모장이나 글 같은 워드프로세서 프로그램으로 열 수 있다. 그리고 위와 같이 엑셀 프로그램을 사용하여 열면 좀 더 보기 좋게 표시된다.

위 파일을 Weka에서 입력으로 받아 분석하기 위해서는 ARFF 형식으로 변경해주어야 한다. CSV 형식은 WEKA 프로그램에서 입력으로 허용하지 않는다. ARFF 형식으로 변경한 결과는 아래와 같다.

ARFF 형식은 왼쪽 그림과 같이 @relation, @attribute, @data 의 3개의 영역으로 표현된다.
각 내용은 아래와 같이 입력한다.

@relation 데이터명칭

@attribute 속성이름 {범주형의 값 리스트 }
본 데이터셋은 5개의 범주형 속성으로 구성되었다.

@data
하단에 한 줄에 하나의 레코드(인스턴스)를 기록함.
본 데이터셋은 14개의 레코드가 입력되었다.

데이터는 범주형 속성 뿐 아니라 수치형 속성을 포함할 수도 있다.
위에서 소개한 Weather 데이터의 원래 형태는 아래와 같이 수치형으로 구성되어 있다.



위의 파일과 같이 수치형 속성을 포함했을 때의 ARFF 파일을 생성하는 방법을 예를 통해 설명하겠다.

위 파일을 ARFF 형식으로 변환한 결과는 아래와 같다.

 
위에서 설명한 바와 같이 @attribute 라인을 통해 각 속성에 대한 정보를 기록한다. 이 때, 범주형 속성과 수치형 속성을 구분하여 기록해주어야 한다.

(1) 범주형 속성
@attribute 속성이름 {범주형의 값 리스트 }
본 데이터셋은 5개의 범주형 속성으로 구성되었다.

(2) 수치형 속성
@attribute 속성이름 real

즉, 수치형 속성은 속성의 이름을 적어 준 후, 뒤에 real 이라고만 기록해주면 된다. 범주형 속성의 경우 값을 모두 적어주지만, 수치형은 간단하다.



통계 또는 데이터마이닝 등의 분석 프로그램에서는 입력데이터의 속성을 지정해주어야 한다. 다양하게 요구하는 프로램도 있지만, Weka에서는 2개의 속성 즉, ➀범주형 속성, ➁수치형 속성으로만 구분한다. 범주형 속성은 Categorial 또는 Nominal 속성으로 불려진다. 그리고 수치형 속성은 보통 numeric 속성으로 불려진다.  

@attribute 정의 부분에서 맨 아래쪽에 기입한 속성이 분석의 목표가 되는 속성으로 인식된다. 
그럼, 위에서 설명하고 준비한 weather.nominal.arff 파일을 Weka를 사용하여 분석해보도록 하자. 초기화면에서 [Open file...]을 클릭하여 해당 파일을 선택하면, 아래 그림과 같이 표시된다.




좌측 중간 화면에 5개의 속성의 이름이 표시된 것을 볼 수 있다. 특정 속성에 대한 체크박스를 클릭하면, 오른쪽 부분에 각 속성의 통계 분석이 표시된다.



그림에서 파랑색은 play 속성이 Yes 값을 갖는 경우이고, 빨강색은 play 속성이 No 값을 갖는 경우를 구분한 것이다. 즉 해석하면, Outlook(조망)이 Sunny(맑음)인 경우는 안하는 경우가 약간많고, Overcast(흐림)인 경우 100% 운동을 하고, Rainy(비옴)인 경우도 경기하는 비율이 약간 높음을 볼 수 있다. 온도에 따라서는 크게 비율의 차이가 없는 것으로 보인다.

그럼, 대표적인 데이터마이닝 분석 방법인 C4.5 의사결정트리 알고리즘을 사용하여 분석해보도록 하자. Weka에서는 C4.5 알고리즘을 J4.8 이라는 이름으로 제공하고 있다.  

단계1. 데이터를 선택한다. (우리는 이미 전 단계에서 weather.arff 파일을 선택하였다. )

단계2. 메뉴에서 [Classify]를 선택한다. 왼쪽 상단의 [Choose] 버튼을 클릭한 후 trees 항목에 속해있는 J48 알고리즘을 선택한다.



단계3. 왼쪽 중간 부분의 [Start] 버튼을 클릭하면, J48 분석을 수행을 시작한다.
          데이터의 크기가 작으므로 잠깐만 기다리면 오른쪽에 결과가 텍스트 형식으로 출력된다.



  위에서 수행한 Weather 데이터에 대한 J48 알고리즘의 수행결과를 분석해보도록 하자. 텍스트 결과 전체를 아래의 그림에 표시하였다. 데이터에 대한 설명과 트리 결과 모델 그리고 데이터를 구분하여 검증한 결과들을 보여준다.  

  아래의 결과에서 가장 중요한 부분은 빨강색으로 표시한 트리(tree) 부분이다. 운동 경기(play)에 영향을 주는 속성은 조명(outlook), 습도(humidity), 풍량(windy)으로 분석되었다. 가장 중요한 속성은 조망(outlook)이다.

=== Run information ===

Scheme  :     weka.classifiers.trees.J48 -C 0.25 -M 2
Relation  :     weather
Instances :     14
Attributes :     5    ( outlook , temperature, humidity, windy, play )

Test mode: 10-fold cross-validation

=== Classifier model (full training set) ===

J48 pruned tree
------------------
outlook = sunny
|   humidity <= 75: yes (2.0)
|   humidity > 75: no (3.0)
outlook = overcast: yes (4.0)
outlook = rainy
|   windy = TRUE: no (2.0)
|   windy = FALSE: yes (3.0)

Number of Leaves  :  5
Size of the tree :  8

Time taken to build model: 0.03 seconds

=== Stratified cross-validation ===

=== Summary ===
Correctly Classified Instances           9               64.2857 %
Incorrectly Classified Instances         5               35.7143 %
Kappa statistic                          0.186
Mean absolute error                      0.2857
Root mean squared error                  0.4818
Relative absolute error                 60      %
Root relative squared error             97.6586 %
Total Number of Instances               14    

=== Detailed Accuracy By Class ===
TP Rate   FP Rate   Precision   Recall  F-Measure   Class
  0.778     0.6        0.7       0.778     0.737    yes
  0.4       0.222      0.5       0.4       0.444    no

=== Confusion Matrix ===
 a b   <-- classified as
 7 2 | a = yes
 3 2 | b = no 



위의 텍스트로 된 Tree 결과를 시각적으로 표시하면 의미를 쉽게 이해할 수 있다. Weka에서는 텍스트 뿐 아니라 시각적인 기능도 제공하고 있다. 왼쪽 하단의 [Result list] 부분에서 방금 수행된 [tree.J48] 항목에서 마우스 오른쪽 버튼을 누른 후 [Visualzie tree]를 클릭한다.



아래와 같은 시각화된 의사결정트리를 볼 수 있다.



이상으로 Weka 를 설치하고 간단히 사용해 보는 연습을 마치겠습니다.



 



 


 

by 에이아이 2009. 8. 1. 23:41
| 1 |