Индекс Жаккара , также известный как коэффициент сходства Жаккара , представляет собой статистику, используемую для оценки сходства и разнообразия наборов выборок .
Он был разработан Гроувом Карлом Гилбертом в 1884 году как коэффициент проверки (v) [1] и теперь часто упоминается как критический индекс успеха в метеорологии. [2] Позже он был независимо разработан Полем Жаккаром , первоначально дав французское название коэффициента de communauté , [3] [4] и независимо сформулирован снова Т. Танимото. [5] Таким образом, индекс Танимото или коэффициент Танимото также используются в некоторых областях. Однако они идентичны в том, что обычно принимают отношение пересечения к объединению .
Коэффициент Жаккара измеряет сходство между конечными наборами выборок и определяется как размер пересечения, деленный на размер объединения наборов выборок:
Обратите внимание, что по задумке, если пересечение A B пусто, то J ( A , B ) = 0. Коэффициент Жаккара широко используется в информатике, экологии, геномике и других науках, где используются двоичные или бинаризованные данные . Для проверки гипотез с помощью коэффициента Жаккара доступны как методы точного решения, так и методы аппроксимации. [6]
Сходство Жаккара применимо и к сумкам, т. е. мультисетам . Формула аналогична [7] , но используемые символы обозначают пересечение мешков и сумму мешков (а не объединение). Максимальное значение — 1/2.
Расстояние Жаккара , которое измеряет несходство между наборами выборок, является дополнительным к коэффициенту Жаккара и получается путем вычитания коэффициента Жаккара из 1 или, что то же самое, путем деления разницы размеров объединения и пересечения двух наборов на размер союза:
Альтернативная интерпретация расстояния Жаккара - как отношение размера симметричной разности к объединению. Расстояние Жаккара обычно используется для расчета матрицы размера n × n для кластеризации и многомерного масштабирования n наборов выборок.
Это расстояние является метрикой совокупности всех конечных множеств. [8] [9] [10]
Существует также версия расстояния Жаккара для мер , включая вероятностные меры . Если – мера на измеримом пространстве , то мы определяем коэффициент Жаккара формулой
и расстояние Жаккара на
Необходимо соблюдать осторожность, если или , поскольку в этих случаях эти формулы не определены четко.
Схема хеширования MinHash с независимыми и независимыми перестановками, чувствительной к локальности, может использоваться для эффективного вычисления точной оценки коэффициента сходства Жаккара пар наборов, где каждый набор представлен сигнатурой постоянного размера, полученной из минимальных значений хеш -функции. .
Учитывая два объекта, A и B , каждый из которых имеет n двоичных атрибутов, коэффициент Жаккара является полезной мерой перекрытия, которое A и B разделяют со своими атрибутами. Каждый атрибут A и B может иметь значение 0 или 1. Общее количество каждой комбинации атрибутов для A и B определяется следующим образом:
Каждый атрибут должен относиться к одной из этих четырех категорий, а это означает, что
Коэффициент подобия Жаккара J определяется как
Расстояние Жаккара d J определяется как
Статистические выводы можно сделать на основе коэффициентов сходства Жаккара и, следовательно, связанных с ними показателей. [6] Учитывая два набора выборок A и B с n атрибутами, можно провести статистический тест, чтобы увидеть, является ли перекрытие статистически значимым . Точное решение доступно, хотя вычисления могут быть дорогостоящими по мере увеличения n . [6] Доступны методы оценки либо путем аппроксимации полиномиального распределения , либо путем начальной загрузки. [6]
При использовании для двоичных атрибутов индекс Жаккара очень похож на простой коэффициент соответствия . Основное отличие состоит в том, что SMC имеет этот термин в числителе и знаменателе, а индекс Жаккара — нет. Таким образом, SMC считает как взаимное присутствие (когда атрибут присутствует в обоих наборах), так и взаимное отсутствие (когда атрибут отсутствует в обоих наборах) как совпадения и сравнивает их с общим количеством атрибутов во вселенной, тогда как индекс Жаккара только считает взаимное присутствие совпадением и сравнивает его с количеством атрибутов, выбранных хотя бы одним из двух наборов.
Например, при анализе рыночной корзины корзина двух потребителей, которых мы хотим сравнить, может содержать лишь небольшую часть всех доступных продуктов в магазине, поэтому SMC обычно возвращает очень высокие значения сходства, даже если корзины имеют очень большое сходство. малое сходство, что делает индекс Жаккара более подходящим показателем сходства в этом контексте. Например, рассмотрим супермаркет с 1000 товарами и двумя покупателями. В корзине первого покупателя находятся соль и перец, а в корзине второго — соль и сахар. В этом сценарии сходство между двумя корзинами, измеренное индексом Жаккара, составит 1/3, но при использовании SMC сходство становится 0,998.
В других контекстах, где 0 и 1 несут эквивалентную информацию (симметрию), SMC является лучшей мерой сходства. Например, векторы демографических переменных, хранящихся в фиктивных переменных , таких как пол, лучше сравнивать с SMC, чем с индексом Жаккара, поскольку влияние пола на сходство должно быть одинаковым, независимо от того, определяется ли мужской пол как 0, а женский. как 1 или наоборот. Однако, когда у нас есть симметричные фиктивные переменные, можно воспроизвести поведение SMC, разделив фиктивные переменные на два двоичных атрибута (в данном случае, мужской и женский), преобразуя их таким образом в асимметричные атрибуты, позволяя использовать индекс Жаккара без внесение какой-либо предвзятости. Однако SMC остается более эффективным в вычислительном отношении в случае симметричных фиктивных переменных, поскольку не требует добавления дополнительных измерений.
Если и — два вектора со всеми действительными , то их коэффициент сходства Жаккара (также известный тогда как сходство Ружички) определяется как
и расстояние Жаккара (также известное тогда как расстояние Зёргеля)
В еще большей общности, если и являются двумя неотрицательными измеримыми функциями на измеримом пространстве с мерой , то мы можем определить
где и – поточечные операторы. Тогда расстояние Жаккара равно
Тогда, например, для двух измеримых множеств где и – характеристические функции соответствующего множества.
Описанное выше взвешенное подобие Жаккара обобщает индекс Жаккара на положительные векторы, где набор соответствует двоичному вектору, заданному индикаторной функцией , т.е. Однако он не обобщает индекс Жаккара на распределения вероятностей, где набор соответствует равномерному распределению вероятностей, т.е.
Всегда меньше, если наборы различаются по размеру. Если и тогда
Вместо этого обобщение, которое является непрерывным между распределениями вероятностей и соответствующими наборами поддержки, имеет вид
которая называется «Вероятностью» Жаккара. [11] Он имеет следующие ограничения на взвешенный Жаккар на векторах вероятности.
Здесь верхней границей является (взвешенный) коэффициент Сёренсена–Дайса . Соответствующее расстояние является метрикой распределений вероятностей и псевдометрикой неотрицательных векторов.
Вероятностный индекс Жаккара имеет геометрическую интерпретацию как площадь пересечения симплексов . Каждая точка единичного симплекса соответствует распределению вероятностей элементов, поскольку единичный симплекс представляет собой набор точек в измерениях, сумма которых равна 1. Чтобы геометрически получить индекс Жаккара вероятности, представьте распределение вероятностей в виде единичного симплекса, разделенного на подсимплексы по массе каждого предмета. Если вы наложите два распределения, представленных таким образом, друг на друга и пересечете симплексы, соответствующие каждому элементу, оставшаяся площадь будет равна индексу Жаккара вероятности распределений.
Рассмотрим задачу построения случайных величин так, чтобы они как можно чаще сталкивались друг с другом. То есть, если и , мы хотели бы построить и максимизировать . Если мы посмотрим только на два распределения по отдельности, то максимум, которого мы можем достичь, будет равен где – расстояние общей вариации . Однако предположим, что нас интересует не только максимизация этой конкретной пары, а предположим, что мы хотели бы максимизировать вероятность столкновения любой произвольной пары. Можно построить бесконечное число случайных величин, по одной для каждого распределения , и стремиться к максимизации для всех пар . В довольно строгом смысле, описанном ниже, индекс Жаккара вероятности является оптимальным способом выравнивания этих случайных величин.
Для любого метода выборки и дискретных распределений , если то для некоторых где и , либо или . [11]
То есть ни один метод выборки не может обеспечить большее количество коллизий, чем в одной паре, при этом не добившись меньшего количества коллизий, чем в другой паре, где уменьшенная пара более сходна, чем увеличенная пара. Эта теорема верна для индекса Жаккара множеств (если интерпретировать его как равномерное распределение) и вероятности Жаккара, но не для взвешенного Жаккара. (В теореме используется слово «метод выборки» для описания совместного распределения по всем распределениям в пространстве, поскольку оно основано на использовании алгоритмов взвешенного минхеширования , которые достигают этого как вероятности столкновения.)
Эта теорема имеет наглядное доказательство для трехэлементных распределений с использованием симплексного представления.
В литературе и Интернете встречаются различные формы функций, описываемых как сходство Танимото и расстояние Танимото. Большинство из них являются синонимами сходства Жаккара и расстояния Жаккара, но некоторые математически различны. Многие источники [12] ссылаются на Технический отчет IBM [5] как на основополагающую ссылку. Отчет доступен в нескольких библиотеках.
В «Компьютерной программе для классификации растений», опубликованной в октябре 1960 г. [13] дан метод классификации, основанный на коэффициенте сходства и производной функции расстояния. Кажется, это наиболее авторитетный источник по значению терминов «Сходство Танимото» и «Расстояние Танимото». Коэффициент сходства эквивалентен сходству Жаккара, но функция расстояния не совпадает с расстоянием Жаккара.
В этой статье «коэффициент сходства» дается для растровых изображений , где каждый бит массива фиксированного размера представляет наличие или отсутствие характеристики моделируемого объекта. Определение отношения – это количество общих битов, деленное на количество битов, установленных ( т.е. ненулевых) в любой выборке.
Выражаясь математическими терминами, если выборки X и Y являются растровыми изображениями, являются i- м битом X и являются побитовыми операторами и , или соответственно, то коэффициент сходства равен
Если вместо этого каждая выборка моделируется как набор атрибутов, это значение равно коэффициенту Жаккара двух наборов. Жаккар в статье не цитируется, и вполне вероятно, что авторы об этом не знали. [ нужна цитата ]
Танимото далее определяет «коэффициент расстояния» на основе этого соотношения, определенного для растровых изображений с ненулевым сходством:
Этот коэффициент намеренно не является показателем расстояния. Он выбран таким образом, чтобы два образца, сильно отличающиеся друг от друга, были похожи на третий. Легко построить пример, опровергающий свойство неравенства треугольника .
Расстояние Танимото часто ошибочно называют синонимом расстояния Жаккара . Эта функция является правильной метрикой расстояния. «Расстояние Танимото» часто называют подходящим показателем расстояния, вероятно, из-за его путаницы с расстоянием Жаккара. [ нужны разъяснения ] [ нужна ссылка ]
Если сходство Жаккара или Танимото выражается через битовый вектор, то его можно записать как
где тот же расчет выражается через векторное скалярное произведение и величину. Это представление основано на том факте, что для битового вектора (где значение каждого измерения равно 0 или 1) тогда
и
Это потенциально запутанное представление, поскольку функция, выраженная над векторами, является более общей, если ее область определения явно не ограничена. Свойства не обязательно распространяются на . В частности, разностная функция не сохраняет неравенство треугольника и, следовательно, не является правильной метрикой расстояния, тогда как она есть.
Существует реальная опасность того, что сочетание «Расстояния Танимото», определенного с помощью этой формулы, с утверждением «Расстояние Танимото является правильной метрикой расстояния» приведет к ложному выводу, что функция на самом деле является метрикой расстояния над векторами или мультимножества в целом, тогда как его использование в алгоритмах поиска по сходству или кластеризации может не дать правильных результатов.
Липкус [9] использует определение сходства Танимото, которое эквивалентно , и называет расстояние Танимото функцией . Однако в статье ясно указано, что контекст ограничен использованием (положительного) весового вектора, так что для любого рассматриваемого вектора A : При этих обстоятельствах функция является надлежащей метрикой расстояния, и поэтому набор векторов, управляемых таким весовым вектором, образует метрическое пространство относительно этой функции.
В матрицах путаницы, используемых для бинарной классификации , индекс Жаккара можно представить в виде следующей формулы:
где TP — истинные положительные результаты, FP — ложные положительные результаты и FN — ложные отрицательные результаты. [14]