K-Means Clustering 알고리즘
Clustering 알고리즘이란?
레이블이 지정되지 않은 데이터 셋을 일정한 클러스터 기준으로 그룹화하는 알고리즘이다 -> Unsupervised Learning(비지도 학습)
클러스터링 알고리즘은, 데이터셋이 얼마나 뭉쳐져 있는지/ 얼마나 떨어져있는지/ 비슷한 분포를 따르는지 등의 기준으로 그룹화 할 수 있다.
Kmeans Clustering 알고리즘이란?
데이터를 K개의 클러스터로 그룹화하는 알고리즘으로, 데이터 포인트끼리 얼마나 가까운지를 기준으로 그룹화한다.
클러스터의 중심점(Centroid)을 가지고, 클러스터를 할당하거나 중심점을 업데이트 하는 방식으로 작동한다.
핵심 아이디어
할당 단계(cluster assignment step) : K 개의 클러스터를 할당
업데이트 단계(move centroid step) : 각 클러스터의 중심을 이동
작동 단계
1. 클러스터(k)의 개수에 따라 무작위로 중심점을 정한다.
2. 데이터 포인트 마다 가장 가까운 중심점을 찾아 해당 클러스터로 분류한다.
3. 데이터가 클러스터로 분류될 때마다, 클러스터의 중심을 업데이트 한다.
4. 2,3 번 과정을 반복한 후, 중심점이 변화가 없고 수렴할 경우 알고리즘을 종료한다
알고리즘 설계
1. 입력값
def k_means_clustering(data, k, max_iterations=100):- data : 데이터
- k : 클러스터 개수
- max_iterations : 최대 반복 횟수
2. 반복문
- 할당 단계(Assignment)
- 각 데이터 포인트를 가장 가까운 중심에 할당
- clusters: 클러스터 할당을 저장할 리스트 초기화
- 각 데이터 포인트에 대해 모든 중심까지의 거리를 계산(유클리드 거리 기반)하고, 가장 가까운 중심의 인덱스를 찾아 해당 클러스터에 데이터 포인트를 추가
- 업데이트 단계(move centroid)
- 각 클러스터에 속한 데이터 포인트들의 평균을 계산하여 새로운 중심을 계산
- 각 클러스터에 대해 데이터 포인트들의 평균을 계산하여 새로운 중심을 구하고 > new_centroids 리스트에 저장
- 중심점 갱신 & 반복(Iteration)
- if 이전 중심과 새로운 중심이 거의 같으면 알고리즘이 수렴 > break 반복문 탈출 종료
3. Numpy 라이브러리 사용
import numpy as np
넘파이 라이브러리를 이용해서, 초기 중심점을 설정 / 가장 가까운 중심의 인덱스를 찾아서 할당/ 알고리즘이 수렴하는지 등의 기능을 구현할 것이다. 다음은 간단한 사용법이다.
샘플링 함수
np.random.choice(a, size=None, replace=True, p=None)
# a: 배열 혹은 정수 범위로, 샘플링 대상
# size: 생성하려는 샘플의 크기를 지정 , 기본값은 None으로, 하나의 샘플을 반환
# replace: 중복 샘플링을 허용할지 여부를 지정. 기본값은 True로, 중복 샘플링을 허용
# p: 각 요소가 선택될 확률을 나타내는 배열. 이 매개변수는 선택 사항, 주어지지 않으면 동일한 확률
유클리드 거리 계산 함수
np.linalg.norm(point1 - point2)
가장 작은 값 반환 함수
np.argmin(arr)
두 배열이 거의 동일한지 확인하는 함수
np.allclose(array1, array2)
# 기준 : 1e-05 (0.00001) - 혀용오차전체 코드
import numpy as np
def k_means_clustering(data, k, max_iterations=100):
# 초기 중심 설정
centroids = data[np.random.choice(data.shape[0], k, replace=False)] # 임의의 k개 데이터 포인트를 중심으로 선택
for _ in range(max_iterations):
# 할당 단계: 각 데이터 포인트를 가장 가까운 중심에 할당
clusters = [[] for _ in range(k)] # 클러스터 할당을 저장할 리스트 초기화
for point in data:
distances = [np.linalg.norm(point - centroid) for centroid in centroids] # 모든 중심까지의 거리 계산
cluster_index = np.argmin(distances) # 가장 가까운 중심의 인덱스를 찾음
clusters[cluster_index].append(point) # 해당 클러스터에 데이터 포인트 추가
# 업데이트 단계: 각 클러스터에 속한 데이터 포인트들의 평균을 계산하여 새로운 중심을 구함
new_centroids = []
for cluster in clusters:
new_centroid = np.mean(cluster, axis=0) # 클러스터 내 데이터 포인트들의 평균을 계산하여 새로운 중심 구함
new_centroids.append(new_centroid)
# 중심이 수렴하면 종료
if np.allclose(centroids, new_centroids): # 이전 중심과 새로운 중심이 거의 같으면
break
centroids = np.array(new_centroids) # 새로운 중심으로 갱신
return centroids, clusters
# 클러스터링 결과 시각화
def plot_clusters(centroids, clusters):
colors = ['r', 'g', 'b', 'y', 'c', 'm'] # 클러스터 시각화를 위한 색상 리스트
for i, cluster in enumerate(clusters):
cluster = np.array(cluster)
plt.scatter(cluster[:, 0], cluster[:, 1], c=colors[i % len(colors)], label=f'Cluster {i+1}')
plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', s=200, c='black', label='Centroids')
plt.title('K-Means Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.show()적용
%matplotlib inline
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
import numpy as np
import random
sklearn 에서 제공하는 데이터셋 생성 함수를 이용해서 k-means 클러스터링을 수행하고 시각화해본다.
# make_moons 데이터셋 생성
X, _ = make_moons(n_samples=200, noise=0.1, random_state=19)
# k 개수 설정
k = 2
# 클러스터링 수행
centroids, clusters = k_means_clustering(X, k) # 클러스터링 수행
# 군집 결과 시각화
plot_clusters(centroids, clusters)
클러스터링 결과를 시각화 했을 때, 직관적으로 그룹화가 잘 안된 것을 확인할 수 있다.
K means 클러스터링은 거리기반 알고리즘이기 때문에, 데이터의 분포를 원형으로 가정한다.
K means 알고리즘은 알고리즘이 간단해서 큰 데이터에도 쉽게 사용할 수 있는 장점이 있지만,
데이터의 분포가 원형이 아닐 경우, 적절하지 않은 클러스터링 결과를 리턴할 수도 있다.
클러스터링 알고리즘을 선택할 때, 먼저 데이터의 분포를 확인해야 한다.
데이터의 분포가 원형이 아닌 경우에는, 밀도 기반 클러스터링(Density-Based Clustering) 알고리즘인 DBSCAN 등을 사용하는 것이 더 적합할 수 있다.