داده کاوی توالی های تکرارپذیر

داده کاوی توالی های تکرارپذیر

سمینار درس data mining

Frequent sequences

ALGORITHMS FOR MINING FREQUENT SEQUENCES

مساله داده کاوی توالیهای تکرارپذیر این است که تکرارپذیری را که در زیر توالیهای یک پایگاه داده تکرارپذیر روی می دهد استخراج کنیم.

مقدمه

بعضی از کاربردهای sequence mining عبارت است از:

• با انجام بر روی پایگاه داده پزشکی محقق ممکن است به این موضوع پی ببرد که رویدادن توالی نشانه های معینی منجر به بیماری معینی می گردد.
• با تحلیل weblog (گزارشات روزانه بدست آمده از web ) یک web site می تواند محبوبترین صفحات web را که مورد بازدید واقع می شود شناسایی کند .
• آنالیز توالی DNA یکی از سطوح تحقیق بسیار مهم است در علم ژنتیک که اجازه می دهد بیماریهای ارثی را کشف کنیم و پیش بینی کنیم که آیا یک فرد ناقل بیماری معینی می باشد یا نه ؟
• یک کتابفروش اینترنتی می تواند تحلیل کند توالیهای خرید مشتریانش را برای دستیابی به الگوی خرید آنها و می تواند به مغازه در طراحی استراتژی فروش کمک کند.

اولین مدلی که در این زمینه ارائه شده بود دارای پایگاه داده ای متشکل از تراکنش ها می شود. هر Transaction مجموعه ای از آیتمها در ارتباط با یک ID برای مشتری ویک ID برای زمان. اگر این transaction ها با ID هایشان گروهبندی شوند و سپس بر اساس افزایش ID زمان هر مشتری مرتب شوند تعدادی توالی مشتری بدست می آید.هر توالی مشتری نشان دهنده سفارشی است که یک مشتری انجام داده است. مساله این است که زیرتوالیهایی پیدا کنیم که در بین همه مشتریان زیاد تکرار شده اند.

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

ابتدا چهار الگوریتم مهم برای sequencing ارائه می گردد.که عبارتد از gsp MFS، SPADE و PREFIXSPAN می باشند.

در میان همه الگوریتمها، GSP یک الگوریتم چند فازی تکرارشونده می باشد. این الگوریتم تعدادی از آیتمها را بررسی اجمالی میکند. بسیار شبیه به ساختار الگوریتم APRIORIبرای داده کاوی ASSOCIATION RULES ،GSP کارش را با پیدا کردن همه توالیهای با طول یک با بررسی اجمالی پایگاه داده شروع می کند. این شیوه سپس برای توالیهای با طول 2 بکار برده می شود.میزان SUPPORT یا تکرار÷ذیری از توالیهای انتخاب شده با مرور مجدد پایگاه داده محاسبه می شود.آن توالیهایی با طول 2 کهتکرار پذیر هستند برای تولید توالیهای منتخب با طول 3 بکار برده می شوندو به همین ترتیب. این فرآیند تا زمانی تکرار می شود که در بررسی اجمالی پایگاه داده توالیهای تکرارپذیر بیشتری کشف نشوند. GSP الگوریتم کارایی می باشد.

بهر حال تعداد تکرارها ( و بنابر این مرور پایگاه داده ) مورد نیاز در GSP وابسته به طول بلند ترین توالیهای تکرار÷ذیر در پایگاه داده می باشند. بنابراین در صورتیکه پایگاه داده بزرگ باشد و یا اگر آن دربردارنده طولهای بزرگی از توالیهای تکرارپذیر باشند ، هزینه I/O (ورودی ، خروجی) در GSP بالا خواهد بود.

برای بهبود اجرای I/O در GSP، الگوریتمی که MFS گفته می شود بدست آمده است. MFS ابتدا جوابهای تقریبی را پیدا می کند وSest و برایمجموعهتوالیهایتکرارپذیریکراه برای دستیابی به Sest، تحلیل داده ای یک نمونه از پایگاه داده مورد استفاده، برای مثال، GSP است.

MFS سپس یكبار پایگاه داده را برای تعیین توالیهایی كه در Sest تكرار پذیر هستند مرور می كند .