K-means clustering 이해하기

클러스터링은 데이터를 분류한다는 뜻입니다. 쉽게 말하자면 비슷한 녀석들끼리 너네는 1번 그룹, 너네는 2번 그룹 이런 식으로 나누어 주는 거예요.

여러가지 방법이 많은데, 그 중 가장 기초가 되는 K-means clustering (K-평균 알고리즘) 에 대해 알아보겠습니다.

용어 설명

가장 먼저 이 글에 나올 용어 몇개를 설명하겠습니다.

클러스터 : 데이터 그룹이라는 뜻입니다. 데이터 1~10까지는 A 그룹, 데이터 11~16까지는 B 그룹, ... 이라는 식으로 클러스터를 나누게 됩니다.
중심점 : 클러스터의 중심이 되는 지점입니다. 이 알고리즘에서 클러스터의 중심은, 클러스터에 속하는 데이터들의 평균입니다.

용어는 이거 딱 두개만 알고 계시면 됩니다. 어려운 말은 다 없애고 갑니다.

알고리즘 동작 방식

이 알고리즘은 클러스터의 갯수를 임의로 정하고, 각 클러스터별로 중심점을 학습시켜 감으로써 데이터를 분류합니다.

2차원 데이터가 100개가 있다고 합니다.
그러면 데이터는 (x, y) 형태를 가질 거고, 좌표평면에 나타낼 수 있을 겁니다.
데이터는 데이터대로 두고, 데이터를 몇 개 그룹으로 구분할 것인지를 임의로 정합니다.
각 그룹의 중심점이라고 생각되는 위치를 임의로 정합니다.
만약 그룹이 3개라면, 예를 들어 (1,1), (2,5), (3,0) 과 같이 아무렇게나 정할 수도 있습니다.
각각의 데이터가 어느 중심점과 가장 가까운지 계산합니다. 예를 들어 데이터 (2,4)은 (2,5)이라는 중심점과 가장 가깝습니다.
가장 가까운 클러스터로 데이터를 할당합니다. (2,4) 데이터는 2번 클러스터에 할당되었습니다.
전체 데이터를 대상으로 클러스터를 할당했으면, 각 클러스터의 데이터를 가지고 중심점을 재계산합니다.
클러스터 별 새로운 중심점은, 클러스터에 속하는 데이터 전체의 평균으로 계산합니다.
위의 6~9번까지의 스텝을 반복합니다. 어느 단계까지 가면 더이상 중심점이 변하지 않습니다.
계산을 종료합니다.

그림으로 살펴 보기

가능한 한 풀어서 쓰려고 했으나, 여전히 이해되지 않는 부분이 분명히 있을 겁니다. 그림으로 동작하는 과정을 살펴보면 보다 쉽습니다.

데이터를 준비하기

아래와 같이 데이터를 준비했다고 합시다. 2차원의 데이터이고, 사람이 보면 딱 봐도 3개 그룹으로 나눠지는 걸 볼 수가 있습니다. 다만 그룹 간에 정확한 경계를 나누는 것까지 손으로 하기에는 다소 번거로운 작업이 되겠죠. 이걸 컴퓨터로 나눠보겠습니다.

그룹 갯수와 중심점을 임의로 정하기

아래와 같이, 그룹의 갯수는 3개로 정하고 중심점의 위치는 임의로 아무렇게나 둡니다. 그리고 각 클러스터별로 데이터를 배당한 결과는 아래와 같습니다.

누가 봐도 엉터리로 나눠진 결과인 걸 알 수가 있지만, 이제 위에서 설명한 6~9번의 스텝을 반복적으로 계산시켜 보겠습니다.

배당 결과로 중심점을 재계산하기

배당 결과로 중심점을 재계산한다는 건 다음과 같습니다.

파란색 데이터만 모아서 평균을 낸다.
주황색 데이터만 모아서 평균을 낸다.
초록색 데이터만 모아서 평균을 낸다.

위의 세 단계에서 나온 각각의 평균점이 각 클러스터의 새로운 중심점이 됩니다. 그리고 이 중심점을 가지고 전체 데이터에 대해서 클러스터별로 다시 데이터를 배당한 결과가, 아래 그림과 같습니다.

위 그림을 보면, 중심점이 마치 알아서 사람이 느끼는 중심으로 이동하는 것처럼 보입니다. 사람 눈에 그렇게 보인다고 해서 이걸 "학습"한다고 흔히들 표현을 합니다. 꼭 마치 알아서 배우는 것 같잖아요? 이제 두번째 스텝으로 다시 한 번 학습을 진행해 보겠습니다.

두번째 학습 결과

두번째 학습을 하게 되면 아래와 같이 중심점이 실제 중심에 현저히 가까운 곳으로 이동하게 됩니다. 이정도 결과만 봐도 마치 거의 학습이 끝난 것처럼 보이죠? 딱 보기에는 그냥 끝난 것 같고, 경계선을 자세히 들여다 보면 뭔가 좀 분류가 잘못된 느낌이 있는 점이 몇개 보이는 수준입니다.

알고리즘의 한계점

K-means clustering 은 사실 쉽고 빠르고 이해도 직관적인 방법이긴 한데, 이상하게 생긴 데이터들에는 잘 안 먹힙니다.

솔직히... 저런 식으로 생긴 게 물리적인 특성을 가진 데이터에 존재할까 싶기는 한데, 어쨌든 저러한 한계점이 있다는 내용이구요, 이를 보완하기 위한 알고리즘도 많습니다. 그런 알고리즘들의 단점은, 복잡하게 생긴 데이터셋을 처리할 수 있느니만큼 보다 느리다는 점입니다.

코딩으로 구현하기

코딩하는 방식은 여러개가 있겠습니다만, 사실 파이썬이 제일 쉬우니까 그걸로 알아보겠습니다. 다음 코드를 보시죠. 사실 이런 무식한 하드코딩을 쓰는 사람은 없겠지만, 원리의 이해 정도로만 생각해 주시면 좋을 거 같습니다. 원리만 이해하고 나면 한줄짜리 라이브러리로 되어 있는 것도 있으니 차라리 그런 걸 보시고 따라하는 게 낫습니다.

원리의 이해에 받아쓰기만큼 좋은 게 없습니다. 복사 붙여넣기 하지 마시고, 그냥 다 따라서 타이핑 해보세요!

#-*- coding:utf-8 -*-

import numpy as np
from matplotlib import pyplot as plt


####################################
#
# Step 0 : 데이터 만들기

num_data = 300
dimension = 2
data = np.random.randn(num_data, dimension)
offsets = np.array([[5,2], [-1,5], [2,3], [5,5], [-4,0], [4,-3]])

for offset in offsets:
    data = np.append(data,np.random.randn(num_data, dimension)*1.2 + offset, axis=0)




####################################
#
# Step 1 : 초기화 - 클러스터의 갯수를 정하고, 각 클러스터의 중심점을 정함

num_cluster = 7

# 각 차원별 min/max가 구해짐. 2차원이라면 x축의 min/max와 y축의 min/max
# [[x_min, y_min], [x_max, y_max]] 이런 식
min_max = [np.min(data, axis=0), np.max(data, axis=0)]

# 범위가 0~10 이고 클러스터가 2개라 하면
# 일단 0~5/5~10 으로 나눈 다음에,
# 2.5, 7.5 를 클러스터의 초기 중심값으로 하려는 것
quantile = (min_max[1] - min_max[0])/num_cluster/2

# 클러스터 초기 중심값을 구함
clst_mu = np.array([quantile*(2*i+1) + min_max[0] for i in range(num_cluster)])
print(f'각 클러스터별 평균 : {clst_mu}')




####################################
#
# Step 2 : 각 데이터에서 가장 가까운 클러스터를 찾아 데이터를 배당

distance = (data - clst_mu.reshape(num_cluster,1,dimension))
distance = distance*distance
distance = distance.sum(axis=2).T
cluster = np.where(distance==distance.min(axis=1).reshape((len(data),1)))[1]




####################################
#
# Step 3 : 배당 결과를 가지고 클러스터 중심점을 재계산

clst_mu_old = clst_mu.copy()
for i in range(num_cluster):
    clst_mu[i] = np.mean(data[np.where(cluster==i)[0]], axis=0)

# 특정 그룹에 속하는 인자가 하나도 없을 경우 np.mean의 결과로 nan을 뱉어냄
# 그럴 경우 이전 평균을 그대로 갖다 쓰는 것으로 코드 만듬
clst_mu = clst_mu_old*np.isnan(clst_mu) + np.nan_to_num(clst_mu)
print(f'\n* 각 클러스터별 평균\n{clst_mu}')




####################################
#
# Step 4 : 계속 반복하는 코드 (Step.2 & Step.3)

maxEpoch = 100

for epoch in range(maxEpoch):
    distance = (data - clst_mu.reshape(num_cluster,1,dimension))
    distance = distance*distance
    distance = distance.sum(axis=2).T
    cluster = np.where(distance==distance.min(axis=1).reshape((len(data),1)))[1]
    
    clst_mu_old = clst_mu.copy()
    for i in range(num_cluster):
        clst_mu[i] = np.mean(data[np.where(cluster==i)[0]], axis=0)

    clst_mu = clst_mu_old*np.isnan(clst_mu) + np.nan_to_num(clst_mu)    





####################################
#
# Step 5 : 시각화

clustered = []

for i in range(num_cluster):
    clustered.append(data[np.where(cluster==i)[0]])

    
fig = plt.figure(figsize=[6,6])

for clustered_data in clustered:
    plt.scatter(clustered_data.T[0],clustered_data.T[1], s=6)
plt.scatter(clst_mu.T[0],clst_mu.T[1], c='black', s=50)

plt.grid()
plt.show()

저작자표시 비영리 변경금지

컴퓨터와 코드, 데이터와 친해지기