دانلود ترجمه مقاله تاب خوردگی زمانی پویا عمیق کننده تکراری برای سری های زمانی (سال 2002)

تاب خوردگی زمانی پویا عمیق کننده تکراری برای سری های زمانی

Iterative Deepening Dynamic Time Warping for Time Series

1. مقدمه
2. پس‌زمینه
3. روش جدید: انحراف زمانی پویای عمیق تکراری
3-1. کاهش ابعاد
4. ارزیابی تجربی
5. کارهای مربوطه
6. نتایج و کار آتی
منابع

1. مقدمه
سری‌های زمانی، شکل فراگیری از داده‌ها هستند که تقریباً در هر رشته علمی و کاربردهای تجاری اتفاق می‌افتد. اخیراً کارهای بسیاری در زمینه سازگاری الگوریتم‌های داده‌کاوی با پایگاه داده‌های سری زمانی انجام شده است. به عنوان مثال، داس و همکاران برای نشان دادن چگونگی آموختن قوانین ترکیبی سری زمانی تلاش کردند [7]. دبرگاس و هبریل در [8]، تکنیکی برای مقیاس‌گذاری الگوریتم‌های خوشه‌بندی سری زمانی در مجموعه داده‌های گسترده ارائه کردند. کغ و پازانی الگوریتم طبقه‌بندی سری زمانی جدید مقیاس‌پذیر را معرفی کردند [16]. تقریباً همه الگوریتم‌هایی که بر روی داده‌های سری زمانی کار می‌کنند، باید شباهت بین آنها را محاسبه کنند. فاصله اقلیدسی یا برخی از پسوندها یا اصلاحات آن به طور معمول مورد استفاده قرار می‌گیرد. با این وجود، همان‌طور که در بخش 2-1 نشان خواهیم داد، فاصله اقلیدسی ممکن است در اندازه‌گیری فاصله بسیار ناپایدار باشد.

دلیل اینکه فاصله اقلیدسی ممکن است نتواند ارزیابی بصری صحیحی از شباهت بین دو بخش ایجاد کند، این است که به انحرافات کوچک در محور زمان بسیار حساس است. شکل 1-A را در نظر بگیرید، دو دنباله تقریباً شکل کلی یکسانی دارند اما اشکال در محور زمان تراز نیستند. تراز غیرخطی نشان داده شده در شکل 1-B باعث میشود که اندازه فاصله بصری بیشتری محاسبه شود.

روشی که این امکان را برای تغییر الاستیک محور X فراهم می‌کند به منظور تشخیص اشکال مشابه با فازهای مختلف می‌باشد. چنین روشی مدتهاست که در جامعه پردازش گفتار شناخته‌شده است [26 و 29]. روش انحراف زمان پویا (DTW) توسط برند و کلیفورد به جامعه داده‌کاوی معرفی شد [4]. اگرچه آنها کاربرد این روش را نشان دادند اما اذعان کردند که پیچیدگی زمانی الگوریتم یک مشکل است و «… ممکن است عملکرد آن در بانک‌های اطلاعاتی بسیار بزرگ محدودیت باشد». با وجود ایراد روش انحراف زمان پویا، هنوز هم در زمینه‌های مختلف مورد استفاده گسترده قرار می‌گیرد. در بیوانفورماتیک، آچ و چورچ با موفقیت از روش انحراف زمان پویا در بیان داده‌های RNA استفاده کردند [1]. در مهندسی شیمی از آن برای هماهنگ‌سازی و نظارت بر فرآیندهای دسته‌ای در پلیمریزاسیون استفاده شد [14]. از روش انحراف زمان پویا با موفقیت برای تراز کردن داده‌های بیومتریک، مانند راه رفتن، امضاها و حتی اثر انگشت استفاده شد [11، 14، 22، 19]. محققان متعددی از جمله وولینگز و همکاران [30] و کیانی و همکاران [5]، استفاده از روش انحراف زمان پویا را برای تطبیق الگوی ECG نشان دادند. سرانجام در رباتیک، اوتس و همکاران نشان دادند كه روش انحراف زمان پویا را می‌توان براي خوشه‌بندي خروجي‌هاي حسي عامل مورد استفاده قرار داد [23].

2. پس‌زمینه
در این بخش با سه تجربه داده‌کاوی اصلی بر کاربرد انحراف زمان پویا متمرکز می‌شویم. برای تکمیل، الگوریتم انحراف زمان پویا کلاسیک را مرور می‌کنیم.

2-1. انحراف زمان پویا با فاصله اقلیدسی
اگرچه کاربرد انحراف زمان پویا به طور گسترده در بسیاری از حوزه‌ها نشان داده شده است [1، 5، 11، 14، 22، 23، 29 و 30]، برای تکمیل مثال‌های جالب مختصری در اینجا ارائه می‌دهیم. به طور خاص، متداول‌ترین سه وظیفه داده‌کاوی، دسته‌بندی، خوشه‌بندی و کشف قواعد متناظر، را در نظر می‌گیریم. در هر مثال، انحراف زمان پویا را با فاصله اقلیدسی که معمولاً بیشتر برای مقایسه اندازه فاصله برای سری‌های زمانی استفاده می‌شود، مقایسه می‌کنیم [2، 7، 8، 10 و 15].

2-1-1. دسته‌بندی
کارهای زیادی درباره دسته‌بندی سری‌های زمانی وجود دارد. چارچوب متداول پایگاه داده، سیلندر- بل- فونل است، این پایگاه داده ترکیبی در [28] معرفی و در [21، 13 و 9] و غیره مورد استفاده قرار گرفت. پایگاه داده شامل 3 دسته مسأله است، با دسته‌هایی که با استفاده از معادلات زیر تولید می‌شوند