평균 이동(Mean Shift)
28 Apr 2023 | Machine-Learning
평균 이동(Mean Shift) 은 K-평균과 유사하게 중심을 군집의 중심으로 지속적으로 움직이면서 군집화를 수행 합니다. 하지만 K-평균이 중심에 소속된 데이터의 평균 거리 중심으로 이동하는 데 반해, 평균 이동은 중심을 데이터가 모여 있는 밀도가 가장 높은 곳으로 이동시킵니다.
평균 이동 군집화는 데이터의 분포도를 이용 해 군집 중심점을 찾으며 군집 중심점은 데이터 포인트가 모여있는 곳이라는 생각 에서 착안하여, 이를 위해 확률 밀도 함수(probability density function)를 이용 합니다. 가장 집중적으로 데이터가 모여있어 확률 밀도 함수가 피크인 점을 군집 중심점으로 선정 하며 일반적으로 주어진 모델의 확률 밀도 함수를 찾기 위해서 KDE(Kernel Density Estimation)를 이용 합니다.
평균 이동 군집화는 특정 데이터를 반경 내의 데이터 분포 확률 밀도가 가장 높은 곳으로 이동하기 위해 주변 데이터와의 거리 값을 KDE 함수 값으로 입력한 뒤 그 반환 값을 현재 위치에서 업데이트하면서 이동하는 방식 을 취합니다. 이러한 방식을 전체 데이터에 반복적으로 적용하면서 데이터의 군집 중심점을 찾아냅니다.
KDE(Kernel Density Estimation) 는 커널(Kernel) 함수를 통해 어떤 변수의 확률 밀도 함수를 추정하는 대표적인 방법 입니다. 관측된 데이터 각각에 커널 함수를 적용한 값을 모두 더한 뒤 데이터 건수로 나눠 확률 밀도 함수를 추정 합니다. 확률 밀도 함수 PDF(Probability Density Function)는 확률 변수의 분포를 나타내는 함수로, 확률 밀도 함수를 알면 특정 변수가 어떤 값을 갖게 될지에 대한 확률을 알게 되므로 이를 통해 변수의 특성(평균, 분산 등), 확률 분포 등 변수의 많은 요소를 알 수 있습니다.
KDE는 개별 관측 데이터에 커널 함수를 적용한 뒤, 이 적용 값을 모두 더한 후 개별 관측 데이터의 건수로 나눠 확률 밀도 함수를 추정하며, 대표적인 커널 함수로서 가우시안 분포 함수가 사용됩니다. 다음 그림의 왼쪽은 개별 관측 데이터에 가우시안 커널 함수를 적용한 것이고 오른쪽은 적용 값을 모두 더한 KDE 결과입니다.
KDE는 다음과 같은 커널 함수식으로 표현됩니다. 다음 식에서 $K$ 는 커널 함수, $x$는 확률 변숫값, $x_i$ 는 관측값, $h$ 는 대역폭(bandwidth) 입니다.
\[KDE = \cfrac{1}{n}\sum^n_{i=1}K_h(x-x_i)=\cfrac{1}{nh}\sum^n_{i=1}K\left(\cfrac{x-x_i}{h}\right)\]
대역폭 $h$ 는 KDE 형태를 부드러운(또는 뾰족한) 형태로 평활화(Smoothing) 하는 데 적용되며, 이 $h$ 를 어떻게 설정하느냐에 따라 확률 밀도 추정 성능을 크게 좌우 할 수 있습니다.
다음 그림은 $h$ 값을 증가시키면서 변화되는 KDE 를 나타냅니다.
- 작은 값(h=1.0)
- 좁고 뾰족한 KDE를 가짐.
- 이는 변동성이 큰 방식으로 확률 밀도 함수를 추정하므로 과적합(over-fitting)하기 쉬움.
- 매우 큰 h 값(h=10)
- 과도하게 평활화(smoothing)된 KDE로 인해 지나치게 단순화된 방식으로 확률 밀도 함수를 추정
- 결과적으로 과소적합(under-fitting)하기 쉬움.
따라서 적절한 KDE의 대역폭 $h$ 를 계산하는 것 은 KDE 기반의 평균 이동(Mean Shift) 군집화에서 매우 중요 합니다.
일반적으로 평균 이동 군집화 는 대역폭이 클수록 평활화된 KDE로 인해 적은 수의 군집 중심점 을 가지며 대역폭이 적을수록 많은 수의 군집 중심점 을 가집니다. 또한 평균 이동 군집화는 군집의 개수를 지정하지 않으며, 오직 대역폭의 크기에 따라 군집화를 수행합니다.
사이킷런은 평균 이동 군집화를 위해 MeanShift 클래스를 제공합니다. MeanShift 클래스의 가장 중요한 초기화 파라미터는 bandwidth 이며 이 파라미터는 KDE 의 대역폭 $h$ 와 동일합니다. 대역폭 크기 설정이 군집화의 품질에 큰 영향 을 미치기 때문에 사이킷런은 최적의 대역폭 계산을 위해 estimate_bandwidth() 함수를 제공합니다.
다음 예제는 make_blobs() 의 cluster_std 를 0.7로 정한 3개 군집의 데이터에 대해 bandwidth 를 0.8로 설정한 평균 이동 군집화 알고리즘을 적용한 예제입니다.
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))
[output]
cluster labels 유형: [0 1 2 3 4 5]
군집이 0부터 5까지 6개로 분류됐습니다. 지나치게 세분화돼 군집화됐습니다. 일반적으로 bandwidth 값을 작게 할수록 군집 개수가 많아집니다. 이번에 bandwidth 를 살짝 높인 1.0으로 해서 MeanShift 를 수행해 보겠습니다.
meanshift = MeanShift(bandwidth=1)
cluster_labels = meanshift.fit_predict(X)
print('cluster labels 유형:', np.unique(cluster_labels))
[output]
cluster labels 유형: [0 1 2]
3개의 군집으로 잘 군집화됐습니다. 데이터의 분포 유형에 따라 bandwidth 값의 변화는 군집화 개수에 큰 영향을 미칠 수 있습니다. 따라서 MeanShift에서는 이 bandwidth를 최적화 값으로 설정하는 것이 매우 중요합니다.
사이킷런은 최적화된 bandwidth 값을 찾기 위해서 estimate_bandwidth() 함수를 제공하며, 파라미터로 피처 데이터 세트를 입력해주면 최적화된 bandwidth 값을 반환해줍니다.
from sklearn.cluster import estimate_bandwidth
bandwidth = estimate_bandwidth(X)
print('bandwidth 값:', round(bandwidth, 3))
[output]
bandwidth 값: 1.816
estimate_bandwidth() 로 측정된 bandwidth 를 평균 이동 입력값으로 적용해 동일한 make_blobs() 데이터 세트에 군집화를 수행해 보겠습니다.
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))
[output]
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 값을 비교해 보겠습니다. Target 값과 군집 label 값이 1:1로 잘 매칭됐습니다.
print(clusterDF.groupby('target')['meanshift_label'].value_counts())
[output]
target meanshift_label
0 0 67
1 1 67
2 2 66
Name: meanshift_label, dtype: int64
평균 이동의 장점 은 데이터 세트의 형태를 특정 형태로 가정한다든가, 특정 분포도 기반의 모델로 가정하지 않기 때문에 좀 더 유연한 군집화가 가능 하고, 이상치의 영향력도 크지 않으며, 미리 군집의 개수를 정할 필요도 없습니다. 하지만 알고리즘의 수행 시간이 오래 걸리고 무엇보다도 bandwidth의 크기에 따른 군집화 영향도가 매우 큽니다.
평균 이동(Mean Shift) 은 K-평균과 유사하게 중심을 군집의 중심으로 지속적으로 움직이면서 군집화를 수행 합니다. 하지만 K-평균이 중심에 소속된 데이터의 평균 거리 중심으로 이동하는 데 반해, 평균 이동은 중심을 데이터가 모여 있는 밀도가 가장 높은 곳으로 이동시킵니다.
평균 이동 군집화는 데이터의 분포도를 이용 해 군집 중심점을 찾으며 군집 중심점은 데이터 포인트가 모여있는 곳이라는 생각 에서 착안하여, 이를 위해 확률 밀도 함수(probability density function)를 이용 합니다. 가장 집중적으로 데이터가 모여있어 확률 밀도 함수가 피크인 점을 군집 중심점으로 선정 하며 일반적으로 주어진 모델의 확률 밀도 함수를 찾기 위해서 KDE(Kernel Density Estimation)를 이용 합니다.
평균 이동 군집화는 특정 데이터를 반경 내의 데이터 분포 확률 밀도가 가장 높은 곳으로 이동하기 위해 주변 데이터와의 거리 값을 KDE 함수 값으로 입력한 뒤 그 반환 값을 현재 위치에서 업데이트하면서 이동하는 방식 을 취합니다. 이러한 방식을 전체 데이터에 반복적으로 적용하면서 데이터의 군집 중심점을 찾아냅니다.
KDE(Kernel Density Estimation) 는 커널(Kernel) 함수를 통해 어떤 변수의 확률 밀도 함수를 추정하는 대표적인 방법 입니다. 관측된 데이터 각각에 커널 함수를 적용한 값을 모두 더한 뒤 데이터 건수로 나눠 확률 밀도 함수를 추정 합니다. 확률 밀도 함수 PDF(Probability Density Function)는 확률 변수의 분포를 나타내는 함수로, 확률 밀도 함수를 알면 특정 변수가 어떤 값을 갖게 될지에 대한 확률을 알게 되므로 이를 통해 변수의 특성(평균, 분산 등), 확률 분포 등 변수의 많은 요소를 알 수 있습니다.
KDE는 개별 관측 데이터에 커널 함수를 적용한 뒤, 이 적용 값을 모두 더한 후 개별 관측 데이터의 건수로 나눠 확률 밀도 함수를 추정하며, 대표적인 커널 함수로서 가우시안 분포 함수가 사용됩니다. 다음 그림의 왼쪽은 개별 관측 데이터에 가우시안 커널 함수를 적용한 것이고 오른쪽은 적용 값을 모두 더한 KDE 결과입니다.
KDE는 다음과 같은 커널 함수식으로 표현됩니다. 다음 식에서 $K$ 는 커널 함수, $x$는 확률 변숫값, $x_i$ 는 관측값, $h$ 는 대역폭(bandwidth) 입니다.
\[KDE = \cfrac{1}{n}\sum^n_{i=1}K_h(x-x_i)=\cfrac{1}{nh}\sum^n_{i=1}K\left(\cfrac{x-x_i}{h}\right)\]대역폭 $h$ 는 KDE 형태를 부드러운(또는 뾰족한) 형태로 평활화(Smoothing) 하는 데 적용되며, 이 $h$ 를 어떻게 설정하느냐에 따라 확률 밀도 추정 성능을 크게 좌우 할 수 있습니다.
다음 그림은 $h$ 값을 증가시키면서 변화되는 KDE 를 나타냅니다.
- 작은 값(h=1.0)
- 좁고 뾰족한 KDE를 가짐.
- 이는 변동성이 큰 방식으로 확률 밀도 함수를 추정하므로 과적합(over-fitting)하기 쉬움.
- 매우 큰 h 값(h=10)
- 과도하게 평활화(smoothing)된 KDE로 인해 지나치게 단순화된 방식으로 확률 밀도 함수를 추정
- 결과적으로 과소적합(under-fitting)하기 쉬움.
따라서 적절한 KDE의 대역폭 $h$ 를 계산하는 것 은 KDE 기반의 평균 이동(Mean Shift) 군집화에서 매우 중요 합니다.
일반적으로 평균 이동 군집화 는 대역폭이 클수록 평활화된 KDE로 인해 적은 수의 군집 중심점 을 가지며 대역폭이 적을수록 많은 수의 군집 중심점 을 가집니다. 또한 평균 이동 군집화는 군집의 개수를 지정하지 않으며, 오직 대역폭의 크기에 따라 군집화를 수행합니다.
사이킷런은 평균 이동 군집화를 위해 MeanShift 클래스를 제공합니다. MeanShift 클래스의 가장 중요한 초기화 파라미터는 bandwidth 이며 이 파라미터는 KDE 의 대역폭 $h$ 와 동일합니다. 대역폭 크기 설정이 군집화의 품질에 큰 영향 을 미치기 때문에 사이킷런은 최적의 대역폭 계산을 위해 estimate_bandwidth() 함수를 제공합니다.
다음 예제는 make_blobs() 의 cluster_std 를 0.7로 정한 3개 군집의 데이터에 대해 bandwidth 를 0.8로 설정한 평균 이동 군집화 알고리즘을 적용한 예제입니다.
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))
[output]
cluster labels 유형: [0 1 2 3 4 5]
군집이 0부터 5까지 6개로 분류됐습니다. 지나치게 세분화돼 군집화됐습니다. 일반적으로 bandwidth 값을 작게 할수록 군집 개수가 많아집니다. 이번에 bandwidth 를 살짝 높인 1.0으로 해서 MeanShift 를 수행해 보겠습니다.
meanshift = MeanShift(bandwidth=1)
cluster_labels = meanshift.fit_predict(X)
print('cluster labels 유형:', np.unique(cluster_labels))
[output]
cluster labels 유형: [0 1 2]
3개의 군집으로 잘 군집화됐습니다. 데이터의 분포 유형에 따라 bandwidth 값의 변화는 군집화 개수에 큰 영향을 미칠 수 있습니다. 따라서 MeanShift에서는 이 bandwidth를 최적화 값으로 설정하는 것이 매우 중요합니다.
사이킷런은 최적화된 bandwidth 값을 찾기 위해서 estimate_bandwidth() 함수를 제공하며, 파라미터로 피처 데이터 세트를 입력해주면 최적화된 bandwidth 값을 반환해줍니다.
from sklearn.cluster import estimate_bandwidth
bandwidth = estimate_bandwidth(X)
print('bandwidth 값:', round(bandwidth, 3))
[output]
bandwidth 값: 1.816
estimate_bandwidth() 로 측정된 bandwidth 를 평균 이동 입력값으로 적용해 동일한 make_blobs() 데이터 세트에 군집화를 수행해 보겠습니다.
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))
[output]
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 값을 비교해 보겠습니다. Target 값과 군집 label 값이 1:1로 잘 매칭됐습니다.
print(clusterDF.groupby('target')['meanshift_label'].value_counts())
[output]
target meanshift_label
0 0 67
1 1 67
2 2 66
Name: meanshift_label, dtype: int64
평균 이동의 장점 은 데이터 세트의 형태를 특정 형태로 가정한다든가, 특정 분포도 기반의 모델로 가정하지 않기 때문에 좀 더 유연한 군집화가 가능 하고, 이상치의 영향력도 크지 않으며, 미리 군집의 개수를 정할 필요도 없습니다. 하지만 알고리즘의 수행 시간이 오래 걸리고 무엇보다도 bandwidth의 크기에 따른 군집화 영향도가 매우 큽니다.