Матрица расстояний - Distance matrix

В математика, Информатика и особенно теория графов, а матрица расстояний это квадратная матрица (двумерный массив), содержащий расстояния, взятые попарно, между элементами множества.^[1] В зависимости от используемого приложения расстояние используется для определения этой матрицы, может быть или не быть метрика. Если есть N элементов, эта матрица будет иметь размер N×N. В теоретико-графических приложениях элементы чаще называют точками, узлами или вершинами.

Неметрические матрицы расстояний

В общем случае матрица расстояний представляет собой взвешенную матрица смежности некоторого графа. В сеть, а ориентированный граф с весами, присвоенными дугам, расстояние между двумя узлами сети можно определить как минимум сумм весов на кратчайших путях, соединяющих два узла.^[2] Эта функция расстояния, хотя и хорошо определена, не является метрикой. Не требуется никаких ограничений на веса, кроме необходимости иметь возможность комбинировать и сравнивать их, поэтому в некоторых приложениях используются отрицательные веса. Поскольку пути являются направленными, симметрия не может быть гарантирована, и если существуют циклы, матрица расстояний не может быть пустой.

Алгебраическая формулировка вышеизложенного может быть получена с помощью мин-плюс алгебра. Умножение матриц в этой системе определяется следующим образом: Даны два ${\displaystyle n\times n}$ матрицы ${\displaystyle A=(a_{ij})}$ и ${\displaystyle B=(b_{ij})}$, их произведение расстояния ${\displaystyle C=(c_{ij})=A\star B}$ определяется как ${\displaystyle n\times n}$ матрица такая, что ${\displaystyle c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}}$. Обратите внимание, что недиагональные элементы, которые не связаны напрямую, необходимо установить на бесконечность или подходящее большое значение для правильной работы операций min-plus. Ноль в этих местах будет неправильно интерпретирован как граница без расстояния, стоимости и т. Д.

Если ${\displaystyle W}$ является ${\displaystyle n\times n}$ матрица, содержащая веса ребер график, тогда ${\displaystyle W^{k}}$ (используя это произведение расстояний) дает расстояния между вершинами, используя пути длиной не более ${\displaystyle k}$ края и ${\displaystyle W^{n}}$ - матрица расстояний графа.

Произвольный граф грамм на п вершины можно моделировать как взвешенный полный граф на п вершин, присвоив вес один каждому ребру полного графа, который соответствует ребру грамм и ноль ко всем остальным краям. W для этого полного графа матрица смежности из грамм. Матрица расстояний грамм можно вычислить из W как указано выше, однако, W^п рассчитывается обычным матричное умножение кодирует только количество путей между любыми двумя вершинами длиной не более п.

Матрицы метрических расстояний

Ценность формализма матрицы расстояний во многих приложениях заключается в том, как матрица расстояний может явно кодировать метрические аксиомы и как она поддается использованию методов линейной алгебры. То есть, если M = (Икс_ij) с 1 ≤ я, j ≤ N матрица расстояний для метрического расстояния, тогда

1. все элементы на главной диагонали равны нулю (то есть матрица является полая матрица ), т.е. Икс_ii = 0 для всех 1 ≤ я ≤ N,
2. все недиагональные элементы положительны (Икс_ij > 0 если я ≠ j), (это неотрицательная матрица ),
3. матрица - это симметричная матрица (Икс_ij = Икс_джи), и
4. для любого я и j, Икс_ij ≤ Икс_ik + Икс_кДж для всех k (неравенство треугольника). Это можно выразить в терминах умножение тропических матриц

Когда матрица расстояний удовлетворяет первым трем аксиомам (что делает ее полуметрической), ее иногда называют матрицей предварительных расстояний. Матрица предварительных расстояний, которую можно вложить в евклидово пространство, называется Матрица евклидовых расстояний.

Другой распространенный пример метрической матрицы расстояний возникает в теория кодирования когда в код блока элементы представляют собой строки фиксированной длины по алфавиту, а расстояние между ними задается Расстояние Хэмминга метрика. Наименьший ненулевой элемент в матрице расстояний измеряет способность кода исправлять и обнаруживать ошибки.

Приложения

Иерархическая кластеризация

Матрица расстояний необходима для иерархическая кластеризация.

Филогенетический анализ

Матрицы расстояний используются в филогенетический анализ.

Другое использование

В биоинформатика, матрицы расстояний используются для представления белок структуры независимо от координат, а также попарные расстояния между двумя последовательностями в пространстве последовательностей. Они используются в структурный и последовательный выравнивания, а также для определения белковых структур из ЯМР или же Рентгеновская кристаллография.

Иногда удобнее выражать данные как матрица сходства.

Он используется для определения корреляция расстояний.

Примеры

Например, предположим, что эти данные должны быть проанализированы, где пиксель Евклидово расстояние это метрика расстояния.

Необработанные данные

Матрица расстояний будет следующей:

	а	б	c	d	е	ж
а	0	184	222	177	216	231
б	184	0	45	123	128	200
c	222	45	0	129	121	203
d	177	123	129	0	46	83
е	216	128	121	46	0	83
ж	231	200	203	83	83	0

Затем эти данные можно просмотреть в графической форме как Тепловая карта. На этом изображении черный цвет обозначает расстояние 0, а белый - максимальное расстояние.

Графический вид

Смотрите также

• Кластеризация данных
• Компьютерное зрение
• Умножение матриц мин-плюс

Рекомендации

1. Вейенберг, Г., и Йошида, Р. (2015). Реконструкция филогении: вычислительные методы. В «Алгебраические и дискретные математические методы для современной биологии» (стр. 293-319). Академическая пресса.
2. Фрэнк Харари, Роберт З. Норман и Дорвин Картрайт (1965) Структурные модели: введение в теорию ориентированных графов, страницы 134–8, Джон Уайли и сыновья МИСТЕР0184874