Индекс Жаккара

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

Пересечение и объединение двух множеств A и B

Пересечение по объединению как мера сходства для обнаружения объектов на изображениях — важная задача компьютерного зрения .

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

Он был разработан Гроувом Карлом Гилбертом в 1884 году как коэффициент проверки (v) ^[1] и теперь часто упоминается как индекс критического успеха в метеорологии. ^[2] Позже он был независимо разработан Полем Жаккаром , первоначально дав французское название коэффициента de communauté , ^{[3] [4]} и независимо сформулирован снова Т. Танимото. ^[5] Таким образом, индекс Танимото или коэффициент Танимото также используются в некоторых областях. Однако они идентичны в общем отношении отношения Intersection к Union .

Обзор

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

${\displaystyle J(A,B)={{|A\cap B|} \over {|A\cup B|}}={{|A\cap B|} \over {|A|+|B|-|A\cap B|}}.}$

Обратите внимание, что по задумке, если пересечение A B пусто, то J ( A , B ) = 0. Коэффициент Жаккара широко используется в информатике, экологии, геномике и других науках, где используются двоичные или бинаризованные данные . Для проверки гипотез с помощью коэффициента Жаккара доступны как методы точного решения, так и методы аппроксимации. ^[6] ${\displaystyle 0\leq J(A,B)\leq 1.}$

Сходство с Жаккаром распространяется и на сумки, т. е. мультисеты . Формула аналогична ^[7] , но используемые символы обозначают пересечение мешков и сумму мешков (а не объединение). Максимальное значение — 1/2.

${\displaystyle J(A,B)={{|A\cap B|} \over {|A\uplus B|}}={{|A\cap B|} \over {|A|+|B|}}.}$

Расстояние Жаккара , которое измеряет несходство между наборами выборок, является дополнительным к коэффициенту Жаккара и получается путем вычитания коэффициента Жаккара из 1 или, что то же самое, путем деления разницы размеров объединения и пересечения двух наборов на размер союза:

${\displaystyle d_{J}(A,B)=1-J(A,B)={{|A\cup B|-|A\cap B|} \over |A\cup B|}.}$

Альтернативная интерпретация расстояния Жаккара - как отношение размера симметричной разности к объединению. Расстояние Жаккара обычно используется для расчета матрицы размера n × n для кластеризации и многомерного масштабирования n наборов выборок. ${\displaystyle A\triangle B=(A\cup B)-(A\cap B)}$

Это расстояние является метрикой совокупности всех конечных множеств. ^{[8] [9] [10]}

Существует также версия расстояния Жаккара для мер , включая вероятностные меры . Если – мера на измеримом пространстве , то мы определяем коэффициент Жаккара формулой ${\displaystyle \mu }$ ${\displaystyle X}$

${\displaystyle J_{\mu }(A,B)={{\mu (A\cap B)} \over {\mu (A\cup B)}},}$

и расстояние Жаккара на

${\displaystyle d_{\mu }(A,B)=1-J_{\mu }(A,B)={{\mu (A\triangle B)} \over {\mu (A\cup B)}}.}$

Необходимо соблюдать осторожность, если или , поскольку в этих случаях эти формулы не определены четко. ${\displaystyle \mu (A\cup B)=0}$ ${\displaystyle \infty }$

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

Сходство асимметричных двоичных атрибутов

Учитывая два объекта, A и B , каждый из которых имеет n двоичных атрибутов, коэффициент Жаккара является полезной мерой перекрытия, которое A и B разделяют со своими атрибутами. Каждый атрибут A и B может иметь значение 0 или 1. Общее количество каждой комбинации атрибутов для A и B определяется следующим образом:

${\displaystyle M_{11}}$представляет общее количество атрибутов, где A и B имеют значение 1.

${\displaystyle M_{01}}$представляет общее количество атрибутов, где атрибут A равен 0, а атрибут B равен 1.

${\displaystyle M_{10}}$представляет общее количество атрибутов, где атрибут A равен 1, а атрибут B равен 0.

${\displaystyle M_{00}}$представляет общее количество атрибутов, где A и B имеют значение 0.

Каждый атрибут должен относиться к одной из этих четырех категорий, а это означает, что

${\displaystyle M_{11}+M_{01}+M_{10}+M_{00}=n.}$

Коэффициент подобия Жаккара J определяется как

${\displaystyle J={M_{11} \over M_{01}+M_{10}+M_{11}}.}$

Расстояние Жаккара d _J определяется как

${\displaystyle d_{J}={M_{01}+M_{10} \over M_{01}+M_{10}+M_{11}}=1-J.}$

Статистические выводы можно сделать на основе коэффициентов сходства Жаккара и, следовательно, связанных с ними показателей. ^[6] Учитывая два набора выборок A и B с n атрибутами, можно провести статистический тест, чтобы увидеть, является ли перекрытие статистически значимым . Точное решение доступно, хотя вычисления могут быть дорогостоящими по мере увеличения n . ^[6] Доступны методы оценки либо путем аппроксимации полиномиального распределения , либо путем начальной загрузки. ^[6]

Отличие от простого коэффициента соответствия (SMC)

При использовании для двоичных атрибутов индекс Жаккара очень похож на простой коэффициент соответствия . Основное отличие состоит в том, что SMC имеет термин в числителе и знаменателе, а индекс Жаккара — нет. Таким образом, SMC считает как взаимное присутствие (когда атрибут присутствует в обоих наборах), так и взаимное отсутствие (когда атрибут отсутствует в обоих наборах) как совпадения и сравнивает их с общим количеством атрибутов во вселенной, тогда как индекс Жаккара только считает взаимное присутствие совпадением и сравнивает его с количеством атрибутов, выбранных хотя бы одним из двух наборов. ${\displaystyle M_{00}}$

Например, при анализе рыночной корзины корзина двух потребителей, которых мы хотим сравнить, может содержать лишь небольшую часть всех доступных продуктов в магазине, поэтому SMC обычно возвращает очень высокие значения сходства, даже если корзины очень сильно отличаются друг от друга. малое сходство, что делает индекс Жаккара более подходящим показателем сходства в этом контексте. Например, рассмотрим супермаркет с 1000 товарами и двумя покупателями. В корзине первого покупателя находятся соль и перец, а в корзине второго — соль и сахар. В этом сценарии сходство между двумя корзинами, измеренное индексом Жаккара, составит 1/3, но при использовании SMC сходство становится 0,998.

В других контекстах, где 0 и 1 несут эквивалентную информацию (симметрию), SMC является лучшей мерой сходства. Например, векторы демографических переменных, хранящихся в фиктивных переменных , таких как пол, лучше сравнивать с SMC, чем с индексом Жаккара, поскольку влияние пола на сходство должно быть одинаковым, независимо от того, определяется ли мужской пол как 0, а женский. как 1 или наоборот. Однако, когда у нас есть симметричные фиктивные переменные, можно воспроизвести поведение SMC, разделив фиктивные переменные на два двоичных атрибута (в данном случае, мужской и женский), преобразуя их таким образом в асимметричные атрибуты, позволяя использовать индекс Жаккара без внесение какой-либо предвзятости. Однако SMC остается более эффективным в вычислительном отношении в случае симметричных фиктивных переменных, поскольку не требует добавления дополнительных измерений.

Взвешенное сходство и расстояние Жаккара

Если и — два вектора со всеми действительными , то их коэффициент сходства Жаккара (также известный тогда как сходство Ружички) определяется как ${\displaystyle \mathbf {x} =(x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle \mathbf {y} =(y_{1},y_{2},\ldots ,y_{n})}$ ${\displaystyle x_{i},y_{i}\geq 0}$

${\displaystyle J_{\mathcal {W}}(\mathbf {x} ,\mathbf {y} )={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}},}$

и расстояние Жаккара (также известное тогда как расстояние Зёргеля)

${\displaystyle d_{J{\mathcal {W}}}(\mathbf {x} ,\mathbf {y} )=1-J_{\mathcal {W}}(\mathbf {x} ,\mathbf {y} ).}$

В еще большей общности, если и являются двумя неотрицательными измеримыми функциями на измеримом пространстве с мерой , то мы можем определить ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle X}$ ${\displaystyle \mu }$

${\displaystyle J_{\mathcal {W}}(f,g)={\frac {\int \min(f,g)d\mu }{\int \max(f,g)d\mu }},}$

где и – поточечные операторы. Тогда расстояние Жаккара равно ${\displaystyle \max }$ ${\displaystyle \min }$

${\displaystyle d_{J{\mathcal {W}}}(f,g)=1-J_{\mathcal {W}}(f,g).}$

Тогда, например, для двух измеримых множеств имеем где и – характеристические функции соответствующего множества. ${\displaystyle A,B\subseteq X}$ ${\displaystyle J_{\mu }(A,B)=J(\chi _{A},\chi _{B}),}$ ${\displaystyle \chi _{A}}$ ${\displaystyle \chi _{B}}$

Вероятность Жаккара сходство и расстояние

Описанное выше взвешенное подобие Жаккара обобщает индекс Жаккара на положительные векторы, где набор соответствует двоичному вектору, заданному индикаторной функцией , т.е. Однако он не обобщает индекс Жаккара на распределения вероятностей, где набор соответствует равномерному распределению вероятностей, т.е. ${\displaystyle x_{i}\in \{0,1\}}$

${\displaystyle x_{i}={\begin{cases}{\frac {1}{|X|}}&i\in X\\0&{\text{otherwise}}\end{cases}}}$

Всегда меньше, если наборы различаются по размеру. Если и тогда ${\displaystyle |X|>|Y|}$ ${\displaystyle x_{i}=\mathbf {1} _{X}(i)/|X|,y_{i}=\mathbf {1} _{Y}(i)/|Y|}$

${\displaystyle J_{\mathcal {W}}(x,y)={\frac {|X\cap Y|}{|X\setminus Y|+|X|}}<J(X,Y).}$

Вероятностный индекс Жаккара можно интерпретировать как пересечение симплексов.

Вместо этого обобщение, которое является непрерывным между распределениями вероятностей и соответствующими наборами поддержки, имеет вид

${\displaystyle J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0,y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}}$

которая называется «Вероятностью» Жаккара. ^[11] Он имеет следующие ограничения на взвешенный Жаккар на векторах вероятности.

${\displaystyle J_{\mathcal {W}}(x,y)\leq J_{\mathcal {P}}(x,y)\leq {\frac {2J_{\mathcal {W}}(x,y)}{1+J_{\mathcal {W}}(x,y)}}}$

Здесь верхней границей является (взвешенный) коэффициент Сёренсена–Дайса . Соответствующее расстояние является метрикой распределений вероятностей и псевдометрикой неотрицательных векторов. ${\displaystyle 1-J_{\mathcal {P}}(x,y)}$

Вероятностный индекс Жаккара имеет геометрическую интерпретацию как площадь пересечения симплексов . Каждая точка единичного симплекса соответствует распределению вероятностей элементов, поскольку единичный симплекс представляет собой набор точек в измерениях, сумма которых равна 1. Чтобы геометрически получить индекс Жаккара вероятности, представьте распределение вероятностей в виде единичного симплекса, разделенного на подсимплексы по массе каждого предмета. Если вы наложите два распределения, представленных таким образом, друг на друга, и пересечете симплексы, соответствующие каждому элементу, оставшаяся площадь будет равна индексу Жаккара вероятности распределений. ${\displaystyle k}$ ${\displaystyle k+1}$ ${\displaystyle k}$ ${\displaystyle k+1}$

Оптимальность вероятностного индекса Жаккара

Наглядное доказательство оптимальности индекса Жаккара вероятности для трехэлементных распределений.

Рассмотрим задачу построения случайных величин так, чтобы они как можно чаще сталкивались друг с другом. То есть, если и , мы хотели бы построить и максимизировать . Если мы посмотрим только на два распределения по отдельности, то максимум, которого мы можем достичь, будет равен где – расстояние общей вариации . Однако предположим, что нас интересует не только максимизация этой конкретной пары, предположим, что мы хотели бы максимизировать вероятность столкновения любой произвольной пары. Можно построить бесконечное число случайных величин, по одной для каждого распределения , и стремиться к максимизации для всех пар . В довольно строгом смысле, описанном ниже, индекс Жаккара вероятности является оптимальным способом выравнивания этих случайных величин. ${\displaystyle X\sim x}$ ${\displaystyle Y\sim y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \Pr[X=Y]}$ ${\displaystyle x,y}$ ${\displaystyle \Pr[X=Y]}$ ${\displaystyle 1-{\text{TV}}(x,y)}$ ${\displaystyle {\text{TV}}}$ ${\displaystyle x}$ ${\displaystyle \Pr[X=Y]}$ ${\displaystyle x,y}$

Для любого метода выборки и дискретных распределений , если то для некоторых где и , либо или . ^[11] ${\displaystyle G}$ ${\displaystyle x,y}$ ${\displaystyle \Pr[G(x)=G(y)]>J_{\mathcal {P}}(x,y)}$ ${\displaystyle z}$ ${\displaystyle J_{\mathcal {P}}(x,z)>J_{\mathcal {P}}(x,y)}$ ${\displaystyle J_{\mathcal {P}}(y,z)>J_{\mathcal {P}}(x,y)}$ ${\displaystyle \Pr[G(x)=G(z)]<J_{\mathcal {P}}(x,z)}$ ${\displaystyle \Pr[G(y)=G(z)]<J_{\mathcal {P}}(y,z)}$

То есть ни один метод выборки не может обеспечить большее количество коллизий, чем в одной паре, не достигая при этом меньшего количества коллизий, чем в другой паре, где уменьшенная пара более сходна, чем увеличенная пара. Эта теорема верна для индекса Жаккара множеств (если интерпретировать его как равномерное распределение) и вероятности Жаккара, но не для взвешенного Жаккара. (В теореме используется слово «метод выборки» для описания совместного распределения по всем распределениям в пространстве, поскольку оно основано на использовании алгоритмов взвешенного минхеширования , которые достигают этого как вероятности столкновения.) ${\displaystyle J_{\mathcal {P}}}$ ${\displaystyle J_{\mathcal {P}}}$ ${\displaystyle J_{\mathcal {P}}}$

Эта теорема имеет наглядное доказательство для трехэлементных распределений с использованием симплексного представления.

Сходство и расстояние Танимото

В литературе и Интернете встречаются различные формы функций, описываемых как сходство Танимото и расстояние Танимото. Большинство из них являются синонимами сходства Жаккара и расстояния Жаккара, но некоторые математически различны. Многие источники ^[12] ссылаются на Технический отчет IBM ^[5] как на основополагающую ссылку. Отчет доступен в нескольких библиотеках.

В «Компьютерной программе для классификации растений», опубликованной в октябре 1960 г. ^[13] дан метод классификации, основанный на коэффициенте сходства и производной функции расстояния. Кажется, это наиболее авторитетный источник по значению терминов «Сходство Танимото» и «Расстояние Танимото». Коэффициент сходства эквивалентен сходству Жаккара, но функция расстояния не совпадает с расстоянием Жаккара.

Определения сходства и расстояния Танимото

В этой статье «коэффициент сходства» дается для растровых изображений , где каждый бит массива фиксированного размера представляет наличие или отсутствие характеристики моделируемого объекта. Определение отношения – это количество общих битов, деленное на количество битов, установленных ( т.е. ненулевых) в любой выборке.

Выражаясь математическими терминами, если выборки X и Y являются растровыми изображениями, являются i- м битом X и являются побитовыми операторами и , или соответственно, то коэффициент сходства равен ${\displaystyle X_{i}}$ ${\displaystyle \land ,\lor }$ ${\displaystyle T_{s}}$

${\displaystyle T_{s}(X,Y)={\frac {\sum _{i}(X_{i}\land Y_{i})}{\sum _{i}(X_{i}\lor Y_{i})}}}$

Если вместо этого каждая выборка моделируется как набор атрибутов, это значение равно коэффициенту Жаккара двух наборов. Жаккар в статье не цитируется, и вполне вероятно, что авторы об этом не знали. ^{[ нужна цитата ]}

Танимото далее определяет «коэффициент расстояния» на основе этого соотношения, определенного для растровых изображений с ненулевым сходством:

${\displaystyle T_{d}(X,Y)=-\log _{2}(T_{s}(X,Y))}$

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

Другие определения расстояния Танимото

Расстояние Танимото часто ошибочно называют синонимом расстояния Жаккара . Эта функция является правильной метрикой расстояния. «Расстояние Танимото» часто называют подходящим показателем расстояния, вероятно, из-за его путаницы с расстоянием Жаккара. ${\displaystyle 1-T_{s}}$

Если сходство Жаккара или Танимото выражается через битовый вектор, то его можно записать как

${\displaystyle f(A,B)={\frac {A\cdot B}{\|A\|^{2}+\|B\|^{2}-A\cdot B}}}$

где тот же расчет выражается через векторное скалярное произведение и величину. Это представление основано на том факте, что для битового вектора (где значение каждого измерения равно 0 или 1) тогда

${\displaystyle A\cdot B=\sum _{i}A_{i}B_{i}=\sum _{i}(A_{i}\land B_{i})}$

и

${\displaystyle \|A\|^{2}=\sum _{i}A_{i}^{2}=\sum _{i}A_{i}.}$

Это потенциально запутанное представление, поскольку функция, выраженная над векторами, является более общей, если ее область определения явно не ограничена. Свойства не обязательно распространяются на . В частности, разностная функция не сохраняет неравенство треугольника и, следовательно, не является правильной метрикой расстояния, тогда как есть. ${\displaystyle T_{s}}$ ${\displaystyle f}$ ${\displaystyle 1-f}$ ${\displaystyle 1-T_{s}}$

Существует реальная опасность того, что сочетание «Расстояния Танимото», определенного с помощью этой формулы, с утверждением «Расстояние Танимото является правильной метрикой расстояния» приведет к ложному выводу, что функция на самом деле является метрикой расстояния над векторами или мультимножества в целом, тогда как его использование в алгоритмах поиска по сходству или кластеризации может не дать правильных результатов. ${\displaystyle 1-f}$

Липкус ^[9] использует определение сходства Танимото, которое эквивалентно , и называет расстояние Танимото функцией . Однако в статье ясно указано, что контекст ограничен использованием (положительного) весового вектора, так что для любого рассматриваемого вектора A : При этих обстоятельствах функция является надлежащей метрикой расстояния, и поэтому набор векторов, управляемых таким весовым вектором, образует метрическое пространство относительно этой функции. ${\displaystyle f}$ ${\displaystyle 1-f}$ ${\displaystyle W}$ ${\displaystyle A_{i}\in \{0,W_{i}\}.}$

Индекс Жаккара в матрицах путаницы двоичной классификации

В матрицах путаницы, используемых для бинарной классификации , индекс Жаккара можно представить в виде следующей формулы:

${\displaystyle {\text{Jaccard index}}={\frac {TP}{TP+FP+FN}}}$

где TP — истинные положительные результаты, FP — ложные положительные результаты и FN — ложные отрицательные результаты. ^[14]

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

• Коэффициент перекрытия
• Простой коэффициент соответствия
• Расстояние Хэмминга
• Коэффициент Сёренсена–Дайса , который эквивалентен: и ( : индекс Жаккара, : коэффициент Сёренсена–Дайса) ${\displaystyle J=S/(2-S)}$ ${\displaystyle S=2J/(1+J)}$ ${\displaystyle J}$ ${\displaystyle S}$
• Индекс Тверского
• Корреляция
• Взаимная информация , нормализованным метрическим вариантом которой является энтропийное расстояние Жаккара.

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

1. Мерфи, Аллан Х. (1996). «Дело Финли: знаковое событие в истории проверки прогнозов». Погода и прогнозирование . 11 (1): 3. Бибкод : 1996WtFor..11....3M. doi : 10.1175/1520-0434(1996)011<0003:TFAASE>2.0.CO;2 . ISSN  1520-0434. S2CID  54532560.
2. «Глоссарий проверки прогнозов» (PDF) . noaa.gov . Проверено 21 мая 2023 г.
3. Жаккар, Поль (1901). «Сравнительное исследование распространения цветов в Альпах и Юре». Бюллетень водного общества естественных наук . 37 : 547–579.
4. Жаккар, Поль (февраль 1912 г.). «Распространение флоры в альпийской зоне.1». Новый фитолог . 11 (2): 37–50. doi :10.1111/j.1469-8137.1912.tb05611.x. ISSN  0028-646X. S2CID  85574559.
5. Tanimoto TT (17 ноября 1958 г.). «Элементарная математическая теория классификации и прогнозирования». Внутренний технический отчет IBM . 1957 (8?).
6. Chung NC, Miasojedow B, Startek M, Gambin A (декабрь 2019 г.). «Тест на сходство Жаккара/Танимото и методы оценки данных о биологическом присутствии-отсутствии». БМК Биоинформатика . 20 (Приложение 15): 644. arXiv : 1903.11372 . дои : 10.1186/s12859-019-3118-5 . ПМК 6929325 . ПМИД  31874610. 
7. Лесковец Дж., Раджараман А., Ульман Дж. (2020). Интеллектуальный анализ массивных наборов данных . Кембридж. ISBN 9781108476348.и п. 76-77 в более ранней версии http://infolab.stanford.edu/~ullman/mmds/ch3.pdf
8. Косуб С (апрель 2019 г.). «Заметка о неравенстве треугольника для расстояния Жаккара». Буквы для распознавания образов . 120 : 36–8. arXiv : 1612.02696 . Бибкод : 2019PaReL.120...36K. doi :10.1016/j.patrec.2018.12.007. S2CID  564831.
9. Липкус А.Х. (1999). «Доказательство неравенства треугольника для расстояния Танимото». Журнал математической химии . 26 (1–3): 263–265. дои : 10.1023/А: 1019154432472. S2CID  118263043.
10. Левандовский М, Винтер Д (1971). «Расстояние между сетами». Природа . 234 (5): 34–35. Бибкод : 1971Natur.234...34L. дои : 10.1038/234034a0. S2CID  4283015.
11. Моултон Р., Цзян Ю (2018). «Максимально согласованная выборка и индекс Жаккара вероятностных распределений». Международная конференция IEEE по интеллектуальному анализу данных (ICDM) 2018 г. стр. 347–356. arXiv : 1809.04052 . дои : 10.1109/ICDM.2018.00050. ISBN 978-1-5386-9159-5. S2CID  49746072.
12. Например, Хуэйхуань Q, Синьюй W, Яншэн X (2011). Интеллектуальные системы наблюдения . Спрингер. п. 161. ИСБН 978-94-007-1137-2.
13. Роджерс DJ, Танимото TT (октябрь 1960 г.). «Компьютерная программа для классификации растений». Наука . 132 (3434): 1115–8. Бибкод : 1960Sci...132.1115R. дои : 10.1126/science.132.3434.1115. ПМИД  17790723.
14. Азиз Таха, Абдель (2015). «Метрики оценки сегментации медицинских 3D-изображений: анализ, выбор и инструмент». Медицинская визуализация BMC . 15 (29): 1–28. дои : 10.1186/s12880-015-0068-x . ПМЦ 4533825 . ПМИД  26263899. 

дальнейшее чтение

• Тан П.Н., Штайнбах М., Кумар В. (2005). Введение в интеллектуальный анализ данных . ISBN 0-321-32136-7.

Внешние ссылки

• Конспекты лекций «Введение в интеллектуальный анализ данных» от Тана, Штайнбаха, Кумара
• Обнаружение особенностей спутниковых изображений Kaggle Dstl — оценка