تاب‌دادن زمان هوشمند

در سری‌های زمانی تاب دادن زمان هوشمند یا کش و قوس زمانی پویا (به انگلیسی: (Dynamic time warping(DTW) الگوریتمی برای اندازه‌گیری شباهت بین دو دنباله زمانیست که ممکن است در سرعت یا زمان متفاوت باشند. برای نمونه، DTW می‌تواند شباهت بین دو الگوی راه رفتن را بیابد حتی اگر سرعت یا شتاب راه رفتنشان در بازه‌های زمانی یکسان نباشد.
DTW دنباله‌های زمانی داده‌های صوتی، ویدئویی و تصویری را تحلیل کرده‌است. در واقع هر داده‌ای که بتواند به صورت دنبالهٔ پشت سر هم اطلاعات به دست بیاید، DTW می‌تواند آن را تحلیل کند. یک کاربرد مهم این الگوریتم بازشناسی گفتار یکسان افراد مختلف با سرعت گفتار مختلف است. و از کاربردهای دیگر DTW می‌توان به تشخیص صدا، تشخیص دستخط و امضا اشاره کرد. همچنین استفاده‌های از آن در تشخیص تطبیق اشکال هندسی جزئی دیده شده‌است.
در مجموع، DTW روشی است که بهینه‌ترین تطبیق بین دو دنباله زمانی با محدودیت‌های معین را پیدا می‌کند (برای مثال:سری زمانی).
دنباله‌ها به صورت غیر خطی در محور زمان «کش و قوس پیدا می‌کنند» تا معیاری برای شباهت آن‌ها مستقل از برخی تغییرات غیر خطی در محور زمان به دست‌آورد. این روش تنظیم دنباله بسیاری از اوقات در دسته‌بندی سری زمانی مورد استفاده قرار می‌گیرد. اگرچه DTW معیاری همانند 	فاصله بین دو دنباله داده شده می‌یابد، تضمین نمی‌کند که نامساوی مثلث در مورد آن برقرار باشد.

 پیاده‌سازی 
این مثال پیاده‌سازی الگوریتم DTW را برای دو دنباله رشته‌ای s و t  از نشانه‌های مجزا ترسیم می‌کند. برای نشانه‌های 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] := ۰

    for i := 1 to n
        for j := 1 to m
            cost:= d(s[i], t[j<nowiki>])</nowiki>
            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 نباشد، که w یک پارامتر پنجره‌ای است.
ما می‌توانیم به سادگی الگوریتم بالا را برای اعمال محدودیت‌های خاص تغییر دهیم. با این حال، ویرایش داده شده در بالا تنها هنگامی کار می‌کند که |n-m| برگتر از w نباشد. یعنی نقطه انتهایی داخل طول قطری پنجره جای بگیرد. برای این که الگوریتم کار کند، بایستی پارامتر پنجره‌ای w طوری انتخاب شود که n - m| ≤ w|(خط علامتگذاری شده با (*) در کد را ببنید)

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

     w := max(w, abs(n-m))// adapt window size (*)

     for i := 0 to n
         for j:= 0 to m
             DTW[i, j] := infinity
     DTW[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]

 محاسبه سریع 
محاسبه الگوریتم DTW در حالت کلی از مرتبه زمانی (O(N^2 است. از جمله تکنیک‌های سریع تر برای محاسبه DTW می‌توان به SparseDTW	
Al-Naymat, G. , Chawla, S. , & Taheri, J. (2012). SparseDTW: A Novel Approach to Speed up Dynamic Time Warping وFastDTWStan 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  اشاره نمود. یکی از کارهای معمول در این زمینه، به دست آوردن سری‌های زمانی مشابه است که می‌تواند با استفاده از کران پایین‌هایی چون LB_KeoghE. Keogh, C. A. Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems 7 (3) (2005) 358–386. و LB_ImprovedD. Lemire, Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound, Pattern Recognition 42 (9), pages 2169-2180, 2009. تسریع گردد. در یک بررسی، Wang et al. گزارش نموده است که به کمک کران پایین‌های LB_Improved نتایج بهتری از کران پایین LB_Keoghبه دست آورده و نشان داده است که تکنیک‌های دیگر بهینه نیستند.Wang, Xiaoyue, et al. "Experimental comparison of representation methods and distance measures for time series data." Data Mining and Knowledge Discovery (2010): 1-35.

 دنباله متوسط 
میانگین‌گیری از الگوریتم کش و قوس زمانی پویا هم ارز مسئله دنباله میانگین مجموعه‌ای از دنباله هاست. دنباله میانگین، دنباله‌ای است که مجموع مربع‌های فواصل آن از دنباله‌های مجموعه داده شده کمینه باشد. NLAAF روش دقیق حل این مسئله است. برای بیش از دو دنباله، مسئله مربوط به یکی از تنظیم‌های چندگانه است و به روشی هیوریستیک نیاز دارد. در حال حاضر روش مورد استفاده برای به دست آوردن میانگین مجموعه‌ای از دنباله‌ها به صورت پایدار به وسیله DTW،DBA نام دارد. COMASA با استفاده از DBA به عنوان یک پردازش بهینه‌سازی محلی، جستجو برای دنباله بهینه را به‌طور بهینه اتفاقی می‌کند.

 جستارهای وابسته 
 فاصله لون‌اشتاین

 منابع 



رده:الگوریتم‌های یادگیری ماشین
رده:برنامه‌نویسی پویا
رده:تحلیل سری زمانی
رده:مقاله‌های ایجادشده توسط ایجادگر