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

به نام خدا

مقدمه

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

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

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

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

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

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

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

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

 

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

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

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

  

  مروری بر الگوریتم استخراج قوانین ممتیکی

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

فاز آموزش

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

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

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

فاز آزمایش

مجموعه قوانینی که در مرحله آموزش بیشترین برازندگی را داشته‌اند بر روی مجموعه داده آزمون به کار گرفته می‌شوند.

جستجوی محلی

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

الگوریتم جستجوی محلی میکرو ژنتیکی μGA

چارچوب μGA  شبیه به فرایند تکاملی معمول است؛ اگرچه هدفش متفاوت است. هدف الگوریتم تکاملی سرتاسری بهینه‌سازی ساختار مجموعه قوانین و تبادل قوانین خوب مابین مجموعه قوانین با استفاده از عملیات ضربدری و جهش ساختاری است. در الگوریتم جستجوی محلی میکرو ژنتیک ساختار مجموعه قوانین در طی فرایند تکامل بدون تغییر باقی می‌ماند درحالی‌که پارامترهای قوانین جابه‌جا (تعویض) و جهش می‌یابند. بدین‌وسیله مقادیر پارامترها بهینه می‌شوند تا مناسب ساختار مجموعه قوانین باشند. 

 

میکرو-جهش 

به‌وسیله عملگر جهش الگوریتم قادر خواهد بود نواحی جدیدی از فضای حل مسئله را جستجو کند؛ و این امکان را دارد که راه‌حل بهتری را کشف کند. احتمال اینکه یک آلل جهش یابد برحسب احتمال p_mm  است. احتمال جهش برحسب نسل/تکرار است.

مجموعه قوانین تولیدشده

مجموعه قوانین تولیدشده دارای ویژگی‌های زیر هستند:

1)مجموعه قوانین جمعیت والدین دارای طول‌های مختلفی هستند و از تعداد متفاوتی از ویژگی‌ها با توجه به عملگر ماسک استفاده می‌کنند.

2) هر یک از افراد مجموعه قوانین یک کلاس را پیش‌بینی می‌کند و آن‌ها بر روی‌هم کل قوانین مجموعه را تشکیل می‌دهند.

یعنی هر مجموعه قانون به‌عنوان یک والد تمامی کلاس‌های ممکن را پیش‌بینی می‌کند(تنها زمانی یک دسته قانون معتبر است که تمامی کلاس‌ها را پیش‌بینی کند).

3) مشاهدات نشان می‌دهد که تمام ویژگی‌های ورودی برای تصمیم‌گیری موردنیاز نیستند و اغلب زیرمجموعه‌ای از آن‌ها کفایت می‌کند. گنجاندن تمامی ویژگی‌ها حتی ممکن است عملکرد الگوریتم را بدتر کند زیرا برخی از ویژگی‌ها مخرب هستند و ممکن است با تصمیم‌گیری بر اساس ویژگی‌های دیگر تداخل پیدا کنند تعداد ویژگی‌های زیاد برای دسته‌بندی خوب لازم نیست.

خلاصه‌سازی

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

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

هدف اصلی الگوریتم پیشنهادی این است که با ترکیب دو نوع الگوریتم جستجوی محلی در الگوریتم تکاملی سرتاسری بهره‌برداری از نواحی کشف‌شده توسط این الگوریتم بهبود یابد. به همین دلیل از دو زیر الگوریتم  μGA  و AIS در قالب الگوریتم جستجوی محلی برای بهبود عملیات اکتشاف استفاده‌شده است.

درنهایت برای گزارش مؤثر بودن الگوریتم پیشنهادی از سه مجموعه داده از مخزن داده USI استفاده‌شده که از مجموعه دیتا ست‌های معروف پزشکی این مخزن داده هستند.

J.H. Ang, K.C. Tan, A.A. Mamun, An evolutionary memetic algorithm for rule extraction, Expert Systems with Applications 37 (2010) 1302–1315,2010.

 

دانلود اصل مقاله الگوریتم ممتیکی تکاملی برای استخراج قانون