Matricea distanțelor

Matricea distanțelor este o matrice pătrată obiect la obiect (de ordinul n ), care conține ca elemente distanțele dintre obiecte dintr-un spațiu metric .

Proprietăți

Proprietățile matricei sunt o reflectare a proprietăților distanțelor în sine [1] :

simetria fata de diagonala, adica ; $d_{ij} = d_{ji}$
reflectarea proprietății identității distanței în matricea distanței se manifestă în prezența lui 0 de-a lungul diagonalei matricei, deoarece distanța obiectului cu el însuși este în mod evident 0 și, de asemenea, în prezența valorilor zero pentru absolut similare obiecte; $d_{ij}=0 \Leftrightarrow i = j$
valorile distanței din matrice sunt întotdeauna nenegative $d_{ij}\geqslant 0$
inegalitatea triunghiulară ia forma pentru toate , și . $d_{ij}+d_{jk}\geqslant d_{ik}$ $i$ $j$ $k$

În general, matricea arată astfel:

\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}

Într-un sens larg, distanțele sunt o reflectare a unui astfel de concept precum diferența , care este dual cu conceptul de similaritate , iar elementele matricei de diferențe (în termeni generali, matrice de divergență) sunt duale cu elementele matricei de similaritate ( în general, matrice de convergență ). Relația dintre o măsură a asemănării și o măsură a diferenței poate fi scrisă ca , unde F este o măsură a diferenței; K este o măsură a asemănării. Prin urmare, toate proprietățile de măsurare a similitudinii pot fi extrapolate la măsurile lor de diferență corespunzătoare folosind o transformare simplă și invers. Din punct de vedere vizual, relațiile dintre obiecte pot fi reprezentate folosind algoritmi de grupare grafică . Putem spune că distanțele sunt folosite mult mai des decât măsurile de similaritate: ele sunt mai des implementate în programele statistice ( Statistica , SPSS , etc.) în modulul de analiză a clusterelor . $F = 1 - K$

Distanțe

Se știe [2] că există o măsură generalizată a distanțelor propusă de Hermann Minkowski :

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

Familia de distanțe de mai sus include:

la p = 1 - „ Distanța Manhattan ” („distanța blocurilor”, în engleză city-block ) sau „ -norm”. Măsura Hamming generalizată [3] [4] în notația teoretică a mulțimilor (după normalizare) poate fi reprezentată ca și măsura duală a asemănării absolute . $l$ $d_{ij} = n(A) + n(B) - 2n(A \cap B)$
pentru p = 2 , distanța euclidiană . Pătratul acestei distanțe este, de asemenea, adesea folosit.
ca p → ∞ , este o metrică sup-metrică, sau o metrică de „dominanță”. Cunoscută și ca distanța Chebyshev .

Sunt distante folosite in afara acestei familii. Cea mai cunoscută este distanța Mahalanobis .

Este, de asemenea, interesant, ca o bună ilustrare a legăturii dintre măsurile de similaritate și diferență, distanța Yurtsev , duală cu măsura asemănării 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)|}}.

Exemplu

Există șase puncte diferite pe plan (vezi imaginea). Distanța euclidiană în pixeli a fost aleasă ca metrică .

Matricea distanțelor corespunzătoare va fi egală cu

	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

Matricea rezultată poate fi reprezentată ca o hartă termică . Aici, o culoare mai închisă corespunde unei distanțe mai mici între puncte.

Note

↑ Schrader, Yu. A. Ce este distanța? . — M .: Fizmatgiz , 1963. — 76 p.
↑ Kim, J.-O. , Muller, C.W., Klekka , W.R. , Oldenderfer, M.S. , Blashfield, R.K. Analiză factor, discriminant și cluster. - M. : Finanţe şi statistică, 1989. - 215 p. — ISBN 5-279-00247-X .
↑ Sokal, R. R. , Sneath, P. H. A. Principiile taxonomiei numerice . — San Francisco, Londra: W. H. Freeman and Co., 1963 . — 359 p.
↑ Godron, M. Quelques applications de la notion de fréquence en ecologie végétale (franceză) // Oecol. Plant.. - 1968. - Vol. 3 , nr 3 . _ - P. 185-212 .
↑ Semkin, B. I. La metoda de analiză a seturilor de diferite dimensiuni în floristica comparativă // Lecturi Komarov. - 2009. - Emisiune. 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