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

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

تعاریف

مساله انتخاب ویژگی بوسیله نویسندگان مختلف،  از دیدگاه­های متفاوتی مورد بررسی قرار گرفته است . هر نویسنده نیز با توجه به نوع کاربرد، تعریفی را از آن ارائه داده است. در ادامه چند مورد از این تعاریف را بیان می­کنیم[6]:

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

روش­های مختلف انتخاب ویژگی، تلاش می­کنند تا از میان ^N2 زیر مجموعه کاندید، بهترین زیرمجموعه را پیدا کنند. در تمام این روشها بر اساس کاربرد و نوع تعریف، زیر مجموعه­ای به عنوان جواب انتخاب می­شود، که  بتواند مقدار یک تابع ارزیابی را بهینه کند. با وجود اینکه هر روشی سعی می­کند که بتواند، بهترین ویژگی­ها را انتخاب کند، اما با توجه به وسعت جواب­های ممکن، و اینکه این مجموعه­های جواب بصورت توانی با N افزایش پیدا می­کنند، پیدا کردن جواب بهینه مشکل و در N های متوسط و بزرگ بسیار پر هزینه است. به طور کلی روش­های مختلف انتخاب ویژگی را بر اساس  نوع جستجو به دسته های مختلفی تقسیم بندی می­کنند. در بعضی روش­ها تمام فضای ممکن جستجو می­گردد. در سایر روش­ها که می­تواند مکاشفه­ای و یا جستجوی تصادفی باشد، در ازای از دست دادن مقداری از کارآئی، فضای جستجو کوچکتر می­شود. برای اینکه بتوانیم تقسیم بندی درستی از روش­های مختلف انتخاب ویژگی داشته باشیم، به این صورت عمل می­کنیم که فرآیند انتخاب ویژگی­ در تمامی روش­ها را به این بخش­ها تقسیم­ می­کنیم:

1. تابع تولید کننده (Generation procedure): این تابع زیر مجموعه­های کاندید را برای روش مورد نظر پیدا می­کند.
2. تابع ارزیابي  (Evaluation function) : زیرمجموعه مورد نظر را بر اساس روش داده شده، ارزیابی و یک عدد به عنوان میزان خوبی روش باز می­گرداند. روش­های مختلف سعی در یافتن زیرمجموعه­ای دارند که این مقدار را بهینه کند.
3. شرط خاتمه: برای تصمیم­گیری در مورد زمان توقف الگوریتم.
4. تابع تعیین اعتبار (Validation procedure): تصمیم می­گیرد که آیا زیر مجموعه انتخاب شده معتبر است یا خیر؟

 

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

1)     بدون ویژگی

2)     با مجموعه تمام ویژگی­ها

3)     با یک زیرمجموعه تصادفی

در حالت اول ویژگی­ها به ترتیب به مجموعه اضافه می­شوند و زیرمجموعه­های جدید را تولید می­کنند. این عمل آنقدر تکرار می­شود تا به زیر مجموعه مورد نظر برسیم. به اینگونه روش­ها، روشهای پائین به بالا می­گویند.

در حالت دوم از یک مجموعه شامل تمام ویژگی­ها، شروع می­کنیم و به مرور و در طی اجرای الگوریتم، ویژگی­ها را حذف می­کنیم، تا به زیرمجموعه دلخواه برسیم. روش­هایی که به این صورت عمل می­کنند، روشهای بالا به پائین نام دارند.

یک تابع ارزیابی، میزان خوب بودن یک زیرمجموعه تولید شده را بررسی کرده و یک مقدار به عنوان میزان خوب بودن زیرمجموعه مورد نظر بازمی­گرداند. این مقدار با بهترین زیرمجموعه قبلی مقایسه می­شود. اگر زیر مجموعه جدید، بهتر از زیرمجموعه­های قدیمی باشد، زیرمجموعه جدید به عنوان زیرمجموعه بهینه، جایگزین قبلی می­شود.

باید توجه داشت که بدون داشتن یک شرط خاتمه مناسب، فرآیند انتخاب ویژگی ممکن است، برای همیشه درون فضای جستجو، برای یافتن جواب سرگردان بماند. شرط خاتمه می­تواند بر پایه تابع تولید کننده باشد، مانند:

1)     هر زمان که تعداد مشخصی ویژگی انتخاب شدند.

2)     هر زمان که به تعداد مشخصی تکرار رسیدیم.

و یا اینکه بر اساس تابع ارزیابی انتخاب شود، مانند:

1)     وقتیکه اضافه یا حذف کردن ویژگی، زیرمجموعه بهتری را تولید نکند

2)     وقتیکه به یک زیرمجموعه بهینه بر اساس تابع ارزیابی برسیم.

تابع تعیین اعتبار جزئی از فرآیند انتخاب ویژگی نیست، اما در عمل بایستی یک زیرمجموعه ویژگی را در شرایط مختلف تست کنیم تا ببینیم که آیا شرایط مورد نیاز، برای حل مساله مورد نظر ما را دارد یا نه؟ برای اینکار می­توانیم از داده­های نمونه­برداری شده و یا مجموعه داده های شبیه سازی شده استفاده کنیم.

 

3-2- روش­های مختلف انتخاب ویژگی

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

3-2-1- توابع تولید کننده

اگر تعداد کل ویژگی­ها برابر N باشد، تعداد کل زیرمجموعه­های ممکن برابر 2^N می­شود. این تعداد برای N های متوسط هم خیلی زیاد است. بر اساس نحوه جستجو در میان این تعداد زیر مجموعه، روشهای مختلف انتخاب ویژگی را می­توان به سه دسته زیر تقسیم­بندی نمود:

1)     جستجوی کامل

2)     جستجوی مکاشفه­ای

3)     جستجوی تصادفی

در ادامه به معرفی هر کدام از این دسته­ها می­پردازیم.

3-2-1-1-  جستجوی کامل

در روش­هایی که از این نوع جستجو استفاده می­کنند، تابع تولید کننده بر اساس تابع ارزیابی استفاده شده، تمام فضای جواب (زیرمجموعه­های ممکن) را برای یافتن جواب بهینه جستجو می­کند. البتهSchlimmer استدلال آورده است که[7]: “کامل بودن جستجو به این معنی نیست که جستجو باید جامع باشد”.

توابع مکاشفه­ای مختلف زیادی طراحی شده­اند، تا جستجو را بدون از دست دادن شانس پیدا کردن جواب بهینه، کاهش دهند. اما با توجه به بزرگی فضای جستجو، O(2^N)، این روش­ها باعث می­شوند که فضای کمتری جستجو شود. روش­ها و تکنیک­های مختلفی برای اینکار استفاده شده اند، بعضی از آنها از تکنیک بازگشت به عقب (Backtracking) نیز در جریان کار استفاده کرده­اند، مانند: branch and bound، best first search و .beam search

3-2-1-2-  جستجوی مکاشفه ­ای

در روش­های با این نوع جستجو، در هر بار اجرای الگوریتم، یک ویژگی به مجموعه ویژگی انتخاب شده، اضافه و یا از آن حذف می­شود. به همین دلیل پیچیدگی زمانی آنها محدود و کمتر از O(N²) می­باشد. در اینگونه موارد، اجرای الگوریتم خیلی سریع می­باشد و پیاده سازی آنها نیز بسیار ساده است.

3-2-1-3-  جستجوی تصادفی

روش­هایی که از این نوع جستجو استفاده می­کنند، محدوده کمتری از فضای کل حالات را جستجو می­کنند، که اندازه این محدوده  به حداکثر تعداد تکرار الگوریتم بستگی دارد. در این روش­ها پیدا شدن جواب بهینه به اندازه منابع موجود و زمان اجرای الگوریتم بستگی دارد. در هر بار تکرار، تابع تولید کننده تعدادی از زیرمجموعه­های ممکن از فضای جستجو را به صورت تصادفی انتخاب می­کند و در اختیار تابع ارزیابی قرار می­دهد. تابع تولید کننده تصادفی پارامتر­هایی دارد که بایستی تنظیم شوند، تنظیم مناسب این پارامترها در سرعت رسیدن به جواب و پیدا شدن جواب­های بهتر موثر است.

 

3-2-2- تابع ارزیابی

پیدا شدن یک زیرمجموعه بهینه از مجموعه ویژگی­ها، به صورت مستقیم با انتخاب تابع ارزیابی بستگی دارد. چرا که اگر تابع ارزیابی به زیرمجموعه ویژگی بهینه یک مقدار نامناسب نسبت دهد، این زیرمجموعه هیچگاه بعنوان زیرمجموعه بهینه انتخاب نمی­شود. مقادیری که توابع ارزیابی مختلف به یک زیرمجموعه می­دهند، با هم متفاوت است.

توابع ارزیابی را می­توان به طرق مختلفی دسته بندی کرد. در اینجا ما دسته بندی­ای که توسط Dash و Liu ارائه شده است [6] را بیان می­کنیم. آنها این معیارها را به پنج دست تقسیم کرده­اند:

1. معیارهای مبتنی بر فاصله (Distance Measures): در این معیارها، مثلاً برای یک مساله دو کلاسه، یک ویژگی یا یک مجموعه ویژگی مثل X بر یک ویژگی یا یک مجموعه ویژگی دیگر مثل Yارجحیت دارد، اگر که با آن مجموعه ویژگی مقادیر بزرگتری برای اختلاف بین احتمالات شرطی دو کلاس داشته باشیم. نمونه­ای از این معیارها همان معیار فاصله اقلیدسی می­باشد.
2. معیارهای مبتنی بر اطلاعات (Information Measures) : این معیارها میزان اطلاعاتی را که بوسیله یک ویژگی بدست می­آید را در نظر می­گیرند. ویژگی X در این روش­ها بر ویژگی Y اولویت دارد، اگر اطلاعات بدست آمده از ویژگی X بیشتر از اطلاعاتی باشد، که از ویژگی Y بدست می­آید. نمونه­ای از این معیارها همان معیار آنتروپی می­باشد.
3. معیارهای مبتنی بر وابستگی (Dependence Measures): این معیارها که با عنوان معیارهای همبستگی (Correlation) نیز شناخته می­شوند، قابلیت پیشگوئی مقدار یک متغیر بوسیله یک متغیر دیگر را اندازه­گیری می­کنند. ضریب (Coefficient) یکی از معیارهای وابستگی کلاسیک است و می­توانیم آنرا برای یافتن همبستگی بین یک ویژگی و یک کلاس به کار ببریم. اگر همبستگی ویژگی X با کلاس C بیشتر از همبستگی ویژگی Y با کلاس C باشد، در اینصورت ویژگی X بر ویژگی Y برتری دارد. با یک تغییر کوچک، می­توانیم وابستگی یک ویژگی با ویژگی­های دیگر را اندازه­گیری کنیم. این مقدار درجه افزونگی این ویژگی را نشان می­دهد. همه توابع ارزیابی بر پایه معیار وابستگی را می­توانیم بین دو دسته معیارهای مبتنی بر فاصله و اطلاعات تقسیم کنیم. اما به خاطر اینکه این روش­ها از یک دید دیگر به مساله نگاه می­کنند، این کار را انجام نمی­دهیم.
4. معیارهای مبتنی بر سازگاری (Consistency Measures): این معیارها جدیدتر هستند و اخیراً توجه بیشتری به آنها شده است. این معیارها خصوصیات متفاوتی نسبت به سایر معیارها دارند، زیرا که به شدت به داده­های آموزشی تکیه دارند و در انتخاب یک زیرمجموعه از ویژگی­ها تمایل دارند، که مجموعه ویژگی­های کوچکتری را انتخاب کنند. این روش­ها زیرمجموعه­های با کمترین اندازه را بر اساس از دست دادن یک مقدار قابل قبول سازگاری که توسط کاربر تعیین می­شود، پیدا می­کنند.
5. معیارهای مبتنی بر خطای طبقه ­بندی کننده (Classifier Error Rate Measures): روش­هایی که این نوع از تابع ارزیابی را استفاده می­کنند، با عنوان “wrapper methods” شناخته می­شوند. دقت عملکرد در این روش­ها برای تعیین کلاسی که نمونه داده شده متعلق به آن است، برای نمونه­های دیده نشده بسیار بالا است، اما هزینه­های محاسباتی در آنها نیز نسبتاً زیاد است.

در جدول زیر مقایسه­ای بین انواع مختلف تابع ارزیابی، صرف نظر از نوع تابع تولید کننده مورد استفاده، انجام شده است. پارامترهایی که برای مقایسه استفاده شده­اند به صورت زیر می­باشند:

1. عمومیت (Generality): اینکه بتوان زیرمجموعه انتخاب شده را برای طبقه­بندی کننده­های متفاوت به کار ببریم.
2. پیچیدگی زمانی: زمان لازم برای پیدا کردن زیرمجموعه ویژگی­ جواب.
3. دقت: دقت پیشگوئی با استفاده از زیرمجموعه انتخاب شده.

علامت “—” که در ستون آخر آمده است، به این معنی است که در مورد میزان دقت حاصل نمی­توانیم مطلبی بگوئیم. بجز خطای طبقه­بندی کننده، دقت سایر توابع ارزیابی به مجموعه داده مورد استفاده و طبقه بندی کننده­ای که بعد از انتخاب ویژگی برای طبقه­بندی کلاس­ها استفاده می­شود، بستگی دارد.

 

 

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

در این قسمت بر اساس تابع ارزیابی و تابع تولید کننده، روش­های مختلف انتخاب ویژگی را به چند دسته تقسیم بندی می­کنیم و سپس تعدادی از روش­ها را شرح داده و الگوریتم کار را به صورت شبه کد، ذکر می­کنیم.

قبل از اینکه بحث را ادامه دهیم، لازم است که متغیرهای به کار رفته در شبه کدها را معرفی کنیم. این متغیرها و شرح آنها به صورت زیر می­باشد:

• D: مجموعه آموزشی
• S: مجموعه ویژگی اصلی (شامل تمام ویژگی­ها)
• N: تعداد ویژگی­ها
• T: زیرمجموعه ویژگی انتخاب شده
• M: تعداد ویژگی­های انتخاب شده یا تعداد ویژگی­هایی که لازم است انتخاب شوند.

 

3-2-3-1-  تابع ارزیابی مبتنی بر فاصله – تابع تولید کننده مکاشفه ای

مهمترین روش در این گروه Relief [8] است. در اینجا ما ابتدا این روش را به عنوان نماینده این گروه شرح می­دهیم، سپس یک مرور مختصری بر سایر روش­ها خواهیم داشت.

روش Relief از یک راه حل آماری برای انتخاب ویژگی استفاده می­کند، همچنین یک روش مبتنی بر وزن است که از الگوریتم­های مبتنی بر نمونه الهام گرفته است. روش کار به این صورت است که از میان مجموعه نمونه­های آموزشی، یک زیرمجموعه نمونه انتخاب می­کنیم. کاربر بایستی تعداد نمونه­ها(NoSample) در این زیرمجموعه را مشخص کرده باشد. و آنرا به عنوان ورودی به الگوریتم ارائه دهد. الگوریتم به صورت تصادفی یک نمونه از این زیرمجموعه­ را انتخاب می­کند، سپس برای هر یک از ویژگیهای این نمونه، نزدیکترین برخورد (Nearest Hit) و نزدیکترین شکست (Nearest Miss) را بر اساس معیار اقلیدسی پیدا می­کند.

نزدیکترین برخورد نمونه­ای است که کمترین فاصله اقلیدسی را در میان سایر نمونه­های هم­کلاس با نمونه انتخاب شده دارد. نزدیکترین شکست نیز نمونه­ای است که کمترین فاصله اقلیدسی را در میان نمونه­هایی که هم­کلاس با نمونه انتخاب شده نیستند، دارد.

ایده اصلی در این الگوریتم این است که هر چه اختلاف بین اندازه یک ویژگی در نمونه انتخاب شده و نزدیکترین برخورد کمتر باشد، این ویژگی بهتر است و بعلاوه یک ویژگی خوب آن است که اختلاف بین اندازه آن ویژگی و نزدیکترین شکست وی بیشتر باشد. دلیل کار هم خیلی ساده است، ویژگی­هایی که به خوبی دو کلاس (یا یک کلاس از سایر کلاس­ها) را از هم تمییز می­دهند، برای نمونه­های متعلق به دو کلاس متفاوت مقادیری نزدیک به­هم نمی­دهند و یک فاصله معنی­داری بین مقادیری که به نمونه­های یک کلاس می­دهند و مقادیری که به سایر کلاس(ها) می­دهند وجود دارد.

الگوریتم پس از تعیین نزدیکترین برخورد و نزدیکترین شکست، وزن­های ویژگی­ها را به روزرسانی می­کند، این به­روز­رسانی به این صورت است که مربع اختلاف بین مقدار ویژگی مورد نظر در نمونه انتخاب شده و نمونه نزدیکترین برخورد از وزن ویژگی کم می­شود و در عوض مربع اختلاف بین مقدار ویژگی در نمونه انتخاب شده و نزدیکترین شکست به وزن ویژگی اضافه می­شود. هر چه مقدار این وزن بزرگتر باشد، ویژگی مورد نظر، بهتر می­تواند نمونه­های یک کلاس را از دیگران جدا کند.

بعد از تعیین فاصله برای تمام نمونه­های موجود در مجموعه نمونه­ها، الگوریتم ویژگی­هایی را که وزن آنها کمتر یا مساوی با یک حد آستانه­ای است، را حذف می­کند، و سایر ویژگی­ها بعنوان زیرمجموعه ویژگی جواب باز می­گردند. مقدار حد آستانه­ای توسط کاربر تعیین می­گردد، البته ممکن است که بصورت اتوماتیک بوسیکه یک تابعی از تعداد کل ویژگی­ها تعیین شود و یا اینکه با سعی و خطا تعیین گردد. همچنین می­توان ویژگی­هایی که وزن آنها منفی است را حذف کرد.

 

 

روش استفاده شده توسط Koller و Sahami­

روش استفاده شده توسط Koller و Sahami­ که اخیراً ارائه شده است، بر این پایه استوار است که ویژگی­هایی که داده مفید چندانی را در بر ندارند و یا اصلاً داده مفیدی را در اختیار قرار نمی­دهند و می­توان آنها را با سایر ویژگی­ها نمایش داد، یا ویژگی­هایی که بی­ربط هستند و یا داده اضافی هستند، را شناسائی و حذف می­کنیم. برای پیاده سازی این مطلب، تلاش می­کنیم تا با پوشش مارکوف آنها را پیدا کنیم، به این صورت که یک زیرمجموعه مانند T، یک پوشش مارکوف برای ویژگی f_i است، اگر f_i  برای زیرمجموعه T بصورت مشروط هم از کلاس و هم از سایر ویژگی­هایی که در T نیستند، مستقل باشد[14].

 

3-2-3-4-  تابع ارزیابی مبتنی بر اطلاعات – تابع تولید کننده کامل

مهمترین روشی که در این گروه می­توانیم پیدا کنیم، روش Minimum Description Length Method (MDLM) است[16]. نویسندگان این روش تلاش می­کنند تا همه ویژگی­های بدون استفاده (بی­ربط یا اضافی) را حذف نمایند، با این دید که اگر ویژگی­های زیرمجموعه V را بتوانیم بصورت یک تابع ثابتی مانند F که وابسته به کلاس نیست، بر اساس یک زیرمجموعه ویژگی دیگر مانند U بیان کنیم. در این صورت وقتی که مقادیر ویژگی­های زیرمجموعه U شناخته شده باشند، ویژگی­های موجود در زیرمجموعه V بدون استفاده هستند.

از دیدگاه انتخاب ویژگی، اجتماع دو زیرمجموعه U و V، مجموعه کامل، شامل تمام ویژگی­ها را تشکیل می­دهد. و کاری که ما باید در انتخاب ویژگی انجام دهیم این است که این دو زیرمجموعه را جدا کنیم. برای انجام این کار، نویسندگان MDLM، از معیار Minimum Description Length Criterion (MDLC) که بوسیله Rissanen ارائه شده است[17]، استفاده کرده­اند. آنها فرمولی را بدست آورده­اند، که شامل تعداد بیتهای لازم برای انتقال کلاسها، پارامترهای بهینه سازی، ویژگی­های مفید و ویژگی­های غیرمفید است. الگوریتم تمام زیرمجموعه­های ممکن (2N) جستجو می­کند و بعنوان خروجی زیرمجموعه­ای را بازمی­گرداند که معیار MDLC را ارضا کند. این روش می­تواند تمام ویژگی­های مفیدی را پیدا کند که دارای توزیع نرمال باشند. برای حالتهای غیر نرمال این روش قادر نیست، ویژگی­های مفید را پیدا کند. الگوریتم زیر روش کار و فرمول­های استفاده شده را نشان می­دهد.

 

 

تابع ارزیابی مبتنی بر وابستگی – تابع تولید کننده مکاشفه ­ای

دو روش عمده در این گروه می­بینیم:

3)    Probability of Error & Average Correlation Coefficient (POE1ACC)

که خود شامل هفت روش است[18]، ما در اینجا روش هفتم را که به گفته نویسنده کاملتر است را بررسی می­کنیم.

در این روش اولین ویژگی به این صورت تعیین می­شود که احتمال خطا را برای تمام ویژگی­ها محاسبه می­کنیم، ویژگی با کمترین احتمال خطا (P_e)، به عنوان اولین ویژگی انتخاب می­شود. ویژگی بعدی، آن ویژگی است که مجموع وزن­دار P_e و میانگین ضریب همبستگی(ACC) با ویژگی(های) انتخاب شده را مینیمم کند.  سایر ویژگی­ها به همین ترتیب انتخاب می­شوند. میانگین ضریب همبستگی به اینصورت است که میانگین ضریب همبستگی ویژگی کاندید با ویژگی­های انتخاب شده در آن نقطه محاسبه می­شوند.

 

این روش می­تواند تمام ویژگی­ها را بر اساس مجموع وزن­دار درجه­بندی کند. شرط خاتمه نیز در این روش تعداد ویژگی­های مورد نیاز خواهد بود.

4)    PreSet

این روش از تئوری مجموعه­های ناهموار (Rough) استفاده می­کند. در اینجا یک کاهش (Reduct) پیدا می­کنیم. یک کاهش مانند R از یک مجموعه P به این معنی است که نمونه­ها بوسیله آن به خوبی مجموعه P طبقه بندی شوند. پس از پیدا کردن یک کاهش، تمام ویژگی­هایی که در مجموعه کاهش داده شده وجود ندارند، را از مجموعه ویژگی حذف می­کنیم. سپس ویژگی­ها را بر اساس اهمیت آنها درجه­بندی می­کنیم. اهمیت یک ویژگی بر این اساس بیان می­شود که یک ویژگی در جریان کلاس­بندی چقدر اهمیت دارد. این معیار بر پایه صفات وابستگی ویژگی تعیین می­گردد [19].

 

3-2-3-6-  تابع ارزیابی مبتنی بر سازگاری – تابع تولید کننده کامل

روش­هایی که در این گروه قرار دارند، در سالهای اخیر ارائه شده­اند. ما به صورت مختصر سه روش این گروه را بررسی می­کنیم ولی بحث اصلی ما بر روی روش اول است.

1)     Focus

این روش یک حداقل گرا است، به این معنی که سعی می­کند که حداقل تعداد ویژگی ممکن را برای ارائه پیدا کند. این روش فرضیه­های قابل تعریف را بررسی کرده و فرضیه­ای که بتواند سازگاری را با حداقل تعداد ویژگی ممکن برقرار کند را بعنوان جواب بازمی­گرداند.

در ساده­ترین پیاده سازی برای این روش، برای یافتن یک ناسازگاری با یک زیرمجموعه از ویژگی­های انتخاب شده، درخت جستجو را به صورت سطح به سطح (جستجو در پهنا)، پیمایش می­کنیم. در این جریان که از مجموعه­های کوچکتر شروع می­شود، در صورتی که به یک ناسازگاری برسیم، مجموعه انتخاب شده رد می­شود و جستجو با مجموعه بعدی ادامه می­یابد. به محض اینکه به یک مجموعه برسیم که ناسازگاری نداشته باشد، جستجو متوقف شده و مجموعه یاد شده به عنوان جواب انتخاب می­شود.

می­توان گفت که این روش به نویز حساس است و نمی­تواند نویز را مدیریت کند، زیرا در صورتی که نویز وجود داشته باشد، هیچ زیرمجموعه­ای را نمی­توان پیدا کرد که ناسازگاری نداشته باشد و الگوریتم تمام ویژگی­ها را به عنوان جواب بازمی­گرداند. با یک تغییر کوچک می­توانیم این مساله را حل کنیم، به اینصورت که اجازه می­دهیم یک میزان معینی از ناسازگاری در مجموعه انتخاب شده وجود داشته باشد.

 

شکل 19- الگوریتم روش Focus

 

2)     Schlimmer

این روش از یک شمارش سیستماتیک برای تابع تولید کننده و  یک معیار ناسازگاری نیز به عنوان تابع ارزیابی استفاده می­کند. همچنین با استفاده از یک تابع مکاشفه­ای سرعت جستجو را برای یافتن زیرمجموعه بهینه افزایش می­دهد. این تابع مکاشفه­ای یک معیار قابلیت اعتماد است، بر پایه این ایده که احتمال مشاهده یک ناسازگاری مشاهده شود، نسبتی از درصد مقادیری است که زیاد مشاهده شده­اند[7].

3)     MIFES1

این روش در انتخاب ویژگی شباهت زیادی به روش Focus دارد. در اینجا مجموعه نمونه­ها را به شکل یک ماتریس ارائه می­دهیم، هر عنصر نماینده یک ترکیب یکتا از یک نمونه منفی و یک نمونه مثبت است. یک ویژگی مانند f  یک پوشش برای یک نمونه از ماتریس نامیده می­شود، اگر برای نمونه­های منفی و نمونه­های مثبت، مقادیر عکسی داشته باشد. این روش از یک پوشش با همه ویژگی­ها شروع می­کند، و تکرار می­شود تا وقتی که هیچ کاهشی نتوانیم برای پوشش داشته باشیم. مشکل اساسی این روش اینست که فقط برای مسائل دو کلاسه و ویژگی­های منطقی قابل استفاده است. توضیحات کاملتر راجع به پوشش و نحوه اجرای الگوریتم را می­توانید در مرجع شماره [20] پیدا کنید.

 

3-2-3-7- تابع ارزیابی مبتنی بر سازگاری – تابع تولید کننده تصادفی

نماینده این گروه که جدیدتر هستند، روش LVF است[21]. این روش فضای جستجو را بصورت تصادفی با استفاده از یک الگوریتم Las Vegas جستجو می­کند، که یکسری انتخاب­های احتمالی انجام می­دهد تا با استفاده از آنها سریعتر به جواب بهینه برسیم، همچنین از یک معیار سازگاری که با معیار استفاده شده در الگوریتم Focus متفاوت است.

این روش برای هر زیرمجموعه کاندید، تعداد ناسازگاری را محاسبه می­کند، که بر این ایده استوار است که کلاس محتمل­تر آن است که در میان نمونه­های این زیرمجموعه ویژگی­، تعداد بیشری متعلق به آن کلاس باشند. یک حد آستانه­ای برای ناسازگاری در نظر گرفته می­شود، که در ابتدا ثابت و بصورت پیش فرض صفر است و هر زیرمجموعه­ای که مقدار ناسازگاری آن بیشتر باشد، رد می­شود.

 

شکل 20- الگوریتم روش LVF

 

این روش می­تواند هر زیرمجموعه بهینه را پیدا کند، حتی برای داده­های دارای نویز، به شرط آنکه سطح نویز درست را در ابتدا مشخص کنیم. یک مزیب این روش اینست که احتیاجی نیست که کاربر مدت زیادی را برای بدست آوردن یک زیرمجموعه بهینه منتظر بماند، زیرا الگوریتم هر زیرمجموعه­ای که بهتر از بهترین جواب قبلی باشد (هم از لحاظ اندازه زیرمجموعه انتخاب شده و هم از لحاظ نرخ سازگاری)، را به عنوان جواب باز­ می­گرداند.

این الگوریتم کارا است، زیرا تنها مجموعه­هایی برای ناسازگاری تست می­شوند، که تعداد ویژگی­های درون آن کمتر یا مساوی بهترین زیرمجموعه­ای است که تا کنون پیدا شده است. پیاده سازی­ آن آسان است و پیدا شدن زیرمجموعه بهینه را اگر منابع موجود اجازه دهند، تضمین می­کند. یکی از مشکلات این الگوریتم این است که برای پیدا کردن جواب بهینه زمان بیشتری نسبت به الگوریتم­هایی که از توابع تولید کننده مکاشفه­ای استفاده می­کنند، نیاز دارد، چون این الگوریتم از دانش مربوط به زیرمجموعه­های قبلی استفاده نمی­کند.

 

3-2-3-8-  تابع ارزیابی مبتنی بر خطای طبقه ­بندی کننده- تابع تولید کننده مکاشفه­ ای

همانطور که قبلاً نیز اشاره کردیم، به مجموعه روش­هایی که از تابع ارزیابی مبتنی بر نرخ خطای طبقه­بندی کننده استفاده می­کنند، (بدون توجه به نوع تابع تولید کننده استفاده شده) روش­های wrapperمی­گویند. در این گروه روش­های مشهور زیر را می­توانیم ببینیم:

1)     SFS (Sequential Forward Selection)

این روش، کارش را با یک مجموعه خالی شروع می­کند، سپس در هر تکرار یک ویژگی با استفاده از تابع ارزیابی مورد استفاده، به مجموعه جواب اضافه می­کند، این کار را تکرار می­کند تا زمانیکه تعداد ویژگی لازم انتخاب شود. مشکلی که این روش با آن روبروست، اینست که ویژگی اضافه شده در صورتیکه مناسب نباشد، از مجموعه جواب حذف نمی­شود[23].

2)     SBS (Sequential Backward Selection)

این روش برعکس SFS کارش را با مجموعه­ای شامل تمام ویژگی­ها شروع می­کند و در هر بار تکرار الگوریتم، ویژگی که بوسیله تابع ارزیابی انتخاب می­شود، را از مجموعه مورد نظر حذف می­کند. این کار را تا زمانی ادامه­ می­دهد که تعداد ویژگی­ها برابر یک تعداد معینی شود. مانند روش قبل مشکل این روش اینست که ویژگی حذف شده را دیگر به مجموعه اضافه نمی­کند، حتی اگر مناسب باشد[23].

روش­های دیگری که در این گروه وجود دارند، نسخه­های متفاوتی از دو روش قبلی یا ترکیب آنها هستند.

3)     SBS-Slash

این روش بر پایه این مشاهده است که هنگامی­ که تعداد زیادی ویژگی وجود دارد، بعضی از طبقه بندی کننده­ها (مانند ID3 یا C4.5) مکرراً تعداد زیادی از آنها را استفاده نمی­کنند. الگوریتم با یک مجموعه ویژگی کار خودش را شروع می­کند (مانند SBS)، اما بعد از یک مرحله تمام ویژگی­هایی را که در این مرحله یاد گرفته است و استفاده نشده­اند، را حذف (Slashes) می­کند[24].

4)     PQSS ((p,q) Sequential Search)

در اینجا از بعضی از خواص بازگشت به عقب (Backtracking) استفاده می­کنیم. عملکرد الگوریتم به این صورت است که در هر مرحله p ویژگی به مجموعه اضافه و q ویژگی از آن حذف می­کند. حال اگر الگوریتم از مجموعه خالی شروع ­کرده باشد، بایستی اندازه p بزرگتر از اندازه q باشد. ولی اگر از مجموعه تمام ویژگی­ها شروع شده باشد، بایستی اندازه p کوچکتر از q باشد[25].

5)     BDS (Bi-Directional Search)

مانند روش­های قبل است با این تفاوت که جستجو را از دو طرف انجام می­دهد[25].

6)     Schemata Search

الگوریتم کارش را با مجموعه خالی و یا مجموعه تمام ویژگی­ها شروع می­کند و در هر تکرار، بهترین زیرمجموعه را با حذف یا اضافه تنها یک ویژگی به مجموعه ویژگی، پیدا می­کند. برای اینکه هر زیرمجموعه را ارزیابی کند، از تعیین اعتبار Leave-One-Out Cross Validation (LOOCV) استفاده می­کند. در هر تکرار زیرمجموعه­ای انتخاب می­شود که کمترین خطای LOOCV را داشته باشد. کار به اینصورت ادامه می­یابد تا هیچ تغییر با تک ویژگی نتواند باعث بهتر شدن زیرمجموعه شود[26].

7)     RC (Relevance in Context)

در اینجا این واقعیت تشریح شده است که بعضی از ویژگی­ها فقط در قسمتی از فضای کار مربوط هستند. روش کار مشابه SBS است، اما با تغییرات عمده­ای که باعث محلی شدن آن شده است(انتخاب ویژگی­های مرتبط بر اساس تصمیم گیری بوسیله نمونه­ها­) [27].

8)     Queiros and Gelsema

شبیه SFS است اما پیشنهاد می­کند که در هر تکرار، هر ویژگی در با تنظیمات متفاوتی بوسیله اثرات متفاوت ناشی از ویژگی­های قبلی ارزیابی شود[28]. دو نمونه از این تنظیمات به اینصورت هستند:

i)                   همیشه فرض کنیم که ویژگی­ها مستقل هستند (ویژگی­های قبلی را در نظر نمی­گیریم).

ii)                 هیچگاه فرض نمی­کنیم که ویژگی­ها مستقل هستند (ویژگی­های قبلی را در نظر می­گیریم).

در این روش و تعدادی از روش­های قبلی در این گروه از نرخ خطای بیز به عنوان خطای طبقه بندی کننده استفاده می­کنیم.

 

3-2-3-9-  تابع ارزیابی مبتنی بر خطای طبقه­ بندی کننده – تابع تولید کننده کامل

در این گروه چهار روش وجود دارد، که دو روش اول آن بوسیله Ichino  و  Sklansky ارائه شده است.

1)     Linear Classifier

2)     Box Classifier

در دو روش فوق مساله انتخاب ویژگی بوسیله برنامه نویسی صفر و یک حل شده است[29,30,31].

3)     AMB&B (Approximate monotonic branch and bound)

این روش برای حل مشکلات B&B ارائه شده است، به این صورت که به تابع ارزیابی اجازه داده می­شود که غیر یکنوا باشد[32]. در اینجا به تابع تولید کننده اجازه داده می­شود که زیرمجموعه­هایی تولید کند که محدودیت تعیین شده را نقض می­کنند، اما زیرمجموعه­ای که بعنوان جواب انتخاب می­شود، نباید محدودیت ذکر شده را نقض کرده باشد.

4)     BS (Beam Search)

این روش یک نمونه از جستجوی Best-First، است که از صف محدود شده برای محدود کردن فضای جستجو استفاده می­کند. صف از بهترین به بدترین مرتب می­شود، در اینصورت، بهترین زیرمجموعه در ابتدای صف قرار داده می­شود. تابع تولید کننده به این صورت عمل می­کند که زیرمجموعه موجود در ابتدای صف را انتخاب و کلیه زیرمجموعه­های ممکن با اضافه کردن یک ویژگی به آن را تولید می­کند و آنها را در محل مناسبشان در صف قرار می­دهد. در صورتی که هیچ محدودیتی در اندازه صف نداشته باشیم، این روش یک جستجوی جامع است. در حالتی که محدودیت طول برابر یک را برای صف داشته باشیم، این روش با SFS برابر است.

 

3-2-3-10-  تابع ارزیابی مبتنی بر خطای طبقه ­بندی کننده – تابع تولید کننده تصادفی

در این گروه پنج روش وجود دارد، که به شرح ذیل می­باشند.

1)     LVW

این روش زیرمجموعه­هایی به صورت کاملاً تصادفی با استفاده از الگوریتم Las Vegas تولید می­کند[33].

2)     GA (Genetic Algorithm)

در این روش یک جمعیت از زیرمجموعه­های کاندید تولید می­کنیم. در هر بار تکرار الگوریتم، با استفاده از عملگرهای جهش و بازترکیبی بر روی عناصر جمعیت قبلی، عناصر جدیدی تولید می­کنیم. با استفاده از یک تابع ارزیابی، میزان شایستگی عناصر جمعیت فعلی را مشخص کرده و عناصر بهتر را به عنوان جمعیت نسل بعد انتخاب می­کنیم. پیدا شدن بهترین جواب در این روش تضمین نمی­شود ولی همیشه یک جواب خوب به نسبت مدت زمانی که به الگوریتم اجازه اجرا داده باشیم، پیدا می­کند.

3)     SA (Simulated Annealing)

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

4)     RGSS (Random Generation plus Sequential Selection)

این روش مشابه SBS و SFS است با این تفاوت که یک زیرمجموعه تصادفی تولید می­کند و سپس SBS و  SFS را با استفاده از این زیرمجموعه تولید شده اجرا می­کند. در واقع فاکتور تصادف را به دو روش ذکر شده تزریق می­کند، تا کارآئی آنها را افزایش دهد.

5)     RMHC-PF1 (Random Mutation Hill Climbing-Prototype and Feature selection)

نمونه­های اولیه (Prototype) و ویژگی­ها در اینجا همزمان برای استفاده در طبقه بندی کننده نزدیکترین همسایه انتخاب می­شوند، همچنین برای ثبت نمونه­های اولیه و ویژگی­ها از یک بردار شرطی استفاده می­شود. تابع ارزیابی نیز، نرخ خطای طبقه­بندی کننده نزدیکترین همسایه می­باشد. در هر تکرار، بصورت تصادفی یکی از بیتهای بردار جهش داده می­شوند، تا یک بردار جدید برای تکرار بعدی تولید شود.

تمام روش­های این گروه پارامتر­های زیادی دارند که بایستی تنظیم شود، مثلاً LVW حد آستانه­ای برای نرخ ناسازگاری، در الگوریتم­های ژنتیک اندازه جمعیت اولیه، نرخ بازترکیبی و نرخ جهش و یا در SA، تعداد تکرار حلقه، دمای اولیه و احتمال جهش. تنظیم دقیق این پارامترها عملکرد این الگوریتم­ها را بهبود می­بخشد.

 

3-2-4- جمع بندی روشهای انتخاب ویژگی

برای اینکه یک جمع­بندی از کلیه روش­های انتخاب ویژگی داشته باشیم، نمودار آنها را برحسب سه نوع تابع تولید کننده در شکل زیر نشان داده­ایم[6].

 

شکل 21- طبقه بندی روش­های مختلف انتخاب ویژگی