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

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

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

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

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

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

Существует множество различных вариантов поиска сходства между двумя точками данных, некоторые из которых представляют собой комбинацию других методов сходства. Некоторые из методов измерения сходства между двумя точками данных включают евклидово расстояние, манхэттенское расстояние, расстояние Минковского и расстояние Чебышева. Формула евклидова расстояния используется для поиска расстояния между двумя точками на плоскости, что визуализировано на изображении ниже. Манхэттенское расстояние обычно используется в приложениях GPS , поскольку его можно использовать для поиска кратчайшего маршрута между двумя адресами. ^{[ необходима цитата ]} При обобщении формулы евклидова расстояния и формулы манхэттенского расстояния остаются формулы расстояния Минковского , которые можно использовать в самых разных приложениях.

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

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

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

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

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

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

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

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

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

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

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

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

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

Другой часто используемой мерой сходства является индекс Жаккара или сходство Жаккара, которое используется в методах кластеризации, работающих с двоичными данными, такими как данные о присутствии/отсутствии ^[3] или логические данные; Сходство Жаккара особенно полезно для методов кластеризации, работающих с текстовыми данными, где его можно использовать для идентификации кластеров похожих документов на основе их общих признаков или ключевых слов. ^[4] Он рассчитывается как размер пересечения двух множеств, деленный на размер объединения двух множеств: . $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$

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Верт, Жан-Филипп; Цуда, Кодзи; Шёлкопф, Бернхард (2004). «Основы методов ядра» (PDF) . Ядерные методы в вычислительной биологии .
^ https://iq.opengenus.org/similarity-measurements/ «Различные типы измерений сходства»
^ Chung, Neo Christopher; Miasojedow, BłaŻej; Startek, Michał; Gambin, Anna (2019). «Тест на сходство Жаккара/Танимото и методы оценки для данных о биологическом присутствии-отсутствии». BMC Bioinformatics . 20 (S15): 644. doi : 10.1186/s12859-019-3118-5 . ISSN 1471-2105. PMC 6929325. PMID 31874610 .
^ Международная мультиконференция инженеров и специалистов по информатике: IMECS 2013: 13–15 марта 2013 г., Royal Garden Hotel, Коулун, Гонконг. SI Ao, Международная ассоциация инженеров. Гонконг: Newswood Ltd. 2013. ISBN 978-988-19251-8-3. OCLC 842831996.{{cite book}}: CS1 maint: другие ( ссылка )
^ ab Ng, AY; Jordan, MI; Weiss, Y. (2001), «О спектральной кластеризации: анализ и алгоритм», Advances in Neural Information Processing Systems , 14 , MIT Press: 849–856
^ Ли, Синь-Йе; Го, Ли-Цзе (2012), «Построение матрицы сродства в спектральной кластеризации на основе распространения соседей», Neurocomputing , 97 : 125–130, doi :10.1016/j.neucom.2012.06.023
^ Бондаренко, Кирилл (2019), Метрики сходства в рекомендательных системах , получено 25 апреля 2023 г.
^ Стейтс, Д.; Гиш, В.; Альтшул, С. (1991). «Повышенная чувствительность поиска в базе данных нуклеиновых кислот с использованием матриц оценки, специфичных для приложений». Методы: дополнение к методам в энзимологии . 3 (1): 66. CiteSeerX 10.1.1.114.8183 . doi :10.1016/S1046-2023(05)80165-3.
^ Шон Р. Эдди (2004). «Откуда взялась матрица оценок выравнивания BLOSUM62?» (PDF) . Nature Biotechnology . 22 (8): 1035–6. doi :10.1038/nbt0804-1035. PMID 15286655. S2CID 205269887. Архивировано из оригинала (PDF) 2006-09-03.
^ Шапиро, Линда ; Джордж Стокман (2001). Компьютерное зрение . Верхняя Сэддл-Ривер, Нью-Джерси: Prentice Hall. ISBN 978-0-13-030796-5.
^ Эйденбергер, Хорст (2011). «Фундаментальное понимание медиа», atpress. ISBN 978-3-8423-7917-6 .

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