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

روش­هایی که در این گروه قرار دارند، در سالهای اخیر ارایه شده­اند. ما به صورت مختصر سه روش این گروه را بررسی می­کنیم ولی بحث اصلی ما بر روی روش اول یعنی Focusاست [Huss94].

1)     روش Focus

این روش یک حداقل گرا است، به این معنی که سعی می­کند که حداقل تعداد ویژگی ممکن را برای ارایه جواب پیدا کند. Johnو Kohaviو Pflegerویژگی­ها را از لحاظ رابطه بین ان­ها به سه کلاس تقسیم کرده­اند [Geor94]:

     i.            بدون ارتباط

    ii.            ارتباط ضعیف

   iii.            ارتباط شدید

الگوریتم Focusبرای یافتن پاسخ، با تمام مجموعه ویژگی­های با ارتباط شدید و تعداد کمی از مجموعه­های با ارتباط ضعیف، موفق عمل می­کند. در نتیجه Focusیک الگوریتم ایده­ال برای زمانی است که کوچکترین مجموعه از ویژگی­ها موردنیاز است و نمونه­ها بدون نویز باشند. این الگوریتم همیشه مجموعه جواب بهینه را با استفاده از جستجوی کامل روی فضای زیرمجموعه­های ویژگی، با زمان و کارایی شبه چندجمله­ای پیدا می­کند. در مقایسه با الگوریتم­های مشابه نتایج خوبی به دست اورده است و همچنین ثابت کرده است با پایگاه داده­های دارای مقدار کمی نویز، نیز بخوبی کار می­کند. با این وجود Focus محدود به دامنه بولی[1] می­باشد، درحالی­که اکثر مسایل، ویژگی­های گسسته یا پیوسته دارند. برای رفع این محدودیت، نسخه تکمیل شده این الگوریتم یعنی Focus-2یا (C-Focus) ارایه شد که رفتار بهتری از خود نشان می­دهد.

 
   

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

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

ایده اصلی الگوریتمFocus، شناخت تمام جفت ویژگی­های نمونه است که نتیجه بولی متفاوت داشته باشند. هر یک از این جفت­ها یک ناسازگاری نامیده می­شود و هدف الگوریتم این است که کوچکترین مجموعه از ویژگی­ها را پیدا کند که تمام ناسازگاری­ها را برطرف کند. ویژگی برای حل ناسازگاری در نظر گرفته می­شود که مقدار ان در دو نمونه متفاوت باشد. در این موقع است که این ویژگی به ما اجازه می­دهد که ان نمونه را به دو قسمت تقسیم کنیم. واضح است که در دامنه گسسته یا بولی، این ناسازگاری توسط یک متغیر گسسته یا بولی حل خواهد شد، اما ما به یک راه حل برای متغیر­های پیوسته که مقادیر متفاوت دارند، نیاز داریم. به این منظور اختلاف مطلق بین دو مقدار را بکار می­بریم. تمام مقادیر در نمونه­های یک ویژگی مشخص به [0,1]نرمالیزه خواهد شد. اگر اختلاف بزرگتر از مقدار استانه Uباشد، دو مقدار متمایز در نظر گرفته می­شوند.

شکل 10- الگوریتمی دیگر از روش Focus

Focusجستجو بر روی مجموعه­های با 1,2,3,…متغیر را به طور مداوم ادامه می­دهد تا مجموعه­ای که تمام ناسازگاری­ها را حل می­کند، پیدا شود. با این ایده، Almuallim and Dieterichالگوریتم Focus-2را ارایه کردند [Geor94].

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

 
 

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

MA,Bبه معنی فضای زیرمجموعه­های تمام ویژگی­هایی است که شامل ویژگی­های مجموعه Aو هیچ یک از ویژگی­های Bباشد. به عنوان ازمایش شایستگی در مرحله 4.4.1از الگوریتم، با استفاده از تابع Sufficient(Features, Sample)به دنبال دو مورد در نمونه می­گردیم که دارای مقادیر نامتمایز در ویژگی­های انتخاب شده بوده و متعلق به کلاس متفاوت باشند. اگر این­چنین دو موردی وجود نداشت، مجموعه ویژگی شایسته است، در غیر این­صورت ناشایسته می­باشد.

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

به عنوان مثالی از چگونگی کارکرد الگوریتم Focus، در شکل زیر دو کلاس C1وC2 را مشاهده می­کنید که مقادیر ویژگی­های Bو Dدر دوکلاس متفاوت هستند. چون مقادیر ویژگی­های Aو Cهمانند یکدیگر است، برای دسته­بندی مفید نمی­باشند.

شکل 12- کلاس های مورد بررسی در الگوریتم Focus

شکل 12- کلاس­های مورد بررسی در الگوریتم Focus

 
 

 

 
   


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

شکل 13- روند الگوریتم Focus

شکل 13- روند الگوریتم Focus

یک داده نامربوط مانند Aممکن است یک ناسازگاری را حل کند، ولی به مجموعه مینیمم ویژگی تعلق نخواهد داشت. با این حال تعداد کمتری ویژگی مناسب مثل Dباید تمام ناسازگاری­ها را حل نماید. اگر nتعداد ویژگی­های مناسب و مرتبط باشد، کارایی O(n!)خواهد بود. جستجو مرتبا با مجموعه­های 1,2,3,…تکرار خواهد شد، به این ترتیب:

{A}, {B}, {C}, {D}, {AB}, {AC}, {AD}, {BC}, {BD},… ویژگی­های Aو Cبرای حل ناسازگاری مورد نیاز هستند.


شکل 14- حل ناسازگاری در الگوریتم Focus

شکل 14- حل ناسازگاری در الگوریتم Focus

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

2)     روش Schlimmer

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

3)     روش MIFES1

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


[1] - boolean domains

[2]breadth first search

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