الگوریتم ECLAT (Equivalence Class Clustering and Bottom-up Lattice Traversal) مقدمه الگوریتم ECLAT یکی از مهم‌ترین الگوریتم‌های استخراج مجموعه اقلام پرتکرار (Frequent Itemsets) در حوزه داده‌کاوی است. این الگوریتم برای کشف الگوهای تکرارشونده در پایگاه داده‌های تراکنشی طراحی شده و در مسائلی مانند تحلیل سبد خرید، سیستم‌های پیشنهاددهنده، تحلیل رفتار مشتریان و کشف قوانین انجمنی کاربرد گسترده‌ای دارد. هدف اصلی ECLAT، شناسایی مجموعه‌ای از اقلام است که تعداد دفعات حضور آن‌ها در تراکنش‌ها از یک آستانه مشخص به نام حداقل حمایت (Minimum Support) بیشتر باشد. ایده اصلی الگوریتم ECLAT مبنای کار ECLAT بر استفاده از نمایش عمودی داده‌ها (Vertical Data Format) است. در بسیاری از الگوریتم‌های استخراج الگوهای پرتکرار مانند Apriori، داده‌ها به صورت افقی ذخیره می‌شوند؛ یعنی برای هر تراکنش، اقلام موجود در آن ثبت می‌شوند. اما ECLAT از رویکرد متفاوتی استفاده می‌کند و برای هر قلم، فهرست شناسه تراکنش‌هایی که آن قلم در آن‌ها وجود دارد نگهداری می‌شود. به این فهرست، Transaction ID List (TID List) گفته می‌شود. در نتیجه، به جای جستجو در کل پایگاه داده برای محاسبه فراوانی مجموعه اقلام، تنها کافی است اشتراک لیست‌های تراکنش محاسبه شود.

مفاهیم پایه در ECLAT 1. آیتم (Item) هر ویژگی، کالا یا عنصر موجود در پایگاه داده که مورد بررسی قرار می‌گیرد. 2. تراکنش (Transaction) مجموعه‌ای از اقلام که در یک رکورد از پایگاه داده حضور دارند. 3. مجموعه اقلام (Itemset) گروهی از یک یا چند قلم که به صورت همزمان بررسی می‌شوند. 4. حمایت (Support) حمایت معیاری برای اندازه‌گیری میزان تکرار یک مجموعه اقلام در پایگاه داده است. حمایت برابر است با تعداد تراکنش‌هایی که آن مجموعه اقلام در آن‌ها ظاهر شده‌اند. هرچه مقدار حمایت بیشتر باشد، اهمیت مجموعه اقلام بیشتر خواهد بود. 5. حداقل حمایت (Minimum Support) آستانه‌ای است که توسط تحلیلگر تعیین می‌شود. اگر حمایت یک مجموعه اقلام کمتر از این مقدار باشد، آن مجموعه حذف می‌شود و در مراحل بعدی مورد بررسی قرار نمی‌گیرد. ساختار داده در ECLAT ویژگی اصلی ECLAT استفاده از ساختار عمودی داده است. در این ساختار: هر قلم دارای یک شناسه است. برای هر قلم، لیستی از شناسه تراکنش‌های شامل آن ذخیره می‌شود. این لیست‌ها مبنای تمام محاسبات بعدی قرار می‌گیرند. مزیت این روش آن است که محاسبه فراوانی مجموعه اقلام از طریق عملیات اشتراک روی لیست‌ها انجام می‌شود و نیازی به پیمایش مکرر پایگاه داده وجود ندارد.

مراحل اجرای الگوریتم ECLAT مرحله اول: تبدیل داده‌ها به فرم عمودی در ابتدا پایگاه داده تراکنشی خوانده می‌شود. سپس برای هر قلم، لیست شناسه تراکنش‌های مربوط به آن استخراج می‌شود. در پایان این مرحله، پایگاه داده به مجموعه‌ای از TID Listها تبدیل می‌شود. مرحله دوم: محاسبه حمایت اقلام منفرد برای هر قلم، تعداد عناصر موجود در TID List محاسبه می‌شود. این مقدار همان حمایت آن قلم است. اقلامی که حمایت آن‌ها کمتر از حداقل حمایت تعیین‌شده باشد حذف می‌شوند. مرحله سوم: تشکیل کلاس‌های هم‌ارز پس از شناسایی اقلام پرتکرار اولیه، الگوریتم آن‌ها را در ساختارهایی به نام کلاس هم‌ارز (Equivalence Class) سازمان‌دهی می‌کند. هدف از این کار کاهش فضای جستجو و جلوگیری از تولید ترکیب‌های غیرضروری است. هر کلاس شامل مجموعه‌ای از اقلامی است که دارای پیشوند مشترک هستند. مرحله چهارم: تولید مجموعه اقلام جدید الگوریتم مجموعه‌های بزرگ‌تر را از روی مجموعه‌های قبلی تولید می‌کند. برای محاسبه حمایت مجموعه جدید، به جای مراجعه به پایگاه داده، اشتراک TID Listهای مربوطه محاسبه می‌شود. تعداد عناصر موجود در اشتراک، حمایت مجموعه جدید را مشخص می‌کند.

مثال👆