Meranie podobnosti časovo sekvenovaných údajov s rôznou dĺžkou - algoritmus, dynamické programovanie

Zvážte nasledujúce údaje.

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    |

Vizualizované takto (ako v počte - medzi každým identifikátorom):

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

Mojím cieľom je porovnať súbory údajov s databázamikrutá pravda. Chcem vytvoriť funkciu, ktorá generuje meranie podobnosti medzi jedným zo súborov údajov a základnou zemou s cieľom vyhodnotiť, aký dobrý je môj algoritmus segmentácie. Je zrejmé, že by som chcel, aby segmentačný algoritmus pozostával z rovnakého počtu dátových bodov (segmentov) ako pozemnej pravdy, ale ako je znázornené na údajových súboroch, nejde o záruku, ani o počet údajových bodov známych vopred.

Ja už som vytvoril Jacard Index na generovanie azákladné hodnotenie. Teraz sa však zameriavam na metódu hodnotenia, ktorá trestá množstvo / neprítomnosť údajových bodov a obmedzuje vzdialenosť na správny údajový bod. To znamená, že b sa nemusí zhodovať s B, musí byť len v blízkosti správneho údajového bodu.

Pokúsil som sa nahliadnuť do dynamického programovaniametóda, kde som zaviedla pokutu za odstránenie alebo pridanie údajového bodu, ako aj pokutu za prejdenie na najbližší dátový bod. Bojujem však kvôli: 1. Musím obmedziť každý dátový bod na jeden správny dátový bod 2. Zistite, ktoré dátové body sa v prípade potreby majú odstrániť 3. Všeobecný nedostatok porozumenia pri implementácii algoritmov DP

Každý, kto má nápady, ako to urobiť? Ak je dynamické programovanie spôsob, akým by som mal postupovať, rád by som odporučil niekoľko odkazov, ako aj niekoľko tipov, ako to dosiahnuť.

odpovede:

V zásade môžete modifikovať DP pre Levenshteinupravte vzdialenosť, aby ste vypočítali vzdialenosti pre váš problém. Levenshtein DP predstavuje nájdenie najkratších ciest v acyklickom riadenom grafe, ktorý vyzerá takto

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

kde sú oblúky orientované zľava doprava atop-k-dolná časť. DAG má riadky číslované 0 až ma stĺpce číslované 0 až n, kde m je dĺžka prvej sekvencie a n je dĺžka druhej sekvencie. Zoznamy pokynov na zmenu prvej postupnosti na druhú zodpovedajú individuálnym (nákladom a všetkým) cestám z ľavého horného rohu na pravý dolný. Oblúk od (i, j) do (i + 1, j) zodpovedá inštrukcii na vymazanie i^th element z prvej sekvencie. Oblúk od (i, j) do (i, j + 1) zodpovedá inštrukcii na pridanie j^th prvok z druhej sekvencie. Oblúk z (i, j) zodpovedá modifikácii i^th prvkom prvej sekvencie, ktorá sa stane j^th prvok druhej sekvencie.

Všetko, čo musíte urobiť, aby ste dosiahli kvadratický časAlgoritmom pre váš problém je definovanie nákladov na (i) pridanie údajového bodu (ii) vymazanie údajového bodu (iii) úpravu dátového bodu tak, aby sa stal ďalším údajovým bodom, a potom vypočítajte najkratšie cesty na DAG v jednom z spôsoby opísané na Wikipédii.

(Okrem toho tento algoritmus predpokladá, že jenikdy nie je výhodné vykonávať úpravy, ktoré sa „krížia“ navzájom. Za pomerne mierneho predpokladu nákladov na modifikáciu je tento predpoklad zbytočný. Ak vás zaujímajú ďalšie podrobnosti, prečítajte si moju odpoveď: Približné porovnanie dvoch zoznamov udalostí (s trvaním) .)