Distanční matice - Distance matrix

v matematika, počítačová věda a hlavně teorie grafů, a matice vzdálenosti je čtvercová matice (dvourozměrné pole) obsahující vzdálenosti, po dvojicích, mezi prvky množiny.^[1] V závislosti na použité aplikaci, vzdálenost používaný k definování této matice může a nemusí být metrický. Pokud existují $N$ prvků, bude mít tato matice velikost $N \times N$ . V graficko-teoretických aplikacích jsou prvky častěji označovány jako body, uzly nebo vrcholy.

Nemetrické matice vzdálenosti

Obecně je matice vzdálenosti vážena matice sousedství nějakého grafu. V síť, a řízený graf s váhami přiřazenými k obloukům lze vzdálenost mezi dvěma uzly sítě definovat jako minimum součtu vah na nejkratších cestách spojujících dva uzly.^[2] Tato funkce vzdálenosti, i když je dobře definována, není metrikou. Na váhy nemusí existovat žádná omezení, kromě nutnosti kombinovat a porovnávat je, takže v některých aplikacích se používají záporné váhy. Vzhledem k tomu, že cesty jsou směrovány, nelze zaručit symetrii a pokud existují cykly, matice vzdálenosti nemusí být prázdná.

Algebraickou formulaci výše uvedeného lze získat pomocí min-plus algebra. Násobení matic v tomto systému je definováno následovně: Dáno dvěma ${ displaystyle n krát n}$ matice ${ displaystyle A = (a_ {ij})}$ a ${ displaystyle B = (b_ {ij})}$ , jejich produkt na dálku ${ displaystyle C = (c_ {ij}) = A hvězda B}$ je definován jako ${ displaystyle n krát n}$ matice taková ${ displaystyle c_ {ij} = min _ {k = 1} ^ {n} {a_ {ik} + b_ {kj} }}$ . Všimněte si, že mimo diagonální prvky, které nejsou přímo připojeny, bude nutné nastavit nekonečno nebo vhodnou velkou hodnotu, aby operace min-plus fungovaly správně. Nula na těchto místech bude nesprávně interpretována jako hrana bez vzdálenosti, nákladů atd.

Li ${ displaystyle W}$ je ${ displaystyle n krát n}$ matice obsahující okrajové závaží a graf, pak ${ displaystyle W ^ {k}}$ (pomocí tohoto produktu vzdálenosti) udává vzdálenosti mezi vrcholy pomocí cest délky maximálně ${ displaystyle k}$ hrany a ${ displaystyle W ^ {n}}$ je matice vzdálenosti grafu.

Libovolný graf $G$ na $n$ vrcholy lze modelovat jako vážený kompletní graf $n$ vrcholy přiřazením váhy jedné každé hraně celého grafu, která odpovídá hraně $G$ a nula ke všem ostatním hranám. $Ž$ pro tento kompletní graf je matice sousedství z $G$ . Matice vzdálenosti $G$ lze vypočítat z $Ž$ jak je uvedeno výše, $Ž n$ vypočteno obvyklým způsobem násobení matic kóduje pouze počet cest mezi libovolnými dvěma vrcholy délky $n$ .

Metrické matice vzdálenosti

Hodnota formalismu matice vzdálenosti v mnoha aplikacích spočívá v tom, jak může matice vzdálenosti zjevně kódovat metrické axiomy a v tom, jak se hodí k použití technik lineární algebry. To je, pokud $M = (X ij)$ s $1 \leq i, j \leq N$ je tedy matice vzdálenosti pro metrickou vzdálenost

položky na hlavní úhlopříčce jsou všechny nulové (tj. matice je a dutá matice ), tj. $X ii = 0$ pro všechny $1 \leq i \leq N$ ,
všechny položky mimo úhlopříčku jsou kladné ( $X ij > 0$ -li $i \neq j$ ), (tj nezáporná matice ),
matice je a symetrická matice ( $X ij = X ji$ ), a
pro všechny $i$ a $j$ , $X ij \leq X ik + X kj$ pro všechny $k$ (nerovnost trojúhelníku). To lze konstatovat z hlediska násobení tropické matice

Když distanční matice splňuje první tři axiomy (což z ní činí polometrickou), je někdy označována jako matice před vzdáleností. Matice předcházející vzdálenosti, kterou lze vložit do euklidovského prostoru, se nazývá a Euklidovská matice vzdálenosti.

Další běžný příklad metrické matice vzdálenosti vzniká v teorie kódování když v blokovat kód prvky jsou řetězce pevné délky nad abecedou a vzdálenost mezi nimi je dána znakem Hammingova vzdálenost metrický. Nejmenší nenulový vstup v matici vzdálenosti měří schopnost kódu opravovat a detekovat chyby.

Aplikace

Hierarchické shlukování

Matice vzdálenosti je nutná pro hierarchické shlukování.

Fylogenetická analýza

Distanční matice se používají v fylogenetická analýza.

Jiná použití

v bioinformatika, k vyjádření se používají matice vzdálenosti protein struktury způsobem nezávislým na souřadnicích, jakož i párové vzdálenosti mezi dvěma sekvencemi v prostoru sekvencí. Používají se v strukturální a sekvenční zarovnání a pro stanovení proteinových struktur z NMR nebo Rentgenová krystalografie.

Někdy je pohodlnější vyjádřit data jako a matice podobnosti.

Používá se k definování korelace vzdálenosti.

Příklady

Předpokládejme například, že tato data mají být analyzována, kde pixel Euklidovská vzdálenost je vzdálenost metrická.

Nezpracovaná data

Matice vzdálenosti by byla:

	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

Tyto údaje lze poté zobrazit v grafické podobě jako a teplotní mapa. Na tomto obrázku černá označuje vzdálenost 0 a bílá je maximální vzdálenost.

Grafické zobrazení

Viz také

Reference

^ Weyenberg, G. a Yoshida, R. (2015). Rekonstrukce fylogeneze: Výpočetní metody. In Algebraické a diskrétní matematické metody pro moderní biologii (str. 293-319). Akademický tisk.
^ Frank Harary Robert Z. Norman a Dorwin Cartwright (1965) Strukturální modely: Úvod do teorie směrovaných grafů, strany 134–8, John Wiley & Sons PAN 0184874

[1] Weyenberg, G. a Yoshida, R. (2015). Rekonstrukce fylogeneze: Výpočetní metody. In Algebraické a diskrétní matematické metody pro moderní biologii (str. 293-319). Akademický tisk.

[2] Frank Harary Robert Z. Norman a Dorwin Cartwright (1965) Strukturální modely: Úvod do teorie směrovaných grafů, strany 134–8, John Wiley & Sons PAN 0184874

[1]

[2]

	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

	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

	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