بخشی از مقاله
چکیده
طبقهبندی دادههای نامتعادل یکی از مسائل مورد توجه در جامعه تحقیقاتی یادگیری ماشین و تشخیص الگو است. داده نامتعادل دادهای است که در آن در یک کلاس که معمولا اهمیت بیشتری دارد داده بسیار اندک است. یکی از روشهای برخورد با عدم تعادل پیشپردازش دادهها به دو شکل نمونهزدایی و نمونهافزایی است. نمونهافزایی مشکل یادگیری افزونه و نمونهزدایی مشکل حذف دادههای با اهمیت را دارد. در این تحقیق روشی ترکیبی مبتنی بر نمونه زدایی و نمونه افزایی ارائه می شود.نتایج بر روی دادههای استاندارد نشان می دهد که این روش در مقایسه با چند روش مشابه با معیار AUC نتایج را بهبود داده است.
.1 مقدمه
با افزایش حجم دادهها، طبقه بندی یکی از مسائل مهم در دادهکاوی محسوب میشود، خصوصا که دادههای دنیای واقعی دارای پیچیدگی و پارامترهای فراوانی است. از طرف دیگر عدم تعادل دادهها یکی از مسائل معمول در دنیای واقعی بحساب میاید که دادههای کلاس اقلیت معمولا دادههای کمیاب ولی بسیار با اهمیتی هستند که نمونههای کمتری نسبت به دیگر کلاسها دارند و هدف در طبقه بندی این نوع دادهها جبران یادگیری ضعیف در دادههای کلاس اقلیت است.
در اینجا تمرکز روی مسائل طبقهبندی دو کلاسه است. از کاربردهای کلاسبندی میتوان بازاریابی، تشخیص بیماری، تحلیل اثرات معالجه، تشخیص خرابی در صنعت و تعیین اعتبار را نام برد. راه حل های مربوط به طبقه بندی نامتعادل را می توان در سه گروه تقسیم کرد:
- 1 روش های حساس به هزینه که نیازمند تعیین هزینه است و اغلب در مجموعه دادهی طبقه بندی استاندارد یافت نمیشود و از طرفی تنظیم آنها بطور مناسب نیز مشکل است.
- 2 روشهای سطح الگوریتم که یادگیری و ساخت مدل در این سطح بدست میآید. بنابراین این دیدگاه سعی بر تنظیم الگوریتمهای یادگیری موجود با تمایل به یادگیری کلاس اقلیت دارد. این متد برای درک آنکه چرا طبقه بند در توزیع نامتعادل شکست میخورد، نیازمند دانش خاصی از محدودهی کلاسبند و کاربرد است.
- 3 روش های در سطح داده فضای جستجو را با افزایش نمونههای کلاس اقلیت و یا کاهش نمونههای کلاس اکثریت متوازن میسازد. به این ترتیب از اصلاح الگوریتم یادگیری خودداری میشود و سعی بر کاهش تاثیرات عدم تعادل از طریق تکنیکهای پیشپردازش می-شود.بدینترتیب این روش مستقل از نوع کلاسبند است و بههمین دلیل تطبیق پذیرتر است
در دسته روشهای سطح الگوریتم، در [1] برای تشخیص زودرس سرطان یک روش طبقه بندی ترکیبی حساس به هزینه معرفی شده است. رویکرد اصلی این روش مجموعه ای از درخت های تصمیم گیری حساس به هزینه است،که به کلاس بدخیم هزینه طبقه بندی بالاتری را نسبت میدهد.
در [2] یک روش اجماع جدیدمعرفی شده است که ابتدا مجموعه داده های نامتعادل را به چندین مجموعه متعادل تبدیل می کند وسپس چندین طبقه بند را با یک الگوریتم طبقه بندی خاص ایجاد میکند.این روش با روش نمونه گیری معمولی و یک روش یادگیری حساس به هزینه و چند روش اجماع boostingو bagging مقایسه می شود.
در[3] اجماعی از طبقه بندهای نامتعادل 2کلاسه به نام Random Balance معرفی می شود.هر مجموعه از این اجماع به روش SMOTE آموزش داده می شود و نسبت کلاس ها در هر مرحله به صورت تصادفی می باشد.
الگوریتم های سطح داده شامل دو نوع نمونه افزایی 1 و نمونه زدایی2 میباشد.درروش های نمونهزدایی اطلاعات مفیدی از کلاس اکثریت بطور دائم از دست میرود.
از الگوریتم های نمونه افزایی می توان به الگوریتم SMOTEاشاره کرد [4]که نمونههای جدید را براساس شباهت به نمونههای جاری کلاس اقلیت ایجاد می کند.یکی دیگر از روشهای نمونهافزایی Adaptive Synthetic Sampling - ADASYN - است[5]، ایدهی اصلی این روش آن است که نمونههای کلاس اقلیت را برطبق توزیعشان تولید کنیم، که اغلب دادههای جدید بهجای دادههای "راحت" برای دادههای "مشکل" ایجاد میشود.
از الگوریتم های نمونه زدایی الگوریتم نمونهزدایی تصادفی3 را می توان نام برد.این الگوریتم یک روش غیر هیوریستیک است که بصورت تصادفی نمونههایی از کلاس اکثریت را کم میکندتا زمانی که اندازه هر دو کلاس برابر شود.
1CNN روش کاهش نمونهای است که سعی بر یافتن و حذف نمونههای دور از محدودهی تصمیمگیری دارد.
2ENN هر نمونهای که برچسب کلاس آن با برچسب کلاس حداقل سه تا از نزدیکترین همسایگانش متفاوت است، حذف میکند.[7]در [8] در مرحله اول کﻻس اقلیت با پروسه SMOTE سعی بر افزایش نمونهها کردهاست. سپس الگوریتم ممتیک در هر تکامل نمونههایی را تولید میکند
در مقالات دیگری Chen نوع دیگری از ترکیب SMOTE و PSO را در کلاسبندهای RBF استفاده کرده است
روشهای مختلف نمونهافزایی و نمونهزدایی دارای ایراداتی هستند. در الگوریتم های نمونهزدایی اطلاعات مفیدی از کلاس اکثریت را بطور دائم از دست میرود. الگوریتم نمونه-افزایی بدلیل تولید داده های جدید و تزریق آنها به مجموعه داده دارای مشکل یادگیری افزونه است و بهمین دلیل است که مدل یادگیری حاصل تطبیق بیشتری با کلاس اقلیت خواهد داشت.
به منظور غلبه بر مشکلات روش های نمونهافزایی و نمونهزدایی می توان از روشهای تجمیع استفاده کنیم. این روشها می-توانند به بهترین نحو از مزایای الگوریتمهای ترکیبی بهره ببرند و معایب آنها را تا حد ممکن کاهش دهند.
اجماع برای افزایش صحت یک طبقه بندتوسط آموزش چندین طبقه بند مختلف و ترکیب خروجی آن ها به عنوان یک تصمیم نهایی است.اما این روش یادگیری به تنهایی مشکل عدم تعادل طبقه بند را حل نمی کند.بنابراین از تکنیک های سطح داده همرا با اجماع استفاده می شود.
در اینجا به طور مختصر چند روش اجماع را مرور می کنیم:
در هر مرحله از اجماع نیمی از داده های کلاس اکثریت و بقیه نمونه ها توسط الگوریتم smote از کلاس اقلیت ایجاد می شوند. :
در هرمرحله از Bagging نمونه زدایی تصادفی از کلاس اکثریت انجام میشود در حالی که تمام نمونه های کلاس اقلیت باقی می ماند.
درهرمرحله از AdaBoost.M2 حذف تصادفی نمونه ها از کلاس اکثریت انجام میشود.وزن نمونه ها در مجموعه داده جدید نرمال میشود.
در هر مرحله با استفاده از SMOTE نمونه های مصنوعی از کلاس اقلیت تولید می شود و وزن های جدید به نمونه های جدید انتساب داده می شود. :
عملکرداین روش مانند UnderBaggingاست با این تفاوت که آموزش هر طبقه بندبرای هر bagجدید با استفاده از Adaboostانجام میشود.بنابراین طبقه بند نهایی مانند یک اجماع از اجماع ها است.
در این مقاله از روش های اجماع همراه با ترکیب الگوریتم های سطح داده استفاده می کنیم.بدینترتیب در فاز 1 الگوریتم پیشنهادی، ابتدا توسط یکی از الگوریتمهای نمونه افزایی با نرخ اجرا میشود. نرخ بگونهای انتخاب میشود که بطور کامل مسئولیت از بین بردن عدم تعادل را بعهده نخواهد داشت.
بعد از پایان فاز 1 همچنان مجموعه داده جدید نیاز به متعادل-سازی خواهد داشت. بعد از انجام این مرحله سعی اجرای آموزش تجمیعی برمبنای randomunder sampling و boosting میکنیم. هدف ما در این مرحله کارایی کلاسبند با ایدهی حذف نمونهی تکاملی است.
