مروری بر یادگیری قوانین

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

 

انواع قوانین یادگیری

کشف قانون توصیفی

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

کشف زیر گروه

یک زیر گروه را می‌توان به عنوان یک قانون IF-THEN مفهوم‌سازی کرد که مجموعه‌ای از متغیرهای مستقل را با یک متغیر هدف خاص مورد علاقه پیوند می‌دهد. شرط قانون، یا مقدم، به طور کلی شامل مجموعه‌ای از اصطلاحات بولی است که به عنوان ویژگی‌ها شناخته می‌شوند. هر ویژگی یک محدودیت را نشان می‌دهد که باید توسط یک مثال داده برآورده شود. هنگامی که تمام محدودیت‌های مشخص شده برآورده می‌شوند، قانون فعال می‌شود یا «آتش[1]» و مثال تحت پوشش قانون در نظر گرفته می‌شود. نتیجه‌گیری قانون، که به عنوان سر قانون یا نتیجه آن شناخته می‌شود، یک مقدار کلاس واحد را زمانی که قانون اجرا می‌شود، پیش‌بینی می‌کند. به طور معمول، در ساده‌ترین سناریوها، این شامل یک کلاس هدف باینری “c” است و هدف شناسایی یک یا چند قانون است که به طور موثر این کلاس را پیش‌بینی می‌کند. چندین کار وجود دارد که نزدیک به این موضوع هستند، جایی که سر قانون به یک ویژگی باینری منفرد محدود نمی‌شود.

تصور کنید مجموعه‌ای از نمونه‌های داده دارید که هر کدام دارای ویژگی‌های مختلفی مانند سن، درآمد یا سطح تحصیلات هستند. یک زیرگروه را می‌توان به عنوان گروه خاصی از این نمونه‌ها در نظر گرفت که ویژگی‌های خاصی دارند و ما این گروه را با استفاده از نوع خاصی از قانون IF-THEN تعریف می‌کنیم.

در اینجا نحوه عملکرد گام به گام آمده است:

۱) بخش IF (شرط قانون یا پیشین): این بخش از قانون شرایط یا ویژگی‌هایی را مشخص می‌کند که برای اینکه یک نمونه داده بخشی از زیرگروه در نظر گرفته شود باید درست باشد. این شرایط معمولاً ترکیبی از ویژگی‌ها و مقادیر آنها، مانند "سن بیشتر از 30 سال" یا "درآمد کمتر از 50000" است. گاهی اوقات این شرایط می‌توانند پیچیده‌تر باشند، که شامل مقادیر متعدد یا محدوده‌های مقادیر خاص می‌شود.

۲) بخش THEN (نتیجه‌گیری یا نتیجه قانون): این همان چیزی است که در مورد نمونه‌های داده‌ای که شرایط قسمت IF را برآورده می‌کنند به این نتیجه می‌رسیم. به طور معمول، در موارد ساده، پیش‌بینی می‌کند که این نمونه‌ها متعلق به یک کلاس خاص، مانند پیش‌بینی اینکه «فرد یک ماشین جدید می‌خرد» بر اساس ویژگی‌های آنها هستند.

۳) فعال‌سازی قانون: وقتی تمام شرایط مشخص‌شده در قسمت IF توسط یک مثال داده برآورده می‌شود، قانون "آتش" - به این معنی که اعمال می‌شود، و پیش‌بینی قسمت THEN برای آن مثال معتبر در نظر گرفته می‌شود.

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

کشف قانون انجمن

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

نان، کره ← شیر، پنیر

نشان می‌دهد که افرادی که نان و کره می‌خرند احتمالا شیر و پنیر نیز می‌خرند.

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

به عنوان مثال، اگر قاعده مذکور دارای پشتوانه 10 درصد و اطمینان 80 درصد باشد، به این معناست که 10 درصد کل معاملات شامل نان، کره، شیر و پنیر با هم است. همچنین در بین کسانی که نان و کره می‌خرند، 80 درصد شیر و پنیر نیز خریداری می‌کنند.

یادگیری قواعد پیش‌بینی

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

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

۱) شلیک قوانین چندگانه: شرایطی که چندین قانون در یک مثال اعمال می‌شود و پیش‌بینی‌های متناقضی را ارائه می‌دهند، معمولاً با اولویت‌بندی قوانین با پوشش بیشتر کلاس مربوطه در داده‌های آموزشی، که اغلب با اصلاح لاپلاس تنظیم می‌شوند، حل می‌شوند. این فرآیند ممکن است به طور موثر مجموعه قوانین را شبیه به یک لیست تصمیم‌گیری بر اساس اکتشافی مورد استفاده دوباره ترتیب دهد. روش‌های پیچیده‌تر برای حل چنین تضادهایی شامل استفاده از الگوریتم Naive Bayes یا پیاده‌سازی یک مجموعه قوانین جداگانه طراحی‌شده برای این سناریوها (القاء مضاعف) است.

۲) شلیک بدون قوانین: مواردی که هیچ قاعده‌ای برای مثال اعمال نمی‌شود، معمولاً با یک قانون پیش‌فرض مدیریت می‌شوند که کلاس اکثریت را پیش‌بینی می‌کند. تکنیک‌های پیشرفته‌تر، مانند آن‌هایی که در الگوریتم القای قانون نامرتب فازی[2] (FURIA) استفاده می‌شوند، تلاش می‌کنند تا یک قانون موجود را برای مطابقت با مثال تطبیق یا گسترش دهند.

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

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

دسته‌بندی بر اساس انجمن

یک مثال اولیه از دسته‌بندی انجمنی توسط الگوریتم یادگیری قانون دسته‌بندی بر اساس انجمن‌ها[3] (CBA) نشان داده شده است. این روش به طور کلی با استفاده از یک الگوریتم سنتی کشف قانون انجمن، مانند Apriori، برای شناسایی طیف گسترده‌ای از الگوها شروع می‌شود. از این مجموعه، فقط آن الگوهایی که دارای کلاس هدف در راس قانون هستند برای استفاده بیشتر در ایجاد مجموعه قوانین انتخاب می‌شوند. سپس الگوهای انتخاب شده بر اساس یک تابع اکتشافی سازماندهی می‌شوند و موثرترین الگوها در مجموعه قوانین ادغام می‌شوند.

چندین سیستم جانشین که به این چارچوب اصلی پایبند هستند توسعه یافته‌اند. با این حال، CBA و جانشینان فوری آن مانند دسته‌بندی بر اساس قوانین انجمن چندگانه[4] (CMAR) دارای محدودیت‌هایی، به ویژه با محدودیت آنها به ویژگی‌های اسمی هستند. وقتی یک مجموعه داده شامل ویژگی‌های عددی است، اینها باید گسسته شوند، اغلب با استفاده از اصل حداقل طول توصیف، فرآیندی که می‌تواند الگوریتم را در مقایسه با سایر مواردی که ذاتاً داده‌های عددی را در خود جای می‌دهند، محدود کند. برای پرداختن به این محدودیت، برخی از رویکردهای دسته‌بندی انجمنی، منطق فازی را برای گسترش دامنه انواع ویژگی‌هایی که می‌توان به طور موثر مدیریت کرد، ترکیب می‌کند.

الگوریتم پوشش

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

الگوریتم پوشش برای یافتن مجموعه قوانین

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

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

منبع

Fürnkranz, J. and Kliegr, T., 2015, July. A brief overview of rule learning. In International symposium on rules and rule markup languages for the semantic web (pp. 54–69). Cham: Springer International Publishing.

---

[1] Fire

[2] Fuzzy Unordered Rule Induction Algorithm

[3] Classification Based on Associations

[4] Classification based on Multiple Association Rules

[5] Separate-and-Conquer Method