[Python] Clustering

본 포스트에서는 K-Means를 활용한 클러스터링을 진행해보도록 하겠습니다.

 

기본적으로 클러스터 분석이란, 다차원 공간에서 여러 개의 점들이 존재할 때 서로 가까이 있는 점들을 서로 연관시키는 문제입니다. 단순히 2차원 좌표의 점이 아닌, 다차원 공간으로 확장이 가능하기 때문에 인물 사진 분류, 스팸 메일 분류 등 다양한 task에 활용이 가능합니다.

 

클러스터링에는 매우 다양한 방법들이 있는데, 그중 K-Means Clustering은 반복적인 연산을 통해 데이터를 k개의 클러스터로 분할하는 알고리즘입니다. 크게 다음과 같은 4가지 순서를 따릅니다.

 

1. 임의로 k개의 중심점(centroid)을 생성

2. 각각의 점을 가장 가까운 중심점의 클러스터에 포함

3. 각 클러스터에 포함된 점들을 평균내어 새로운 중심점 계산

4. 2-3 단계를 반복하다가 클러스터에 변화가 없으면 종료

 

그럼 이제부터 파이썬을 이용해 직접 코드를 구현해보도록 하겠습니다.

 

모듈 불러오기

먼저 실습에 진행될 모듈을 불러옵니다.

import random
import numpy as np
import matplotlib.pyplot as plt

 

K - Means

본격적으로 k-means 알고리즘을 구현합니다. 기본적으로 위의 4단계를 따르도록 구성합니다. k는 중심점의 개수이고, points는 각 점들의 좌표입니다.

 

1. 먼저 임의의 k개의 점을 중심점으로 선택합니다. 이때 Forgy라는 방법을 사용하는데, 아래 구현한 것처럼 데이터 점들 중 랜덤하게 선택하는 방법입니다. 이 방법은 간단하지만 Local Optimum에 빠질 수 있습니다. 직접 보는 것이 이해하기 좋으니 아래 실행 결과에 첨부하도록 하겠습니다. (이를 해결하기 위해 K-Means++라는 방법을 사용할 수 있습니다. 멀리 떨어진 점들을 초기 중심점으로 사용합니다.)

2. 다음으로 각 점이 할당될 중심점을 계산합니다. 아래 함수 설명에서 더 자세히 살펴보겠습니다.

3. 새로운 centroid를 계산합니다. 마찬가지로 아래 함수에서 더 자세히 보겠습니다.

4. 할당된 클러스터에 변화가 없을 경우에는 종료하고, 변화한 경우에는 2-3 단계를 다시 반복합니다.

def kmeans(k, points):
  prev_assingment = []

  # 1. 임의로 k개의 점을 중심점으로 선택 (forgy)
  centroids = points[np.random.choice(points.shape[0], replace=False, size=k)]

  for epoch in range(10):
    # 2. 각 점이 할당될 중심점을 계산
    assignment = [assign(p, centroids, k) for p in points]

    # 3. 새로운 centroid 계산
    centroids = compute_centroids(assignment, points, k)

    # 4. 클러스터에 변화가 없을 경우 종료
    if prev_assingment == assignment:
      break
      
    prev_assignment = assignment
  
  return assignment, centroids

 

assign()

assign 함수는 각 점들과, centroid, k 값을 인자로 받습니다. 리턴값으로는 인자로 받은 점이 어떤 centroid와 가장 가까운가를 돌려주어야 합니다. 때문에 인자로 받은 점과 centroid들과의 거리를 모두 구한 후 최솟값을 반환해주면 됩니다. 이때 거리는 흔히 알려져있는 유클리디안 거리를 활용합니다.

# 각각의 포인트마다 어떤 centroid와 가까운가
def assign(point, centroids, k):
  return min(range(k), key=lambda i: np.dot(centroids[i]-point, centroids[i]-point))

 

compute_centroids()

centroids를 계산하는 함수입니다. 코드가 살짝 복잡해보일 수 있지만, 어떤 역할을 수행하는지 생각해보면 됩니다. 앞 설명에서, 각 클러스터에 포함된 점들을 평균내어 새로운 중심점(centroid)를 계산한다고 했습니다. 따라서 vec_sum 리스트에 각 클러스터마다 점들을 모아주고, counts 리스트에 몇 개의 점이 있는지도 저장하여줍니다. 이후 평균 계산 시에 사용하기 위함입니다. 마지막으로 반환 시에 점들의 개수가 0보다 많으면 평균을 계산하고, 아닌 경우에는 새로운 centroid를 랜덤하게 선택하여 반환합니다.

def compute_centroids(assignments, points, k):
  vec_sum = [np.zeros(len(points[0])) for _ in range(k)]
  counts = [0] * k
  
  for i, p in zip(assignments, points):
    vec_sum[i] += p
    counts[i] += 1
  
  return [vec_sum[i]/counts[i] if counts[i] > 0 else random.choice(points) for i in range(k)]

 

테스트

앞서 구현했던 함수들을 이용하여 간단한 테스트를 진행해보도록 하겠습니다. 임의로 약간 떨어진 군집 3개를 만들어줍니다.

# 데이터 생성
k = 3

points = [np.random.randn(k) for _ in range(80)]
points.extend([np.random.randn(k) + np.array([5, 5, 5]) for _ in range(20)])
points.extend([np.random.randn(k) + np.array([10, 5, 0]) for _ in range(20)])
points = np.array(points)

# kmeans 실행
assignments, centroids = kmeans(k, points)

 

k-means 함수를 실행한 후 결과물로 시각화를 진행합니다. 아래의 두 이미지 중 좌측 이미지는 Local Optimum에 빠진 경우입니다. 잘못된 centroids 선택으로 클러스터링이 제대로 진행되지 않은 것을 확인할 수 있습니다. 뒷부분에서 sklearn 모듈을 이용하면 이러한 문제를 해결할 수 있습니다. (아마 내부적으로 K-Means++ 로 구현되어 있을 겁니다.)

# 결과 확인
fig = plt.figure()
ax = fig.gca(projection='3d')

clusters = [[] for _ in range(k)]
for a, p in zip(assignments, points):
  clusters[a].append(p)

for cluster in clusters:
  ax.scatter(*zip(*cluster))

ax.scatter(*zip(*centroids), s=100)
plt.show()

좌측 이미지는 초기 잘못된 centroids 선택으로 local optimum에 빠진 경우입니다.

 

사진 불러오기

다음은 이미지를 대상으로 클러스터링을 진행해보겠습니다. 우선 원하는 이미지를 불러옵니다. 코랩으로 진행하는 경우 구글 드라이브를 이용해도 좋고, 런타임에 바로 업로드해도 좋습니다.

from PIL import Image

# 사진 불러오기 & 크기 조절 & 화면에 출력
im = Image.open("/content/squirrel.png")

width = 200
height = im.height * width // im.width
im = im.resize((width, height))

plt.imshow(im)
plt.show()

 

K - Means 적용, 결과 확인

kmeans 함수를 불러온 이미지 데이터에 적용합니다. 이후 모든 픽셀의 색을 centroids 중 하나로 선택합니다. 만약 k가 5라면, 불러온 이미지의 색을 5개로만 표현하도록 바꾸는 것입니다.

# 데이터 준비 & k-means 알고리즘 적용
pixels = np.array(im).reshape(-1,3)
assignments, centroids= kmeans(10, pixels)

# 모든 픽셀의 색을 centroid중 하나로 선택
for a, i in zip(assignments, range(pixels.shape[0])):
 pixels[i] = centroids[a]
 
# 바뀐 그림 출력
im_remastered = Image.fromarray(pixels.reshape(im.height, im.width, 3), 'RGB')
plt.imshow(im_remastered)
plt.show()

 

K - Means using sklearn

지금까지 직접 구현했던 함수들은 사실 모듈을 불러오면 쉽게 실행해볼 수 있습니다. 공부할 때는 직접 구현해보는 것을 추천하지만, 실제로 사용할 때는 모듈을 사용하는 것이 더 빠르고 정확합니다.

from sklearn.cluster import KMeans

k = 3

points = [np.random.randn(k) for _ in range(80)]
points.extend([np.random.randn(k) + np.array([5, 5, 5]) for _ in range(20)])
points.extend([np.random.randn(k) + np.array([10, 5, 0]) for _ in range(20)])
points = np.array(points)

kmeans = KMeans(n_clusters=k)
kmeans.fit(points)

# 결과 확인
fig = plt.figure()
ax = fig.gca(projection='3d')

clusters = [[] for _ in range(k)]
for a, p in zip(kmeans.labels_, points):
  clusters[a].append(p)

for cluster in clusters:
  ax.scatter(*zip(*cluster))

ax.scatter(*zip(*kmeans.cluster_centers_), s=100)
plt.show()

 

K - Means using sklearn

이미지의 경우도 마찬가지로 모듈을 활용할 수 있습니다.

from sklearn.cluster import KMeans

pixels = np.array(im).reshape(-1,3)

kmeans = KMeans(n_clusters=10)
kmeans.fit(pixels)

for a, i in zip(kmeans.labels_, range(pixels.shape[0])):
 pixels[i] = kmeans.cluster_centers_[a]

im_remastered = Image.fromarray(pixels.reshape(im.height, im.width, 3), 'RGB')
plt.imshow(im_remastered)
plt.show()