Русская Википедия:Матрица расстояний
Матрица расстояний — это квадратная матрица типа «объект-объект» (порядка n), содержащая в качестве элементов расстояния между объектами в метрическом пространстве.
Свойства
Свойства матрицы являются отражением свойств самих расстояний[1]:
- симметричность относительно диагонали, то есть <math> d_{ij} = d_{ji} </math>;
- отражение свойства тождественности расстояния <math>d_{ij}=0 \Leftrightarrow i = j</math> в матрице расстояний проявляется в наличии 0 по диагонали матрицы, так как расстояние объекта с самим собой очевидно равно 0, а также в наличии нулевых значений для абсолютно сходных объектов;
- значения расстояний в матрице всегда неотрицательны <math>d_{ij}\geqslant 0</math>
- неравенство треугольника принимает форму <math>d_{ij}+d_{jk}\geqslant d_{ik}</math> для всех <math>i</math>, <math>j</math> и <math>k</math>.
В общем виде матрица выглядит так:
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> F = 1 - K </math>, где F — мера различия; K — мера сходства. Следовательно, все свойства мер сходства можно экстраполировать на соответствующие им меры различия с помощью простого преобразования и наоборот.
Визуально отношения между объектами можно представить с помощью графовых алгоритмов кластеризации. Можно сказать, что расстояния используются намного чаще, чем меры сходства: их чаще реализуют в статистических программах (Statistica, SPSS и др.) в модуле кластерного анализа.
Расстояния
Известно[2], что существует обобщённая мера расстояний, предложенная Германом Минковским:
- <math> d_{ij} = \left[ \sum_{k=1}^n \left| x_{ik} - x_{jk} \right|^p \right]^\frac{1}{p}. </math>
В вышеуказанное семейство расстояний входит:
- при p = 1 — «манхэттенское расстояние» («расстояние городских кварталов», Шаблон:Lang-en), или «<math>l</math>-норма». Обобщённая мера Хэмминга[3][4] в теоретико-множественной записи (после нормировки) может быть представлена как <math> d_{ij} = n(A) + n(B) - 2n(A \cap B) </math> и являться двойственной мере абсолютного сходства.
- при p = 2 — расстояние Евклида. Часто используется и квадрат этого расстояния.
- при p → ∞ — sup-метрика, или метрика «доминирования». Также известна как расстояние Чебышёва.
Существуют используемые расстояния и вне данного семейства. Наиболее известным является расстояние Махаланобиса.
Также интересно в качестве удачной иллюстрации связи мер сходства и различия расстояние Юрцева, двойственное мере сходства Браун-Бланке[5]:
- <math> 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 |
Полученную матрицу можно изобразить в виде тепловой карты. Здесь более тёмный цвет соответствует меньшему расстоянию между точками.
Примечания
