평균이동(Mean Shift)

Mean Shift

평균 이동(Mean Shift)는 K-평균과 유사하게 중심을 군집의 중심으로 지속적으로 움직이면서 군집화를 수행한다.

하지만 K-평균이 중심에 소속된 데이터의 평균 거리 중심으로 이동하는 데 반해, Mean Shift는 중심을 데이터가 모여 있는 밀도가 가장 높은 곳으로 이동시킨다.

다음 그림에서 볼 수 있듯이 평균 이동 알고리즘은 특정 대역폭을 가지고 최초의 확률 밀도 중심 내에서 데이터의 확률 밀도 중심이 더 높은 곳으로 중심을 이동한다.

평균 이동은 데이터의 분포도를 이용해 군집 중심점을 찾는다. 군집 중심점은 데이터 포인트가 모여 있는 곳이라는 생각에서 착안한 것이며 이를 위해 확률 밀도 함수(P.D.F)를 이용한다.

가장 집중적으로 데이터가 모여있어 확률 밀도 함수가 피크인 점을 군집 중심점으로 선정한다.

일반적으로 주어진 모델의 확률 밀도로 함수를 찾기 위해서 KDE(Kernel Density Estimation)을 이용한다.

평균 이동 알고리즘은 임의의 포인트에서 시작해 이러한 피크 포인트를 찾을 때까지 KDE를 반복적으로 적용하며 군집화를 수행한다.

평균 이동은 K-평균과 다르게 군집의 개수를 지정할 필요가 없다. 대역폭의 크기에 따라 알고리즘 자체에서 군집의 개수를 최적으로 정한다.

하지만 이 때문에 대역폭 크기를 어떤 값으로 설정하는가에 따라 군집화의 품질이 결정된다. 사이킷런의 평균 이동 군집화를 위해 MeanShift 클래스를 제공한다.

다음 예제는 make_blobs() 의 cluster_std를 0.8로 정한 3개 군집의 데이터에 대해 badnwidth를 0.9로 설정한 평균 이동 알고리즘을 적용한 예제이다.

import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import MeanShift

X, y = make_blobs(n_samples=200, n_features=2, centers=3, 
                  cluster_std=0.7, random_state=0)

meanshift= MeanShift(bandwidth=0.8)
cluster_labels = meanshift.fit_predict(X)
print('cluster labels 유형:', np.unique(cluster_labels))

cluster labels 유형: [0 1 2 3 4 5]

군집이 0부터 5 까지 무려 6개로 분류됐습니다.
일반적으로 bandwidth 값을 작게 할수록 군집 개수가 많아집니다. 이번에는 bandwidth를 살짝 높인 1로해서 MeanShift를 수행해 보자.

meanshift= MeanShift(bandwidth=1)
cluster_labels = meanshift.fit_predict(X)
print('cluster labels 유형:', np.unique(cluster_labels))

cluster labels 유형: [0 1 2]

3개의 군집으로 잘 군집화 됐다. 데이터의 분포 유형에 따라 bandwidth 값의 변화는 군집화 개수에 큰 영향을 미칠 수 있다.

따라서 MeanShift에서는 이 bandwidth를 최적화 값으로 설정하는 것이 매우 중요하다.

사이킷런은 최적화된 bandwidth 값을 찾기 위해 estimate_bandwidth()를 제공한다.
estimate_bandwidth()의 파라미터로 피처 데이터 셋을 입력하면 최적화된 bandwidth 값을 반환해 준다.

from sklearn.cluster import estimate_bandwidth

bandwidth = estimate_bandwidth(X)
print('bandwidth 값:', round(bandwidth,3))

bandwidth 값: 1.816

estimate_bandwidth()로 측정된 bandwidth를 평균 이동 값으로 군집화를 진행해 보자.

import pandas as pd


clusterDF = pd.DataFrame(data=X, columns=['ftr1', 'ftr2'])
clusterDF['target'] = y

# estimate_bandwidth()로 최적의 bandwidth 계산
best_bandwidth = estimate_bandwidth(X)

meanshift= MeanShift(bandwidth=best_bandwidth)
cluster_labels = meanshift.fit_predict(X)
print('cluster labels 유형:',np.unique(cluster_labels))    

cluster labels 유형: [0 1 2]

3개의 군집으로 구성됨을 알 수 있다. 구성된 3개의 군집을 시각화 해보자.
평균 이동도 K-평균과 유사하게 중심을 가지고 있으므로 cluster_centers_ 속성으로 군집 중심 좌표를 표시할 수 있다.

import matplotlib.pyplot as plt
%matplotlib inline

clusterDF['meanshift_label']  = cluster_labels
centers = meanshift.cluster_centers_
unique_labels = np.unique(cluster_labels)
markers=['o', 's', '^', 'x', '*']

for label in unique_labels:
    label_cluster = clusterDF[clusterDF['meanshift_label']==label]
    center_x_y = centers[label]
    # 군집별로 다른 마커로 산점도 적용
    plt.scatter(x=label_cluster['ftr1'], y=label_cluster['ftr2'], edgecolor='k', marker=markers[label] )

    # 군집별 중심 표현
    plt.scatter(x=center_x_y[0], y=center_x_y[1], s=200, color='gray', alpha=0.9, marker=markers[label])
    plt.scatter(x=center_x_y[0], y=center_x_y[1], s=70, color='k', edgecolor='k', marker='$%d$' % label)

plt.show()

마지막으로 target값과 군집 label 값을 비교해 보자.

print(clusterDF.groupby('target')['meanshift_label'].value_counts())

target  meanshift_label
0       0                  67
1       1                  67
2       2                  66
Name: meanshift_label, dtype: int64

Target 값과 군집 Label 값이 대부분 1:1로 잘 매칭 되었다.

평균 이동의 장점은 데이터 셋의 형태를 특정 형태로 가정한다든가, 특정 분포도 기반의 모델로 가정하지 않기 때문에 좀 더 유연한 군집화가 가능하다는 점이다.

또한 이상치의 영향력도 크지 않으며 ,미 리 군집의 개수를 정할 필요도 없다. 하지만 알고리즘의 수행 시간이 오래 걸리며, 무엇보다도 bandwidth의 크기에 따른 군집화 영향도가 매우크다.

이같은 특징 때문에 일반적으로 평균 이동 군집화 기법은 업무 기반의 데이터 셋보단느 컴퓨터 비전영역에서 잘 사용된다.
이미지나 영성 데이터에서 특정 개체를 구분하거나 움직임을 추적하는 데 뛰어난 역할을 수행하는 알고리즘이다.