پرش به محتوا

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

از ویکی‌پدیا، دانشنامهٔ آزاد
انحراف زمانی پویا بین دو تابع خطی قطعه‌ای. خط نقطه‌چین رابطه انحراف زمانی را نشان می‌دهد. ممکن است چندین نقطه در تابع پایین به یک نقطه در تابع بالا نگاشته شده‌اند و بالعکس.

در سری‌های زمانی تاب دادن زمان هوشمند یا کش و قوس زمانی پویا (به انگلیسی: (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])
            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[۱] وFastDTW[۲] اشاره نمود. یکی از کارهای معمول در این زمینه، به دست آوردن سری‌های زمانی مشابه است که می‌تواند با استفاده از کران پایین‌هایی چون LB_Keogh[۳] و LB_Improved[۴] تسریع گردد. در یک بررسی، Wang et al. گزارش نموده است که به کمک کران پایین‌های LB_Improved نتایج بهتری از کران پایین LB_Keoghبه دست آورده و نشان داده است که تکنیک‌های دیگر بهینه نیستند.[۵]

دنباله متوسط

[ویرایش]

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

جستارهای وابسته

[ویرایش]

منابع

[ویرایش]

ویکی‌پدیای انگلیسی

  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. ↑ E. Keogh, C. A. Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems 7 (3) (2005) 358–386.
  4. ↑ D. Lemire, Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound, Pattern Recognition 42 (9), pages 2169-2180, 2009.
  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.
  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. doi:10.1109/10.486255. ISSN 0018-9294.
  7. ↑ Petitjean, François; Ketterlin, Alain; Gançarski, Pierre (2011). "A global averaging method for dynamic time warping, with applications to clustering". Pattern Recognition. 44 (3): 678–693. doi:10.1016/j.patcog.2010.09.013. ISSN 0031-3203.
  8. ↑ Petitjean, François; Gançarski, Pierre (2012). "Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment". Theoretical Computer Science. 414 (1): 76–91. doi:10.1016/j.tcs.2011.09.029. ISSN 0304-3975.
برگرفته از «https://fa.wikipedia.org/w/index.php?title=تاب‌دادن_زمان_هوشمند&oldid=40419774»