PROFILPELAJAR.COM

Матрица расстояний — это квадратная матрица типа «объект-объект» (порядка n), содержащая в качестве элементов расстояния между объектами в метрическом пространстве.

Свойства

Свойства матрицы являются отражением свойств самих расстояний^[1]:

симметричность относительно диагонали, то есть $d_{ij}=d_{ji}$ ;
отражение свойства тождественности расстояния $d_{ij}=0\Leftrightarrow i=j$ в матрице расстояний проявляется в наличии 0 по диагонали матрицы, так как расстояние объекта с самим собой очевидно равно 0, а также в наличии нулевых значений для абсолютно сходных объектов;
значения расстояний в матрице всегда неотрицательны $d_{ij}\geqslant 0$
неравенство треугольника принимает форму $d_{ij}+d_{jk}\geqslant d_{ik}$ для всех $i$ , $j$ и $k$ .

В общем виде матрица выглядит так:

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

В широком смысле расстояния являются отражением такого понятия как различие, что двойственно понятию сходства, а элементы матрицы различия (в общем виде — матрицы дивергенций) двойственны элементам матрицы сходства (в общем виде — матрицы конвергенций). Связь между мерой сходства и мерой различия можно записать как $F=1-K$ , где F — мера различия; K — мера сходства. Следовательно, все свойства мер сходства можно экстраполировать на соответствующие им меры различия с помощью простого преобразования и наоборот.
Визуально отношения между объектами можно представить с помощью графовых алгоритмов кластеризации. Можно сказать, что расстояния используются намного чаще, чем меры сходства: их чаще реализуют в статистических программах (Statistica, SPSS и др.) в модуле кластерного анализа.

Расстояния

Известно^[2], что существует обобщённая мера расстояний, предложенная Германом Минковским:

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

В вышеуказанное семейство расстояний входит:

при p = 1 — «манхэттенское расстояние» («расстояние городских кварталов», англ. city-block), или « $l$ -норма». Обобщённая мера Хэмминга^[3]^[4] в теоретико-множественной записи (после нормировки) может быть представлена как $d_{ij}=n(A)+n(B)-2n(A\cap B)$ и являться двойственной мере абсолютного сходства.
при p = 2 — расстояние Евклида. Часто используется и квадрат этого расстояния.
при p → ∞ — sup-метрика, или метрика «доминирования». Также известна как расстояние Чебышёва.

Существуют используемые расстояния и вне данного семейства. Наиболее известным является расстояние Махаланобиса.

Также интересно в качестве удачной иллюстрации связи мер сходства и различия расстояние Юрцева, двойственное мере сходства Браун-Бланке^[5]:

F_{\text{Yu}}=1-K_{\text{B-B}}=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)|}}.

Пример

На плоскости расположено шесть различных точек (см. изображение). В качестве метрики выбрано расстояние Евклида в пикселях.

Соответствующая матрица расстояний будет равна

	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

Полученную матрицу можно изобразить в виде тепловой карты. Здесь более тёмный цвет соответствует меньшему расстоянию между точками.

Матрица расстояний в виде тепловой карты

Примечания

↑ Шрейдер, Ю. А. Что такое расстояние? . — М.: Физматгиз, 1963. — 76 с.
↑ Ким, Дж.-О., Мьюллер, Ч. У., Клекка, У. Р., Олдендерфер, М. С., Блэшфилд, Р. К.. Факторный, дискриминантный и кластерный анализ. — М.: Финансы и статистика, 1989. — 215 с. — ISBN 5-279-00247-X.
↑ Sokal, R. R., Sneath, P. H. A.. Principles of numerical taxonomy (англ.). — San Francisco, London: W. H. Freeman and Co., 1963 . — 359 p.
↑ Godron, M.. Quelques applications de la notion de fréquence en écologie végétale (фр.) // Oecol. Plant.. — 1968. — Vol. 3, n^o 3. — P. 185—212.
↑ Сёмкин, Б. И.. К методике анализа разновеликих множеств в сравнительной флористике // Комаровские чтения. — 2009. — Вып. LVI. — С. 170—185.