Minkowski-afstand: een uitgebreide gids

Afstandsmetriek vormt de ruggengraat van talloze algoritmen in data science en machine learning. Ze maken het mogelijk om de (on)gelijkheid tussen datapunten te meten. In deze gids verkennen we de basis van de Minkowski-afstand, de wiskundige eigenschappen en de implementaties. We bekijken de relatie met andere gangbare afstandsmaten en laten het gebruik zien met codevoorbeelden in Python en R. 

Of je nu clusteringalgoritmen ontwikkelt, werkt aan anomaliedetectie of classificatiemodellen verfijnt, inzicht in de Minkowski-afstand kan je aanpak van data-analyse en modelontwikkeling versterken. Laten we kijken.

Wat is Minkowski-afstand?

Minkowski-afstand is een veelzijdige metriek in genormeerde vectorruimten, vernoemd naar de Duitse wiskundige Hermann Minkowski. Het is een generalisatie van verschillende bekende afstandsmaten en daardoor een fundamenteel concept in onder meer wiskunde, informatica en data-analyse.

In de kern biedt de Minkowski-afstand een manier om de afstand tussen twee punten in een meer-dimensionale ruimte te meten. Wat het bijzonder nuttig maakt, is dat het andere afstandsmetriek omvat als speciale gevallen, vooral via een parameter p. Deze parameter laat de Minkowski-afstand aanpassen aan verschillende probleemruimten en datakenmerken. De algemene formule voor Minkowski-afstand is:

Waarbij:

• x en y twee punten zijn in een n-dimensionale ruimte

• p een parameter is die het type afstand bepaalt (p ≥ 1)

• |xi - yi| het absolute verschil is tussen de coördinaten van x en y in elke dimensie

Minkowski-afstand is om twee hoofdredenen nuttig. Enerzijds geeft het je de flexibiliteit om naar behoefte te schakelen tussen Manhattan- of Euclidische afstand. Anderzijds erkent het dat niet alle datasets (denk aan hoog-dimensionale ruimten) goed passen bij puur Manhattan of puur Euclidisch.

In de praktijk wordt de parameter p doorgaans gekozen via een train/test-validatieworkflow. Door verschillende p-waarden te testen tijdens kruisvalidatie, kun je bepalen welke waarde de beste modelprestatie geeft voor jouw specifieke dataset.

Hoe Minkowski-afstand werkt

Laten we bekijken hoe Minkowski-afstand zich verhoudt tot andere afstandsformules en daarna een voorbeeld doorlopen. 

Generalisatie van andere afstandsmetriek

Het eerste om te bekijken is hoe de Minkowski-formule de formules voor Manhattan-, Euclidische en Chebyshev-afstanden bevat. 

Manhattan-afstand (p = 1): 

Wanneer p gelijk is aan 1, wordt de Minkowski-afstand de Manhattan-afstand. 

Ook bekend als cityblock-afstand of L1-norm, meet Manhattan-afstand de som van absolute verschillen. 

Euclidische afstand (p = 2): 

Wanneer p gelijk is aan 2, wordt de Minkowski-afstand de Euclidische afstand.

Euclidische afstand is de meest gangbare afstandsmaat en staat voor de rechtelijnsafstand tussen twee punten. 

Chebyshev-afstand (p → ∞): 

Chebyshev-afstand, ook wel schaakbordafstand genoemd, meet het maximale verschil langs een willekeurige dimensie. 

Een voorbeeld uitwerken

Om de functionaliteit en kracht van Minkowski-afstand echt te begrijpen, werken we een voorbeeld uit. Deze verkenning helpt ons te zien hoe de parameter p de berekening en interpretatie van afstanden in meer-dimensionale ruimten beïnvloedt.

Laten we twee punten in een 2D-ruimte nemen:

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

We berekenen de Minkowski-afstand tussen deze punten voor verschillende p-waarden.

De parameter p in de Minkowski-formule stuurt de gevoeligheid van de metriek voor verschillen in individuele componenten:

• Als p=1: Alle verschillen tellen lineair mee.
• Als p=2: Grotere verschillen hebben meer impact door kwadrateren.
• Als p>2: Nog meer nadruk op grotere verschillen.
• Als p→∞: Alleen het maximale verschil over alle dimensies is bepalend.

Naarmate p toeneemt, neemt de Minkowski-afstand in het algemeen af en nadert deze de Chebyshev-afstand. Dat komt doordat hogere p-waarden meer gewicht geven aan het grootste verschil en minder aan kleinere verschillen.

Om te visualiseren hoe verschillende p-waarden de afstandsberekening tussen onze punten A(2, 3) en B(5, 7) beïnvloeden, bekijken we de volgende grafiek:

Als we de grafiek bekijken, zien we hoe de afstandsmaat verandert wanneer p toeneemt:

• De Manhattan-afstand (p=1), weergegeven door het groene pad, levert het langste pad op, omdat het strikt het raster volgt.
• De Euclidische afstand (p=2), getoond door de oranje rechte lijn, geeft een directe, rechtelijnse route.
• De Chebyshev-afstand (p=∞), afgebeeld met rode stippellijnen, focust uitsluitend op het grootste coördinatenverschil en creëert een pad dat maximaal in één dimensie beweegt voordat de andere wordt aangepakt.
• De Minkowski-afstand met p=3 in paars toont een lichte kromming, als overgang tussen Euclidische en Chebyshev-afstanden.

Deze visualisatie helpt te begrijpen waarom verschillende p-waarden voor uiteenlopende toepassingen worden gekozen. Zo kan Manhattan-afstand geschikter zijn voor stadsnavigatie, terwijl Euclidische afstand vaak wordt gebruikt in fysieke ruimten. Hogere p-waarden, zoals bij Minkowski p=3, kunnen nuttig zijn in scenario’s waar grotere verschillen benadrukt moeten worden, en Chebyshev-afstand kan de voorkeur hebben als het maximale verschil in een dimensie de doorslag geeft.

Toepassingen van Minkowski-afstand

De Minkowski-afstand, met de instelbare parameter p, is een flexibel hulpmiddel in verschillende domeinen. Door p te variëren, kunnen we bepalen hoe we de afstand tussen punten meten, wat het geschikt maakt voor diverse taken. Hieronder vier toepassingen waarin Minkowski-afstand een belangrijke rol speelt.

Machine learning en data science

In machine learning en data science is Minkowski-afstand fundamenteel voor algoritmen die leunen op het meten van (on)gelijkheid tussen datapunten. Een bekend voorbeeld is het k-Nearest Neighbors (k-NN)-algoritme, dat datapunten classificeert op basis van de categorieën van hun dichtstbijzijnde buren. Met Minkowski-afstand kunnen we de parameter p aanpassen om te veranderen hoe we de "nabijheid" tussen punten berekenen.

Patroonherkenning

Patroonherkenning omvat het identificeren van patronen en regelmatigheden in data, zoals handschriftherkenning of detectie van gelaatstrekken. In deze context meet Minkowski-afstand het verschil tussen featurevectoren die patronen vertegenwoordigen. In beeldherkenning kun je bijvoorbeeld elk beeld voorstellen als een vector van pixelwaarden. Door de Minkowski-afstand tussen deze vectoren te berekenen, kunnen we kwantificeren hoe (on)gelijk de beelden zijn.

Door p aan te passen kun je de gevoeligheid van de afstandsmaat voor verschillen in specifieke features sturen. Een lagere p bekijkt meer de algehele verschillen over alle pixels, terwijl een hogere p juist grote verschillen in bepaalde regio’s benadrukt.

Anomaliedetectie

Anomaliedetectie richt zich op het identificeren van datapunten die significant afwijken van de meerderheid, cruciaal in domeinen als fraudedetectie, netwerkbeveiliging en foutdetectie in systemen. Minkowski-afstand meet hoe ver een datapunt van andere punten in de dataset ligt. Punten met grote afstanden zijn potentiële anomalieën. Door een geschikte p te kiezen, kunnen analisten de gevoeligheid van anomaliedetectiesystemen afstemmen op de afwijkingen die in hun context het meest relevant zijn.

Computationele geometrie en ruimtelijke analyse

In computationele geometrie en ruimtelijke analyse wordt Minkowski-afstand gebruikt om afstanden tussen punten in de ruimte te berekenen, de basis van veel geometrische algoritmen. Zo is botsingsdetectie in deze domeinen afhankelijk van Minkowski-afstand om te bepalen wanneer objecten dicht genoeg bij elkaar komen om te interageren. Door p aan te passen, kunnen ontwikkelaars uiteenlopende botsingsgrenzen creëren, variërend van hoekig (lagere p) tot afgerond (hogere p).

Naast botsingsdetectie kan Minkowski-afstand nuttig zijn in ruimtelijke clustering en vormanalyse. Door de waarde van p te variëren, kunnen onderzoekers verschillende aspecten van ruimtelijke relaties benadrukken, van cityblock-afstanden tot algehele vormgelijkenis.

Wiskundige eigenschappen van Minkowski-afstand

De Minkowski-afstand is niet alleen veelzijdig in de praktijk, maar ook een belangrijk concept in de wiskundige theorie, met name in de studie van metrische ruimten en normen.

Eigenschappen van metrische ruimten

De Minkowski-afstand voldoet aan de vier essentiële eigenschappen waaraan een functie moet voldoen om als metriek in een metrische ruimte te gelden:

• Niet-negativiteit: De Minkowski-afstand tussen twee punten is altijd niet-negatief, d(x,y)≥0. Dit is duidelijk omdat het de p-de wortel is van een som van niet-negatieve termen (absolute waarden tot de macht p).
• Identiteit van ononderscheidbaren: De Minkowski-afstand tussen twee punten is nul als en slechts als de twee punten identiek zijn. Wiskundig: d(x,y) = 0 als en slechts als x=y. Dit volgt omdat het absolute verschil tussen identieke componenten nul is.
• Symmetrie: De Minkowski-afstand is symmetrisch, dus d(x,y)=d(y,x). Dit geldt omdat de volgorde van aftrekken binnen absolute waarden het resultaat niet beïnvloedt.
• Driehoeksongelijkheid: De Minkowski-afstand voldoet aan de driehoeksongelijkheid, die stelt dat voor drie punten x, y en z de afstand van x naar z hoogstens de som is van de afstand van x naar y en van y naar z; formeel, d(x,z)≤d(x,y)+d(y,z). Deze eigenschap is minder intuïtief om direct uit de formule te bewijzen en vergt doorgaans geavanceerdere wiskunde, maar garandeert in essentie dat de directe route tussen twee punten het kortst is.

Normgeneralisatie

De Minkowski-afstand fungeert als een algemeen kader dat verschillende manieren om afstanden in wiskundige ruimten te meten verenigt via het concept van normen. Simpel gezegd is een norm een functie die een niet-negatieve lengte of grootte aan een vector in een vectorruimte toekent; met andere woorden: hoe "lang" de vector is. Door de parameter p in de Minkowski-formule aan te passen, kunnen we vloeiend schakelen tussen verschillende normen, elk met een eigen manier om de vectorlengte te berekenen.

Zo wordt bij p=1 de Minkowski-afstand de Manhattan-norm, waarbij afstand de som is van absolute verschillen per dimensie—denk aan navigeren op een stadsraster. Bij p=2 wordt het de Euclidische norm, die de rechtelijnse ("as-the-crow-flies") afstand tussen punten berekent. Als p naar oneindig gaat, convergeert het naar de Chebyshev-norm, waarbij de afstand wordt bepaald door het grootste enkele verschil over de dimensies. Deze flexibiliteit laat de Minkowski-afstand aansluiten bij uiteenlopende wiskundige en praktische contexten, en maakt het tot een veelzijdig hulpmiddel om afstanden te meten in verschillende scenario’s.

Minkowski-afstand berekenen in Python en R

We bekijken implementaties van Minkowski-afstand in zowel Python als R. We gebruiken direct beschikbare packages en libraries om dit te doen. 

Python-voorbeeld

Om Minkowski-afstand in Python te berekenen, kunnen we de SciPy-bibliotheek gebruiken, die efficiënte implementaties van diverse afstandsmetriek biedt. Hier is een voorbeeld dat Minkowski-afstand voor verschillende p-waarden berekent:

import numpy as np
from scipy.spatial import distance

# Example points
point_a = [2, 3]
point_b = [5, 7]

# Different p values
p_values = [1, 2, 3, 10, np.inf]
print("Minkowski distances using SciPy:")

for p in p_values:
	if np.isinf(p):
	    # For p = infinity, use Chebyshev distance
	    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}")Mogelijk gemaakt door

Door deze code uit te voeren, kun je zien hoe de afstand verandert bij verschillende p-waarden, wat de eerder besproken concepten versterkt.

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.00Mogelijk gemaakt door

Deze code laat zien:

1. Hoe je de afstandsfuncties van SciPy gebruikt voor Minkowski- en Chebyshev-afstanden.
2. Berekening van afstanden voor verschillende p-waarden, inclusief oneindig.
3. De relatie tussen Minkowski-afstand en andere metriek (Manhattan, Euclidisch, Chebyshev).

R-voorbeeld

Voor R gebruiken we de functie dist() uit de stats-bibliotheek:

# Define the Minkowski distance function using stats::dist

minkowski_distance <- function(x, y, p) {
  points <- rbind(x, y)
  if (is.infinite(p)) {
    # For p = Inf, use method = "maximum" for Chebyshev distance
    distance <- stats::dist(points, method = "maximum")
  } else {
    distance <- stats::dist(points, method = "minkowski", p = p)
  }
  return(as.numeric(distance))
}

# Example usage
point_a <- c(2, 3)
point_b <- c(5, 7)

# Different p values
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))
  }
}Mogelijk gemaakt door

Deze code laat zien:

1. Hoe je een functie minkowski_distance maakt met de functie dist() uit stats.

2. Hoe je verschillende p-waarden verwerkt, inclusief oneindig voor Chebyshev-afstand.

3. Berekening van Minkowski-afstand voor diverse p-waarden.

4. Formatteren van uitvoer om afstanden afgerond op 2 decimalen te tonen.

De uitvoer van deze code is:

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.00Mogelijk gemaakt door

Deze R-implementatie is het tegenhanger van het Python-voorbeeld en laat zien hoe je Minkowski-afstand in verschillende programmeeromgevingen kunt berekenen.

Conclusie

Minkowski-afstand biedt een flexibele en aanpasbare manier om afstanden in meer-dimensionale ruimten te meten. Doordat het via de parameter p andere gangbare afstandsmetriek generaliseert, is het een waardevol hulpmiddel in diverse gebieden van data science en machine learning. Door p aan te passen, kun je afstandsberekeningen afstemmen op de specifieke kenmerken van je data en de eisen van je project, wat de resultaten kan verbeteren bij taken van clustering tot anomaliedetectie.

Als je Minkowski-afstand in je eigen werk toepast, moedigen we je aan om met verschillende p-waarden te experimenteren en hun effect op je resultaten te observeren. Wil je je begrip en vaardigheden verder verdiepen? Bekijk dan de cursus Designing Machine Learning Workflows in Python en overweeg ons Data Scientist Certification-carrièreprogramma. Deze resources helpen je voort te bouwen op je kennis van afstandsmetriek en ze effectief toe te passen in uiteenlopende scenario’s.