Мера сходства

«Матрица сходства» перенаправляется сюда. Чтобы узнать о концепции линейной алгебры, см. « Сходство матриц» .

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

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

Использование различных формул меры сходства

Для разных типов объектов существуют разные типы мер сходства в зависимости от сравниваемых объектов. Для каждого типа объектов существуют различные формулы измерения сходства.

Сходство между двумя точками данных

На изображении показан путь расчета при использовании формулы евклидова расстояния.

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

• Евклидово расстояние
• Расстояние Манхэттен
• Расстояние Минковского
• Расстояние Чебышева

Сходство между строками

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

• Изменить расстояние
• Расстояние Левенштейна
• Расстояние Ли
• Расстояние Хэмминга
• Через год

Сходство между двумя распределениями вероятностей

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

• Расстояние Бхаттачарья
• Расстояние Хеллингера

Сходство между двумя наборами

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

• Индекс Жаккара
• Коэффициент Серенсена – Дайса

Сходство между двумя последовательностями

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

• Динамическое искажение времени

Использование в кластеризации

См. также: Иерархическая кластеризация § Метрика сходства

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

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

Одной из наиболее часто используемых мер сходства является евклидово расстояние , которое используется во многих методах кластеризации, включая кластеризацию K-средних и иерархическую кластеризацию . Евклидово расстояние — это мера расстояния по прямой между двумя точками в многомерном пространстве. Он рассчитывается как квадратный корень из суммы квадратов разностей между соответствующими координатами двух точек. Например, если у нас есть две точки данных $(x_{1},y_{1})$ и $(x_{2},y_{2})$, евклидово расстояние между ними равно $d=\surd [(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}]$.

Тепловая карта региона HIST1, расположенного на 13 хромосоме мыши по следующим координатам: [21,7 Мб, 24,1 Мб].

Другой часто используемой мерой сходства является индекс Жаккара или сходство Жаккара, который используется в методах кластеризации, работающих с двоичными данными, такими как данные о присутствии/отсутствии. или логические данные; Сходство Жаккара особенно полезно для методов кластеризации, работающих с текстовыми данными, где его можно использовать для идентификации кластеров похожих документов на основе их общих функций или ключевых слов. Он рассчитывается как размер пересечения двух множеств, деленный на размер объединения двух множеств: $J(A,B)={A\bigcap B \over A\bigcup B}$.

Сходства среди 162 соответствующих ядерных профилей проверяются с использованием меры сходства Жаккара (см. рисунок с тепловой картой). Сходство ядерного профиля по Жаккару варьируется от 0 до 1, где 0 указывает на отсутствие сходства между двумя наборами, а 1 указывает на полное сходство с целью кластеризации наиболее похожего ядерного профиля.

Манхэттенское расстояние, также известное как геометрия такси , является широко используемой мерой сходства в методах кластеризации, которые работают с непрерывными данными. Это мера расстояния между двумя точками данных в многомерном пространстве, рассчитываемая как сумма абсолютных разностей между соответствующими координатами двух точек. $\left\vert x_{1}-x_{2}\right\vert +\left\vert y_{1}-y_{2}\right\vert$.

При работе с данными смешанного типа, включая номинальные, порядковые и числовые атрибуты для каждого объекта, расстояние Гауэра (или сходство) является распространенным выбором, поскольку оно может неявно обрабатывать различные типы переменных. Сначала он вычисляет сходство между парой переменных в каждом объекте, а затем объединяет эти сходства в одно взвешенное среднее значение для каждой пары объектов. Таким образом, для двух объектов $i$ и $j$ имея $p$ дескрипторы, сходство $S$ определяется как: $$S_{ij}={\frac {\sum _{k=1}^{p}w_{ijk}s_{ijk}}{\sum _{k=1}^{p}w_{ijk}}},$$ где $w_{ijk}$ являются неотрицательными весами и $s_{ijk}$ это сходство между двумя объектами относительно их $k$-я переменная.

При спектральной кластеризации мера сходства или близости используется для преобразования данных, чтобы преодолеть трудности, связанные с отсутствием выпуклости в форме распределения данных. Эта мера приводит к $(n,n)$-размерный матрица сходства для набора из n точек, где запись $(i,j)$ (обратным) в матрице может быть просто евклидовым расстоянием между $i$ и $j$или это может быть более сложная мера расстояния, такая как гауссова мера $e^{-\|s_{1}-s_{2}\|^{2}/2\sigma ^{2}}$. Также распространено дальнейшее изменение этого результата с помощью методов сетевого анализа.

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

Использование в рекомендательных системах

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

Рекомендательные системы наблюдаются на многих развлекательных онлайн-платформах, в социальных сетях и на веб-сайтах потокового вещания. Логика построения этих систем основана на мерах подобия.

Использование для выравнивания последовательности

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

Матрицы сходства нуклеотидов используются для выравнивания последовательностей нуклеиновых кислот . обычно встречаются только четыре нуклеотида Поскольку в ДНК ( аденин (А), цитозин (С), гуанин (G) и тимин (Т)), матрицы сходства нуклеотидов намного проще, чем матрицы сходства белков . Например, простая матрица присвоит идентичным основаниям оценку +1, а неидентичным основаниям — оценку -1. Более сложная матрица даст более высокую оценку переходам (переходам от пиримидина, такого как C или T, к другому пиримидину или от пурина, такого как A или G, к другому пурину), чем трансверсиям (от пиримидина к пурину или наоборот). наоборот).Соотношение совпадения/несоответствия матрицы устанавливает целевое эволюционное расстояние. Матрица ДНК +1/-3, используемая BLASTN, лучше всего подходит для поиска совпадений между последовательностями, идентичными на 99%; матрица +1/-1 (или +4/-4) гораздо больше подходит для последовательностей со сходством около 70%. Матрицы для последовательностей с более низким сходством требуют более длительного выравнивания последовательностей.

Матрицы сходства аминокислот кодирует 20 аминокислот более сложны, поскольку генетический код и, следовательно, большее количество возможных замен. Поэтому матрица сходства аминокислот содержит 400 записей (хотя обычно она симметрична ). Первый подход оценивал все аминокислотные изменения одинаково. Более позднее усовершенствование заключалось в определении сходства аминокислот на основе того, сколько изменений оснований потребовалось для изменения кодона, кодирующего эту аминокислоту. Эта модель лучше, но она не учитывает селективное давление замен аминокислот. Лучшие модели учитывали химические свойства аминокислот.

Один из подходов заключался в эмпирическом создании матриц сходства. В методе Дайхоффа использовались филогенетические деревья и последовательности, взятые у видов на дереве. Этот подход привел к появлению PAM серии матриц . Матрицы PAM маркируются в зависимости от того, сколько изменений нуклеотидов произошло на 100 аминокислот. Хотя матрицы PAM выигрывают от хорошо понятной эволюционной модели, они наиболее полезны на коротких эволюционных расстояниях (PAM10–PAM120). Было показано, что на больших эволюционных дистанциях, например PAM250 или 20% идентичности, матрицы BLOSUM гораздо более эффективны.

Серия BLOSUM была создана путем сравнения ряда расходящихся последовательностей. Серии BLOSUM маркируются на основе того, сколько энтропии остается неизменной между всеми последовательностями, поэтому более низкий номер BLOSUM соответствует более высокому номеру PAM.

Использование в компьютерном зрении

Этот раздел представляет собой отрывок из статьи «Поиск изображений на основе контента § Сравнение контента с использованием показателей расстояния между изображениями» . [ редактировать ]

Самый распространенный метод сравнения двух изображений при поиске изображений на основе контента (обычно изображения-примера и изображения из базы данных) — использование меры расстояния между изображениями. Мера расстояния изображения сравнивает сходство двух изображений по различным параметрам, таким как цвет, текстура, форма и другие. Например, расстояние 0 означает точное совпадение с запросом по рассматриваемым измерениям. Как можно интуитивно понять, значение больше 0 указывает на различную степень сходства между изображениями. Результаты поиска затем можно отсортировать по расстоянию до запрашиваемого изображения. Было разработано множество мер расстояния изображения (модели сходства).

См. также

• Распространение сходства - алгоритм интеллектуального анализа данных
• Скрытое пространство - встраивание данных в многообразие на основе функции подобия.
• Обучение по подобию - контролируемое обучение функции подобия.
• Матрица самоподобия
• Семантическое сходство – обработка естественного языка
• Сходство (сетевая наука) - в сетевом анализе, когда два узла (или другие более сложные структуры) попадают в один и тот же класс эквивалентности. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Сходство (философия) - Отношение сходства между объектами.
• Статистическое расстояние – расстояние между двумя статистическими объектами.
• Строковая метрика – метрика, измеряющая расстояние между двумя строками текста. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Поиск по сходству – поиск похожих элементов в наборе данных.
• tf–idf – Оценка важности слова в документе.
• График повторений , инструмент визуализации повторений в динамических (и других) системах.

Ссылки

• Ф. Грегори Эшби; Дэниел М. Эннис (2007). «Меры сходства» . Схоларпедия . 2 (12): 4116. Бибкод : 2007SchpJ...2.4116A . дои : 10.4249/scholarpedia.4116 .