Mean shift

Mean shift è un metodo non parametrico per la ricerca delle mode di una funzione di densità di probabilità. Introdotto nel 1975 da Fukunanga e Hostetler, è equivalente all'applicazione della discesa del gradiente alla stima kernel di densità della distribuzione. L'algoritmo non richiede assunzioni sulla forma dei cluster e ha un singolo parametro, l'ampiezza di banda, la cui determinazione è tuttavia non banale in generale. Mean shift ha applicazioni in analisi dei cluster, elaborazione digitale delle immagini e visione artificiale.

Descrizione

Mean shift è un algoritmo iterativo per determinare il massimo locale di una funzione di densità di probabilità a partire da un dataset di campioni. Data una funzione kernel $K$ e una stima iniziale della moda $x$, ad ogni iterazione viene calcolata la media pesata della stima kernel di densità

$m(x)=\frac{\sum _{x_i\in N(x)}K(x_i-x)x_i}{\sum _{x_i\in N(x)}K(x_i-x)}$

dove $N(x)$ è l'insieme di campioni $x_i$ per i quali $K(x_i)\ne 0$. Il vettore $m(x)-x$ è detto mean shift. Il punto $x$ viene aggiornato con uno spostamento verso la media, nella direzione indicata dal vettore mean shift

$x\leftarrow m(x)$

e il procedimento viene iterato fino a convergenza, quando lo shift diventa irrilevante.

La funzione kernel è solitamente una funzione radiale di base. Alcune funzioni comuni sono la palla

$K(x)=\{\begin{array}{cc}1& \text{if}\Vert x\Vert \le \lambda \\ 0& \text{if}\Vert x\Vert >\lambda \end{array}$

la gaussiana

$K(x_i-x)=e^{-c||x_i-x|{|}^2}$

e la funzione kernel di Epanechnikov

$K(x)=\{\begin{array}{cc}\frac{D+2}{2V_D}(1-||x|{|}^2)& \text{if}\Vert x\Vert \le 1\\ 0& \text{if}\Vert x\Vert >\lambda \end{array}$

dove $V_D$ denota il volume della sfera unitaria in $D$ dimensioni.

Nonostante il diffuso utilizzo dell'algoritmo, non è nota una dimostrazione di convergenza nel caso generale. È dimostrata la convergenza nel caso unidimensionale, se la funzione kernel è differenziabile, convessa e strettamente decrescente, e nel caso multidimensionale se la funzione di densità ha un numero finito di punti stazionari isolati.

Applicazioni

Mean shift è usato come algoritmo di clustering, assegnando ogni punto del dataset alla moda della distribuzione di densità più vicina lungo la direzione determinata dal gradiente. L'algoritmo ha applicazioni nel tracking, e l'idea di base è quella di costruire per un frame una mappa di confidenza basata sull'istogramma dell'oggetto tracciato nel frame precedente, e applicare mean shift per determinare il massimo della distribuzione di confidenza nella regione prossima alla posizione precedente dell'oggetto. Un numero limitato di iterazioni di mean shift può essere usato come metodo di riduzione del rumore.