[Clustering] K-means clustering 구현해보기

서론

Clustering은 묶음으로 만들어버린다는 뜻이다.

이때 뭘 묶어버리냐 하면, 관련있는 데이터들끼리 하나로 묶는다.

 

 

 

이름에 대해 이야기 해보자면

 

1. 몇개의 묶음으로 만들지에 대한 것이 "k", 즉 k개의 묶음으로 만든다는 것이다.
2. 묶어진 데이터들을 대표하는 데이터(중심점, centroid)를 구할때 "평균(mean)"을 사용하게 된다.

결국 "k개의 묶음 만들기" 라고 할 수 있겠다.

 

 

 

K-means clustering에 대한 자세한 증명이 아닌, 구현(scratch)에 초점을 맞췄음을 미리 밝힌다.

 

 

 

 

 

 

관련있다란 무엇인가?

데이터 a와 b가 어느정도로 관련있는지에 대해 어떻게 말할 수 있을까?

"얼추 비슷해요~"
"좀 다르지 않나요?"

이런 말은 공학도들 사이에서 죽고싶다는 말과 같다.



k-means는 거리의 개념으로 "관련있다"를 정의한다.

데이터 A와 B는 상당히 관련있어 --> 거리가 가깝다.
데이터 A와 B는 아예 관련이 없어 --> 거리가 멀다.

따라서 하나의 값(거리)으로 나타낼 수 있으며, 정통적인 k-means는 euclidean 거리를 사용한다.

 

 

단, 풀고자하는 상황에 맞게 거리를 구하는 방식을 다르게 구성해도 된다.

Euclidean 거리를 사용하여 관련도를 구하지 않고, 본인이 원하는 공식을 사용해서 구해도 된다!

물론 관련있을때의 값과 관련 없을때의 값이 확실히 구분되야한다는 것을 잊지말자.

 

 

Euclidean 거리

예를들어 데이터 A와 B가 N개의 값으로 이루어져있다고 생각해보자.

 

 

그럼 euclidean 거리는 다음과 같다.

 

 

 

 

 

 

 

 

 

알고리즘에 대하여

K-means는 다음과 같이 동작한다.
1. k개의 중심점(centroid)을 무작위로 뿌린다음
2. 데이터 각각이 어느 중심점과 가장 가까운지 체크한다.

3. 중심점이 같은 데이터들을 모은 후, 같은 위치에 해당하는 값들끼리 평균(mean)을 낸다.
        1. 데이터가 N개의 값을 가진다면, 3번에서 N개의 평균값이 나온다.
4. 3번에서 구해진 평균값들이 새로운 중심점이 된다.

5. 새로 구한 중심점들이 이전 중심점과 값이 같다면, 알고리즘을 종료한다.
6. 새로 구한 중심점들이 이전 중심점과 값이 같지 않다면, 2번으로 돌아간다.

 

 

위 과정을 하나씩, 코드를 실행해보며 확인해보자.

 

 

 

 

 

 

0. 무작위 데이터 만들기

시각화를 위해 데이터는 2개의 값으로 이루어져있다고 가정하자.

임의의 평균과 분산을 가지는 정규분포로부터 임의의 수만큼 표본을 뽑아낸다.

K개의 묶음을 만들어내기 위해, 위에서 말한 임의의 정규분포 K개로부터 표본 뽑기를 해주는 코드를 작성해보자.

 

import numpy as np
import matplotlib.pyplot as plt

def create_kmeans_dataset(
	cluster_count:int,
	variance_range:list,
	data_count_range:list,
	mean_range:list,
):
	"""
	[Params]
	
	cluster_count: 클러스터 개수
	variance_range: 해당 범위 내의 분산으로부터 데이터가 생성된다. [variance_low, variance_high]
	data_count_range: 해당 범위 내의 데이터 개수로부터 데이터가 생성된다. [data_count_low, data_count_high]
	mean_range: 해당 범위 내의 평균으로부터 데이터가 생성된다. [mean_low, mean_high]
	
	[Return]
	clusters: list[np.ndarray]
	- 각 클러스터는 (data_count, 2) 의 shape을 갖는다.
	
	"""
	
	clusters = []
	variance_low, variance_high = variance_range
	data_count_low, data_count_high = data_count_range
	mean_low, mean_high = mean_range
	
	# Cluster 생성
	for _ in range(cluster_count):
		# 랜덤하게 데이터 분포를 결정
		feature_variances = np.random.uniform(variance_low, variance_high, (2,))
		data_count = int(np.random.uniform(data_count_low, data_count_high))
		location = np.random.uniform(mean_low, mean_high, (2,))
		
		cluster = []
		for _ in range(data_count):
			cluster.append([
				np.random.normal(loc=location[0], scale=feature_variances[0]),
				np.random.normal(loc=location[1], scale=feature_variances[1])
			])
		
			cluster = np.array(cluster, np.float32)
			clusters.append(cluster)
	
	return clusters

 

 

위 코드를 통해 5개의 cluster를 만들어보자.

dataset = create_kmeans_dataset(
	cluster_count=5,
	variance_range=[0.5,3],
	data_count_range=[500,3000],
	mean_range=[-15,15]
)

for data in dataset:
	plt.scatter(data[:,0], data[:,1])

plt.show()

임의로 생성된 데이터

 

 

생성된 데이터들은 cluster별로 데이터가 따로 존재한다.

이제 이걸 하나로 합친다음에 무작위로 섞자.

 

dataset_flatten = []

for cluster in dataset:
	for data in cluster:
		dataset_flatten.append(data)

dataset_flatten = np.array(dataset_flatten, np.float32)
np.random.shuffle(dataset_flatten)

plt.scatter(dataset_flatten[:,0], dataset_flatten[:,1])

더이상 clustering되지 않는다

 

 

 

 

 

 

 

 

1. k개의 중심점을 무작위로 뿌린다

말을 뿌린다고 한거지, 존재하는 데이터들에서 무작위로 k개를 뽑는것과 같다.

 

 

def get_random_centroids(datas:np.ndarray, centroid_count:int):
	"""
	[Params]
	datas: 데이터셋, (data_count,2)
	centroid_count: 중심점 개수
	
	[Return]
	centroids: np.ndarray
	- (centroid_count, 2)
	"""
	
	centroids = set()
	
	while len(centroids) < centroid_count:
		centroids.add(int(np.random.uniform(0,len(datas))))
	
	centroids = [datas[idx] for idx in list(centroids)]
	centroids = np.stack(centroids, axis=0)
	
	return centroids

 

 

위와같이 구현할 수 있고, 5개의 중심점을 만든다고 가정한 뒤 시각화 해보면 다음과 같다.

random_centroids = get_random_centroids(dataset_flatten, 5)

plt.scatter(dataset_flatten[:,0], dataset_flatten[:,1])
plt.scatter(random_centroids[:,0], random_centroids[:,1])
plt.show()

 

랜덤이라 매번 다르게 나온다

 

 

 

랜덤으로 생성하면, 중심점들이 서로 너무 가까이 있을 수 있기 때문에

 

1. 제대로 clustering이 되지 않거나

2. 수렴이 되긴하는데, 오래 걸릴 수도 있다.

 

물론 이를 해결할 수 있는 k-means++ 라는 방식이 있는데, 다음 포스팅에서 다룰 예정이다.

 

 

 

 

 

 

 

 

 

2. 데이터 각각이 어느 중심점과 가장 가까운지 체크한다

Numpy의 broadcasting을 활용해서 데이터들과 중심점들간의 거리를 한번에 계산한다.

 

이후 가장 가까운 중심점을 numpy의 argmin(가장 작은 값의 인덱스를 반환하는 함수)을 사용하여 찾는다.

 

def clustering(centroids:np.ndarray, datas:np.ndarray):
	"""
	[Params]
	centroids: 중심점들, (centroid_count, 2)
	datas: 데이터셋, (data_count, 2)
	
	[Return]
	clustered_datas: 클러스터링 결과, list[np.ndarray]
	"""
	
	clustered_datas = [[] for _ in range(len(centroids))]
	
	# Broadcasting을 위해 차원을 추가
	centroids_ = centroids[np.newaxis,:,:] # (1, centroid_count, 2)
	datas_ = datas[:,np.newaxis,:] # (data_count, 1, 2)
	
	# 거리 계산 및 가장 가까운 중심점 찾기
	distance = np.sum((centroids_ - datas_)**2, axis=-1)**0.5 # (data_count, centroid_count)
	clustering_result = np.argmin(distance, axis=-1) # (data_count,)
	
	# 가장 가까운 중심점에 해당하는 곳에 데이터 넣기
	for data_idx, centroid_idx in enumerate(clustering_result):
		clustered_datas[int(centroid_idx)].append(datas[data_idx])
	
	clustered_datas = [np.array(clustered_data, np.float32) for clustered_data in clustered_datas]
	
	return clustered_datas

 

결과로 나오는 데이터의 shape이 헷갈릴 수도 있기 때문에 주석으로 표시해놨다.

 

 

 

 

 

 

 

 

 

3, 4.  새로운 중심점 찾기

def update_centroids(clustered_data:list):
	"""
	[Params]
	clustered_data: 클러스터링이 완료된 데이터들, 리스트의 원소들은 특정 중심점으로 묶인 데이터들이다. (cluster_size, 2) x cluster_count
	
	[Return]
	new_centroids: 새로 업데이트된 중심점들, (cluster_count, 2)
	"""
	
	new_centroids = []
	
	for cluster in clustered_data:
		cluster = np.array(cluster, np.float32) # (cluster_size, 2)
	
		new_centroid = np.mean(cluster, axis=0) # (2,)
		new_centroids.append(new_centroid)
	
	new_centroids = np.stack(new_centroids, axis=0)
	
	return new_centroids

 

 

첫번째 차원에 대해 평균을 내게 되면, 같은 위치에 있는 값들끼리 평균을 한번에 낼 수 있다.

 

 

 

 

 

 

 

 

 

5, 6. 알고리즘의 진행 여부

알고리즘은 이전에 구해진 중심점과 새로 구해진 중심점들이 서로 차이가 없으면 끝난다.

 

물론 차이가 있다면, 계속 진행된다.

 

centroids = get_random_centroids(dataset_flatten, 5) # 초기 중심점 얻기

difference = np.sum(centroids) # 이전 중심점과의 차이값을 저장하는 변수, 초기값은 초기 중심점들 값의 합으로 했다
datas = dataset_flatten.copy() # 사용할 데이터 복사

# 초기 중심점들 위치 plot
plt.scatter(datas[:,0], datas[:,1])
plt.scatter(centroids[:,0], centroids[:,1])
plt.show()

# 알고리즘 진행
while difference != 0:
	clustered_datas = clustering(centroids, datas)
	new_centroid = update_centroids(clustered_datas)
	
	difference = np.sum(centroids - new_centroid) # 구해진 중심점과 이전 중심점간의 차이 구하기
	centroids = new_centroid

# 최종 결과 plot
for clustered_data in clustered_datas:
	plt.scatter(clustered_data[:,0], clustered_data[:,1])

plt.scatter(centroids[:,0], centroids[:,1])
plt.show()

 

위 코드의 결과는 다음과 같다.

초기 중심점(좌), Clustering 결과(우)

 

보면 결과가 별로일 때도 있다.

 

초기 중심점(좌), Clustering 결과(우)

 

물론 잘 나올때도 있다.

 

 

 

 

중심점 위치가 정중앙이 아닌데요?

저기가 중심점이 맞아? 라고 생각이 들 수 있는데, 이상하게 보이는 이유는 중심점을 평균을 사용해서 구했기 때문이다.

 

데이터들이 특정 값에 몰려있으면, 중심점은 몰려있는 부분으로 치우칠 수밖에 없다.

 

위 데이터도 점들의 투명도를 조절하면, 데이터들이 어느 값에 몰려있는지 확인할 수 있다.

투명도를 조절한 결과