Введение в сходство джаро – винклера (определение и пример)


В статистике сходство Джаро-Винклера — это способ измерения сходства между двумя строками.

Сходство Джаро (sim j ) между двумя строками определяется как:

sim j = 1/3 * ( м /|с 1 | + м/|с 2 | + (мт)/м )

Золото:

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

Сходство Яро-Винклера (sim w ) определяется как:

sim w = sim j + lp(1 – sim j )

Золото:

  • sim j : сходство Джаро между двумя строками, s 1 и s 2.
  • l : Длина общего префикса в начале строки (максимум 4 символа).
  • p : Коэффициент масштабирования, указывающий, насколько увеличивается оценка, чтобы иметь общие префиксы. Обычно это определяется как p = 0,1 и не должно превышать p = 0,25.

Сходство Яро-Винклера между двумя строками всегда находится между 0 и 1, где:

  • 0 указывает на отсутствие сходства между строками.
  • 1 указывает, что строки точно совпадают

Примечание . Расстояние Яро-Винклера будет определяться как 1 – sim w .

В следующем примере показано, как на практике вычислить сходство Джаро-Винклера между двумя строками.

Пример: вычисление сходства Яро-Винклера между двумя строками

Предположим, у нас есть следующие две строки:

  • Канал 1 (s 1 ): мышь
  • Канал 2 (s 2 ): без звука

Сначала давайте посчитаем сходство Джаро между этими двумя строками:

sim j = 1/3 * ( м /|с 1 | + м/|с 2 | + (мт)/м )

Золото:

  • m : Количество совпадающих символов.
    • Два символа s 1 и s 2 считаются совпадающими, если они одинаковы и находятся на расстоянии не более [max(|s 1 |, |s 2 |) / 2] – 1 символ друг от друга.

В этом случае [max(|s 1 |, |s 2 |) / 2] – 1 рассчитывается как 5/2 – 1 = 1,5. Мы бы определили три буквы как соответствующие: m, u, e. Итак, м = 3 .

  • 1 | , 2 | : Длина первой и второй строк соответственно.

В этом случае |s 1 | = 5 и |s 1 | = 4 .

  • t : Количество транспозиций
    • Рассчитывается как количество совпадающих символов (но в другом порядке последовательности), разделенное на 2.

В этом случае есть три совпадающих символа, но они уже находятся в одном и том же последовательном порядке, поэтому t = 0 .

Итак, мы бы вычислили сходство Джаро следующим образом:

сим j = 1/3 * (3/5 + 3/4 + (3-0)/3) = 0,78333.

Далее давайте рассчитаем сходство Джаро-Винклера (sim w ) следующим образом:

sim w = sim j + lp(1 – sim j )

В этом случае мы будем рассчитывать:

сим ш = 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

Это соответствует значению, которое мы рассчитали вручную.

Дополнительные ресурсы

В следующих руководствах объясняется, как рассчитать другие показатели сходства:

Введение в несходство Брея-Кёртиса
Введение в индекс сходства Жаккара

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *