Динамичко временско савијање

Динамичко временско савијање

У анализи временских серија, динамичко временско савијање (ДВС) је алгоритам за мерење сличности између две временске секвенце које могу да варирају у времену и брзини. На пример, сличност образаца може да се детектује коришћењем ДВС, чак и ако је једна особа ишла брже од осталих, или ако је било убрзања и успоравања током једног посматрања. ДВС је примењен на временске секвенце видео, аудио и графичке податке - заиста, било какви подаци који могу бити претворени у линеарном низу могу бити анализирани са ДВС. Добро позната апликација је аутоматско препознавање говора, да се избори са различитим брзинама говора. Остале апликације укључују признавање звучника и интернет признање потписа. Такође се види да може да се користи у парцијалном поређењу у апликацији.

У принципу, ДВС је метод који израчунава оптимално подударање између две дате секвенце (нпр. временске серије) са одређеним ограничењима. Секвенце су "извијене" не-линеарно на временску димензију да одреди меру њихове сличности независно од неких нелинеарних варијација у временску димензију. Овај метод секвенци се често користи у класификацији временских серија. Иако ДВС мери даљину као количину између две дате секвенце, то не гарантује троугао неједнакости за одржавање.

Имплементација

Овај пример илуструје примену динамичког временског савијања алгоритама када су две секвенце s и t низови дискретних симбола. За два симбола x и y, d(x, y) x и y, d(x, y) је растојање између симбола, нпр. d(x, y) = $|x-y|$

int DTWDistance(s: array [1..n], t: array [1..m]) {
    DTW := array [0..n, 0..m]

    for i := 1 to n
        DTW[i, 0] := infinity
    for i := 1 to m
        DTW[0, i] := infinity
    DTW[0, 0] := 0

    for i := 1 to n
        for j := 1 to m
            cost:= d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // уметање
                                        DTW[i  , j-1],    // брисање
                                        DTW[i-1, j-1])    // подударање

    return DTW[n, m]
}

Понекад желите да додате локалитет ограничења. То је, ако захтеввамо да је s[i] упарен са t[j], а затим $|i-j|$ није већи од w прозора параметра.

Можемо лако изменити алгоритам за додавање локалитета ограничења (разлике означене у bold italic). Међутим, дата горе модификација ради само ако $|n-m|$ није већа од w , тј. крајња тачка је у дужини прозора дијагонале. Да би алгоритам радио, прозор параметра w мора бити прилагођен тако да је $|n-m|\le w$ (погледајте линију означенu са (*) у коду).

int DTWDistance(s: array [1..n], t: array [1..m], w: int) {
    DTW := array [0..n, 0..m]
 
    w := max(w, abs(n-m)) // прилагоди величину прозора (*)
 
    for i := 0 to n
        for j:= 0 to m
            DTW[i, j] := infinity
    DTW[0, 0] := 0

    for i := 1 to n
        for j := max(1, i-w) to min(m, i+w)
            cost := d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // уметање
                                        DTW[i, j-1],    // брисање
                                        DTW[i-1, j-1])    // подударање
 
    return DTW[n, m]

Брзо рачунање

Израчунавање ДВС захтева $O(N^2)$ у целини. Брзе технике за рачунање ДВС укључују ОскудноДВС и БрзоДВС. Заједнички задатак, проналажење сличне временске серије, може се убрзати коришћењем ниже границе као што су LB_Keogh или LB_Improved. У анкети, дају боље резултате са LB_Improved доњом границом од LB_Keogh, и може се утврдити да cу друге технике нефикасне.

Просечна секвенца

Просечно динамичко ременско савијање је проблем проналажења просечне секвенце за скуп секвенци. Просечна секвенца је секвенца која минимизира збир квадрата на скупу објеката.NLAAF је тачна метода за две секвенце. За више од две секвенце, проблем се односи на једну од вишеструких секвенци и захтева хеуристику. DBA је референтна метода за низ секвенци доследно са DTW. COMASA је ефикасна рандом потрага за просечан низ, користећи DBA као локални процес оптимизације.

Учење под надзором

Најближи суседни класификатор може остварити најмодерније-савремене перформансе када се користи Динамичко време савијања као мера на даљину.

Алтернативни приступ

Алтернатива техника за ДВС је заснована на функционалној анализи података, у којој се временска серија сматра функцијом времена и стога се стално примењује у математици. Оптимално нелинеарно време савијања функције израчунава минималну меру удаљености од низа функција у односу на њихов просек. Услов за функције савијања може бити додат, нпр. ограничења величине њиховог закривљења. Настале функције савијања су глатке, што олакшава даљу обраду. Овај приступ је успешно примењен за анализу узорка и варијабилност покрета говора.

Апликације

Препознавање речи

Због различитих стопа, нелинеарна флуктуација јавља се у говору у односу на временску осу коју треба елиминисати DP-одговарајући, што је образац подударања алгоритма који се на папиру могу звати "Динамичко програмирање алгоритма за оптимизацију признавања изговорене речи" од Hiroaki Sakoe и Sibi Chiba, и који користи ефекат времена нормализације, где су флуктуације у временској оси узор користећи нелинеарну временску функцију савијања. С обзиром на било која два шаблона говора, можемо се решити своје временске разлике од савијања временске осе једног тако да постигнемо максималну случајност у другом. Штавише, ако је савијање функција дозвољено да преузме било какву могућу вредност, веома мање разлика се може направити између речи које припадају различитим категоријама. Дакле, да би се побољшала разлика између речи које припадају различитим категоријама, наметнута су ограничења на функције савијања.

Анализа корелација енергије

Нестабилни сатови се користе да се победи анализа корелација енергије. Неколико техника се користи да се супротставе овој одбрани, од којих је једна динамичко временско савијање.

Види још

• Левенштајново растојање

Литература

• Шаблон:Cite book