Manhattan distance, známá také jako distance Manhattan, je základní metriku vzdálenosti, která se často používá v informatice, strojovém učení, geoinformatice a analýze dat. Její názvy se objevují v různých formátech – od formálního označení v angličtině až po české překlady typu „Manhattanova vzdálenost“ nebo „vzdálenost typu Manhattan“. V tomto článku si projdeme, co tato vzdálenost vlastně znamená, jak ji počítat, proč je užitečná, a v jakých situacích je vhodné ji zvolit místo jiných metrik, například Euclidean distance. Budeme také pracovat s praktickými příklady, ukázkami kódu a tipy pro implementaci v reálných projektech.
Co je Manhattan distance a proč se jmenuje takto
Manhattan distance je definována jako součet absolutních rozdílů souřadnic mezi dvěma body. Pro dva body v n-rozměrném prostoru x = (x1, x2, …, xn) a y = (y1, y2, …, yn) se vzdálenost vypočítá jako:
Manhattan distance(x, y) = Σi=1..n |xi − yi|
V geometrické intuici jde o to, že se pohybujeme po osách souřadnic (na mřížce). Představte si město s pravidelnou sítí ulic, kde se pohybujete jen po vodorovných a svislých ulicích. Cesta z bodu A do bodu B tedy nevede diagonálním půlměsícem, ale po křivkách – a celková délka cesty odpovídá součtu rozdílů v jednotlivých souřadnicích. Z tohoto důvodu se často zobrazuje jako „pohyb po mříži“ a odráží reálné navigační scénáře v městském prostředí.
Termín Manhattan distance vychází z geografického vzoru manhattanských ulic na Manhattanu v New Yorku, kde se cesty často volí podél pravidelného bloku. Proto se v literatuře i v kódu setkáváme s názvem manhattan distance nebo distance Manhattan. V České literatuře se objevují i tvary jako Manhattanova vzdálenost či vzdálenost typu Manhattan.
Jak Manhattan distance souvisí s ostatními metrikami vzdálenosti
Existuje celá rodina metrik, které popisují „jak daleko je něco od něčeho jiného“, a každá z nich má své ideální použití. Dvě nejčastější srovnávané metriky jsou:
- Manhattan distance (L1 norm): součet absolutních rozdílů souřadnic. Vhodná pro data, která se pohybují po osách a kde hraje roli lineární součet rozdílů.
- Euclidean distance (L2 norm): klasická euclidovská vzdálenost, která odpovídá nejkratší přímé vzdálenosti mezi body v prostoru. Ve vysokých dimenzích může být citlivější na extrémní hodnoty.
Rozdíl mezi těmito dvěma metrikami může být klíčový pro výsledky strojového učení. Manhattan distance klade důraz na jednotlivé souřadnicové rozdíly samostatně a často je robustnější vůči odchylkám na některých souřadnicích. Euclidean distance naopak vyvažuje rozdíly více „centrálně“, protože jsou ve vzorci čtverce jednotlivých rozdílů. V praxi to znamená, že volba metriky může ovlivnit, jak se k sobě budou nová data tisknout a jaké budou výsledné klasifikace, shluky či doporučení.
Vlastnosti a geometrie Manhattan distance
Mezi klíčové vlastnosti patří:
- Nezápornost: Manhattan distance je vždy nezáporná a bude nulová pouze tehdy, když body jsou identické.
- Symetrie: distance(x, y) = distance(y, x).
- Mezikrokové chování: jakýkoliv krok v jedné ose zpřísní vzdálenost o absolutní rozdíl v dané souřadnici, zatímco ostatní souřadnice zůstávají beze změny.
- Rovnost pro ortogonální pohyb: pokud dva body leží na rovnoběžce s osou, Manhattan distance se zjednoduší na součet rozdílů právě v té jedné ose, která měří odchylku.
Geometricky lze Manhattan distance chápat jako „volený“ způsob měření vzdálenosti v prostředí s regulárním mřížovým pohybem. Na rozdíl od Euclidean distance zde není žádná přímá nejkratší cesta v prostoru mezi body – spíše jde o součet vzdáleností po jednotlivých osách. To má dopad na interpretaci v kontextu dat, kde se jednotlivé rozměry často interpretují samostatně (například věk, výše mzdy, počet produktů v košíku atd.).
Praktické výpočty: jednoduché příklady v 2D a 3D
2D příklad
Uvažujme dva body A = (2, 3) a B = (5, 1). Manhattan distance mezi nimi je:
|2 − 5| + |3 − 1| = 3 + 2 = 5
Tento jednoduchý výpočet je ilustrativní pro to, jak se součet absolutních rozdílů promítá do skutečné vzdálenosti po mříži.
3D příklad
Rozšíření do tří rozměrů: A = (1, 4, 2), B = (3, 0, 5). distance Manhattanu je:
|1 − 3| + |4 − 0| + |2 − 5| = 2 + 4 + 3 = 9
Rozšíření na vyšší dimenze a robustnost vůči vychýlení dat
V praxi se často pracuje s daty v 4D, 6D či více dimenzích. Definice zůstává stejná: Manhattan distance(x, y) = Σi |xi − yi|. Výpočet v programech bývá jednoduchý a rychlý, protože zahrnuje jen absolutní hodnoty a součet. Důležité je zvolit reprezentaci dat a normalizaci souřadnic. Pokud mají jednotlivé dimenze velmi odlišné měřítko, maličkým rozdílem se může změnit pořadí blízkých vzorků. V takovém případě je často vhodné normalizovat nebo standardizovat data před výpočtem vzdálenosti.
Aplikace Manhattan distance v datech a strojovém učení
Manhattan distance nachází široké uplatnění v různých oblastech datové vědy. Níže uvádím několik příkladů:
Shlukování a klasifikace
V algoritmech shlukování, zejména v k-means, lze Manhattan distance použít jako metrický vzorec pro výpočet vzdáleností mezi body a středy clusterů. V praxi to znamená, že aktualizace centroidů (středů clusterů) se provádí v souladu s L1 normou. Některé implementace preferují právě estetiku a interpretaci L1, protože zřetelně odráží rozdíly mezi jednotlivými atributy.
Vyhledávání nejbližších sousedů (KNN)
V klasifikaci a regresi pomocí KNN se Manhattan distance používá k vyhledání nejbližších sousedů v trénovacích datech. Užitečné je zejména u dat, která mají jasnou interpretaci v jednotlivých souřadnicích a kde kombinace změn v jednotlivých atributech má významný dopad na příslušnou třídu či hodnotu. Pro rychlost vyhledávání se často používají strukturální datové útvary jako kd-tree, které lze přizpůsobit i pro L1 metriku, či využívají prostorové indexy.
Geoinformatika a mapové systémy
V geodézii a mapových systémech se Manhattan distance někdy používá pro odhady cest v městském prostředí, kdy lze vyjádřit vzdálenost v rámci pravidelné uliční sítě. Samozřejmě je důležité poznamenat, že v skutečném měřítku městských sítí se mohou diapazony lišit v závislosti na šířce ulic a křižovatkách, takže v některých případech se i nadále používají přesnější modely, jako je R-tree a topologické sítě. Nicméně koncept Manhattan distance zůstává užitečným interpretativním nástrojem pro rychlé odhady a porovnání různých lokalit.
Manhattan distance a prostorové uspořádání dat
Když pracujeme s vysokodimenzionálními daty, může být zajímavé zkoumat, jak se vzorky organizují z pohledu jednotlivých souřadnic. Manhattan distance v takových scénářích činí atributy rovnocenné průvodce vzdálenostmi, pokud normalizace nebyla provedena. To znamená, že atributy s různým rozsahem mohou mít různou vliv na výslednou vzdálenost. Z tohoto důvodu bývá doporučeno před výpočtem vzdáleností promítnout data do jednotného měřítka: například standardizace (z- skóre) nebo minima-maxima normalizace.
Odchylky a alternativy: kdy zvolit jiné metriky
V některých scénářích mohou být jiné metriky výhodnější:
Chebyshev distance (L-infinity)
Chebyshev distance se počítá jako maximum absolute difference mezi souřadnicemi. Pro dva body x a y platí:
Chebyshev distance(x, y) = max(|xi − yi|)
V některých hrách, shelfových modelech a hrách s pohybem po čtvercové mříži se může hodit právě tato metrika, kde rozhodující je největší odchylka v jakékoliv souřadnici.
Euclidean distance (L2 norm)
Euclidean distance je tradiční volba pro mnoho problémů v počítačovém vidění, fyzice a geometrii, kde je důležitá skutečná geometrická vzdálenost v prostoru. Vzdálenost mezi dvěmaBody x a y je odmocnina součtu čtverců rozdílů:
distance(x, y) = sqrt(Σi (xi − yi)^2)
Je však méně robustní vůči vysokým dimenzím a některým druhům dat, kde dominují velké rozdíly v určitých souřadnicích.
Praktické tipy pro práci s Manhattan distance v Pythonu
Následující tipy vám pomohou začít a vybudovat jednoduché i pokročilé řešení s Manhattan distance:
Knihovny a základní funkce
V Pythonu lze Manhattan distance spočítat snadno. Základní implementace bez knihoven:
def manhattan_distance(a, b):
return sum(abs(x – y) for x, y in zip(a, b))
Pokud pracujete s většími datasetmi, doporučuje se použít knihovny NumPy pro efektivní vektorový výpočet:
import numpy as np
def manhattan_distance_np(a, b):
a = np.asarray(a)
b = np.asarray(b)
return np.abs(a – b).sum()
Využití distance funkcí z popularních knihoven
Pro pohodlí a výkon můžete využít i hotové funkce z knihoven jako SciPy:
from scipy.spatial.distance import cityblock
distance = cityblock(a, b)
„Cityblock“ je termín v SciPy pro L1 metriku, tedy Manhattan distance.
Normalizace a předzpracování dat
Jak bylo uvedeno dříve, zvažte normalizaci dat, pokud mají různá měřítka souřadnic. Příklady technik:
- Standardizace (z-score): data se transformují na rozdělení s průměrem 0 a směrodatnou odchylkou 1.
- Min-max normalizace: každý atribut se škáluje do intervalu [0, 1].
- Robustní škálování: odolné vůči outlierům, například pomocí mediánu a interkvartilního rozpětí.
Ukázka praktického scénáře: klasifikace s Manhattan distance
Představte si dataset pacientů s atributy jako věk, krevní tlak a cholesterol. Chcete klasifikovat, zda pacient patří do kategorie A nebo B na základě trénovaného modelu s nejbližšími sousedy. Po normalizaci dat můžete použít Manhattan distance pro výběr nejbližších sousedů. Následně klasifikaci provést na základě většiny labels mezi blízkými vzorky. Takový postup je jednoduchý, efektivní a často zřetelný pro interpretaci.
Využití Manhattan distance ve vyšší dimenzi a specializované aplikace
Ve specifických doménách jako je analýza textu, doporučovací systémy či bioinformatika se mohou objevit situace, kdy L1 distance lépe vyjadřuje rozdíly mezi vzorky než jiné metriky. Například v textových údajích často reprezentovaných bag-of-words modelem, kde každý rozměr odpovídá frekvenci či váze určitého slova, se Manhattan distance může ukázat jako jednoduše interpretovatelnější a stabilnější vůči vysokému počtu vzorků a zbytkům vektorů.
Často kladené otázky o Manhattan distance
Je Manhattan distance vhodná pro každý typ dat?
Ne vždy. Manhattan distance nejlépe funguje pro data, která lze rozumně interpretovat jako součty rozdílů jednotlivých atributů. Pokud však data vykazují velmi rozdílné měřítko dimenz, je důležité je normalizovat. V některých aplikacích může být výhodnější Euclidean distance nebo Chebyshev distance, v závislosti na tom, jaké vlastnosti dat jsou pro problémy rozhodující.
Proč bych měl volit Manhattan distance namísto Euclidean distance?
Důležité jsou především praktické aspekty: jednodušší výpočet, odolnost vůči některým typům odchylek a v některých situacích lepší interpretovatelnost. Manhattan distance také lépe odráží „lokální“ rozdíly po jednotlivých osách, což může být výhodné ve scénářích s atributy, které reprezentují nezávisle měřené faktory.
Je možné kombinovat Manhattan distance s jinými metrikami?
Ano. V některých modelech se používají kombinované metriky, například vážená součet L1 a L2, nebo metrika, která zohledňuje specifické atributy více významné než jiné. Například pro smíšená data lze kombinovat Manhattan distance pro numerické atributy a jiné metriky pro kategorické atributy, aby výsledek lépe odpovídal realitě daného problému.
Praktické tipy pro návrh projektů s Manhattan distance
- Prvním krokem je vyjasnění, zda data sedí na mřížově definovaný pohyb a zda součty rozdílů jednotlivých atributů mají interpretaci v daném problému.
- Normalizace dat je klíčová pro stabilní výsledky, zejména pokud mají atributy široká měřítka.
- Vždy si ověřte, zda vaše implementace odpovídá očekávané metrice. V Pythonu se to velmi rychle ověří testovacími případy.
- Pro velké dataset se zaměřte na efektivní knihovny (NumPy, SciPy) a případně zvažte paralelní výpočty nebo projektování indexů pro rychlejší vyhledávání sousedů.
- Pro interpretaci výsledků si pořiďte vizualizaci pro nižší dimenze (např. PCA projektování do 2D) a porovnávejte rozložení dat podle různých metrik.
Shrnutí klíčových myšlenek o Manhattan distance
Manhattan distance je jednoduchá, rychlá a intuitivní metrika vzdálenosti, která vychází z představy pohybu po mříži. Definice je prostá: součet absolutních rozdílů souřadnic. Tato metrika je užitečná zejména v aplikacích, kde jednotlivé atributy mají nezávislou a srozumitelnou interpretaci, kde prostor je „pozdvižený“ po osách a kde rychlost výpočtu a robustnost vůči některým typům šumu bývá žádoucí. Pro správný výsledek je důležité zvažovat normalizaci dat, volbu vhodné dimenze a kompatibilitu s ostatními komponentami vašeho modelu.
Závěr: proč je Manhattan distance v praxi stále relevantní
Manhattan distance zůstává robustní a srozumitelnou volbou pro širokou škálu úloh v datech a strojovém učení. Její výhody – jednoduchost, interpretovatelnost a rychlost – jí zajišťují pevné místo v arzenálu metrík. Ať už pracujete s klasifikací, shlukováním, vyhledáváním nejbližších sousedů, nebo s geoinformatikou, vzdálenost typu Manhattan vám často poskytne přiměřený a stabilní odhad, který je snadné vysvětlit uživatelům i kolegům z týmu. Experimentujte s Manhattan distance v různých scénářích, ale vždy je doplňte o vhodnou normalizaci a porovnání s jinými metrikami, aby vaše řešení bylo co nejpřesnější a nejpřehlednější.