Mean shift 📖 Wikipedia

Mean shift è un metodo non parametrico per la ricerca delle mode di una funzione di densità di probabilità.^[1] Introdotto nel 1975 da Fukunanga e Hostetler,^[2] è equivalente all'applicazione della discesa del gradiente alla stima kernel di densità della distribuzione.^[3] 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.^[4]

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

${\displaystyle 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 ${\displaystyle N(x)}$ è l'insieme di campioni ${\displaystyle x_{i}}$ per i quali ${\displaystyle K(x_{i})\neq 0}$. Il vettore ${\displaystyle m(x)-x}$ è detto mean shift. Il punto ${\displaystyle x}$ viene aggiornato con uno spostamento verso la media, nella direzione indicata dal vettore mean shift

${\displaystyle 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

${\displaystyle K(x)={\begin{cases}1&{\text{if}}\ \|x\|\leq \lambda \\0&{\text{if}}\ \|x\|>\lambda \\\end{cases}}}$

la gaussiana

${\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}$

e la funzione kernel di Epanechnikov

${\displaystyle K(x)={\begin{cases}{\frac {D+2}{2V_{D}}}\left(1-||x||^{2}\right)&{\text{if}}\ \|x\|\leq 1\\0&{\text{if}}\ \|x\|>\lambda \\\end{cases}}}$

dove ${\displaystyle V_{D}}$ denota il volume della sfera unitaria in ${\displaystyle D}$ dimensioni.^[5]

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

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.^[2] 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.^{[8][9][10][11]} Un numero limitato di iterazioni di mean shift può essere usato come metodo di riduzione del rumore.^[2]

Portale Informatica

Portale Matematica

Portale Statistica