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

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

Свойства

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

симметричность относительно диагонали, то есть d i j = d j i {displaystyle d_{ij}=d_{ji}} ;

отражение свойства тождественности расстояния d i j = 0 ⇔ i = j {displaystyle d_{ij}=0Leftrightarrow i=j} в матрице расстояний проявляется в наличии 0 по диагонали матрицы, так как расстояние объекта с самим собой очевидно равно 0, а также в наличии нулевых значений для абсолютно сходных объектов;

значения расстояний в матрице всегда неотрицательны d i j ⩾ 0 {displaystyle d_{ij}geqslant 0}

неравенство треугольника принимает форму d i j + d j k ⩾ d i k {displaystyle d_{ij}+d_{jk}geqslant d_{ik}} для всех i {displaystyle i} , j {displaystyle j} и k {displaystyle k} .

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

[ 0 ⋯ d 1 j ⋯ d 1 n ⋮ ⋯ ⋮ ⋯ ⋮ d i 1 ⋯ d i j ⋯ d i n ⋮ ⋯ ⋮ ⋯ ⋮ d n 1 ⋯ d n j ⋯ 0 ] {displaystyle {egin{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 &0end{bmatrix}}}

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

Расстояния

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

d i j = [ ∑ k = 1 n | x i k − x j k | p ] 1 p . {displaystyle d_{ij}=left[sum _{k=1}^{n}left|x_{ik}-x_{jk} ight|^{p} ight]^{frac {1}{p}}.}

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

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

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

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

F Yu = 1 − K B-B = 1 − n ( A ∩ B ) max ( n ( A ) , n ( B ) ) = n ( A ) + n ( B ) − 2 n ( A ∩ B ) + | n ( A ) − n ( B ) | n ( A ) + n ( B ) − | n ( A ) − n ( B ) | . {displaystyle F_{ ext{Yu}}=1-K_{ ext{B-B}}=1-{frac {n(Acap B)}{max {ig (}n(A),n(B){ig )}}}={frac {n(A)+n(B)-2n(Acap B)+|n(A)-n(B)|}{n(A)+n(B)-|n(A)-n(B)|}}.}