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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

В ботаніці[ред.ред. код]

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

 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 коефіцієнта подібності Жаккара називають мірою флористичного контрасту[2][3].

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

 K_{1,-1} = { \sum^{r}_{i=1} min(A_i, B_i) \over ( \sum^r_{i=1} (A_i) + \sum^r_{i=1} (B_i) - \sum^r_{i=1} min(A_i, B_i) ) } =  { \sum^r_{i=1} min(A_i, B_i) \over \sum^r_{i=1} max(A_i, B_i) ) }

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

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

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

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

 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 та В дорівнює відношенню кількості елементів перетину множин до кількості елементів їхнього об'єднання:[10]

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

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

Примітки[ред.ред. код]

  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. Миркин Б. М., Розенберг Г. С. Толковый словарь современной фитоценологии. — М.: Наука, 1983. — 134 с.
  3. Миркин Б. М., Розенберг Г. С., Наумова Л. Г. Словарь понятий и терминов современной фитоценологии. — М.: Наука, 1989. — 223 с.
  4. Ružička M.K. Anwendung mathematiseh-statistiseher Methoden in der Geobotanik (sintetischa Bearbeitung von Aufnahmen) // Biologia. — 1958. — Roč. 13, č. 9. — S. 647–661.
  5. Tanimoto T.T. IBM Internal Report — 17th Nov. — 1957.
  6. Iversen J. Über die Korrelationen zwischen den Pflanzenarten in einem grönlandischen Talgebiet // Vegetation. — 1954. — V. 5-6. — P. 238–246.
  7. 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. 
  8. Rajski C. Entropy and metric spaces // C. Cherry (ed.). Information Theory. — London: Butterworths, 1961. — P. 41-45.
  9. Елисеева И. И., Рукавишников В. О. Группировка, корреляция, распознавание образов: (статистические методы классификации и измерения связей). — М.: Статистика, 1977. — 143 с.
  10. Jure Leskovec, Anand Rajaraman, Jeffrey D. Ullman (2014). 3.1.1 Jaccard Similarity of Sets. Mining of Massive Datasets. 

Див. також[ред.ред. код]

Посилання[ред.ред. код]