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

Матрица расстояний - это квадратная матрица типа "объект-объект" (порядка n) содержащая в качестве элементов расстояния между объектами в метрическом пространстве.
Свойства матрицы являются отражением свойств самих расстояний^[1]:

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

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

$\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 ] ^{1 \over p}$.

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

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

Существуют используемые расстояния и вне данного семейства. Наиболее известным является расстояние Махаланобиса.
Также интересно, в качестве удачной иллюстрации связи мер сходства и различия, расстояние Юрцева, двойственное мере сходства Браун-Бланке^[5]:

$F_{Yu} = 1 - K_{B-B} = 1 - \frac{n(A \cap B)}{max(n(A),n(B))} = \frac{n(A) + n(B) - 2n(A \cap B)+ |n(A) - n(B)|}{n(A) + n(B) - |n(A) - n(B)|}$.

Литература и примечания

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