SAS
바로가기 : http://www.sasmining.co.kr/information.asp

사용자 삽입 이미지
by 에이아이 2009. 8. 2. 03:19

인공지능개념및응용 교재의 PPT 강의자료 입니다. 교재의 각 장별 구성은 아래의 표와 같습니다.

이 교재에서는 탐색, 지식표현, 불확실성, 퍼지이론, 전문가시스템, 계획, 학습, 신경망, 비전, 자연어, 에이전트 등의 인공지능의 전반적인 내용들을 다루고 있습니다.

 

 교재의 강의교안 PPT 자료입니다.

 아래의 파일을 클릭하면 다운로드할 수 있습니다.

각 장별 내용입니다.

 내용

 제목

 1장  서론
 2장  탐색
 3장  지식표현
 4장  불확실성
 5장  퍼지이론
 6장  전문가
 7장  계획
 8장  학습
 9장  신경망
 10장  비전
 11장  자연어
 12장  에이전트



by 에이아이 2009. 8. 2. 03:04

출처 : 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 홈페이지 소개 

웨카(weka) 설치 프로그램은 해당 프로젝트 홈페이지를 방문하여 다운로드 받을 수 있다.

 * 프로젝트 명칭 : Weka Machine Learning Project
 * 프로젝트 주소 : http://www.cs.waikato.ac.nz/ml/weka/


Weka 다운로드 <6단계 과정> 설명  


[1단계] 홈페이지를 방문한 후 왼쪽 편의 [Download] 를 클릭한다.

[2단계]
 개발자 버전(소스코드 포함)에서 다운로드한다.
            자바환경을 포함할 경우 34이고 포함하지 않을 경우 18M 정도이다.

[3단계]
전 단계에서 다운로드 하기 위해 <here> 부분을 클릭하면 [SourceForge.Net] 사이트를 통해
            다운로드 할 수 있도록 연결된다. [Download] 글자를 클릭한다.

[4단계]
 다양한 버전의 weka를 선택하여 다운로드 받을 수 있다.
            2008년 8월 현재 3.5.8 버전까지 개발된 것을 확인할 수 있다. 3.4.13 버전을 클릭하였다. 
            (최근 버전의 경우 오류가 발생할 수 있음으로 안정성이 있는 약간 이전의 버전을 선택했다.) 

[5단계] weka-3-4-13jre.exe 파일을 클릭하여 다운로드 한다.

[6단계] [저장] 버튼을 눌러 다운로드를 시작한다.


아래에 WEKA 다운로드 과정을 그림으로 다시 설명하였다.

1단계.

홈페이지를 방문한 후 왼쪽 편의 [Download] 를 클릭한다.

2단계.

개발자 버전(소스코드 포함)에서 다운로드한다. 자바환경을 포함할 경우 34이고 포함하지 않을 경우 18M 정도이다. 

3단계.

전 단계에서 다운로드 하기 위해 <here> 부분을 클릭하면 [SourceForge.Net] 사이트를 통해 다운로드 할 수 있도록 연결된다. [Download] 글자를 클릭한다. 

4단계. 

 다양한 버전의 weka를 선택하여 다운로드 받을 수 있다.     2008년 8월 현재 3.5.8 버전까지 개발된 것을 확인할 수 있다. 3.4.13 버전을 클릭하였다. (최근 버전의 경우 오류가 발생할 수 있음으로 안정성이 있는 약간 이전의 버전을 선택했다.)


5단계.

weka-3-4-13jre.exe 파일을 클릭하여 다운로드 한다.  

6단계. 

[저장] 버튼을 눌러 다운로드를 시작한다.


바탕화면에 설치 프로그램 파일(weka-3-4-13jre.exe) 다운로드가 완료되었다.




지금까지 weka 설치 프로그램을 다운로드 하는 방법을 사용하였다.

다운로드하는 방법은 차후 변경될 수 있음으로 참고하기 바란다.

이제 다음 부분에서는 프로그램을 설치하고 실행하는 방법을 배워보도록 하겠다. 


Weka 설치하고 실행하기   

이전 단계에서 다운로드 한 설치 프로그램 파일을 더블클릭하여 실행한다.

설치 마법사가 실행되는데 아래와 같이 단계별로 선택하여 설치한다. 

 [1단계] [next] 버튼을 클릭한다.  [2단계] [next] 버튼을 클릭한다.
 



  [3단계] 설치 옵션을 선택한다.  [4단계] 설치할 폴더를 선택한다.
 
 


Weka 실행하기 

이전 단계에서 weka 프로그램을 설치를 완료하였다.

설치를 완료하였으면 시작 프로그램에 weka가 등록된 것을 확인할 수 있다.

그럼 등록된 버튼을 눌러 weka를 실행해보자.

[시작] - [모든 프로그램] - [Weka 3.4.13] - [Weka 3.4] 경로로 실행하였다.




앗~ 그런데 ..., 아래와 같이 에러 화면이 발생하였다.



이 화면에서는 왜 에러가 발생했는지 이유를 설명하지 않고, 그냥 치명적인 오류가 발생하여 종료된다고 설명할 뿐이다.

이러한 에러가 발생하는 이유는 자바 프로그램 실행시 기본적으로 지정되어 있는 메모리의 크기가 부족하기 때문에 발생하는 것이다. (컴퓨터에 설치된 메모리가 부족하기 때문은 아니다.)

따라서 이 문제를 해결하고 제대로 실행하기 위해서는 다음과 같은 명령으로 실행하면 된다.

                                                       java -Xmx256m -jar weka.jar 

위 명령을 수행하기 위해서는 도스 명령창을 띄우고, weka가 설치되어 있는 폴더로 이동한 후,

아래와 같이 명령을 실행하면 된다. 

 

설명한 것과 같이 메모리를 설정한 후 실행하면 아래와 같이 프로그램이 실행된다.

작은 프로그램 화면이 나타난다.  프로그램에는 weka 새의 그림이 표시되어 있다.

도스 프로그램 창에는 "---Registering Weka Editors-- " 라고 텍스트가 표시된 것을 볼 수 있다.



이렇게 해서 처음에 발생하는 에러 문제를 해결하고 정상적으로 웨카 프로그램을 실행하였다.

* 쉽게 실행하는 방법

메모리 크기 설정 문제로 인해서 도스 명령어를 사용해서 실행하는 방법을 설명하였다.

이러한 방식은 번거롭기 때문에 배치(Batch) 파일을 만들어서 클릭만 하면 실행되도록 하는 것이 좋다.  

[1단계] 아래와 같이 메모장을 사용하여 텍스트 파일을 만들자.
[2단계] 이 파일을 바탕화면에 두고 클릭하여 간단하게 실행할 수 있다. (또는 바로가기 링크)  



위와 같이 텍스트 파일을 만들어서 바탕화면에 두거나 또는 바로가기 아이콘을 만들어 두고 실행하면 되겠다. 
 
이상으로 Weka를 설치하고 실행하는 방법을 설명하였습니다.

끝~


 

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

본 글에서는 대표적인 데이터마이닝 프로그램인 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
  • 로그인시러 2009.11.18 15:26 신고 ADDR EDIT/DEL REPLY

    잘 보고 갑니다.
    자주 놀러올게욤 .. 근데, 출처 남기고 긁어가도 대죵??
    원치 않으시면 삭제하겠습니다.

  • LOV2 2010.06.19 11:56 ADDR EDIT/DEL REPLY

    너무 감사히 잘봤습니다. 그러면 WEKA를 사용해서 규칙기반 분류도 할 수 있나요?

  • 도리도롱 2011.07.18 15:28 ADDR EDIT/DEL REPLY

    웨카로 디시전트리 분석 하려고 하면서 찾아오게 되었습니다. 차근차근 이해하기 좋게 잘 정리해주셔서 감사합니다. 도움이 많이 되었네요.

  • 김범수 2012.01.25 19:22 ADDR EDIT/DEL REPLY

    저 WEKA 관련해서 궁금하게 하나 있는대요.. FP-Growth 알고리즘은 True/false 데이터에 대해서만 가능한건가요? 제가 지식이 없어서요.... 며칠째 고생중입니다..

  • 나경민 2012.11.14 03:27 ADDR EDIT/DEL REPLY

    arff 변환과정이 이해가 안되는데요.... 다른 변환프로그램은 따로 없나요. ㅜㅜ

EM 알고리즘 소개 (Expectation Maximazation)

2004년 즈음에 EM 알고리즘에 대해서 발표한 PPT 입니다.
발표 후에 2005년 3월 즈음에 오류를 수정했었습니다.

K-Means 알고리즘과 비교하여 EM 알고리즘을 자세히 소개하려고 했었고,
예제를 사용하여 EM 알고리즘을 쉽게 이해할 수 있도록 준비하였습니다.

파일을 첨부합니다.

위의 파일은 PPT 파일이고, 아래의 파일은 한글로 자세하게 설명한 자료입니다.
( 2003년 데이터마이닝 특론 수업에서 발표 및 제출했던 자료들입니다. )

(1) EM 알고리즘 소개 PPT 파일



(2) EM 알고리즘 자세한 소개 한글 파일

by 에이아이 2009. 8. 1. 10:08
  • 김병균 2012.10.15 14:36 ADDR EDIT/DEL REPLY

    좋은 자료 감사합니다~ 열공할께요~ ^^

  • 로보틱스 2013.02.13 22:17 ADDR EDIT/DEL REPLY

    좋은자료 감사합니다!!

  • 오산돌구 2013.04.18 11:31 신고 ADDR EDIT/DEL REPLY

    정말 감사합니다.
    데이터 마이닝의 기초지식없이 들이대고 있는데, ai-times님의 포스트들이 많은 도움 되고있습니다.
    소개된 Data mining 책도 구해서 읽어봐야겠네요 : )

인공지능의 분류 방법 중 하나인 HMM 에 대해서 설명한 자료를 링크한다.

KISS ILVB Tutorial(한국정보과학회)에서 발표( Dr. Sung-Jung Cho)된 내용 중 발췌된 것이다.

자료보기 : http://blog.daum.net/hazzling/15669927

[내용 중 일부]  

얼마전에 Markov Model에 대해서 주석을 달아서 올렸는데, 이번에는 HMM에 대해서 알아보자
지난번 글에서 언급되었듯이 MM과 HMM의 차이점은 상태(state)를 관측할 수 있는가에 달려있다.
날씨나 동전던지기와 같은 사건(event)에서는 쉽게 상태를 알 수 있지만, 그렇지 않는 사건들도 존재한다.
예를 들어,  아래와 같은 문제가 있다고 하자.
...

 


by 에이아이 2009. 7. 31. 22:09

가장 많이 사용되고 있는 데이터마이닝 툴에 대한 조사 자료입니다.
정확하다고는 할 수 없지만 참고할만 합니다.

http://cafe.daum.net/dmmaster/9ypr/20

2004년도 자료이고 Clementine 이 가장 많이 사용된다고 조사되었습니다.
2009년 현재는 Clementine의 점유율이 훨씬 많이 높아졌을 거라 생각됩니다.

최근 자료를 찾는다면 이 자료에 추가해야겠습니다.
혹시 관련 내용을 알고 계신가요?  

by 에이아이 2009. 7. 29. 21:33
  • HelloDJ? 2010.05.02 03:31 ADDR EDIT/DEL REPLY

    http://www.kdnuggets.com/polls/2009/data-mining-tools-used.htm
    여기에 2009년 자료가 있습니다~_~

  • iguana 2013.04.09 12:30 ADDR EDIT/DEL REPLY

    좋은 참고가 되었습니다. 감사합니다.


의사결정트리 분석 기법

1장. 의사결정트리 분석 소개
2장. ID3 알고리즘
   (1) ID3 알고리즘 소개
   (2) Entropy 계산
   (3) Information 계산
   (4) 알고리즘 구현 소스코드
3장. C4.5 알고리즘
4장. 참고자료 <발췌>

ID3 알고리즘

1. ID3 알고리즘 소개

    ID3 알고리즘은 대표적인 의사결정트리 기반 분류 알고리즘이다. ID3 알고리즘은 1970년대 후반 J. Ross Quinlan 박사에 의해 제안되었다. (대청. CRM위한 데이터마이닝, p.157) 그 이후에 개발된 다양한 의사결정트리 기반의 분류 알고리즘(C4.5, CART, CHAID 등)들도 기본적으로 ID3 알고리즘의 아이디어에 기초하고 있다. 따라서 현재 데이터마이닝 툴에서 지원하고 있는 C4.5(C5.0), CART, CHAID 등의 알고리즘을 이해하기 위해서는 ID3를 먼저 정확해게 이해할 필요가 있다. (ID3 알고리즘은 오래된 방법이므로 배울 필요가 없다고 생각하고, 처음부터 진보된 알고리즘인 C4.5를 공부하는 경우가 있는데, ID3를 이해하지 못한 상태에서 C4.5등의 최근 사용되는 알고리즘을 이해하기는 쉽지않다. 즉, ID3 알고리즘을 알지 못하고서는 C4.5를 이해할 수가 없다.)

   ID3 알고리즘에 관계된 키워드들은 아래와 같다. 알고리즘 과목 또는 인공지능 과목을 수강한 경험이 있다면 익숙한 단어들을 찾을 수 있을 것이다. 본 2장을 자세히 학습하면 ID3 알고리즘이 왜 아래의 키워드들과 관계가 있는지 이해하게 될 것이다.

  ▪ 탐욕 알고리즘 (Greedy Algorithm)
  ▪ Divide & Conquer 방식
  ▪ 귀납적 추론
  ▪ 휴리스틱 (Heuristic) 기법
  ▪ 엔트로피 (Entropy)
  ▪ 정보 이득 (Information Gain)
 
   먼저 간단한 데이터를 가지고 ID3 알고리즘이 어떤 일을 하는 지 살펴보도록 하자. 설명에서 사용할 데이터는 데이터마이닝 및 기계학습 등의 교재에서 예제로 많이 사용되고 있는 유명하고 간단한 데이터이다. 데이터이름은 weather 이다. 간단히 설명하면 어떤 날씨 조건(조망, 온도, 습도 등)에서 경기를 했는지, 안했는지에 대한 정보를 기록한 데이터이다.

   데이터 파일의 형식은 csv 형식의 텍스트 파일이다. 아래의 <그림1>과 같이 메모장으로 열수도 있고, <그림2>와 같이 엑셀 프로그램을 사용해서 열수도 있다. 엑셀 프로그램을 사용한 경우 데이터를 더 잘 이해하며 볼 수 있다. 맨 위의 한줄은 데이터의 각 속성(필드)의 이름이고, 그 아래 14개의 레코드(Record or Instance)가 존재함을 볼 수 있다.

 

 그림1

 

   그림2

   위 데이터를 ID 알고리즘에 적용하면 어떤 결과가 나올까? 우리는 이 데이터를 통해 어떤 날씨가 경기하기에 좋고, 또 어떤 날씨가 경기하기에 안 좋은 날씨인가에 대한 지식을 얻고 싶다. ID3 알고리즘을 지원하는 다양한 데이터마이닝 프로그램들이 있지만, 무료로 공개되어 있는 weka 프로그램을 작성하여 수행한 결과는 아래와 같다.

   그림3

   위 그림이 갖는 의미를 해석해보자. 왼쪽부터 순서로 해석하면 아래와 같은 규칙으로 된 지식들을 얻을 수 있다. 해석하는 방법은 단순하므로 3개 정보만 기록하였다. 물론, 해석결과가 일반적이지 않을 수 있지만 주어진 데이터에서는 적합한 규칙들이다. (아마도 실내 경기장이 아닐까?)
 
 ▪ 날씨가 맑고(outlook=sunny) 습도가 낮으면(humidity=low) 운동을 한다. (play=yes)
 ▪ 날씨가 맑고(outlook=sunny) 습도가 낮으면(humidity=high) 운동을 한다. (play=no)
 ▪ 날씨가 흐리면(outlook=overcast) 운동을 한다. (play=yes)

2. Entropy 계산 방법  

참고 : (1) Data Mining (IAN.H) p.93-94. (2) Concept & Tech(한글판) p.356.

   ID3 알고리즘의 자세한 동작 방법, 절차는 본 장의 마지막에서 설명하기로 하고, 먼저 필요한 수식들을 학습하도록 하자. 본 절에서는 Entropy 개념 및 계산 방법을 학습한다.

   엔트로피(entropy)는 주어진 데이터 집합의 혼잡도를 의미한다. 즉, 주어진 데이터 집합에 레코드들이 서로 다른 종류(클래스)들이 많이 섞여있으면 엔트로피가 높고, 같은 종류(클래스)의 레코드들이 많이 있으면 엔트로피가 낮다. 곧 소개할 엔트로피 계산식에서는 엔트로피 값은 0에서 1사이의 값을 갖는다. 가장 혼잡도가 높은 상태의 값이 1이며, 하나의 클래스로만 구성된 상태의 값이 0이다. 의사결정트리 분류 알고리즘에서는 엔트로피가 높은 상태에서 낮은 상태가 되도록 데이터를 특정 조건을 찾아 나무 모양으로 구분해 나간다.

   그림4

   바로 전 절에서 소개한 그림을 예로 들어 설명해보자. 매 위의 노드(outlook이라고 써있는 노드)의 엔트로피 값이 가장 크며 그 하위의 3개의 노드(outook에 의해 구분된 하위 노드)들의 엔트로피가 더 낮을 것이다. 또 그 하위에 있는 노드들은 부모노드 보다 엔트로피 값이 작을 것이다.

   엔트로피 값은 아래의 식에 의하여 계산된다. 이 식은 주어진 데이터셋 S에 대한 엔트로피 값을 구하는 계산식이다. 엔트로피 값은  즉 각 클래스 값의 포함 비율에 로그를 적용하고 다시 값을 가중치로 곱한 값을 모두 더하는 식이다. log2 함수 적용을 통해 마이너스(-) 값이 나타나므로 전체 수식 값에 - 를 붙여주어 0 에서 1 사이의 값을 갖도록 한다.

 

  위 식에서 는 i번째 클래스 값이 대하여 해당 데이터집합 중에서 차지하는 비율(Probability)을 의미한다. 각 변수들이 갖는 의미는 아래와 같다.

  S : 주어진 데이터들의 집합
 C = {C1, C2, ... , Ck} : 클래스 값들의 집합
 freq(Ci,S) : S에서 class Ci에 속하는 레코드의 수
 |S| : 주어진 데이터들의 집합의 데이터 개수

 
    그러면, 간단한 예를 가지고 엔트로피 값을 계산해보자. 10명의 회원이 있는데 5명이 우수회원, 5명이 일반회원이라고 하자. 그러면, 데이터가 완전히 혼합되어 있으므로 엔트로피 값은 1이 된다. 반면, 10명 모두 일반회원이라면 전혀 혼합되어 있지 않으므로 엔트로피 값은 0 이 된다.

  10명의 회원이 있는데 5명이 우수회원, 5명이 일반회원인 경우 엔트로피 계산식에 적용하면 아래와 같다.

   식?

  
   10명의 회원이 있는데 10명이 우수회원, 0명이 일반회원인 경우 엔트로피 계산식에 적용하면 아래와 같다.

 식?


  이해를 위하여 다른 예를 들어보자. 노드에 데이터가 총 14개 있는데 클래스가 Yes인 레코드가 9개, No인 클래스가 5개 있다고 가정하자. 그러면 아래와 같이 계산할 수 있다.

 

 식?

   물론, 클래스가 2개 이상일 경우에도 같은 방식으로 적용하면 된다. 클래스의 값이 a 또는 b 또는 c의 3가지인 경우는 아래와 같이 계산될 수 있다.

  

 식?

잠깐! 실습문제  

 실습문제 :  데이터셋의 클래스값들을 입력받아 엔트로피 값을 구하는 프로그램을 작성하시오.
 ( 여러 개의 정수들을 입력하고 엔터를 치면 해당 노드의 엔트로피 값을 계산합니다. )

 결과예시 :     Input # of Classes :  5 5
                          Entropy Value :  1.0

                     Input # of Classes :  10 0
                          Entropy Value :   0.0

                     Input # of Classes :  2 3 5
                          Entropy Value :  ??? 

3. Information Gain 계산 방법  

  “정보 이득(information gain)”이란 어떤 속성을 선택함으로 인해서 데이터를 더 잘 구분하게 되는 것을 의미한다. 예를 들어, 학생 데이터에서 수능등급을 구분하는데에 있어 수학 점수가 체육 점수보다 변별력이 더 높다고 하자. 그러면 수학점수 속성이 체육 점수 속성보도 정보이득이 높다라고 말할 수 있다. 정보이득을 계산하기 위해서는 먼저 엔트로피 개념과 계산방법을 이해해야 한다. 따라서, 정보이득 계산방법을 설명하기 전에 엔트로피 계산식을 살펴보기로 하자.

정보 이득의 계산식은 아래와 같다.

   식 ?

   여기서,       , I(s1,s2,...,sm) 은 원래 상위 노드의 엔트로피를 의미한다. 즉, 상위노드의 엔트로피에서 하위노드의 엔트로피를 뺀 것이다. 그리고 E(A)는 A라는 속성을 선택했을 때 하위로 작은 m개의 노드를 나누어진다고 하면 하위 각 노드의 엔트로피를 계산한 후 노드의 속한 레코드의 개수를 가중치로 하여 엔트로피를 평균한 값이다.

  식 Gain(A) 의 의미는 ... 속성 A를 선택했을 때의 정보이득 양을 계산하는 수식으로써 ... 원래 노드의 엔트로피를 구하고 A라고 하고, 속성 A를 선택한 후의 m개의 하위 노드로 나누어진 것에 대한 전체적인 엔트로피를 구한 후 그것을 B라고 하면, A-B를 의미한다. 이 값이 클수록 정보 이득이 큰 것이고 해당 속성 A가 변별력이 좋다는 것을 의미한다.



 그림?

각 노드의 Entropy를 구해보자.

   

 각 노드의 엔트로피를 계산하였으면, 속성 A에 의한 Information 값을 구할 수 있다.

 

잠깐! 실습문제  

 실습문제 :  Weather 데이터에서 [Outlook] 속성을 사용하는 경우 Information Gain을 구하는 프로그램을
 작성하시오.

 결과예시 :     Weahter 데이터에서 Outlook 속성에 대한 Information Gain 값을 계산합니다.

 - 부모노드의 Entropy : 0.940

 - 하위노드( sunny ) Entropy : 0.971    가중치 : 5/14
 - 하위노드(overcast) Entropy : 0        가중치 : 4/14
 - 하위토드( rainy )  Entropy : 0.971    가중치 : 5/14

 - Information Gain :  0.246

4. ID3 알고리즘 정리

 * ID3 알고리즘
1. 전체 데이터를 포함하는 루트 노드를 생성한다.
2. 만약 샘플들이 모두 같은 클래스라면, 노드는 잎이 되고, 해당 클래스로 레이블을 부여한다.
3. 그렇지 않으면 정보이득이 높은(즉, 데이터를 가장 잘 구분할 수 있는) 속성을 선택한다.
   (이때 정보이득은 엔트로피의 변화를 가지고 계산한다.)
4. 선택된 속성으로 가지(Branch)를 뻗어 하위 노드들을 생성한다.
   (각 하위 노드들은 가지의 조건을 만족하는 레코드들이다.)
5. 각 노드에 대해여 2단계로 이동한다.

* 정지조건  
- 해당 노드에 속하는 레코드들이 모두 같은 클래스를 같는다.
- 상위 노드에서 이미 모든 속성들을 다 사용하였다. 더 이상 사용할 속성이 없다.

* ID3의 특징
- 범주형 속성에 대해서만 사용이 가능하다.
  (엔트로피 기반 척도 수식이 범주형 속성에 대해서만 적용이 가능하기 때문에 그렇다.) 
- 상위 노드에서 사용된 속성은 다시 사용하지 않는다.  

5. ID3 알고리즘의 한계 (단점)

- 연속형 (수치형) 속성을 사용할 수 없다.
- 범주형 속성을 전체에 대해서 하위 노드를 생성하기 때문에
  선택된 속성의 범주값이 매우 많을 경우 하위 노드의 가지(branch)의 수가 매우 많아진다.
  예를 들어, 주소가 선택된 경우 매우 잘게 구분되고 해석이 어려워진다.

* 참고자료 (References)

[1] 인공지능의 이해, 생능출판사, 양기철 저, p.204 - 207
[2] MACHINE LEARNING, Tom M. Mitchell, Carnegie Mellong University. (p.52-80, 3장 전체)

* 참고자료 [1]에 발췌

Quinlan이 1986년 제안한 ID3 알고리즘은 학습결과(개념)를 의사결정 트리(Tree) 형태로 표현하며 예를 통한 귀납적 학습을 수행한다. 의사결정 트리는 하향식(Top-Down)으로 생성하며 필요한 정보는 미래 준비되어 있어야 한다. ID3는 루트 노드(Root Node)에서 평가할 특성(Property)을 선택하여 평가 후 자신의 자노드(Child Node)를 생성한다. 각자의 자노드에서 같은 작업이 반복되고 더 이상의 자노드가 생성되지 않을 때까지 반복하여 의사결정 트리를 완성한다.

 ( 위 자료에서 1986년 이라는 연도는 잘못된 듯하다. ID3는 1970년대 발표된 것으로 알려져있다.)

관련파일들


by 에이아이 2009. 7. 29. 19:22
  • kevin 2010.02.02 17:28 ADDR EDIT/DEL REPLY

    많은 도움이 되고있습니다. 그런데 죄송하지만 그림이 뜨지 않습니다. 혹시 확인해 주실수 있을까요?

    • 에이아이 2010.02.02 23:40 신고 EDIT/DEL

      네, 방문해주셔서 감사합니다.^^ 처음에 등록할 때는 잘 보였는데 언제부턴가 그림이 이렇게 안보이네요. 뭔가 실수를 한 듯~ 이번 주엔 외부로 나갈일이 있어서 다음주에 수정하겠습니다.

  • Joo 2010.10.13 14:48 ADDR EDIT/DEL REPLY

    안녕하세요 검색으로 우연히 들어와서 자료보는데 많은 도움이 되고 있습니다! 감사합니다 '_'
    그런데 그림이 안떠요 ㅜㅜ 그림좀 ☞☜ ..

  • IM 2012.03.22 17:19 ADDR EDIT/DEL REPLY

    안녕하세요.
    잘 정리된 자료 공개해주시고 정말 고맙습니다.
    막막하던 차에 정말 도움이 되고 있습니다.
    그런데 위에 그림이 안보이네요.. 그리고 중간중간 식이 좀 틀린거 같습니다.
    예를들어 Entropy(9,4)->Entropy(9,5)인거 같네요.

    • 에이아이 2012.03.31 11:56 신고 EDIT/DEL

      네, 알려주셔서 감사합니다. 시간될 때 수정하겠습니다. 요즘은 블로그에 잘 안들어오다보니 자료도 못올리고 수정도 늦어집니다^^

  • ybh2204 2012.06.11 14:07 ADDR EDIT/DEL REPLY

    좋은 정보 감사드립니다 ㅠ

  • 그라시아 2015.11.09 22:33 ADDR EDIT/DEL REPLY

    관리자의 승인을 기다리고 있는 댓글입니다

| 1 2 3 4 5 6 |