Afstandsfunktioner

Afstandsfunktioner beskriver hvor stor en forskel der er mellem to objekter i en given mængde. En afstand d er en funktion d: X × X → R≥0, der tilordner hvert par af objekter en ikke-negativ størrelse. Hvis d opfylder identitet (d(x,y)=0 kun hvis x=y), symmetri (d(x,y)=d(y,x)) og trekantsulighed (d(x,z) ≤ d(x,y) + d(y,z)), betegnes det som en metrisk afstand og giver X et metrisk rum, der muliggør begreber som konvergens og topologi baseret på afstanden.

Ikke alle afstande opfylder alle krav. Hvis d(x,y)=0 også når x≠y, kaldes det en pseudo-metrik. Hvis trekantsuligheden ikke gælder fuldt ud, er afstanden ikke en metrisk afstand. I praksis vælger man ofte afstande der er sikre i den forstand, at de opfylder metricets fire grundlæggende egenskaber.

Eksempler på almindelige afstande er Euclidsk afstand (L2): d(x,y) = sqrt(sum_i (x_i - y_i)^2); Manhattan afstand (L1): d(x,y) = sum_i |x_i - y_i|; Chebyshev afstand (L∞): d(x,y) = max_i |x_i - y_i|; Minkowskisk afstand: d_p(x,y) = (sum_i |x_i - y_i|^p)^{1/p} for p ≥ 1. Andre eksempler er Hammingafstand for strenge eller bitstrenge af lig længde og Mahalanobis afstand, der tager dataets varians og korrelationer i betragtning.

Anvendelser af afstandsfunktioner spænder fra klyngeanalyse og nærmeste naboer til informationssøgning og mønstergenkendelse. I maskinlæring og statistik definerer valg af afstand, hvordan data sammenlignes, og forskellige algoritmer er mere eller mindre følsomme over for den valgte distance.

Valg af afstand har stor indflydelse på resultater. Data-normalisering og enhedsskalering er ofte nødvendig; høj-dimensionale data kan kræve dimensionreduktions- eller metodespecifikke tilpasninger gennem metric learning for at tilpasse afstanden til dataenes struktur.