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

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

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

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

Овај пример илуструје примену динамичког временског савијања алгоритама када су две секвенце 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|\leq 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})$ у целини. Брзе технике за рачунање ДВС укључују ОскудноДВС^[1] и БрзоДВС.^[2] Заједнички задатак, проналажење сличне временске серије, може се убрзати коришћењем ниже границе као што су LB_Keogh^[3] или LB_Improved.^[4] У анкети, дају боље резултате са LB_Improved доњом границом од LB_Keogh, и може се утврдити да cу друге технике нефикасне.^[5]

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

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

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

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

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

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

Апликације

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

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

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

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

Види још

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

Референце

^ Al-Naymat, G., Chawla, S., & Taheri, J. (2012). Al-Naymat, Ghazi; Chawla, Sanjay; Taheri, Javid (2012). „SparseDTW: A Novel Approach to Speed up Dynamic Time Warping”. arXiv:1201.2969 .
^ Stan Salvador & Philip Chan, FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space. KDD Workshop on Mining Temporal and Sequential Data. стр. 70-80, 2004
^ Keogh, E.; Ratanamahatana, C. A. (2005). „Exact indexing of dynamic time warping”. Knowledge and Information Systems. 7 (3): 358—386. S2CID 59899155. doi:10.1007/s10115-004-0154-9.
^ Lemire, D. (2009). „Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound”. Pattern Recognition. 42 (9): 2169—2180. Bibcode:2009PatRe..42.2169L. S2CID 8658213. arXiv:0811.3301 . doi:10.1016/j.patcog.2008.11.030.
^ Wang, Xiaoyue (2010). „Experimental comparison of representation methods and distance measures for time series data”. Data Mining and Knowledge Discovery. 2010: 1—35. arXiv:1012.2789 .
^ Gupta, L.; Molfese, D. L.; Tammana, R.; Simos, P. G. (1996). „Nonlinear alignment and averaging for estimating the evoked potential”. IEEE Transactions on Biomedical Engineering. 43 (4): 348—356. PMID 8626184. S2CID 28688330. doi:10.1109/10.486255.
^ Petitjean, F. O.; Ketterlin, A.; Gançarski, P. (2011). „A global averaging method for dynamic time warping, with applications to clustering”. Pattern Recognition. 44 (3): 678. Bibcode:2011PatRe..44..678P. S2CID 14850691. doi:10.1016/j.patcog.2010.09.013.
^ Petitjean, F. O.; Gançarski, P. (2012). „Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment”. Theoretical Computer Science. 414: 76—91. doi:10.1016/j.tcs.2011.09.029.
^ Ding, Hui; Trajcevski, Goce; Scheuermann, Peter; Wang, Xiaoyue; Keogh, Eamonn (2008). „Querying and mining of time series data: experimental comparison of representations and distance measures”. Proc. VLDB Endow. 1 (2): 1542—1552. S2CID 2615628. doi:10.14778/1454159.1454226.
^ Lucero, J. C.; Munhall, K. G.; Gracco, V. G.; Ramsay, J. O. (1997). „On the Registration of Time and the Patterning of Speech Movements”. Journal of Speech, Language, and Hearing Research. 40 (5): 1111—1117. PMID 9328881. doi:10.1044/jslhr.4005.1111.
^ Howell, P.; Anderson, A.; Lucero, J. C. (2010). „Speech motor timing and fluency”. Ур.: Maassen, B.; van Lieshout, P. Speech Motor Control: New Developments in Basic and Applied Research. Oxford University Press. стр. 215—225. ISBN 978-0199235797.
^ Koenig, Laura L.; Lucero, Jorge C.; Perlman, Elizabeth (2008). „Speech production variability in fricatives of children and adults: Results of functional data analysis”. The Journal of the Acoustical Society of America. 124 (5): 3158—3170. Bibcode:2008ASAJ..124.3158K. ISSN 0001-4966. PMC 2677351 . PMID 19045800. doi:10.1121/1.2981639.
^ Sakoe, Hiroaki; Chiba, Seibi (1978). „Dynamic programming algorithm optimization for spoken word recognition”. IEEE Transactions on Acoustics, Speech and Signal Processing. 26 (1): 43—49. S2CID 17900407. doi:10.1109/tassp.1978.1163055.

Литература

Howell, P.; Anderson, A.; Lucero, J. C. (2010). „Speech motor timing and fluency”. Ур.: Maassen, B.; van Lieshout, P. Speech Motor Control: New Developments in Basic and Applied Research. Oxford University Press. стр. 215—225. ISBN 978-0199235797.

[1] Al-Naymat, G., Chawla, S., & Taheri, J. (2012). Al-Naymat, Ghazi; Chawla, Sanjay; Taheri, Javid (2012). „SparseDTW: A Novel Approach to Speed up Dynamic Time Warping”. arXiv:1201.2969 .

[2] Stan Salvador & Philip Chan, FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space. KDD Workshop on Mining Temporal and Sequential Data. стр. 70-80, 2004

[3] Keogh, E.; Ratanamahatana, C. A. (2005). „Exact indexing of dynamic time warping”. Knowledge and Information Systems. 7 (3): 358—386. S2CID 59899155. 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. Bibcode:2009PatRe..42.2169L. S2CID 8658213. arXiv:0811.3301 . doi:10.1016/j.patcog.2008.11.030.

[5] Wang, Xiaoyue (2010). „Experimental comparison of representation methods and distance measures for time series data”. Data Mining and Knowledge Discovery. 2010: 1—35. arXiv:1012.2789 .

[6] Gupta, L.; Molfese, D. L.; Tammana, R.; Simos, P. G. (1996). „Nonlinear alignment and averaging for estimating the evoked potential”. IEEE Transactions on Biomedical Engineering. 43 (4): 348—356. PMID 8626184. S2CID 28688330. doi:10.1109/10.486255.

[DBA-7] Petitjean, F. O.; Ketterlin, A.; Gançarski, P. (2011). „A global averaging method for dynamic time warping, with applications to clustering”. Pattern Recognition. 44 (3): 678. Bibcode:2011PatRe..44..678P. S2CID 14850691. doi:10.1016/j.patcog.2010.09.013.

[8] Petitjean, F. O.; Gançarski, P. (2012). „Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment”. Theoretical Computer Science. 414: 76—91. doi:10.1016/j.tcs.2011.09.029.

[9] Ding, Hui; Trajcevski, Goce; Scheuermann, Peter; Wang, Xiaoyue; Keogh, Eamonn (2008). „Querying and mining of time series data: experimental comparison of representations and distance measures”. Proc. VLDB Endow. 1 (2): 1542—1552. S2CID 2615628. doi:10.14778/1454159.1454226.

[10] Lucero, J. C.; Munhall, K. G.; Gracco, V. G.; Ramsay, J. O. (1997). „On the Registration of Time and the Patterning of Speech Movements”. Journal of Speech, Language, and Hearing Research. 40 (5): 1111—1117. PMID 9328881. doi:10.1044/jslhr.4005.1111.

[11] Howell, P.; Anderson, A.; Lucero, J. C. (2010). „Speech motor timing and fluency”. Ур.: Maassen, B.; van Lieshout, P. Speech Motor Control: New Developments in Basic and Applied Research. Oxford University Press. стр. 215—225. ISBN 978-0199235797.

[12] Koenig, Laura L.; Lucero, Jorge C.; Perlman, Elizabeth (2008). „Speech production variability in fricatives of children and adults: Results of functional data analysis”. The Journal of the Acoustical Society of America. 124 (5): 3158—3170. Bibcode:2008ASAJ..124.3158K. ISSN 0001-4966. PMC 2677351 . PMID 19045800. doi:10.1121/1.2981639.

[13] Sakoe, Hiroaki; Chiba, Seibi (1978). „Dynamic programming algorithm optimization for spoken word recognition”. IEEE Transactions on Acoustics, Speech and Signal Processing. 26 (1): 43—49. S2CID 17900407. doi:10.1109/tassp.1978.1163055.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]