[ML] Mean Shift, DBSCAN, and Silhouette metric

이번 포스팅에서는 군집화 모델인 Mean Shift와 DBSCAN에 대해 알아보고 군집화 모델의 성능을 평가하는 지표인 Silhouette metric에 대해서 소개하려한다. 그리고 이 두 가지 모델들과 평가지표를 Scikit-learn을 이용해서 간단하게 구현해보는 시간도 갖는다. 목차는 다음과 같다.

 

1. Mean Shift

2. DBSCAN(Density Based Spatial Clustering of Application with Noise)

3. Silhouette metric for clustering

 

1. Mean Shift

Mean Shift는 Non-parametric(비모수 방법론) 모델이며 KDE(Kernel Density Estimation)을 이용하여 개별 데이터 포인트들이 데이터 분포가 높은 곳으로 이동하면서 군집화를 수행하는 모델이다. Non-parametric모델이기 때문에 사전에 군집화 개수를 지정하지 않으며 데이터 분포도에 기반해 자동으로 군집화 개수를 정하게 된다.

 

Mean Shift 모델이 동작하는 프로세스를 단계적으로 하나씩 따라가 보자. 하단의 그림으로 예시를 들어 이해해보자.

 

https://www.semanticscholar.org/paper/Accelerating-Mean-Shift-Segmentation-Algorithm-on-Huang-Men/f35ce3b996d4f7be146ac2fef6a03510815bb907/figure/0

우선 Mean Shift의 큰 동작 과정을 요약하면 다음과 같다. 가장 먼저 개별 포인트 하나가 하늘색 동그라미의 반경 내에서 데이터 분포 확률 밀도가 가장 높은 곳으로 이동을 하게 된다. 이 때 이동할 '밀도가 가장 높은 곳'을 찾기 위해 주변의 데이터 포인트들과의 거리값을 Kernel 함수값으로 입력한 후 반환되는 값을 처음 위치에서 그만큼 이동하면서 위치를 업데이트 해나간다.

 

1. Step 1: 개별 데이터의 특정 반경 내에서 주변 데이터를 포함한 데이터 분포도를 계산한다.
2. Step 2: 계산한 데이터 분포도 중 가장 밀도가 높은 방향으로 데이터의 위치를 이동시킨다. 이 때, 가장 밀도가 높은 곳을 찾기 위해 KDE 함수를 사용한다. 
3. Step 3: 업데이트된 위치에서 다시 Step 1처럼 반경 내에서 다시 주변 데이터를 포함해 데이터 분포도를 계산하고 Step 2처럼 KDE 함수를 사용해 가장 밀도가 높은 곳으로 위치를 업데이트 시킨다. 
4. Step 4: Step 3를 계속적으로 반복하다가 더 이상 데이터의 위치가 업데이트 되지 않을 때(움직이지 않을 때) 반복을 멈춘다.
5. Step 5: 위와 같은 과정을 모든 개별 데이터에 일일이 적용한다.

그렇다면 KDE란 무엇일까? KDE란, 개별 데이터 포인트들에 커널함수를 적용한 후 반환값들을 모두 합한 뒤에 개별 데이터 포인트들의 개수로 나누어서 확률 밀도 함수를 추정하는 방식이다. 가장 대표적인 커널함수로는 Gaussian 분포 함수(정규분포 함수)가 사용된다.

 

https://blogs.sas.com/content/iml/2016/07/27/visualize-kernel-density-estimate.html#prettyPhoto/0/

 

 

위와 같이 빨간색의 Components가 개별 데이터 포인트들에 해당하고 각각의 데이터 포인트들을 커널함수에 적용시킨 후 총 데이터 건수로 나누어 확률밀도를 추정한 것이 파란색선의 KDE이다. 파란색 선을 적절하게 결정하기 위해서 KDE의 중요한 하이퍼파라미터가 존재한다. 이 파라미터에 대해 알아보기 위해 잠시나마 어려운 수식 하나만 살펴보자.

 

KDE에 대한 수식은 다음과 같다. 여러 문자로 이루어져있고 이해하기 난감한 것처럼 보이겠지만 여기서 중요한 파라미터는 단 하나다.

 

KDE의 수식

 

우선, K는 개별 데이터를 입력시킬 Kernel 함수이다. 그리고 h값이 우리가 알아두어야 할 중요한 파라미터이다. h는 bandwidth라고 불리는 smoothing 파라미터이다. 이 h값을 작게 부여할수록 undersmoothing이 발생하며 결국 오버피팅이 발생한다. 반면에 h값을 크게 부여할수록 oversmoothing이 발생하며 결국 언더피팅이 발생한다. 따라서 h값도 bias 와 variance의 Trade-off 관계 즉, '두 마리 토끼를 모두 잡을 수 없는 상태' 이다. 

 

https://deepai.org/machine-learning-glossary-and-terms/kernel-density-estimation

 

위 그림을 살펴보면서 bandwidth 값에 따라 어떻게 KDE 분포가 변하는지 살펴보자. 우선 빨간색 선의 True PDF(Probability Density Function)이 실제 데이터들의 확률 밀도함수이다. 이 때 bandwidth값이 1.6일 때 가장 True PDF와 비슷한 분포를 그리는 것을 볼 수 있다. 반면에 bandwidth가 0.2로 매우 작은 값을 부여한 파란색 선을 보자. 모든 개별 데이터들을 다 잡아내려고 하기 위해 매우 복잡한 함수를 그리는 것을 볼 수 있다. 따라서 이로 인해 오버피팅이 발생하게 된다. 이번엔 bandwidth값을 3.0으로 크게 부여한 초록색 선을 보자. 이번엔 개별 데이터들을 대충 대충 학습하는 듯한(?) 느낌의 oversmoothing된 함수를 그리는 것을 볼 수 있다. 따라서 언더피팅이 발생하게 된다.

 

추가적으로 h값 즉, bandwidth 적정값을 산출해내기 위한 공식도 따로 존재한다고 한다. 이는 L2 risk function(cost function)이라고 하며 MISE(Mean Integrated Square Error)라고도 부른다. 아마 개별 커널 함수들을 합하는 연산이 들어가 있기 때문에 공식에 적분의 기호가 들어가 있는 듯 하다. 이에 대한 자세한 설명은 여기를 참고하자.

 

이제 Mean Shift를 Scikit-learn을 이용해서 구현하는 간단한 코드를 살펴보자.

# 클러스터링용 데이터 생성
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import MeanShift
# 2차원 feature와 label반환
X, y = make_blobs(n_samples=200, n_features=2, centers=3,
                 cluster_std=0.8, random_state=12)
meanshift = MeanShift(bandwidth=1.4)
# clustering 레이블 반환(이 레이블은 실제 y값 레이블과 수치적으로 동일매핑 아님!)
cluster_labels = meanshift.fit_predict(X)
print('Cluster Label 유형:',np.unique(cluster_labels))

위와 같은 코드를 입력하면 MeanShift 클러스터링 결과로 군집화 시킨 군집 레이블들이 개별 데이터에 할당된다. Scikit-learn에서는 bandwidth 적정 파라미터값을 계산해주는 API도 제공한다.

# bandwidth의 적정값을 estimate_bandwidth함수로 출력 가능
from sklearn.cluster import estimate_bandwidth
# quantile : 데이터 개수의 일정 비율만큼 샘플링하면서 meanshift하게됨
# 따라서, 데이터 개수가 엄청 많아질시 quantile값이 적으면 시간이 너무 오래걸림
bandwidth = estimate_bandwidth(X, quantile=0.25)
print("최적의 bandwidth 값:", round(bandwidth, 3))

2. DBSCAN(Density Based Spatial Clustering of Application with Noise)

DBSCAN은 특정 공간 내에 데이터 밀도 차이를 기반으로 하는 알고리즘이다. 즉, 데이터 밀도 차이를 자동으로 알고리즘이 감지하며 군집을 생성한다. 따라서 사용자가 사전에 군집 개수를 지정할 수 없다. 그래서 Non-parametric 모델에 속한다. 또한 복잡한 기하학적 분포도를 가진 데이터셋에 대해서 군집화를 잘 수행한다.

 

DBSCAN 적용하기 용이한 기하학적으로 복잡한 데이터셋 분포

 

이제 DBSCAN이 동작하는 과정에 대해서 살펴보자. 그 전에 먼저 DBSCAN의 구성요소에 대해 알아보자.

 

DBSCAN의 구성요소

 

DBSCAN은 크게 3가지 구성요소를 갖고 있다. 이 때 Eps란, 개별 포인트를 기준으로 특정 반경의 거리를 뜻한다. 

 

• Core Point : 해당 데이터 포인트 주변 반경 내에 최소 데이터 개수 이상의 다른 데이터를 가지고 있을 경우, Core point(핵심 포인트)라고 한다. (단, 반경 내에 존재해야 하는 최소 데이터 개수는 일종의 하이퍼파라미터로 설정해주어야 한다.)
• Neighbor Point : 특정 데이터 포인트 주변 반경 내에 존재하는 다른 데이터 포인트를 의미한다.
• Border Point : 특정 데이터 포인트 주변 반경 내에 최소 데이터 개수의 다른 데이터를 가져야 하는 조건을 만족하진 못하지만 Core Point가 주변 반경 내에 존재하는 경우 이를 경계(Border) 포인트라고 한다.
• Noise Point : Border Point조건도 만족하지 못하는 포인트 즉, 반경 내에 최소 개수의 다른 데이터 존재 조건도 만족하지 못하며 Neighbor Point로 Core Point도 없는 경우 

이제 본격적으로 DBSCAN의 동작 프로세스에 대해서 알아보자. 위 DBSCAN의 구성요소 그림을 예시로 들어 이해해보자.

 

1. 우선 Eps(반경 거리)와 반경 내에 존재해야 하는 최소 샘플 개수를 3개로 설정한다. 그리고 가장 왼쪽에 있는 빨간색 동그라미를 Core Point로하여 시작한다.
2. 1번에서 설정한 빨간색 Core point에서 반경 내에 존재하는 Neighbor point들 중 Core Point를 만족하는 데이터 포인트로(그림에서는 1번에서 설정한 빨간색 동그라미의 오른쪽 빨간색 동그라미들) 직접 연결이 가능하며 군집화 영역을 확장해 나간다.
3. 2번을 반복하면서 양쪽 오른쪽에 있는 노란색 동그라미인 Border Point에 다다르면 그 때 군집화 영역을 확장하는 행동을 멈춘다.
4. 그리고 주변 반경 내에 Core point를 Neighbor point로도 갖지 못하는 데이터들을 Noise point로 간주하며 이 포인트들은 어떠한 군집에도 속하지 않는 것으로 취급한다.

Scikit-learn에서 제공하는 DBSCAN API를 사용해서 파이썬으로 간단히 구현해보자. Scikit-learn에서 제공하는 DBSCAN API에서 반드시 하이퍼파라미터로 설정해주어야 하는 값들은 바로 Eps(반경 거리)와 min_samples(반경 내에 존재해야 하는 다른 데이터 최소 개수) 두 가지이다. 이 때 min_samples 값을 지정해줄 때 주의해야 할 점은 Scikit-learn에서는 자신 데이터를 포함한 값을 지정해주어야 한다. 예를 들어, 최소 개수를 5개로 설정하고 싶다면 자신을 합쳐서 min_samples=6 으로 지정해주어야 한다는 뜻이다.

from sklearn.cluster import DBSCAN
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

iris = load_iris()
feature_names = ['sepal_length','sepal_width','petal_length','petal_width']

iris_df = pd.DataFrame(data=iris.data, columns=feature_names)
iris_df['target'] = iris.target

dbscan = DBSCAN(eps=0.6, min_samples=8, metric='euclidean')
#DBSCAN도 마찬가지로 fit_predict로 클러스터링 레이블 반환
dbscan_label = dbscan.fit_predict(iris.data)
iris_df['dbscan_label'] = dbscan_label

#원본 데이터의 class와 클러스터링 레이블 비교하면서 어떻게 클러스터링 됬는지 확인
iris_result = iris_df.groupby(['target'])['dbscan_label'].value_counts()
print(iris_result)

3. Silhouette metric for clustering

지금 소개할 개념은 군집화 모델이 아닌 군집화 모델의 성능을 평가하기 위한 일종의 지표이다. 바로 Silhouette(실루엣)지표이다. 물론 Clustering 모델들이 정답이 없는 상태로 학습하는 Unsupervised Learning(비지도 학습) 모델이지만 이러한 비지도 학습 모델도 어쨌거나 정확도의 성능을 평가해야 하기 때문에 결국에는 정답이 필수적으로 필요하다. 

 

하지만 실루엣 지표는 정답을 갖고와서 군집화 모델을 정답과 비교하며 평가한다기 보다는 군집화를 얼마나 잘 수행했는지를 살펴보는 지표 중 하나로 볼 수 있다. 

 

다시 말해, 실루엣 지표는 각 군집 간의 거리가 얼마나 효율적으로 분리되어 있는지를 나타내며 '실루엣 계수(Coefficient)'를 기반으로 계산을 한다. 개별 데이터가 갖는 실루엣 계수는 해당 데이터가 같은 군집 내의 데이터와 얼마나 가깝게 군집화되어 있고, 다른 군집에 있는 데이터와는 얼마나 멀리 분리되어 있는지를 나타내는 지표이다. 따라서 간단하게 실루엣 지표의 공식을 나타내면 다음과 같다.

 

실루엣 지표 공식

 

a(i)는 i번째 데이터에서 자신이 속한 군집 내의 다른 데이터들과의 평균적인 거리를 뜻한다. b(i)는 i번째 데이터에서 가장 가까운 다른 군집내의 다른 데이터들과의 평균적인 거리를 뜻한다. 이 두 값을 뺀 b(i) - a(i)는 두 군집 간의 거리가 얼마나 떨어져 있는 것을 의미하며 정규화시켜주기 위해 a(i) 와 b(i) 중 큰 값인 max{a(i), b(i)} 를 나누어준다. 실루엣 지표는 값의 크기에 따라 다음과 같은 의미를 지닌다.

 

• 1에 가까운 값 : 근처의 군집과의 거리가 멀다는 의미
• 0에 가까운 값 : 근처의 군집과의 거리가 가깝다는 의미
• -(음수)인 값 : 원래 A라는 군집내의 데이터인데 다른 B 군집에 할당됬다는 의미

이제 Scikit-learn을 이용해 실루엣 지표를 계산해보자. Scikit-learn에서 실루엣 API를 2가지 함수로 제공을 한다.

 

• silhouette_samples : 모든 데이터포인트들 각각의 실루엣 계수를 계산해주어 반환한다.
• silhouette_score : 전체 데이터의 실루엣 계수값들의 평균값을 반환한다. 이 값이 바로 -1~1사이의 값으로 정규화 시켜준 값이다.

from sklearn.preprocessing import scale
from sklearn.datasets import load_iris
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_samples, silhouette_score
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd

iris = load_iris()
feature_names = ['sepal_length','sepal_width','petal_length','petal_width']
irisDF = pd.DataFrame(data=iris.data, columns=feature_names)
# fit함수의 labels_속성에 클러스터링된 값들 있음
kmeans = KMeans(n_clusters=3, init='k-means++',
               max_iter=300, random_state=42).fit(irisDF)

irisDF['cluster'] = kmeans.labels_
# 모든 데이터들 실루엣 계수값들의 평균 계수값 출력
average_coef = silhouette_score(iris.data, irisDF['cluster'])
print(f'평균 실루엣 계수값: {average_coef:.4f}')

하지만 주의해야 할 점이 하나 있다. 실루엣 계수값이 높다고 해서 반드시 클러스터링이 잘 수행됬다는 보장은 없다. 반드시 실루엣 계수값을 본 후 클러스터링된 데이터들을 시각화 해보아야 한다. 다음은 실루엣 score가 높다고 좋은 클러스터링을 보장할 순 없다는 것을 보여주는 그림이다. 다른 그림도 보고 싶다면 공식문서를 참고해보자.

 

실루엣 점수가 좋다고 좋은 클러스터링을 보장하진 못한다.

# Reference

파이썬 머신러닝 완벽 가이드

Wikipedia