2008. 04. 17 데이터 마이닝 연구실 윤언근. □ 결정트리 □ 연관규칙 □ K-Means 알고리즘 □ 유전자 학습 □ 데이터 마이닝 기법의 선택.

Presentation on theme: "2008. 04. 17 데이터 마이닝 연구실 윤언근. □ 결정트리 □ 연관규칙 □ K-Means 알고리즘 □ 유전자 학습 □ 데이터 마이닝 기법의 선택."— Presentation transcript:

1 2008. 04. 17 데이터 마이닝 연구실 윤언근

2 □ 결정트리 □ 연관규칙 □ K-Means 알고리즘 □ 유전자 학습 □ 데이터 마이닝 기법의 선택

3 1 단계 : K 값, 만들어질 클러스터의 개수 정함. 2 단계 : 데이터 집합에서 무작위로 k 개의 인스턴스 골라 클러스터 의 초기값으로 정함 3 단계 : 나머지 인스턴스들은 Euclidean distance 를 사용하여 가 장 가까운 센터를 가진 클러스터에 배정 4 단계 : 각 클러스터마다 그 안에 배정된 모든 인스턴스의 평균 값 을 구하여 그것을 그 클러스터에 대한 새로운 센터로 지정 5 단계 : 새로운 센터값들이 이전 센터 값들과 같다면 알고르즘은 종료되고 그렇지 않으면, 그 새로운 센터 값으로 단계 3-5 를 반복함. □ K-Means 알고리즘은 간단하면서 매우 효과적인 통계적 클러스터링 기법이다. K-Means 알고리즘은 아래와 같다.

4 Instancexy 123456123456 1.0 2.0 3.0 5.0 1.5 4.5 1.5 3.5 2.5 6.0 표 3.6] K-Means 입력값 그림 3.6] 표 3.6 에 있는 데이터의 좌표 매핑

5 표 3.6 을 이용한 K-Means 알고리즘을 이용하여 클러스터 센터를 구하는 과정입니다. 1 단계 : 두개의 클러스터가 있다고 가정하고 K 값을 2 로 정한다. 2 단계 : 표 3.6 의 인스턴스 1 과 3 을 골라서 두개의 클러스터 센터로 정한다. 3 단계 : 나머지 인스턴스들을 두 개의 클러스터 중 하나로 분류하는 단계이다. Euclidean distance 거리 함수 사용 ※(x1,y1) 과 (x2,y2) 의 좌표를 가지는 A 와 B 간의 Euclidean distance 는 Distance(A - B) = √(x1 - x2)²+(y1 - y2)²

6 3-1 단계 : 첫번째 iteration 에서는 c1 = (1.0, 1.5) 과 c2 = (2.0, 1.5) 로 시작 한다. Distance(C1 - 1) = 0.00 Distance(C1 - 2) = 3.00 Distance(C1 - 3) = 1.00 Distance(C1 - 4) = 2.24 Distance(C1 - 5) = 2.24 Distance(C1 - 6) = 6.02 Distance(C2 - 1) = 1.00 Distance(C2 - 2) = 3.16 Distance(C2 - 3) = 0.00 Distance(C2 - 4) = 2.00 Distance(C2 - 5) = 1.41 Distance(C2 - 6) = 5.41 표 3.7 Euclidean distance 계산 3-2 단계 : 첫번째 iteration 후에는 클러스터링은 다음과 같이 정해진다. C1 은 인스턴스 1 과 2 를 가진다. C2 는 인스턴스 3,4,5,6 을 가진다.

7 3-3 단계 : 각 클러스터 센터를 다시 계산한다. C1 X(1.0+1.0) / 2 = 1.0 Y(1.5+4.5) / 23.0 C2 X(2.0+2.0+3.0+5.0) / 4 = 3.0 Y(1.5+3.5+2.5+6.0) / 4 = 3.375 표 3.8] C1 과 C2 의 새로운 센터 좌표 4 단계 : 새로운 클러스터 센터가 C1 = (1.0, 3.0) C2 = (3.0, 3.375) 로 변경 되었으므로 두 번째 iteration 을 수행한다.

8 OutcomeCluster CentersCluster PointsSquared Error 1 (2.67, 4.67)2,4,6 14.50 (2.00, 1.83)1,3,5 2 (1.5, 1.5)1,3 15.94 (2.75, 4.125)2,4,5,6 3 (1.8, 2.7)1,2,3,4,5 9.60 (5,6)6 표 3.9] k = 2 일때 K-Means 알고리즘 적용의 다양한 결과 그림 3.7] K = 2 일때 표 3.6 에 있는 데이터에 대한 K-Means 클러스터링

9 첫 번째 iteration 두 번째 iteration 네 번째 iteration 세 번째 iteration iteration 인스턴스 평균 1 C11,2C1(1.0, 3.0) C23,4,5,6C2(3.0, 3.375) 2 C11,2,3C1(1.33, 2.50) C24,5,6C2(3.33, 4.00) 3 C11,2,3,4C1(1.5, 2.75) C25,6C2(4, 4.25) 4 C11,2,3,4,5C1(1.8, 2.7) C26 (5, 6) 5 C11,2,3,4,5C1(1.8, 2.7) C26 (5, 6) 표 3.10] 표 3.9 의 Outcome = 3 일때 클러스터 센터 계산 단계 C1 의 인스턴스 C2 의 인스턴스

10 1 단계 : 염색체라고 부르는 n 개의 개체로 이루어진 개체군 P 를 초기화한다. 2 단계 : 주어진 종료 조건이 만족될 때까지 다음을 계속한다. a : 현재 solution 의 각 개체를 적합도 함수로 평가하여 개체가 적합 기준을 만족하면 그 개체군에 남아 있는다. b : 그 개체군은 이제 m 개의 개체를 갖게 되고, 유전자 연산자를 사용하여 나머지 (n-m) 개의 새로운 개체를 만든다. □ 유전적 지식을 표현하는 일반적인 방법은 개체들을 이진 부호로 변환하는 것 이다. - ex) income range 항목의 20-30K 을 ‘00’ 2 비트의 부호열로 만들 수 있다. □ 유전자 알고리즘 (Genetic Algorithm, GA) 은 적자 생존과 유전의 메카니즘을 바탕으로 하는 탐색 알고리즘이다. 다시 말해 주어진 환경에 잘 적응하는 유전자 만을 선택하고 교차하고 때에 따라서는 돌연변이도 하며 다음 세대에 우수한 유 전 형질이 전달되게 된다. 따라서 진화가 거듭될수록 주어진 환경에 더 적합한 유전자들만이 남아있게 될 것이다. 유전적 알고리즘은 다음과 같다.

11 □ 유전 연산자 ■ 교차 현재의 개체군에 있는 두 개의 개체들의 일부분을 합쳐서 새로운 개체를 만들어 내는 것. ■ 돌연변이 제거될 후보 개체들에 일부 사용되며 하나의 개체에 무작위 변이에 적용 된다. ■ 선택 높은 적합도 점수를 가진 개체들이 개체군에서 지워진 개체를 대신에 들 어 간다.

12 개체군 □ 유전자 알고리즘과 Supervised 학습 Training 데이터 교차와 돌연변이 연산을 위한 후보자들 1 단계 : 개체군 P 초기화. 2 단계 : 적합도 함수를 적 용하여 현재 개체군에 있 는 각 개체를 평가하여 적 합도 값이 낮은 개체를 삭 제. 3 단계 : 단계 2 에서 삭제 된 개체를 대치하기 위하 여 새로운 개체를 개체군 에 추가한다. 그림 3.8 은 교차와 돌연변이를 적용 하고 2 단계에서 삭제된 개체를 이용하여 새로운 개체를 만드는 것을 보여 준다. 그림 3.8] Supervised 유전자 학습 Keep throw 적합도 함수

13 □ 적합도 함수 정의 ■ 적합도 함수란 개체의 적합도를 평가하여 삭제할 개체를 찾는 것. 1.N 을 개체 E 의 입력 어트리뷰트 값들과 그 클래스의 training 인스턴 스의 match 횟수로 정의한다. 2. M 을 개체 E 의 입력 어트리뷰트 값들과 상대방 클래스의 training 인스턴스의 match 횟수로 정의한다. 3. M 에 1 을 더한다.(0 으로 나누게 되는 것을 막기 위한 것.) 4. N 을 M 으로 나누자.

14 Population Elemenet Income Range Life Insurance Promotion Credit Card Insurance SexAge 120-30KNOYESMeal30-39 230-40KYESNOFemale50-59 3?NO Male40-49 430-40KYES Male40-49 표 3.9] Supervised 유전자 학습 초기 개체군 Population Elemenet Income Range Life Insurance Promotion Credit Card Insurance SexAge 130-40KYES Meal30-39 230-40KYESNOFemale40-49 350-60KYESNOFemale30-39 420-30KNO Female50-59 520-30KNO Meal20-29 630-40KNO Meal40-49 표 3.10] 유전자 학습을 위한 training 데이터

15 □ 개체 1 에 대한 적합도 점수 계산 ■ 개체 1 은 클래스 Life Insurance Promotion = no 에 속한다. ■ N 을 구하는 과정으로 개체 1 을 training 인스턴스 4,5,6 과 비교 □ Income Range = 20 – 30K 는 training 인스턴스 4,5 와 match 한다. □ Credit Card Insurance = YES 에 해당하는 match 는 없다. □ SEX = Male 는 training 인스턴스 5,6 과 match 한다. □ Age = 30 – 39 에 해당하는 match 는 없다. 따라서 N 은 4 가 된다. ■ M 을 구하는 과정으로 개체 1 을 training 인스턴스 1,2,3 과 비교 □ Income Range = 20 – 30K 에 해당하는 match 는 없다. □ Credit Card Insurance = YES 는 training 인스턴스 1 과 match 된다. □ SEX = Male 는 training 인스턴스 1 과 match 한다. □ Age = 30 – 39 는 training 인스턴스 1,3 과 match 한다. 따라서 M 은 4 가 된다. □ Supervised 학습을 이용하여 만들고자 하는 모델은 생명보험 프로모션 을 수락한 사람들을 그렇지 않은 사람들과 구별해내는 것이다.

16 F(1)4 / 5 = 0.80 F(2)6 / 7 = 0.86 F(3)6 / 5 = 1.20 F(4)5 / 5 = 1.00 표 3.11] 표 3.9 의 개체 1 – 4 적합도 값 Population Elemenet Income Range Life Insurance Promotion #120 - 30KNO Population Elemenet Income Range Life Insurance Promotion #230 - 40KYES Credit Card Insurance SexAge YESMale30-39 Credit Card Insurance SexAge NOFemale50-59 Population Elemenet Income Range Life Insurance Promotion Credit Card Insurance SexAge #120 - 30KNO Female50-59 Population Elemenet Income Range Life Insurance Promotion Credit Card Insurance SexAge #230 - 40KYES Male30-39 그림 3.9] 교차 연산자 교차 연산 후 얻 은 새로운 개체 들에 대한 적합 도 점수가 F(1) = 7/5, F(2) = 6/4 로 향상되었음을 알 수 있다.

17 표 3.11] 두 번째 세대의 개체군 Population Elemenet Income Range Life Insurance Promotion Credit Card Insurance SexAge 120-30KNO Female50-59 230-40KYES Meal30-39 3?NO Male40-49 430-40KYES Male40-49 ※ 표 3.9 의 데이터를 그림 3.9 의 교차 연산이 적용 된 Supervised 유전자 학습의 두 번째 세대의 개체군

18 a1 a2 a3... an L1 L2............. Lp S1 S2 Sk E11 E21 E22 Ek2 Ek1 E12...... Solutions(m( 클러스터 개수 ) = 2) 그림 3.10] Unsupervised 유전자 클러스터링 □ 유전자 알고리즘과 Unsupervised 클러스터링

19 S1S2S3 Solution elements(1.0, 1.0)(3.0, 2.0)(4.0, 3.0) (initial population)(5.0, 5.0)(3.0, 5.0)(5.0, 1.0) Fitness score11.319.7815.55 Solution elements(5.0, 1.0)(3.0, 2.0)(4.30, 3.0) (second generation)(5.0, 5.0)(3.0, 5.0)(1.0, 1.0) Fitness score17.969.7811.34 Solution elements(5.0, 5.0)(3.0, 2.0)(4.0, 3.0) (third generation)(1.0, 5.0)(3.0, 5.0)(1.0, 1.0) Fitness score13.649.7811.34 표 3.12] unsupervised 클러스터링에서 첫번째 세대의 개체 군 0.5 + 3.5 + 1.11 + 2.69 + 2.5 + 1 Instancexy 123456123456 1.0 2.0 3.0 5.0 1.5 4.5 1.5 3.5 2.5 6.0 표 3.6 K-Means 입력값 표 3.12 는 표 3.6 에 있는 6 개의 인스턴스에 적용한다. 2 개의 클러스터를 가지고 세 개의 가능한 Solution(k = 3) 으로 알고리즘을 시작. 즉 m = 2, p = 6, k = 3 초기화.

20 ■ 어떤 특정 문제를 해결해야 할 때에는 여러 가지 기법들 중에서 어느 것을 사용 해야 하는지 선택을 해야 한다. 문제는 어느 데이터 마이닝 기법을 사용해야 하는 지 결정하는 것이다. 이 문제를 서술하면 다음과 같다. - 어떤 데이터 집합이 주어지고, 그 데이터에는 어트리뷰트와 그 값들이 있으며, 해결해야 할 문제에 대한 정보가 주어졌을 때 사용하기에 적절한 데이터 마이 닝 기법을 결정 해야 한다. ■ 어느 기법을 적용할 지를 결정하기 위해서는 다음의 질문들이 유용할 수 있다. - 학습은 supervised 인가 unsupervised 인가 ? - 데이터에 들어 있는 관계에 대한 명확한 설명이 요구되는 상황인가 ? - 입력 어트리뷰트와 출력 어트리뷰트가 별도로 있는 경우인가 ?, 아니면 어트 리뷰트들이 여러 방법으로 서로 상호작용하는 경우인가 ? - 입력 데이터는 범주 아니면 수치, 혹은 그 둘이 섞인 어트리뷰트인가 ? - 학습이 supervised 라면 출력 어트리뷰트는 하나인가 아니면 여러 개인가 ? 그리고 그 출력 어트리뷰트는 범주인가 아니면 수치인가 ? □ 데이터 마이닝 기법의 선택