برای مقایسه الگوریتمهای مختلف ارائه‌شده در هر قسمت از آزمایش‌ها، چندین کلاسهبند با توجه به خصوصیات روشها مورد استفاده قرار گرفتهاند. در ادامه به توضیح 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، یک روش یادگیری جمعی است و معروف‌ترین الگوریتم از خانواده الگوریتمهای 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