بخشی از مقاله
خلاصه
انتخاب ویژگی یک مرحله مهم در سیستم های تشخیص الگو است. انتخاب ویژگی، انتخاب زیرمجموعه بهینه از روی مجموعه ویژگی اصلی است، بگونه ای که این زیر مجموعه کمترین تعداد ویژگی و بیشترین صحت طبقه بندی را داشته باشد. ویژگی ها هزینه های محاسباتی، اقتصادی مربوط به خود را دارند. هدف از انتخاب ویژگی کاهش هزینه ها، حداقل کردن ابعاد فضای ویژگی، و بهبود صحت پیشگویانه است.
در این مقاله ما مجموعه ای از ویژگی ها را در اختیارگرفته ایم که این و یژگی ها بطور کلی سه نوع هستند: ویژگی های مفید ، ویژگی های غیر مفید، و ویژگی مضر. هدف از انتخاب ویژگی یافتن فقط ویژگی های مفید است، که نتیجه آن حداقل شدن ابعاد فضای ویژگی، کاهش هزینه های محاسباتی و اقتصادی، و بهبود صحت طبقه بندی است. اکثر روش های انتخاب ویژگی بر روی شبکه آموزش دیده شده انجام شده است. این روش ها در عین سادگی و سرعتی که دارند، روش های اطمینان بخشی نیستند. هدف ما در این مقاله انجام انتخاب ویژگی قبل از فرایند آموزش و با استفاده از الگوریتم های تکاملی است. برای انتخاب ویژگی از الگوریتم کلونی زنبورهای مصنوعی استفاده کرده ایم.
1. مقدمه
با توجه به اینکه ارزیابی زیر مجموعه های ویژگی اصولا زمانبر است الگوریتم های تکاملی برای دستیابی به جواب بهینه نیاز به جمعیت مناسب و تعداد تکرار مناسب دارند. یکی از مباحثی که در تشخیص الگو مطرح می شود انتخا ویژگی است. که در بسیاری از مسائل صنعتی، پزشکی، امنیتی و ... کاربرد فراوان دارد. در تشخیص الگو ما یک سری ویژگی داریم که براساس این ویژگی ها می خواهیم بهترین رابطه را بین ورودی ها با خروجی بدست آوریم. اما مشکلی که وجود دارد این است که معمولا تمام ویژگی های داده شده مفید و موثر نیستند. عموما در تشخیص الگو پس از مرحله استخراج ویژگی استفاده از یک الگوریتم انتخاب ویژگی برای یافتن ویژگی های موثر الزامی است.
هدف از انتخاب ویژگی، استخراج ویژگی های موثر و مفید و حذف ویژگی های بی اثر و یا حتی در بعضی مواقع مخرب، به منظور کاهش هزینه های عملیاتی و افزایش دقت می باشد. دو روش کلی برای انتخاب و یژگی وجود دارد: -1 روش های انتخاب ویژگی با روش ارزیابی زیر مجموعه مبتنی بر الگوریتم یادگیری- 2 روش های مستقل از الگوریتم یادگیری برای ارزیابی زیر مجموعه ویژگی. که روش دو عموما ساده تر و بسیار سریعتر هستند ولی روش های اول از حیث کیفیت پاسخ روش های بهتری هستند.
یکی از روش های ساده برای انتخاب ویژگی جستجوی کامل است که کلیه زیرمجموعه های ممکن را آنالیز می کند و هر کدام را جداگانه بررسی می کند و در نهایت بهترین زیر مجموعه را انتخاب می کند. این روش با اینکه روش دقیقی است و همیشه به بهینه کل می رسد. ولی در عمل غیر ممکن است. چون آنالیز 2N حالت مختلف حتی برای ابعاد ویژگی متوسط غیر ممکن است. و فقط زمانی قابل پیاده سازی است که ابعاد فضای ویژگی بسیار کوچک باشد.
در روش های پیشرفته تر، یک سری از کارهایی که انجام شده است استفاده از الگوریتم های تکاملی برای بهبود انتخاب ویژگی است. با توجه به اینکه در انتخاب ویژگی اطلاعات هیوریستیک وجود ندارد تا جستجوی زیر مجموعه بهینه را راهنمایی کند استفاده از الگوریتم های متاهیوریستیک مثل الگوریتم های تکاملی بسیار مناسب بنظر می رسد. برای انجام انتخاب ویژگی با استفاده از الگوریتم های تکاملی اساسی ترین مشکلی که وجود دارد انتخاب یک تابع هدف مناسب است. در ساده ترین حالت می توان از آموزش و تست یک شبکه عصبی برای تابع هدف استفاده کرد. ولی مشکل جدی در این حالت زمان بسیار طولانی مورد نیاز برای اجرای برنامه است .[1]
2. بررسی روش های کلاسیک انتخاب ویژگی
برای انتخاب ویژگی روش های گوناگونی وجود دارد که با توجه به نوع داده، ابعاد داده، و هدف از انتخاب ویژگی تعیین می شود. آشکاراست که بررسی تمام زیر مجموعه های ممکن و انتخاب زیر مجموعه بهینه با معرفی یک تابع هدف مناسب، همیشه بهترین نتیجه را می دهد. ولی از آنجا که برای N ویژگی تعداد 2N-1 زیر مجموعه ویژگی وجود دارد .[2] در اکثر مسائل تعداد زیر مجموعه ها بسیار زیاد می شود و ارزیابی تمام این زیر مجموعه ها مشکلات محاسباتی زیادی را منجر می شود و در عمل امری غیر ممکن است. پس باید فقط زیرمجموعه های خاصی بررسی شوند. استفاده از الگوریتم های تکاملی مانند GA, PSO ,ACO ABCدر چنین مواردی بسیار مناسب به نظر می رسد. روش های متنوعی برای انتخاب ویژگی معرفی شده اند، که تمام این روش ها دارای دو بخش اساسی هستند :[3]
-1 ارزیابی زیر مجموعه های تولید شده - استراتژی ارزیابی -
-2 تولید زیرمجموعه های ویژگی - استراتژی جستجو -
تقسیم بندی روش های انتخاب ویژگی بر مبنای استراتژی ارزیابی زیر مجموعه های ویژگی برای انتخاب ویژگی روشهای مختلفی وجود دارد. روشهای کلی انتخاب ویژگی را بر مبنای استراتژی ارزیابی الگوریتم انتخاب ویژگی به طور کلی می توان به دو دسته اصلی تقسیم نمود: روش های وابسته به الگوریتم یادگیری معروف به روش wrapper و روش های غیر وابسته به الگوریتم یادگیری معروف به روش .[4] filter
روش های با استراتژی ارزیابی wrapper
در روش های wrapper با استفاده از الگوریتم یادگیری زیرمجموعه های ویژگی براساس صحت آنها در طبقه بندی امتیازبندی می شوند. در این روش ها از تخمین صحت طبقه بندی برای ارزیابی شایستگی زیر مجموعه های ویژیگی استفاده می شود. دقت این روش ها بسیار قابل قبول است . ولی ایراد اصلی این روش ها حجم بالای محاسباتی است .[5]
روش های با استراتژی filter
در روش های filter زیرمجموعه های ویژگی بصورت پیش پردازشی انتخاب می شوند. در این روشها انتخابگر ویژگی از یک معیار غیر وابسته به الگوریتم یادگیری برای ارزیابی شایستگی زیر مجموعه های ویژگی استفاده می کند. مانند فاصله درون کلاسی و بین کلاسی [6]، همبستگی بین ویژگی ها [7]، خوشه یابی. روشهای filter دارای سرعت بالای هستند و مستقل از الگوریتم یادگیری هستند، ولی طبقه بندی کننده برای زیرمجموعه ویژگی انتخاب شده به بالاترین صحت ممکن نمی رسد.
مزیت این روش سرعت بالاتر نسبت به روش wrapper و کلی بودن آن برای انتخاب ویژگی بدون وابستگی به الگوریتم یادگیری و طبقه بندی کننده خاصی می باشد. روشهای wrapper انتخاب ویژگی های مناسب برای الگوریتم یادگیری و نیز صحت بالای طبقه بندی را تضمین می کنند. تقسیم بندی روش های انتخاب ویژگی بر مبنای استراتژی جستجو زیر مجموعه های ویژگی انتخاب ویژگی جز مسائل بهینه سازی گسسته می باشد. در الگوریتم های مختلف انتخاب ویژگی تولید زیر مجموعه های ویژگی به سه روش صورت می گیرد.
الگوریتم های با فرایند جستجو کامل
در روش های با فرایند جستجوکامل، تمام زیر مجموعه ویژگی های ممکن تولید می شوند و یک جستجو کامل برای یافتن زیر مجموعه بهینه صورت می گیرد. این روش بهترین نتیجه را از نظر کیفیت - هم از نظر صحت طبقه بندی و هم از نظر تعداد ویژگی - حاصل می کند. ولی حتی برای فضاهای ویژگی متوسط بدلیل هزینه های محاسباتی بسیار زیاد عملا غیر ممکن است.
الگوریتم های با فرایند جستجوی ابتکاری
در روش های با فرایند جستجو ابتکاری فضای ویژگی بنا بر استراتژی های خاصی جستجو می شود. عموما الگوریتم های جستجوی ویژگی ترتیبی مانند الگوریتم انتخاب ویژگی ابتکاری ترتیبی پیشرو و الگوریتم انتخاب ویژگی ترتیبی رو به عقب به این گروه تعلق دارند. در این روش ها در هر تکرار یک ویژگی به زیرمجموعه ویژگی اضافه / کم می شود .[8]
الگوریتم های با فرایند جستجوی تصادفی
روش های با فرایند جستجوی تصادفی بر مبنای الگوریتم های جستجوی تصادفی می باشند. این الگوریتم ها فضای ویژگی را برای بدست آوردن زیر مجموعه ویژگی جستجو می کنند که صحت پیشگویانه الگوریتم یادگیری را بیشینه کند.
3. معرفی الگوریتم های بهینه سازی تکاملی
GA الگوریتم ژنتیک
PSO الگوریتم بهینه سازی گروه ذرات
ABC الگوریتم بهینه سازی کلونی مورچه
ABC الگوریتم کلونی زنبورهای مصنوعی
مزیت الگوریتم های تکاملی در این است که برای مسائلی که جواب قطعی ندارند و یا نمی توان از راه حل های معمول به جواب رسید طی یک روند تکاملی مجموعه ای از نزدیکترین جواب ها به بهترین جواب را نشان خواهند داد. مهمترین نقطه قوت الگوریتم های تکاملی این است که آنها ذاتا موازی اند و می توانند فضای مسئله مورد نظر را در چندین جهت مختلف در یک لحظه جستجو کنند. از آنجایی که این الگوریتم ها چندین نقطه شروع دارند، در یک لحظه می توانند فضای مسئله را از چند جهت مختلف جستجو کند. اگر یکی به نتیجه نرسید سایر راه ها ادامه می یابند.
