평균 이동(Mean Shift)
K-평균과 비슷하게 중심을 군집의 중심으로 지속적으로 움직이면서 군집화를 수행
K-평균이 중심에 소속된 데이터의 평균 거리 중심으로 이동하는 반면, 평균 이동 중심은 데이터가 모여 있는 밀도가 가장 높은 곳으로 이동
평균 이동 군집화를 데이터 분포도를 이용해 군집 중심점을 찾는다. 이를 위해 확률 밀도 함수(probability density function)를 이용한다. 주어진 모델의 확률 밀도 함수를 찾기 위해 KDE(Kernel Density Estimation)를 이용한다.
(표현은 확률 밀도 함수를 찾는다고 했지만 확률 밀도 함수를 정하여 밀도가
특정 데이터를 반경 내의 데이터 분포 확률 밀도가 가장 높은 곳으로 이동하기 위해 주변 데이터와의 거리 값을 KDE 함수 값으로 입력한 뒤 그 반환 값을 현재 위치에서 업데이트하면서 이동한다.
KDE는 커널 함수를 통해 어떤 변수의 확률 밀도 함수를 추정하는 대표적인 방법이다.
관측된 데이터 각각에 커널 함수를 적용한 값을 모두 더하여 데이터 건수로 나눠 확률 밀도 함수를 추정한다.
모든 커널 함수를 더하게 되면 KDE 함수가 생성되고, 각 커널 함수에서 겹치는 부분, 데이터의 밀도가 높은(밀집되어 있는)구간은 KDE 함수의 크기가 커진다.
확률 밀도 함수 PDF(Probability Density Function)는 확률 변수의 분포를 나타내는 함수로 널리 알려진 정규 분포 함수를 포함해 감마 분포, t-분포 등이 있다.
이렇게 구한 확률 밀도 함수로 특정 변수가 어떤 값을 갖게 될지에 대한 확률을 알게되므로 이를 통해 변수의 특성(정규분포의 경우 평균, 분산), 확률 분포 등 변수의 많은 요소를 알 수 있다.
대표적인 커널 함수로는 가우시안 분포 함수가 있다.
$$ 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 = 커널 함수, xi = 관측값, h = 대역폭
h(대역폭)는 KDE 형태를 부드러운(또는 뾰족한) 형태로 평활화(Smoothing)하는데 적용된다.
이 h를 어떻게 설정하느냐에 따라 확률 밀도 추정 성능을 크게 좌우 할 수 있다.
h가 작다면 좁고 뾰족한 KDE를 가지고(군집 중심점이 많다) 이는 변동성이 큰 방식으로 확률 밀도 함수를 추정하여 과적합이 발생하기 쉽다. 반대로 h가 크다면 KDE가 과도하게 평활화되어(군집 중심점이 적다) 과소적합이 발생하기 쉽다. 따라서 적절한 h값은 평균 이동 군집화에서 매우 중요하다.
평균 이동의 장점은 데이터 세트의 형태를 특정 형태로 가정한다든가, 특정 분포도 기반의 모델로 가정하지 않기 때문에 좀 더 유연한 군집화가 가능하다는 것이다. 이상치의 영향력 또한 크지 않으며, 미리 군집의 개수를 정할 필요도 없다.
하지만 알고리즘 수행 시간이 오래걸리고 bandwidth의 크기에 따른 군집화 영향도가 매우 크다.
그렇기에 평균 이동 군집화는 분석 업무 기반의 데이터 세트보단 컴퓨터 비전 영역에서 많이 사용된다.
이미지나 영상 데이터에서 특정 개체를 구분하거나 움직임을 추적하는데 뛰어난 역할을 수행하는 알고리즘이다.