[Algorithm] What is K-means Clustering?

 

1. K-means Clustering 이란 ? 

K-means clustering 에서 K는 데이터 집단에서 만들어지는 총 cluster수 이고 means는 각 데이터가 속한 클러스터의 중심까지의 평균 거리를 말한다. 이때 K-means clustering의 목표는 중심까지의 평균 거리를 최소화 하는 것이다.

 

해당 알고리즘의 구현 방법은 간단하다.

1. 각각의 데이터를 현재 가장 가까운 cluster에 배치 해준다

2. 모든 데이터의 배치가 끝난 후, 각 cluster의 centroid를 업데이트 해준다

3. 모든 데이터들을 새로 업데이트된 centroid를 기준으로 가장 가까운 곳으로 다시 재배치 해준다.

2번, 3번을 모든 데이터들이 수렴할때까지 반복해준다.

 

2. How to select K ? 

우리는 적절한 K를 찾기 위해 K를 다르게 하여 중심점으로 부터의 평균거리를 계산해 봐야한다.

이때, 적합한 K를 찾을 때까지 평균 거리는 급속도로 떨어질 것이다.

Fig 1. Cluster가 적은 경우

 

Fig2. Cluster가 적당한 경우

Fig 3. Cluster 가 많은 경우

 

3. How to apply K-means Clustering in program ?

def distance(x, y):
	 return sqrt(sum(pow(int(a) - int(b), 2) for a, b in zip(x, y)))

partial_sums = {}

for i in range(10):
 	partial_sums.setdefault(i, [0 for i in range(784)] )
    
def sum_vector(A,B):
 	return [int(x)+int(y) for x,y in zip(A, B)]


for line in sys.stdin:
 	line = line.strip()
 	img = [int(item) for item in line.split(",")]
 	min_dis = distance(centroids[0] , img)
 	# print(min_dis)
 	min_idx = 0
 	for i in range(1,10):
 		dis = distance(centroids[i], img)
 		if dis < min_dis:
 			min_dis = dis
 			min_idx = i
 	partial_sums[min_idx] = sum_vector(partial_sums[min_idx], img)
 	cnt[min_idx] += 1

해당 알고리즘은 내가 짠 알고리즘인데 일단 간단하게 해당 알고리즘이 들어간 일부분만 갖고와봤다.

먼저, 해당 파일의 각 이미지(데이터)를 읽고 각 중심점과 의 최소 거리를 구한 후 최소 평균거리의 중심점을 찾아 partial_sum에 해당 img의 최소 distance를 더해준다.

for line in sys.stdin:
	 line = line.strip()
 	idx, partial = line.split("\t")
 	partial_sum, cnt = partial.split("|")
 	partial_sum = partial_sum.split(",")
 	for i in range(len(partial_sum)):
 		partial_sum[i] = int(partial_sum[i].strip())
        
 	idx = int(idx)
 	cnt = int(cnt)
    
 	if (cur_idx == idx):
 		total += cnt
 		centroids = [centroids[i] + int(partial_sum[i]) for i in range(784)]
 	else:
 		if cur_idx is not None:
 			if total > 0:
 				new_cent = [str(centroids[i]/total) for i in range(784)]
 				new_cent = ' '.join(new_cent)
 				total = str(total)
 				print("Centroid "+ str(cur_idx) + ": " + str(total) + "," + new_cent)
 				total = cnt
 				centroids = [0 for i in range(784)]
 				centroids = [centroids[i] + int(partial_sum[i]) for i in range(784)]
 
 		elif cur_idx is None:
 				total = cnt
 				centroids = [centroids[i] + int(partial_sum[i]) for i in range(784)]
                
                cur_idx = idx
                
if total > 0:
 	new_cent = [str(centroids[i]/total) for i in range(784)]
 	new_cent = ' '.join(new_cent)
 	total = str(total)
 	print("Centroid "+ str(cur_idx) + ": " + str(total) + "," + new_cent)

다음 프로그램에서는 이제 각 클러스터(idx) 마다 전에 구했던 partial들을 총합 해주고 평균을 내어 새로운 클러스터의 중심점으로 갱신해준다.

지금 이 두 프로그램이 이제 위에서 설명한 2,3번 구간이다. 이제 이 프로그램 두개를 계속해서 반복해서 실행해주면 K-means Clustering을 시행시킬 수 있다.