در این روش برای افزایش نمونه ها در کلاس اقلیت به تولید نمونه های مصنوعی می­پردازیم. بیش نمونه برداری با تکرار(که از طریق کپی کردن نمونه های کلاس اقلیت ، آنها را تکثیر می­ کند) به طور بالقوه می ­تواند منجر به بیش برازش نمونه های کلاس اقلیت شود.برای غلبه بر این مشکل و گسترش ناحیه تصمیم گیری کلاس اقلیت از روش ایجاد نمونه های مصنوعی استفاده می­کنیم که در این روش به جای استفاده از فضای داده، از فضای ویژگی استفاده می شود. درواقع هر نمونه از کلاس اقلیت انتخاب شده و نمونه های مصنوعی با در نظر گرفتن همه/هر K نزدیک ترین نمونه از کلاس اقلیت که در امتداد خطی به هم می­پیوندند، تولید می­شوند.بسته به میزان بیش نمونه برداری مورد نیاز، همسایگانی از K نزدیک ترین همسایه انتخاب می­شوند.نمونه مصنوعی به صورت زیر تولید می شود : ابتدا نگاهی به تفاوت بین بردار ویژگی ( نمونه ) مورد نظر و نزدیکترین همسایه آن می اندازیم. سپس این تفاوت در عددی تصادفی بین صفر تا یک ضرب شده و آن را به بردار ویژگی اضافه می­کنیم. به طور معمول، نمونه برداری با تکرار باعث ایجاد مناطقی کوچک برای تصمیم گیری می­ شود اما با بهره گرفتن از نمونه های مصنوعی مناطق بزرگتری برای تصمیم گیری خواهیم داشت]38[.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

هنگامی که مجموعه های داده به شدت اریب هستند، برای بهبود تعمیم یادگیرنده از ترکیب روش­های بیش نمونه برداری و زیرنمونه برداری استفاده می­ شود.به عنوان مثال زمانی که مجموعه داده به شدت نامتوازن است و یا نمونه های کمی برای کلاس اقلیت وجود دارد، میتوان با ترکیب روش های SMOTE و Tomek Link ، و همچنین ترکیب روش های SMOTE و ENN به نتیجه بهتری دست یافت]36[.

2-9-2-1-6 نزدیک ترین همسایه فشرده^[91](CNN)

رویکرد اصلی روش CNN مانند روش نزدیک ترین همسایگی(NN)^[92] است اما تنها از زیرمجموعه­ای از نمونه های آموزشی استفاده می­ کند.این زیرمجموعه زمانی که به عنوان یک مجموعه مرجع ذخیره شده برای تصمیم گیری نزدیک ترین همسایگی مورد استفاده قرار گرفت، باعث شد که تمام نمونه های متعلق به مجموعه آموزشی اصلی به درستی طبقه بندی شوند.
در روش نزدیک ترین همسایگی، نمونه ورودی به دسته ای اختصاص می­یابد که اکثریت را در N همسایه نزدیک این نمونه دارد.قاعده ساده و در عین حال قدرتمند است و زمانی که تعداد نمونه­ها نامحدود باشد، ریسک این روش هرگز بدتر از دوبرابر ریسک روش bayes نیست.اما برای طبقه بندی یک نمونه آزمون، باید تمام نمونه های برچسب دار مجموعه آموزشی جستجو شوند.روش NN انباره بزرگ و نیازهای محاسباتی را تحمیل می­ کند]39[.
روش CNN برای کاهش و خلاصه کردن مجموعه اموزشی و پیدا کردن مهم ترین مشاهدات به کار می­رود که از این مشاهدات برای طبقه بندی هر مشاهده جدید استفاده خواهد شد.این امر به شدت تعداد مقایسه ها برای طبقه بندی یک مشاهده جدید را می­کاهد، در حالی که دقت را تنها کمی کاهش می­دهد.
روش کار بدین صورت است که داده ها به 3 نوع متفاوت تقسیم می­شوند:

1. 1. Outliers : یک داده پرت مشاهده ای است که بطور غیر عادی یا اتفاقی از وضعیت عمومی داده ­های تحت آزمایش و نسبت به قاعده ای که براساس آن آنالیز می­شوند، انحراف داشته است.

1. 1. Prototype : حداقل مجموعه آموزشی که مورد نیاز است تا همه نقاط غیر پرت دیگر به درستی تشخیص داده شوند.

1. 1. Absorbed points : نقاطی که پرت نیستند و بر اساس مجموعه نقاط پروتوتایپ به درستی تشخیص داده می­شوند.

بنابراین ما فقط نیاز به مقایسه مشاهدات جدید با نقاط پروتوتایپ داریم.
الگوریتم این روش به صورت زیر خلاصه میشود :

1. 1. نقاط موجود در مجموعه آموزشی را به نوبت حذف کرده، و سپس چک میکنیم آیا کلاس آن به درستی تشخیص داده شده یا خیر؟

• • اگر چنین باشد آن نقطه را دوباره در مجموعه قرار می دهیم

• • اگر نباشد، پس نتیجه میگیریم که داده ای پرت است و نباید در مجموعه گذاشته شود.

1. 1. یک پایگاه داده جدید ایجاد کرده و نقطه ای تصادفی به آن اضافه میکنیم.

1. 1. تمام نقاط موجود در مجموعه اصلی را انتحاب میکنیم،و سپس چک میکنیم که آیا بر اساس نقاط موجود در پایگاه داده جدید کلاس این نقاط به درستی تشخیص داده شده است؟، از KNN=1 استفاده میکنیم،

• • اگر چنین است نتیجه میگیریم که این یک نقطه جذب است و میتوانیم آن را از پایگاه داده جدید کنار بگذاریم

• • اگر چنین نباشد باید از مجموعه اصلی حذف شود و به پایگاه داده جدید از پروتوتایپ اضافه شود.

1. 1. به همین منوال در مجموعه اصلی پیش می رویم.

1. 1. مراحل 3 و4 را تکرار کنید تا زمانی که هیچ نمونه پروتوتایپ جدیدی اضافه نشود]39[.

این الگوریتم به زمان اجرای زیادی نیاز دارد زیرا باید تکرارها نگه داشته شود. همچنین CNN کاملا تحت تاثیر داده های مغشوش در مجموعه آموزشی قرار میگیرد.

2-9-2-1-7 نزدیک ترین همسایه تغییر یافته(ENN)^[93]

بر اساس روش ENN ویلسون، قانون پاک سازی همسایه برای حذف و یا از بین بردن نمونه های کلاس اکثریت پیشنهاد شده است.در این روش به منظور زیر نمونه برداری داده ها ، نمونه های نویزی از کلاس اکثریت حذف می­شوند.در این روش اگر برچسب نمونه ای با حداقل دو همسایه (از سه نزدیکترین همسایه) متفاوت باشد، آنگاه این نمونه حذف می­ شود. حالت متفاوتی از ENN ،^[94]NCL نامیده می­ شود. در این روش در زمان پاکسازی مجموعه داده، با نمونه های کلاس اقلیت و اکثریت به صورت جداگانه­ ای رفتار می­ شود.NCL برای حذف نمونه های اکثریت از روش ENN استفاده می­ کند.برای هر نمونه E_i در مجموعه آموزشی، سه نزدیکترین همسایگان آن یافت می­ شود. اگر E_i متعلق به طبقه اکثریت است و طبقه بندی ارائه شده توسط سه نزدیکترین همسایه، با طبقه اصلی E_i در تضاد باشد، آنگاه E_i حذف می­ شود.اگر E_i متعلق به کلاس اقلیت است و سه نزدیکترین همسایگان آن، E_i را به نادرستی طبقه بندی کنند، سپس نزدیک ترین همسایگان متعلق به کلاس اکثریت حذف خواهند شد ]36[.

2-9-2-1-8 Tomek-Link

این روش، یکی از تکنیک های پاکسازی داده است که برای حذف همپوشانی به کار می­رود.در این روش به نمونه هایی که در نزدیکی مرز قرار دارند توجه بیشتری می­ شود.به عنوان مثال ، دو نمونه E_i و E_j را در نظر بگیرید که به کلاس های متفاوت تعلق دارند.,d( E_j, E_i) فاصله این دو نمونه را نشان میدهد.جفت. ( E_i, E_j) یک Tomek Link نامیده می­ شود اگر نمونه ای مانند E₁ وجود نداشته باشد، به طوری که d(Ei,E1) < d(Ei, Ej) or d(Ej , E1) < d(Ei, Ej). اگر دو نمونه یک Tomek Linkرا تشکیل دهند، آنگاه یکی از این نمونه ها نویز است یا هر دو در کنار مرز قرار دارند.بنابراین می­توانیم از Tomek Link ها برای پاکسازی همپوشانی های ناخواسته بین کلاس ها استفاده کنیم و همه Tomek Link­ ها حذف می­شوند تا زمانی که همه جفت های نزدیک ترین همسایه، عضو یک کلاس باشند.لازم به ذکر است که Tomek Link، NCL و ENN بسیار وقت گیر هستند زیرا باید برای هر نمونه موجود در مجموعه داده، نزدیک همسایگان آن را یافت. بنابراین برای مجموعه داده های بزرگ قابل استفاده نیستند]36[.بنابراین با حذف نمونه های همپوشان می­توانیم خوشه های خوش تعریفی در مجموعه آموزشی ایجاد کنیم که به نوبه خود می ­تواند منجر به بهبود کارایی طبقه بندی شود.شکل (2-17) روش Tomek Link را نشان می دهد. برخی از کارهای ترکیبی انجام شده در این زمینه عبارتند از : نزدیک ترین همسایه فشرده و Tomek Link (Tomek Link +CNN) ، ترکیب SMOTE و ENN (SMOTE+ENN)، و همچنین ترکیب SMOTE و Tomek Link (SMOTE+Tomek Link). به عنوان مثال شکل (2-17) روش ترکیبی SMOTE+Tomek Link را برای حذف نقاط داده همپوشان نشان میدهد]15[. در قسمت (a) توزیع مجموعه داده اصلی نشان داده شده است که دارای همپوشانی در نمونه های اقلیت و اکثریت است. شکل (b)توزیع مجموعه داده بعد از اعمال روش SMOTE را نشان می دهد.شکل©، Tomek Link ها را در کادری مشخص کرده است و شکل (d) مجموعه داده را پس از اعمال پاکسازی نشان میدهد.

شکل (2-17)- (a) مجموعه داده اصلی. (b) مجموعه داده بعد از اعمال SMOTE. ) (c Tomek-Link های شناخته شده (d) مجموعه داده بعد از پاکسازی Tomek-Link ها]36[
2-9-2-2 روش­های یادگیری جمعی^[95]
یادگیری جمعی نیز به عنوان یک راه حل برای آموزش SVM با مجموعه داده نامتوازن بکار می­رود. به طور کلی، در این روش­ها، مجموعه داده های طبقه اکثریت به چندین زیر مجموعه داده^[96] تقسیم می­شوند به طوری که هر یک از این زیر مجموعه داده ها دارای تعداد یکسانی از نمونه ها به عنوان نمونه های طبقه اقلیت هستند.(تعداد نمونه های کلاس اقلیت در تمام زیرمجموعه داده ها یکسان است).این را میتوان با بهره گرفتن از نمونه گیری تصادفی با جایگزینی و یا بدون جایگزینی^[97] و یا از طریق روش­های خوشه بندی انجام داد.سپس مجموعه ای از کلاسه بندهای SVM توسعه داده شده و هر کدام از آنها با مجموعه داده مثبت یکسان و زیر مجموعه داده منفی متفاوت آموزش داده می­شوند.در نهایت با بهره گرفتن از روشی مانند رای گیری اکثریت^[98]، تصمیمات اتخاذ شده توسط کلاسه بندها با یکدیگر ترکیب می­شوند]20[.
در واقع روش های یادگیری جمعی به طور وسیعی در ارتباط با مشکل عدم توازن کلاس به کار می روند. این روش ها، نتایج کلاسه بند ها را با هم ترکیب می­ کنند.در این گروه، روش های Boosting و Bagging جز برتـرین روش ها هستند.در ادامـه برخی از روش هـای این گروه را مختصر توضیح می­دهیم.

2-9-2-2-1الگوریتم آموزشی Bagging

این الگوریتم از مفهوم Bootstrap Aggregatingدر ایجاد تخمین­هاي مختلف استفاده نموده است. اصولاً می­تـوان از تـکنیک فوق به منـظور ارزیابی دقت تخمین­هاي بکار گرفته شده در روش­هاي داده­کاوي از طریق نمونه برداري با جایگزینی از داده‌هاي آموزشی استفاده نمود. در این تکنیک فرض بر آنست که مجموعه‌داده هاي آموزشی نماینده جامعه تحت بررسی بوده و انواع حالات تحقق یافته جامعه را می­توان از این مجموعه داده شبیه سازی نمود. بنابراین با بهره گرفتن از دوباره نمونه برداری توسط به کارگیری مجموعه داده‌های مختلف تنوع مورد نیاز حاصل خواهد شد و زمانی که یک نمونه جدید وارد هرکدام از کلاسه بندها می‌شود، توافق اکثریتی به کار گرفته می‌شود تا کلاس مورد نظر تشخیص داده شود.به عنوان یک روش از bagging میتوان pasting small votes را نام برد که عموما برای مجموعه داده‌های حجیم طراحی شده است. این مجموعه داده‌ها به زیرمجموعه‌های کوچکتری تقسیم می‌شوند که به منظور آموزش دسته‌کننده‌های گوناگون به کار می‌رود. در این حالت دو نوع مختلفRvotes و Ivotes وجود دارند که اولین مقدار، زیرمجموعه‌هایی به صورت تصادفی ایجاد می‌کند و دومین مقدار زیرمجموعه‌های متوالی بر پایه اهمیت این نمونه‌ها ایجاد می‌کند.نمونه‌های مهم هم آن نمونه‌هایی هستند که موجب افزایش تنوع در مجموعه داده می‌شوند.استفاده از توزیع موزون داده‌های ضعیف و سخت است که باعث ساخت مجموعه داده می‌شود.داده‌های سخت^[99]توسط کلاسه بندهای out-of-bag شناسایی می‌شوند، به طوری که زمانی یک نمونه “سخت” در نظر گرفته می‌شود که توسط ensemble به صورت اشتباه کلاسه بندی شده است. این داده‌های سخت همیشه به مجموعه داده‌های بعدی اضافه می‌شوند در حالی که داده‌های آسان شانس کمی برای داخل شدن به مجموعه داده‌ها را دارند]15[.

2-9-2-2-2 الگوریتم آموزشی Boosting