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

الگوریتم Apriori

معرفی‌شده توسط
Agrawal, R. & Srikant, R.
سال
1994
نوع
Frequent itemset and association rule mining algorithm
خانواده
Machine learning

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

اندازه قلم

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

الگوریتم Apriori که در سال ۱۹۹۴ توسط Agrawal و Srikant معرفی شد، روشی بنیادی برای کشف مجموعه‌های مورد (itemsets) پرتکرار و قواعد وابستگی در پایگاه‌های داده تراکنشی است. این الگوریتم از جستجوی سطح به سطح و با جهت‌گیری پهن‌بند (breadth-first) استفاده می‌کند که توسط خاصیت ضد مونوتون پشتیبانی (support) هدایت می‌شود تا به طور کارآمد تمام ترکیبات موردها را که فراوانی آن‌ها بالاتر از یک آستانه حداقل تعیین‌شده توسط کاربر است، شمارش کند و سپس قواعد قابل تفسیر «اگر-آنگاه» را از آن الگوها استخراج نماید.

شهود پشت روش

یک پایگاه داده از رسیدهای سوپرمارکتی را در نظر بگیرید. بینش Apriori خاصیت ضد مونوتون است: اگر یک جفت محصول به ندرت با هم خریداری شوند، هیچ مجموعه بزرگ‌تری که شامل آن جفت باشد نمی‌تواند پرتکرار باشد. این امر به الگوریتم اجازه می‌دهد تا فضای جستجوی نماییِ ترکیبات ممکن موردها را با ساختن کاندیداها سطح به سطح – از موارد منفرد، سپس جفت‌ها، سپس سه‌تایی‌ها – و حذف هر کاندیدایی که زیرمجموعه‌های آن از قبل نامکرر شناخته شده‌اند، قبل از شمارش آن در داده‌ها، هنجارشکنی (prune) کند.

تاریخ

Rakesh Agrawal و Ramakrishnan Srikant الگوریتم Apriori را در VLDB 1994 معرفی کردند، که بر اساس فرمول‌بندی Agrawal و همکاران در سال ۱۹۹۳ از مسئله استخراج قواعد وابستگی بنا شده است. نام آن منعکس‌کننده بینش کلیدی آن است: استفاده از دانش قبلی از مجموعه‌های مورد (k) پرتکرار برای هنجارشکنی کاندیداها در سطح k+1. این الگوریتم به معیار استاندارد تبدیل شد که در برابر آن تمام الگوریتم‌های بعدی استخراج مجموعه مورد پرتکرار – از جمله FP-Growth (2000) و Eclat – سنجیده می‌شوند و همچنان یک فصل استاندارد در کتاب‌های درسی داده‌کاوی و یادگیری ماشین باقی مانده است.

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

هنگامی از Apriori استفاده کنید که هدف کشف الگوهای هم‌رخدادی یا روابط اگر-آنگاه در داده‌های تراکنشی یا حضور مورد باینری است – تحلیل سبد خرید، هم‌تأییدی موارد نظرسنجی، هم‌رخدادی تشخیص پزشکی، یا وابستگی اصطلاحات متنی. این الگوریتم برای مجموعه داده‌های با اندازه متوسط که در آن‌ها شفافیت و قابلیت تفسیر قواعد خروجی اولویت دارد، مناسب است. از Apriori زمانی استفاده نکنید که پایگاه داده تراکنش‌ها بسیار بزرگ است (میلیون‌ها ردیف با کاتالوگ‌های گسترده مورد)، زیرا اسکن‌های مکرر کامل پایگاه داده آن را در مقایسه با FP-Growth کند می‌کند؛ در این موارد FP-Growth ترجیح داده می‌شود. همچنین برای داده‌های عددی پیوسته بدون گسسته‌سازی قبلی نامناسب است و جهت‌داری یا علیت را مدل نمی‌کند.

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

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

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

نقاط قوت

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

کاربردها

  • تحلیل سبد خرید: کشف اینکه کدام محصولات اغلب با هم خریداری می‌شوند تا چیدمان قفسه و تبلیغات را هدایت کنند.
  • اطلاعات پزشکی: شناسایی علائم، تشخیص‌ها یا نسخه‌های دارویی هم‌رخداد در سوابق بیمار.
  • داده‌کاوی استفاده از وب: یافتن اینکه کدام صفحات یا ویژگی‌ها کاربران تمایل دارند با هم بازدید کنند یا فعال نمایند.
  • تحلیل نظرسنجی و پرسشنامه: تشخیص اینکه کدام موارد یا پاسخ‌های مقیاس به طور سیستماتیک با هم تأیید می‌شوند.
  • راه‌اندازی سیستم توصیه‌گر: تولید انجمن‌های مورد کاندید قبل از استقرار فیلترینگ مشارکتی.
  • تشخیص تقلب: آشکارسازی الگوهای هم‌رخدادی غیرمعمول در گزارش‌های تراکنش که از سبدهای عادی منحرف می‌شوند.

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

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

1

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

2

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

فرمول
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

مجموعه‌های مورد پرتکرار یافت‌شده در سطح k به صورت جفتی ترکیب می‌شوند تا مجموعه‌های مورد کاندید با اندازه k+1 تشکیل شوند. تنها جفت‌هایی که k-1 مورد اول یکسان دارند، ترکیب می‌شوند؛ این قانون مجموعه کاندید را فشرده نگه می‌دارد. یک اسکن جدید پایگاه داده، پشتیبانی هر کاندید را شمارش می‌کند.

4

قبل از شمارش، هر کاندید با اندازه k+1 در برابر تمام زیرمجموعه‌های (k) آن بررسی می‌شود. اگر هر زیرمجموعه‌ای در سطح قبلی پرتکرار نبوده باشد، کاندید بلافاصله بدون خواندن داده‌ها هنجارشکنی می‌شود و از خاصیت ضد مونوتون برای کاهش محاسبات بهره می‌برد. بازماندگان این مرحله هنجارشکنی، سطح بعدی مجموعه‌های مورد پرتکرار را تشکیل می‌دهند.

5

از هر مجموعه مورد پرتکرار با اندازه دو یا بیشتر، تمام قواعد اگر-آنگاه ممکن با تقسیم موارد به یک مقدم (antecedent) و یک تالی (consequent) تولید می‌شوند. هر قاعده بر اساس اطمینان ارزیابی می‌شود – نسبت تراکنش‌های مقدم که شامل تالی نیز هستند. قواعد زیر حداقل اطمینان حذف می‌شوند.

فرمول
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

قواعد بازمانده بر اساس لیفت (lift) رتبه‌بندی می‌شوند، که اطمینان مشاهده‌شده را با فراوانی پایه تالی مقایسه می‌کند. لیفت بالاتر از ۱ نشان می‌دهد که مقدم و تالی بیش از حد تصادفی با هم رخ می‌دهند؛ لیفت نزدیک به ۱ نشان‌دهنده استقلال است؛ لیفت کمتر از ۱ نشان‌دهنده یک وابستگی منفی است. قواعد با بالاترین لیفت، عملی‌ترین اکتشافات هستند.

فرمول
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

دام‌های رایج

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

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

تفاوت بین پشتیبانی، اطمینان و لیفت چیست؟

پشتیبانی کسری از کل تراکنش‌ها است که شامل مجموعه مورد می‌شود – این شیوع را اندازه‌گیری می‌کند. اطمینان احتمال شرطی است که تالی با فرض مقدم ظاهر می‌شود – این قابلیت اطمینان قاعده را اندازه‌گیری می‌کند. لیفت نسبت اطمینان مشاهده‌شده به فراوانی پایه تالی است؛ لیفتی بالاتر از ۱ نشان‌دهنده یک وابستگی مثبت واقعی به جای یک تصادف ناشی از محبوبیت مورد است.

چه زمانی باید FP-Growth را به Apriori ترجیح دهم؟

FP-Growth پایگاه داده را به ساختار درختی فشرده می‌کند و آن را بدون اسکن‌های کامل مکرر استخراج می‌کند، که آن را در مجموعه داده‌های بزرگ یا زمانی که حداقل پشتیبانی پایین است، به طور قابل توجهی سریع‌تر می‌کند. Apriori درک و پیاده‌سازی آسان‌تری دارد و در مجموعه داده‌های کوچک تا متوسط که زمان اجرا گلوگاه نیست، به خوبی کار می‌کند.

چگونه حداقل پشتیبانی و اطمینان را انتخاب کنم؟

قانون جهانی وجود ندارد. رویه رایج این است که الگوریتم را در چندین سطح پشتیبانی اجرا کنید، تعداد مجموعه‌های مورد پرتکرار را در برابر پشتیبانی رسم کنید و مقداری را در نقطه خمیدگی منحنی انتخاب کنید. سپس اطمینان بر اساس سوال کسب و کار یا تحقیق تنظیم می‌شود – اطمینان بالاتر برای قواعد حیاتی، پایین‌تر برای اکتشافات اکتشافی. همیشه قواعد برتر را در برابر تخصص دامنه اعتبارسنجی کنید.

آیا Apriori می‌تواند داده‌های عددی یا پیوسته را مدیریت کند؟

Apriori به داده‌های حضور مورد باینری نیاز دارد. متغیرهای پیوسته باید قبل از کدگذاری به عنوان موارد، به سطل‌ها (مثلاً سن به کم/متوسط/زیاد) گسسته شوند. گسسته‌سازی ضعیف می‌تواند قواعد کشف‌شده را به شدت تحریف کند، بنابراین استراتژی سطل‌بندی شایسته تفکر دقیق است.

آیا Apriori علیت بین موارد را القا می‌کند؟

خیر. قواعد وابستگی هم‌رخدادی را ثبت می‌کنند، نه علیت یا جهت‌داری. قاعده‌ای مانند «نان → کره» به این معنی است که آن‌ها اغلب در یک سبد ظاهر می‌شوند؛ این به معنای آن نیست که خرید نان باعث خرید کره می‌شود، و نه اینکه رابطه از نظر علّی نامتقارن است.

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

منابع

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    باز کردن مرجع انتشار
    کپی شد.
  2. Apriori algorithm. Wikipedia.

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