2차원 공간에서 퍼지 클러스터링(fuzzy clustering) 자바 구현

2017년 9월 6일 추가

이 포스트를 EM 알고리즘 구현으로 검색해서 들어오신 분이 있네요

이 포스트는 k-means 알고리즘 구현 입니다.

EM 알고리즘 구현은 제 깃헙에 있는 EM 알고리즘 구현을 참고 부탁드립니다.

링크: https://github.com/WoongheeLee/EM_Clustering

---------------------------

이 포스팅은 Jiawei Han 외 (2012), Data Mining: Concepts and Techniques, Elsevier의 11장 EM 알고리즘 부분 중 k-means 알고리즘 요약했습니다.

k-means 알고리즘 또는 k-평균 알고리즘이라고 부릅니다. 제 느낌엔 k-중심점 알고리즘이라고 번역해야 알고리즘을 잘 나타내는 것 같습니다.

k-means 알고리즘을 EM 알고리즘처럼 두 단계로 분리하면,

Expectation step: 클러스터의 센터가 주어짐. 각각의 오브젝트가 가장 가까운 클러스터에 배정됨
Maximization step: 클러스터에 배정된 데이터가 주어짐. 클러스터의 중심을 업데이트.

으로 정리할 수 있습니다.

예를 들어 2차원 공간에 점 a(3, 3), b(4, 10), c(9, 6), d(14, 8), e(18, 11), f(21, 7)을 두 개의 클러스터로 나눈다고 합시다.

초기의 클러스터 중심점 c1을 점 a로, c2를 점 b로 초기화 하면 c1(3, 3), c2(4, 10)이 됩니다.

아래의 E-step과 M-step을 c1과 c2가 수렴할 때 까지 반복합니다.

E-step: 중심점 c1, c2 각각에 대해 모든 오브젝트의 소속 정도(membership degree)를 구합니다.

공식은 아래와 같습니다.

$${{1 \over dist(o,c_1)^2} \over {1\over dist(o,c_1)^2}+{1\over dist(o,c_2)^2}}={dist(o,c_2)^2 \over dist(o,c_1)^2 + dist(o,c_2)^2} or {dist(o,c_1)^2 \over dist(o,c_1)^2 + dist(o,c_2)^2}$$

M-step: 중심점을 소속 정도와 각 오브젝트 간의 관계로 업데이트 해줍니다.

공식은 아래와 같습니다.

$$c_j = {\Sigma_o w_{o,c_j}^2 \cdot o \over \Sigma_o w_{o,c_j}^2}$$

이를 자바로 구현하면 아래와 같습니다(아파치 공통 수학 라이브러리, Common Math: The Apache Commons Mathematics Library로 두 점의 거리를 구함).

import org.apache.commons.math3.ml.distance.EuclideanDistance;

public class FuzzyClustering {
	public static void main(String[] args) {
		double[][] O = {
				{3d,3d},
				{4d,10d},
				{9d,6d},
				{14d,8d},
				{18d,11d},
				{21d,7d}
		};
		
		double[] C1 = {3d,3d};
		double[] C2 = {4d,10d};
		
		double[][] M = new double[6][2];
		
		double sumOfDiff = 1d;
		int iteration = 0;
		while (sumOfDiff > 0.00001) {
			double[][] tempCenter= {
					{C1[0], C1[1]},
					{C2[0], C2[1]}
			};
			// E - step
			for(int i = 0; i < 6; i++) {
				EuclideanDistance dist1 = new EuclideanDistance();
				EuclideanDistance dist2 = new EuclideanDistance();
				double d1 = dist1.compute(O[i], C1);
				double d2 = dist2.compute(O[i], C2);
				M[i][0] = d2 / (d1+d2);
				M[i][1] = d1 / (d1+d2);
				
				//System.out.println(M[i][0] + " " + M[i][1]);
			}
	
			// S - step
			double c1Top0 = 0d, c1Bot0 = 0d;
			double c1Top1 = 0d, c1Bot1 = 0d;
			double c2Top0 = 0d, c2Bot0 = 0d;
			double c2Top1 = 0d, c2Bot1 = 0d;
			
			for(int i = 0; i < 6; i++) {
				c1Top0 += ( O[i][0]*M[i][0]*M[i][0] );
				c1Bot0 += ( M[i][0]*M[i][0] );
				c1Top1 += ( O[i][1]*M[i][0]*M[i][0] );
				c1Bot1 += ( M[i][0]*M[i][0] );
				
				c2Top0 += ( O[i][0]*M[i][1]*M[i][1] );
				c2Bot0 += ( M[i][1]*M[i][1] );
				c2Top1 += ( O[i][1]*M[i][1]*M[i][1] );
				c2Bot1 += ( M[i][1]*M[i][1] );
			}
			
			C1[0] = c1Top0/c1Bot0;
			C1[1] = c1Top1/c1Bot1;
			
			C2[0] = c2Top0/c2Bot0;
			C2[1] = c2Top1/c2Bot1;
			
			System.out.println(++iteration + ": " + C1[0] + " " + C1[1] + "\t" + C2[0] + " " + C2[1]);
			
			EuclideanDistance distC1 = new EuclideanDistance();
			EuclideanDistance distC2 = new EuclideanDistance();
			
			sumOfDiff = 0d;
			sumOfDiff += distC1.compute(C1, tempCenter[0]);
			sumOfDiff += distC2.compute(C2, tempCenter[1]);
		}
	}
}

결과는 아래와 같습니다.

1: 8.837624350403692 5.2977784548142886    10.117357240135048 8.99396154516859
2: 10.040276842121157 6.726389485774621    12.99261281314849 8.255717316377646
3: 9.013556414634444 6.776829794566906    13.920865686130899 8.122195396423969
4: 8.079702366732649 6.605504714322963    14.745709049978108 8.238359795810537
5: 7.417734033555067 6.536301245768633    15.430405719094198 8.369284145965254
6: 6.958566252497104 6.513948695504151    15.908536196095021 8.45609588636148
7: 6.6775503038294595 6.503990227812495    16.200174278804205 8.50565112094769
8: 6.522849505556704 6.498934400940244    16.361174490755324 8.531639870614727
9: 6.4433180745840755 6.496344550655162    16.444498677471554 8.544538910724029
10: 6.403968718328533 6.495050095482755    16.486049582242035 8.550780858218568
11: 6.384875866181844 6.494417059447915    16.50636122535932 8.55377716361974
12: 6.3756967657475085 6.4941112257598    16.516188566196263 8.555213379461488
13: 6.37130168085309 6.493964238928891    16.520918271497305 8.55590186842661
14: 6.3692006263299 6.493893721733949    16.523188386912295 8.556231947970584
15: 6.368196725615574 6.493859908833084    16.524276408295034 8.556390175380681
16: 6.367717069929296 6.493843699211132    16.52479746775346 8.556466001850012
17: 6.367487862808439 6.493835930205546    16.525046895591334 8.556502327672389
18: 6.3673783147278185 6.493832207667053    16.525166263834592 8.556519724586874
19: 6.367325947972883 6.493830424526666    16.5252233804157 8.556528053910974
20: 6.367300911717189 6.493829570620614    16.52525070729478 8.556532040942807
21: 6.367288940635236 6.493829161805242    16.52526378065735 8.556533949092458
22: 6.3672832161490645 6.493828966121589    16.525270034737975 8.556534862186227
23: 6.3672804785525425 6.493828872471208    16.525273026484218 8.556535299076817

2차원 공간에서 그려보면 아래와 같습니다.

아래 그림에서 클러스터 1의 중심점이 붉은색, 클러스터 2의 중심점이 녹색으로 나타납니다.

위 내용은 Jiawei Han 외 (2012), Data Mining: Concepts and Techniques, Elsevier의 11장 EM 알고리즘 부분 중 k-means 알고리즘으로 설명하는 부분을 자바로 구현한 포스팅입니다.

자세한 내용을 확인하고 싶으신 분은 아래 책을 참고하세요.

한글판도 있습니다. 전에 잠깐 보니 번역이 꽤 괜찮았던걸로 기억합니다.

데이터 마이닝 개념과 기법 국내도서 저자 : 지아웨이 한,미셸린 캠버,지안 페이 / 정사범,송용근역 출판 : 에이콘출판사 2015.04.30 상세보기

당연히 영어판으로 보는 것도 좋습니다.

Data Mining (Hardcover / 3rd Ed.) 외국도서 저자 : Jiawei Han 출판 : Elsevier Science Ltd 2011.06.01 상세보기