کلاسه بند ها

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

 

  • کلاسه­بند درخت تصمیم 5

کلاسه­بند C4.5 [22]، نوعی درخت تصمیم بوده که توسط Ross Quinlan در سال 1993 ارائه شده است. این الگوریتم نوع ارتقا یافته الگوریتم قبلی Quinlan یعنی ID3 بوده که برای کلاسه­بندی مفید است. C4.5 با نمونه های آموزشی، یک درخت تصمیم همانند ID3 با استفاده از مفاهیم تئوری اطلاعات[1] [53] می­سازد و از رابطه جداسازیِ[2] بهره­ی اطلاعات نرمال شده[3] استفاده می­کند. این الگوریتم در موارد مختلفی با الگوریتم ID3 متفاوت است؛ این الگوریتم برای ویژگی­های اسمی[4] و پیوسته[5] قابل‌استفاده بوده، همچنین قابلیت مواجهه با مقادیر غایب[6] در ویژگی­ها را دارد. همچنین می­توان این الگوریتم را به دو صورت هرس شده[7] و هرس نشده[8] پیاده­سازی کرد که در روال آزمایش‌ها الگوریتم هرس شده مورد استفاده قرار گرفته­ است.

  • کلاسه­بند [9]SVM [55]

فرض می­کنیم که نمونه های آموزشی مربوط به کلاس های مختلف به صورت خطی جدا پذیراند[10]. در این صورت می توان بدون داشتن هیچ دانشی در مورد توزیع نمونه های آموزشی، بین نمونه های مربوط به کلاس های مختلف تمایز قائل شد. در کلاسه­بند SVM، مرز کلاسه­بندی به صورتی انتخاب می­شود که حاشیه[11]، بیشینه شود. شکل (5-1)، حاشیه و بردار­های پشتیبان[12] را نشان می­دهد [55].

در این کلاسه­بند، با بیشینه کردن حاشیه، ابر صفحه[13] بهینه برای کلاسه­بندی داده­های خطی به دست می­آید. اما با بهره گیری از توابع کرنل غیرخطی، SVM قادر است تا داده های کلاس های مختلف را بصورت غیرخطی از یکدیگر جدا نماید. در اینصورت، ابرصفحه جداکننده کلاس ها غیرخطی خواهد بود. این باعث می شود که کارایی کلاسه بند SVM در بسیاری از مسائل افزایش یابد.

شکل 5‑1 حاشیه، به فاصله عمودی بین مرز کلاسه­بندی و نزدیک­ترین داده گفته می­شود که با بیشینه کردن این حاشیه، یک مرز کلاسه­بندی ویژه به دست می‌آید. مکان این مرز کلاسه­بندی توسط زیرمجموعه‌ای از داده­ها که بردارهای پشتیبان نامیده می­شوند، مشخص می­شود. بردارهای پشتیبان توسط دایره­های توپر نمایش داده شده­اند[55].

  • کلاسه­بند بیزین ساده[14] [54]

کلاسه بند بیزین ساده، یک مدل احتمالی است که بجای یافتن تابع جداکننده، احتمال شرطی میزان تعلق هر ویژگی به هر کدام از کلاس ها و احتمال هر کلاس در نظر گرفته می شوند. در کلاسه­بند بیزین[15]، برچسب کلاس با بالاترین احتمال به نمونه تست ورودی اختصاص می­یابد [54]. در واقع برای نمونه ، احتمال پسین[16] به ازای عضویت این نمونه در کلاس­های مختلف ، به صورت زیر محاسبه می­شود:

(5-1)         

با استفاده از تئوری بیز[17] برای رابطه بالا داریم:

(5-2)     =  

                

احتمال   احتمال هر کلاس است که از روی داده­های آموزشی قابل محاسبه است. احتمال درست­نمایی[18]  با فرض مستقل بودن ویژگی­ها از یکدیگر به شرط برچسب کلاس، به سادگی قابل محاسبه است. این نکته قابل ذکر است که فرض استقلال ویژگی ها تاثیری بر روی کارایی کلاسه بند ندارد. این کلاسه­بند با استفاده از رابطه زیر، نمونه تست ورودی را کلاسه­بندی می­کند:

(5-3)         

  • کلاسه­بند نزدیک­ترین همسایه[19]

کلاسه­بند Knn، یک الگوریتم کلاسه­بندی تنبل[20] یا مبتنی بر نمونه[21] است. بر خلاف سایر الگوریتم­های کلاسه­بندی ها، این الگوریتم هیچ مرحله آموزشی[22] نداشته و نمونه­های آموزشی را تا وارد شدن نمونه تست، در حافظه ذخیره می­کند. سپس نزدیک­ترین نمونه آموزشی به نمونه ورودی تست بر اساس معیارهایی جستجو می شود، و برچسب کلاس آن نمونه آموزشی را به نمونه تست اختصاص می­یابد. در اغلب موارد از فاصله اقلیدسی برای محاسبه فاصله نمونه های آموزشی از نمونه تست در این الگوریتم استفاده می­شود. پارامتر  در این الگوریتم که تعداد نزدیک‌ترین همسایه را مشخص می­کند، معمولاً یک در نظر گرفته می­شود.

 

  • الگوریتم AdaBoost [24]

الگوریتم AdaBoost، یک روش یادگیری جمعی است و معروف‌ترین الگوریتم از خانواده الگوریتم­های Boosting است که توسطFreund  و Schapire [24] ارائه شده است. در الگوریتم های یادگیری جمعی، یک نمونه توسط چندین کلاسه بند مختلف کلاسه بندی می شود و نتایج کلاسه بندی ها به شکل هوشمندانه ای با یکدیگر ترکیب شده و نتیجه نهایی برای آن نمونه خاص تعیین می گردد. اغلب، کارایی الگوریتم یادگیری جمعی در مقایسه با تک تک کلاسه بندهای شرکت کننده در ساختار آن بالاتری کسب می نماید [56].  این الگوریتم خطا و واریانس داده­های آموزشی را کاهش داده امّا بسیار به نویز موجود در داده حساس است [57].  در الگوریتم یادگیری جمعی، هر کلاسه بند، با یک زیر مجموعه تصادفی و منتخب از کل نمونه ها، آموزش داده می شود. با شکل گرفتن چندین کلاسه بند متفاوت، کلاسه بند نهایی که نتیجه نگاه جمعی است دارای کارایی بالاتری خواهد بود.

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

در روش AdaBoost، در هر تکرار، تمرکز کلاسه بند مربوطه بیشتر بر تشخیص نمونه هایی است که به اشتباه توسط کلاسه بندهای مراحل قبل برچسب گذاری شده اند. در این روش، اولین کلاسه بند با یک bootstrap از مجموعه آموزشی، آموزش داده می شود. سپس کلاسه بند مرحل اول، با تمام نمونه های آموزشی تست می شود و تعیین می گردد که کدام نمونه ها توسط این کلاسه بند به درستی قابل تشخیص می باشند و کدام نمونه ها به اشتباه کلاسه بندی می شوند. سپس احتمال انتخاب نمونه هایی که به اشتباه کلاسه بندی شده اند، برای نمونه گیری مرحله بعد، افزایش می یابد و احتمال انتخاب نمونه هایی که به درستی کلاسه بندی شده اند، کاهش می یابد. بنابراین، کلاسه بندهای بعدی به احتمال زیاد با نمونه هایی آموزش داده می شوند که توسط کلاسه بندهای مراحل قبلی به درستی قابل تشخیص نبوده اند و احتمال آنکه مجددا با نمونه هایی که توسط کلاسه بندهای قبلی به درستی قابل تشخیص بوده اند، آموزش داده می شوند، کاهش می یابد. Schapire نشان داد که اگر کارایی کلاسه بند مورد استفاده، اگر کمی بهتر از شانس (50 درصد) باشد، با دنبال هم قرار دادن مجموعه ای از این کلاسه بندها، می توان به کارایی بالایی دست یافت.

[1] Information theory

[2] Splitting criterion

[3] Normalized information gain

[4] Nominal attribute

[5] Continuous attribute

[6] Missing value

[7] Pruned

[8] Unpruned

[9] Support Vector Machines

[10] Linearly separable

[11] Margin

[12] Support vectors

[13] Hyper-plane

[14] Naïve Bayes

[15] Bayesian classifier

[16] Posterior probability

[17] Bayes theorem

[18] Likelihood

[19] Nearest neighbor

[20] Lazy

[21] Instance-based

[22] Training phase

دیدگاه‌ خود را بنویسید

نشانی ایمیل شما منتشر نخواهد شد.