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

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

. индекс Жаккарда, также известный как пересечение по объединению и Коэффициент сходства Жаккара (первоначально присвоенный французскому названию «коэффициент коммунауте» от Пола Жаккара ) - это статистика, используемая для оценки сходства и разнообразие из выборок наборов. Коэффициент Жаккара измеряет сходство между конечными выборочными наборами и определяется как размер пересечения, деленный на размер union наборов выборок:

J (A, Б) = | A ∩ B | | A ∪ B | = | A ∩ B | | А | + | B | - | A ∩ B |. {\ Displaystyle J (A, B) = {{| A \ cap B |} \ над {| A \ cup B |}} = {{| A \ cap B |} \ над {| A | + | B | - | A \ cap B |}}.}J (A, B) = {{| A \ cap B |} \ over {| A \ cup B |}} = {{| A \ cap B |} \ over {| А | + | B | - | A \ cap B |}}.

(Если A и B оба пусты, определите J (A, B) = 1.)

0 ≤ J (A, B) ≤ 1. {\ displaystyle 0 \ leq J (A, B) \ leq 1.}0 \ le J (A, B) \ le 1.

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

d J (A, B) = 1 - J (A, B) = | A ∪ B | - | A ∩ B | | A ∪ B |. {\ displaystyle d_ {J} (A, B) = 1-J (A, B) = {{| A \ cup B | - | A \ cap B |} \ over | A \ cup B |}.}d_J (A, B) = 1 - J (A, B) = {{| A \ cup B | - | A \ cap B | } \ over | A \ cup B | }.

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

Это расстояние является метрикой на совокупности всех конечных множеств.

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

J μ (A, B) = μ (A ∩ B) μ (A ∪ B), {\ displaystyle J _ {\ mu} (A, B) = {{\ mu (A \ cap B)} \ over {\ mu (A \ cup B)}},}{\ displaystyle J _ {\ mu} (A, B) = {{\ mu (A \ cap B)} \ over {\ mu (A \ cup B)}},}

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

d μ (A, B) = 1 - J μ (A, B) = μ (A △ Б) μ (A ∪ B). {\ Displaystyle d _ {\ mu} (A, B) = 1-J _ {\ mu} (A, B) = {{\ mu (A \ треугольник B)} \ над {\ mu (A \ чашка B)} }.}{\ displaystyle d _ {\ mu} (A, B) = 1-J _ {\ mu} (A, B) = {{\ mu (A \ треугольник B)} \ over {\ mu (A \ cup B)}}.}

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

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

Содержание

  • 1 Сходство асимметричных двоичных атрибутов
    • 1.1 Различие с коэффициентом простого соответствия (SMC)
  • 2 Взвешенное сходство Жаккара и расстояние
  • 3 Вероятность сходства Жаккара и расстояние
    • 3.1 Оптимальность вероятностного индекса Жаккара
  • 4 Сходство Танимото и расстояние
    • 4.1 Определения сходства и расстояния Танимото
    • 4.2 Другие определения Расстояние Танимото
  • 5 См. Также
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки

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

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

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

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

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

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

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

Расстояние Жаккара, d J, задается как

d J = M 01 + M 10 M 01 + M 10 + M 11 = 1 - Дж. {\ displaystyle d_ {J} = {M_ {01} + M_ {10} \ over M_ {01} + M_ {10} + M_ {11}} = 1-J.}d_J = {M_ { 01} + M_ {10} \ over M_ {01} + M_ {10} + M_ {11}} = 1 - J.

Разница с коэффициентом простого соответствия (SMC)

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

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

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

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

Если x = (x 1, x 2,…, xn) {\ displaystyle \ mathbf {x} = (x_ {1}, x_ {2}, \ ldots, x_ {n})}\ mathbf {x} = (x_1, x_2, \ ldots, x_n) и y = (y 1, y 2,…, yn) {\ displaystyle \ mathbf {y} = (y_ {1}, y_ {2}, \ ldots, y_ {n})}\ mathbf {y} = (y_1, y_2, \ ldots, y_n) - два вектора со всеми действительными xi, yi ≥ 0 {\ displaystyle x_ {i}, y_ {i} \ geq 0 }x_i, y_i \ geq 0 , то их коэффициент подобия Жаккара (также известный как подобие Ружички) определяется как

JW (x, y) = ∑ i min (xi, yi) ∑ i max (xi, yi), {\ displaystyle J _ {\ mathcal {W}} (\ mathbf {x}, \ mathbf {y}) = {\ frac {\ sum _ {i} \ min (x_ {i}, y_ {i})} {\ sum _ {i} \ max (x_ {i}, y_ {i})}},}{\ displaystyle J _ {\ mathcal {W}} (\ mathbf {x}, \ mathbf {y}) = {\ frac {\ sum _ {i} \ min (x_ {i}, y_ {i})} {\ sum _ {i} \ max (x_ {i}, y_ {i})}},}

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

d JW (x, y) = 1 - JW (х, у). {\ Displaystyle d_ {J {\ mathcal {W}}} (\ mathbf {x}, \ mathbf {y}) = 1-J _ {\ mathcal {W}} (\ mathbf {x}, \ mathbf {y}).}{\ displaystyle d_ {J {\ mathcal {W }}} (\ mathbf {x}, \ mathbf {y}) = 1-J _ {\ mathcal {W}} (\ mathbf {x}, \ mathbf {y}).}

Если говорить еще шире, если f {\ displaystyle f}f и g {\ displaystyle g}g - две неотрицательные измеримые функции на измеримом пространстве X {\ displaystyle X}X с мерой μ {\ displaystyle \ mu}\ mu , тогда мы можем определить

JW (f, g) Знак равно ∫ мин (е, g) d μ ∫ макс (f, g) d μ, {\ displaystyle J _ {\ mathcal {W}} (f, g) = {\ frac {\ int \ min (f, g) d \ mu} {\ int \ max (f, g) d \ mu}},}{\ displaystyle J _ {\ mathcal {W}} (f, g) = {\ frac {\ int \ min (f, g) d \ mu} {\ int \ max (f, g) d \ mu}},}

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

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

Тогда, например, для двух измеримых множеств A, В ⊆ Икс {\ displaystyle A, B \ substeq X}A, B \ substeq X , мы имеем J μ (A, B) = J (χ A, χ B), {\ displaystyle J_ {\ mu} (A, B) = J (\ chi _ {A}, \ chi _ {B}),}J_ \ mu (A, B) = J (\ chi_A, \ chi_B), где χ A {\ displaystyle \ chi _ {A}}\ chi _ {A} и χ B {\ displaystyle \ chi _ {B}}\ chi_B - характеристические функции соответствующего набора.

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

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

x i = {1 | X | i ∈ X 0 в противном случае {\ displaystyle x_ {i} = {\ begin {cases} {\ frac {1} {| X |}} i \ in X \\ 0 {\ text {else}} \ end {cases} }}{\ displaystyle x_ {i} = {\ begin {cases} {\ frac {1} {| X |}} i \ in X \\ 0 {\ текст {иначе}} \ end {case}}}

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

JW (x, y) = | X ∩ Y | | X ∖ Y | + | X | < J ( X, Y). {\displaystyle J_{\mathcal {W}}(x,y)={\frac {|X\cap Y|}{|X\setminus Y|+|X|}}{\ displaystyle J _ {\ mathcal {W}} (x, y) = {\ frac {| X \ cap Y |} {| X \ setminus Y | + | X |}} <J (X, Y).}
Вероятностный индекс Жаккара можно интерпретировать как пересечения симплексов.

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

JP (x, y) = ∑ xi ≠ 0, yi ≠ 0 1 ∑ j max (xjxi, yjyi) {\ 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)}}}{\ 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)} }}

, который называется «вероятностью» Жаккара. Он имеет следующие границы относительно взвешенного Жаккара на векторах вероятности.

JW (x, y) ≤ JP (x, y) ≤ 2 JW (x, y) 1 + JW (x, y) {\ 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 J _ {\ mathcal {W}} (x, y) \ leq J _ {\ mathcal {P}} (x, y) \ leq {\ frac {2J _ {\ mathcal {W}} (x, y)} {1 + J _ {\ mathcal {W}} (x, y)}}}

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

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

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

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

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

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

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

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

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

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

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

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

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

Представлено в математических терминах, если образцы X и Y являются растровыми изображениями, X i {\ displaystyle X_ {i}}X_ {i} - это i-й бит X, а ∧, ∨ {\ displaystyle \ land, \ lor}\ land, \ lor - это побитовые и, or операторы соответственно, тогда коэффициент сходства T s {\ displaystyle T_ {s }}T_ {s} равно

T s (X, Y) = ∑ i (X i ∧ Y i) ∑ i (X i ∨ Y i) {\ displaystyle T_ {s} (X, Y) = {\ frac {\ sum _ {i} (X_ {i} \ land Y_ {i})} {\ sum _ {i} (X_ {i} \ lor Y_ {i})}}}T_s (X, Y) = \ frac {\ sum_i (X_i \ land Y_i)} {\ sum_i (X_i \ lor Y_i)}

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

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

T d (X, Y) = - log 2 ⁡ (T s (X, Y)) {\ displaystyle T_ {d} (X, Y) = - \ log _ {2} (T_ {s} (X, Y))}T_d (X, Y) = - \ log_2 (T_s (X, Y))

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

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

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

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

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

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

A ⋅ B = ∑ i A i B i = ∑ i (A i ∧ B i) { \ displaystyle A \ cdot B = \ sum _ {i} A_ {i} B_ {i} = \ sum _ {i} (A_ {i} \ land B_ {i})}A \ cdot B = \ sum_i A_iB_i = \ sum_i (A_i \ land B_i)

и

‖ A ‖ 2 знак равно ∑ я А я 2 знак равно ∑ я А я. {\ displaystyle \ | A \ | ^ {2} = \ sum _ {i} A_ {i} ^ {2} = \ sum _ {i} A_ {i}.}{\ displaystyle \ | A \ | ^ {2} = \ sum _ {i} A_ {i} ^ {2} = \ sum _ {i} A_ { i}.}

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

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

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

См. Также

Примечания

Ссылки

  • Тан, Панг-Нин; Штейнбах, Михаэль; Кумар, Випин (2005), Введение в интеллектуальный анализ данных, ISBN 0-321-32136-7
  • Жаккар, Пол (1901), «Этюд сравнительного анализа флорального распределения в une part des Alpes et des Jura ", Bulletin de la Société vaudoise des Sciences naturelles, 37 : 547–579
  • Jaccard, Paul (1912)," Распространение флоры в альпийская зона », New Phytologist, 11 (2): 37–50, doi : 10.1111 / j.1469-8137.1912.tb05611.x

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

Последняя правка сделана 2021-05-24 10:54:20
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте