Distance de Minkowski

En analyse, la distance de Minkowski, ou métrique de Minkowski, est une famille de fonctions distance sur un espace à coordonnées réelles, définie en prenant la puissance p-ième le long de chaque coordonnée, étant donné un paramètre positif p. C'est-à-dire la fonction de distance associée à une p-norme. Il s'agit d'une généralisation de la distance euclidienne ( p=2 ) et la distance de Manhattan ( p=1 ). Il porte le nom du mathématicien Hermann Minkowski.

Comparaison des distances de Tchebychev, euclidienne et de Manhattan pour l'hypoténuse d'un triangle 3-4-5 sur un échiquier (représenté par un roi, une fourmi et un vizir). Le vizir se déplace comme une tour mais d'une case à la fois.

Définition

La distance de Minkowski d'ordre p (où p≥1 ) entre deux points X=(x1,x2,…,xn) et Y=(y1,y2,…,yn)∈ℝn est définie comme : Dp(X,Y)=(∑i=1n|xi−yi|p)1p. Il s'agit de la mesure associée à la norme ‖X‖p=(∑i=1n|xi|p)1/p

La distance de Minkowski est une métrique résultant de l'inégalité de Minkowski. ‖X+Y‖p≤‖X‖p+‖Y‖p. Géométriquement, il s'agit d'une norme car les boules unité ‖X‖p<1 sont bornées et ouvertes pour la topologie usuelle, contiennent l'origine, et sont convexes et équilibrées (invariantes par X→−X ).

Pour0<p<1, la même formule ne définit pas une métrique car elle ne vérifie pas l'inégalité triangulaire. Par exemple, la distance entre (0,0) et (1,1) est 21/p>2, mais le point (0,1) est à une distance unité de ces deux points.

Cependant, une distance peut être obtenue pour ces valeurs en supprimant l'exposant de 1/p : dp(X,Y)=∑i=1n|xi−yi|p,0<p<1. La métrique résultante est également une F-norme, mais ne se déduit pas d'une norme, car les boules unité ne sont pas convexes pour cette distance.

La distance de Minkowski est souvent utilisée avec p=1 ou p=2, pour lesquelles on retrouve respectivement à la distance de Manhattan et à la distance euclidienne. Dans le cas limite de p tendant vers l'infini, on obtient la distance de Tchebychev : limp→∞(∑i=1n|xi−yi|p)1p=maxi=1n|xi−yi|.

La limite pourp→0+ de la métrique dp est parfois appelée norme 0 ou distance de Hamming ; elle compte le nombre de coordonnées xi qui diffèrent des coordonnées yi. Cette fonction de distance est une métrique, mais comme dp, elle n'est pas déduite d'une norme.

La distance de Minkowski peut être considérée comme un multiple de la moyenne d'ordre p des différences composante par composante entre P et Q.

La figure suivante montre des cercles unité (la courbe de niveau de la fonction distance où tous les points sont à une distance unitaire du centre) pour différentes valeurs de p :

Applications

La distance de Minkowski est utile dans le domaine de l'apprentissage automatique . De nombreux algorithmes d'apprentissage automatique populaires utilisent des métriques de distance bien choisies, telles que celles mentionnées précédemment, pour comparer la similarité de deux entrées dans les données. Selon la nature des données analysées, différentes distances peuvent être utilisées. La distance de Minkowski est particulièrement utile pour les ensembles de données numériques où l'on souhaite déterminer la similarité de taille entre plusieurs vecteurs de points de données.

Voir aussi