Введение

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

Индекс Жаккарда, также известный как коэффициент сходства Жаккарда, – это статистическая мера, используемая для оценки сходства и разнообразия выборочных множеств. Он был разработан Гроувом Карлом Гилбертом в 1884 году как его коэффициент верификации (v) и теперь часто называется индексом критического успеха в метеорологии. Позже он был разработан независимо Полом Жаккардом, который первоначально дал ему французское название coefficient de communauté, и независимо сформулирован повторно Т. Танимото. Сходство Жаккарда также применимо к мультимножествам (bags). Для них существует аналогичная формула, но используемые символы обозначают пересечение и сумму мультимножеств (а не объединение). Максимальное значение равно 1/2. Расстояние Жаккарда, которое измеряет различие между выборочными множествами, является дополнением к коэффициенту Жаккарда и получается вычитанием коэффициента Жаккарда из 1 или, что эквивалентно, делением разности размеров объединения и пересечения двух множеств на размер объединения:

Альтернативная интерпретация расстояния Жаккарда – это отношение размера симметричной разности к размеру объединения. Расстояние Жаккарда обычно используется для вычисления матрицы n × n для кластеризации и многомерного масштабирования n выборочных множеств. Это расстояние является метрикой на множестве всех конечных множеств. Существует также версия расстояния Жаккарда для мер, включая вероятностные меры. Если – это мера на измеримом пространстве , то коэффициент Жаккарда определяется как

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

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

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

Рассмотрим задачу построения случайных переменных таким образом, чтобы они как можно чаще совпадали. То есть, если и , мы хотели бы построить и максимизировать . Если рассматривать только два распределения по отдельности, то максимальное значение, которого можно достичь, равно , где – полное расстояние вариации. Однако, предположим, что нас интересует не только максимизация для конкретной пары, а максимизация вероятности совпадения для любой произвольной пары. Можно построить бесконечное количество случайных переменных, по одной для каждого распределения, и стремиться к максимизации для всех пар. В достаточно строгом смысле, описанном ниже, индекс вероятностного Жаккара является оптимальным способом сопоставления этих случайных переменных. Для любого метода выборки и дискретных распределений, если для некоторых , где и , то либо , либо следует сослаться на технический отчет IBM как на основополагающий источник. Отчет доступен в нескольких библиотеках. В "Компьютерной программе для классификации растений", опубликованной в октябре 1960 года, представлен метод классификации, основанный на коэффициенте сходства и производной функции расстояния. Похоже, что это наиболее авторитетный источник для определения значений терминов "сходство Танимото" и "расстояние Танимото". Коэффициент сходства эквивалентен сходству Жаккара, но функция расстояния не идентична расстоянию Жаккара.