Mining Asynchronous Periodic Patterns in Time Series Data

ABSTRACT

Periodicy detection in time series data is a challenging problem of great importance in many applications. Most previous work focused on mining synchronous periodic patterns and did not recognize misaligned presence of a pattern due to the intervention of random noise. In this paper, we propose a more flexible model of asynchronous periodic pattern that may be present only within a subsequence and whose occurrences may be shifted due to disturbance. Two parameters min rep and max dis are employed to specify the minimum number of repetitions that is required within each segment of non-disrupted pattern occurrences and the maximum allowed disturbance between any two successive valid segments. Upon satisfying these two requirements, the longest valid subsequence of a pattern is returned. A two phase algorithm is devised to first generate potential periods by distance-based pruning followed by an iterative procedure to derive and validate candidate patterns and locate the longest valid subsequence. We also show that this algorithm can not only provide linear time complexity with respect to the length of the sequence but also achieve space efficiency .

INTRODUCTION

Periodicy detection on time series data is a challenging problem of great importance in many real applications. Most previous research in this area assumed that the disturbance within a series of repetitions of a pattern, if any, would not result in the loss of synchronization of subsequent occurrences of the pattern with previous occurrences . For example, “Joe Smith reads newspaper every morning” is a periodic pattern. Even though Joe might not read newspaper in the morning occasionally, this disturbance will not affect the fact that Joe reads newspaper in the morning of the subsequent days. In other words, disturbance is allowed only in terms of “missing occurrences” but not as general as any “insertion of random noise events”. However, this assumption is often too restrictive since we may fail to detect some interesting pattern if some of its occurrences is misaligned due to inserted noise events. Consider the application of inventory replenishment. The history of inventory refill orders can be regarded as a symbol sequence .Assume that the time between two replenishments of cold medicine is a month normally.

چکیده

تشخیص دوره ای در داده های سری زمانی یک مشکل چالش برانگیز اهمیت زیادی در بسیاری از برنامه های کاربردی است. اکثر کارهای قبلی بر روی الگوهای دوره زمانی همزمان همزمان انجام شده و حضور بی نظیر الگوی را به دلیل دخالت سر و صدایی تصادفی به رسمیت نمی شناسد. در این مقاله، ما یک مدل انعطاف پذیرتر از الگوی دوره ای ناهمگام ارائه می دهیم که ممکن است تنها در یک پسوند وجود داشته باشد و ممکن است رخدادهای آن به علت اختلال تغییر کند. برای تعیین حداقل تعداد تکرارهایی که در هر بخش از وقایع الگوی بدون وقفه و حداکثر اختلال مجاز بین هر دو بخش متوالی پیوسته وجود دارد، دو پارامتر min rep و max abs استفاده می شود. پس از رعایت این دو الزام، طولانی ترین پیروی معتبر الگوی بازگشتی است. الگوریتم دو مرحلهای برای اولین بار تولید دوره های بالقوه با هرس بر مبنای فاصله و سپس یک روش تکرار برای ایجاد و اعتبار الگوهای کاندیدات و یافتن طولانی ترین پسوند معتبر طراحی شده است. ما همچنین نشان می دهیم که این الگوریتم نه تنها می تواند پیچیدگی زمان خطی را نسبت به طول دنباله ارائه دهد، بلکه به کارآیی فضا نیز کمک می کند.

مقدمه

تشخیص دوره ای در داده های سری زمانی یک مشکل چالش برانگیز اهمیت زیادی در بسیاری از کاربردهای واقعی است. بیشتر تحقیقات قبلی در این زمینه فرض شده است که اختلال در یک سری از تکرار یک الگوی، اگر وجود داشته باشد، منجر به از دست رفتن هماهنگ سازی رخدادهای بعدی الگوی با وقایع قبلی نخواهد شد. به عنوان مثال، “جو اسمیت هر روز صبح روزنامه را می خواند” یک الگوی دوره ای است. هرچند جو ممکن است صبح گاهی روزنامه را بخواند، این اختلال بر این واقعیت تاثیر نمی گذارد که جو روز روزهای روز بعد را بخواند. به عبارت دیگر، اختلال فقط در شرایط “رخدادهای گم شده” مجاز است، اما نه به طور کلی به عنوان “درج رویدادهای ناشی از تصادف”. با این حال، این فرض اغلب بیش از حد محدود کننده است، زیرا ممکن است بعضی از رخدادهای آن به علت رویدادهای نویز وارد شده، نتوانند برخی الگوی جالب را شناسایی کنند. در مورد استفاده مجدد موجودی فکر کنید. تاریخ سفارشات تکمیل موجودی را می توان به عنوان توالی نماد مورد توجه قرار داد. فرض کنید که زمان بین دو بار اضافی دارو سرد یک ماه به طور معمول است.

Year: 2003

Publisher : IEEE

By : Jiong Yang, Wei Wang,Philip S. Yu

File Information: English Language/ 34 Page / size: 197 KB

Download

سال : 1382

ناشر : IEEE

کاری از : جیانگ یانگ، وی وانگ، فیلیپ س. یو

اطلاعات فایل : زبان انگلیسی / 34 صفحه / حجم : KB 197

لینک دانلود