[Python ML Guide] Section 7.3(군집화 Clustering): Mean Shift

https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-%EC%99%84%EB%B2%BD%EA%B0%80%EC%9D%B4%EB%93%9C

[개정판] 파이썬 머신러닝 완벽 가이드 - 인프런 | 강의

 

 

---

1. Mean Shift

 

 

군집의 중심(Centroid)을 데이터가 모여 있는 밀도가 가장 높은 곳으로 이동

 

• Mean Shift는 특정 대역폭을 가지고 최초의 확률 밀도 중심 내 데이터의 확률 밀도 중심이 최대인 지점으로 중심을 이동
• 군집의 중심을 데이터의 확률 밀도가 최대인 지점과 일치하도록 중심을 이동

 

 

 

 

Mean Shift Clustering

 

• Mean Shift는 KDE(Kernel Density Estimation, 관측된 데이터를 기반으로 하여 모든 데이터 세트의 확률 밀도 함수를 추정)를 이용하여 데이터 포인트들이 데이터 분포가 높은 곳으로 이동하면서 군집화를 수행
• 별도의 군집화 개수를 지정하지 않으며 Mean Shift는 데이터 분포도에 기반하여 자동으로 군집화 개수를 결정

 

 

Mean Shift 수행 절차

 

• 1) 개별 데이터의 특정 반경 내에 주변 데이터를 포함한 데이터 분포도 계산
• 2) 데이터 분포도가 높은 방향으로 중심점 이동
• 3) 중심점을 따라 해당 데이터 이동
• 4) 이동된 데이터의 특정 반경내에 다시 데이터 분포 계산 후 2), 3) 스텝을 반복
• 5) 가장 분포도가 높은 곳으로 이동하면 더 이상 해당 데이터는 움직이지 않고 수렴
• 6) 모든 데이터를 1 ~ 5까지 수행하면서 군집 중심점을 찾음

 

 

특정 데이터가 반경 내의 데이터 분포 확률 밀도가 가장 높은 곳으로 이동할 때

 

주변 데이터들과의 거리값을 Kernel 함수 값으로 입력한 뒤 그 반환값을 현재 위치에서 Update 하면서 이동

 

 

 

정리

 

 

 

 

KDE (Kernel Density Estimation)

 

 

KDE는 Kernel 함수를 통해 어떤 변수의 확률 밀도 함수를 추정하는 방식

 

관측된 데이터 각각에 커널 함수를 적용한 값을 모두 더한 뒤 데이터 건수로 나누어서 확률 밀도 함수를 추정

 

• 확률 밀도 함수 PDF(Probability Density Function): 확률 변수의 분포를 나타내는 함수. 대표적으로 정규 분포, 감마 분포, t-분포 등이 있음
• 확률 밀도 함수를 알게 되면 특정 변수가 어떤 값을 갖게 될지의 확률을 알게 됨을 의미함
• 즉 확률 밀도 함수를 통해 변수의 특성(예를 들어 정규 분포의 경우 평균, 분산), 확률 분포 등 변수의 많은 요소를 알 수 있게 됨

 

 

 

확률 밀도 추정 방법

 

모수적(Parametric) 추정 

• 데이터가 특정 분포(예를 들어 가우시안 분포)를 따른다는 가정하에 데이터 분포를 찾는 방법
• Gaussian Mixture

 

비모수적(Non - Parametric) 추정

• 데이터가 특정 분포를 따르지 않는다는 가정 하에서 밀도를 추정
• 관측된 데이터만으로 확률 밀도를 찾는 방법
• KDE, Histogram

 

비모수적 밀도 추정 - Histogram

• Bin의 경계에서 불연속성이 나타남
• Bin의 크기에 따라 Histogram이 달라짐

 

 

비모수적 밀도 추정 - KDE

 

KDE는 개별 관측 데이터들에 커널함수를 적용한 뒤,

커널 함수들의 적용값들을 모두 합친 후에 개별 관측 데이터의 건수로 나누어서 확률 밀도 함수를 추정하는 방식

 

커널함수로는 대표적으로 Gaussian Distribution 함수가 사용됨

 

 

 

KDE와 가우시안 커널함수

• K: Kernel Function
  • uniform
  • gaussian 
• x: Random Variable
• $x_{i}$: 관측값
• h: Bandwidth

 

 

Gaussian Kernel Function을 적용한 KDE의 경우

• $x_{i}$: 평균
• h: 표준편차
• 최적의 bandwidth = $1.06 \sigma  n^{\frac {-1} {5}}$

 

 

 

 

Bandwidth에 따른 KDE의 변화

 

• 작은 h값은 좁고 spike한 KDE로 변동성이 큰 PDF를 추정: Overfitting
  • 개별 데이터의 특성을 잘 반영
• 큰 h값은 과도하게 smoothing된 KDE로 단순화된 PDF를 추정: Underfitting
  • 개별 데이터의 특성을 무시

 

 

 

 

Mean Shift

• Bandwidth가 클수록 적은 수의 Clustering 중심점
  • 개별 데이터의 특성을 덜 반영
• Bandwidth가 작을수록 많은 수의 Clustering 중심점
  • 개별 데이터의 특성을 더 반영
• 군집의 개수를 지정하지 않으며, Bandwidth의 크기에 따라 군집화를 수행

 

 

 

 

 

---

2. Mean Shift @ Scikit - Learn

 

 

Mean Shift w/ Scikit - Learn 

 

 

• Scikit - Learn은 Mean Shift 군집화를 위해 MeanShift 클래스를 제공

 

• MeanShift 클래스의 가장 중요한 초기화 파라미터는 bandwidth이며 해당 파라미터는 밀도 중심으로 이동할 때 사용되는 커널함수의 bandwidth임
  • 이 bandwidth를 어떻게 설정하느냐에 따라 군집화 성능이 달라짐

 

• 최적의 bandwidth 계산을 위해 Scikit - Learn은 estimate_bandwidth() 함수를 제공

 

 

 

---

3. 실습 - KDE 

 

 

 

 

sns.distplot()

• Kernel Density Plot의 구현 방식
• kde, hist, rug가 모두 합쳐짐

 

seaborn의 distplot()을 이용하여 KDE 시각화

import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
%matplotlib inline

sns.set(color_codes=True)

np.random.seed(0)
x = np.random.normal(0, 1, size=30)
print(x)
sns.distplot(x)

 

 

• rug: 그래프 하단에 데이터의 밀집도를 표시

sns.distplot(x, rug=True)

 

 

• kde: 추정한 확률 밀도 함수를 표시

sns.distplot(x, kde=False, rug=True)

 

• hist: Histogram을 표시

sns.distplot(x, hist=False, rug=True)

 

 

개별 관측 데이터에 대해 가우시안 커널 함수를 적용

• KDE는 개별 관측 데이터들에 커널함수를 적용한 뒤
• 커널 함수들의 적용값들을 모두 합친 후에 개별 관측 데이터의 건수로 나누어서 확률 밀도 함수를 추정하는 방식
• 최적의 bandwidth = $1.06 \sigma  n^{\frac {-1} {5}}$

 

 

 

kernel = stats.norm(관측값, 표준편차).pdf(변환값)

 

• KDE는 개별 관측 데이터들에 커널함수를 적용한 뒤
• scipy의 stats package 밑에 norm과 pdf를 호출: Gaussian 확률밀도 함수를 가지는 PDF 값을 반환

from scipy import stats

# x = np.random.normal(0, 1, size=30)
bandwidth = 1.06 * x.std() * x.size ** (-1 / 5.0)
support = np.linspace(-4, 4, 200)

kernels = []
for x_i in x:
    kernel = stats.norm(x_i, bandwidth).pdf(support)
    kernels.append(kernel)
    plt.plot(support, kernel, color="r")

sns.rugplot(x, color=".2", linewidth=3)

 

개별 데이터셋을 평균으로 가지는 Gaussian Kernel Function을 생성

 

 

• 커널 함수들의 적용값들을 모두 합친 후에 개별 관측 데이터의 건수로 나누어서 확률 밀도 함수를 추정하는 방식

from scipy.integrate import trapz

density = np.sum(kernels, axis=0)
density /= trapz(density, support)
plt.plot(support, density)

 

• seaborn은 kdeplot()으로 kde 곡선만 그릴 수 있음

sns.kdeplot(x, shade=True)

 

 

• bandwidth에 따른 KDE 변화

sns.kdeplot(x)
sns.kdeplot(x, bw=0.2, label="bw: 0.2")
sns.kdeplot(x, bw=2, label="bw: 2")
plt.legend()

 

 

 

 

---

4. 실습 - Mean Shift

 

make_blobs()를 이용하여 2개의 feature와 3개의 군집 중심점을 가지는 임의의 데이터 200개를 생성하고

MeanShift를 이용하여 군집화 수행

 

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.8, random_state=0
)

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

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

 

• 커널함수의 bandwidth 크기를 1로 약간 증가 후에 Mean Shift 군집화 재수행

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

cluster labels 유형: [0 1 2]

 

 

estimate_bandwidth(X_features, quantile=0.3)

• 최적의 bandwidth 값을 계산
• quantile: Sampling하는 데이터의 개수들을 필터링할 때 사용
  • 0 에서 1 사이의 값
  • 클수록 더 많은 데이터가 샘플링 시 제외됨
  • 즉 데이터가 많을수록 quantile 값을 키워주는 것이 중요

 

• 최적의 bandwidth 값을 estimate_bandwidth()로 계산한 뒤에 다시 군집화 수행

from sklearn.cluster import estimate_bandwidth

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

bandwidth 값: 1.689

 

import pandas as pd

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

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

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

 cluster labels 유형: [0 1 2]

 

• MeanShift 군집화 결과 시각화

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]
    # 군집별로 다른 marker로 scatter plot 적용
    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='white',
                edgecolor='k', 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()

 

• 실제 데이터와 예측된 군집화가 얼마나 매칭하는지

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

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

 

 

MeanShift Clustering의 가장 큰 단점은 Bandwidth 값 정하는 것이다

 

따라서 일반적으로 Data Mining보다는 영상 쪽에 특히 Object Tracking에 사용됨