Методы оценки близости строк Татьяна Кривошеева. Строковые метрики Расстояние Хэмминга Расстояние Левенштейна Расстояние Дамерай-Левенштейна, Метрика. - презентация

1 Методы оценки близости строк Татьяна Кривошеева

2 Строковые метрики Расстояние Хэмминга Расстояние Левенштейна Расстояние Дамерай-Левенштейна, Метрика Нидлмана-Вунша, Метрика Смита-Вотермана Bag distance Метрики Jaro, Jaro-Winkler q-grams, skip-grams Общий префикс Наибольшая общая подстрока Метрика Monge-Elkan

3 Операции преобразования строк Подстановка kill bill Вставка kill skill Удаление fear ear

4 1. Расстояние Хэмминга (подстановка) d H (GCAT,CGAT) = 2 2. Расстояние Левенштейна (удаление, вставка, подстановка) d E (CGACG, GTCGA) = 3

5 Подсчет расстояния Левенштейна TEST S E T i j

6 TEST 0 S E T Подсчет расстояния Левенштейна 0 0

7 TEST 0 S1 E T Подсчет расстояния Левенштейна

8 TEST 0 S1 E2 T

9 Подсчет расстояния Левенштейна TEST 0 S1 E2 T3

10 Подсчет расстояния Левенштейна TEST S1 E2 T3

11 Подсчет расстояния Левенштейна TEST S11 E2 T3

12 Подсчет расстояния Левенштейна TEST S11223 E22123 T32222

13 Расстояние Дамерау-Левенштейна (перестановка соседних символов) d DL (GCAT,CGAT) = 1 Метрика Нидлмана-Вунша (за операции вставки, удаления, подстановки можно получить разный штраф) delete (c) = 1 insert (c) = 2 substitute (c) = 3 Метрика Смита-Вотермана (штраф за операцию зависит от символа) delete (A) = 2 delete (B) = 0.1

14 Штраф за пропуски Константный штраф d C (gov, government) = 3 Линейный штраф d L (gov, government) = 3 * 7 = 21 Афинный штраф d A (gov, government) = * 2 = 15

15 bag dist (s,t) = max( IM(s) \ M(t)|, |M(t) \ M(s)|) М(Х) – мультимножество символов строки Х Bag distance (Bartolini, 2002)

16 Bag distance metric s = bread t = beer M(s) = {b,r,e,a,d} M(t) = {b,e,e,r} M(s) \ M(t) = { a, d } M(t) \ M(s) = { e } bag dist (s,t) = max (I{ a, d }I, I{ e }I) = 2

17 Jaro metric (Winkler, 1999) J(s,t) = *(IsI/IsI + ItI/ItI + (IsI – [T s,t /2])/IsI) s = a 1 a 2...a k t = b 1...b L s и t строки общих символов s и t T s,t количество транспозиций

18 Jaro metric (Winkler, 1999) Общие символы a i = b j R = [max(IsI,ItI)/2] - 1 a i b i-R b i b i+R s t

19 Jaro metric 1. s = CRETA t = TRACES 2. R = [max(|s|, |t|)/2] – 1 = [max(5, 6)/ 2] -1 =2 3. s = REA t = RAE 4. T st = 2 J(s,t) = *(IsI/IsI + ItI/ItI + (IsI – [T s,t /2])/IsI) = *(3/5 + 3/6 + (3 – [2/2])/3) = 0.59

20 Jaro-Winkler metric JW(s,t) = J(s,t) + α* boost(s,t)*(1-J(s,t)) boost(s,t) = min( ILcp(s,t)I, p) s = DIXON t = DICKSONX J(s,t) = α = 0.1 p = 2 Lcp(s,t) = DI boost(s,t) = min (2, 2) = 2 JW(s,t) = *2 *(1 – 0.767) = 0.813

21 q-grams metric (Gravano, 2001) q-gram – подстрока заданной строки длины q s = MARTHA q = 2 G 2 (s) = { #M,MA, AR, RT, TH, HA, A#} q = 3 G 3 (s) = { ##M,#MA,MAR, ART, RTH, THA,HA#,A##}

22 q-grams metric s = MARTHA t = MARCH G 2 (s) = { #M,MA, AR, RT, TH, HA, А#} G 2 (t) = { #M,MA, AR, RC, CH, H#} q-gram(s,t) = 3 / max(7, 6) = 0.43

23 Skip-gram metric (Keskustalo, 2003) Skip-gram – q-грамма, которая может состоять из несоседних символов s = MARTHA q = 2 skip{0,1} G skip{0,1} (s)={#M,#A,MA,MR,AR,AT, RH,TA,RT,TH, HA,A#, H#}

24 Общий префикс(Common Prefix) 2 CP α (s,t) = (|Lcp(s,t)| + α) / (|s| * |t|) s = MARTHA t = MARCH Lcp(s,t) = 3 α = 1 2 CP 1 (s,t) = (3 + 1) / (6 * 5) = 0.53

25 Наибольшая общая подстрока 0, |Lcs(s,t)| < k |Lcs(s,t)| + LCS(s -Lcs(s,t), t -Lcs(s,t) ) s = abcdeftg t = bcdaefg k = 2 s = abcdeftg t = bcdaefg LCS(s,t) = 3 + LCS(aeftg, aefg) s -Lcs(s,t) = aeftg t -Lcs(s,t) = aefg LCS(s,t)= LCS(tg, g) = 6 { LCS(s,t) =

26 Weighted LCS |Lcs(s,t)| + α – max( α,p) |Lcs(s,t)| + α w Lcs(s,t) =

27 Monge-Elkan (Monge and Elkan, 1996) s = {s 1 s 2..s K } t = {t 1 t 2..t L } Monge-Elkan(s,t) = 1/K * Ʃ max sim(s i,t j ) sim(s i,t j ) – любая метрика для сравнения двух строк K i=1j=1..L

28 Наборы тестирующих данных 1.Польские имена (1457) 2.Полные польские имена (1219)

29 Результаты исследования Польские имена WLCS CP α Полные польские имена WLCS Smith-Waterman metric JWM 0.976

30 Конец доклада Вопросы?