Введение в сходство джаро – винклера (определение и пример)
В статистике сходство Джаро-Винклера — это способ измерения сходства между двумя строками.
Сходство Джаро (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
Это соответствует значению, которое мы рассчитали вручную.
Дополнительные ресурсы
В следующих руководствах объясняется, как рассчитать другие показатели сходства:
Введение в несходство Брея-Кёртиса
Введение в индекс сходства Жаккара