Коефіцієнт Жаккара

Мі́ра Жакка́ра (коефіціє́нт флористи́чної спі́льності, фр. coefficient de communaute, нім. Gemlinschaftskoefficient) — міра подібності, запропонована Полем Жаккаром в 1901 році.[1] Запропонований метод здобув поширення і нині використовується для оцінки подібності скінченних множин, в інформатиці, для пошуку подібних документів, плагіату тощо.

Перетин та об'єднання двох множин A та B

Відношення перетину до об'єднання є мірою подібності при виявленні об'єктів на зображеннях — важливій задачі комп'ютерного зору.

Коефіцієнт Jaccard вимірює подібність між множинами і визначається як міра спільної частини, поділена на міру об'єднання множин:

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

(Коли A та B обидві порожні, тоді J(A,B) = 1.)

0\leqslant J(A,B)\leqslant 1.

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

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

Інакше можна пояснити відстань Жаккара, як відношення міри симетричної різниці $A\triangle B=(A\cup B)-(A\cap B)$ до об'єднання.

Відстань Жаккара є метрикою на множині всіх скінченних множин[2][3][4].

В ботаніці

Коефіцієнт подібності Жаккара обчислюють за формулою:

K_{J}={\frac {c}{a+b-c}}

,

де

а — кількість видів на першому пробному майданчику,
b — кількість видів на другому пробному майданчику,
с — кількість видів, спільних для 1-ого та 2-ого майданчиків.

Це перший відомий коефіцієнт подібності. Прізвище автора коефіцієнта в літературі перекладалася як: Жаккард, Джаккард. Коефіцієнт Жаккара в різних модифікаціях і записах активно використовується в екології, геоботаніці, молекулярній біології, біоінформатиці, геноміці, протеїноміці, інформатиці та інших галузях. Міра Жаккара еквівалентна (пов'язані однією монотонно зростаючою залежністю) мірі Серенсена і міру Сокала-Сніта для скінченних множин (множинна інтерпретація):

K_{1,-1}={\frac {n(A\cap B)}{n(A)+n(B)-n(A\cap B)}}={\frac {n(A\cap B)}{n(A\cup B)}}

Міру різниці, яка є доповненням до 1 коефіцієнта подібності Жаккара, називають мірою флористичного контрасту[5][6].

Для випадку дескриптивних множин (дескриптивна інтерпретація) в екології - це вибірки за рясністю, аналогом вказаної міри є міра Ружички[7]:

K_{1,-1}={\sum _{i=1}^{r}min(A_{i},B_{i}) \over (\sum _{i=1}^{r}(A_{i})+\sum _{i=1}^{r}(B_{i})-\sum _{i=1}^{r}min(A_{i},B_{i}))}={\sum _{i=1}^{r}min(A_{i},B_{i}) \over \sum _{i=1}^{r}max(A_{i},B_{i}))}

В конкретних випадках, коли використовуються компоненти булевих векторів, тобто компоненти, які набувають тільки два значення 0 та 1, міра відома під назвою коефіцієнта Танімото або розширеного коефіцієнта Жаккара[8].

Якщо порівнюються об'єкти за зустрічальністю видів (ймовірнісна інтерпретація), тобто враховуються ймовірності зустрічей, то аналогом міри Жаккара буде ймовірнісна міра Іверсена[9]:

K_{1,-1}={\frac {P(A\cap B)}{P(A\cup B)}}

.

Для інформаційної аналітичної інтерпретації використовується міра взаємозалежності Райського[10][11][12]:

K_{1,-1}={\frac {I(A,B)}{H(A,B)}}

Мірою різниці, коеквівалентною мірі подібності Жаккара, є відстань:

F_{1,-1}=1-{\frac {n(A\cap B)}{n(A)+n(B)-n(A\cap B)}}={\frac {n(A\cup B)-n(A\cap B)}{n(A\cup B)}}

В інформатиці

В інформатиці коефіцієнт Жаккара двох множин A та В дорівнює відношенню кількості елементів перетину множин до кількості елементів їхнього об'єднання:[13]

J(A,B)={\frac {|A\cap B|}{|A\cup B|}}

Коефіцієнт Жаккара та алгоритм шинглів використовують для пошуку схожих текстів у великому корпусі документів, а також для виявлення плагіату. Для ефективного обчислення оцінки значення коефіцієнта Жаккара використовують алгоритм MinHash.

Примітки

Jaccard P. Distribution de la flore alpine dans le Bassin des Dranses et dans quelques regions voisines // Bull. Soc. Vaudoise sci. Natur. — 1901. — V. 37, Bd. 140. — S. 241—272.
Kosub, Sven; «A note on the triangle inequality for the Jaccard distance» arXiv:1612.02696
Lipkus, Alan H. (1999). A proof of the triangle inequality for the Tanimoto distance. Journal of Mathematical Chemistry 26 (1-3): 263–265.
Levandowsky, Michael; Winter, David (1971). Distance between sets. Nature 234 (5): 34–35. doi:10.1038/234034a0.
Миркин Б. М., Розенберг Г. С. Толковый словарь современной фитоценологии. — М.: Наука, 1983. — 134 с.
Миркин Б. М., Розенберг Г. С., Наумова Л. Г. Словарь понятий и терминов современной фитоценологии. — М.: Наука, 1989. — 223 с.
Ružička M.K. Anwendung mathematiseh-statistiseher Methoden in der Geobotanik (sintetischa Bearbeitung von Aufnahmen) // Biologia. — 1958. — Roč. 13, č. 9. — S. 647—661.
Tanimoto T.T. IBM Internal Report — 17th Nov. — 1957.
Iversen J. Über die Korrelationen zwischen den Pflanzenarten in einem grönlandischen Talgebiet // Vegetation. — 1954. — V. 5-6. — P. 238—246.
Rajski C. (1961). A metric space of discrete probability distributions. Information and Control 4 (№ 4): 371–377. doi:10.1016/S0019-9958(61)80055-7.
Rajski C. Entropy and metric spaces // C. Cherry (ed.). Information Theory. — London: Butterworths, 1961. — P. 41-45.
Елисеева И. И., Рукавишников В. О. Группировка, корреляция, распознавание образов: (статистические методы классификации и измерения связей). — М.: Статистика, 1977. — 143 с.
Jure Leskovec, Anand Rajaraman, Jeffrey D. Ullman (2014). 3.1.1 Jaccard Similarity of Sets. Mining of Massive Datasets.

Див. також

Коефіцієнт подібності
Коефіцієнт Танімото
В ботаніці:
- Індекс Соренсена
- Коефіцієнт Кульчинського (пол. Kulczyński)
- Коефіцієнт Сімпсона
- Коефіцієнт Браун-Бланке (розроблений Жозіас Браун-Бланке)
- Коефіцієнт Охаї
В ботаніці та кібернетиці:
- Відстань Геммінга
- Коефіцієнт Тверського

Посилання

Індекс Жаккара // Словник-довідник з екології : навч.-метод. посіб. / уклад. О. Г. Лановенко, О. О. Остапішина. — Херсон : ПП Вишемирський В. С., 2013. — С. 101.
Jaccard's index and species diversity
Introduction to Data Mining lecture notes from Tan, Steinbach, Kumar
http://sourceforge.net/projects/simmetrics/ SimMetrics a sourceforge implementation of Jaccard index and many other similarity metrics
Web based tool for comparing texts using Jaccard coefficient

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Jaccard P. Distribution de la flore alpine dans le Bassin des Dranses et dans quelques regions voisines // Bull. Soc. Vaudoise sci. Natur. — 1901. — V. 37, Bd. 140. — S. 241—272.

[2] Kosub, Sven; «A note on the triangle inequality for the Jaccard distance» arXiv:1612.02696

[lipkus-3] Lipkus, Alan H. (1999). A proof of the triangle inequality for the Tanimoto distance. Journal of Mathematical Chemistry 26 (1-3): 263–265.

[4] Levandowsky, Michael; Winter, David (1971). Distance between sets. Nature 234 (5): 34–35. doi:10.1038/234034a0.

[5] Миркин Б. М., Розенберг Г. С. Толковый словарь современной фитоценологии. — М.: Наука, 1983. — 134 с.

[6] Миркин Б. М., Розенберг Г. С., Наумова Л. Г. Словарь понятий и терминов современной фитоценологии. — М.: Наука, 1989. — 223 с.

[7] Ružička M.K. Anwendung mathematiseh-statistiseher Methoden in der Geobotanik (sintetischa Bearbeitung von Aufnahmen) // Biologia. — 1958. — Roč. 13, č. 9. — S. 647—661.

[8] Tanimoto T.T. IBM Internal Report — 17th Nov. — 1957.

[9] Iversen J. Über die Korrelationen zwischen den Pflanzenarten in einem grönlandischen Talgebiet // Vegetation. — 1954. — V. 5-6. — P. 238—246.

[10] Rajski C. (1961). A metric space of discrete probability distributions. Information and Control 4 (№ 4): 371–377. doi:10.1016/S0019-9958(61)80055-7.

[11] Rajski C. Entropy and metric spaces // C. Cherry (ed.). Information Theory. — London: Butterworths, 1961. — P. 41-45.

[12] Елисеева И. И., Рукавишников В. О. Группировка, корреляция, распознавание образов: (статистические методы классификации и измерения связей). — М.: Статистика, 1977. — 143 с.

[mmds-13] Jure Leskovec, Anand Rajaraman, Jeffrey D. Ullman (2014). 3.1.1 Jaccard Similarity of Sets. Mining of Massive Datasets.