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


در این پروژه هدف انتخاب ویژگی با الگوریتم های متاهیورستیک است. در این پروژه عملیات انتخاب ویژگی با  الگوریتم های متاهیورستیک ازجمله  :

  • انتخاب ویژگی با الگوریتم ژنتیک (Genetic)
  • انتخاب ویژگی با الگوریتم ازدحام ذرات (pso)
  • انتخاب ویژگی با الگوریتم کلونی مورچه ها (aco)
  • انتخاب ویژگی با الگوریتم شبیه سازی تبرید (sa)

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


انتخاب ویژگی – 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 جستجو برای یک مجموعه ویژگی بهینه ، درون ساختار دسته بندی کننده قرار دارد. در این رویکرد کنترل انتخاب تعداد مناسب ویژگی مشکل است و معمولا با افزونگی ویژگی ها مواجه می شویم. در اینجا نیز ارتباط بین ویژگی ها نادیده گرفته شده است که باعث مشکلاتی در انتخاب نهایی ویژگی ها می شود.

الگوریتم ژنتیک-genetic  :

الگوريتمهاي ژنتيك از اصول انتخاب طبيعي داروين براي يافتن فرمول بهينه جهت پيش بيني يا تطبيق الگو استفاده ميكنند. الگوريتمهاي ژنتيك اغلب گزينه خوبي براي تكنيكهاي پيش بيني بر مبناي رگرسيون هستند.جذابيت زياد الگوريتمهاي ژنتيك اين است نتايج نهايي قابل ملاحظهتري دارند. فرمول نهايي براي كاربر قابل مشاهده خواهد بود و براي ارايه سطح اطمينان نتايج ميتوان تكنيكهاي آماري متعارف را بر روي اين فرمولها اعمال كرد. به اختصار گفته ميشود كه الگوريتم ژنتيك يك فن برنامهنويسي است كه از تكامل ژنتيكي به عنوان يك الگوي حل مساله استفاده ميكند. الگوريتم ژنتيك يك فن جستجو در علوم مهندسي براي يافتن راه حل بهينه ومسايل جستجو است.الگوريتم هاي ژنتيك يكي از انواع الگوريتمهاي تكاملي هستند؛ كه از علم زيست شناسي مثل وراثت 1، جهش 2، انتخاب ناگهاني، انتخاب طبيعي و تركيب الهام گرفته شده است.به طور معمول راهحلها به صورت اعداد دودويي نشان داده ميشوند، ولي روشهاي نمايش ديگري هم وجود دارد كه در ادامه اين فصل معرفي خواهند شد. تكامل از يك مجموعه به طور كامل تصادفي از موجوديتها شروع ميشود و در نسلهاي بعدي تكرار ميشود و در هر نسل ، مناسب ترين ها انتخاب ميشوند نه بهترينها. راهحلهاي هر مساله به وسيله يك ليست از پارامترها نشان داده ميشود كه به
آنها كروموزوم 3 يا ژنوم گفته ميشود. كروموزومها به طور معمول به صورت يك رشته 4 ساده از داده ها نمايش داده ميشوند، البته انواع ساختمان دادههاي ديگر هم مي توانند مورد ا ستفاده قرار بگيرند . الگوريتمهاي ژنتيك پس از طي چندين مرحله از توليد نسل در نهايت بايد بر اساس يك سري شرايط خاصي به اجراي خود خاتمه دهند.

شبيه ساز سرد كردن فلزات–SA- Simulated Annealing :

اين روش، فرآيند شبيه ساز سرد كردن فلزات، مواد را شبيه سازي مي كند. طي فرآيند شبيهساز سرد كردن فلزات ، يك ماده تا دمايي بيشتر از دماي ذوبش گرم مي شود و سپس به تدريج، دماي آن پايين آورده مي شود. نحوه ي كاهش دما بسيار كند و در حدي است كه ماده در تعادل ترموديناميكي است. به عبارت ديگر، دماي جسم آن قدر ثابت مي ماند كه بهترين ساختار بلوري با كم ترين انرژي در آن دما تشكيل شود . اجسامي كه ساختار بلوري شان در انرژي هاي بالاتري شكل گرفته باشد، شكننده تر نيز هستند . اما بر عكس، اگر ساختار بلوري جسمي، در انرژي هاي كم تر تشكيل شده باشد، از مقاومت فيزيكي بسيار بيشتري برخور دار خواهد بود. در الگوريتم شبيهساز سرد كردن فلزات، جواب هاي پيشنهادي براي مساله، در دماي بالاتر قرار دارند .و اغلب جواب هاي مناسبي نيستند. اين نامناسب بودن را مي توان به شكنندگي تشبيه نمود. سپس متغيري كه نقش دما را بر عهده دارد به مرور زمان كاهش داده مي شود تا به اين ترتيب جواب هاي بهتري در دماهاي پايين تشكيل شوند. الگوريتم، جواب هاي بعدي را با استفاده از جواب هاي فعلي به دست م يآورد. در اين الگوريتم، گرم كردن با اعمال تغييرات تصادفي بيشتر بر روي متغيرها مترادف است. در دماهاي بالاتر، متغيرها داراي تغييرات زيادتري هستند و هر چه دما پايي نتر م يآيد، دامنه تغييرات تصادفي متغيرها نيز، كم تر و كم تر م يشود. همواره تغييراتي كه منجر به بهتر شدن نتيجه شوند، پذيرفته مي شوند. اما تغييراتي كه منجر به بدتر شدن نتيجه شوند، با احتمالي پذيرفته مي شوند.

الگوریتم کلونی مورچه ها-(Ant Colony Algorithm)- ( aco)  :

در اين الگوریتم ارتباط حشره ها ميبايست محيط اطراف را به نحوي تغيير دهد كه ساير همنوعانش از تغيير محيط آگاه شوند و پيام مورد نظر حشره را دريافت كنند. يكي از بارزترين مثال ها براي چنين ارتباطي، ريزش ماد هاي شيميايي به نام فرومون1 به وسيله مورچه ها بر روي مسير حركت است. به اين نحو كه مورچه ها طي حركت، دنبال هاي از فرومون را ترسيم مي كنند و همواره مشتاق به دنبال كردن مسيرهايي هستند كه فرومون بيشتري را داشته باشند. تغيير محيط به منظور ايجاد تغييرات در رفتار از طريق ارتباط به وجود آمده، به نام اصل ا ستيگم رجي2 معروف است. اين اصطلاح براي اولين بار در سال 1959 و به وسيله زيست شناس فرانسوي به نام پيِرپ ول گراسه3 براي توضيح رفتار موريانه ها به كار برده شده است.  به اين ترتيب، استيگمرجي به معني اشاره (البته غير مستقيم) براي انجام كاري خواهد بود. استيگمرجي پاي هي اصلي بسياري از حركت هاي حشرات به خصوص مورچه هاست. در جوامع مورچه اي، يك مورچه ي خاص به نام ملكه وجود دارد كه فقط مسئوليت تخم گذاري را دارد. در مقابل، ساير مورچه ها عملكرد به طور كامل متفاوتي دارند. مورچه هاي يك مجموعه، خود-ترتيب6 هستند و رفتارهاي پيچيد هي كل مجموعه فقط ناشي از رفتارهاي ساده اي است كه تك تك مورچه ها به صورت خود-ترتيب انجام م يدهند. اين خواص جمعي و فردي به نحوي هستند كه بر روي مسايل مختلف كارآيي مناسبي دارند. به خصوص، هنگامي كه در يك باز هي زماني خاص، برخي از مورچه ها عملكرد مناسبي نداشته باشند، با اين وجود عملكرد كلي مجموعه  مناسب خواهد بود.عملكرد مورچ ههاي آرژانتيني  در يافتن كوتاه ترين مسير بين لانه و منبع غذايي، بسيار عجيب و حيرت انگيز است. مورچه ي آرژانتيني عملا كور است و به طبع كوتاه ترين مسير براي او مفهومي ندارد و به وسيله او قابل شناخت نم يباشد. اما با وجود چنين كمبودي، توده اي از اين مورچه ها مي توانند با همكاري يكديگر، كوتاه ترين مسير موجود بين لانه و محل مواد غذايي را پيدا كنند. الگوريتم بهينه سازي كُلوني مورچه ها، و يا به اختصار الگوريتم مورچه ها، از رفتار مورچه هاي طبيعي كه در مجموعه هاي بزرگ در كنار هم زندگي م يكنند الهام گرفته شده است. الگوريتم هاي ديگري نيز بر اساس الگوريتم مورچه ها ساخته شده اند كه همگي سامان ههاي چند عاملي1 هستند و عامل ها مورچه هاي مصنوعي يا به اختصار مورچه هايي هستند كه مشابه با مورچه هاي واقعي رفتار مي كنند الگوريتم مورچه ها، يك مثال بارز از هوش جمعي است كه در آن عامل هايي كه قابليت چندان  بالايي ندارند، در كنار هم و با همكاري يكديگر م يتوانند نتايج بسيار خوبي به دست بياورند. اين الگوريتم براي حل و بررسي محدوده ي وسيعي از مسايل بهينه سازي به كار برده شده است. از اين ميان مي توان به حل مساله كلاسيك فروشنده دوره گرد و همچنين مساله راهيابي در شبك ههاي مخابرات راه دور  اشاره نمود.

الگوریتم ازدحام ذرات- (Partial Swarm Optimization -pso) :

در الگوریتم pso تعدادي از موجودات وجود دارند، كه به آن ها ذره گفته ميشود و درفضاي جستجوي تابعي كه قصد كمينه كردن (و يا بهينه كردن) مقدار آن را داريم، پخش شده اند. هر ذره مقدار تابع هدف را در موقعيتي از فضا كه در آن قرار گرفته است، محاسبه مي كند. سپس با استفاده از تركيب اطلاعات محل فعل ياش و بهترين محلي كه در گذشته در آن بوده است و همچنين اطلاعات يك يا چند ذره از بهترين ذرات موجود در جمع، جهتي را براي حركت انتخاب مي كند. همه ي ذرات جهتي براي حركت انتخاب م يكنند و پس از انجام حركت، يك مرحله از الگوريتم به پايان مي رسد. اين مراحل چندين بار تكرار مي شوند تا آن كه جواب مورد نظر به دست بيايد. در واقع انبوه ذرات كه مقدار كمينه ي يك تابع را جستجو ميكنند، همانند دست هاي از پرندگان عمل مي كنند كه به دنبال غذا مي گردند.pso چیزی فراتر از يك مجموعه ي ذرات است. هيچكدام از ذرات قدرت حل هيچ مسالهاي PSO الگوريتم را ندارند، بلكه هنگامي مي توان به حل مساله اميدوار شد كه آن ها با همديگر ارتباط و تعامل داشته باشند. در واقع براي انبوه ذرات، حل مساله، يك مفهوم اجتماعي است كه از رفتار تك تك ذرات و تعامل ميان آن ها به وجود مي آيد.

*

مراحل خرید فایل دانلودی
اگر محصول را می پسندید لطفا آنرا به اشتراک بگذارید.

محصولات مرتبط

مجوز ارسال دیدگاه داده نشده است!

0