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

استفاده از این ترکیب در روش­های قدیمی نظیر B&B (Branch and Bound)یافت می­شود [Nare77]. سایر روش­های این گروه، نسخه­های متفاوتی از B&Bهستند، به این ترتیب که یا یک تابع تولید کننده دیگر را استفاده کرده­اند (BFF [Xul88])و یا از یک تابع ارزیابی متفاوتی استفاده کرده­اند (Bobrowski’s method [Bob88]). در اینجا ابتدا به شرح B&Bمی­پردازیم و سپس شرح مختصری در مورد دو روش دیگر ارایه می­دهیم.

تعریف کلاسیک ارایه شده بوسیله Fukunagaو Narendaاز انتخاب ویژگی، احتیاج دارد که تابع ارزیابی یکنوا باشد. یعنی اگر دو زیرمجموعه ویژگی Aو Bبا اندازه­های Mو Nموجود باشند، و BAدر این صورت مقدار تابع ارزیابی برای Aنباید بیشتر از مقدار تابع برای Bباشد. این تعریف باعث ایجاد مشکل در مسائل دنیای واقعی می­شود، زیرا اندازه تخمینی زیرمجموعه ویژگی بهینه در حالت عمومی ناشناخته است.

البته به سادگی می­توان این تعریف را تغییر داد تا با مسائل عمومی سازگار شود، به این صورت که می­گوییم: الگوریتم­های مشابه B&Bتلاش می­کنند که دو شرط زیر را هم­زمان ارضاء کنند [Doak92]:

1.     زیرمجموعه ویژگی پاسخ تا حد امکان کوچک باشد.

2.     یک کران برای مقدار تابع ارزیابی را در نظر بگیرد. (یا یک اندازه مینیمم برای تعداد ویژگی­های انتخاب شده مثلاً بهترین زیرمجموعه ویژگی سه عنصری)

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

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

عموماً توابع ارزیابی زیر برای این‌کار استفاده می­شوند:

·         فاصله ماهالانوبیس (Mahalanobis Distance) [Dura74]

·         تابع جداساز (Discriminant Function)

·         معیار فیشر (Fisher Criterion)

·         فاصله باتاچاریا (Bhattacharya)

·         Divergence[Fuku77]

Xu,Yanو Changیک الگوریتم مشابه برای انتخاب ویژگی BFFپیشنهاد کرده­اند [Chang88]که در این الگوریتم، تابع جستجو به این صورت تغییر کرده است که مشابه حل مساله جستجوی یک مسیر بهینه در یک درخت وزن­دار با یک استراتژی تغییر یافته از Best first searchاست. این الگوریتم تضمین می­کند که بهترین هدف (زیرمجموعه بهینه) بدون از دست دادن جامعیت مساله پیدا شود، البته با ارضای معیار یکنوا بودن تابع ارزیابی.

شکل 4- الگوریتم Branch and Bound

شکل 4- الگوریتم Branch and Bound

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