Skip to content
بازگشت به نتایج جست‌وجو

استخراج مجموعه اقلام پرتکرار ECLAT

معرفی‌شده توسط
Mohammed J. Zaki
سال
2000
نوع
Frequent-itemset mining algorithm (vertical format)
خانواده
Pattern mining

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

ECLAT که در سال ۲۰۰۰ توسط محمد زکی معرفی شد، مجموعه اقلام پرتکرار را با استفاده از نمایش داده عمودی استخراج می‌کند: به جای پیمایش تراکنش‌ها، برای هر قلم، مجموعه شناسه‌های تراکنش (مجموعه شناسه تراکنش یا tidset) که آن را شامل می‌شوند را ذخیره می‌کند و پشتیبانی هر مجموعه قلم را با اشتراک مجموعه‌های شناسه تراکنش محاسبه می‌کند. این رویکرد مبتنی بر اشتراک و پیمایش عمقی، سریع و کم‌مصرف از نظر حافظه است و جایگزینی برای پیمایش‌های افقی آپریوری و درخت FP-Growth محسوب می‌شود.

شهود پشت روش

بیشتر استخراج‌کننده‌های مجموعه اقلام، سطر به سطر فکر می‌کنند: کدام اقلام در هر تراکنش وجود دارند؟ ECLAT میز را به پهلو می‌چرخاند. برای هر قلم، فهرستی از تراکنش‌هایی که آن را شامل می‌شوند را نگه می‌دارد. اکنون پشتیبانی یک جفت قلم، صرفاً اندازه همپوشانی دو فهرست آن‌هاست — یک اشتراک مجموعه ساده — و شما هرگز پایگاه داده را دوباره پیمایش نمی‌کنید. برای یافتن مجموعه‌های قلم پرتکرارتر، فهرست‌های مجموعه‌های کوتاه‌تر را اشتراک‌گذاری کنید. پیمایش این ساختار به صورت عمقی و هرس کردن در هر زمان که اشتراک‌گذاری بیش از حد کوچک شود، به طور مؤثری تمام مجموعه‌های قلم پرتکرار را شمارش می‌کند.

تاریخ

محمد زکی، ECLAT و پارادایم استخراج عمودی را در کاری که در مقاله IEEE TKDE خود در سال ۲۰۰۰ در مورد استخراج وابستگی مقیاس‌پذیر به اوج رسید، معرفی کرد و بعداً آن را با diffset (dECLAT) اصلاح کرد. این الگوریتم به همراه آپریوری (۱۹۹۴، تولید کاندیدای افقی) و FP-Growth (۲۰۰۰، مبتنی بر درخت) به عنوان یکی از سه خانواده متعارف الگوریتم‌های مجموعه اقلام پرتکرار قرار گرفت، که هر کدام پیمایش‌ها، حافظه و تراکم داده را به شیوه‌های متفاوتی مبادله می‌کنند. ECLAT همچنان یک گزینه استاندارد در مجموعه‌های ابزار داده‌کاوی باقی مانده است.

چه زمانی استفاده شود

از ECLAT برای استخراج مجموعه اقلام پرتکرار استفاده کنید زمانی که یک رویکرد عمودی مبتنی بر اشتراک برای داده‌ها مناسب است — این الگوریتم اغلب در مجموعه داده‌های متراکم بسیار سریع است و از پیمایش‌های مکرر پایگاه داده اجتناب می‌کند، و آن را به جایگزینی قوی برای آپریوری و همتراز FP-Growth تبدیل می‌کند. این الگوریتم زمانی می‌درخشد که مجموعه‌های شناسه تراکنش اندازه متوسطی داشته باشند و در حافظه جای گیرند، و نوع diffset داده‌های متراکم را به خوبی مدیریت می‌کند. هزینه‌های آن: مجموعه‌های شناسه تراکنش برای اقلام پرتکرار می‌توانند بزرگ و سنگین از نظر حافظه در مجموعه داده‌های بزرگ پراکنده باشند، اشتراک‌گذاری‌های میانی سربار اضافه می‌کنند، و مانند تمام استخراج مبتنی بر پشتیبانی، به آستانه حداقل پشتیبانی حساس است. مانند همیشه، مجموعه‌های قلم پرتکرار تنها مرحله اول هستند؛ قوانین وابستگی با اطمینان/بلندپروازی بعداً تولید می‌شوند. بین ECLAT، FP-Growth و آپریوری بر اساس تراکم داده و حافظه انتخاب کنید.

محدودیت‌ها و ملاحظات

  • مجموعه‌های شناسه تراکنش برای اقلام پرتکرار می‌توانند بزرگ باشند و در مجموعه داده‌های بزرگ حافظه مصرف کنند.
  • نتایج اشتراک‌گذاری میانی سربار حافظه/زمان اضافه می‌کنند.
  • کمتر از نمایش‌های افقی (آپریوری) شهودی است.
  • به آستانه حداقل پشتیبانی حساس است، مانند تمام استخراج مجموعه‌های قلم.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • پشتیبانی محاسبه شده توسط اشتراک‌گذاری سریع مجموعه‌های شناسه تراکنش — بدون پیمایش مکرر پایگاه داده.
  • جستجوی عمقی با کلاس‌های هم‌ارزی پیشوند، کار را مجدداً استفاده کرده و حافظه را محلی می‌کند.
  • اغلب در مجموعه داده‌های متراکم بسیار کارآمد است، با FP-Growth رقابت می‌کند.
  • بهینه‌سازی diffset حافظه و هزینه اشتراک‌گذاری را بیشتر کاهش می‌دهد.

کاربردها

  • استخراج وابستگی سبد خرید بازار و خرده‌فروشی.
  • تحلیل هم‌وقوعی وب و جریان کلیک.
  • کشف هم‌وقوعی پرتکرار در بیوانفورماتیک.
  • هر وظیفه استخراج مجموعه قلم که رویکرد عمودی مبتنی بر اشتراک را ترجیح می‌دهد.
  • مجموعه داده‌های تراکنشی متراکم که در آن‌ها ECLAT مبتنی بر diffset برتری دارد.

چگونه کار می‌کند

چگونه کار می‌کند

1

پایگاه داده یک بار به فرمت عمودی تبدیل می‌شود: هر قلم به مجموعه شناسه تراکنش خود نگاشت می‌شود، یعنی مجموعه شناسه‌های تراکنش که در آن ظاهر می‌شود. این ساختار داده کلیدی است — تمام کارهای بعدی عملیات مجموعه بر روی مجموعه‌های شناسه تراکنش هستند، نه عبور از تراکنش‌های اصلی.

فرمول
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

پشتیبانی یک مجموعه قلم، تعداد اعضای اشتراک مجموعه‌های شناسه تراکنش اقلام آن است — تعداد تراکنش‌هایی که همه آن‌ها را شامل می‌شوند. شمارش به اشتراک‌گذاری تبدیل می‌شود که سریع است، و اقلام منفرد پرتکرار (آن‌هایی که مجموعه شناسه تراکنش آن‌ها به اندازه کافی بزرگ است) جستجو را آغاز می‌کنند.

فرمول
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

مجموعه‌های قلم با اشتراک‌گذاری مجموعه‌های شناسه تراکنش گسترش می‌یابند: مجموعه شناسه تراکنش X ∪ {y} اشتراک مجموعه‌های شناسه تراکنش X و {y} است. ECLAT شبکه مجموعه اقلام را به صورت عمقی در کلاس‌های هم‌ارزی (مجموعه‌های قلم با پیشوند مشترک) کاوش می‌کند، بنابراین اشتراک‌گذاری‌ها مجدداً استفاده می‌شوند و جستجو محلی باقی می‌ماند.

فرمول
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

یک گسترش تنها در صورتی حفظ می‌شود که مجموعه شناسه تراکنش آن (و در نتیجه پشتیبانی) حداقل آستانه پشتیبانی را برآورده کند؛ در غیر این صورت آن شاخه هرس می‌شود (ضد یکنواختی: هیچ ابرمجموعه‌ای نمی‌تواند پرتکرار باشد). مجموعه‌های تفاضلی (diffsets) — که فقط تفاوت بین مجموعه‌های شناسه تراکنش را ذخیره می‌کنند — یک بهینه‌سازی رایج هستند که حافظه و هزینه اشتراک‌گذاری را بیشتر کاهش می‌دهند.

فرمول
\text{keep extensions with } \text{support} \ge \text{minsup}

دام‌های رایج

  • استخراج داده‌های پراکنده بسیار بزرگ که در آن‌ها مجموعه‌های شناسه تراکنش حافظه را منفجر می‌کنند — diffset یا FP-Growth را در نظر بگیرید.
  • تنظیم حداقل پشتیبانی خیلی پایین و تولید تعداد غیرقابل مدیریتی از مجموعه‌های قلم.
  • اشتباه گرفتن مجموعه‌های قلم پرتکرار با قوانین وابستگی (قوانین یک مرحله جداگانه هستند).
  • نادیده گرفتن نوع diffset در داده‌های متراکم که در آن بسیار کمک می‌کند.

پرسش‌های متداول

ECLAT چگونه با آپریوری و FP-Growth تفاوت دارد؟

هر سه مجموعه اقلام پرتکرار را پیدا می‌کنند. آپریوری از فرمت افقی با تولید کاندیدا و پیمایش‌های متعدد استفاده می‌کند؛ FP-Growth داده‌ها را در یک درخت فشرده کرده و به صورت بازگشتی استخراج می‌کند؛ ECLAT از فرمت عمودی tidset استفاده کرده و پشتیبانی را با اشتراک‌گذاری لیست‌های شناسه تراکنش به صورت عمقی محاسبه می‌کند. ECLAT و FP-Growth از پیمایش‌های مکرر آپریوری اجتناب می‌کنند.

مجموعه شناسه تراکنش (tidset) چیست؟

یک tidset (مجموعه شناسه تراکنش) فهرستی از تراکنش‌هایی است که حاوی یک قلم یا مجموعه قلم معین هستند. ECLAT این‌ها را به صورت عمودی ذخیره کرده و پشتیبانی یک مجموعه قلم را به عنوان اندازه اشتراک مجموعه‌های شناسه تراکنش اقلام آن محاسبه می‌کند و شمارش را به اشتراک‌گذاری مجموعه تبدیل می‌کند.

مجموعه‌های تفاضلی (diffsets) چیستند؟

Diffsetها به جای مجموعه شناسه تراکنش کامل، فقط تفاوت بین مجموعه شناسه تراکنش یک مجموعه قلم و مجموعه شناسه تراکنش والد آن را ذخیره می‌کنند. در داده‌های متراکم، این امر حافظه و هزینه اشتراک‌گذاری را به شدت کاهش می‌دهد و به نوع dECLAT مزیت کارایی قابل توجهی می‌بخشد.

روش‌های مرتبط

منابع

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    باز کردن مرجع DOI
    کپی شد.