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

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

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

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

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

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

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

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

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

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

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

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

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

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

При сравнении распределений вероятностей формулы расстояния Махаланобиса, формулы расстояния Бхаттачарьи и формулы расстояния Хеллингера очень эффективны и полезны. Формула расстояния Махаланобиса обычно используется в статистическом анализе . Он измеряет расстояние между двумя распределениями вероятностей, которые имеют разные средние значения и дисперсии. Это делает его полезным для поиска выбросов в наборах данных. Формула расстояния Бхаттачарьи обычно используется при обработке изображений для сравнения двух распределений вероятностей, представляющих разные категории. Например, может использоваться для классификации изображений по их признакам. Расстояние Хеллингера — мощный инструмент для анализа текста и классификации документов. Как правило, он используется для распределений вероятностей, которые представляют частоту употребления разных слов, что позволяет находить похожие документы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Матрицы сходства нуклеотидов используются для выравнивания последовательностей нуклеиновых кислот . Поскольку в ДНК обычно встречаются только четыре нуклеотида ( аденин (А), цитозин (С), гуанин (G) и тимин (Т)), матрицы сходства нуклеотидов намного проще, чем матрицы сходства белков . Например, простая матрица присвоит идентичным основаниям оценку +1, а неидентичным основаниям — оценку -1. Более сложная матрица даст более высокую оценку переходам (переходам от пиримидина , такого как C или T, к другому пиримидину или от пурина, такого как A или G, к другому пурину), чем трансверсиям (от пиримидина к пурину или наоборот). наоборот). Соотношение совпадения/несоответствия матрицы устанавливает целевое эволюционное расстояние. ^{[9] [10]} Матрица ДНК +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 указывает на различную степень сходства между изображениями. Результаты поиска затем можно отсортировать по расстоянию до запрашиваемого изображения. ^[11] Было разработано множество мер расстояния между изображениями (модели сходства). ^[12]

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

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

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

1. Верт, Жан-Филипп; Цуда, Кодзи; Шёлкопф, Бернхард (2004). «Основы методов ядра» (PDF) . Ядерные методы в вычислительной биологии .
2. https://iq.opengenus.org/similarity-measurements/ «Различные типы измерений сходства»
3. Чунг, Нео Кристофер; Мясоедов, Блажей; Стартек, Михал; Гамбен, Анна (2019). «Тест на сходство Жаккара/Танимото и методы оценки данных о биологическом присутствии-отсутствии». БМК Биоинформатика . 20 (S15): 644. doi : 10.1186/s12859-019-3118-5 . ISSN  1471-2105. ПМК 6929325 . ПМИД  31874610. 
4. Международная мультиконференция инженеров и компьютерщиков: IMECS 2013: 13–15 марта 2013 г., отель Royal Garden, Коулун, Гонконг. СИ Ао, Международная ассоциация инженеров. Гонконг: Newswood Ltd. 2013. ISBN. 978-988-19251-8-3. ОСЛК  842831996.{{cite book}}: CS1 maint: другие ( ссылка )
5. Нг, AY; Джордан, Мичиган; Вайс, Ю. (2001), «О спектральной кластеризации: анализ и алгоритм», Достижения в области нейронных систем обработки информации , MIT Press, 14 : 849–856.
6. Ли, Синь-Йе; Го, Ли-Цзе (2012), «Построение аффинной матрицы при спектральной кластеризации на основе распространения соседей», Neurocomputing , 97 : 125–130, doi : 10.1016/j.neucom.2012.06.023
7. Бондаренко, Кирилл (2019), Метрики сходства в рекомендательных системах , дата обращения 25 апреля 2023 г.
8. Джавед, Махнор (2020), «Использование косинусного сходства для создания системы рекомендаций фильмов», Towards Data Science , получено 25 апреля 2023 г.
9. Штаты, Д; Гиш, В; Альтшул, С (1991). «Улучшенная чувствительность поиска в базе данных нуклеиновых кислот с использованием оценочных матриц для конкретных приложений». Методы: дополнение к методам энзимологии . 3 (1): 66. CiteSeerX 10.1.1.114.8183 . дои : 10.1016/S1046-2023(05)80165-3. 
10. Шон Р. Эдди (2004). «Откуда взялась матрица оценок выравнивания BLOSUM62?» (PDF) . Природная биотехнология . 22 (8): 1035–6. дои : 10.1038/nbt0804-1035. PMID  15286655. S2CID  205269887. Архивировано из оригинала (PDF) 3 сентября 2006 г.
11. Шапиро, Линда ; Джордж Стокман (2001). Компьютерное зрение . Река Аппер-Седл, Нью-Джерси: Прентис-Холл. ISBN 978-0-13-030796-5.
12. Эйденбергер, Хорст (2011). «Фундаментальное понимание медиа», atpress. ISBN 978-3-8423-7917-6 . 

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