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

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

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

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

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

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

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

 

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