بخشی از مقاله
مروری بر الگوریتم های تکاملی برای حل مسأله انتخاب ویژگی
چکیده - با توجه به سرعت جمع آوری داده مساله انتخاب ویژگی تبدیل به یکی از مسائل پراهمیت شده است. در این مقاله انواع روش های انتخاب ویژگی اعم از روش های پایه فیلتر و بسته بندی مورد بررسی قرار گرفته است. طی چند سال اخیر از الگوریتم های تکاملی نیز برای حل مساله انتخاب ویژگی استفاده شده که مورد بررسی قرار میگیرند. در این مقاله هفت نمونه از الگوریتم های تکاملی برجسته برای مساله انتخاب ویژگی بررسی شده است که نتایج نشان می دهد که هیچ کدام از الگوریتم ها ی تکاملی به تنهایی برای حل تمامی مسائل کامل و دارای سرعت بالا نیستند. و با توجه به دیتاست و پروژه مورد نظر باید از الگوریتم تکاملی خاصی استفاده نمود.
کلید واژه- انتخاب ویژگی، الگوریتم های تکاملی، طبقه بندی، فرا ابتکاری،کاهش بعد ویژگی
-1 مقدمه
با توجه به پیشــرفت ســریع کامپیوتر و تکنولوژی در زمینه پایگاه داده، ســرعت جمع آوری داده بســیار بیشــتر از ســرعت پردازش اطلاعات است. به دلیل افزایش متغیرهای مربوط به یک مشـاهده نیاز به پیش پردازش قبل از پردازش داده بسیار اهمیت پیدا کرده است. انتخاب ویژگی از مهم ترین روش ها و تکنیک ها جهـت پیش پردازش داده برای کاوش داده اســـت. به دلیل ارائه برنـامه های جدید برای مقادیر زیاد داده مثل: داده کاوی، بازیابی اطلاعات چندرســانه ای، پردازش داده های پزشــکی که نیازمند پردازش حجم وســـیعی از داده ها میباشـــد محدود کردن تعداد ویژگی اهمیت پیدا کرده اسـت. انتخاب ویژگی فرآیندی است که زیرمجموعه ای از ویژگی ها را براســاس معیارهای بهینه ســازی انتخاب میکند. روش های آماری ســنتی به دو دلیل کارایی خود را ازدسـت داده اند، یکی افزایش تعداد مشاهده و دیگری افزایش تعداد ویژگی های مربوط به یک مشاهده است. روش های انتخاب ویژگی روشـــی برای کـاهش زمان محاســـبه، بهبود پیش بینی عملکرد و فهم بهتر داده هـا در یـادگیری ماشـــین و برنامه های
تشــخیص الگو میباشــد. تکنیک های متعددی برای حذف ویژگی های بی ربط و زائدی که باری به دوش وظایف هسـتند ارائه شده است. تعریف ایده آل برای حل مساله انتخاب ویژگی این است که زیرمجموعـه ای بـا حـداقـل ویژگی پیـداکنیم به طوری که برای هدف مورد نظر اطلاعات لازم و کافی را داشته باشد.
فرایند انتخاب ویژگی شــامل ســه گام اســاســی اســت: روش جســتجو ، ارزیابی زیرمجموعه و یک معیار توقف( H. Liu & Yu, (2005 شکل فرایند انتخاب ویژگی در زیر نشان داده شده است.
برای مســـاله انتخاب ویژگی روش های متعددی ارائه شـــده اســت و از الگوریتم های تکاملی هم برای مســاله انتخاب ویژگی اســتفاده شــده اســت. در این مقاله بعد از مقدمه ابتدا روش های پایه ای انتخاب ویژگی را معرفی کرده و ســـپس در بخش بعدی الگوریتم های تکاملی مورد اسـتفاده در انتخاب ویژگی را براساس سال ارائه بررسی میکنیم.
عططگهشهگعن
-2 بررسی روش های انتخاب ویژگی
-1-2روش فیلتر
این روش از تکنیک رتبه بندی ویژگی ها به همراه یک معیار برای دسـته بندی ویژگی ها استفاده میکند. برای هر ویژگی یک رتبه یا امتیاز محاسـبه شده و سپس براساس این رتبه ویژگی ها دسـته بندی میشوند و ویژگی های با امتیاز کمتر حذف میشوند. در این روش از یک آســتانه برای رتبه بندی ویژگی ها اســتفاده میشـــود. دو روش رتبه بندی وجود دارد که عبارتند از: اطلاعات متقابل1 و معیار ارتباط.2
الگوریتم : focus یک جســتجوی کامل برای تســت همه ی زیرمجموعه های ویژگی انجام میشــود. ســپس زیرمجموعه ای با مینیمم تعـداد ویژگی را مشـــخص میکنـد میتوانـد نمونـه های مجموعه آموزشی را با دقت بالا دسته بندی کند.
الگوریتم : relief با اســتفاده از یک آســتانه یک مجموعه از ویژگی ها انتخاب میشــود. اشــکال این الگوریتم انتخاب آســتانه اســت. در این روش به هر ویژگی بر اســاس مرتبط بودن با هدف یک وزن نسـبت داده میشود و نمونه ها به صورت تصادفی کشف و ویژگی های مرتبط انتخاب میشوند.
مزیت: روشــن بودن محاســبات، جلوگیری از پیش برازش، و مناسب برای دیتاست های خاص.
عیب: زیرمجموعه مطلوبی که ممکن اســـت انتخاب نشـــده باشد از یک زیرمجموعه حذف شده بدست آید.
بعضـــی از روش هـای رتبـه بنـدی مثل معیار همبســـتگی
پیرســون (Pearson correlation criteria) و MI تبعیضــی بین
ارتباط بین متغیرهای یک عبارت با دیگر متغیرها نمیشود. طرز کار روش فیلتر در شکل زیر نشان داده شده است.
-2-2روش wrapper
از یک تابع دسـته بندی برای ارزیابی شایستگی زیرمجموعه های ویژگی اسـتفاده میشود. زیرمجموعه ها توسط یک الگوریتم جستجو کشف میشوند.
:Branch and Bound method ازیک ســاختار درختی برای ارزیابی زیرمجموعه های مختلف اســتفاده می کند. اما رشــد تابع برای تعداد زیادی ویژگی نمایی میشود.
: Exhaustive search methods در دیتـاســـت هـای بزرگ
محاســـبات را فشـــرده تر میکند. الگوریتم های ســـاده ای مثل جستجوی ترتیبی یا الگوریتم های اکتشافی مثل الگوریتم ژنتیک و الگوریتم ازدحام ذرات میتوانند نتایج خوبی ارائه کنند.
الگوریتم های انتخاب ترتیبی3عبارتند از:
:4SFS Algorithm با یک مجموعه خالی شـروع میکند و یک ویژگی که بیشترین مقدار تابع هدف را دارد را اضافه میکند.
:5 SBS Algorithm با یک مجموعه کامل از متغیرها شــروع میکند و ویژگی هایی را حذف میکند که در کاهش عملکرد پیش بینی ضعیف ترین هستند.
:6 SFFS Algorithm مـانند SFS در گام اول یک ویژگی را اضافه میکند وگام دیگری اضافه کرده و یک ویژگی از زیرمجموعه را حذف کرده و مجموعه جدید را ارزیابی میکند.
: ASFFS Algorithm7 اســـتفاده از یک پارامتر r که تعداد ویژگی های اضافه شده را مشخص میکند.
: Plus-L-Minus-r search method در هر سـیکل l متغییر
اضـافه شده و r متغییر حذف میشود تا زیر مجموعه مورد نظر به دست آید.
شکل زیر طرز کار روش بسته بندی را نشان می دهد.
تفاوت دو روش فیلتر و بسته بندی:
روش هـای فیلتر شـــامل یک محاســـبه ی غیر تکراری در دیتـابیس اســـت. چون روش بســـته بندی میتواند خودش را با الگوریتم یادگیری ماشــین اســتفاده شــده تطبیق دهد پس باید نتایج آن از فیلتر بهتر باشــد اما هزینه های محاســباتی این روش بالا است.
-3 مرور الگوریتم های تکاملی مورد استفاده در انتخاب ویژگی
-1-3 الگوریتم کلونی مورچه
علی رغم کور و کم هوش بودن، یکی از توانایی های مورچه ها در پیداکردن کوتاه ترین مسیر است. مورچه ها براساس ماده شیمیایی به نام فرومون که از خود برجای میگذارند با هم ارتباط برقرار میکنند. وقتی که مورچه ای از یک منبع غذایی به سمت لانه حرکت میکند و یا برعکس، از خود فرومونی ترشح میکند
که دنباله ی این فرومون در مسیر سبب میشود مورچه های دیگر با استشمام مسیری که بوی فرمون بیشتری میدهد مسیر بهینه را با احتمال بیشتری پیدا کنند. در مرجع
(T.Hiroyasu,et al.,2000) روشی به نام TACO برای حل
مسائل فضای گسسته و پیوسته ارائه شد. در این روش دو رشته از صفر و یک ها داریم که مورچه ها از بین آنها گذشته و مسیری شامل صفر و یک میسازند. مورچه ها در این فضا با توجه به هزینه مسیر ردپایی از خود برجای میگذارند. این مسیر که یک راه حل پیشنهادی است توسط یک تابع هزینه ارزیابی میشود.
-1-1-3پیاده سازی انتخاب ویژگی با الگوریتم کلونی مورچه
در سال 2007 از این الگوریتم برای حل مساله انتخاب ویژگی استفاده شده است. برای پیاده سازی مساله انتخاب ویژگی با الگوریتم کلونی مورچه دو رشته صفر و یک به طول تعداد متغیرها در نظر میگیریم و الگوریتم را برای تشکیل رشته ای از صفر و یک ها اجرا میکنیم. رشته ی بدست آمده توسط هر مورچه را رمز گذاری میکنیم که مقدار یک به معنی انتخاب ویژگی و مقدار صفر به معنی عدم انتخاب ویژگی میباشد.
برای ارزیابی روش پیشنهادی، این روش در حل دو مسأله انتخاب ویژگی طبقه بندی معنایی تصویر و بازشناسی ارقام دستنویس فارسی آزموده شده است. روش پیشنهادی برای بهبود الگوریتم روش 8 BACOنام دارد که در آن مقدار مینیمم
و ماکزیمم ردپای مورچه ها بین دو مقدار Tminو Tmax محدود شده و به مورچه ای که بهترین تور را پشت سرگذاشته اجازه میدهد ردپا از خود به جا بگذارد. پس از آزمایش و مقایسه باروش های K-NN ،TACO ،MTACO کارایی این روش تائید
و موثرتر و کاراتر از دیگر روش هاست.
-2-3 الگوریتم ژنتیک
الگوریتم ژنتیک نوع خاصی از الگوریتم های تکاملی است که از تکنیک وراثت و جهش استفاده میکند. اولین بار در سال 1967 توسط جان هالند ابداع شد و با تلاش های گلدبرگ در سال 1989 مکان خویش را یافت. این الگوریتم به وسیله ی اصل داروین از انتخاب طبیعی و تکثیر ژنتیکی الهام گرفته است. این الگوریتم مجموعه ای از راه حل ها که افراد یا کروموزوم نامیده میشوند در یک جمعیت را حفظ میکند و دارای یک مکانیسم انتخاب کروموزوم مناسب تر در هر نسل است. الگوریتم GA دارای دو هیوریستیک اصلی است که عبارتند از:
بقای بهترین ها: این هیوریستیک در عملگر انتخاب مهم است. کروموزومی که از همه قوی تر است فرصت بیشتری برای بقا و جفت گیری دارد.
جفت گیری: GA کور است و جلوی راهش را نمی بیند و تنها چیزی که نیاز دارد ارزیابی عملکردش است و اگر بتواند عملکردش را ارزیابی کند میتواند راهش را پیدا کند و همینطور GA مسأله را ساده کرده و رشته ای از کدها را به صورت باینری برای تصمیم گیری در نظر میگیرد.
-1-2-3پیاده سازی انتخاب ویژگی با الگوریتم ژنتیک
درسال 2007 فردی به نام De Stefano از الگوریتم ژنتیک برای حل مسأله انتخاب ویژگی استفاده کرد. در این روش جستجو با الگوریتم ژنتیک که در آن کدگذاری هر فرد انتخاب یک فضا است و برازندگی آن اندازه گیری جدایی پذیری کلاس در آن فضا است انجام میشود. این روش اجازه میدهد تا ویژگی هایی که منجر به افزایش تنوع در نمونه متعلق به همان کلاس
شوند بدون افزایش توانایی تمایز نمونه متعلق به کلاس های مختلف را دور بریزد. درهر آزمایش 15بار اجرا از GA با جمعیت های مختلف اولیه اجرا میشود. در هر اجرا بهترین فرد انتخاب میشود و در نهایت بهترین فرد بعد از 15 اجرا کشف و انتخاب میشود. نتایج آزمایشات بر روی دو پایگاه داده اثربخشی روش پیشنهادی را تائید میکند . در سال 2008 در مقاله ی cordella یک روش انتخاب ویژگی مبتنی برالگوریتم ژنتیک ارائه کرد که در آن زیرمجموعه ویژگی توسط افراد یک جامعه درحال تحول است. نتایج به دست آمده نشان می دهد که این رویکرد هم از نظر تعدد ویژگی های انتخاب شده و هم از نظر نرخ شناخت به دست آمده موثراست. درسال 2014 در مقاله Lu, Zhu, & Gu از الگوریتم ژنتیک با یک معیار تفکیک مبتنی بر ردیابی طراحی شد. با توجه به امتیازات تفکیک کلاس و تفکیک متغیر این معیار اهمیت زیرمجموعه ویژگی را مستقل از هر طبقه بندی خاص اندازه گیری میکند. در سال2010 در مقاله ای gheyas & smith الگوریتم ترکیبی SAGA را معرفی کرد که ترکیبی از نقاط قوت الگوریتم های موجود است. SAGA ترکیبی از روش های Wrapper مثل SA،GA،GRNN و یک الگوریتم جستجوی حریصانه است. این الگوریتم با الگوریتم های ACO،FW ،GA،
PSO،SA، SBS ،SFBS،SFFS،SFS مقایسه شده است. در
نتیجه نشان داده شده که هیچ یک از الگوریتم های موجود به تنهایی رضایت بخش نیست اما ترکیب آنها میتواند بر نقاط ضعف آنها بیفزاید. الگوریتم ژنتیک چهار تفاوت عمده با دیگر روش ها داردکه عبارتند از:
(1 الگوریتم های ژنتیک با متغیرهای تصمیم گیری کد شده استفاده میکنند نه باخود آنها.
(2 با یک مجموعه نقاط کارراشروع میکند نه با یک نقطه.
(3 الگوریتم زنتیک از انتقال تصادفی استفاده میکند نه از قوانین محاسباتی (4 الگوریتم ژنتیک فقط اطلاعات خروجی تابع برازندگی رابه
کارمیگیرد نه مشتقات ویا اطلاعات جانبی دیگر.
