الگوریتم انتخاب ویژگی کرم شب تاب (Firefly Algorithm)

انتخاب ویژگی یا Feature Selection

برای مساله انتخاب ویژگی، راه حل ها و الگوریتم های فراوانی ارائه شده است که بعضی از آن ها قدمت سی یا چهل ساله دارند. مشکل بعضی از الگوریتم ها در زمانی که ارائه شده بودند، بار محاسباتی زیاد آن ها بود، اگر چه امروزه با ظهور کامپیوترهای سریع و منابع ذخیره سازی بزرگ، این مشکل به چشم نمی آید ولی از طرف دیگر، مجموعه های دادهای بسیار بزرگ برای مسائل جدید باعث شده است که همچنان پیدا کردن یک الگوریتم سریع برای این کار مهم باشد. مساله انتخاب ویژگی به وسیله نویسندگان مختلف، از دیدگاه های متفاوتی مورد بررسی قرار گرفته است. هر نویسنده نیز با توجه به نوع کاربرد، تعریفی را از آن ارائه داده است. در ادامه چند مورد از این تعاریف را بیان میکنیم:
1- تعریف ایده آل: پیدا کردن یک زیرمجموعه با حداقل اندازه ممکن، برای ویژگی ها است، که برای هدف موردنظر اطلاعات لازم و کافی را در بر داشته باشد. بدیهی است که هدف تمام الگوریتم ها و روشهای انتخاب ویژگی، همین زیر مجموعه است.
2- تعریف کلاسیک: انتخاب یک زیرمجموعه M عنصری از میان N ویژگی، به طوریکه M < N باشد و مقدار یک تابع معیار (Criterion Function) برای زیرمجموعه موردنظر، نسبت به سایر زیرمجموعه های هماندازه دیگر بهینه باشد. این تعریفی است که Fukunaga و Narenda در سال 1111 ارائه داده اند.
3- افزایش دقت پیشگوئی : هدف انتخاب ویژگی این است که یک زیرمجموعه از ویژگی ها برای افزایش دقت پیشگوئی، انتخاب شوند. به عبارت دیگر کاهش اندازه ساختار بدون کاهش قابل ملاحظه در دقت پیشگوئی طبقه بندی کنندهای که با استفاده از ویژگی های داده شده بدست می آید، صورت گیرد.
4- تخمین توزیع کلاس اصلی: هدف از انتخاب ویژگی این است که یک زیرمجموعه کوچک از ویژگی ها انتخاب شوند، توزیع ویژگی هایی که انتخاب میشوند، بایستی تا حد امکان به توزیع کلاس اصلی با توجه به تمام مقادیر ویژگی های انتخاب شده نزدیک باشد.
روش های مختلف انتخاب ویژگی، تلاش میکنند تا از میان زیر مجموعه کاندید، بهترین زیرمجموعه را پیدا کنند. در تمام این روش ها براساس کاربرد و نوع تعریف، زیر مجموعه ای به عنوان جواب انتخاب میشود، که بتواند مقدار یک تابع ارزیابی را بهینه کند. با وجود این که هر روشی سعی می کند که بتواند، بهترین ویژگی ها را انتخاب کند، اما با توجه به وسعت جواب های ممکن، و این که این مجموعه های جواب به صورت توانی با N افزایش پیدا می کنند، پیدا کردن جواب بهینه مشکل و در Nهای متوسط و بزرگ بسیار پر هزینه است. به طور کلی روش های مختلف انتخاب ویژگی را براساس نوع جستجو به دسته های مختلفی تقسیم بندی می کنند. در بعضی روشها تمام فضای ممکن جستجو میگردد. در سایر روشها که میتواند مکاشفه ای و یا جستجوی تصادفی باشد، در ازای از دست دادن مقداری از کارایی، فضای جستجو کوچکتر میشود.

روش های مختلف انتخاب ویژگی

تکنیک های انتخاب ویژگی را می توان به دو شیوه دسته بندی کرد : در یک شیوه، روش های مختلف انتخاب ویژگی را براساس دو معیار تابع تولید کننده و تابع ارزیابی طبقه بندی میکنیم و براساس رویکرد دیگر تکنیک های انتخاب ویژگی را به سه دسته Filter ، Wrapper و embedded or hybrid تقسیم می کنیم.

روش فیلتر Filter برای انتخاب ویژگی:

ویژگی ها را براساس یک مرحله پیش پردازش که الگوریتم یادگیری را نادیده می گیرد انتخاب میکند. روش فیلتر براساس
ویژگی های ذاتی داده بنا شده است نه براساس دسته بند خاصی. ذات فیلترها برجستجوی ویژگی های وابسته و حذف غیر وابسته ها است. الگوریتم های فیلتر بر پایه چهار معیار ارزیابی مختلف به نام های “مسافت ،اطلاعات ،وابستگی و سازگاری” ارزیابی می شوند .به راحتی برای دیتاست های با ابعاد بالا به کار می روند. از نظر محاسباتی خیلی ساده و سریع هستند و مستقل از الگوریتم دسته بندی هستند . شیوه کار آنها به این طریق است که ابتدا ویژگی ها را به وسیله یک سری معیارها امتیازدهی می کند. سپس d تا از بهترین ویژگی ها را انتخاب می کند. سپس این مجموعه به عنوان ورودی به الگوریتم دسته بندی، داده می شود. به بیان دیگر به طور مستقل به تک تک ویژگی ها امتیازی داده می شود و سپس براساس آن امتیازات مرتب می شوند. این امتیازات می توانند نشان دهنده رابطه بین ویژگی و عنوان کلاس باشند. بدین منظور می توان از تست t یا تست فیشر استفاده کرد. مشکل رویکرد فیلتر آن است که رابطه درونی بین ویژگی ها درنظر گرفته نشده و ممکن است مجموعه انتخابی دارای تعداد زیادی ویژگی وابسته به هم باشد، درنتیجه هدف ما که کاهش ویژگی تا حد ممکن و حذف ویژگی های غیرضروری است را محقق نمی سازد.

انتخاب ویژگی به روش Wrapper:

این رویکرد مجموعه ویژگی را براساس دسته بندی کننده، انتخاب می کند و این مجموعه را با استفاده از دقت پیش بینی یا میزان خوب بودن خوشه ها امتیازدهی می کند یعنی کلاس بندی را یک جعبه سیاه محسوب می کند و زیر مجموعه ویژگی ها را براساس توان پیش بینی آن ها رتبه بندی می کند. این متد از بعضی استراتژی های جستجو مثل SFS و SBS استفاده می کند. این روش ها به روش های ترتیبی منسوب هستند. در این رویکرد، تمامی زیرمجموعه های ممکن از ویژگی ها درنظر گرفته می شود و با ارزیابی همه حالت ها بهترین آن ها که کمترین خطای عمومی را به همراه دارد انتخاب می شود. این متدها در انواع مسائل قادر به یافتن بهترین پاسخ می باشند. اگرچه ممکن است روش های wrapper نسبت به روش های فیلتر نتایج بهتری را تولید کنند ولی اجرای این روش ها پرهزینه است و در بعضی مواقع که تعداد ویژگی ها زیاد باشد منجر به شکست می شوند. مشکل اصلی روش های بسته بندی پیچیدگی بسیار بالاست که منجر به کنترل ناپذیرشدن مسیر حل مسئله می شود.

روش Embedded برای انتخاب ویژگی:

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

الگوریتم انتخاب ویژگی کرم شب تاب (Firefly Algorithm)

الگوریتم انتخاب ویژگی کرم شتاب Firefly Algorithm Optimization، و یا به اختصار الگوریتم کرم شتاب Firefly Algorithm، از رفتارکرم شتاب های طبیعی که در مجموعه ها بزرگ در کنار هم زندگی می کنند الهام گرفته شده است و یکی از الگوریتم های بسیار کارآمد در حل مسائل انتخاب ویژگی ترکیبی است. الگوریتم های دیگری نیز بر اساس الگوریتم کرم شتاب ها ساخته شده اند که همگی سیستم های چند عاملی Multi Agent هستند و عامل ها کرم های شتاب های مصنوعی یا به اختصار کرم شتاب هایی هستند که مشابه با کرم های شتاب واقعی رفتار می کنند. الگوریتم کرم شتاب ، یک مثال بارز از هوش جمعی هستند که در آن عامل هایی که قابلیت چندان بالایی ندارند، در کنار هم و با همکاری یکدیگر می توانند نتایج بسیار خوبی به دست بیاورند.

این الگوریتم برای حل و بررسی محدوده وسیعی از مسائل انتخاب ویژگی به کار برده شده است. از این میان می توان به حل مسأله کلاسیک فروشنده دوره گرد و همچنین مسأله راهیابی در شبکه های مخابرات راه دور اشاره نمود. مساله فروشنده دوره گرد (Traveling Salesman Problem) و یا به اختصار TSP، یکی از مسائل مشهور بهینه سازی ترکیبی است. در این مسأله، یک فروشنده دوره گرد می خواهد به چند شهر سفر کند و کالای خود را به فروش برساند. اما می بایست از تمام شهرها عبور کند، از هر شهر فقط یک بار عبور کند و با طی کوتاه ترین مسیر، سفر خود را به پایان برساند.

رفتار کرم‌های شب تاب

یکی از صحنه‌های جذاب و زیبایی که گردشگران و ساکنین مناطق استوایی یا معتدل، در آسمان شب‌های فصل تابستان، با آن موجه می‌شوند، «نور چشمک‌زن» (Flashing Light) کرم‌های شب تاب است. تا به امروز، چیزی حدود 2 هزار گونه متفاوت از کرم‌های شب تاب در دنیا به ثبت رسیده است و بیشتر آن‌ها، نورهای چشمک‌زن «متناوب» (Rhythmic) و کوتاهی را تولید می‌کنند. معمولا، هر یک از گونه‌های کرم شب تاب، الگوهای نور چشمک‌زن یکتا و منحصر به فردی تولید می‌کنند.

نور چشمک‌زنی که توسط کرم‌های شب تاب ساطع می‌شود، در نتیجه فرایند زیستی به نام «لومینسانس زیستی یا فسفر افکنی» (Bioluminescence) ایجاد می‌شود که سبب ایجاد پدیده شب تابی در کرم‌های شب تاب می‌شود. تاکنون، بحث‌ها و مطالعات زیادی در مورد کارکرد این نورهای چشمک‌زن انجام شده است ولی دانشمندان نتوانستند به نظریه واحدی در رابطه با کارکرد واقعی آن‌ها دست پیدا کنند. با این حال، دو کارکرد بنیادی فرایند لومینسانس زیستی و شب تابی حاصل از آن، عبارتند از:

1- جذب کردن جنس مخالف برای جفت‌گیری و آمیزش (کارکرد ارتباطی (Communication) فرایند لومینسانس زیستی)
2- جذب کردن طعمه‌های محتمل به سمت خود
علاوه بر این، محققان دریافته‌اند که کرم‌های شب تاب از نورهای چشمک‌زن به عنوان یک مکانیزم محافظتی جهت ارسال هشدار به دیگر کرم‌های شب تاب موجود در محیط استفاده می‌کنند. ریتم یا تناوب نور چشمک‌زن، نرخ چشمک زدن نور و مدت زمان چشمک زدن نور توسط کرم‌های شب تاب، بخش‌های مختلف سیستم ارتباطی میان کرم‌ها ( جهت جفت‌گیری با جنس مخالف یا هشدار به کرم‌های شب تاب موجود در محیط در مورد خطرات محتمل) را شکل می‌دهد.

به عنوان نمونه، در هنگام جفت‌گیری کرم‌های شب تاب، کرم ماده (از یک گونه خاص) به الگوی چشمک زن منحصر به فرد کرم‌های مذکر (از همان گون خاص) واکنش نشان می‌دهد. همچنین، در برخی از گونه‌های کرم شب تاب نظیر «فوتوریس» (Photuris)، کرم ماده این قابلیت را دارد که الگوی چشمک زن منحصر به فرد دیگر گونه‌ها (جهت جفت‌گیری) را تقلید کند. با چنین کاری، کرم شب تاب ماده می‌تواند کرم‌های مذکر گونه‌های دیگر را، که برای جفت‌گیری به سمت کرم ماده حرکت کرده‌اند، به دام بیاندازد و بخورد.

ترکیب این دو عامل مهم سبب می‌شود تا کرم‌های شب تاب، تنها از فاصله مشخصی قابل مشاهده باشند؛ معمولا، در تاریکی شب، نور چشمک‌زن کرم‌های شب‌تاب از فاصله چند صد متری قابل رؤیت است که برای مشاهده شدن توسط دیگر کرم‌ها و برقراری ارتباط با آن‌ها کفایت می‌کند.

نور چشمک‌زن تولید شده توسط کرم‌های شب تاب را می‌توان به گونه‌ای فرمول‌بندی (Formulate) کرد که متناظر با «تابع هدفی» (Objective Function) باشد که قرار است توسط الگوریتم‌های بهینه‌سازی بهینه شوند؛ چنین کاری به محققان اجازه می‌دهد تا بتوانند الگوریتم‌های بهینه‌سازی جدید را فرمول‌بندی و پیاده‌سازی کنند. در ادامه این مطلب، ابتدا مفاهیم مقدماتی و نحوه فرمول‌بندی کردن الگوریتم کرم شب تاب مورد بررسی قرار می‌گیرد.

1723 بازدید