Динамичко временско савијање — разлика између измена

С Википедије, слободне енциклопедије
Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 57: Ред 57:




Израчунавање ДВС захтева '''''O(N^2)''''' у целини. Брзе технике за рачунање ДВС укључују ОскудноДВС 1 и БрзоДВС 2. Заједнички задатак, проналажење сличне временске серије, може се убрзати коришћењем ниже границе као што су LB_Keogh [3] или LB_Improved [4] У анкети, дају боље резултате са LB_Improved доње границе од LB_Keogh, и утврдио да su друге технике неефикасне [5]
Израчунавање ДВС захтева <math>O(N^2)</math> у целини. Брзе технике за рачунање ДВС укључују ОскудноДВС<ref>
Al-Naymat, G., Chawla, S., & Taheri, J. (2012). [http://arxiv.org/abs/1201.2969 SparseDTW: A Novel Approach to Speed up Dynamic Time Warping]</ref> и БрзоДВС.<ref>Stan Salvador & Philip Chan, FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space. KDD Workshop on Mining Temporal and Sequential Data, pp. 70-80, 2004</ref>
Заједнички задатак, проналажење сличне временске серије, може се убрзати коришћењем ниже границе као што су LB_Keogh<ref>{{cite journal | last1 = Keogh | first1 = E. | last2 = Ratanamahatana | first2 = C. A. | year = 2005 | title = Exact indexing of dynamic time warping | url = | journal = Knowledge and Information Systems | volume = 7 | issue = 3| pages = 358–386 | doi=10.1007/s10115-004-0154-9}}</ref> или LB_Improved.<ref>{{cite journal | last1 = Lemire | first1 = D. | year = 2009 | title = Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound | url = http://arxiv.org/abs/0811.3301 | journal = Pattern Recognition | volume = 42 | issue = 9| pages = 2169–2180 | doi=10.1016/j.patcog.2008.11.030}}</ref> У анкети, дају боље резултате са LB_Improved доње границе од LB_Keogh, и утврдио да su друге технике неефикасне.<ref>{{cite journal | last1 = Wang | first1 = Xiaoyue | display-authors = 1 | last2 = et al | year = | title = Experimental comparison of representation methods and distance measures for time series data | url = | journal = Data Mining and Knowledge Discovery | volume = 2010 | issue = | pages = 1–35 }}</ref>


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

Верзија на датум 30. јануар 2016. у 00:27

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

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

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

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

Овај пример илуструје примену динамичке време савијање алгоритам када су две секвенце s и t су низови дискретних симбола. За два симбола x и y, d(x, y) x и y, d(x, y) је растојање између симбола, нпр. d(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], а затим није већи од w прозора параметра.

Можемо лако изменити алгоритам за додавање локалитета ограничења (разлике означене у bold italic). Међутим, дата горе модификација ради само ако није већа од w , тј. крајња тачка је у дужини прозора дијагонале. Да би алгоритам радио, прозор параметра 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]

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

Израчунавање ДВС захтева у целини. Брзе технике за рачунање ДВС укључују ОскудноДВС[1] и БрзоДВС.[2] Заједнички задатак, проналажење сличне временске серије, може се убрзати коришћењем ниже границе као што су LB_Keogh[3] или LB_Improved.[4] У анкети, дају боље резултате са LB_Improved доње границе од LB_Keogh, и утврдио да su друге технике неефикасне.[5]

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

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

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

A Nearest Neighbour Classifier can achieve state-of-the-art performance when using Dynamic Time Warping as a distance measure.[9] Најближи Комшија Класификатор може остварити најмодерније-савремене перформансе када се користи Динамичко Време Савијања као мера на даљину.

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

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

  1. ^ Al-Naymat, G., Chawla, S., & Taheri, J. (2012). SparseDTW: A Novel Approach to Speed up Dynamic Time Warping
  2. ^ Stan Salvador & Philip Chan, FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space. KDD Workshop on Mining Temporal and Sequential Data, pp. 70-80, 2004
  3. ^ Keogh, E.; Ratanamahatana, C. A. (2005). „Exact indexing of dynamic time warping”. Knowledge and Information Systems. 7 (3): 358—386. doi:10.1007/s10115-004-0154-9. 
  4. ^ Lemire, D. (2009). „Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound”. Pattern Recognition. 42 (9): 2169—2180. doi:10.1016/j.patcog.2008.11.030. 
  5. ^ Wang, Xiaoyue; et al. „Experimental comparison of representation methods and distance measures for time series data”. Data Mining and Knowledge Discovery. 2010: 1—35. 
Преузето из „https://sr.wikipedia.org/w/index.php?title=Динамичко_временско_савијање&oldid=11597863”