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

امروزه حجم بسیار بالایی اطلاعات، در مخازن داده ذخیره می شود که ممکن لحظه به لحظه بر این حجم افزوده شود. از طرفی سازمان ها به دنبال استخراج دانش از داده های جمع آوری شده هستند. یکی از راه های استخراج دانش ازداده ها، داده کاوی است. تکنیک داده کاوی توزیع شده، یکی از شاخه های علمی جدید و روبه توسعه با قابلیت و کارایی زیاد است که بر اساس نیاز کاوش در منابع توزیع شده و غیر متمرکز داده ای به وجود آمده است. یکی از روش های داده کاوی، استخراج مجموعه آیتم های مکرر یا تولید قوانین انجمنی است. در این مقاله به مطالعه نحوه پیاده سازی الگوریتم FP-growthبه صورت موازی و در محیط توزیع شده با استفاده از مدل برنامه نویسی نگاشت کاهش می پردازیم. سپس این الگوریتم را به منظور استخراج موازی الگوهای تکراری تحت سه سناریو مختلف مورد آزمون قرار دادیم. نتایج تجربی از این آزمون، کارایی الگوریتم برای مجموعه داده ها در زمینه دسترس پذیری، مقیاس پذیری و توسعه پذیری تحت مدل برنامه نویسی نگاشت کاهش را نشان داد. در مورد معیار دسترس پذیری نشان دادیم که افزایش حداقل آستانه تکرار، موجب کاهش چشمگیر زمان اجرای الگوریتم با مجموعه داده ثابت 500 مگابایت می شود. همچنین صحت قابلیت مقیاس پذیری الگوریتم FP-growth، تحت آزمایش با حجم مجموعه داده مختلف، تایید شد. از طرفی تغییر گره ها از دو به پنج و سپس هشت گره، موجب کاهش زمان اجرای الگوریتم FP-growth با مجموعه داده ثابت 500 مگابایت و تحت حد آستانه تکرار مختلف شد که نشان از توسعه پذیر بودن الگوریتم است.

کلیدواژه ها:

قوانین انجمنی ، مدل برنامه نویسی نگاشت کاهش ، الگوهای مکرر ، FP-Growth