Clustering

비지도 학습

비지도 학습이란 지도 학습과 달리 training data로 정답 label이 없는 데이터가 주어지는 학습방법입니다.

다시 말해, 아무도 정답을 알려주지 않은 채 오로지 데이터셋의 특징 및 패턴을 기반으로 모델 스스로가 판단하는 방법입니다.

모든 데이터셋에 각각에 대한 정보가 명시되어 있으면 좋지만, 그렇지 않은 경우가 대부분일뿐더러 라벨링하는 과정에서 적지 않은 인력과 시간, 돈이 소모됩니다.

이러한 문제 해결을 위해 현재도 많은 방법론들이 연구되고 있습니다.

비지도 학습의 대표적인 예시로는 군집화와 차원축소,생성 모델이 있습니다.

K-means

지도학습과 달리 비지도학습에선 데이터 X가 무엇인지에 대한 정답 label y가 없습니다. 또한, y가 될 수 있는 분류 기준도 없다고 할 수 있습니다.

이런 상황에서 군집화(Clustering)이란 명확한 분류 기준이 없는 상황에서도 데이터들을 분석하여 가까운 것 또는 유사한 것들끼리 묶어주는 작업을 의미합니다.
이를 통해 개별적인 데이터들을 몇 개의 그룹으로 추상화하여 새로운 의미를 발견해 나갈 수 있게 됩니다.

K-means 알고리즘은 k값이 주어져있을 때, 주어진 데이터들을 k개의 클러스터로 묶는 알고리즘으로 대표적인 클러스터링 기법 중 하나입니다.

코드로 살펴보기

%matplotlib inline
from sklearn.datasets import make_blobs
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import random

# 중심점이 5개인 100개의 점 데이터를 무작위로 생성합니다.
points, labels = make_blobs(n_samples=100, centers=5, n_features=2, random_state=135)

print(points.shape, points[:10])  # 무작위로 생성된 점의 좌표 10개 출력
print(labels.shape, labels[:10])    # 10개의 점들이 각각 대응하는 중심점(label) 값 출력

임의로 지정한 k개의 중심점이 새로운 label 역할을 하는 것이 K-means의 아이디어입니다.

# 축 그리기
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)

# 위에서 생성한 점 데이터들을 pandas DataFrame 형태로 변환하기
points_df = pd.DataFrame(points, columns=['X', 'Y'])
display(points_df.head())

# 점 데이터를 X-Y grid에 시각화하기
ax.scatter(points[:, 0], points[:, 1], c='black', label='random generated data')

# 축 이름을 라벨에 달고, 점 데이터 그리기
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.legend()
ax.grid()

눈으로 봤을 때 5개의 군집을 이루고 있는 것처럼 보입니다. K-means 알고리즘은 어떻게 군집화할 지 지켜봅시다.

먼저 K-means의 순서는
1. 원하는 클러스터의 수 K를 정합니다.
2. 무작위로 클러스터의 수와 같은 K개의 중심점(Centroid)를 선정합니다. 이들은 각각의 클러스터를 대표하게 됩니다.
3. 나머지 점들과 모든 중심점 간의 유클리디안 거리를 계산한 후, 가장 가까운 거리를 가지는 중심점의 클러스터에 속하도록 합니다.
4. 각 K개의 클러스터의 중심점을 재조정합니다.
5. 특정 클러스터에 속하는 모든 점들의 평균값이 해당 클러스터다음 iteration의 중심점이 됩니다.
6. 재조정된 중심점을 바탕으로 모든 점들과 새로 조정된 중심점 간의 유클리디안 거리를 다시 계산한 후, 가장 가까운 거리를 가지는 클러스터에 해당 점을 재배정합니다.
7. 중심점이 더 이상 바뀌지 않거나 사용자가 지정한 반복 횟수까지 반복합니다.
7가지 단계라고 보시면 됩니다.

from sklearn.cluster import KMeans

# 1), 2) 위에서 생성한 무작위 점 데이터(points)에 클러스터의 수(K)가 5인 K-means 알고리즘을 적용 
kmeans_cluster = KMeans(n_clusters = 5)

# 3) ~ 6) 과정이 전부 함축되어 있는 코드입니다. points에 대하여 K가 5일 때의 K-means iteration을 수행
kmeans_cluster.fit(points)

# n 번째 클러스터 데이터를 어떤 색으로 도식할 지 결정하는 color dictionary
color_dict = {0: 'red', 1: 'blue', 2:'green', 3:'brown', 4:'indigo'} 

# 점 데이터를 X-Y grid에 시각화합니다.
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)

# K-means clustering의 결과대로 색깔별로 구분하여 점에 색칠한 후 도식
for cluster in range(5):
    cluster_sub_points = points[kmeans_cluster.labels_ == cluster] # 전체 무작위 점 데이터에서 K-means 알고리즘에 의해 군집화된 sub data를 분리합니다. 
    ax.scatter(cluster_sub_points[:, 0], cluster_sub_points[:, 1], c=color_dict[cluster], label='cluster_{}'.format(cluster)) # 해당 sub data를 plot합니다.

# 축 이름을 라벨에 달고, 점 데이터 그리기
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.legend()
ax.grid()

예상한대로 5개의 그룹으로 잘 분리된 것으로 보아 K-means는 군집의 수만 주어진다면 데이터의 군집화를 매우 잘 수행하는 것을 알 수 있습니다.
하지만, K-means가 항상 잘 되는 것은 아니며 주어진 데이터의 분포에 따라 의도하지 않은 결과를 초래할 수도 있습니다.
아래에서 알아보겠습니다.

K-means가 잘 동작하지 않는 경우

1. 원
   
2. 초승달(?)
   
3. 평행한 두 직선
   

👏 K-means는
1. 군집의 개수를 미리 지정해야하기에 k의 값을 모르거나 예측하기 어려운 경우에는 사용이 어렵다.
2. 유클리디안 거리가 가까운 데이터끼리 군집이 형성되기에 데이터의 분포에 따라 군집화를 성공적으로 수행하지 못할 수 있다.
가 있습니다.

DBSCAN

DBSCAN(Density Based Spatial Clustering of Applications with Noise) 알고리즘은 가장 널리 알려진 밀도(density) 기반의 군집 알고리즘입니다.

DBSCAN의 가장 큰 특징 중 하나는 군집의 개수를 미리 지정할 필요가 없고 불특정한 형태의 군집도 찾을 수 있습니다.

👍 DBSCAN을 이해하는 데 필요한 변수와 용어 정리 👍
epsilon: 클러스터의 반경
minPts: 클러스터를 이루는 개체의 최솟값
core point: 반경 epsilon 내에 minPts 개 이상의 점이 존재하는 중심점
border point: 군집의 중심이 되지는 못하지만, 군집에 속하는 점
noise point: 군집에 포함되지 못하는 점

먼저 DBSCAN의 순서는
1. 임의의 점 p를 설정하고 p를 포함하여 주어진 클러스터의 반경(epsilon)안에 포함되어 있는 점들의 수를 셉니다.
2. 만일 해당 원에 minPts개 이상의 점이 포함되어 있으면, 해당 점 p를 core point로 간주하고 원에 포함된 점들을 하나의 클러스터를 간주합니다.
3. 해당 원에 minPts개 미만의 점이 포함되어 있으면 일단 넘어갑니다.
4. 모든 점에 대해 돌아가면서 위 과정을 반복하는데 만일 새로운 점 p가 core point가 되고 이 점이 기존의 클러스터(p를 core point로 하는)에 속한다면 두 개의 클러스터는 연결되어 있다고 간주하며 하나의 클러스터로 연결합니다.
5. 모든 점에 대하여 클러스터링 과정을 끝냈는데 어떤 점을 중심을 하더라도 클러스터에 속하지 못하는 점이 있으면 이를 noise point로 간주합니다.
5단계라 보시면 됩니다.

또한, 이해를 돕기 위한 사이트입니다. 한 번 보시면 쉽게 다가오실 겁니다.
https://primo.ai/index.php?title=Density-Based_Spatial_Clustering_of_Applications_with_Noise_(DBSCAN)

K-means에서 잘 되지 않았던 데이터 분포 DBSCAN으로 돌파하기

1. 원
   
2. 초승달
   
3. 평행한 두 직선
   

K-means와 DBSCAN의 알고리즘 소요시간 비교

# DBSCAN 알고리즘과 K-means 알고리즘의 시간을 비교하는 코드 
import time

n_samples= [100, 500, 1000, 2000, 5000, 7500, 10000, 20000, 30000, 40000, 50000]

kmeans_time = []
dbscan_time = []
x = []
for n_sample in n_samples:
    dummy_circle, dummy_labels = make_circles(n_samples=n_sample, factor=0.5, noise=0.01) # 원형의 분포를 가지는 데이터 생성

    # K-means 시간을 측정
    kmeans_start = time.time()
    circle_kmeans = KMeans(n_clusters=2)
    circle_kmeans.fit(dummy_circle)
    kmeans_end = time.time()

    # DBSCAN 시간을 측정
    dbscan_start = time.time()
    epsilon, minPts = 0.2, 3
    circle_dbscan = DBSCAN(eps=epsilon, min_samples=minPts)
    circle_dbscan.fit(dummy_circle)
    dbscan_end = time.time()

    x.append(n_sample)
    kmeans_time.append(kmeans_end-kmeans_start)
    dbscan_time.append(dbscan_end-dbscan_start)
    print("# of samples: {} / Elapsed time of K-means: {:.5f}s / DBSCAN: {:.5f}s".format(n_sample, kmeans_end-kmeans_start, dbscan_end-dbscan_start))

# K-means와 DBSCAN의 소요 시간 그래프화
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)
ax.scatter(x, kmeans_time, c='red', marker='x', label='K-means elapsed time')
ax.scatter(x, dbscan_time, c='green', label='DBSCAN elapsed time')
ax.set_xlabel('# of samples')
ax.set_ylabel('time(s)')
ax.legend()
ax.grid()

그래프를 보고 알 수 있듯이 데이터의 수가 적을 때는 K-means가 더 오래걸리나 군집화할 데이터가 많아질수록 DBSCAN의 수행 시간이 급격히 늘어납니다.