در این مطلب، به شرح و توضیح الگوریتم Eclat می پردازیم که به منظور استخراج قوانین انجمنی/ توصیفی در داده ها استفاده می گردد. همان طور که می دانید قوانین انجمنی برای کشف ارتباط بین آیتم های موجود در دیتاست استفاده می شود. به عنوان مثال برای پیدا کردن الگوهای توصیفی در خرید مشتریان از یک فروشگاه کاربرد دارد. این الگوریتم همانند الگوریتم آپریوری می باشد، با این تفاوت که این الگوریتم بر روی فرمت عمودی داده ها کار می کند. لذا، قبل از ادامه توضیحات در خصوص این الگوریتم نحوه ی تبدیل داده های افقی به عمودی را به صورت زیر شرح می دهیم.
همانطور که می دانید الگوریتم آپریوری بر روی فرمت افقی کار می کند. ولی الگوریتم Eclat با تغییر فرمت داده ها به عمودی باعث افزایش سرعت می گردد. و تفاوت دیگر آن با الگوریتم آپریوری در آن است که داده های تکراری قبل از شروع فرآیند باید حذف گردند. در ادامه با یک مثال این الگوریتم را توضیح می دهیم. در مثال زیر min_sup = 2 در نظر گرفته شده است:
در گام بعدی مشترکات بین هر دو مجموعه را به صورت جداگانه محاسبه می نماییم. تا با این روش آیتم های دو تایی را بدست آوریم. و چون min_sup را 2 در نظر گرفته ایم. مجموعه هایی که کمتر از 2 آیتم دارد در این مرحله حذف می شود.
در این مرحله آیتم های 3 تایی را بدست می آوریم. و با یافتن اشتراکات جدول 2 تایی بدست می آید. فقط مواردی باهم ترکیب می شوند که آغازگر هم نام داشته باشند. مثل جدول بالا مواردی که کمتر از min_sup است حذف می شود.
در مرحله ی بعد آیتم های 4 تایی استخراج می شود.
لیست قوانین معتبر نهایی بر اساس این الگوریتم به صورت زیر است:
مزایای الگوریتم Eclat:
- با توجه به استفاده از متد جستجوی اول عمق (First-Depth) حافظه کمتری را اشغال می کند.
- زمان کمتری را برای تولید الگوهای تکراری مصرف می کند، زیرا کمتر به اسکن داده ها برای محاسبه مقدار ساپورت می پردازد.
معایب الگوریتم Eclat:
- مناسب برای دیتاست های کوچک و متوسط می باشد.
- زمانی که لیست تراکنش ها زیاد شود، زمان زیادی را برای ذخیره لیست های کاندید شده اختصاص می دهد
- در دیتاست های بزرگ، زمان زیادی برای محاسبه اشتراکات بین مجموعه ها در نظر می گیرد.
