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

قواعد وابستگی

معرفی‌شده توسط
Agrawal, R., Imielinski, T., & Swami, A.
سال
1993
نوع
Unsupervised pattern discovery
خانواده
Machine learning

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

یادگیری قواعد وابستگی به طور رسمی توسط آگراوال، ایمیلینسکی و سوامی در کنفرانس ACM SIGMOD سال ۱۹۹۳ معرفی شد، که با چالش استخراج پایگاه داده‌های تراکنش سوپرمارکت‌ها انگیزه گرفته بود. مقاله بعدی آن‌ها در سال ۱۹۹۴ الگوریتم آپریوری را معرفی کرد که یک روش محاسباتی کارآمد را ارائه می‌داد. این حوزه به سرعت در دهه‌های ۱۹۹۰ و ۲۰۰۰ رشد کرد، و الگوریتم اف‌پی-گروث (هان و همکاران، ۲۰۰۰) بعدها بهبودهای بیشتری در سرعت ارائه داد. قواعد وابستگی همچنان یک تکنیک بنیادی در برنامه‌های درسی استخراج داده باقی مانده‌اند و به طور معمول در تحلیل‌های خرده‌فروشی، بهداشت و درمان و وب کاربرد دارند.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

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

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

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

فرمول
X \Rightarrow Y, \quad X \cap Y = \emptyset
4

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

فرمول
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}
5

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

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

دام‌های رایج

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

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

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

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

تفاوت بین اعتماد و بالابری چیست و کدام را باید اولویت دهم؟

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

آیا می‌توان از قواعد وابستگی برای پیش‌بینی استفاده کرد؟

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

مجموعه داده من دارای متغیرهای پیوسته است. آیا هنوز می‌توانم از قواعد وابستگی استفاده کنم؟

تنها پس از گسسته‌سازی. متغیرهای پیوسته باید قبل از کدگذاری به عنوان اقلام باینری به بازه‌های دسته‌بندی شده (مانند گروه‌های سنی، پنجک‌ها) تقسیم شوند. انتخاب مرزهای دسته بندی به طور قابل توجهی بر قوانینی که ظاهر می‌شوند تأثیر می‌گذارد، بنابراین تصمیمات گسسته‌سازی باید از نظر تئوری توجیه شده و به طور شفاف گزارش شوند.

قواعد وابستگی چگونه با تحلیل همبستگی تفاوت دارند؟

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

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

منابع

  1. Agrawal, R., Imielinski, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 207–216.

    باز کردن مرجع DOI
    کپی شد.
  2. Tan, P.-N., Steinbach, M., Karpatne, A., & Kumar, V. (2018). Introduction to Data Mining (2nd ed., Ch. 5). Pearson.

    شابک: 978-0-13-312890-1
    کپی شد.