-목차-
1. 평균 이동(Mean Shift)의 개요
평균 이동(Mean Shift)은 K-means와 유사하게 중심(centroid)을 cluster의 중심으로 지속적으로 움직이면서 군집화를 수행한다. 하지만 K-means가 중심에 소속된 데이터의 평균 거리 중심으로 이동하는데 반해, 평균 이동은 중심을 데이터가 모여 있는 밀도가 가장 높은 곳으로 이동시킨다.
평균 이동 군집화는 데이터의 분포도를 이용해 cluster의 중심점을 찾는다. 중심점은 데이터 포인트가 모여있는 곳이라는 생각에서 착안한 것이며 이를 위해 확률 밀도 함수(probability density function)를 이용한다. 가장 집중적으로 데이터가 모여있어 확률 밀도 함수가 피크인 점을 중심점으로 선정하며 일반적으로 주어진 모델의 확률 밀도 함수를 찾기 위해 KDE(Kernel Density Estimation)을 이용한다.
평균 이동 군집화는 특정 데이터를 반경 내의 데이터 분포 확률 밀도가 가장 높은 곳으로 이동하기 위해 주변 데이터와의 거리 값을 KDE 함수 값으로 입력한 뒤 그 반환 값을 현재 위치에서 업데이트하면서 이동하는 방식을 취한다.
평균 이동 군집화의 알고리즘은 다음과 같다.
- 개별 데이터의 특정 반경 내에 주변 데이터를 포함한 데이터 분포도를 KDE 함수를 통해 계산
- KDE로 계산된 데이터 분포도가 높은 방향으로 데이터 이동
- 모든 데이터를 1~2까지 수행하면서 데이터를 이동, 개별 데이터들이 군집 중심점으로 모임
- 지정된 반복(iteration) 횟수만큼 전체 데이터에 대해서 KDE 기반으로 데이터를 이동시키면서 군집화 수행
- 개별 데이터들이 모인 중심점을 군집 중심점으로 설정
2. 커널 함수(Kernal Function)
KDE를 이해하기 위해선 먼저 커널 함수에 대한 이해가 필요하다. 수학적으로 커널함수는 원점을 중심으로 대칭이면서 적분 값이 1인 non-Negative 함수로 정의된다. 가우시안(Gaussian) Epanechnikov, uniform 함수 등이 대표적인 커널 함수들이다.
커널 함수의정의
- \(\int_{-\infty }^{\infty }K(u)du = 1\)
- \(K(u) = K(-u)\,for \,all\, values \,of \, u \)
- \(Non\,negative\)
\[K(u) = \frac{1}{\sqrt{2\pi }}e^{-u^2/2}\]
3. KDE(Kernal Density Estimation)
KDE는 커널(kernel) 함수를 통해 어떤 변수의 확률 밀도 함수를 추정하는 대표적인 방법이다. 관측된 데이터 각각에 커널 함수를 적용한 값을 모두 더한 뒤에 데이터 건수로 나눠 확률 밀도 함수를 추정한다. 대표적인 커널 함수로서 가우시안 분포 함수가 사용된다.
다음 그림에서 초록 선은 개별 관측 데이터에 가우시안 커널 함수를 적용한 것이고 파란 선은 적용 값을 모두 더한 KDE 결과이다.
KDE는 다음과 같은 커널 함수 식으로 표현된다. 다음 식에서 \(K\)는 커널 함수, \(x\)는 확률 별수, \(x_i\)는 관측값 \(h\)는 대역폭(bandwidth)이다.
\[KDE = \frac{1}{n}\sum_{i=1}^{n}K_{h}(x-x_i) = \frac{1}{nh}\sum_{i=1}^{n}K(\frac{x-x_i}{h})\]
위 수식을 직관적으로 이해하면 다음과 같다.
- 관측 데이터 각각마다 해당 데이터 값을 중심으로 하는 커널 함수를 생성한다. : \(K(x-x_i)\)
- 이렇게 만들어진 커널 함수들을 모두 더한 후 전체 데이터로 나눈다.
대역폭 \(h\)는 KDE 형태를 부드러운(또는 뾰족한) 형태로 평활화(Smoothing)하는 데 적용되며, 이 \(h\)를 어떻게 설정하느냐에 따라 확률 밀도 추정 성능을 크게 좌우할 수 있다. 아래 그림은 \(h\)값을 증가됨에 따라 변화되는 KDE를 나타낸다.
작은 \(h\)값은 좁고 뾰족한 KDE를 가지게 되며, 이는 변동성이 큰 방식으로 확률 밀도 함수를 추정하므로 과적합(over-fitting)하기 쉽다. 반대로 매우 큰 \(h\)값은 과도하게 평활화(Smooting)된 KDE로 인해 지나치게 단순화된 방식으로 확률 밀도 함수를 추정하며 결과적으로 과소 적합(undfer-fitting) 하기 쉽다. 따라서 적절한 KDE의 대역 폭 h를 계산하는 것은 KDE기반의 평균 이동 군집화에서 매우 중요하다.
일반적으로 평균 이동 군집화는 대역폭이 클수록 평활화된 KDE로 인해 적은 수의 중심점을 가지며 대역폭이 적을수록 많은 수의 중심점을 가진다. 또한 평균 이동 군집화는 cluster의 개수를 지정하지 않으며, 오직 대역폭의 크기에 따라 군집화를 수행한다.
참고 자료
https://sungkee-book.tistory.com/2
https://en.wikipedia.org/wiki/Kernel_(statistics)#Kernel_functions_in_common_use
'머신러닝, 딥러닝 > Clustering' 카테고리의 다른 글
| [ML] DBSCAN(Density Based Spatial Clustering of Applications with Noise) (0) | 2022.03.02 |
|---|---|
| [ML] GMM(Gaussian Mixture Model) (0) | 2022.03.02 |
| [ML] K-평균(K-means) 알고리즘 (0) | 2022.03.01 |
댓글