فیلم های آموزشی
ژنتیک و محاسبات تکاملی
فیلم های آموزشی
شبکه عصبی مصنوعی
فیلم های آموزشی
الگوریتم های فراابتکاری
آموزش الگوریتم TLBO آموزش شبکه عصبی مصنوعی آموزش الگوریتم کرم شب تاب
آموزش الگوریتم PSO آموزش شبکه عصبی گازی آموزش الگوریتم مورچگان
آموزش ترکیب ژنتیک و PSO آموزش شبکه عصبی رقابتی آموزش الگوریتم علف هرز
آموزش الگوریتم BBO آموزش شبکه عصبی MLP آموزش الگوریتم جهش قورباغه
آموزش الگوریتم فرهنگی آموزش شبکه عصبی RBF آموزش الگوریتم کرم شب تاب
آموزش انتخاب ویژگی آموزش شبکه عصبی LVQ آموزش الگوریتم زنبور ها
آموزش الگوریتم ژنتیک آموزش شبکه عصبی GMDH آموزش کلونی زنبور مصنوعی
الگوریتم رقابت استعماری شبکه عصبی با نروسولوشن آموزش الگوریتم ژنتیک

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

سوال مطرح شده: سوال دریافتی از طریق بخش تماس با ما در سایت: “آیا با استفاده از الگوریتم رقابت استعماری می شود دیسکریپتور (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 دقیقه (نه سه سال!!) توانسته دسته از ورودی ها را پیدا کند که به خطای صفر می رسند!

 

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

… میخواستم بدونم که چگونه از الگوریتم استعماری میتونم در زمینه انتخاب اسلاید های مناسب زمانی (در مسئله پیش بینی سری های زمانی) یا همان روزهای قبل که در قسمت پیش بینی مثلا مصرف برق یا هر سری زمانی (بحث انتخاب ویژگی) استفاده کنم …

پاسخ:

با سلام.

مسئله انتخاب ویژگی به صورت عمومی یک مسئله باینری می باشد. در این حالت به تعداد ویژگی های کاندیدای اولیه بردار به صورت صفرو  یک در نظر می گیرید. صفر یعنی بودن یک ویژگی و یک یعنی نبودن آن. حال بردار بهینه را می یابید با استفاده از یک معیار مثلاً بهترین خطای تست.

لینک زیر کمی توضیح در این مورد می دهد.
http://www.icasite.info/2010/05/blog-post.html

نسخه های گسسته و باینری این الگوریتم را نیز می توانید به راحتی پیدا و یا ایجاد (با تغییر در کدهای اولیه) نمایید.

فیلم زیر نیز شاید مفید باشد.
http://www.icasite.info/2010/11/feature-selection.html

لینک زیر طبقه بندی مسائل بهینه سازی را ارائه می کند (تا حدی پاسخ سوال دوم شما).
http://www.icasite.info/2010/05/blog-post_31.html

پاسخ زیر را نیز به یک سوال مطرح شده دیگر ببینید.
پرسش:

آیا می توان از آی سی ای برای انتخاب ویژگی استفاده نمود؟ قدم های لازم چه هستند؟

پاسخ:

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

—————————————————————————————————————————————-
{1} برای انتخاب ورودی و ویژگی و دیسکریپتور عناوین مشابه زیر نیز در حوزه های مختلف به کار میرود:

Feature Selection
Input Selection
Descriptor Selection

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



0 پاسخ

ارسال یک پاسخ

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *