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

Свойства

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

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

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

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

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

Расстояния

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

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

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

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

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

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

${\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)|}}.}$

Пример

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

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

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

Примечания