diffusionsavståndet

Diffusionsavståndet är ett mått mellan två punkter i en rumslig eller databaserad mängd som byggs utifrån en diffusionprocess över tiden. Det används framför allt inom maskininlärning och bildbehandling för att beskriva hur lika två punkter är med avseende på hur sannolikheten sprider sig över rummet efter en given tidsåtgång. Begreppet är centralt i diffusion maps-metoden (Coifman och Lafon), där avståndet används för att fånga inre geometriska strukturer som inte framträder i de vanliga rumsliga måtten.

Definition: Låt M vara en mångfald eller ett datautrymme och p_t(x,z) vara diffusionens heat kernel eller transition density från x till z efter tid t. Diffusionsavståndet mellan x och y vid tid t definieras som D_t(x,y) = [ ∫_M (p_t(x,z) - p_t(y,z))^2 dz ]^{1/2}. För diskret data över ett nätverk ersätts integralen med en summa över alla z. I praktiken används ofta ett avgränsat antal komponenter och en empirisk uppskattning av p_t.

Egenskaper och koppling till spektral teori: D_t^2(x,y) kan också skrivas som ∑_{l≥1} e^{-2 λ_l t} (φ_l(x) - φ_l(y))^2, där φ_l och λ_l är eigenfunktioner och egenvärden av Laplace-Beltrami-operatorn (eller av Markov- eller graflappianen). Med diffusion maps representeras varje punkt x av koordinater Ψ_t(x) = [ e^{-λ_1 t/2} φ_1(x), e^{-λ_2 t/2} φ_2(x), ... ], så att D_t(x,y) = ∥Ψ_t(x) - Ψ_t(y)∥.

Användningar och egenskaper: Diffusionsavståndet är relativt robust mot små lokala störningar och återspeglar den inre geometrin hos data eller rum. Det används i dimensionalitetsreducering, clustering och bild- och bioinformatik. Beräkningen bygger på spektral decomposition av Laplacian eller Markovmatris; valet av t och antalet dominerande komponenter avgör hur snabbt avståndet konvergerar till större skala.