clustering 알고리즘 k-means vs Hac

Clustering 이란?

Clustering이란 데이터를 비슷한 속성을 가진 그룹으로 나누는 비지도 학습기법이다.

K-means Clustering

k-means는 데이터를 미리 지정한 k개의 클러스터로 나누고 각, 클러스터의 중심점 (Centroid)을 기준으로 데이터를 반복적으로 재배치 하면서 군집을 형성하는 알고리즘이다. 초기 중심점 선택에 따라 결과가 달라질 수 있다.

동작 방식

초기화 : 클러스터 수 K를 정하고 무작위로 k개의 중심점을 선택한다.
클러스터 할당 : 각 데이터를 가장 가까운 중심점에 할당한다.
중심점 재계산 : 각 클러스터 내 데이터의 평균값으로 중심점을 갱신한다.
반복 : 중심점이 바뀌지 않을 때 까지 반복한다.

동작 예제

1. 초기화 : 위와 같은 예시에서 k=2이고 1,4번째 샘플을 초기 중심점으로 선택해보자

2. 클러스터 할당 : Euclidean distance를 이용하여 나머지 데이터를 가장 가까운 중심점에 할당한다.

ex) Record 2(1.5,2.0) 은 Record 4 (5.0,7.0) 보다 Record 1(1.0,1.0)이 Euclidean distance가 가깝다.

3. 중심점 재계산 : 클러스터의 할당 결과 Cluster 1 에는 1,2,3 데이터가 할당되었다. 중심점은 각 데이터의 평균으로 계산하므로

(1.0+1.5+3.0) / 3 = 1.8xxx , (1.0+2.0+4.0) / 3 = 2.3xxxxx

4. 반복 : 중심점이 바뀌지 않을 때 까지 = 데이터가 이동하지 않을때 까지 반복한다.

결과:

k-means의 변형

k-medoids : 중심점을 구할 때, 평균 대신 중앙값 사용 -> 이상치에 강함
k-modes : 범주형 데이터용
CLARA : 대용량 데이터셋 처리용
EM : 혼합 모델 기반 확률적 클러스터링

HAC (Hierarchical Agglomerative Clustering)

HAC은 모든 데이터를 개별 클러스터로 시작해서 서로 가장 가까운 클러스터끼리 점진적으로 병합하여 하나의 클러스터로 만드는 계층적 클러스터링 기법이다. 병합과정을 덴드로그램(dendrogram)으로 표현할 수 있다.

동작 방식

초기화 : 각 데이터를 클러스터로 간주후 클러스터 간의 거리를 측정
병합 : 가장 가까운 두 클러스터를 병합
반복 : 1개의 클러스터가 남을 때 까지 반복

동작 예제 (single Linkage 방식)

1. 초기화

아래 예제는 이탈리의 도시간의 거리를 나타낸 데이터이다.

2. 병합 :

가장 가까운 거리는 MI와 TO의 138이다. MI와TO를 병합 후, 다른 클러스터간의 거리를 재계산하는데 single Linkage 방식에서는 가까운 거리를 선택한다. 예를 들어 MI/TO의 BA와의 거리는 MI-BA의 거리 877, TO-BA의 거리 996중 더 작은 877을 선택한다.

3. 반복

클러스터가 최종적으로 1개가 남을때 까지 반복한다.

클러스터 수 결정 방법

HAC 방법은 점진적으로 병합을 하면서 계층을 확인할 수 있다.

왼쪽 그림과 같이 나누게 되면 클러스터 2개, 오른쪽 그림에서는 클러스터 1개, 개별데이터 2개로 나뉜다.

dendrogram에서 y축의 값은 각 병합 시점의 거리 값(혹은 유사도)를 의미한다. x축의 값은 순서를 의미하지 않고 y축의 높이가 낮을수록 먼저 병합됨을 의미한다.

거리 계산 종류

가장 가까운 두 클러스터를 병합한 후 다른 클러스터 간의 거리를 계산할 때 계산방식으로 여러가지를 선택할 수 있다.

Single linkage : 두 클러스터 간 가장 가까운 거리
Complete linkage : 가장 먼 거리
Average linkage : 평균 거리
Centroid : 중심점 간 거리

K-Means 코드 예제

python을 사용하여 가장 적합한 cluster의 개수 (k)를 구하는 문제이다.

mouse.csv 파일

mouse.csv

0.04MB

주요 파라미터

n_clusters : 클러스트의 개수
max_iter : 클러스터 중심을 변경하는 최대 반복 횟수 (max_iter를 넘어가면 클러스터의 중심점이 최적화 되지 않아도 중지)
random_state : 난수 생성 시드를 고정해서 항상 같은 값이 나오게 해준다.
n_init : k-means는 초기 중심점을 랜덤하게 선택하기 때문에 n_init의 수만큼 반복해서 가장 최적의 결과를 출력한다.

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

#read csv
df=pd.read_csv("mouse.csv")
plt.scatter(df.iloc[:,0],df.iloc[:,1])
plt.xlabel("x")
plt.ylabel("y")
plt.title("Mouse Data")
plt.show()

n_clusters_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
max_iter_list = [50, 100, 200, 300]

results = []

# kMeans clustering 
for k in n_clusters_list:
    for max_iter in max_iter_list:
        # perform KMeans clustering with different k and max_iter
        kmeans = KMeans(n_clusters=k, max_iter=max_iter, random_state=42, n_init='auto')
        labels = kmeans.fit_predict(df)
        print(f"k={k},max_iter={max_iter},iter={kmeans.n_iter_}")
        #calculate inertia and silhouette score
        inertia = kmeans.inertia_  
        silhouette=silhouette_score(df,labels)if k>1 else None
        # calculate noise 
        centroids=kmeans.cluster_centers_
        distances=np.linalg.norm(df.values-centroids[labels],axis=1)
        threshold=distances.mean()+2*distances.std()
        is_noise=distances>threshold
        
        results.append({
            'k': k,
            'max_iter': max_iter,
            'inertia': inertia,
            'silhouette':silhouette,
            'labels': labels,
            'centroids': centroids,
            'noise':is_noise
        })

#Elbow method
    inertias = []
for k in range(1, 10):
    kmeans = KMeans(n_clusters=k, random_state=42,n_init='auto').fit(df)
    inertias.append(kmeans.inertia_)

plt.plot(range(1, 10), inertias, marker='o')
plt.title('Elbow Method for Optimal K')
plt.xlabel('Number of Clusters')
plt.ylabel('Inertia')
plt.show()

#silhouette score
silhouettes=[]
for k in range(2,10):
    kmeans=KMeans(n_clusters=k, random_state=42,n_init='auto').fit(df)
    score=silhouette_score(df,kmeans.labels_)
    silhouettes.append(score)
    print(f"k={k},silhouette score={score:.4f}")

plt.plot(range(2, 10), silhouettes, marker='o')
plt.title('silhouettes score for Optimal K')
plt.xlabel('Number of Clusters')
plt.ylabel('silhouette score')
plt.show()

# sorted by inertia
top3_inertia = sorted(results, key=lambda x: x['inertia'])[:3]

#sorted by silhouette
top3_silhouette =sorted(
    [r for r in results if r['silhouette'] is not None],
    key=lambda x: x['silhouette'],reverse=True)[:3]

# visualize top 3 silhouette
fig,axes=plt.subplots(1,3,figsize=(20,5))
for i, (res,ax) in enumerate(zip(top3_silhouette,axes), 1):
    ax.scatter(df.iloc[:, 0], df.iloc[:, 1], c=res['labels'], cmap='tab10', s=10, alpha=0.6)
    ax.scatter(res['centroids'][:, 0], res['centroids'][:, 1], c='black', marker='X', s=100)
    ax.scatter(df.iloc[res['noise'],0],df.iloc[res['noise'],1],c='black',s=10,label='Noise')
    ax.set_title(f"Top {i}: k={res['k']}, iter={res['max_iter']}, inertia={res['inertia']:.2f},silhouette={res['silhouette']:.3f}")
    ax.set_xlabel("X")
    ax.set_ylabel("Y")
plt.show()

# visualize top 3 inertia
fig,axes=plt.subplots(1,3,figsize=(20,5))
for i, (res,ax) in enumerate(zip(top3_inertia,axes), 1):
    ax.scatter(df.iloc[:, 0], df.iloc[:, 1], c=res['labels'], cmap='tab10', s=10, alpha=0.6)
    ax.scatter(res['centroids'][:, 0], res['centroids'][:, 1], c='black', marker='X', s=100)
    ax.scatter(df.iloc[res['noise'],0],df.iloc[res['noise'],1],c='black',s=10,label='Noise')
    ax.set_title(f"Top {i}: k={res['k']}, iter={res['max_iter']}, inertia={res['inertia']:.2f},silhouette={res['silhouette']:.3f}")
    ax.set_xlabel("X")
    ax.set_ylabel("Y")
plt.show()

Clustering 이란?

K-means Clustering

HAC (Hierarchical Agglomerative Clustering)

K-Means 코드 예제

티스토리툴바