قواعد انجمنی نیمهنظارتشده
- معرفیشده توسط
- Liu, B.; Hsu, W.; Ma, Y. (and subsequent researchers)
- سال
- 2003–2010s
- نوع
- Pattern mining with partial supervision
- خانواده
- Machine learning
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
کشف قواعد انجمنی نیمهنظارتشده، یادگیری کلاسیک قواعد انجمنی را با گنجاندن مقدار کمی داده برچسبدار در کنار مجموعه داده بزرگتری از دادههای بدون برچسب گسترش میدهد. این روش از اطلاعات کلاس شناختهشده یا محدودیتهای ارائهشده توسط کاربر برای هدایت کشف قواعدی استفاده میکند که هم از نظر آماری فراوان و هم از نظر معنایی معنادار هستند و بین استخراج الگو بدون نظارت و نظارت سبک پل میزند.
شهود پشت روش
کشف قواعد انجمنی استاندارد، تمام الگوهای همرخدادی فراوان را بدون هیچ درکی از اهمیت، پیدا میکند. قواعد انجمنی نیمهنظارتشده با اجازه دادن به مجموعه کوچکی از نمونههای برچسبدار یا محدودیتهای دامنه برای هدایت جستجو، این را تغییر میدهند: قواعدی که با ساختار کلاس شناختهشده همسو هستند، نسبت به قواعدی که از نظر آماری فراوان اما بیمعنی هستند، ارجحیت دارند. به آن به عنوان دادن چند اشاره به الگوریتم در مورد آنچه تحلیلگر به آن اهمیت میدهد فکر کنید، بنابراین الگوریتم از نمایش الگوهای پیشپاافتاده یا از قبل شناختهشده دست میکشد و در عوض روابط واقعاً جدید و قابل اجرا را برجسته میکند. نتیجه، وسعت کشف الگوی بدون نظارت را با هدایت کافی برای مرتبط نگه داشتن نتایج ترکیب میکند.
تاریخ
استخراج قواعد انجمنی در سال ۱۹۹۳ توسط Agrawal، Imielinski و Swami با معرفی الگوریتم Apriori رسمی شد و هدف آن کشف بدون نظارت مجموعه اقلام فراوان در دادههای سبد خرید بود. ادغام برچسبهای کلاس و محدودیتها در استخراج قواعد انجمنی در اوایل دهه ۲۰۰۰ شتاب گرفت، به ویژه از طریق چارچوبهای CMAR و CBA از همکاران Liu، که برچسبهای کلاس را به عنوان نتایج قاعده در نظر میگرفتند. گسترشهای نیمهنظارتشده به عنوان محققانی که تشخیص دادند نظارت جزئی میتواند انفجار ترکیبی قواعد کاندید را کاهش دهد و در عین حال سهم آماری دادههای بدون برچسب را حفظ کند، پدیدار شدند. این رویکرد اکنون در بیوانفورماتیک، استخراج دادههای آموزشی و سیستمهای توصیهگر ظاهر میشود.
چه زمانی استفاده شود
هنگامی که مجموعه داده تراکنشی یا جدولی بزرگی دارید که تنها کسری از آن دارای برچسبهای کلاس یا حاشیهنویسی دامنه است و نیاز به کشف الگوهای همرخدادی دارید که واقعاً به یک مفهوم هدف مرتبط هستند نه صرفاً فراوان، از استخراج قواعد انجمنی نیمهنظارتشده استفاده کنید. این روش برای تحلیل سبد خرید با برخی نتایج خرید شناختهشده، استخراج سوابق پزشکی که تنها زیرمجموعهای از موارد دارای تشخیصهای تأیید شده هستند، و دستهبندی متن که در آن اسناد برچسبدار کمیاب هستند، مناسب است. از آن زمانی اجتناب کنید که بخش برچسبدار ناچیز باشد (کمتر از چند ده نمونه برچسبدار)، زمانی که نظارت کامل امکانپذیر است، یا زمانی که الزامات تفسیرپذیری به مدل سادهتری مانند رگرسیون لجستیک یا درخت تصمیم نیاز دارند.
محدودیتها و ملاحظات
- کیفیت قاعده به شدت به کیفیت و نمایندگی مجموعه بذرهای برچسبدار بستگی دارد؛ زیرمجموعه برچسبدار مغرضانه، سوگیری را به قواعد کشفشده منتقل میکند.
- ترکیب آستانههای پشتیبانی، اطمینان و محدودیت، فضای ابرپارامتر بزرگی ایجاد میکند که تنظیم آن بدون دادههای اعتبارسنجی برچسبدار دشوار است.
- هزینه محاسباتی با تعداد مجموعه اقلام کاندید مقیاس میشود؛ مجموعه دادههایی با فضاهای قلم بسیار پربعد، به استراتژیهای هرس تهاجمی نیاز دارند.
- حلقههای خودآموز میتوانند خطاهای اولیه را در صورت نویزدار بودن شبهبرچسبهای اولیه تقویت کنند و منجر به انحراف قاعده در طول تکرارها شوند.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- از دادههای بدون برچسب فراوان برای یافتن الگوهایی استفاده میکند که در دادههای برچسبدار به تنهایی از نظر آماری نامرئی خواهند بود.
- محدودیتهای مشتقشده از برچسبها، قواعد نامربوط را هرس میکنند و مجموعه قواعد کوچکتر و قابل اجراتری نسبت به استخراج صرفاً بدون نظارت ارائه میدهند.
- قواعد IF-THEN خوانا باقی میمانند و مزیت تفسیرپذیری استخراج کلاسیک قواعد انجمنی را حفظ میکنند.
- بهبود خودآموز میتواند به طور تکراری کیفیت قاعده و پوشش شبهبرچسب را بدون هزینه برچسبگذاری اضافی بهبود بخشد.
- انعطافپذیر: محدودیتها میتوانند دانش دامنه فراتر از برچسبهای کلاس ساده (مانند ترتیب زمانی، سلسله مراتب اقلام) را کدگذاری کنند.
کاربردها
- استخراج سوابق پزشکی که تنها زیرمجموعهای از سوابق بیمار دارای تشخیصهای تأیید شده هستند.
- تحلیل سبد خرید با هدایت زیرمجموعهای شناختهشده از نتایج خرید با ارزش بالا.
- استخراج دادههای آموزشی برای کشف الگوهای رفتار یادگیری مرتبط با مجموعه کوچکی از نتایج عملکرد دانشآموز برچسبدار.
- استخراج متن و دستهبندی اسناد با مجموعههای برچسبدار کمیاب.
- تشخیص نفوذ که در آن تنها کسری از رویدادهای شبکه حملات تأیید شده هستند.
- سیستمهای توصیهگر که از رتبهبندیهای پراکنده کاربر برای محدود کردن قواعد همرخدادی اقلام استفاده میکنند.
چگونه کار میکند
چگونه کار میکند
مجموعه داده به دو بخش تقسیم میشود: بخش کوچک برچسبدار (با برچسبهای کلاس شناختهشده یا محدودیتهای مشخصشده توسط کاربر) و بخش بزرگتر بدون برچسب. نمونههای برچسبدار به عنوان بذرهایی یا لنگرهایی عمل میکنند که فضای مفهوم هدف را تعریف میکنند، در حالی که تراکنشهای بدون برچسب، جرم آماری لازم برای محاسبه تعداد پشتیبانی قابل اعتماد را فراهم میکنند.
شمارش مجموعه اقلام فراوان با استفاده از الگوریتمهای کلاسیک مانند Apriori یا FP-Growth، بر روی هر دو داده برچسبدار و بدون برچسب اجرا میشود و پشتیبانی را به عنوان کسری از تراکنشهای حاوی یک مجموعه قلم معین محاسبه میکند. تنها مجموعههای قلمی که از آستانه پشتیبانی حداقل فراتر میروند، به عنوان کاندید برای تولید قاعده نگهداری میشوند.
فرمول
\text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \text{min\_sup}محدودیتهای مشتقشده از برچسب یا مشخصشده توسط کاربر برای هرس کردن فضای کاندید اعمال میشوند. محدودیتها میتوانند به شکل باید-مرتبط (دو قلم باید در نتیجه با یک کلاس هدف همرخداد باشند)، نباید-مرتبط (ترکیبات خاصی حذف میشوند) یا فیلترهای برچسب کلاس که کدام قواعد شامل یک نتیجه هدف هستند را محدود میکنند، باشند. این به طور چشمگیری تعداد قواعد جعلی یا تکراری را کاهش میدهد.
قواعد معتبر X مستلزم Y از مجموعههای قلم فراوان باقیمانده، فیلتر شده توسط آستانه اطمینان حداقل، تولید میشوند. اطمینان احتمال شرطی ظاهر شدن Y را با داشتن X اندازهگیری میکند. در یک محیط نیمهنظارتشده، قواعدی که نتیجه آنها با یک کلاس برچسبدار یا محدودیت همسو است، اولویتبندی یا وزن بیشتری میگیرند.
فرمول
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \text{min\_conf}قواعد کشفشده میتوانند به صورت تکراری برای تخصیص شبهبرچسب به تراکنشهای قبلاً بدون برچسب استفاده شوند، که سپس به دورهای استخراج بعدی بازگردانده میشوند. این حلقه خودآموز به تدریج مجموعه برچسبدار را غنی میکند و مجموعه قواعد را تیزتر میکند و زمانی که هیچ قاعده جدید با اطمینان بالا یافت نشد یا به حد تکرار از پیش تعیینشده رسید، همگرا میشود.
دامهای رایج
- تنظیم پشتیبانی حداقل خیلی پایین بدون محدودیت، نتیجه را با قواعد پیشپاافتاده فراوان اما غیرمفید پر میکند.
- نادیده گرفتن عدم تعادل کلاس در مجموعه بذرهای برچسبدار، که باعث میشود فیلتر محدودیت، کلاس اکثریت را در قواعد کشفشده بیش از حد نمایندگی کند.
- رفتار با اطمینان به عنوان تنها معیار جالب بودن و از دست دادن قواعد با بلندای (lift) یا قاطعیت (conviction) بالا که کاربردیتر هستند.
- نادیده گرفتن ارزیابی کیفیت پیشبینی قاعده در یک مجموعه جدا شده و پذیرش قواعد استخراجشده بدون اعتبارسنجی بر روی دادههای دیدهنشده.
- اشتباه گرفتن انجمن (همرخدادی) با علیت هنگام گزارش یافتهها.
پرسشهای متداول
این روش چه تفاوتی با استخراج قواعد انجمنی استاندارد دارد؟
استخراج قواعد انجمنی استاندارد کاملاً بدون نظارت است: تمام الگوهای همرخدادی را بالاتر از آستانه پشتیبانی و اطمینان پیدا میکند بدون اینکه مفهومی از کلاس هدف داشته باشد. قواعد انجمنی نیمهنظارتشده اطلاعات جزئی برچسب یا محدودیتهای دامنه را برای فیلتر کردن و اولویتبندی قواعد مرتبط با یک نتیجه خاص، ترکیب میکند و مجموعه نتایج کوچکتر و قابل اجراتری تولید میکند.
چه مقدار داده برچسبدار مورد نیاز است؟
حتی یک مجموعه برچسبدار کوچک میتواند محدودیتهای مفیدی را فراهم کند، اما کیفیت بذرها مهمتر از کمیت است. در عمل، داشتن حداقل چند ده نمونه برچسبدار برای هر کلاس برای جلوگیری از محدودیتهای به شدت مغرضانه توصیه میشود. اگر برچسبها بسیار پراکنده باشند، نتایج باید با دقت بر روی یک زیرمجموعه برچسبدار جدا شده اعتبارسنجی شوند.
چه آستانههایی را باید برای پشتیبانی و اطمینان تنظیم کنم؟
پاسخ جهانی وجود ندارد: آستانهها به اندازه مجموعه داده، دامنه و تعداد قواعدی که میتوانید واقعبینانه ارزیابی کنید بستگی دارند. با آستانههای متوسط شروع کنید (به عنوان مثال، پشتیبانی ۰.۰۵–۰.۱۰، اطمینان ۰.۶۰–۰.۸۰)، تعداد قواعد حاصل را بررسی کنید و تنظیم کنید. هنگامی که محدودیتها فعال هستند، اغلب میتوانید آستانههای پشتیبانی کمی پایینتر را تحمل کنید زیرا قواعد نامربوط توسط شرایط برچسب فیلتر میشوند.
آیا این روش میتواند ویژگیهای پیوسته یا عددی را مدیریت کند؟
استخراج قواعد انجمنی به طور ذاتی بر روی اقلام گسسته عمل میکند. ویژگیهای پیوسته باید قبل از استخراج به سطلها گسستهسازی شوند. انتخاب استراتژی سطلبندی بر کدام مجموعههای قلم فراوان میشوند تأثیر میگذارد، بنابراین ارزش دارد که با سطلبندی با عرض برابر، فرکانس برابر و سطلبندی مبتنی بر دامنه آزمایش کنید و حساسیت نتایج به انتخاب را بررسی کنید.
چگونه کیفیت قواعد کشفشده را ارزیابی کنم؟
فراتر از پشتیبانی و اطمینان، قواعد را با استفاده از بلندای (lift) (مقادیر بالاتر از ۱ نشاندهنده همرخدادی واقعی فراتر از شانس است)، قاطعیت (conviction) و اهرم (leverage) ارزیابی کنید. اگر قواعد برای پیشبینی استفاده میشوند، دقت طبقهبندی، F1 یا AUC را بر روی یک مجموعه برچسبدار جدا شده اندازهگیری کنید. معیارهای جالب بودن به تنهایی برای ارزیابی سودمندی عملی کافی نیستند.
روشهای مرتبط
منابع
Liu, B., Hsu, W., & Ma, Y. (2003). Integrating Classification and Association Rule Mining. In Proceedings of the 4th IEEE International Conference on Data Mining (ICDM), pp. 339–346.
باز کردن مرجع انتشارکپی شد.Association rule learning. Wikipedia.
باز کردن مرجع انتشارکپی شد.