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

کاوش قوانین انجمنی (آپریوری)

معرفی‌شده توسط
Rakesh Agrawal & Ramakrishnan Srikant
سال
1994
نوع
Unsupervised pattern discovery algorithm
خانواده
Pattern mining

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

اندازه قلم

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

کاوش قوانین انجمنی (Association Rule Mining) یک تکنیک داده‌کاوی بدون نظارت است که الگوهای هم‌رخدادی را در میان اقلام در مجموعه‌داده‌های تراکنشی کشف می‌کند. این تکنیک که به طور رسمی توسط آگراوال، ایمیلینسکی و سوامی در سال ۱۹۹۳ معرفی شد و با الگوریتم برجسته آپریوری توسط آگراوال و سریکانت در سال ۱۹۹۴ تکمیل گردید، قوانینی به شکل X ⇒ Y را شناسایی می‌کند — به این معنی که تراکنش‌های حاوی مجموعه اقلام X تمایل دارند مجموعه اقلام Y را نیز شامل شوند — که با معیارهای پشتیبانی (support)، اطمینان (confidence) و ارتقاء (lift) کمی‌سازی می‌شوند.

شهود پشت روش

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

تاریخ

مقاله بنیادی آگراوال، ایمیلینسکی و سوامی (۱۹۹۳) مسئله قانون انجمنی را در زمینه داده‌های تراکنش سوپرمارکت تعریف کرد. مقاله VLDB آگراوال و سریکانت در سال ۱۹۹۴ الگوریتم آپریوری و استراتژی هرس کارآمد آن را معرفی کرد که کاوش در مقیاس بزرگ را عملی ساخت. کارهای بعدی FP-Growth (هان و همکاران، ۲۰۰۰) را تولید کرد که به طور کامل از تولید کاندید اجتناب می‌کند، و ECLAT که در قالب داده عمودی کاوش می‌کند — و یک خانواده الگوریتمی غنی را ایجاد کرد که اکنون در برنامه‌های درسی داده‌کاوی مرکزی است.

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

کاوش قوانین انجمنی برای مجموعه‌داده‌های تراکنشی بزرگ که هدف کشف الگوهای هم‌رخدادی بدون یک متغیر هدف از پیش تعریف شده است، مناسب است. این روش فرض می‌کند که اقلام برای هر تراکنش باینری (موجود/ناموجود) هستند. برای تحلیل سبد خرید، سیستم‌های توصیه‌گر، تحلیل جریان کلیک وب و کشف هم‌تشخیصی پزشکی مناسب است. برای داده‌های پیوسته یا ترتیبی، مگر اینکه از قبل گسسته‌سازی شده باشند، برای مجموعه‌داده‌هایی با ابعاد بسیار بالا (فضای کاندید نمایی)، یا زمانی که استنتاج علّی به جای استنتاج انجمنی مورد نیاز است، نامناسب است. جایگزین‌ها شامل FP-Growth برای شمارش سریع‌تر مجموعه‌های اقلام پرتکرار و کاوش توالی زمانی که ترتیب زمانی اهمیت دارد، هستند.

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

این الگوریتم پایگاه داده تراکنش D را اسکن می‌کند تا تعداد دفعات ظاهر شدن هر مجموعه اقلام X را بشمارد. یک مجموعه اقلام تنها زمانی پرتکرار اعلام می‌شود — و در L_k قرار می‌گیرد — که پشتیبانی آن (کسری از تراکنش‌های حاوی آن) به آستانه حداقل پشتیبانی σ_min تعریف شده توسط کاربر برسد یا از آن فراتر رود. این فرآیند با اقلام منفرد (k=1) آغاز می‌شود و به صورت تکراری مجموعه‌های کاندید بزرگتر را می‌سازد.

فرمول
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

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

فرمول
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

از هر مجموعه اقلام پرتکرار X ∪ Y، الگوریتم قوانینی به شکل X ⇒ Y تولید می‌کند که در آن X و Y زیرمجموعه‌های مجزا هستند. یک قانون تنها زمانی حفظ می‌شود که اطمینان آن — احتمال شرطی Y به شرط X، که به صورت support(X ∪ Y) / support(X) محاسبه می‌شود — به آستانه حداقل اطمینان γ_min برسد یا از آن فراتر رود. این مرحله هم‌رخدادی خام را به گزاره‌های پیش‌بینی‌کننده جهت‌دار تبدیل می‌کند.

فرمول
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

قوانین حفظ شده بر اساس ارتقاء (lift) رتبه‌بندی و فیلتر می‌شوند، که میزان احتمال بیشتر ظاهر شدن Y با X را نسبت به حالت تصادفی اندازه‌گیری می‌کند. ارتقاء > 1 نشان‌دهنده همبستگی مثبت فراتر از استقلال است؛ ارتقاء = 1 نشان‌دهنده استقلال است؛ ارتقاء < 1 نشان‌دهنده همبستگی منفی است. معیارهای جالب‌توجهی اضافی مانند conviction و leverage می‌توانند مجموعه قوانین را برای استقرار عملی بیشتر پالایش کنند.

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

دام‌های رایج

  • تنظیم حداقل پشتیبانی بیش از حد پایین، تحلیلگر را با قوانین کاذب غرق می‌کند؛ انتخاب آستانه نیاز به دانش دامنه یا اعتبارسنجی متقابل دارد.
  • اشتباه گرفتن همبستگی آماری با علیت: ارتقاء بالا به معنای این نیست که X باعث Y می‌شود.
  • نادیده گرفتن توزیع فراوانی اقلام: اقلام رایج بر قوانین غالب می‌شوند و ارتباطات معنی‌دار اقلام نادر را تحت‌الشعاع قرار می‌دهند.
  • در نظر گرفتن تنها اطمینان به عنوان یک معیار کیفیت؛ یک قانون با اطمینان بالا اما ارتقاء پایین ممکن است بهتر از شانس تصادفی عمل نکند.

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

تفاوت بین پشتیبانی، اطمینان و ارتقاء چیست؟

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

الگوریتم آپریوری چگونه هزینه محاسباتی را کاهش می‌دهد؟

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

چه زمانی باید به جای آپریوری از FP-Growth استفاده کنم؟

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

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

منابع

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    باز کردن مرجع DOI
    کپی شد.
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

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