ai-times

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

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

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

[내용 중 일부]  

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

 

본 글에서는 데이터마이닝 프로그램인 웨카(WEKA)를 소개합니다.  데이터마이닝에 대해 설명을 보고 싶다면 아래 링크를 클릭하세요.  데이터마이닝 소개 강좌 => http://ai-times.tistory.com/32

웨카(WEKA) 라는 세계적으로 유명한 데이터마이닝 프로그램을 설명하고자 한다.

만약, 여러분이 인공지능, 데이터마이닝 또는 기계학습(자동학습) 등의 분야를 공부하고 있다면 (아니면 이제 공부를 시작했다면) WEKA 라는 프로그램에 대해 여러차례 들어보았을 것이라 생각된다.

먼저 간단히 이 프로그램을 소개하면, 웨카 프로그램은 뉴질랜드의 와이카토(Waikato) 대학의 '이안 위튼' 교수팀에 의해 개발되어지고 있는 프로그램이다. 

웨카 프로그램이 전세계적으로 유명한 이유

1. 무료 데이터마이닝 프로그램이다.
대부분의 상용 데이터마이닝 프로그램들 (SPSS사의 Clementine, SAS사의 E-Miner 등) 이 설치크기가 매우 크고 가격이 고가이다보니 사용해보기가 쉽지 않은 불편함이 있다. WEKA 는 무료 프로그램이면서 기능 또한 상용프로그램에 뒤쳐지지 않는다. 오히려 더 많은 알고리즘들이 포함되어 있어 연구하는 입장에서는 매우 유용하다. 아래 쪽에 소개한 WEKA 홈페이지에 방문하여 다운로드할 수 있다.

2. 오픈 소스 프로그램이다.
이 프로그램은 오픈 소스 프로그램 (즉, 자바 JAVA 로 된 소스 코드 전체가 공개되어있음) 으로 데이터마이닝 알고리즘을 깊이 이해하고 또 활용하여 자신만의 프로그램을 개발할 경우에 매우 큰 도움이 된다.  
많은 국산 데이터마이닝 프로그램들도 WEKA 소스를 기초로 하여 (참고로 하여) 제작되었다.

3. 아직도 계속 업그레이드되고 있는 프로그램이다.
1999년부터 시작되어 지금까지 꾸준하게 업그레이드되며 개발되고 있는 프로그램이다. 새롭게 연구된 알고리즘들이 추가되고 있어서 최신 기술들을 테스트해볼 수가 있다. 또한 버전이 업그레이드될 수록 시각화 기능도 확장되는 등 기능 및 성능이 발전되고 있다.


왜 이름을 WEKA 라고 지었을까?

그런데 왜 이 데이터마이닝 프로그램의 이름을 weka라고 지었을까? 궁금증이 생겨 사전을 찾아보았다. 영어사전을 찾아보면 “뉴질랜드 산 호주뜸부기 조류(새)”라고 나온다.

참고 : 웨카(weka)는 뉴질랜드에서 자주 볼 수 있는 새의 이름이다. 우리나라에서는 볼 수 없어 말로 설명하기에는 어려울 듯하다. 쉽게 설명하면 뉴질랜드에서 작은 개울을 건너다니는 닭 비슷하게 생긴 새 정도로 설명하면 좀 이해가 갈 것이다. 이해를 돕기 위하여 weka 새의 사진을 추가하였다.

Weka라는 프로그램의 “Waikato Environment for Knowledge Analysis" 의 앞 글자를 따서 지어진 것이다. 이름에서 알 수 있듯이 이 프로그램은 뉴질랜드의 와이카토(Waikato) 대학에서 프로젝트를 수행하여 제작한 것이다.


좀 더 자세한 설명

  weka는 Java 언어로 개발된 데이터마이닝 프로그램이다. 여러 데이터마이닝 프로그램들이 고가이어서 접하기 힘든 것과 달리 weka는 무료로 제공되는 프로그램으로 쉽게 얻을 수 있다. 무엇보다도 weka는 오픈 소스로서 프로그램 전체에 대한 Java 언어로 된 소스코드를 제공하고 있어  데이터마이닝 프로그램을 개발하는 개발자들이 참고하기에 매우 유용한 프로그램이다. 상업용 프로그램이 아니라 연구용으로 제작된 프로그램이기 때문에 사용할 때 약간의 어려움이 느껴질 수도 있다. 무료이지만 여러 유료 프로그램들 보다 오히려 많은 다양한 분석 알고리즘들을 제공하고 있고, 시각적 분석 기능도 뛰어나 데이터분석에 유용하게 사용될 수 있는 프로그램이다.

   weka 프로그램은 [Weka Machine Learning Project] 프로젝트를 통해 개발되어졌고 지금도 계속 기능이 추가 및 개선되고 있다. 1999년 경 부터 프로젝트가 시작되었고, 2008년 10월 현재 3.5.8 버전 까지 개발되어 발표된 상태이다.


WEKA 프로그램 홈페이지 (웹사이트)

   weka 프로그램은 [Weka Machine Learning Project] 라는 이름의 프로젝트로 꾸준하게 연구 개발되어지고 있다. 프로젝트 홈페이지( http://www.cs.waikato.ac.nz/ml/weka/ )에 방문하면 weka에 대한 자세한 정보들을 찾아 볼 수 있다.

추가적인 WEKA 프로그램 강좌

만약, WEKA 프로그램을 다운로드 받고 설치하는 방법이 궁금하다면 여기 를 클릭하라.

WEKA 프로그램을 사용하는 방법이 알고싶다면 여기 를 클릭하라.
WEKA 에서 기본적으로 지원하는 IRIS 데이터에 대하여 C4.5(J48)을 수행하는 과정을 설명하였다.

자료설명

본 자료에서는 See5.0/C5.0 이라는 결정트리 프로그램을 소개합니다.
결정트리를 지원하는 데이터마이닝 상용 프로그램들은 이미 많이 출시되어 있습니다. SPSS의Clementine, SAS의 E-Miner 그 외에도 수많은 프로그램들이 있지만, 상용 프로그램이고 크기가 크다 보니 프로그램을 준비하여 설치하고 테스트해보기가 쉽지 않습니다. 

본 자료에서는 간단하게 설치하고 결정트리를 수행할 수 있는 See5.0/C5.0 프로그램의 다운로드 방법, 설치방법, 사용방법 등을 설명합니다. 이 프로그램도 상용(유료) 프로그램이지만 인터넷을 통하여 평가용 프로그램을 쉽게 다운로드 할 수 있고, 사용법도 단순한 편입니다. 

다운로드 방법

제작사인 RuleQuest 사의 홈페이지에 방문하여 프로그램을 다운로드 할 수 있습니다.
(홈페이지 : http://www.rulequest.com/ )

화면의 우측에 보면 이 회사에서 제작 판매하는 몇 개의 데이터마이닝 프로그램 리스트가 보입니다.
해당 제품을 클릭하면 프로그램의 설명이 나옵니다. 설명의 하단에 보면 downloads 라는 내용이 있는데 클릭하여 해당 제품을 다운로드 할 수 있습니다.

See5.0/C5.0 (제품설명)
Cubist 2.06 (제품설명)
BritBot 2.01 (제품설명)
ODBCHook 1.01a (제품설명)
 
프로그램 다운로드 링크를 별도로 연결하였습니다. 또는 링크가 연결되지 않는 경우 (2)의 파일을 직접 다운로드 하세요. 

(1) 홈페이지통해서 다운로드하기 
(2) 아래의 파일을 클릭 (628 kbyte의 크기로 1 Mbyte 도 안되는 작은 크기임)

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

참고자료: Machine Learning p.66 (issues in decision tree learning)

Chapter 3. < C4.5 알고리즘 >

ID3 알고리즘의 단점을 보완하고 새로운 기능을 추가한 알고리즘이다. 수치형속성 처리, 결측치  처리, 속성선택 시 Branch의 수에 대한 가중치 적용, 가지치기(Pruning) 등의 기능을 추가하였다. 기본적인 개념은 ID3와 동일하다. 따라서 C4.5를 이해하려면 ID3의 동작원리를 자세히 이해하고 그 후에 보완된 기능들을 학습해야 한다.

1. C4.5 알고리즘 소개

   이번 장에서는 C4.5 라는 분류 알고리즘에 대해서 설명하고자 한다. C4.5 알고리즘은 1993년 Quinlan 에 의해 제안되었다. C4.5 알고리즘은 ID3 알고리즘과 크게 다르지 않다. ID3 알고리즘과 다른 어떤 더 좋은 알고리즘이라고 하기 보다는 ID3 알고리즘의 몇 가지 단점(한계)들을 보완한 알고리즘이라고 이해해는 것이 정확하다.

  앞에서 설명한 ID3 알고리즘은 트리 기반의 분류 알고리즘에 있어 대표적인 알고리즘이다. 이 알고리즘은 몇 가지 점에서 단점을 가지고 있다. ID3가 갖고 있는 한계점을 들을 보완한 알고리즘이 C4.5 알고리즘이다.

* C4.5 알고리즘들이 보완하고자 한 ID3 알고리즘의 문제들은 아래와 같다.

(a) 수치형 속성 취급 (handling continuous attributes)
   ID3 알고리즘은 범주형 속성에 대해서만 트리를 생성하는 방법을 제시하고 있다. 따라서 수치형 속성은 모델 생성에 활용할 수 없는 한계가 있다. C4.5에서는 수치형 속성까지 사용하는 방법에 대해서 제안한다.

(b) 무의미한 속성을 제외하는 문제
   학번, 생일, 번지수(세부주소)등과 같이 모든 레코드를 잘게 분할하는 (극단적으로는 한 개의 속성으로 구분하는) 속성이 선택되지 않도록 하는 것이 필요하다.

(b) 나무의 깊이 문제 (how deeply to grow the decision tree)
   ID3 알고리즘으로 나무 모델을 생성할 경우 나무의 깊이가 너무 깊게 들어가는 문제가 있다. C4.5 알고리즘에서는 이 문제를 해결하기 위해 깊이를 어느 정도까지 진행할 것인가에 대하여 제안한다. 이것은 “과적합(overfitting) 문제” 및 “가지치기(pruning)”와 관련이 있다.

(c) 결측치 처리 (Handling missing attributes values)
   데이터 중 특정 속성의 값이 부분적으로 입력되어 있지 않는 데이터에 대한 처리 문제

(d) 비용고려 (handling attributes with different costs)
   속성들을 서로 다른 가중치를 반영하여 사용하는 방법

(e) 효율성 (Improving computational efficiency)
   시행되는 시간적인 효율성을 높이는 방법

2. C4.5 에서 수치형 속성을 처리하는 방법

참고1: Data Mining (IAN H.WITTEN, EIBE FRANK) p.159-161 (6.1절 Numeric Attr.)
참고2: Machine Learning p.72 중반 p.73

   전에 설명했던 ID3 알고리즘은 모든 속성이 명목형(Nominal) 속성일 경우에만 처리가 가능하였다. (명목형 속성은 범주형 속성<Categorical Attribute)과 같은 의미로 볼 수 있다.) 그러나 실세계의 데이터들은 대부분 수치형 속성들을 포함하고 있다. ID3 알고리즘에 수치형 속성을 처리할 수 있도록 확장하는 것이 필요하다. 이 작업은 그렇게 어려운 것은 아니다. 수치형 속성에 대하여 우리는 binary 방식과 Split 방식의 두 가지 방식을 고려할 수 있다. Table1.3과 같이 수치형 속성을 갖고 있는 Weather 데이터에 대하여 분석을 하는 경우를 고려해보자. 먼저 온도(Temperature)에 대한 분할을 고려해보자. 온도는 아래와 같이 표현될 수 있다. (클래스 값과 같이 표현하였다.) (위 그림에서 72, 75의 경우 클래스 값이 두 개가 기록된 것은 같은 온도 값에 대한 레코드가 2개로 중복된 경우이다.)

64	65	68	69	70	71	72	75	80	81	83	85
yes	no	yes	yes	yes	no	no yes	yes yes	no	yes	yes	no

   위 표에서 보면 분할할 수 있는 Breakpoint는 11개가 존재한다. 만약 같은 클래스에 대해서 분할을 허용하지 않는다면 8개의 가능한 분할지점(Breakpoint)이 있다. 각 분할지점에 대한 Information Gain 값을 이전에 배운 Entropy 식에 의해 계산될 수 있다.

    예를 들어, [온도 < 71.5] 를 기준으로 하면 4개의 yes와 2개의 no가 포함된다. 반면 [온도 > 71.5] 에 대해서는 5개의 yes와 3개의 no가 포함된다. 따라서 Information value는 아래와 같이 계산된다. (아래와 같이 71.5도를 분할점으로 한 온도라는 속성을 기준으로 분할하면 0.939의 Info Gain 값을 얻는다.) 

Info( [4,2], [5,3] ) = (6/14)*Info([4,2]) + (8/14)*(info[5,3]) = 0.939 bits.

   더 복잡한 아이디어를 사용하면 더 좋은 info gain을 얻을 수도 있겠지만, (위와 같은 방식으로 Info가 가장 낮은 분할지점을 찾아서) 특정 값을 찾아서 그 값을 기준으로 하여 분할하는 단순한 방법을 일반적으로 많이 사용한다. 예를 들어, 인스턴스기반 학습에서 개념의 중간지점을 분할점으로 선택하는 단순한 방식이 ---
 
   분할정복 방식을 사용하여 의사결정트리를 생성할 때, 분할을 위한 첫 번째 속성이 선택되면 그 속성에 의하여 하위노드들로 분리하고 각 하위 자식노드들에 대하여 재귀적으로 알고리즘을 호출한다. 수치형 속성에 대해서는 각 노드의 레코드들을 수치형 속성의 값에 따라 정렬하여야 한다. 실제로 의사결정트리를 생성하는 프로그램들이 이러한 방식을 사용한다. 그러나 사실은 각 노드별로 다시 정렬해야할 필요가 없다. 왜냐하면 상위노드에서 정렬된 순서는 하위 노드에서도 그대로 사용될 수 있기 때문이다. 빠른 프로그램의 구현을 위해서는 상위 노드의 정렬 정보를 사용하면 된다. Weather 데이터 분석에서 Temperature(온도) 속성에 대하여 고려해보자. 온도 속성의 정렬 순서는 아래와 같다. (이번에는 중복된 경우를 모두 포함하고 있다.)

64	65	68	69	70	71	72	72	75	75	80	81	83	85
7	6	5	9	4	14	8	12	10	11	2	13	3	1

   위 그림에서 아래의 기울임체로 기록된 숫자는 각 인스턴스들의 번호를 의미한다. 즉, 인스턴스 7의 온도는 64도이고, 인스턴스 6의 온도는 65도 이다. (앞에서부터 순서대로 설명한 것임) 우리가 최 상위노드에서 outlook 이라는 속성을 분할을 위하여 선택했다고 가정해보자. 자식 노드들 중에서 outlook=sunny 인 경우에 해당하는 노드를 고려해보자. outlook이 sunny 값을 갖는 인스턴스들의 번호는 1, 2, 8, 9 그리고 11이다. (즉 5개의 인스턴스가 노드에 포함됨)

상위노드에서 생성된 순서를 사용하여 하위 노드의 순서를 찾을 수 있다.

9

8

11

2

1

   따라서, 각 수치형 속성에 대하여 반복적인 정렬은 하지 않아도 된다. 각 수치형 속성의 순서는 처음의 상위 노드(루트노드)에서 결정되므로 하위 노드에서 더 이상의 정렬을 필요하지 않다.

   4.3절에서 설명한 것 같이 의사결정트리는 명목형(범주형) 속성을 테스트 할 때, 각 분할되는 가지(branch)는 속성이 갖는 값들의 개수만큼 펼쳐지게 된다. 그러나 수치형 속성에 대해서는 하나의 breakpoint 값을 기준으로하여  2개의 branch를 펼치게 된다. 이러한 방식(수치형 속성에 대해서 2개의 가지를 평치는 방식)은 명목형 속성과 수치형 속성을 처리하는 면에서 중요한 차이점을 발생시키게 된다. 명목형 속성에 대해서는 상위노드에서 선택되었다면 하위 노드에서는 다시 고려할 필요가 없다. (즉, 다시 선택되지 않는다.)  반면에 수치형 속성에 대해서는 같은 속성에 대해서도 계속적인 분할이 발생할 수 있다. 명목형 속성은 루트노드로부터 해서 단 한번만 선택될 수 있지만, 수치형 속성의 경우 여러 차례 (하위노드에서) 테스트될 수 있다. 이러한 방식으로 생성된 트리는 복잡하고 이해하기 어려울 수 있다. 왜냐하면 하나의 수치형 속성에 대한 기준이 한꺼번에 나타나지 않고, path에 걸쳐서 분산되어 나타나기 때문이다. 이러한 문제를 개선한 만들기는 어렵지만 이해하기 좋은 트리를 생성하기 위해서는 상위노드로부터 여러 개의 기준값을 선정하여 다중 분할하는 multiway ( <-> binary-way) 테스트를 사용한다. 이 외에, 성능은 조금 떨어지지만 단순한 방식인 이산화 방식을 7.2절에서 설명한다.

정리 * 수치형 데이터에 대해서는 binary 분할 방식을 사용한다. (다중 분할 보다는) * binary 분할에서는 하나의 breakpoint를 찾아야 한다. * 가능한 모든 값에 대하여 breakpoint를 설정하고 Info 값을 계산해 본다. (시간이 많이 걸림)   가장 좋은 (info가 가장 작은 분할 값을 선택한다.) * 범주형 속성의 경우는 하나의 path에서 한번만 사용되지만, 반면에 수치형 속성은 여러차례   나타날 수 있다. 흩어져서 속성이 나타나므로 트리의 모양이 복잡하고 이해하기 어려울 수 있다. * 따라서, 이에 대한 보완책으로 다중 분할 방식을 사용할 수 도 있다. * 미리 수치형 값을 이산화 처리하여 사용하는 방식도 있다. * (정렬하는 방법에 대해서 많은 부분을 할애하고 있으나 많이 중요한 부분은 아닌 것 같다. 구현시   시간을 줄여주는 방법이며 핵심적인 아이디어는 아니다.)

그림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명이 일반회원인 경우 엔트로피 계산식에 적용하면 아래와 같다.

식1

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

식2

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

식3

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

식?

3. Information Gain 계산 방법  

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

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

식 5

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

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

그림 5

각 노드의 Entropy를 구해보자.

그림 6

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

 * 참고자료 (References)

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

[3] C4.5 알고리즘을 소개하는 논문 ( http://ai-times.tistory.com/173 )

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

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

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

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

의사결정트리 분석 기법 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년대 발표된 것으로 알려져있다.)

관련파일들

CHAID 알고리즘 소개

나무를 구축하는 방식이 CART 와 흡사하나 데이터를 분할하는 방식에 차이가 있다.

다시 말해, 최적의 분할, 즉 최적의 예측변수를 선택하는데 있어 엔트로피나 지니 매트릭스 대신
통계학의 카이스퀘어 테스트를 사용한다.

따라서 이 방법은 범주형 자료에 대해서만 적용할 수 있다.
수치형 속성(나이 등) 범주형으로 변환한 후에 입력해야 한다. (10대, 20대, ... 등) 

< CHAID > : Chi-squared Automatic Interaction Detection (1980, KASS)  CHAID 알고리즘은 Chi-suare검정 또는 F-검정을 이용하여 데이터를 분리하는 방법을 사용한다. (범주형의 속성에 대해서는 Chi-squre검정을 사용하고, 연속형 변수에 대해서는 F-검정을 사용한다.) 참고자료 : 사례로 배우는 데이터마이닝 [자유아카데미, 최종후/소선하] p.27

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

2.1 CHAID(Chi-square Automatic Interaction Detection)

1975년 J.A. Hatigan에 의해 처음 발표된 CHAID 알고리즘은 카이제곱-검정 (이산형 목표변수) 또는 F-검정 (연속형 목표변수)을 이용하여 다지분리(Multiway Split)를 수행하는 알고리즘으로 1963년 J.A.Morgan과 J.N.Sonquist이 발표한 AID (Automatic Interaction Detection) 시스템에서 유래되었다. AID 에서 암시하고 있는 것과 같이 CHAID는 원래 변수들 간의 통계적 관계를 찾는 것이 그 목적이었다. 변수들 간의 통계적인 관계는 다시 의사결정트리를 통해 표현될 수 있었으므로, 이 방법은 분류기법(Classification Technique)으로써 사용할 수 있다[Thearling, 1995].
계속...

CART 알고리즘은

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

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

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

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

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

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

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

2.2 CART(Classification And Regression Tree)

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

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

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

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

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

K-Means 알고리즘을 소개한 PPT 자료입니다.

예제를 사용하여 알고리즘의 절차를 쉽게 이해할 수 있도록 작성하였습니다.
(EM 알고리즘 소개 자료의 앞부분 내용과 동일합니다.)

파일을 첨부합니다.

아래는 작성한 소스코드 입니다. 참고하세요. 

package xminer.mining.clustering; import xminer.core.*; import java.util.Random; public class KMeans {   Dataset m_dataset;   int m_clusterSize;   int m_maxIteration;   int m_recordCount;   int m_fieldCount;   int m_recordClusterIndex[];   // 각 레코드에 대하여 소속 군집번호   int m_clusterCount[];            // 각 클러스터별 소속 개수   Record m_cetroids[];   public KMeans(Dataset ds, int clusterSize, int maxIteration) {     m_dataset = ds;     this.m_clusterSize = clusterSize;     this.m_maxIteration = maxIteration;     this.m_recordCount = ds.getRecordCount();     this.m_fieldCount = ds.getAttrCount();     this.m_recordClusterIndex = new int[ ds.getRecordCount() ];     this.m_cetroids = new Record[ this.m_clusterSize ];     this.m_clusterCount = new int[ this.m_clusterSize ];   }   public void learn(){     // 초기 랜덤 시드 결정     int i=0;     init_centroid();     this.print_centroid();     while(true){       //System.out.println( i + "번재 수행결과");       reAssign_Step();       findNewCentroid_Step();       // System.out.println();       // this.print_centroid();       // this.print_state();       // 최대반복횟수에 의한 학습 종료       i++;       if( i >= this.m_maxIteration){         System.out.println("최대반복횟수에 도달하여 종료합니다. 반복횟수 : " + i);         break;       }       // 중심점(Centroid)의 고정에 의한 학습 종료       // -- 새로운 중심점의 계산       // -- 이전 중심점과의 차이를 계산       // -- 만약 중심점의 변화가 없으면 끝     }     System.out.println( i + "번재 수행결과");     System.out.println();     this.print_centroid();     this.print_state();   }   /**    * 초기에 클러스터 개수만큼의 레코드를 선택하여 이들을 초기 군집 중심으로 합니다.    * 이때 같은 레코드가 중복해서 다른 군집의 중심점이 되지 않도록 합니다.    */   public void init_centroid(){     Random random = new Random();     for(int c=0; c<this.m_clusterSize; c++){       this.m_cetroids[c] = this.m_dataset.getRecord( random.nextInt(m_recordCount-1)).copy();     }   }   /**    * 군집의 중심을 새롭게 계산합니다.    * 모든 레코드의 소속값을 고려하여 평균값을 정합니다.    */   public void findNewCentroid_Step(){     // 초기화     for(int c=0; c<this.m_clusterSize; c++){       this.m_clusterCount[c] = 0;       for(int f=0; f<this.m_fieldCount; f++){        this.m_cetroids[c].add(f, 0.0);       }     }     int c_num;     // 클러스터별 소속 레코드 개수를 계산합니다.     for(int r=0; r<this.m_recordCount; r++){       c_num = this.m_recordClusterIndex[r];       this.m_clusterCount[c_num]++;     }     // 클러스터별 중심을 계산합니다.     for(int r=0; r<this.m_recordCount; r++){       c_num = this.m_recordClusterIndex[r];       Record record = this.m_dataset.getRecord(r).copy();       for(int f=0; f<this.m_fieldCount; f++){        this.m_cetroids[c_num].addOnPrevValue(f, record.getValue(f));       }     }     for(int c=0; c<this.m_clusterSize; c++){       //System.out.println("군집 " + c + "의 개수 : "  + this.m_clusterCount[c]);       this.m_cetroids[c].multiply( 1.0/(double)this.m_clusterCount[c] );     }   }   /**    * 주어진 중심에 대하여 모든 레코드들을 지정(Assign)합니다.    * 레코드와 각 군집중심과의 거리를 계산해보고 가장 거리가 가까운 군집에 지정합니다.    */   public void reAssign_Step(){     int c_num;     double min_dist = Double.POSITIVE_INFINITY;     double distance;     for(int r=0; r<this.m_recordCount; r++){       Record record = this.m_dataset.getRecord(r).copy();       c_num = 0;       min_dist = 10000; //Double.POSITIVE_INFINITY;       for(int c=0; c<this.m_clusterSize; c++){         distance = this.m_dataset.getDistanceOfUclideanP(record, this.m_cetroids[c]);         // 해당 레코드와 군집중심과의 거리를 계산합니다.         if(distance < min_dist){ // 최소           min_dist = distance;           c_num = c;         }       }       this.m_recordClusterIndex[r] = c_num;     }   }   /**    * 현재 중심점(Centroid)의 값을 출력합니다.    */   public void print_centroid() {     for (int c = 0; c < this.m_clusterSize; c++) {       System.out.println("군집[" + (c) + "]의 중심점 : " +  this.m_cetroids[c].toString());     }   }   public void print_state(){     for(int r=0; r<this.m_recordCount; r++){       System.out.print("번호 "+ (r+1) + " : " );       for(int f=0; f<this.m_fieldCount; f++){         System.out.print( this.m_dataset.getRecord(r).getValue(f) + ", " );       }       System.out.println( this.m_recordClusterIndex[r] );     }   }   public static void main(String[] args) {     // 아이리스 원본 데이터     Dataset ds = new Dataset("아이리스","D:\\ai-miner-test-data\\iris.csv",                          Dataset.FIRSTLINE_ATTR_NO_INFO, true);     // 수치 필드만 있는 아이리스 데이터     // Dataset ds = new Dataset("D:\\work\\(01) (입력모듈) Dataset\\datafile\\iris_4.csv",                            Dataset.HAS_NOT_FIELD_NAME_LINE);     ds.printDataInfo();     KMeans km = new KMeans(ds, 3, 200); // 3개 군집, 최대 10번 반복, 종료변화값 0.01     km.learn();   } }

더 참고할 만한 사이트

[1] http://adeuxist.egloos.com/971452

공유하기 게시글 관리 구독하기ai-times '스터디 자료' 카테고리의 다른 글 [강좌] CHAID 결정트리 정리  (1) 2009.07.29 [강좌] CART 알고리즘 정리  (1) 2009.07.29 협력적 여과를 이용한 개인화 추천 (CF: Collaborative Filtering)  (0) 2009.07.29 [강좌] SPSS 사용하여 데이터의 다중공선성 진단하기  (12) 2009.07.27 SPSS를 이용한 요인분석 결과의 해석  (37) 2009.07.27 by 에이아이 2009. 7. 29. 18:57 글 협력적 여과를 이용한 개인화 추천 (CF: Collaborative Filtering) 스터디 자료 설정 협력적 여과 개념을 이용한 개인화 추천 방법 소개 자료립니다. CF 알고리즘은 개인화 추천을 위해 매우 널리 사용되고 있는 알고리즘입니다. 2006년 1월 세미나 강의를 위해 준비한 자료입니다. 예제를 사용하여 개념 및 절차를 쉽게 이해할 수 있도록 작성하였습니다. 아래에 파일을 첨부하였습니다. invalid-file   추가로 Youtube 에 공개된 CF 관련 강의 동영상을 추가하니 참고하세요. 공유하기 게시글 관리 구독하기ai-times '스터디 자료' 카테고리의 다른 글 [강좌] CART 알고리즘 정리  (1) 2009.07.29 K-Means (K-평균) 군집 알고리즘 소개  (2) 2009.07.29 [강좌] SPSS 사용하여 데이터의 다중공선성 진단하기  (12) 2009.07.27 SPSS를 이용한 요인분석 결과의 해석  (37) 2009.07.27 SPSS를 이용한 요인분석(Factor Analysis) 수행  (8) 2009.07.24 by 에이아이 2009. 7. 29. 18:39 PREV | 1 ··· 20 21 22 23 24 25 26 ··· 31 | NEXT 사이드 메뉴 나의 키워드 - 인공지능, 통계학, 데이터마이닝 ... CATEGORY 분류 전체보기 (307) My Room (0) Do-List (0) My Account (0) 즐겨찾기 사이트 (0) 맛집 (0) 숭실대학교 관련 (0) 강의 관리 (0) 발표논문 (0) 참고논문 (12) 항목 (1) 참고논문전체 (11) 스터디 자료 (53) 인공지능 (1) 패턴인식 (1) 기계학습 (1) 의사결정트리 (1) 신경망 (1) 데이터마이닝 (1) 마이닝 실험 데이터 (1) WEKA (웨카) 정보 (1) 통계분석 (1) Hobby : 탁구 (11) 탁구 초보 강좌 (3) 탁구 빅매치 동영상 (4) 탁구 관련 사이트 (0) Hobby : 유머 (95) 유용한 자료 모음 (17) CCM Songs (8) 유용한 사이트 (1) 유용한 프로그램 (6) 블로그 운영 방법 (0) 구글 에드센스 (0) SPSS 활용 강좌 (1) AMOS 활용 강좌 (0) Excel 활용 강좌 (1) 저널/학회/세미나 (1) JAVA 프로그래밍 (0) 추천 사이트 (1) 컴퓨터공학 자료 (2) JSP 웹사이트 (1) C언어 및 C++ (0) 알고리즘 (1) 자료구조 (0) 이산수학 (0) IT 뉴스 (3) 연구하는 내용 (8) 발표한 연구 (2) 진행중인 연구 (0) 참고논문 (4) TAG 요인분석 결정트리 WEKA 데이터마이닝 C4.5 SPSS 유머 웨카 RECENT POSTS RECENT COMMENT ARCHIVE NOTICE MY LINK 데이터마이닝 블로그. 에이아이타임즈. 텍스트큐브 블로그. 논문_컴퓨터연구정보센터. 인포마스터. 좋은글 유머모음. 무한감사TV. 61.250.91.197. CALENDAR 이전 달의 달력을 보여줍니다. 2024.5 다음 달의 달력을 보여줍니다. 포스팅달력 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 COUNTER TOTAL TODAY 지역로그 : 태그 : 방명록 : 관리자 : 쓰기 에이아이's Blog is powered by Daum & Tattertools / Designed by Tistory 티스토리툴바