مروری بر مقاله‌ای با عنوان "الگوریتم ممتیکی تکاملی برای استخراج قانون"

به نام خدا

مقدمه

در ادامه مروری بر مقاله‌ای با عنوان "الگوریتم ممتیکی تکاملی برای استخراج قانون" خواهیم داشت. 

 الگوریتم‌های ممتیکی تکاملی EMAs(Evolutionary Memetic Algorithm) بر روی طرح‌هایِ اضافه کردن جستجوی محلی، برای تکمیل قابلیت جستجوی سرتاسری الگوریتم‌های تکاملی EAs، تمرکز دارند.

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

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

در این مقاله دو الگوریتم جستجوی بهبود محلی به کارگرفته شده است؛ یکی از الگوریتم میکروژنتیک μGA استفاده می‌کند که منجر به بهبود کارایی و راهنمایی هدایت شده بر روی نسل‌ها می‌گردد؛ و دیگری AIS(Artificial Immune System) سیستم ایمنی مصنوعی، که به طور گسترده برای تجزیه و تحلیل داده‌ها در الگوریتم‌های یادگیری ماشین بدون ناظر استفاده شده است.

این مقاله بر روی یکی از مهمترین وظایف داده‌کاوی یعنی دسته‌بندی تمرکز دارد. ملاک ارزیابی الگوریتم‌های دسته‌بندی، دقت دسته‌بندی است. علاوه بر این، میزان پوشش قوانین نیز مهم است، یعنی کمترین قوانین قادر به دسته‌بندی بیشترین مقدار داده باشند.

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

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

 

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

چندین معیار ارزیابی مختلف برای سنجش عملکرد الگوریتم‌ها استفاده شده از جمله : دقت دسته‌بندی، حساسیت و خاص بودن؛ علاوه بر این‌ها در این مقاله، دو معیار ارزیابی که کمتر مورد توجه بوده‌اند نیز بررسی شده‌اند؛ قابلیت فهم(درک) (comprehensibility) و جذابیت(interestingness).

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