Matice vzdálenosti

Matice vzdálenosti je čtvercová matice objektů (řádu n ), obsahující jako prvky vzdálenosti mezi objekty v metrickém prostoru .

Vlastnosti

Vlastnosti matice jsou odrazem vlastností samotných vzdáleností [1] :

symetrie kolem úhlopříčky, to je ; $d_{ij} = d_{ji}$
odraz vlastnosti identity vzdálenosti v matici vzdálenosti se projevuje v přítomnosti 0 podél úhlopříčky matice, protože vzdálenost objektu sama od sebe je zjevně 0, a také v přítomnosti nulových hodnot pro absolutně podobné předměty; $d_{ij}=0 \Šipka doleva i = j$
hodnoty vzdálenosti v matici jsou vždy nezáporné $d_{ij}\geqslant 0$
trojúhelníková nerovnost má tvar pro všechny , a . $d_{ij}+d_{jk}\geqslant d_{ik}$ $i$ $j$ $k$

Obecně matice vypadá takto:

\begin{bmatrix} 0 & \cdots & d_{1j} & \cdots & d_{1n} \\ \vdots & \cdots & \vdots & \cdots & \vdots \\ d_{i1} & \cdots & d_{ ij} & \cdots & d_{in} \\ \vdots & \cdots & \vdots & \cdots & \vdots \\ d_{n1} & \cdots & d_{nj} & \cdots & 0 \\ \end{ bmatrix}

V širokém smyslu jsou vzdálenosti odrazem takového konceptu, jako je rozdíl , který je duální s pojmem podobnosti , a prvky matice rozdílů (obecně řečeno matice divergence) jsou duální s prvky matice podobnosti ( obecně konvergenční matice ). Vztah mezi mírou podobnosti a mírou rozdílu lze zapsat jako , kde F je míra rozdílu; K je míra podobnosti. Proto lze všechny vlastnosti míry podobnosti extrapolovat na jejich odpovídající rozdílové míry pomocí jednoduché transformace a naopak. Vztahy mezi objekty lze vizuálně reprezentovat pomocí algoritmů shlukování grafů . Dá se říci, že vzdálenosti jsou používány mnohem častěji než míry podobnosti: častěji jsou implementovány ve statistických programech ( Statistica , SPSS atd.) v modulu shlukové analýzy . $F = 1 - K$

Vzdálenosti

Je známo [2] , že existuje zobecněná míra vzdáleností navržená Hermannem Minkowskim :

d_{ij}=\left[\sum _{k=1}^{n}\left|x_{ik}-x_{jk}\right|^{p}\right]^{\frac { 1}{p}}.

Výše uvedená skupina vzdáleností zahrnuje:

při p = 1 - „ vzdálenost Manhattan “ („vzdálenost městských bloků“, anglicky city-block ) nebo „ -norm“. Zobecněná Hammingova míra [3] [4] v množinovém teoretickém zápisu (po normalizaci) může být reprezentována jako a být duální mírou absolutní podobnosti . $l$ $d_{ij} = n(A) + n(B) - 2n(A \cap B)$
pro p = 2 , euklidovská vzdálenost . Často se také používá čtverec této vzdálenosti.
jako p → ∞ jde o sup-metriku neboli metriku „dominance“. Také známý jako Chebyshev vzdálenost .

Mimo tuto rodinu se používají vzdálenosti. Nejznámější je Mahalanobisova vzdálenost .

Zajímavá je také, jako dobrá ilustrace spojení mezi mírami podobnosti a rozdílu, Yurtsevova vzdálenost , duální s mírou podobnosti Brown-Blanque [5] :

F_{\text{Yu}}=1-K_{\text{BB}}=1-{\frac {n(A\cap B)}{\max {\big (}n(A), n(B){\big )))}={\frac {n(A)+n(B)-2n(A\cap B)+|n(A)-n(B)|}{n(A )+n(B)-|n(A)-n(B)|}}.

Příklad

V rovině je šest různých bodů (viz obrázek). Jako metrika byla zvolena euklidovská vzdálenost v pixelech .

Odpovídající matice vzdálenosti bude rovna

	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

Výsledná matice může být reprezentována jako teplotní mapa . Zde tmavší barva odpovídá menší vzdálenosti mezi body.

Poznámky

↑ Schrader, Yu. A. Co je vzdálenost? . — M .: Fizmatgiz , 1963. — 76 s.
↑ Kim, J.-O. , Muller, C. W., Klekka , W. R. , Oldenderfer, M. S. , Blashfield , R. K. Faktorová, diskriminační a shluková analýza. - M. : Finance a statistika, 1989. - 215 s. — ISBN 5-279-00247-X .
↑ Sokal, R. R. , Sneath, P. H. A. Principy numerické taxonomie . — San Francisco, Londýn: W. H. Freeman and Co., 1963. — 359 s.
↑ Godron, M. Quelques aplikace de la pojem de fréquence en ecologie végétale (francouzsky) // Oecol. Plant.. - 1968. - Sv. 3 , č . 3 . - str. 185-212 .
↑ Semkin, B. I. K metodě analýzy různě velkých souborů ve srovnávací floristice // Komarov Readings. - 2009. - Vydání. LVI . - S. 170-185 .

	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