Вступ до подібності яро–вінклера (визначення та приклад)

У статистиці подібність Яро-Вінклера — це спосіб вимірювання подібності між двома рядками.

Подібність Jaro (sim _j ) між двома рядками визначається як:

sim _j = 1/3 * ( м/|с ₁ | + м/|с ₂ | + (мт)/м )

золото:

• m : кількість відповідних символів
  • Два символи s ₁ і s ₂ вважаються такими, що збігаються, якщо вони однакові і не далі ніж [max(|s ₁ |, |s ₂ |) / 2] – 1 символ один від одного.
• |s ₁ | , |s ₂ | : довжина першої та другої струн відповідно
• t : кількість транспозицій
  • Обчислюється як кількість відповідних символів (але в іншому порядку послідовності), поділена на 2.

Подібність Джаро-Вінклера (sim _w ) визначається як:

sim _w = sim _j + lp(1 – sim _j )

золото:

• sim _j : Подібність Jaro між двома рядками, s ₁ і s ₂
• l : довжина загального префікса на початку рядка (макс. 4 символи)
• p : Коефіцієнт масштабування, що вказує, наскільки оцінка скоригована вгору, щоб мати спільні префікси. Зазвичай це визначається як p = 0,1 і не повинно перевищувати p = 0,25.

Подібність Джаро-Вінклера між двома рядками завжди між 0 і 1, де:

• 0 означає відсутність подібності між рядками
• 1 означає, що рядки точно збігаються

Примітка : відстань Джаро-Вінклера буде визначена як 1 – sim _w .

У наступному прикладі показано, як на практиці обчислити подібність Джаро-Вінклера між двома рядками.

Приклад: обчислення подібності Яро-Вінклера між двома рядками

Припустимо, що ми маємо такі два рядки:

• Канал 1 (s ₁ ): миша
• Канал 2 (s ₂ ): вимкнення звуку

Спочатку давайте обчислимо подібність Jaro між цими двома рядками:

sim _j = 1/3 * ( м/|с ₁ | + м/|с ₂ | + (мт)/м )

золото:

• m : кількість відповідних символів
  • Два символи s ₁ і s ₂ вважаються такими, що збігаються, якщо вони однакові і не далі ніж [max(|s ₁ |, |s ₂ |) / 2] – 1 символ один від одного.

У цьому випадку [max(|s ₁ |, |s ₂ |) / 2] – 1 обчислюється як 5/2 – 1 = 1,5. Ми б визначили три літери як відповідні: m, u, e. Отже, m = 3 .

• |s ₁ | , |s ₂ | : довжина першої та другої струн відповідно

У цьому випадку |s ₁ | = 5 і |s ₁ | = 4 .

• t : кількість транспозицій
  • Обчислюється як кількість відповідних символів (але в іншому порядку послідовності), поділена на 2.

У цьому випадку є три збігаються символи, але вони вже знаходяться в тому самому послідовному порядку, тому t = 0 .

Отже, ми б обчислили подібність Джаро наступним чином:

sim _j = 1/3 * (3/5 + 3/4 + (3-0)/3) = 0,78333.

Далі обчислимо подібність Яро-Вінклера (sim _w ) наступним чином:

sim _w = sim _j + lp(1 – sim _j )

У цьому випадку ми розрахуємо:

sim _w = 0,78333 + (1)*(0,1)(1 – 0,78333) = 0,805.

Подібність Яро-Вінклера між двома ланцюгами становить 0,805 .

Оскільки це значення наближається до 1, це означає, що два рядки дуже схожі.

Ми можемо підтвердити, що це правильно, обчисливши подібність Джаро-Вінклера між двома рядками в R:

 library (stringdist)

#calculate Jaro-Winkler similarity between 'mouse' and 'mute'
1 - stringdist("mouse", "mute", method = "jw", p= 0.1 )

[1] 0.805

Це відповідає значенню, яке ми розрахували вручну.

Додаткові ресурси

У наступних посібниках пояснюється, як обчислити інші показники подібності:

Вступ до несхожості Брей-Кертіс
Знайомство з індексом подібності Жаккара