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})\neq 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{cases}1&{\text{if}}\ \|x\|\leq \lambda \\0&{\text{if}}\ \|x\|>\lambda \\\end{cases}}

la gaussiana

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

e la funzione kernel di Epanechnikov

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 $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.

Note

1 2 Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, n. 8, agosto 1995, pp. 790-799, DOI:10.1109/34.400568.
1 2 3 Keinosuke Fukunaga e Larry D. Hostetler, The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition, in IEEE Transactions on Information Theory, vol. 21, n. 1, gennaio 1975, pp. 32-40, DOI:10.1109/TIT.1975.1055330.
↑ Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011
↑ Dorin Comaniciu e Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, n. 5, maggio 2002, pp. 603-619, DOI:10.1109/34.1000236.
1 2 3 Youness Aliyari Ghassabeh, A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel, in Journal of Multivariate Analysis, vol. 135, 1º marzo 2015, pp. 1-10, DOI:10.1016/j.jmva.2014.11.009.
↑ Youness Aliyari Ghassabeh, On the convergence of the mean shift algorithm in the one-dimensional space, in Pattern Recognition Letters, vol. 34, n. 12, 1º settembre 2013, pp. 1423-1427, DOI:10.1016/j.patrec.2013.05.004, arXiv:1407.2961.
↑ Xiangru Li, Zhanyi Hu e Fuchao Wu, A note on the convergence of the mean shift, in Pattern Recognition, vol. 40, n. 6, 1º giugno 2007, pp. 1756-1762, DOI:10.1016/j.patcog.2006.10.016.
↑ Dorin Comaniciu, Visvanathan Ramesh e Peter Meer, Kernel-based Object Tracking, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, n. 5, maggio 2003, pp. 564-575, DOI:10.1109/tpami.2003.1195991.
↑ Shai Avidan, Ensemble Tracking, in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), vol. 2, San Diego, California, IEEE, 2005, pp. 494-501, DOI:10.1109/CVPR.2005.144, ISBN 978-0-7695-2372-9.
↑ Gary Bradski (1998) Computer Vision Face Tracking For Use in a Perceptual User Interface Archiviato il 17 aprile 2012 in Internet Archive., Intel Technology Journal, No. Q2.
↑ Ebrahim Emami, Online failure detection and correction for CAMShift tracking algorithm, in 2013 Iranian Conference on Machine Vision and Image Processing (MVIP), vol. 2, IEEE, 2013, pp. 180-183, DOI:10.1109/IranianMVIP.2013.6779974, ISBN 978-1-4673-6184-2.

Portale Informatica

Portale Matematica

Portale Statistica

[PAMI95-1] 1 2 Yizong Cheng, Mean Shift, Mode Seeking, and Clustering, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, n. 8, agosto 1995, pp. 790-799, DOI:10.1109/34.400568.

[Fukunaga-2] 1 2 3 Keinosuke Fukunaga e Larry D. Hostetler, The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition, in IEEE Transactions on Information Theory, vol. 21, n. 1, gennaio 1975, pp. 32-40, DOI:10.1109/TIT.1975.1055330.

[note3-3] Richard Szeliski, Computer Vision, Algorithms and Applications, Springer, 2011

[PAMI02-4] Dorin Comaniciu e Peter Meer, Mean Shift: A Robust Approach Toward Feature Space Analysis, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, n. 5, maggio 2002, pp. 603-619, DOI:10.1109/34.1000236.

[:0-5] 1 2 3 Youness Aliyari Ghassabeh, A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel, in Journal of Multivariate Analysis, vol. 135, 1º marzo 2015, pp. 1-10, DOI:10.1016/j.jmva.2014.11.009.

[note1-6] Youness Aliyari Ghassabeh, On the convergence of the mean shift algorithm in the one-dimensional space, in Pattern Recognition Letters, vol. 34, n. 12, 1º settembre 2013, pp. 1423-1427, DOI:10.1016/j.patrec.2013.05.004, arXiv:1407.2961.

[note2-7] Xiangru Li, Zhanyi Hu e Fuchao Wu, A note on the convergence of the mean shift, in Pattern Recognition, vol. 40, n. 6, 1º giugno 2007, pp. 1756-1762, DOI:10.1016/j.patcog.2006.10.016.

[PAMI03-8] Dorin Comaniciu, Visvanathan Ramesh e Peter Meer, Kernel-based Object Tracking, in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, n. 5, maggio 2003, pp. 564-575, DOI:10.1109/tpami.2003.1195991.

[avidan2001-9] Shai Avidan, Ensemble Tracking, in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), vol. 2, San Diego, California, IEEE, 2005, pp. 494-501, DOI:10.1109/CVPR.2005.144, ISBN 978-0-7695-2372-9.

[note4-10] Gary Bradski (1998) Computer Vision Face Tracking For Use in a Perceptual User Interface Archiviato il 17 aprile 2012 in Internet Archive., Intel Technology Journal, No. Q2.

[Emami2001-11] Ebrahim Emami, Online failure detection and correction for CAMShift tracking algorithm, in 2013 Iranian Conference on Machine Vision and Image Processing (MVIP), vol. 2, IEEE, 2013, pp. 180-183, DOI:10.1109/IranianMVIP.2013.6779974, ISBN 978-1-4673-6184-2.

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Classificazione a singola classe · Ranking · Regole di associazione · Apprendimento non supervisionato · Apprendimento semi-supervisionato · Apprendimento supervisionato · Apprendimento debolmente supervisionato · Apprendimento auto-supervisionato · Apprendimento da pochi esempi · Apprendimento gerarchico · Apprendimento per rinforzo · Apprendimento profondo · Apprendimento online · Apprendimento incrementale · Apprendimento trasduttivo · Apprendimento di rappresentazioni · Apprendimento per similarità · Apprendimento per contrasto · Concept drift · Meta-apprendimento · Dati mancanti
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · Clustering spettrale · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random field CRF · Modello di Markov nascosto · Algoritmo k-nearest neighbors (k-NN) · Ragionamento basato su casi (CBR) · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modello grafico · Rete bayesiana · Macchine a vettori di supporto (SVM) · Processo gaussiano · Modello ensemble · Boosting · Bagging · Classifier chain · Cascading · Classificatore ECOC · Stacking · Voting
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Apprendimento di varietà (manifold learning) · Estrazione di caratteristiche · Immersione localmente lineare (LLE) · Isomap · Scaling multidimensionale (MDS) · Selezione delle caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Percettrone basato su kernel · Rete neurale a funzioni base radiali (RBF net) · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Rete neurale grafica · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · PyTorch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico