۳-۷- روش بیشترین وابستگی و کمترین افزونگی (mRMR^[19])
در بسیاری از کاربرد‌های شناسایی آماری الگو، انتخاب زیرمجموعه‌ای از مجموعه ویژگی‌ها می‌تواند سبب کاهش خطای دقت طبقه‌بندی گردد. هدف روش بیشترین وابستگی و کمترین افزونگی، انتخاب زیرمجموعه از فضای ویژگی مبتنی بر مفهوم همبستگی و کاهش افزونگی اطلاعات می‌باشد. فرض کنید فضای داده ورودی D، شامل N نمونه و M ویژگی است و c نیز برچسب مربوط به هر گروه باشد. در این حالت، هدف انتخاب بهینه m ویژگی از فضای M بعدی است بطوریکه هر نمونه متعلق به گروه c باشد. از آنجاییکه تعداد زیرمجموعه‌های ممکن بوده و تعداد زیرمجمو ع‌هایی که ابعادشان کوچکتر از m باشد نیز می‌باشد جستجوی کامل زیرمجموعه‌های ویژگی بسیار دشوار است. از اینرو، روش‌های جستجوی ترتیبی مانند پیش رو ترتیبی و شناور پیش رو ترتیبی، برای جستجوی فضای کامل زیرمجموعه‌ها در فضای ویژگی پیشنهاد می‌شوند]۲۹[. شرط توصیف بهینه معادل با کمترین خطای دقت طبقه‌بندی درنظر گرفته می‌شود، بطوریکه در طبقه‌بندی بی سرپرست،‌کمترین خطا زمانی رخ می‌دهد که بیشترین وابستگی آماری دادگان در زیر فضای گروه هدف c پیدا شود. از این شیوه به عنوان شرط بیشترین وابستگی یاد می‌شود. یکی از روش‌های رایج برای بررسی مفهوم بیشترین وابستگی، روش بیشترین ارتباط است که مقصود آن بالاترین ارتباط هر ویژگی با گروه هدف c می‌باشد. بطور عام، ارتباط برحسب همبستگی و یا اطلاعات متقابل دو متغیر معرفی می‌شود. اطلاعات متقابل دو متغیر x و y، بر حسب توابع چگالی احتمال بصورت زیر تعریف می‌شود:

(۳-۶)
در انتخاب ویژگی بر اساس بیشترین ارتباط، بیشترین اطلاعات متقابل بین ویژگی‌های منتخب گروه هدف c صورت می‌گیرد که مبین بیشترین وابستگی ویژگی به هدف مربوط می‌باشد. در روش‌های جستجوی متوالی، m بهترین ویژگی انفرادی، یعنی آن‌هایی که بیشترین مقدار وابستگی را دارند به عنوان ویژگی‌های منتخب برگزیده می‌شوند. ولی همواره ترکیبی از بهترین ویژگی‌های منفرد به عنوان یک زیرمجموعه بهینه نیست، به عبارت دیگر m بهترین ویژگی همیشه بهترین m ویژگی نیستند. از اینرو، در کنار بیشترین همبستگی ویژگی‌ها با گروه هدف c، روش هایی جهت کاهش افزونگی وجود دارد که ویژگی هایی با کمترین افزونگی را برمی‌گزیند. لذا روش انتخاب ویژگی با معیار بیشترین وابستگی و کمترین افزونگی، یکی از روش‌هایی است که مبتنی بر سه اصل بیشترین وابستگی، بیشترین ارتباط و کمترین افزونگی بنا شده است. بر اساس اطلاعات متقابل بین دو نمونه، هدف از انتخاب ویژگی با بیشترین وابستگی به هدف گروه c، یافتن یک مجموعه ویژگی S با m عضو است که بطور مشترک بیشترین وابستگی را به هدف مربوطه داشته باشد. از دید ریاضی این مفهوم به شکل زیر بیان می‌شود]۳۱[:
(۳-۷)
هنگامی که m برابر ۱ باشد، مساله به یافتن ویژگی تبدیل می‌شود که را بیشینه کند و زمانی که m بزرگتر از ۱ باشد، یک روش جستجوی ترتیبی ساده می‌تواند افزودن یک متغیر در هر لحظه باشد. در حالتی که مجموعه شامل m-1 ویژگی دردست باشد، m امین ویژگی بصورت ویژگی‌ای که بیشترین افزایش را در ایجاد می‌کند، تعریف می‌شود:
(۳-۸)
از آنجایی‌که تخمین دقیق از توابع چگالی چند متغیره و بدلیل کافی نبودن تعداد نمونه‌ها و دشواری محاسبه ابعاد بالای ماتریس کوواریانس، مشکل است، بنابراین بجای استفاده از بیشترین وابستگی از معیار بیشترین ارتباط استفاده می‌کنیم. این معیار، را با بهره گرفتن از میانگین مقادیر اطلاعات متقابل میان ویژگی‌های انفرادی و گروه c تخمین می زند:
(۳-۹)
ویژگی‌هایی که براساس بیشترین ارتباط انتخاب می‌شوند دارای افزونگی بالایی هستند، یعنی وابستگی میان آن ها زیاد است. هنگامی که دو ویژگی به شدت به هم وابسته باشند، در صورت حذف یکی از آن‌ ها قدرت مجزاسازی مربوط به آن ها تغییر زیادی نخواهد کرد]۳۷[. بنابراین معیار کمترین افزونگی برای انتخاب ویژگی‌های مستقل بصورت زیر است:
(۳-۱۰)
برای ترکیب D و R از عملگر استفاده کرده و در ساده ترین حالت داریم:
(۳-۱۱)
(۳-۱۲)
در عمل از روش‌های جستجوی ترتیبی می توان به‌منظور انتخاب ویژگی‌های زیربهینه منتخب توسط عملگر استفاده کرد. اگر فرض شود که مجموعه ویژگی از مجموعه X انتخاب شده و هدف انتخاب ویژگی m ام باشد، آنگاه این ویژگی باید تابع را بیشینه کند:
(۳-۱۳)
۳-۸- الگوریتم فاخته COA^[20]
الگوریتم فاخته یکی از جدیدترین و قوی ترین روش‌های بهینه سازی تکاملی می باشد که تا کنون معرفی شده است. الگوریتم فاخته با الهام از روش زندگی پرنده‌ای به نام فاخته است که در سال ۲۰۰۹ توسط شین اویانگ ودب ساش، توسعه یافته است. این الگوریتم توسط پرواز levy به جای پیاده روی ایزوتروپیک تصادفی ساده توسعه یافته است. الگوریتم فاخته بعدها در سال ۲۰۱۱ توسط رامین رجبیون به طور کامل با جزئیات بیشتر مورد بررسی قرار گرفت]۳۰[.
اکثر پرندگان لانه‌های خود را به صورت جدا شده، نامعلوم و مستتر در پوشش گیاهی ایجاد می‌کنند تا از شناسایی توسط شکارچیان جلوگیری نمایند.در این میان برخی از پرندگان خود را از دردسر هر گونه لانه سازی و وظایف والدین رهانیده و به نوعی زیرکی جهت پرورش جوجه های خود متوسل شدند. این پرندگان هرگز برای خود لانه نمی‌سازند و به جای آن تخم‌های خود را در داخل لانه سایر انواع پرندگان قرار داده و صبر می‌کنند تا آنها در کنار تخم‌های خود به تخم‌های این پرندگان نیز رسیدگی نمایند.
فاخته مشهورترین پرنده‌ای می‌باشد که به نوعی یک متخصص در زمینه فریبکاری است. فاخته به جای ساختن لانه و تخم‌گذاری در لانه خود،لانه یک پرنده را انتخاب کرده و یکی از فاخته‌ها لانه های انواع پرنده ها را آلوده به تخم خود می‌کنند و این کار را با دقت و با تقلید از رنگ و الگوی تخم‌های موجود در هر لانه انجام می‌دهند تا تخم‌های جدید لانه شبیه تخم های تخم‌های پرنده میزبان را از بین می‌برد و تخم خود را لابه لای تخم‌های آن پرنده قرار می‌دهدو از آن محل دور می‌شود. با این عمل نگهداری تخم خود را به پرنده میزبان واگذار می‌کند.کل این فرایند به زحمت ۱۰ثانیه طول می‌کشد.‌ فاخته لانه های انواع پرندگان را برای این کار انتخاب می‌کند و این کار را با دقت و با توجه به رنگ و الگوی تخم‌های هر لانه انجام می‌دهد تا تخم‌های جدید شبیه تخم‌های قبلی لانه باشند. هر‌گروه‌ از فاخته‌ها،روی میزبان خاصی تخصص می‌یابند.ثابت شده که هر گروه متخصص از فاخته ها به صورت ژنتیکی با گروه دیگر اختلاف دارند.در این بین برخی پرندگان میزبان تخم‌های فاخته را در لانه خود تشخیص داده و تخم‌های فاخته را بیرون می‌اندازند و برخی لانه را ترک کرده و یک لانه جدید می‌سازند.فاخته‌ها تقلید خود را در لانه میزبان بهبود می‌بخشند و پرندگان میزبان هم روش شناسایی تخم‌های بیگانه را یاد می‌گیرند.این تلاش و مبارزه برای بقا بین پرندگان مختلف و فاخته ها مدام و پیوسته است.
جوجه‌های فاخته زودتر از تخمهای پرنده میزبان بیرون می‌آیند و زودتر هم رشد می‌کنند. در اکثر موارد جوجه‌ی فاخته تخم‌ها و یا جوجه‌های پرنده میزبان را از لانه بیرون می‌اندازند. این مساله کاملا غریزی می باشد.
۳-۸-۲- جزییات الگوریتم بهینه‌سازی فاخته
همانند سایر الگوریتم‌های تکاملی COA هم با جمعیت اولیه کار خود را شروع می‌کند و جمعیتی متشکل از فاخته‌ها. این جمعیت از فاخته‌ها تعدادی تخم دارند که آنها را در لانه تعدادی پرنده میزبان خواهند گذاشت. تعدادی از این تخم‌ها که شباهت بیشتری به تخم‌های پرنده میزبان دارند شانس بیشتری برای رشد و تبدیل شدن به فاخته بالغ را خواهند داشت. سایرتخم‌ها توسط پرنده میزبان شناسایی شده و از بین میروند. میزان تخم‌های رشد کرده، مفید بودن لانه را نشان میدهد. هر چه تخم‌های بیشتری در یک ناحیه قادر به زیست باشند و نجات یابند به همان اندازه سود (تمایل) بیشتری به آن منطقه اختصاص می‌یابد. بنابراین موقعیتی که در آن بیشترین تعداد تخم‌ها نجات یابند پارامتری خواهد بود که COA قصد بهینه سازی آن را دارد.
شروع
تعیین شعاع تخمگذاری برای هر فاخته
تعیین پارامترها و ورودی ها
تخم گذاری در لانه های مختلف
حرکت تمامی فاخته ها به سمت بهترین محل
مشخص نمودن جوامع فاخته ها
بعضی از تخم ها کشته یا از بین می روند
خیر
جمعیت از ماکزیموم مقدار کوجکتر است؟
بله
محاسبه سود (چک نمودن احتمال بقا هر تخم)
پرورش تخم ها
یافتن لانه ها با بهترین نوع زیست
از بین بردن فاخته ها در نواحی مختلف
شرط توقف برقرار است؟
بله
خیر
توقف
شکل ۳-۸ : فلوچارت الگوریتم بهینه سازی فاخته]۳۰[.
فاخخته‌ها برای نجات تعداد بیشتری از تخم‌های خود دنبال بهترین منطقه می‌گردند.پس از انکه جوجه ها از تخم درامدندو بالغ شدند جوامع و گروه‌هایی تشکیل می‌دهند.هر گروه محل سکونت خود را برای زندگی دارد.تمام گروه‌ها به سمت بهترین منطقه مهاجرت می‌کنند و هر گروه نزدیک بهترین منطقه ساکن می شوند.شعاع تخم‌گذاری فاخته در بهترین منطقه فعلی با توجه به در نظر گرفتن تعداد تخم‌هایی که هر فاخته می‌گذارد و فاصله فاخته‌ها از منطقه بهینه فعلی شکل می‌گیرد.سپس فاخته ها در لانه های مو جود در این شعاع تخم‌گذاری می‌کنند.این فرایند تا رسیدن به بهترین محل تخم‌گذاری ادامه می‌یابد.محل بهینه جایی است که بیشترین تعداد فاخته در آن مکان گرد می‌آیند.]۳۰[.
۳-۸-۲-۱- تولید محل‌های سکونت اولیه فاخته‌ها (جمعیت اولیه‌ی جواب‌های کاندید)
برای حل یک مساله بهینه‌سازی لازم است تا مقادیر متغیر‌های مساله به فرم یک آرایه شکل گیرند. دراین آرایه‌ها با نام‌های کروموزوم و موقعیت ذرات مشخص می‌شوند. ولی در الگوریتم بهینه‌سازی فاخته این آرایه habitat یا محل سکونت نام دارند.
در یک مساله بهینه‌سازی بعدی یک habitat آرایه ۱* خواهد بود که موقعیت فعلی زندگی فاخته‌ها را نشان می‌دهد. این آرایه به شکل زیر تعریف می‌شود:
(۳-۱۴)
میزان مناسب بودن (یا مقدار سود) در habitat فعلی با ارزیابی تابع سود )در habitat به دست می آید. بنابراین:
(۳-۱۵)
همانطور که دیده می شود COA الگوریتمی است که تابع سود را ماکزیمم می‌‌کند. برای استفاده از COA برای حل مسایل کمینه‌سازی کافی است یک علامت منفی در تابع هزینه ضرب کنیم. برای شروع الگوریتم بهینه‌سازی یک ماتریس habitat به سایز تولید می‌شود. سپس برای هر کدام از این habitatها تعدادی تصادفی تخم تخصیص می‌یابد. در طبیعت هر فاخته بین ۵ تا ۲۰ تخم می‌گذارد. این اعداد به عنوان حد بالا و پایین تخصیص تخم به هر فاخته در تکرار‌های مختلف استفاده می‌شود. دیگر عادت هر فاخته حقیقی این است که آن در یک دامنه مشخص تخم‌های خود را می‌گذارند که به آن حداکثر دامنه تخم‌گذاری (ELR) گفته می‌شود. در یک مساله بهینه‌سازی ‌هر متغیر دارای حد بالا و حد پایین است که هر ELRبا استفاده از این حدود قابل تعریف خواهد بود. ELR متناسب است با تعداد کل تخم‌ها، تعداد تخم‌های فعلی فاخته و همچنین حد بالا و پایین متغیر‌های مساله. بنابراین ELR به صورت رابطه زیر تعریف می‌شود:
(۳-۱۶)
آلفا متغیری است که حداکثر مقدار ELR تنظیم می‌شود.
۳-۸-۲-۲- روش فاخته‌ها برای تخم‌گذاری
هر فاخته به صورت تصادفی تخم‌هایی را در لانه پرندگان میزبان که در ELR خود قرار دارد می‌گذارد (شکل ۳-۸). وقتی تمام فاخته‌ها تخم‌های خود را گذاشتند برخی از تخم‌ها که شباهت کمتری به پرنده میزبان دارند شناسایی شده و از لانه بیرون انداخته می‌شود. بنابراین بعد از هر تخم‌گذاری p% از تمام تخم ها (معمولا ۱۰%)که مقدار تابع سود آنها کمتر است نابود می‌شوند. بقیه جوجه‌ها در لانه‌های میزبان تغذیه شده و رشد می‌کنند.