تاب‌دادن زمان هوشمند
در سری‌های زمانی تاب دادن زمان هوشمند یا کش و قوس زمانی پویا (به انگلیسی: (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 به عنوان یک پردازش بهینه‌سازی محلی، جستجو برای دنباله بهینه را به طور بهینه اتفاقی می‌کند.
جستارهای وابسته[ویرایش]
منابع[ویرایش]
- ↑ Al-Naymat, G. , Chawla, S. , & Taheri, J. (2012). SparseDTW: A Novel Approach to Speed up Dynamic Time Warping
- ↑ 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
- ↑ E. Keogh, C. A. Ratanamahatana, Exact indexing of dynamic time warping, Knowledge and Information Systems 7 (3) (2005) 358–386.
- ↑ D. Lemire, Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound, Pattern Recognition 42 (9), pages 2169-2180, 2009.
- ↑ Wang, Xiaoyue, et al. "Experimental comparison of representation methods and distance measures for time series data." Data Mining and Knowledge Discovery (2010): 1-35.
- ↑ الگو:Cite doi
- ↑ الگو:Cite doi
- ↑ الگو:Cite doi
This article "تاب‌دادن زمان هوشمند" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:تاب‌دادن زمان هوشمند. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
|
This page exists already on Wikipedia. |
