distansfunktioner

Distansfunktioner, i matematiken ofta kallade mått eller metriker, är funktioner d: X×X → [0, ∞) som anger hur långt två element x och y i en mängd X är från varandra. En distans används för att jämföra och analysera objekt i rumsliga eller abstrakta sammanhang och ligger till grund för konstruktion av metriska rum, klustring och närhetsberäkningar.

En distans uppfyller tre grundvillkor: d(x,y) ≥ 0 med d(x,y)=0 när x=y, d(x,y)=d(y,x) (symmetri) och d(x,z) ≤ d(x,y) + d(y,z) (triangelolikheten). När ett d uppfyller dessa villkor säger man att (X,d) är ett metriskt rum.

Vanliga distansfunktioner på vektorrum som R^n inkluderar: Euclidean distance d2(x,y) = sqrt( Σ_i (x_i − y_i)^2 ), Manhattan distance d1(x,y) = Σ_i |x_i − y_i| och Chebyshev distance d∞(x,y) = max_i |x_i − y_i|. I allmänhet kan man definiera Lp-distans d_p(x,y) = ( Σ_i |x_i − y_i|^p )^{1/p} för p ≥ 1, där p=2 ger Euclidean och p=1 ger Manhattan. Discrete distance d(x,y) = 0 om x=y och 1 annars är ett enkelt exempel för avstånd i ändliga eller diskreta sammanhang.

Användningar av distansfunktioner är bland annat klustring (t.ex. k-means eller hierarkisk klustring), närmaste grannar-sökning, mönsterigenkänning, dataanalys samt robotik och datorgrafik. Valet av distans påverkar resultat och beteende hos algoritmer betydligt.