یکشنبه 30 شهریور 1399 | Sunday 20 th of September 2020 صفحه اصلی گروه الکترونیکی کامپیوتر
دسته بندی و تشریح الگوریتم های مختلف انتخاب ویژگی

در این بخش، تعدادی از روش­ها را شرح داده و الگوریتم کار را به صورت شبه کد، ذکر می­کنیم.

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

·         متغیر D: مجموعه اموزشی

·         متغیر S: مجموعه ویژگی اصلی (شامل تمام ویژگی­ها)

·         متغیر N: تعداد ویژگی­ها

·         متغیر T: زیرمجموعه ویژگی انتخاب شده

·         متغیر M: تعداد ویژگی­های انتخاب شده یا تعداد ویژگی­هایی که لازم است انتخاب شوند.

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

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

روش Relief

این روش از یک راه حل اماری برای انتخاب ویژگی استفاده می­کند، همچنین یک روش مبتنی بر وزن است که از الگوریتم­های مبتنی بر نمونه الهام گرفته است [Aha91] , [Call91]. روش کار به این صورت است که از میان مجموعه نمونه­های اموزشی،یک زیرمجموعه نمونه انتخاب می­کنیم، کاربر بایستی تعداد نمونه­ها(NoSample) در این زیرمجموعه را مشخص کرده باشد و ان­را به عنوان ورودی به الگوریتم ارایه دهد. الگوریتم به صورت تصادفی یک نمونه از این زیرمجموعه­را انتخاب می­کند، سپس برای هر یک از ویژگیهای این نمونه، نزدیک­ترین برخورد[1] و نزدیک­ترین شکست[2] را بر اساس معیار اقلیدسی پیدا می­کند.

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

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

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

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

شکل 3- الگوریتم Relief

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

یکی از محدودیت­های اساسی این الگوریتم این است که ویژگی­هایی که دارای افزونگی باشند را پیدا نمی­کند و بنابراین مجموعه­های غیر بهینه را پیدا می­کند که دارای افزونگی هستند. این مشکل را می­توان با یک جستجوی تعیین جامعیت برای زیرمجموعه­های تولید شده توسط الگوریتم حل کرد. مشکل دیگر این است که تنها با مسائل دو کلاسه خوب کار می‌کند. این محدودیت نیز با الگوریتم Relief-F [Kon94]مرتفع شده است، با الگوریتم جدید مشکل داده­های غیر کامل (نمونه­های اموزشی غیرکامل) نیز حل شده است.

روش Jakub

روشی که Jakub Segen [Seg84]برای انتخاب ویژگی مطرح کرده است، از یک تابع ارزیابی استفاده می­کند که مجموع یک معیار اختلاف اماری و یک معیار پیچیدگی ویژگی را محاسبه کرده و ان را مینیمم می­کند. این الگوریتم، اولین ویژگی که بهتر بتواند کلاس­ها را از هم تمیز دهد پیدا می­کند. سپس به دنبال ویژگی­هایی می­گردد که در ترکیب با ویژگی­های انتخاب شده، جدائی­پذیری کلاس­ها را افزایش دهند، این فرایند زمانی متوقف می­شود که به حداقل معیار بازنمائی مورد انتظار برسیم.


[1]- Nearest Hit

[2]- Nearest Miss

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26