ED-4.2-m10-1.0-Slajd13
Inne miary odległości (3)
Rozważmy ponownie problem grupowania sekwencji dostępów do stron WWW, o którym wspominaliśmy już wcześniej. Definicja odległości (podobieństwa) sekwencji symboli powinna uwzględniać fakt, że sekwencje mogą mieć różną długość oraz różne symbole na tych samych pozycjach, np.: sekwencja x= abcde oraz sekwencja y= bcdxye. Popularną miarą odległości stosowaną do oceny podobieństwa sekwencji symboli jest tzw. miara LCS (ang. ang. longest common subsequence) – najdłuższej wspólnej podsekwencji. Odległość pomiędzy sekwencjami x i y definiujemy następująco: D(x, y) = |x| + |y| - 2 |LCS(x, y)|. Przykładowo, odległość pomiędzy sekwencją x= abcde a sekwencją y= bcdxye wynosi:
D(x, y) = 5 + 6 – 2* 4 = 3, gdyż LCS(x, y) = bcde. Łatwo zauważyć, że przedstawiona miara spełnia wszystkie aksjomaty metryki odległości.
