Mean Shift

Mean Shift란??

일정 크기(h)의 영역내에서 가장 밀도가 큰 곳으로 중심을 이동해나간다. 이렇게 이동을 계속하다보면 어느 순간 수렴을 하게되는데 수렴하러 이동하는 동안에 같은 곳으로 수렴한 데이터들을 같은 곳에 속한다고 보고 클러스터링하는 방법이다.

Mean Shift pdf나 ppt 파일에 있는 그림을 보면 이해하기가 훨씬 쉬울 것이다.

Mean Shift는 Non-parametric density estimation으로 계산한다.

parametric density estimation을 할 경우에는 아래 그림에서 처럼

c_i라는 각 Mode에서의 상수값과 평균, 분산값을 추정해야 한다.

따라서 Mean shift는 non-parametric density estimation을 하겠다.

그리고 kernel을 이용해서 해보겠다 라고 말하고 있다.

커널의 종류는 Epanechnikov, Uniform, Normal 등이 있다.

위에 식에서 P(x)가 커널에서의 밀도 값을 나타낸다. 그리고 K의 종류는 사용자가 선택할 수 있다.

일단 아래에서 왼쪽의 커널에 대한 식을 보면 각 차원에 대해서 joint pdf를 계산하는데 이것은 복잡하므로

오른쪽 식처럼 각 차원의 점을 독립적으로 보고 1차원의 vector 값만으로 계산을 한다.

근데 여기서 pdf를 추정하지 말고 우리는 gradient를 추정하자 해서 kernel density gradient estimation을 한다.

위에서 h는 아주 중요한 요소로써 mean shift의 성능을 좌우한다. h의 크기를 적절하게 정하는 것이 mean shift의 성능을
향상시키는 방법이라고 볼 수 있다.

아래식에서 x는 영역 내의 중심점이고 왼쪽은 영역내의 모든 데이터의 대한 중심점이라 할 수 있다.
그리고 제일 앞에 식은 각 커널 종류에 대한 상수 값으로서 간단한 mens shift에서는 뒤에 부분 만 사용되어
mean shift vector를 계산할 수 있다.

이렇게 찾아진 mode로 수렴하는 데이터를 같은 클러스터에 속한다고 판단한다.
하지만 찾아진 mode가 진짜 mode인지 아닌지 모르기 때문에 각 mode에서 확인 작업을 수행한다.
이것을 pruning이라고 하는데 이 작업을 통해서 saddle point에 도달했을 때 가장 높은 mode만 남기고 근처에
낮은 mode들은 제거한다.

Mean shift의 장점
 - Application independent tool
 - 실제 데이터 분석에 적합
 - 데이터 클러스터에 대한 사전 모양을 추정하지 않아도 됨
 - 임의의 featur space를 다룰 수 있다
 - 하나의 파라미터만 선택
 - h가 물리적으로 중요한 의미를 가짐(k-menas와 달리)

단점
 - window size(h)에 대해 정해진 해가 없다.(적절한 값을 찾아야 함)
 - window size가 적합하지 않으면 shallow mode가 생성 될 수 있거나 합병되는 mode가 발생 할 수 있다.