4130

4130

ارائه يك مدل توزيع شده قوانين انجمني براي داده كاوي در داده هاي حجيم

كارشناسي ارشد

1383

دكتر محمد رضا كنگاوري

16

استخراج قوانين انجمني يكي از مهمترين اهداف داده كاوي است و معمولا شامل دو مرحله است .در مرحله اول مجموعه آيتم هاي مكرر (Frequent) موجود در تراكنشها پيدا مي شود و در مرحله دوم قوانين انجمني موجود در اين مجموعه استخراج مي گردد .مرحله دوم اين الگوريتمها داراي پيچيدگي خاصي نيست و تمامي بار اين فرايند ،مربوط به مرحله اول ميباشد .با توجه به ماهيت مسئله ،مرحله اول الگوريتمهاي استخراج قوانين انجمني ،داراي پيچيدگي زماني نمايي هستند . دراين رساله دو الگوريتم دراين زمينه ارائه شده است .الگوريتم اول به صورت ترتيبي است و با ديدي جديد به اين مسئله نگاه مي كند .اين الگوريتم بيشتر به محتواي تراكنشها تكيه دارد و در نتيجه ،در اغلب موارد بسيار خوب عمل مي نمايد و براي استخراج تمام مجموعه آيتمهاي مكرر ،حتي در بدترين حالت ،كارايي آن معادل الگوريتمهاي قبلي مي باشد .الگوريتم ارائه شده دوم ،بر روي موازي سازي مرحله پيدا نمودن مجموعه آيتمهاي مكرر تمركز دارد .اين الگوريتم از نمايش عمودي براي نمايش تراكنشها استفاده مي كند و پس از توزيع تراكنشها بر روي گره هاي خوشه ،از استراتژي جستجوي عمق اول براي پيدا نمودن مجموعه آيتمهاي مكرر بر روي اين پردازنده ها استفاده مي كند .