Введение

Квадратная матрица, содержащая расстояния между элементами множества.

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

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

В общем, матрица расстояний — это матрица взвешенной смежности некоторого графа. В сети, представляющей собой ориентированный граф с весами, присвоенными дугам, расстояние между двумя узлами сети может быть определено как минимум сумм весов на кратчайших путях, соединяющих эти два узла. Эта функция расстояния, хотя и корректно определена, не является метрикой. На веса не должно быть никаких ограничений, кроме возможности их комбинирования и сравнения, поэтому отрицательные веса используются в некоторых приложениях. Поскольку пути ориентированы, симметрия не гарантируется, и если существуют циклы, матрица расстояний может быть не разреженной. Алгебраическая формулировка вышеописанного может быть получена с помощью алгебры «минимум плюс». Умножение матриц в этой системе определяется следующим образом: для двух матриц n × n и , их произведение расстояний определяется как матрица n × n, такая что

Следует отметить, что элементы вне главной диагонали, которые не связаны напрямую, должны быть установлены в бесконечность или достаточно большое значение для корректной работы операций «минимум плюс». Нуль в этих позициях будет неверно интерпретирован как ребро без расстояния, стоимости и т. д. Если W — это матрица n × n, содержащая веса ребер графа, то (используя это произведение расстояний) дает расстояния между вершинами, используя пути длиной не более k ребер, а — это матрица расстояний графа. Произвольный граф G на n вершинах может быть смоделирован как взвешенный полный граф на n вершинах, присваивая вес один каждому ребру полного графа, соответствующему ребру G, и ноль всем остальным ребрам. Матрица W для этого полного графа является матрицей смежности G. Матрица расстояний G может быть вычислена из W, как описано выше, однако, , вычисленная с помощью обычного умножения матриц, кодирует только количество путей между любыми двумя вершинами длиной ровно n.

Биоинформатика

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

Выровнение последовательности

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

Глобальное выравнивание

Алгоритм Нидлмана-Вунша, используемый для вычисления глобального выравнивания, применяет динамическое программирование для получения матрицы расстояний.

Местное выравнивание

Алгоритм Смита-Уотермана также основан на динамическом программировании и включает в себя построение матрицы расстояний и последующее получение локального выравнивания.

МАФФТ

Многократное выравнивание с использованием быстрого преобразования Фурье (MAFFT) — это программа с алгоритмом, основанным на прогрессивном выравнивании, предлагающая различные стратегии множественного выравнивания. Сначала MAFFT строит матрицу расстояний на основе количества общих 6-меров. Затем, на основе этой матрицы, строится направляющее дерево. Далее последовательности кластеризуются с помощью быстрого преобразования Фурье, после чего начинается выравнивание. На основе полученного выравнивания направляющее дерево перестраивается, и выравнивание повторяется.

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

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

Методы матрицы расстояний

Методы филогенетического анализа, основанные на матрице расстояний, явно опираются на меру "генетического расстояния" между классифицируемыми последовательностями и, следовательно, требуют нескольких последовательностей в качестве входных данных. Методы, использующие матрицу расстояний, стремятся построить матрицу "все к каждому" на основе набора запрошенных последовательностей, описывающую расстояние между каждой парой последовательностей. На основе этой матрицы строится филогенетическое дерево, которое объединяет близкородственные последовательности под одним внутренним узлом, а длины ветвей дерева соответствуют наблюдаемым расстояниям между последовательностями. Методы матриц расстояний могут создавать как укорененные, так и неукорененные деревья, в зависимости от используемого алгоритма расчета. Для n видов входными данными являются матрица расстояний n × n M, где Mij представляет собой расстояние мутаций между видами i и j. Цель состоит в том, чтобы получить дерево степени 3, которое соответствует матрице расстояний. Они часто используются в качестве основы для прогрессивных и итеративных методов множественного выравнивания последовательностей. Основным недостатком методов матриц расстояний является их неспособность эффективно использовать информацию о локальных областях с высокой изменчивостью, встречающихся в нескольких поддеревьях.

Фич-Марголиаш

Метод Fitch — Margoliash использует метод взвешенных наименьших квадратов для кластеризации на основе генетического расстояния. В процессе построения дерева более высокий вес придается близкородственным последовательностям, чтобы скорректировать возросшую неточность при измерении расстояний между далёкородственными последовательностями. Критерий наименьших квадратов, применяемый к этим расстояниям, является более точным, но менее эффективным, чем методы присоединения соседей. Дополнительное улучшение, корректирующее корреляции между расстояниями, возникающие из-за большого количества близкородственных последовательностей в наборе данных, также может быть применено, но требует больших вычислительных затрат.

Добыча данных

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

Машинное обучение

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

Компьютерное зрение

Матрица расстояний может использоваться в нейронных сетях для регрессии из 2D в 3D в моделях машинного обучения, предназначенных для предсказания изображений.

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

Гауссово расстояние смеси для точного поиска ближайших соседей в задачах информационного поиска. Основываясь на установленной модели конечной гауссовой смеси для распределения данных в базе данных, гауссово расстояние смеси формируется путем минимизации расхождения Кульбака — Лейблера между распределением запроса и распределением данных в базе данных. Экспериментальные результаты, демонстрирующие превосходство гауссова расстояния смеси над известными евклидовым и махаланобисовым расстояниями при оценке точности, показывают, что гауссова функция расстояния смеси превосходит их для различных типов тестовых данных. Среди перспективных базовых алгоритмов в области информационного поиска следует отметить алгоритм поиска стаи рыб, использующий матрицы расстояний для моделирования коллективного поведения рыбных стай. Веса обновляются с помощью оператора, имитирующего процесс питания.

Уравнение A:

Уравнение B:

Stepvol определяет размер максимального объема смещения, вычисляемого с использованием матрицы расстояний, в частности, евклидовой матрицы расстояний.

Оценка сходства или несоответствия матриц сходства косинусов и расстояний

В то время как мера косинусного сходства, пожалуй, является наиболее часто используемой мерой близости в информационном поиске, измеряющей углы между документами в поисковом пространстве на основе косинуса, евклидово расстояние инвариантно к центрированию данных. Выборочное распределение среднего вычисляется путем многократного отбора проб из одной и той же генеральной совокупности и записи полученных выборочных средних. Это формирует распределение различных средних значений, которое само имеет свое среднее и дисперсию. Для данных, которые могут быть как отрицательными, так и положительными, нулевое распределение для косинусного сходства представляет собой распределение скалярного произведения двух независимых случайных единичных векторов. Это распределение имеет среднее значение, равное нулю, и дисперсию, равную 1/n. При этом евклидово расстояние остаётся инвариантным к центрированию.

Кластерные документы

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

Изокарта

Изомапа использует матрицы расстояний для вычисления геодезических расстояний и, как следствие, получения низкоразмерных представлений. Это позволяет эффективно работать с коллекциями документов, представленных в большом числе измерений, и выполнять кластеризацию этих документов.

Визуализатор поиска соседства (NeRV)

Алгоритм, используемый как для неконтролируемой, так и для контролируемой визуализации, который применяет матрицы расстояний для выявления схожих данных, основываясь на сходстве, отображаемом на дисплее или экране. Матрица расстояний, необходимая для неконтролируемой NeRV, может быть вычислена на основе заданных парных расстояний. Для контролируемой NeRV требуется разработка метрики контролируемого расстояния, чтобы вычислять расстояние до входных данных контролируемым способом.

Химия

Матрица расстояний — математический объект, широко используемый как в графотеоретических (топологических), так и в геометрических (топографических) вариантах химии. Матрица расстояний применяется в химии как в явном, так и в неявном виде.

Механизмы межконверсии между двумя пермутационными изомерами

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

Полиномы расстояний и спектры расстояний

Для построения полиномов расстояний и спектров расстояний молекулярных структур необходимо явное использование матриц расстояний.

Модель структуры-собственности

Неявное использование матриц расстояний было применено посредством метрики, основанной на расстоянии, – числа Вайнера / индекса Вайнера, сформулированной для представления расстояний во всех химических структурах. Число Вайнера равно половине суммы элементов матрицы расстояний.

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

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

Создание помеченного графа с весами ребер, используемого в теории химических графов для представления молекул, содержащих гетероатомы. Метод Le Verrier Fadeev Frame (LVFF) – это алгоритм, ориентированный на компьютерные вычисления, используемый для ускорения процесса определения центра графа в полициклических графах. Однако LVFF требует на вход диагонализированную матрицу расстояний, что легко решается путем реализации тридиагонального QL-алгоритма Хаусхолдера, который принимает матрицу расстояний и возвращает необходимую диагонализированную матрицу для метода LVFF.

Матрица геометрического расстояния

В то время как матрица расстояний на основе теории графов 2D отражает конституционные особенности молекулы, ее трехмерный (3D) характер кодируется в матрице геометрических расстояний. Матрица геометрических расстояний – это иной тип матрицы расстояний, который, основываясь на матрице расстояний на основе теории графов молекулы, позволяет представить и визуализировать ее 3D структуру. Матрица геометрических расстояний молекулярной структуры G представляет собой вещественную симметричную матрицу n x n, определяемую аналогично 2D матрице. Однако элементы матрицы D<sub>ij</sub> содержат набор кратчайших декартовых расстояний между атомами i и j в G. Также известная как топографическая матрица, матрица геометрических расстояний может быть построена на основе известной геометрии молекулы. В качестве примера, ниже представлена матрица геометрических расстояний углеродного скелета 2,4-диметилгексана:

Анализ временных рядов

Матрицы расстояний, вычисленные с помощью динамического выравнивания по времени, используются с алгоритмами кластеризации и классификации набора/группы объектов временных рядов.