. индекс Жаккарда, также известный как пересечение по объединению и Коэффициент сходства Жаккара (первоначально присвоенный французскому названию «коэффициент коммунауте» от Пола Жаккара ) - это статистика, используемая для оценки сходства и разнообразие из выборок наборов. Коэффициент Жаккара измеряет сходство между конечными выборочными наборами и определяется как размер пересечения, деленный на размер union наборов выборок:
(Если A и B оба пусты, определите J (A, B) = 1.)
Расстояние Жаккара, которое измеряет несходство между наборами выборок, является дополнением к коэффициенту Жаккара и получается путем вычитания коэффициента Жаккара из 1, или, что то же самое, делением разницы размеров объединения и пересечения двух множеств на размер объединения:
Альтернативная интерпретация расстояния Жаккара - это отношение размера симметричной разности в союз. Расстояние Жаккара обычно используется для вычисления матрицы размера n × n для кластеризации и многомерного масштабирования n наборов выборок.
Это расстояние является метрикой на совокупности всех конечных множеств.
Существует также версия расстояния Жаккара для мер, включая вероятностные меры. Если - это мера на измеримом пространстве , тогда мы определяем Коэффициент Жаккара на
и расстояние Жаккара на
Следует проявлять осторожность, если или , поскольку в этих случаях эти формулы не определены должным образом.
Схема MinHash минимальных независимых перестановок хеширования с учетом местоположения может использоваться для эффективного вычисления точной оценки коэффициента подобия Жаккара пар наборов, где каждый набор представлен сигнатурой постоянного размера, полученной из минимальных значений хэш-функции .
Даны два объекта, A и B, каждый с n двоичных атрибутов коэффициент Жаккара является полезной мерой перекрытия которые A и B разделяют со своими атрибутами. Каждый атрибут A и B может быть 0 или 1. Общее количество каждой комбинации атрибутов для A и B указано следующим образом:
A | |||
---|---|---|---|
0 | 1 | ||
B | 0 | ||
1 |
Каждый атрибут должен попадать в одну из этих четырех категорий, то есть что
Коэффициент подобия Жаккара, J, задается как
Расстояние Жаккара, d J, задается как
При использовании для двоичных атрибутов индекс Жаккарта очень похож на простой коэффициент соответствия. Основное отличие состоит в том, что в числителе и знаменателе SMC есть термин , тогда как в индексе Жаккара нет. Таким образом, SMC считает как взаимное присутствие (когда атрибут присутствует в обоих наборах), так и взаимное отсутствие (когда атрибут отсутствует в обоих наборах) как совпадения и сравнивает его с общим количеством атрибутов во вселенной, тогда как индекс Жаккарда только считает взаимное присутствие совпадениями и сравнивает его с количеством атрибутов, которые были выбраны хотя бы одним из двух наборов.
В анализе корзины, например, корзина из двух потребителей, которых мы хотим сравнить, может содержать только небольшую часть всех доступных в магазине товаров, поэтому SMC обычно возвращают очень высокие значения сходства, даже если корзины очень мало похожи, что делает индекс Жаккара более подходящей мерой сходства в этом контексте. Например, рассмотрим супермаркет с 1000 товарами и двумя покупателями. Корзина первого покупателя содержит соль и перец, а корзина второго - соль и сахар. В этом сценарии сходство между двумя корзинами, измеренное индексом Жаккара, будет 1/3, но схожесть становится 0,998 с использованием SMC.
В других контекстах, где 0 и 1 несут эквивалентную информацию (симметрию), SMC является лучшей мерой сходства. Например, векторы демографических переменных, хранящиеся в фиктивных переменных, таких как пол, будут лучше сравниваться с SMC, чем с индексом Жаккара, поскольку влияние пола на сходство должно быть одинаковым, независимо от того, является ли мужчина определяется как 0, а женский - как 1 или наоборот. Однако, когда у нас есть симметричные фиктивные переменные, можно воспроизвести поведение SMC, разделив фиктивные атрибуты на два бинарных атрибута (в данном случае мужской и женский), тем самым преобразовав их в асимметричные атрибуты, что позволяет использовать индекс Жаккара без внесение предвзятости. Однако SMC остается более эффективным с точки зрения вычислений в случае симметричных фиктивных переменных, поскольку не требует добавления дополнительных измерений.
Если и - два вектора со всеми действительными , то их коэффициент подобия Жаккара (также известный как подобие Ружички) определяется как
и расстояние Жаккара (также известное как расстояние Зёргеля)
Если говорить еще шире, если и - две неотрицательные измеримые функции на измеримом пространстве с мерой , тогда мы можем определить
где и - точечные операторы. Тогда расстояние Жаккара
Тогда, например, для двух измеримых множеств , мы имеем где и - характеристические функции соответствующего набора.
Описанное выше взвешенное подобие Жаккара обобщает индекс Жаккара на положительные векторы, где набор соответствует двоичному вектору, заданному функцией индикатора , т. е. . Однако он не обобщает индекс Жаккара на распределения вероятностей, где набор соответствует равномерному распределению вероятностей, то есть
Всегда меньше, если наборы различаются по размеру. Если и , затем
Вместо этого, обобщение, которое является непрерывным между распределениями вероятностей и их соответствующими опорами наборы есть
, который называется «вероятностью» Жаккара. Он имеет следующие границы относительно взвешенного Жаккара на векторах вероятности.
Здесь верхняя граница - (взвешенный) коэффициент Соренсена – Дайса. Соответствующее расстояние, , является показателем распределений вероятностей, а псевдометрика по неотрицательным векторам.
Индекс вероятности Жаккара имеет геометрическую интерпретацию как площадь пересечения симплексов. Каждая точка в модуле -simplex соответствует распределению вероятностей для элементов , потому что единица -simplex - это набор точек в измерениях , сумма которых равна 1. Чтобы получить индекс Жаккара вероятности геометрически, представьте распределение вероятностей в виде единичного симплекса, разделенного на субсимплексы в соответствии с массой каждого элемента. Если вы наложите два распределения, представленных таким образом, друг на друга и пересечете симплексы, соответствующие каждому элементу, оставшаяся площадь будет равна индексу вероятности Жаккара распределений.
Рассмотрим проблему построения случайных величин, которые бы конфликтовали друг с другом. насколько возможно. То есть, если и , мы хотели бы построить и , чтобы максимизировать . Если мы посмотрим только на два распределения по отдельности, самое высокое , которого мы можем достичь, определяется как где - это расстояние полного изменения. Однако предположим, что мы не были заинтересованы только в максимизации этой конкретной пары, предположим, что мы хотели бы максимизировать вероятность столкновения любой произвольной пары. Можно построить бесконечное число случайных величин по одной для каждого распределения и стремиться максимизировать для всех пар . В довольно строгом смысле, описанном ниже, индекс Жаккара вероятности является оптимальным способом согласования этих случайных величин.
Для любого метода выборки и дискретных распределений , если затем для некоторого где и , либо
То есть, нет метод выборки может достичь большего количества коллизий, чем
Эта теорема имеет наглядное доказательство для трехэлементных распределений с использованием симплексного представления.
В литературе и в Интернете встречаются различные формы функций, описываемые как сходство Танимото и расстояние Танимото. Большинство из них являются синонимами сходства Жаккара и расстояния Жаккара, но некоторые математически отличаются. Многие источники ссылаются на технический отчет IBM как на основную справочную информацию. Отчет доступен в нескольких библиотеках..
В «Компьютерной программе для классификации растений», опубликованной в октябре 1960 г., дается метод классификации, основанный на коэффициенте сходства и производной функции расстояния. Похоже, что это наиболее авторитетный источник значений терминов «Сходство Танимото» и «Расстояние Танимото». Коэффициент подобия эквивалентен подобию Жаккара, но функция расстояния не совпадает с расстоянием Жаккара.
В этой статье «коэффициент сходства» дается для растровых изображений, где каждый бит массива фиксированного размера представляет присутствие или отсутствие характеристики у моделируемого объекта. Определение отношения - это количество общих битов, деленное на количество установленных битов (т.е. ненулевых) в любой выборке.
Представлено в математических терминах, если образцы X и Y являются растровыми изображениями,
Если вместо этого каждый образец моделируется как набор атрибутов, это значение равно коэффициенту Жаккара двух наборов. Жаккар не цитируется в статье, и кажется вероятным, что авторы не знали об этом.
Танимото продолжает определять «коэффициент расстояния» на основе этого отношения, определенного для растровых изображений с ненулевым сходством:
Этот коэффициент намеренно не является метрикой расстояния. Он выбран, чтобы позволить двум образцам, которые сильно отличаются друг от друга, быть похожими на третий. Легко построить пример, который опровергает свойство неравенства треугольника.
расстояние Танимото часто ошибочно называют синонимом расстояния Жаккара
Если подобие Жаккара или Танимото выражается над битовым вектором, то его можно записать как
где то же вычисление выражается в терминах скалярного векторного произведения и величины. Это представление основано на том факте, что для битового вектора (где значение каждого измерения равно 0 или 1) тогда
и
Это потенциально запутанное представление, потому что функция, выраженная над векторами, является более общей, если ее область определения явно не ограничена. Свойства
Существует реальная опасность того, что комбинация «Расстояние Танимото», определяемая с помощью этой формулы, вместе с утверждением «Расстояние Танимото является правильной метрикой расстояния» приведет к ложному заключению, что функция
Липкус использует определение сходства Танимото, которое эквивалентно