DBSCAN 알고리즘

DBSCAN 알고리즘

epsilon: 클러스터의 반경
minPts: 클러스터를 이루는 개체의 최솟값
core point:반경 epsilon 내에 minPts개 이상의 점이 존재하는 중심점
border point: 군집의 중심이 되지는 못하지만, 군집에 속하는 점
noise point: 군집에 포함되지 못하는 점

K-means의 k값처럼 DBSCAN에서는 esplion과 minPts값을 미리 지정해주어야 함

알고리즘의 동작 원리

1. 임의의 점 p를 선택하고 p를 포함한 주어진 클러스터의 반경 안에 포함되어 있는 점들의 개수를 셈

2. 만일 해당 원에 minPts 개 이상의 점이 포함되어 있으면, 해당 점 p를 core point로 간주하고 원에 포함된 점들을 하나의 클러스터로 묶음

3. 해당 원에 minPts 개의 미만의 점이 포함 되어 있으면 일단 패스

4. 모든 점에 대해 돌아가면서 1~3 번의 과정을 반복, 만일 새로운 점 p가 core point가 되고, 이 점이 기존의 클러스터(p를 core point로 하는) 에 속한다면, 두 개의 클러스터는 연결되어 있다고 하며 하나의 클러스터로 묶음

5. 모든 점에 대해 클러스터링 과정을 끝냈는데, 어떤 점을 중심으로 하더라도 클러스터에 속하지 못하는 점이 있으면 이를 noise point로 간주, 또한 특정 군집에는 속하지만 core point가 아닌 border point라고 칭함

%matplotlib inline #주피터에서 쓰이는  Matplotlib을 사용할 때 그래프를 인라인으로 표시하도록 지정하는 명령어
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_circles, make_moons, make_blobs
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import random

circle_points, circle_labels = make_circles(n_samples = 100, factor = 0.5, noise = 0.01)
moon_points, moon_labels = make_moons(n_samples = 100, noise = 0.01)
diag_points, _ = make_blobs(n_samples = 100, random_state = 170)
transfromation = [[0.6, -0.6], [-0.4, 0.8]]
diag_points = np.dot(diag_points, transfromation)

fig = plt.figure()
ax = fig.add_subplot(1,1,1) # 그래프 초기화

color_dict = {0 :'red', 1:'blue', 2:'green', 3:'brown', 4:'indigo'} #각 클러스터별 색깔 지정

epsilon, minPts = 0.2, 3 #epsilon, minPts 초기화 

circle_dbscan = DBSCAN(eps = epsilon, min_samples = minPts) #DBSCAN 알고리즘 적용

circle_dbscan.fit(circle_points) #circle_point를 DBSCAN 알고리즘 훈련

n_cluster = max(circle_dbscan.labels_)+1 # 클러스터 수 label은 인덱스로 반환 하기 때문에 +1을 해주어 클러스터 수를 입력해줌
print(f'# of cluster: {n_cluster}')
print(f'DBSCAN Y-hat: {circle_dbscan.labels_}') #각 points들이 어떤 군집에 속해있는지 label로 나타냄 -1은 noise point로 아무 군집에 속해있지 않다는 것을 의미 

for cluster in range(n_cluster):
    cluster_sub_points = circle_points[circle_dbscan.labels_ == cluster] # 불리언 인덱싱을 이용해 레이블과 cluster의 값이 같을 때만 cluster_sub_points에 저장
    ax.scatter(cluster_sub_points[:, 0], cluster_sub_points[:, 1], c = color_dict[cluster], label = 'cluster_{}'.format(cluster)) # label에 맞는 값들을 그래프에 저장 

ax.set_title('DBSCAN on circle data')
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.legend()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

epsilon, minPts = 0.4, 3
moon_dbscan = DBSCAN(eps = epsilon, min_samples = minPts)
moon_dbscan.fit(moon_points)
n_cluster = max(moon_dbscan.labels_) + 1

for cluster in range(n_cluster):
    cluster_sub_points = moon_points[moon_dbscan.labels_ == cluster]
    ax.scatter(cluster_sub_points[:,0], cluster_sub_points[:,1], c = color_dict[cluster], label = 'cluster_{}'.format(cluster))

ax.set_title('DBSCAN on moon data')
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.legend()


fig = plt.figure()
ax = fig.add_subplot(1,1,1)

epsilon, minPts = 0.7, 3
diag_dbscan = DBSCAN(eps=epsilon, min_samples=minPts)
diag_dbscan.fit(diag_points)
n_cluster = max(diag_dbscan.labels_)+1
print(f'# of cluster: {n_cluster}')
print(f'DBSCAN Y-hat: {diag_dbscan.labels_}')
for cluster in range(n_cluster):
    cluster_sub_points = diag_points[diag_dbscan.labels_ == cluster]
    ax.scatter(cluster_sub_points[:,0], cluster_sub_points[:,1], c = color_dict[cluster], label = 'cluster_{}'.format(cluster))
ax.set_title('DBSCAN on diagonal shaped data')
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.legend()

epsilon과 minPts의 조절이 잘 되면 클러스터의 수를 입력해주지 않아도 클러스터의 개수를 설정하여 주어진 데이터에 대한 군집화 수행이 가능하다. 비교적 k-means 보다 유연하며 보편적으로 사용되는 알고리즘

DBSCAN의 단점

k-means에 비해 알고리즘의 수행 시간이 길다. 군집화 해야하는 데이터 수가 많아질수록 수행 시간은 증가한다.

import time
from sklearn.cluster import KMeans
n_samples = [100, 500, 1000, 2000, 5000, 7500, 10000, 20000, 30000, 40000, 50000] # sample의 개수 초기화

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)
    
    kmeans_start = time.time() #kmeans 훈련 시작시간 측정
    circle_kmeans = KMeans(n_clusters = 2)
    circle_kmeans.fit(dummy_circle)
    kmeans_end = time.time() # kmeans 훈련 종료시간 측정
    
    dbscan_start = time.time() #dbscan 훈련 시작시간 측정
    epsilon, minPts = 0.2, 3
    circle_dbscan = DBSCAN(eps = epsilon, min_samples = minPts)
    circle_dbscan.fit(dummy_circle)
    dbscan_end = time.time() #dbscan 훈련 종료시간 측정
    x.append(n_sample) # 
    kmeans_time.append(kmeans_end - kmeans_start) # y축에 측정시간 저장
    dbscan_time.append(dbscan_end - dbscan_start)# y축에 측정 시간 저장
    print("# of samples: {} / Elapsed time of K-means:{:.5f}s / DBSCAN: {:.5f}s".format(n_sample, kmeans_end - kmeans_start, dbscan_end - dbscan_start)) # 샘플의 개수당 kmeans가 훈련되는데 걸린시간, 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()