Матрица расстояний

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

Свойства

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

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

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

[math]\displaystyle{ \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} }[/math]


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

Расстояния

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

[math]\displaystyle{ d_{ij} = \left[ \sum_{k=1}^n \left| x_{ik} - x_{jk} \right|^p \right]^\frac{1}{p}. }[/math]

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

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

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

[math]\displaystyle{ 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)|}. }[/math]

Пример

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

Точки на плоскости

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

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

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

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

Примечания

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