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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Свойства[править | править исходный текст]

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

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

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

 \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} .


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

Существуют используемые расстояния и вне данного семейства. Наиболее известным является расстояние Махаланобиса.
Также интересно, в качестве удачной иллюстрации связи мер сходства и различия, расстояние Юрцева, двойственное мере сходства Браун-Бланке[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.