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. 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 . 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. +more 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}\}. +more 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 s vrcholy lze modelovat pomocí ohodnoceného úplného grafu s vrcholy, v němž váhu 1 mají hrany, které jsou v grafu , a ostatní hrany mají váhu 0. Matice tohoto úplného grafu je maticí sousednosti grafu . +more Matici vzdáleností grafu lze vypočítat z jak je uvedeno výše. Ovšem spočítané obvyklým násobením matic kóduje pouze počet cest délky přesně 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 pro je matice vzdáleností, které splňují podmínky metriky, pak

# všechny hodnoty na hlavní diagonále jsou nulové, tj. pro všechna , # všechny hodnoty mimo diagonálu jsou kladné (tj. +more pro ), (tj. matice je nezáporná), # matice je symetrická , a # pro každé, platí (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í. +more 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).

Syrová data

Matice vzdáleností je:

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.

Grafické znázornění

Odkazy

Reference

Související články

Shluková analýza * Počítačové vidění * Min-plus maticové násobení

Kategorie:Metrická geometrie Kategorie:Bioinformatika Kategorie:Matice Kategorie:Vzdálenosti v grafu