Distance de Minkowski : un guide complet

Tutoriels
Python

Les métriques de distance constituent l’ossature de nombreux algorithmes en sciences des données et en apprentissage automatique, permettant de mesurer la similarité ou l’altérité entre points de données. Dans ce guide, nous explorerons les fondements de la distance de Minkowski, ses propriétés mathématiques et ses implémentations. Nous examinerons comment elle se rapporte à d’autres mesures de distance communes et nous démonterons son utilisation à travers des exemples de codage en Python et R.

Que vous soyez en train de développer des algorithmes de clustering, de travailler sur la détection d’anomalies, ou de微调 des modèles de classification, comprendre la distance de Minkowski peut améliorer votre approche de l’analyse des données et du développement de modèles. Essayons-en un coup d’oeil.

Qu’est-ce que la distance de Minkowski ?

La distance de Minkowski est une métrique polyvalente utilisée dans les espaces vectoriels normés, nommée d’après le mathématicien allemand Hermann Minkowski. Elle est une généralisation de plusieurs mesures de distance bien connues, ce qui en fait un concept fondamental dans divers domaines tels que la mathématique, les sciences informatiques et l’analyse des données.

Au cœur de la distance de Minkowski, il s’agit de mesurer la distance entre deux points dans un espace multidimensionnel. Ce qui la rend particulièrement utile est sa capacité à englober d’autres mesures de distance comme des cas spéciaux, principalement par l’intermédiaire d’un paramètre p. Ce paramètre permet à la distance de Minkowski de s’adapter à différents espaces de problèmes et aux caractéristiques des données. La formule générale pour la distance de Minkowski est :

Où :

  • x et y sont deux points dans un espace de dimension n

  • p est un paramètre qui détermine le type de distance (p ≥ 1)

  • |xi - yi| représente la différence absolue entre les coordonnées de x et y dans chaque dimension

La distance de Minkowski est utile pour deux raisons principales. D’une part, elle vous donne la flexibilité de basculer entre la distance de Manhattan ou la distance euclidienne selon vos besoins. D’autre part, elle reconnaît que toutes les données (envisagez les espaces de haute dimension) ne se prêtent pas nécessairement à une distance purement Manhattan ou purement euclidienne.

En pratique, le paramètre p est généralement choisi en intégrant un processus de validation train/test. En testant différentes valeurs de p pendant la validation croisée, vous pouvez déterminer quelle valeur offre la meilleure performance du modèle pour votre jeu de données spécifique.

Comment fonctionne la distance de Minkowski

Examinons comment la distance de Minkowski se rapporte aux autres formules de distance et passons ensuite par un exemple.

Généralisation d’autres métriques de distance

La première chose à considérer est que la formule de distance de Minkowski contient en elle-même les formules pour la distance de Manhattan, la distance euclidienne et la distance de Chebyshev.

Distance de Manhattan (p = 1) :

Lorsque p est réglé à 1, la distance de Minkowski devient la distance de Manhattan.

Connue également sous le nom de distance de ville ou norme L1, la Distance de Manhattan mesure la somme des différences absolues.

Distance euclidienne (p = 2) :

Lorsque p est réglé à 2, la distance de Minkowski devient la distance euclidienne.

Distance euclidienne est la mesure de distance la plus commune, représentant la distance en ligne droite entre deux points.

Distance de Chebyssév (p → ∞) :

Distance de Chebyssév, également connue sous le nom de distance de damier, mesure la différence maximale le long de n’importe quelle dimension.

Exemple de travail

Pour véritablement saisir la fonctionnalité et le pouvoir de la distance de Minkowski, passons par un exemple. Cette exploration nous aidera à comprendre comment le paramètre p affecte la calcul et l’interprétation des distances dans des espaces multi-dimensionnels.

Considérons deux points dans un espace 2D :

  • Point A : (2, 3)
  • Point B : (5, 7)

Nous calculerons la distance de Minkowski entre ces points pour différentes valeurs de p.

Le paramètre p dans la formule de la distance de Minkowski contrôle la sensibilité de la mesure aux différences dans les composants individuels :

  • Lorsque p=1 : Toutes les différences contribuent linéairement.
  • Lorsque p=2 : Les différences plus grandes ont un impact plus important en raison de l’exponentiation.
  • Lorsque p>2 : still greater emphasis on larger differences.
  • Lorsque p→∞ : Seule la différence maximale entre toutes les dimensions compte.

Comme p augmente, la distance de Minkowski généralement diminue, approchant la distance de Chebyssév. Cela est dû au fait que les valeurs p plus élevées donnent davantage de poids à la plus grande différence et moins à les petites différences.

Pour visualiser comment les valeurs différentes de p affectent la calcul de distance entre nos points A(2, 3) et B(5, 7), examinons le graphique suivant:

En observant le graphique, nous pouvons voir comment la mesure de la distance change quand p augmente :

  • La distance de Manhattan (p=1), représentée par la trajectoire verte, produit la plus longue distance, car elle suit strictement le grid.
  • La distance euclidienne (p=2), représentée par la droite orange, offre une direction droite et directe.
  • La distance de Chebyssév (p=∞), représentée par les lignes rouges pointillées, se concentre uniquement sur la plus grande différence de coordonnées, créant ainsi une trajectoire qui se déplace de manière maximale dans une seule dimension avant de se soucier de l’autre.
  • La distance de Minkowski avec p=3 en violet montre une légère courbe, annonçant la transition entre la distance euclidienne et la distance de Chebyssév.

Cette visualisation nous aide à comprendre pourquoi différentes valeurs de p pourraient être choisies pour diverses applications. Par exemple, la distance de Manhattan pourrait être plus appropriée pour les problèmes de navigation dans une ville, tandis que la distance euclidienne est souvent utilisée pour les calculs dans l’espace physique. Les valeurs de p plus élevées, comme dans le cas de la distance de Minkowski p=3, peuvent être utiles dans des situations où les différences plus grandes devraient être mises en avant, et la distance de Chebyssév pourrait être préférée lorsque la plus grande différence dans n’importe quelle dimension est le facteur le plus critique.

Applications de la distance de Minkowski.

La distance de Minkowski, dotée de son paramètre ajustable p, est une outil souple utilisé dans de nombreux domaines. En changeant p, nous pouvons adapter la manière dont nous mesurons la distance entre points, ce qui la rend adaptable à différentes tâches. Ci-dessous, quatre applications où la distance de Minkowski joue un rôle important.

Apprentissage automatique et science des données

Dans l’apprentissage automatique et la science des données, la distance de Minkowski est fondamentale pour les algorithmes qui font appel à la mesure de la similarité ou de la dissimilarité entre les points de données. Un exemple remarquable est l’algorithme k-Plus Proches Voisins (k-NN), qui classe les points de données en fonction des catégories de leurs voisins les plus proches. En utilisant la distance de Minkowski, nous pouvons ajuster le paramètre p pour modifier la manière dont nous calculons la « proximité » entre les points.

Reconnaissance de motifs

La reconnaissance de motifs consiste à identifier des motifs et des régularités dans les données, comme la reconnaissance de la handwriting ou la détection des caractéristiques faciales. Dans ce contexte, la distance de Minkowski mesure la différence entre les vecteurs de caractéristiques représentant les motifs. Par exemple, dans la reconnaissance d’images, chaque image peut être représentée par un vecteur de valeurs de pixels. Calculer la distance de Minkowski entre ces vecteurs permet de quantifier dans quelle mesure les images sont similaires ou différentes.

En modifiant p, nous pouvons contrôler la sensibilité de la mesure de distance à les différences spécifiques des caractéristiques. Un p plus bas pourrait considérer les différences générales sur toutes les pixels, tandis qu’un p plus élevé pourrait mettre l’accent sur les différences significatives dans certaines régions de l’image.

Détection d’anomalies

La détection d’anomalies vise à identifier les points de données qui déviennent significativement du reste, ce qui est crucial dans des domaines tels que la détection de fraude, la sécurité réseau et la détection de défaillances dans les systèmes. La distance de Minkowski est utilisée pour mesurer à quelle distance un point de données se trouve des autres points dans le jeu de données. Les points avec des distances importantes sont des anomalies potentielles.En choisissant un p approprié, les analystes peuvent améliorer la sensibilité des systèmes de détection d’anomalies à la nature de déviations les plus pertinentes pour leur contexte spécifique.

Géométrie computationnelle et analyse spatiale.

Dans la géométrie calculatoire et l’analyse spatiale, la distance de Minkowski est utilisée pour calculer les distances entre points dans l’espace, ce qui est la base de nombreux algorithmes géométriques. Par exemple, la détection de collision dans ces domaines repose sur la distance de Minkowski pour déterminer quand les objets sont suffisamment proches pour interagir. En ajustant p, les développeurs peuvent créer diverses zones de collision, allant d’angulaires (plus bas p) à arrondies (plus haut p).

Au-delà de la détection de collision, la distance de Minkowski peut être utile dans la clustering spatial et l’analyse des formes. En variant la valeur de p, les chercheurs peuvent accorder de l’importance à différents aspects des relations spatiales, des distances entre quartiers à des similitudes globales des formes.

Propriétés mathématiques de la distance de Minkowski

La distance de Minkowski n’est pas seulement une outil polyvalent dans les applications pratiques mais également un concept important dans la théorie mathématique, en particulier dans l’étude des espaces métriques et des normes.

Propriétés des espaces métriques

La distance de Minkowski satisfait les quatre propriétés essentielles requises pour qu’une fonction soit considérée comme une distance dans un espace métrique :

  • Non-négativité: La distance de Minkowski entre deux points est toujours non négative, d(x,y)≥0. Cela est évident car c’est la racine p-ième d’une somme de termes non négatifs (les valeurs absolues à la puissance p).
  • Identité des indiscernables: La distance de Minkowski entre deux points est nulle si et seulement si les deux points sont identiques. Mathématiquement, d(x,y) = 0 si et seulement si x=y. Cela suit parce que la différence absolue entre des composants identiques est nulle.
  • Symétrie: La distance de Minkowski est symétrique, ce qui signifie que d(x,y)=d(y,x). Cette propriété est valable parce que l’ordre de la soustraction dans les termes de valeur absolue n’affecte pas le résultat.
  • Inégalité du triangle : La distance de Minkowski satisfait l’inégalité du triangle, qui stipule que pour trois points x, y et z, la distance de x à z est au plus égale à la somme des distances de x à y et de y à z ; formellement, d(x,z) ≤ d(x,y) + d(y,z). Cette propriété est moins intuitive à démontrer directement à partir de la formule et nécessite généralement des mathématiques plus avancées, mais elle garantit essentiellement que la plus courte distance entre deux points est de prendre la route directe.

Généralisation de la norme

La distance de Minkowski agit comme un cadre général qui unit diverses manières de mesurer les distances dans les espaces mathématiques par le biais du concept de normes. En termes simples, une norme est une fonction qui affecte une longueur ou une taille non négative à un vecteur dans un espace vectoriel, mesurant essentiellement la « longueur » du vecteur. En ajustant le paramètre p dans la formule de la distance de Minkowski, nous pouvons transitions fluides entre différentes normes, chacune fournissant une méthode unique pour calculer la longueur de vecteurs.

Par exemple, quand p=1, la distance de Minkowski devient la norme de Manhattan, qui mesure la distance en calculant la somme des differences absolues along chaque dimension — imaginez-vous comme vous naviguez sur un reseau de rues dans une ville. Lorsque p=2, elle se transforme en la norme euclidienne, qui calcule la distance en ligne Droite (« comme le vol des corneilles ») entre les points. Quand p approche de l’infini, elle converge vers la norme de Chebyshev, où la distance est determinee par la plus grande difference unique along les dimensions. Cette flexibilité permet à la distance de Minkowski d’adapter à divers contextes mathematiques et pratiques, ce qui la rend une outil polyvalent pour mesurer les distances dans différents scenarios.

Calcul de la distance de Minkowski en Python et R

Explorons les implémentations de calculs de distance de Minkowski en utilisant à la fois Python et R. Nous examinerons les packages et bibliothèques disponibles pour accomplir cela.

Exemple Python

Pour calculer la distance de Minkowski en Python, nous pouvons utiliser la bibliothèque SciPy, qui fournit des implémentations efficientes de diverses mesures de distance. Voici un exemple qui calcule la distance de Minkowski pour différents valeurs de p :

import numpy as np
from scipy.spatial import distance

# Points d'exemple
point_a = [2, 3]
point_b = [5, 7]

# Différentes valeurs de p
p_values = [1, 2, 3, 10, np.inf]
print("Minkowski distances using SciPy:")

for p in p_values:
	if np.isinf(p):
	    # Pour p = infini, utiliser la distance de Chebyssév
	    dist = distance.chebyshev(point_a, point_b)
	    print(f"p = ∞, Distance = {dist:.2f}")
	else:
	        dist = distance.minkowski(point_a, point_b, p)
	        print(f"p = {p}, Distance = {dist:.2f}")

En exécutant ce code, les lecteurs peuvent observer comment la distance change avec différentes valeurs de p, renforçant les concepts discutés plus tôt dans l’article.

Minkowski distances using SciPy:
p = 1, Distance = 7.00
p = 2, Distance = 5.00
p = 3, Distance = 4.50
p = 10, Distance = 4.02
p = ∞, Distance = 4.00

Ce code montre :

  1. Comment utiliser les fonctions de distance de SciPy pour les distances de Minkowski et de Chebyshev.
  2. Calcul de distances pour diverses valeurs de p, y compris l’infini.
  3. La relation entre la distance de Minkowski et d’autres métriques (Manhattan, Euclidienne, Chebyshev).

Exemple en R

Pour R, nous utiliserons la fonction dist() de la bibliothèque stats :

# Définir la fonction de distance de Minkowski en utilisant stats::dist

minkowski_distance <- function(x, y, p) {
  points <- rbind(x, y)
  if (is.infinite(p)) {
    # Pour p = Inf, utilisez la méthode "maximum" pour la distance de Chebyshev
    distance <- stats::dist(points, method = "maximum")
  } else {
    distance <- stats::dist(points, method = "minkowski", p = p)
  }
  return(as.numeric(distance))
}

# Exemple d'utilisation
point_a <- c(2, 3)
point_b <- c(5, 7)

# Des valeurs de p différentes
p_values <- c(1, 2, 3, 10, Inf)
cat("Minkowski distances between points A and B using stats::dist:\n")

for (p in p_values) {
  distance <- minkowski_distance(point_a, point_b, p)
  if (is.infinite(p)) {
    cat(sprintf("p = ∞, Distance = %.2f\n", distance))
  } else {
    cat(sprintf("p = %g, Distance = %.2f\n", p, distance))
  }
}

Ce code montre :

  1. Comment créer une fonction minkowski_distance en utilisant la fonction dist() de la bibliothèque stats.

  2. Gestion des valeurs de p différentes, y compris l’infini pour la distance de Chebyshev.

  3. Calcul de la distance de Minkowski pour diverses valeurs de p.

  4. Affichage des distances arrondies à 2 chiffres après la virgule.

La sortie de ce code sera :

Minkowski distances between points A and B using stats::dist:
p = 1, Distance = 7.00
p = 2, Distance = 5.00
p = 3, Distance = 4.50
p = 10, Distance = 4.02
p = ∞, Distance = 4.00

Cette implémentation R fournit un contre-exemple à l’exemple Python, permettant aux lecteurs de voir comment la distance de Minkowski peut être calculée dans différents environnements de programmation.

Conclusion

La distance de Minkowski offre une méthode souple et adaptable pour mesurer les distances dans des espaces multi-dimensionnels. Sa capacité à généraliser d’autres mesures de distance communes en utilisant le paramètre p en fait une arme précieuse dans de nombreux domaines des sciences des données et de l’apprentissage automatique. En ajustant p, les praticiens peuvent adapter leurs calculs de distance aux caractéristiques spécifiques de leurs données et aux exigences de leurs projets, améliorant potentiellement les résultats dans des tâches allant de la clustération à la détection d’anomalies.

Lorsque vous appliquez la distance de Minkowski dans votre propre travail, nous vous encourageons à expérimenter différentes valeurs de p et à observer leur impact sur vos résultats. Pour ceux qui souhaitent approfondir leur compréhension et leurs compétences, nous recommandons d’explorer le cours Designing Machine Learning Workflows in Python et d’envisager notre programme de formation professionnelle Data Scientist Certification. Ces ressources peuvent vous aider à construire sur vos connaissances relatives aux mesures de distance et à les appliquer efficacement dans diverses situations.

Source:
https://www.datacamp.com/tutorial/minkowski-distance