Afstandsfunktionen

Afstandsfunktionen, ofte kaldet en metric, er en funktion d: X × X → [0, ∞), der måler, hvor langt to elementer i X er fra hinanden. En afstandsfunktion opfylder normalt fire grundlæggende egenskaber: ikke-negativitet (d(x,y) ≥ 0); identitet af indbyrdes lighed (d(x,y) = 0 hvis og kun hvis x = y); symmetri (d(x,y) = d(y,x)); og trekantsulighed (d(x,z) ≤ d(x,y) + d(y,z)) for alle x, y og z i X. Når alle fire betingelser gælder, taler man om et metrisk rum (X, d). Hvis identiteten ikke helt gælder, men de tre andre gør, kaldes d en pseudometrik.

Mange kendte afstande består af geometriske eller kombinationsbaserede mål: Den euclidiske distance dE(x,y) = sqrt(∑(xi−yi)²) i R^n; L1- eller Manhattan-distance d1(x,y) = ∑|xi−yi|; Chebyshev-distance d∞(x,y) = max_i |xi−yi|. Diskrete afstande som Hamming-distance måler antal positioner, hvor to lige lange strenge adskiller sig; Levenshtein-distance måler mindste antal redigeringer mellem to strenge. Afstande kan også defineres som d(x,y) = ||x−y|| for en given norm.

Anvendelserne omfatter clustering (f.eks. k-means), nærmeste nabo-søgning, multidimensionel skalering og beregning i graf- og billedbehandling. Der findes variationer som pseudometrier og ikke-metriske afstandsmål til specialiserede anvendelser i dataanalyse og maskinlæring.