الگوریتم Boosting اثبات می­ کند که یک کلاسه کننده ضعیف زمانی می‌تواند تبدیل به یک کلاسه‌کننده قوی شود که در قالب تشخیص احتمالا درست(PAC)^[100] قرار گیرد.یکی از معروف‌ترین الگوریتم‌های این خانواده AdaBoost می‌باشد که جزء 10 الگوریتم برتر داده کاوی محسوب می‌شود. در این روش، اریبی در کنار واریانس کاهش می‌یابد و مانند ماشین‌های بردار پشتیبان حاشیه‌ها افزایش می‌یابند. این الگوریتم از کل مجموعه داده به منظور آموزش هر دسته‌کننده استفاده می‌کند، اما بعد از هر بار آموزش، بیشتر بر روی داده‌های سخت تمرکز می‌کند تا به درستی کلاسه بندی شوند. اين روش تکراري تغيير انطباقي به توزيع داده های آموزش با تمرکز بيشتر بر روي نمونه هايي است که قبلا بطور صحيح کلاس بندي نشده اند. در ابتدا تمام رکوردها وزن يکساني مي­گيرند و بر خلاف Bagging وزن ها در هر تکرار افزایش پیدا خواهند کرد. وزن نمونه هايي که به اشتباه طبقه بندي شده اند افزايش خواهد يافت در حالی که وزن آن دسته از نمونه‌هایی که به درستي کلاس بندي شده اند کاهش خواهد يافت. سپس وزن دیگری به صورت مجزا به هر دسته‌کننده با توجه به دقت کلی آن  اختصاص داده می‌شود که بعدا در فاز تست مورد استفاده قرار می‌گیرد. کلاسه بندهای دقیق از ضریب اطمینان بالاتری برخوردار خواهند بود. در نهایت هنگام ارائه یک نمونه جدید هر کلاسه بند یک وزن پیشنهاد می‌دهد و برچسب کلاس با رأی اکثریت انتخاب خواهد شد]15[.
همچنین الگوریتم­های Boosting مانند Adacost ]21[، ]RareBoost22[، وSMOTEBoost ]23[، که با تنظیمات جمعی^[101] برای یادگیری عدم توازن کلاس استفاده شده اند،نیز می­توانند برای SVM بکار گرفته شوند.

• • AdaBoost : بسیاری از مشکلات عملی الگوریتم های Boosting را حل کرده است.در این روش در ابتدا همه وزن ها یکسان هستند، اما در هر دور، وزن نمونه هایی که به اشتباه طبقه بندی شدند افزایش می یابند و این باعث میشود که یادگیرنده تمرکز بیشتری بر روی نمونه های سخت داشته باشد.

• • Rare-Boost : نمونه های مثبت-غلط را نسبت به نمونه های مثبت-درست مورد سنجش قرار میدهد تا مشخص شود که این نمونه ها تا چه اندازه به درستی تشخیص داده شده اند و همچنین نمونه های مثبت-غلط را نسبت به نمونه های منفی-درست نیز مورد سنجش قرار می دهد.

• • یکی دیگر از الگوریتم هایی که از روش Boosting برای مقابله با مشکل عدم توازن کلاس استفاده می­ کند، الگوریتم SMOTEBoost است.این الکوریتم تشخیص داد که Boosting ممکن است مانند روش بیش نمونه برداری از مشکل بیش برازش رنج ببرد.در SMOTEBoost ، برای ایجاد تغییر در توزیع داده ها از روش بروز رسانی وزن مربوط به هر نمونه استفاده نمیشود، بلکه در این روش با بهره گرفتن از الگوریتم SMOTE، نمونه های جدیدی به کلاس اقلیت اضافه میشود و از این طریق باعث ایجاد تغییر در توزیع داده می­ شود.

2-9-3 روش­های یادگیری عدم تعادل داخلی^[102] برای ماشین بردار پشتیبان(روش­های الگوریتمیک)

در این بخش برای کاهش حساسیت الگوریتم SVM به عدم تعادل کلاس، تغییرات الگوریتمی پیشنهاد می­ شود.

2-9-3-1 هزینه خطای متفاوت^[103]

همانطور که در بخش 2-8-1 بیان شد، دلیل اصلی حساسیت الگوریت به عدم توازن کلاس این است که تابع هدف حاشیه نرم که در معادله (2-34) ارائه شد، برای طبقه بندی اشتباه منفی^[104] و طبقه بندی اشتباه مثبت^[105] هزینه یکسانی را در نظر می گیرد. این امر باعث میشود که ابرصفحه جداکننده به سمت کلاس اقلیت انحراف پیدا کند و مورب^[106] شود که نهایتا منجر به تولید مدلی با بهینگی کمتر از حد مطلوب^[107] می شود.
متد یک روش یادگیری حساس به هزینه است که برای غلبه بر این مشکل ارائه شده است]16[.در این روش، تابع هدف حاشیه نرم^[108]، تغییر می­ کند و دو هزینه متفاوت برای طبقه بندی اشتباه اختصاص می­دهد.به طوری که ، هزینه طبقه بندی اشتباه برای نمونه های کلاس مثبت، و ، هزینه طبقه بندی اشتباه برای نمونه های کلاس منفی است.فرمول (2-35) زیر این شرایط را نشان می­دهد.

(2-35)
ما در اینجا کلاس مثبت را به عنوان کلاس اقلیت، و کلاس منفی را به عنوان کلاس اکثریت در نظر می­گیریم.اگر برای طبقه بندی اشتباه نمونه های کلاس اقلیت، هزینه بیشتری را نسبت به نمونه های کلاس اکثریت اختصاص دهیم(>)، اثر عدم توازن کلاس کاهش می یابد.بنابراین الگوریتم SVM اصلاح شده تمایلی ندارد که برای کاهش misclassification کلی، ابرصفحه جداکننده را به سمت نمونه های کلاس اقلیت انتقال دهد زیرا اکنون به نمونه های کلاس اقلیت، هزینه misclassification بیشتری اختصاص داده شده است.
فرم لاگرانژ دوگانه^[109] برای تابع هدف تغییر یافته را میتوان به صورت زیر بیان کرد:

(2-36)
و ضرایب لاگرانژ را برای نمونه های مثبت و منفی نشان می­دهد.این مشکل بهینه سازی دوگانه را میتوان همانند مشکل بهینه سازی SVM نرمال حل کرد]20[.
با بهره گرفتن از روش DEC، و در صورتی که مساوی با نسبت کلاس اقلیت به کلاس اکثریت تنظیم شود، میتوان نتایج طبقه بندی مناسبی را بدست آورد]18[.
2-9-3-2 یادگیری یک کلاس^[110]
دو روش متعادل سازی مجدد^[111] برای آموزش SVM با مجموعه داده های بسیار نامتوازن ارائه شده است.روش اول مدل SVM را تنها با نمونه های کلاس اقلیت آموزش می­دهد]24[. در روش دوم، متد DEC توسعه داده شده است و در آن هزینه طبقه بندی اشتباه برای نمونه های کلاس اکثریت و هزینه طبقه بندی اشتباه برای نمونه های کلاس اقلیت اختصاص داده شده است.تعداد نمونه هاس کلاس اقلیت است]25[.نتایج تجربی بدست آمده از مجموعه داده های به شدت نامتوازن در دنیای واقعی و همچنین مجموعه های ساختگی، نشان می­دهد که این روش­ها از متدهای معمول متعادل سازی مجدد موثرتر هستند.

2-9-3-3ZSVM

zSVM یکی دیگر از روش های اصلاح الگوریتمی برای SVM است که برای یادگیری از مجموعه داده های نامتوازن پیشنهاد شده است]26[.در این روش در ابتدا یک مدل SVM با بهره گرفتن از مجموعه داده نامتوازن آموزشی^[112] اصلی توسعه داده شده است.پس از آن مرز تصمیم گیری^[113] مدل حاصل اصلاح شده است تا تمایل و سوگیری^[114] آن به سمت کلاس اکثریت (منفی) حذف شود. تابع تصمیم گیری SVM استاندارد داده شده در فرمول (2-33)را در نظر بگیرید که می ­تواند به صورت زیر باز نویسی شود :

(2-37)
که ضریب بردارهای پشتیبان مثبت، وضریب بردارهای پشتیبان منفی است.M₁و M₂ نیز بیانگر تعداد نمونه های آموزشی مثبت و منفی هستند.در این روش، شدت مقادیر از بردارهای پشتیبان مثبت، با ضرب همه آنها در مقدار کوچک مثبتی به نام z ، افزایش می یابد.سپس تابع تصمیم تغییریافته را می­توان به شرح زیر بیان کرد :

(2-38)
این تغییر باعث افزایش وزن بردارهای پشتیبان مثبت در تابع تصمیم گیری می شود و درنتیجه تمایل به سمت کلاس منفی اکثریت کاهش می­یابد.
2-9-3-4 روش­های اصلاح کرنل ^[115]
در این روش ها، حساسیت الگوریتم SVM نسبت به عدم توازن کلاس از طریق اصلاح عملکرد تابع هسته مرتبط^[116] کاهش می­یابد.از جمله این روش ها می­توان به همترازی مرز کلاس^[117] ،همترازی هدف کرنل^[118]درجه بندی حاشیه ^[119] اشاره کرد.در بسط این روش، تابع هدف SVM به گونه ای تغییر می­یابد که این تغییر هم بر حسب جریمه و هم بر حسب حاشیه خواهد بود.در این صورت اگر در مرز تصمیم سوگیری وجود داشته باشد، می­توان آن را بهبود داد]29[.همچنین تکنیک هایی در زمینه کلاسه بندهای مبتنی بر کرنل^[120] ارائه شده است که برخی عبارتند از: الگوریتم ساخت کلاسه بند کرنل بر حسب OFS^[121] و براوردکننده ^[122]ROWLS ، الگوریتم KNG^[123]برای خوشه بندی نامتوازن]30[، الگوریتم P2PKNNC بر مبنای K نزدیک ترین همسایه و الگوی ارتباطیp2p ]31[، ماشین بردار رابط^[124]AdaBoost ]32[ و موارد دیگر.
2-9-3-5 یادگیری فعال^[125]
روش های یادگیری فعال نیز به عنوان روشی برای حل مشکل عدم توازن برای SVM ، ارائه شده است و با روش های مرسوم متفاوت است.استراتژی یادگیری فعال موثری برای غلبه بر مشکل ارائه شده است.این روش به صورت متناوب از بین داده آموزشی مشاهده نشده، نزدیک ترین نمونه به ابر صفحه جدا کننده را انتخاب می­ کند و ان را به مجموعه آموزشی می افزاید.این کار برای اموزش مجدد کلاسه بند صورت می­گیرد.با انتخاب معیار توقف زودهنگام، این متد می ­تواند زمان آموزش را به طرز قابل توجهی در مجموعه داده های نامتوازن بزرگ مقیاس کاهش دهد]33[.

2-9-3-6 روش های ترکیبی

علاوه بر روش های بالا، روشی تحت عنوان FSVM-CIL ارائه شده است که از مفاهیم فازی برای برخورد با مشکل عدم توازن کلاس استفاده می­ کند که در فصل بعد به مرور آن می­پردازیم.همچنین برخی روش­ها برای حل مشکل عدم توازن از ترکیب روش­های خارجی و داخلی استفاده کردند.به عنوان مثال، روش HKME^[126]، برای حل این مشکل از ترکیب SVM استاندارد باینری و کلاسه بند one-class SVM استفاده می­ کند]35[.
در روشی دیگر، الگوریتم SMOTE با متدDEC ترکیب شده است که کارایی بهتری را نسبت به استفاده جداگانه از هر کدام از این روش ها نشان می­دهد]18[.

فصل سوم:

روش تحقیق

3-1مقدمه

الگوریتم های متفاوتی برای بهبود SVM و بهبود نتایج ارائه شده است. در فصل قبل ماشین بردار پشتیبان و همچنین مفاهیم فازی و تکنیک حداقل مربعات را شرح دادیم.در این فصل به بررسی الگوریتم های ماشین بردار پشتیبان حداقل مربعات^[127](LS-SVM) و ماشین بردار پشتیبان فازی^[128](FSVM) می­پردازیم.
3-2 ماشین بردار پشتیبان فازی برای یادگیری عدم توازن کلاس^[129]
مطالعات به خوبی نشان می دهد که SVM علاوه بر عدم تعادل، به نویز و داده های پرت موجود در مجموعه داده نیز حساس است.بنابراین می توان ادعا کرد که اگرچه روش های یادگیری عدم تعادل موجود می­توانند باعث کاهش حساسیت الگوریتم SVM به عدم توازن شوند، اما این الگوریتم هنوز به نویز و داده های پرت موجود در مجموعه داده حساس است که هنوز باعث تولید مدل هایی با بهینگی کمتر از حد مطلوب می­ شود.در واقع برخی از روش های یادگیری عدم تعادل مانند بیش نمونه برداری تصادفی و SMOTE، با تکثیر نمونه های نویزی و داده های پرت موجود، می­توانند مشکل را بدتر کنند.
روش ماشین بردار پشتیبان فازی برای یادگیری عدم توازن کلاس(FSVM-CIL)، یک روش بهبود یافته ازSVM است که مسئولیت رسیدگی به مشکل عدم توازن کلاس و همچنین داده های نویزی و پرت را دارد]34[.اکنون این روش را با جزئیات بیشتر مورد بررسی قرار می­دهیم.

3-2-1 روش SVMFuzzy

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