Pomiar podobieństwa danych czasowych o różnej długości - algorytm, programowanie dynamiczne

Rozważ następujące dane.

Groundtruth      |  Dataset1         |  Dataset2         |  Dataset3
Datapoints|Time  |  Datapoints|Time  |  Datapoints|Time  |  Datapoints|Time
A     |0     |      a     |0     |      a     |0     |      a     |0
B     |10    |      b     |5     |      b     |5     |      b     |13
C     |15    |      c     |12    |      c     |12    |      c     |21
D     |25    |      d     |22    |      d     |14    |      d     |30
E     |30    |      e     |30    |      e     |17    |
|                   |      f     |27    |
|                   |      g     |30    |

Wizualizowane w ten sposób (jak w liczbie - między każdym identyfikatorem):

Time ->
Groundtruth: A|----------|B|-----|C|----------|D|-----|E
Dataset1:    a|-----|b|-------|c|----------|d|--------|e
Dataset2:    a|-----|b|-------|c|--|d|---|e|----------|f|---|g
Dataset3:    a|-------------|b|--------|c|---------|d

Moim celem jest porównanie zestawów danych zgruntowa prawda. Chcę utworzyć funkcję, która generuje pomiar podobieństwa między jednym ze zbiorów danych a gruntem, aby ocenić, jak dobry jest mój algorytm segmentacji. Oczywiście chciałbym, aby algorytm segmentacji składał się z równej liczby punktów danych (segmentów), co groundtruth, ale jak pokazano w zestawach danych, nie jest to gwarancją, podobnie jak liczba punktów danych znanych wcześniej.

Już stworzyłem Indeks Jacarda, aby wygenerowaćpodstawowy wynik oceny. Teraz jednak szukam metody oceny, która karze obfitość / brak punktów danych, a także ogranicza odległość do właściwego punktu danych. Oznacza to, że b nie musi pasować do B, po prostu musi znajdować się blisko poprawnego punktu danych.

Próbowałem zajrzeć do programowania dynamicznegometoda, w której wprowadziłem karę za usunięcie lub dodanie punktu danych oraz karę za odległość, aby przejść do najbliższego punktu danych. Ale walczę z powodu: 1. Muszę ograniczyć każdy punkt danych do jednego poprawnego punktu danych 2. Dowiedz się, który punkt danych usunąć, jeśli to konieczne 3. Ogólny brak zrozumienia sposobu implementacji algorytmów DP

Czy ktoś ma pomysły, jak to zrobić? Jeśli dynamiczne programowanie jest dobrym rozwiązaniem, uwielbiam rekomendację łącza, a także wskazówki, jak to zrobić.

Odpowiedzi:

Zasadniczo możesz zmodyfikować DP dla Levenshteinodległość edycji, aby obliczyć odległości dla problemu. Levenshtein DP polega na znalezieniu najkrótszych ścieżek w acyklicznym ukierunkowanym wykresie, który wygląda tak

*-*-*-*-*
|||||
*-*-*-*-*
|||||
*-*-*-*-*

gdzie łuki są zorientowane od lewej do prawej iod góry do dołu. DAG ma wiersze ponumerowane od 0 do m, a kolumny ponumerowane od 0 do n, gdzie m jest długością pierwszej sekwencji, a n jest długością drugiej. Listy instrukcji do zmiany pierwszej sekwencji na drugą odpowiadają jeden do jednego (koszt i wszystko) do ścieżek od górnego lewego do dolnego prawego. Łuk od (i, j) do (i + 1, j) odpowiada instrukcji usuwania i^th element z pierwszej sekwencji. Łuk od (i, j) do (i, j + 1) odpowiada instrukcji dodawania j^th element z drugiej sekwencji. Łuk z (i, j) odpowiada modyfikacji i^th element pierwszej sekwencji, aby stać się j^th element drugiej sekwencji.

Wszystko, co musisz zrobić, aby uzyskać czas kwadratowyAlgorytm twojego problemu polega na zdefiniowaniu kosztu (i) dodania punktu danych (ii) usunięcia punktu danych (iii) modyfikacji punktu danych, aby stał się innym punktem danych, a następnie obliczenia najkrótszych ścieżek w DAG w jednym z sposoby opisane przez Wikipedię.

(Na marginesie, ten algorytm zakłada, że ​​tak jestnigdy nie opłaca się dokonywać modyfikacji, które „krzyżują się” ze sobą. Przy dość łagodnym założeniu dotyczącym kosztów modyfikacji założenie to jest zbędne. Jeśli jesteś zainteresowany szczegółami, zobacz moją odpowiedź: Przybliżone dopasowanie dwóch list wydarzeń (z czasem trwania) .)