[머신러닝] 군집화 # 2. 평균 이동 (Mean Shift)

이 글은 책 「파이썬 머신러닝 완벽가이드」와 다크프로그래머님의 블로그 글을 바탕으로 작성되었습니다.

평균 이동(Mean Shift)란?

- KDE 기반으로 밀도가 가장 높은 지점으로 군집 중심점을 이동시켜 군집화를 수행하는 알고리즘

 

KDE(Kernel Density Estimation, 커널 밀도 추정)이란?

1. 밀도 추정 :

관측된 데이터(표본)의 분포를 통해 원래 변수(모집단)의 확률 밀도(분포)를 추정하는 것

• 기계 학습, 확률과 통계에서의 밀도 = 확률 밀도(probability density)
• 어떤 변수 x의 밀도(density)를 추정하는 것은 x의 확률 밀도 함수 (probability density function, pdf)를 추정하는 것과 같음
• f(a)는 x=a에서의 확률 밀도 = "변수 x가 a라는 값을 가질 상대적인 확률"

확률 밀도 함수 (probability density function) [출처:다크프로그래머]

2. 밀도(density) vs 확률(probability)

• 지점 x=a에서의 함수값 f(a) → 밀도
• 구간 x ∈ [a,b]일 함수값 f(x)의 면적분 → 확률 $$P(a\leq x \leq b) = \int_{a}^{b}f(x)dx$$  

3. 모수적(parametic) vs 비모수적(non-parametic) 검정

• parametic : 확률 밀도 함수의 모델을 정해놓고, 데이터들로부터 함수의 파라미터를 추정하는 방식 (예) 관측한 데이터의 확률 밀도 함수를 정규분포라고 가정하고, 데이터들로부터 평균과 분산을 계산
• non-parametic : 모델에 대한 아무런 정보 없이 데이터만으로 분포를 추정하는 방식

4. 커널밀도추정 (KDE, Kernel Density Estimation)

• 커널함수(Kernel Function)란? 원점을 중심으로 대칭이면서 적분값이 1인 non-negative 함수 (예) 가우시안(Gaussian)

$$\int_{-\infty}^{\infty} K(x)dx = 1,\ K(-u) = K(u), K(u) \geq 0\ for\ \forall u$$

다양한 커널함수들 [출처:위키피디아]

• 관측된 데이터를 각각 커널함수에 적용한 값을 모두 더한 뒤 데이터 건수로 나누어 확률 밀도 함수를 추정하는 방법$$KDE = \frac{1}{n} \Sigma_{i=1}^{n} K_{h}(x-x_{i}) = \frac{1}{nh} \Sigma_{i=1}^{n}K(\frac{x-x_{i}}{h})$$

커널밀도추정(Kernel Density Estimation) [출처:위키피디아]

• 대역폭(bandwidth, h로 표기)

- 작은 h일수록 표족한 KDE를 가지며, 변동성 大 → 과적합 위험

- 큰 h일수록 넓은/일반화된 KDE를 가지며, 변동성 小 → 과소적합 위험

서로 다른 대역폭에 따른 KDE [출처:위키피디아]

- 적절한 대역폭을 추정하는 것이 평균 이동 군집화에서 중요

- 대역폭 계산을 위한 사이킷런 클래스 estimation_bandwidth

sklearn.cluster.estimate_bandwidth(X, *, quantile=0.3, n_samples=None, random_state=0, n_jobs=None)

- 커널함수를 가우시안으로 사용할 경우, 최적의 대역폭 파라미터 값

$$h = (\frac{4 \sigma^{5}}{3n})^{\frac{1}{5}} \approx 1.06 \sigma n^{\frac{-1}{5}} \ where\ n : 샘플의 개수,\ \sigma = 샘플의 표준편차$$

 

사이킷런 클래스 MeanShift

1. sklearn.cluster.estimation_bandwidth로 적절한 대역폭 계산

2. MeanShift 객체를 할당하여 앞서 계산한 대역폭을 인자로 넣어줌

 

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.decomposition import PCA
from sklearn.cluster import MeanShift, estimate_bandwidth

# load_iris
iris = load_iris()
cols = ['sepal_length', 'sepal_width','petal_length','petal_width']
iris_df = pd.DataFrame(iris.data, columns = cols)
iris_df['target'] = iris.target

# PCA
pca = PCA(n_components=2)
iris_pca = pca.fit_transform(iris.data)
iris_df[['ftr1','ftr2']] = iris_pca

# MeanShift
best_h = estimate_bandwidth(iris_pca)
meanshift = MeanShift(bandwidth=best_h)
iris_df['meanshift_label'] = meanshift.fit_predict(iris_pca)
centers = meanshift.cluster_centers_

# plot
markers = ['o','s']
for i, mark in enumerate(markers) :
    pca_x = iris_df[iris_df['meanshift_label']==i]['ftr1']
    pca_y = iris_df[iris_df['meanshift_label']==i]['ftr2']
    plt.scatter(pca_x, pca_y, marker=mark)
    plt.scatter(centers[i,0], centers[i,1], marker= mark, s=150, c='white', alpha=0.7, edgecolor='k')
    plt.scatter(centers[i,0], centers[i,1], marker='$%d$'%i, s=70, c='k')

plt.title('MeanShift Clustering with Iris Dataset')    
plt.xlabel('pca_x')
plt.ylabel('pca_y')
plt.grid()
plt.show()

MeanShift with Iris Dataset

• Meanshift 내부적으로 2개의 군집으로 군집화하는 것이 좋다고 판단 (KMeans - '군집별 평균 실루엣 계수의 시각화'의 결과와 동일) 

장점

• 유연한 군집화 가능 (데이터 세트의 형태나 추정 모델에 대한 가정 X)
• 이상치 영향 小, 군집 개수 설정 필요 X

 

단점

• 알고리즘 수행 시간 大
• 대역폭의 영향이 크다

 

참고 문헌

• 권철민, 「파이썬 머신러닝 완벽가이드」, 위키북스, 2020, p.409~465
• 다크 프로그래머, "Kernel Density Estimation(커널밀도추정)에 대한 이해", https://darkpgmr.tistory.com/147
• 위키피디아, "Kernel (statistics)", https://en.wikipedia.org/wiki/Kernel_(statistics)
• 위키피디아, "kernel density estimation", https://en.wikipedia.org/wiki/Kernel_density_estimation
• "sklearn.cluster.estimate_bandwidth", scikit-learn, https://scikit-learn.org/stable/modules/generated/sklearn.cluster.estimate_bandwidth.html