'

Методы оценки близости строк

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

Подсчет расстояния Левенштейна i j


Слайд 5

Подсчет расстояния Левенштейна 0 0


Слайд 6

Подсчет расстояния Левенштейна


Слайд 7

Подсчет расстояния Левенштейна


Слайд 8

Подсчет расстояния Левенштейна


Слайд 9

Подсчет расстояния Левенштейна


Слайд 10

Подсчет расстояния Левенштейна


Слайд 11

Подсчет расстояния Левенштейна


Слайд 12

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


Слайд 13

Штраф за пропуски Константный штраф dC(“gov”, “government”) = 3 Линейный штраф dL(“gov”, “government”) = 3 * 7 = 21 Афинный штраф dA(“gov”, “government”) = 3 + 6 * 2 = 15


Слайд 14

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


Слайд 15

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’ } bagdist(s,t) = max (I{ ‘a’, ‘d’ }I, I{ ‘e’ }I) = 2


Слайд 16

Jaro metric (Winkler, 1999) J(s,t) = ?*(Is’I/IsI + It’I/ItI + (Is’I – [Ts’,t’ /2])/Is’I) s = a1a2. . .ak t = b1. . .bL s’ и t’ строки общих символов s и t Ts’,t’ количество транспозиций


Слайд 17

Jaro metric (Winkler, 1999) Общие символы ai = bj R = [max(IsI,ItI)/2] - 1 s t


Слайд 18

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. Ts’t’ = 2 J(s,t) = ?*(Is’I/IsI + It’I/ItI + (Is’I – [Ts’,t’ /2])/Is’I) = ?*(3/5 + 3/6 + (3 – [2/2])/3) = 0.59


Слайд 19

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.767 ? = 0.1 p = 2 Lcp(s,t) = “DI” boost(s,t) = min (2, 2) = 2 JW(s,t) = 0.767 + 0.1*2 *(1 – 0.767) = 0.813


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

Наибольшая общая подстрока 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)= 3 + 3 + LCS(“tg”, “g”) = 6 { LCS(s,t) =


Слайд 25

Weighted LCS |Lcs(s,t)| + ? – max(?,p) |Lcs(s,t)| + ? wLcs(s,t) =


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


×

HTML:





Ссылка: