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

۱)     بدون ویژگی

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

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

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

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

 

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

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

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

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

 

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

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

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

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

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

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