Mean Shift

데이터 포인트들의 밀도를 추정하여 밀도가 높은 방향으로 이동하며 군집 중심을 찾는 비모수적 군집화 알고리즘

각 데이터 포인트에서 주변 데이터 포인트의 평균을 계산하고, 이 평균으로 데이터 포인트를 업데이트하는 과정을 반복함으로써, 데이터 포인트들이 밀도가 높은 영역으로 이동하게 되어 클러스터링을 수행한다.

Mean Shift

---

---

• 각 sample 을 starting point 로, 주변에 data 가 가장 concentrated 된 곳으로 shift 하는 것을 converge 할 때 까지 반복

• 모든 data 에 대해 converge point 를 계한하여, number of cluster 를 결정

• 각 샘플들을 가장 가까운 centroid point 를 가진 cluster 로 assignment.

• K-means algorithm 과 다르게 cluster 의 갯수에 대한 hyper-parameter 가 필요하지 않는다.

• That model is Non-Parametric method

• Sliding window’s size 를 조절해 주변 어느 정도까지 볼 지 결정해야 한다.

• KDE (Kernel Density Estimation) 를 통해 maximum density point 를 찾는다.

Histogram

• Estimate of density from Non-Parametric methods, simply used histogram

• But Due to Boundary of Bin, they have tended to discontinuity

Kernel Density Estimation

Kernel function 을 통해 any variance 의 probability of density function 를 estimate 하는 method

Each samples 에 kernel function 을 applicative 한 값을 모두 합한 뒤, 데이터의 개수로 나누어 probability of density function 를 estimate.

$\textrm{KDE}=\frac1{nh}\sum^n_{i=1}K(\frac{x-x_1}h)$

$h$ 는 kernel function 의 bandwidth parameter 로, 뾰족한 형태 혹은 완만한 형태일 지 결정

대표적인 Kernel function 으로 Gaussian distribution function 이 사용됨.

Set average is Observed value $x_i$, and Standard deviation is $h$

개별 샘플들에 kernel function 을 applicative 한 값을 모두 합한 뒤, 데이터 갯수로 나누어 probability density function 를 추정

Figure 1

Figure 2

$h$ 값이 작을수록, 뾰족한 Gaussian kernel function

• Over-fitting problem (Increasing number of cluster)

$h$ 값이 클수록, deviation 이 큰 완만한 kernel function

• Under-fitting problem (Decreasing number of cluster)

Hyper-parameter, $h$ 에 대한 optimum value 를 찾아야 한다.

Gaussian kernel function 을 사용할 때, optimum bandwith 는 아래와 같다.

How to apply 2-Dimensional data to kernel function?

• 각 차원으로 데이터를 projection 시켜, kernel function 을 applicative 하여 density 가 가장 높은 coordinate 를 계산한다.

Limitation of Mean Shift

Sliding Window 의 size 가 bandwidth, $h$ 에 대한 선택이 필요하다.

데이터 distribution 이 specialize 한 경우, clustering learn 이 어렵다.