Avståndsmetrik

Avståndsmetrik, eller avståndsmetrikfunktion, är inom matematik och datavetenskap en funktion som tilldelar varje par av objekt i en mängd X ett icke-negativt tal och som uppfyller vissa krav. För att kallas metrik måste funktionen uppfylla fyra axiomer: icke-negativitet (d(x,y) ≥ 0), identitet av distinkta objekt (d(x,y) = 0 endast om x = y), symmetri (d(x,y) = d(y,x)) och triangelolikhet (d(x,z) ≤ d(x,y) + d(y,z)) för alla x, y och z i X. Om något av kriterierna saknas används termerna semimetri eller pseudometrik i stället.

Vanliga avståndsmetrik är exempelvis den Euclideaniska metrikens d_E(x,y) = √Σ_i (x_i − y_i)^2, den Manhattan- eller L1-metoden d_1(x,y) = Σ_i |x_i − y_i|, samt Chebyshev- eller L-infinity metrik d∞(x,y) = max_i |x_i − y_i|. Det finns också generella Minkowskiska metrikker d_p(x,y) = (Σ_i |x_i − y_i|^p)^(1/p) för p ≥ 1. För diskreta sekvenser används Hamming-avståndet, antal positioner där två strängar skiljer sig. Redigeringsavståndet (t.ex. Levenshtein) mäter antal operationer för att omvandla en sträng till en annan och är i standardform en metric.

Användningsområden inkluderar klustring (t.ex. k-means), närhetsbaserad sökning och rekonstruktion av datastrukturer, visualisering av avstånd i multidimensionella rum samt möjliggörande av dimensionell reduktion genom metriker som bevarar avstånd. Avståndsmetrikken kan skapas från normer, t.ex. d(x,y) = ||x − y||_p, eller från grafbaserade mått som längden av kortaste vägen. Inom maskininlärning talas också om metric learning, där man lär en lämplig metrik från märkt data. Vissa mått, som vissa informationsmått, uppfyller inte triangelolikheten och är därför inte metriker.