Dinamičko vremensko savijanje
U analizi vremenskih serija, dinamičko vremensko savijanje (DVS) je algoritam za merenje sličnosti između dve vremenske sekvence koje mogu da variraju u vremenu i brzini. Na primer, sličnost obrazaca može da se detektuje korišćenjem DVS, čak i ako je jedna osoba išla brže od ostalih, ili ako je bilo ubrzanja i usporavanja tokom jednog posmatranja. DVS je primenjen na vremenske sekvence video, audio i grafičke podatke - zaista, bilo kakvi podaci koji mogu biti pretvoreni u linearnom nizu mogu biti analizirani sa DVS. Dobro poznata aplikacija je automatsko prepoznavanje govora, da se izbori sa različitim brzinama govora. Ostale aplikacije uključuju priznavanje zvučnika i internet priznanje potpisa. Takođe se vidi da može da se koristi u parcijalnom poređenju u aplikaciji.
U principu, DVS je metod koji izračunava optimalno podudaranje između dve date sekvence (npr. vremenske serije) sa određenim ograničenjima. Sekvence su "izvijene" ne-linearno na vremensku dimenziju da odredi meru njihove sličnosti nezavisno od nekih nelinearnih varijacija u vremensku dimenziju. Ovaj metod sekvenci se često koristi u klasifikaciji vremenskih serija. Iako DVS meri daljinu kao količinu između dve date sekvence, to ne garantuje trougao nejednakosti za održavanje.
Implementacija
urediOvaj primer ilustruje primenu dinamičkog vremenskog savijanja algoritama kada su dve sekvence s i t nizovi diskretnih simbola. Za dva simbola x i y, d(x, y) x i y, d(x, y) je rastojanje između simbola, npr. 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]
}
Ponekad želite da dodate lokalitet ograničenja. To je, ako zahtevvamo da je s[i] uparen sa t[j], a zatim nije veći od w prozora parametra.
Možemo lako izmeniti algoritam za dodavanje lokaliteta ograničenja (razlike označene u bold italic).
Međutim, data gore modifikacija radi samo ako nije veća od w , tj. krajnja tačka je u dužini prozora dijagonale. Da bi algoritam radio, prozor parametra w mora biti prilagođen tako da je (pogledajte liniju označenu sa (*) u kodu).
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]
Brzo računanje
urediIzračunavanje DVS zahteva u celini. Brze tehnike za računanje DVS uključuju OskudnoDVS[1] i BrzoDVS.[2] Zajednički zadatak, pronalaženje slične vremenske serije, može se ubrzati korišćenjem niže granice kao što su LB_Keogh[3] ili LB_Improved.[4] U anketi, daju bolje rezultate sa LB_Improved donjom granicom od LB_Keogh, i može se utvrditi da cu druge tehnike nefikasne.[5]
Prosečna sekvenca
urediProsečno dinamičko remensko savijanje je problem pronalaženja prosečne sekvence za skup sekvenci. Prosečna sekvenca je sekvenca koja minimizira zbir kvadrata na skupu objekata.NLAAF[6] je tačna metoda za dve sekvence. Za više od dve sekvence, problem se odnosi na jednu od višestrukih sekvenci i zahteva heuristiku. DBA[7] je referentna metoda za niz sekvenci dosledno sa DTW. COMASA[8] je efikasna random potraga za prosečan niz, koristeći DBA kao lokalni proces optimizacije.
Učenje pod nadzorom
urediNajbliži susedni klasifikator može ostvariti najmodernije-savremene performanse kada se koristi Dinamičko vreme savijanja kao mera na daljinu.[9]
Alternativni pristup
urediAlternativa tehnika za DVS je zasnovana na funkcionalnoj analizi podataka, u kojoj se vremenska serija smatra funkcijom vremena i stoga se stalno primenjuje u matematici.[10] Optimalno nelinearno vreme savijanja funkcije izračunava minimalnu meru udaljenosti od niza funkcija u odnosu na njihov prosek. Uslov za funkcije savijanja može biti dodat, npr. ograničenja veličine njihovog zakrivljenja. Nastale funkcije savijanja su glatke, što olakšava dalju obradu. Ovaj pristup je uspešno primenjen za analizu uzorka i varijabilnost pokreta govora.[11][12]
Aplikacije
urediPrepoznavanje reči
urediZbog različitih stopa, nelinearna fluktuacija javlja se u govoru u odnosu na vremensku osu koju treba eliminisati[13] DP-odgovarajući, što je obrazac podudaranja algoritma koji se na papiru mogu zvati "Dinamičko programiranje algoritma za optimizaciju priznavanja izgovorene reči" od Hiroaki Sakoe i Sibi Chiba, i koji koristi efekat vremena normalizacije, gde su fluktuacije u vremenskoj osi uzor koristeći nelinearnu vremensku funkciju savijanja. S obzirom na bilo koja dva šablona govora, možemo se rešiti svoje vremenske razlike od savijanja vremenske ose jednog tako da postignemo maksimalnu slučajnost u drugom. Štaviše, ako je savijanje funkcija dozvoljeno da preuzme bilo kakvu moguću vrednost, veoma manje razlika se može napraviti između reči koje pripadaju različitim kategorijama. Dakle, da bi se poboljšala razlika između reči koje pripadaju različitim kategorijama, nametnuta su ograničenja na funkcije savijanja.
Analiza korelacija energije
urediNestabilni satovi se koriste da se pobedi analiza korelacija energije. Nekoliko tehnika se koristi da se suprotstave ovoj odbrani, od kojih je jedna dinamičko vremensko savijanje.
Vidi još
urediReference
uredi- ^
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. str. 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”. Ur.: Maassen, B.; van Lieshout, P. Speech Motor Control: New Developments in Basic and Applied Research. Oxford University Press. str. 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.
Literatura
uredi- Howell, P.; Anderson, A.; Lucero, J. C. (2010). „Speech motor timing and fluency”. Ur.: Maassen, B.; van Lieshout, P. Speech Motor Control: New Developments in Basic and Applied Research. Oxford University Press. str. 215—225. ISBN 978-0199235797.