ai-times

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

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

교재의 강의교안 PPT 자료입니다.  아래의 파일을 클릭하면 다운로드할 수 있습니다. invalid-file

각 장별 내용입니다.

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

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

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

   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

			 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

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

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

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

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

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

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

CART

본 글에서는 데이터마이닝 공개 프로그램으로 유명한 웨카 프로그램을 인터넷에서 다운로드 받고 설치하는 방법을 설명합니다. 기본적으로 프로그램을 설치하고 실행하면 에러가 발생하는데 이것을 해결하는 방법도 설명하였습니다. 

Weka 홈페이지 소개 

웨카(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 설치하고 실행하기   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Weka 시작하기

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

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

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

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

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

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

ARFF 형식은 왼쪽 그림과 같이 @relation, @attribute, @data 의 3개의 영역으로 표현된다. 각 내용은 아래와 같이 입력한다. @relation 데이터명칭 @attribute 속성이름 {범주형의 값 리스트 } 본 데이터셋은 5개의 범주형 속성으로 구성되었다. @data 하단에 한 줄에 하나의 레코드(인스턴스)를 기록함. 본 데이터셋은 14개의 레코드가 입력되었다.

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

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

위에서 설명한 바와 같이 @attribute 라인을 통해 각 속성에 대한 정보를 기록한다. 이 때, 범주형 속성과 수치형 속성을 구분하여 기록해주어야 한다. (1) 범주형 속성 @attribute 속성이름 {범주형의 값 리스트 } 본 데이터셋은 5개의 범주형 속성으로 구성되었다. (2) 수치형 속성 @attribute 속성이름 real 즉, 수치형 속성은 속성의 이름을 적어 준 후, 뒤에 real 이라고만 기록해주면 된다. 범주형 속성의 경우 값을 모두 적어주지만, 수치형은 간단하다.

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

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

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

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

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

EM 알고리즘 소개 (Expectation Maximazation)

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

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

파일을 첨부합니다.

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

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

invalid-file

invalid-file

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

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

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

[내용 중 일부]  

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

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

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

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

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)을 의미한다. 각 변수들이 갖는 의미는 아래와 같다.

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

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

식?

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

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

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

잠깐! 실습문제  

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 값을 구할 수 있다.

잠깐! 실습문제  

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장 전체)

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

관련파일들

chap9_ai_20090628.ppt

chapter9-2_ID3_20090628.ppt

InformationTheory_mrMoon_20090628.pdf