Worldlex Wiki Détails
Soit data un ensemble fini plongé dans l' espace euclidien de dimension . Soit un noyau plat qui est la fonction caractéristique de la -boule dans ,
\\lambda\\\\ \\end{cases} " 
À chaque itération de l'algorithme, l' opération est effectuée simultanément pour tous les échantillons . La première question est donc de savoir comment estimer la fonction de densité à partir d'un ensemble clairsemé d'échantillons. Une des approches les plus simples consiste à lisser les données, par exemple en les convoluant avec un noyau de largeur fixe .
où représentent les échantillons d'entrée et la fonction noyau (ou fenêtre de Parzen ). est le seul paramètre de l'algorithme et est appelé la largeur de bande. Cette approche est connue sous le nom d'estimation de densité par noyau ou technique de la fenêtre de Parzen. Une fois calculé à partir de l'équation ci-dessus, on peut trouver ses maxima locaux en utilisant la méthode de la montée de gradient ou une autre technique d'optimisation. Le problème de cette approche « par force brute » est que, pour les grandes dimensions, l'évaluation sur l'ensemble de l'espace de recherche devient prohibitive en termes de calcul. L'algorithme Mean Shift utilise plutôt une variante de ce que l'on appelle dans la littérature sur l'optimisation la descente de gradient à redémarrage multiple . En partant d'une estimation d'un maximum local, , qui peut être un point de données d'entrée aléatoire , Mean Shift calcule le gradient de l'estimation de densité en et effectue un pas ascendant dans cette direction.
Types de grains
Définition du noyau : Soit l’ espace euclidien de dimension n, . La norme de est un nombre non négatif, . Une fonction est dite noyau s’il existe un profil , , tel que
- k est non négatif.
- k est non croissant : si .
- k est continue par morceaux et
Les deux profils de noyau les plus fréquemment utilisés pour le décalage moyen sont :
- Noyau plat
\\lambda\\\\ \\end{cases} " 
- Noyau gaussien
où le paramètre d'écart type fonctionne comme paramètre de bande passante, .
Applications
Clustering
Considérons un ensemble de points dans un espace bidimensionnel. Supposons une fenêtre circulaire centrée en un point et de rayon comme noyau. L'algorithme Mean-Shift est un algorithme de recherche locale qui consiste à déplacer itérativement ce noyau vers une région de plus forte densité jusqu'à convergence. Chaque déplacement est défini par un vecteur de déplacement moyen. Ce vecteur pointe toujours vers la direction de l'augmentation maximale de la densité. À chaque itération, le noyau est déplacé vers le centroïde, c'est-à-dire la moyenne des points qu'il contient. La méthode de calcul de cette moyenne dépend du choix du noyau. Dans ce cas, si un noyau gaussien est choisi au lieu d'un noyau uniforme, chaque point se voit attribuer un poids qui décroît exponentiellement avec la distance au centre du noyau. À convergence, il n'existe plus de direction dans laquelle un déplacement puisse inclure davantage de points à l'intérieur du noyau.
Suivi
L'algorithme de Mean Shift peut être utilisé pour le suivi visuel. Dans sa version la plus simple, il crée une carte de confiance dans la nouvelle image à partir de l'histogramme des couleurs de l'objet dans l'image précédente, puis utilise Mean Shift pour trouver le pic de cette carte près de l'ancienne position de l'objet. La carte de confiance est une fonction de densité de probabilité sur la nouvelle image, attribuant à chaque pixel une probabilité correspondant à la probabilité que sa couleur soit présente dans l'objet de l'image précédente. Plusieurs algorithmes, tels que le suivi d'objets basé sur les noyaux , le suivi d'ensembles et CAMshift développent cette idée.
Lissage
Soient et les pixels de l'image d'entrée et de l'image filtrée de dimension dans le domaine spatial conjoint. Pour chaque pixel,
- Initialiser et
- Calculer selon jusqu'à convergence, .
- L' affectation s et r désignent respectivement les composantes spatiale et de portée d'un vecteur. Cette affectation spécifie que les données filtrées sur l'axe de position spatiale auront la composante de portée du point de convergence .
Points forts
- Mean Shift est un outil indépendant de l'application, adapté à l'analyse de données réelles.
- Ne présuppose aucune forme prédéfinie pour les groupes de données.
- Il est capable de gérer des espaces de caractéristiques arbitraires.
- La procédure repose sur le choix d'un seul paramètre : la bande passante.
- La largeur de bande/taille de fenêtre 'h' a une signification physique, contrairement à k -means .
Faiblesses
- Le choix de la taille de la fenêtre n'est pas une mince affaire.
- Une taille de fenêtre inappropriée peut entraîner la fusion de modes ou la génération de modes « superficiels » supplémentaires.
- Nécessite souvent l'utilisation d'une taille de fenêtre adaptative.
Disponibilité
Des variantes de cet algorithme se retrouvent dans les logiciels d'apprentissage automatique et de traitement d'images :
- ELKI . Outil d'exploration de données Java doté de nombreux algorithmes de clustering.
- ImageJ . Filtrage d'images à l'aide du filtre de décalage moyen.
- mlpack . Implémentation efficace basée sur un algorithme à double arbre.
- OpenCV contient une implémentation du décalage moyen via la méthode cvMeanShift.
- Boîte à outils Orfeo . Une implémentation en C++.
- L'implémentation Numpy/Python de scikit-learn utilise un arbre de boules pour une recherche efficace des points voisins.