[cite]10.1007/978-3-540-88693-8_52[/cite]

1 Introduction

Mode seeking 알고리즘으로써 주로 클러스터링에 이용되는 Mean shift, Medoid shift, Quick shift 에 대하여 알아보자. 워낙 유영한 방법들이고 일반화된 설명을 정확히 할 수 있을까 걱정되어 세세한 설명은 생략하고 그 차이만을 간단히 기록하고자 한다.

Mean shift는 기본적으로 gradient ascent 알고리즘이라 gradient 가 계산될 수 있어야지만 성립하는 방법이다. 하지만 Hilbert space 나 smooth manifold structure처럼 gradient 를 정의할 수 없는 공간도 존재한다.

대안으로 나온 Medoid shift 는 non-linear manifolds에서 Mean shift 를 부가적인 계산 없이 구현하고, 그 반복성을 제거하였지만 그 계산복잡도가 단점으로 남아있다.

2 Mode Seeking

N개의 샘플, $ x_1, x_2, ..., x_N \in X = R^d $ 이 주어졌다고 하자. Mode seeking 방법은 Parzen density estimate 방법,

$$P(x) = \frac{1}{N} \sum_{i=1}^{N}{k(x- x_i)}$$

에서 출발한다. 밀도 (density) 를 계산하고자 하는 위치 $ x $ 에서, 커널 함수 k 를 이용하여 샘플의 각 밀도 $ P(x) $ 를 짐작해 볼 수 있다. 이 때 현재 위치보다 밀도가 높은 방향, 즉 밀도의 gradient 를 따라 이동하다보면 밀도가 가장 높은 부분, 우리가 찾는 가장 밀도가 높은 mode 로 수렴할 할 것이라고 생각할 수 있다.
이러한 생각에서 출발한 세가지 방법, Mean shift, Medoid shift, Quick shift 세가지 방법들을 간단히 알아보자.

Mean Shift

mean shift는 $ k(x) $ 를 convex function $ (||x||_2^2) $ 로 바꾼 것으로, 이것은 Parzen density estimate 에 사용되는 샘플을 제한하는 범위로도 사용된다. Mean shift 에서 t번째 반복에서 현재 위치 $ y_i(t) $ 에서 갱신될 다음 위치는 아래와 같다.

$$y_i(t+1) = {\arg\max}_{y} \frac{1}{N} \sum_{j=1}^{N} { ||y - x_j||^2_2 \psi(||y_i(t) - x_j||^2_2) }$$

Mean shift 에서 반복적으로 계산되는 mode의 위치는 샘플과는 관계없이 샘플 공간 내의 한 위치로 갱신되며 최종 지점으로 이동하게 된다.

Medoid shift

1. 각 샘플마다 한 번의 계산이 필요하다는 점
2. 계산을 멈출 조건이 필요하지 않다는 점
3. 샘플 공간이 유클리디언이 아니라도 괜찮다는 점이다.

Medoid shift

일단 Medoid shift의 식을 먼저 살펴보자.

$$y_i(1) = {\arg\max}_{y \in x_1, ..., x_N} \frac{1}{N} \sum_{j=1}^{N} { d^2(y, x_j) \phi(x_j, x_i) }$$

Mean shift 와의 가장 큰 차이는 계산을 통해 갱신되는 mode의 위치가 공간상의 한 지점이 아닌 샘플들의 위치 중 하나로 제한된다는 점이다.Mean shift 와 비슷하게 계산은 이루어지나 계산된 gradient 값 (mean) 으로 mode를 이동 (shift) 하는 것이 아니라, 샘플들 중 어느 하나의 샘플을 다음 mode 값으로 사용하도록 되어있다. 선택 방법은, 현재 샘플 위치를 기준으로 나머지 샘플 위치에서의 Mean shift 를 계산하였을 때, 그 밀도가 가장 큰 샘플을 계산하는 것이다. 이는 거리 계산 함수 $ d $ 와, 커널 함수 $ \phi $ 에 영향을 받기 때문에 커널 함수의 영향 안에 있는 샘플들만이 그 선택 과정에서 고려될 것이다.

이러한 방식 덕 택에, 샘플마다 어떠한 한 샘플이 mode로써 대응되는 관계를 갖기 때문에 각 샘플마다 mode 계산이 한 번만 이루어지는 장점이 있다.

하지만 커널 함수의 종류나 그 크기가 작아질 경우, 다음 샘플로 shift되지 못하고 자기 자신을 최종 mode로 선택되는 경향이 생겨 local mode에 빠지는 현상이 잦다.

3. Fast clustering

논무에서는, Quick shift 로 넘어가기 전 Medoid shift 의 빠른 계산 법을 소개하였다. 각 샘플마다 계산 식이 확정적으로 정해지기 때문에 이를 행렬식으로 정리하고, 샘플을 제외한 상수 부분을 샘플에 종속적이지 않도록 최대한 풀어내어 계산을 단순화 하였다. 자세한 내용은 논문을 참고하도록 하자.

Quick shift

이전의 Medoid shift의 문제점을 해결하기 위하여 식을 살짝 더 수정하여보자.

$$y_i(1) = {\arg\min}_{j_i P_j \gt P_i } { D_{ij}}, P_i = \frac{1}{N} \sum_{j=1}^{N} { \phi(D_{ij}) }$$

다음 mode 의 위치를 샘플에서 선택하는 방식은 동일하다. Medoid shift 에서 과감히 샘플 간의 거리 항을 빼버렸고, 커널 함수만이 그 밀도 $ P $ 를 계산하는데 사용되었다. 그리고 다음 mode로 선택되는 샘플은 현재 밀도보다 높은 샘플들 중 가장 거리가 가까운 샘플을 선택하도록 변경되었다. 따라서, 커널 함수의 크기는 충분히 크게 잡아주기만 한다면, Medoid shift 에 비해 다음 mode 로의 이동이 아주 수월하게 될 것이다.

6. Conclusions

커널 함수를 사용하는 방법 등 여러 응용이 논문에서 소개되어있지만, 시간 및 이해 부족으로 과감히 생략하고자 한다. 자세한 내용이 궁금하다면 논문을 참고하도록 하자.