انتخاب ورودی و ویژگی توسط الگوریتم رقابت استعماری

سوال مطرح شده: سوال دریافتی از طریق بخش تماس با ما در سایت: “آیا با استفاده از الگوریتم رقابت استعماری می شود دیسکریپتور (Descriptor) انتخاب کرد؟ (دسکریپتر‌های برنامه SPSS). من قبلاً به روش استپوایز (Stepwize) اینکار رو در برنامه SPSS انجام میدادم. حالا می‌خواهم بدونم که آیا با الگوریتم ICA هم می‌شه این کارو کرد؟”

جواب: بله می شود.

در حقیقت انتخاب دیسکریپتور و به طور کلی انتخاب ورودی های موثر در خروجی یک سیستم (یا همان انتخاب ویژگی ها در مسائل طبقه بندی {1}) یک مسئله بهینه سازی گسسته می باشد که بسته به تعداد کاندیداهای موجود برای انتخاب و نیز تعداد انتخاب های مورد نیاز می تواند مسئله بسیار پیچیده ای باشد. البته پیچیدگی ارتباط میان ورودی و خروجی سیستم نیز در پیچیدگی این مسئله تاثیر دارد. در حالتی که ما می خواهیم تعداد کمی از ورودی ها یا همان دیسکریپتورها را انتخاب کنیم، این مسئله می تواند با یک جستجوی جامع انجام شود. فرض کنیم که 70 مورد دیسکریپتور داریم و می خواهیم از میان آنها n موردی را که بیشترین اثر را در روی خروجی سیتم دارند انتخاب کنیم. همیشه معیاری برای این انتخاب وجود دارد. مثلاً در مسائل طبقه بندی (Classification) در حوزه بازشناسی الگو (Pattern Recognition) ، خطای طبقه بندی معیار انتخاب ما می باشد. در مسائل رگرسیون و تقریب تابع، این معیار می تواند میانگین مربعات خطای میان خروجی واقعی و خروجی حاصل از رابطه باشد. در هر صورت ما این معیار را داریم و می خواهیم بدانیم که با در نظر گرفتن این معیار چه دسته ای ورودی های خوب هستند!!؟

حال فرض کنید، ما بخواهیم یک دسته 3 تایی از آن 70 تا انتخاب ممکن را داشته باشیم. تعداد انتخاب های ممکن تعداد انتخاب 3 از 70 است. یعنی:

70! / (3! * 67!) = 70*69*68 / 6 = 54,740

اگر فرض کنیم که هر 100 بار ارزیابی تابع معیار انتخاب ما یک ثانیه برای کامپیوتر طول بکشد، تقریباً 9 دقیقه طول می کشد که جواب مسئله (بهترین دسته سه تایی از ورودی ها) را پیدا کنیم. این امر امکان پذیر است.حال فرض کنید، ما بخواهیم یک دسته 8 تایی از آن 70 تا انتخاب ممکن را داشته باشیم. تعداد انتخاب های ممکن تعداد انتخاب 8 از 70 است. یعنی:

70! / (8! * 62!) = 9.4404e+009

یعنی تقریباً 9 میلیارد انتخاب ممکن وجود دارد. باز اگر فرض کنیم که هر 100 بار ارزیابی تابع معیار انتخاب ما یک ثانیه برای کامپیوتر طول بکشد، تقریباً یک هزار و نود و دو (1092) روز یعنی تقریباً 3 سال طول می کشد که جواب مسئله (بهترین دسته 8 تایی از ورودی ها) را پیدا کنیم. 3 سال برای این انتخاب زمان کمی به نظر نمی رسد. به سادگی می تواد حدس زد که انتخاب 9، 10 و حتی 20 ویژگی چقدر طول می کشد.

یکی از روشهای فایق آمدن بر این مشکل استفاده از انتخاب مستقیم (Forward Selection) و انتخاب معکوس (Backward Selection) است. اما مشکل این روش ها این است که جواب به دست آمده از آنها ممکن است بسیار با جواب اصلی مسئله تفاوت داشته باشد. یک جایگزین مناسب برای الگوریتم های فوق می تواند الگوریتم های بهینه سازی تکاملی و در کنار آنها الگوریتم رقابت استعماری باشد. البته نسخه اولیه الگوریتم که برای مسائل بهینه سازی پیوسته می باشد، باید تغییراتی پیدا کند تا برای حل این مسئله گسسته مناسب شود.

شکل زیر انتخاب 8 ویژگی با الگوریتم رقابت استعماری را نشان می دهد. روش انتخاب مستقیم، به میزان خطای 0.0167 در زمان حدود 10 دقیقه رسیده است. در مقابل الگوریتم رقابت استعماری در حدود 30 دقیقه (نه سه سال!!) توانسته دسته از ورودی ها را پیدا کند که به خطای صفر می رسند!

 

_____________________________________________

نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.

صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.