Matice vzdáleností

Matice vzdáleností je v matematice, matematické informatice a především v teorii grafů čtvercová matice (dvourozměrné pole) obsahující vzdálenosti mezi dvojicemi prvků množiny.^[1] Podle potřeby může mít vzdálenost používaná v této matici různé významy a může, ale nemusí být metrikou. Pro popis vzdáleností mezi prvky n-prvkové množiny bude mít matice vzdáleností velikost $n \times n$ . V grafových aplikacích jsou tyto prvky obvykle označované jako body, uzly nebo vrcholy.

Nemetrické matice vzdáleností

Matice vzdáleností je obecně váženou maticí sousednosti nějakého grafu. V orientovaném grafu, jehož hranám jsou přiřazeny váhy, lze vzdálenost mezi dvěma uzly definovat jako minimum součtů vah hran tvořících nejkratší cestu propojující příslušné dva uzly.^[2] Tato funkce vzdálenosti, přestože je dobře definovaná, není metrikou. Vyžaduje, aby jedinými omezeními na váhy bylo, že je možné je kombinovat a porovnávat. V některých aplikacích se používají záporné váhy. Protože cesty mohou být jednosměrné, nelze zaručit symetrii, a pokud povolíme smyčky, matice vzdáleností může mít na diagonále nenulové hodnoty.

Algebraickou formulaci výše uvedených vlastností lze získat pomocí tropického polookruhu (též min-plus algebra). Násobení matic je v této struktuře definované takto: Jsou-li dány dvě matice $n\times n$ , $A=(a_{ij})$ a $B=(b_{ij})$ , pak jejich součin $C=(c_{ij})=A\star B$ je matice $n\times n$ taková, že $c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\$ . Aby min-plus operace správně fungovaly, musí být hodnoty prvků mimo diagonálu, které nejsou přímo propojené, nastavené na nekonečno nebo na vhodné velmi velké číslo. Nuly by byly nesprávně interpretovány jako hrany nulové vzdálenosti, ceny, apod.

Pokud $W$ je matice $n\times n$ obsahující ohodnocení hran nějakého grafu, pak $W^{k$ (kde mocnina je definována pomocí výše uvedeného součinu) dává vzdálenosti mezi vrcholy s použitím cesty obsahující nejvýše $k$ hran, a $W^{n$ je matice vzdáleností daného grafu.

Libovolný graf $G$ s $n$ vrcholy lze modelovat pomocí ohodnoceného úplného grafu s $n$ vrcholy, v němž váhu 1 mají hrany, které jsou v grafu $G$ , a ostatní hrany mají váhu 0. Matice $W$ tohoto úplného grafu je maticí sousednosti grafu $G$ . Matici vzdáleností grafu $G$ lze vypočítat z $W$ jak je uvedeno výše. Ovšem $W n$ spočítané obvyklým násobením matic kóduje pouze počet cest délky přesně $n$ mezi libovolnými dvěma vrcholy.

Metrické matice vzdáleností

Formalismus matic vzdáleností má v mnoha aplikacích velkou hodnotu, protože srozumitelně kóduje axiomy metriky a umožňuje použití technik lineární algebry. Pokud $M = (x ij)$ pro $1 \leq i, j \leq N$ je matice vzdáleností, které splňují podmínky metriky, pak

všechny hodnoty na hlavní diagonále jsou nulové, tj. $x ii = 0$ pro všechna $1 \leq i \leq N$ ,
všechny hodnoty mimo diagonálu jsou kladné (tj. $x ij > 0$ pro $i \neq j$ ), (tj. matice je nezáporná),
matice je symetrická ( $x ij = x ji$ ), a
pro každé $i$ , $j$ , $k$ platí $x ij \leq x ik + x kj$ (trojúhelníková nerovnost). To lze vyjádřit pomocí tropického maticového násobení

Matice vzdáleností, která vyhovuje prvním třem axiomům (to znamená, že odpovídá semimetrice), se někdy nazývá matice předvzdáleností. Matice předvzdáleností, kterou lze vnořit do eukleidovského prostoru, se nazývá Eukleidovská matice vzdáleností.

Metrické matice vzdáleností se často objevují v teorii kódování. Prvky matice v blokových kódech jsou řetězce pevné délky nad nějakou abecedou, a vzdálenost mezi nimi je metrika určená jejich Hammingovou vzdáleností. Nejmenší nenulová hodnota v matici vzdáleností pak určuje míru schopnosti kódu opravovat a detekovat chyby.

Aplikace

Hierarchické clusterování

Matice vzdáleností jsou nezbytné pro hierarchické shlukování.

Fylogenetická analýza

Matice vzdáleností se používají ve fylogenetické analýze.

Jiná použití

V bioinformatice se matice vzdáleností používají pro souřadnicově nezávislé reprezentace struktury bílkovin, i po dvou vzdálenosti mezi dvěma posloupnosti v posloupnost prostor. Používají se pro zarovnání (alignment) struktur a sekvencí a pro stanovení struktury bílkovin pomocí nukleární magnetické rezonance nebo rentgenové krystalografie.

Někdy je pohodlnější vyjadřovat data pomocí matice podobnosti.

Používá se pro definování vzdálenostní korelace.

Příklad

Předpokládejme například, že se mají analyzovat následující data, kde metrikou vzdálenosti je Eukleidovská vzdálenost v pixelech (obrazových bodech).

Matice vzdáleností je:

	a	b	c	d	e	f
a	0	184	222	177	216	231
b	184	0	45	123	128	200
c	222	45	0	129	121	203
d	177	123	129	0	46	83
e	216	128	121	46	0	83
f	231	200	203	83	83	0

Tato data pak mohou být graficky znázorněna formou teplotní mapy. V tomto obraze černá označuje nulovou vzdálenost a bílá maximální vzdálenost.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Distance matrix na anglické Wikipedii.

↑ WEYENBERG, G.; YOSHIDA, R. Reconstructing the phylogeny: Computational methods. [s.l.]: Academic Press, 2015. S. 293–319.
↑ HARARY, Frank; NORMAN, Robert Z.; CARTWRIGHT, Dorwin. Structural Models: An Introduction to the Theory of Directed Graphs. [s.l.]: John Wiley & Sons, 1965.

Související články

[1] WEYENBERG, G.; YOSHIDA, R. Reconstructing the phylogeny: Computational methods. [s.l.]: Academic Press, 2015. S. 293–319.

[2] HARARY, Frank; NORMAN, Robert Z.; CARTWRIGHT, Dorwin. Structural Models: An Introduction to the Theory of Directed Graphs. [s.l.]: John Wiley & Sons, 1965.

[1]

[2]