فصل۳: داده های نامتوازن
۳-۱٫ مقدمه
اغلب الگوریتمهای ردهبندی، فرض میکنند که توزیع رده ها یکسان است و در صورتیکه توزیع رده ها نامتوازن باشد، این الگوریتمها در تشخیص خود دچار مشکل میشوند و ردهی اقلیت که تعداد داده های آن بسیار کم است، اغلب نادیده انگاشته میشود. نمونهای از این مسائل نامتوازن، بیماری مزمن انسدادی ریه است؛ که یکی از انواع بیماری تنفسی میباشد.
در این فصل روش های یادگیری در داده های نامتوازن و معیارهای ارزیابی مناسب برای مسائل نامتوازن را بررسی میکنیم.
۳-۲٫ روش های یادگیری در داده های نامتوازن
در دنیای واقعی، معمولا داده ها نامتوازن هستند. بهطوریکه برخی از رده ها، تعداد نمونه های بیشتری نسبت به سایر رده ها دارند. البته درجهی عدم توازن (نسبت تعداد نمونه های ردهی اکثریت به تعداد نمونه های ردهی اقلیت) ممکن است کم یا زیاد باشد. اغلب الگوریتمهای ردهبندی، فرض میکنند که توزیع رده ها یکسان است و در صورتیکه توزیع رده ها نامتوازن باشد، این الگوریتمها در تشخیص خود دچار مشکل شده و عملا بهسمت ردهی اکثریت متمایل میشوند و ردهی اقلیت که تعداد داده های آن بسیار کم است، اغلب نادیده انگاشته میشود [۴۹].
۳-۲-۱٫ نمونهبرداری
نمونهبرداری، یکی از روش های غلبه بر مشکلات یادگیری در داده های نامتوازن است. در این روش، با هدف متوازنسازی مجموعهی داده، از یکسری مکانیسمهایی برای تغییر مجموعه دادهی نامتوازن استفاده میشود. مطالعات نشان میدهد که اغلب ردهبندهای پایه، روی دادهی متوازن بهتر عمل میکنند [۵۰, ۵۱] و این یک دلیل قانعکننده برای استفاده از تکنیک نمونهبرداری است. دو رویکرد مختلف در نمونهبرداری وجود دارد: بیشنمونهبرداری و زیرنمونهبرداری [۴۹].
۳-۲-۱-۱٫ بیشنمونهبرداری تصادفی[۵۸]
در بیشنمونهبرداری تصادفی، یک مجموعهی تصادفی از ردهی اقلیت، به مجموعهی آموزش اضافه میشود و به این ترتیب توازن در مجموعهی آموزش برقرار میشود. با تعیین تعداد نمونه هایی از ردهی اقلیت که بهصورت تصادفی انتخاب شده و به مجموعهی آموزش اضافه میشوند، میتوان درجهی عدم توازن موردنظر را در مجموعهی آموزش نهایی بهدست آورد.
۳-۲-۱-۲٫ زیرنمونهبرداری تصادفی[۵۹]
در زیرنمونهبرداری تصادفی، برخلاف بیشنمونهبرداری، یک مجموعه از نمونه های ردهی اکثریت بهصورت تصادفی انتخاب شده و از مجموعهی آموزش حذف میشوند و به این ترتیب توازن در مجموعهی آموزش برقرار میشود.
۳-۲-۱-۳٫ نمونهبرداری آگاهانه[۶۰]
در نگاه اول بهنظر میرسد که عملکرد هر دو روش زیرنمونهبرداری و بیشنمونهبرداری، یکسان است اما هریک از این دو روش، مشکلاتی را ایجاد میکند. در زیرنمونهبرداری، با حذف تعدادی از نمونه های ردهی اکثریت، ممکن است ردهبند برخی از مفاهیم مهم مربوط به ردهی اکثریت را از دست بدهد. در بیشنمونهبرداری، بهدلیل تکرار برخی از نمونه های ردهی اکثریت، مشکل بیشبرازش اتفاق میافتد [۵۲] یعنی علیرغم صحت بالای ردهبند در مجموعهی آموزش، کارایی ردهبند روی داده های آزمون، مناسب نخواهد بود.
روش نمونهبرداری آگاهانه، برای غلبه بر این مشکلات ارائه شده است. الگوریتمهای EasyEnsemble و BalanceCascade، نمونه هایی از این روش هستند [۵۳, ۵۴]. هدف این دو الگوریتم، غلبه بر مشکل از دست رفتن اطلاعات هنگام استفاده از روش زیرنمونهبرداری است. الگوریتم EasyEnsemble، چندین مجموعه شامل نمونه هایی از ردهی اکثریت را که بهصورت تصادفی انتخاب شدهاند، تولید میکند سپس هریک از این مجموعه ها را با ردهی اقلیت ترکیب کرده و چندین ردهبند تولید میکند. سرانجام این ردهبندها با هم ترکیب شده و مدل نهایی را تشکیل میدهند. الگوریتم BalanceCascade نیز مشابه EasyEnsemble است با این تفاوت که پس از تولید هر ردهبند، نمونه هایی که توسط آن ردهبند درست تشخیص داده شدهاند، از مجموعه دادهی آموزش حذف میشوند. در این بخش به توضیح کامل دربارهی این الگوریتمها میپردازیم.
روش انتخاب یکطرفه[۶۱]، یکی دیگر از روش های زیرنمونهبرداری آگاهانه است [۵۵]. این روش، بهجای حذف تصادفی نمونه ها از ردهی اکثریت، تنها نمونه های اضافی یا نویزدار را از ردهی اکثریت حذف میکند.
۳-۲-۱-۳-۱٫ EasyEnsemble
اگر نمونه های ردهی اکثریت از مجموعهی آموزش را با N و نمونه های ردهی اقلیت آن را با P نمایش دهیم، زیرنمونهبرداری، زیرمجموعهیN′ را بهصورت تصادفی از N، نمونهبرداری میکند بهطوریکه |N′|˂|N|. معمولا برای مسائلی با عدم توازن بالا، حالت |N′|=|P| را انتخاب میکنیم که در نتیجه خواهیم داشت |N′|<<|N|.
از آنجائیکه در زیرنمونهبرداری، تنها از یک زیرمجموعه از نمونه های ردهی اکثریت جهت آموزش ردهبند استفاده میشود، فرایند آموزش بسیار کاراست. اما اطلاعات بالقوه مفیدی که در نمونه های نادیده گرفته شده وجود دارد، مورد غفلت واقع میشوند و این، ایراد اصلی زیرنمونهبرداری است. در الگوریتم EasyEnsemble راهکاری برای غلبه بر این مشکل معرفی شده است [۵۳, ۵۴]. ایدهی اصلی، ساختن ترکیبی از ردهبندهای بهدست آمده از آموزش زیرنمونه هایی از مجموعهی آموزش است بهطوریکه داده های نادیده گرفته شده، بتوانند کاوش شوند. شبهکد الگوریتم EasyEnsemble در شکل ۳-۱ آمده است.
{Input:
A set of minor class examples P,
a set of major class examples N, |P| < |N|, and
T, the number of subsets to be sampled from N.}
Method:
i ۰
repeat
i i + 1
Randomly sample a subset 

مطلب دیگر :
رساله عدل و انصاف- قسمت ۳۲

برای دانلود متن کامل این فایل به سایت torsa.ir مراجعه نمایید.

m>Ni from N, |Ni| = |P|.
Learn Hi using P and Ni. Hi is an AdaBoost ensemble with
weak classifiers hi,j and corresponding weights αi,j, i.e.
𝐻𝑖 (𝑥)= 𝑠𝑔𝑛 (𝛼𝑖, 𝑗𝑖,𝑗 (𝑥) – 𝜃𝑖 (.
until i = T
Output: An ensemble:
𝐻 (𝑥)= 𝑠𝑔𝑛 (𝛼𝑖, 𝑗𝑖, 𝑗 (𝑥) –).
شکل۳-۱: شبهکد الگوریتم EasyEnsemble [53 , 54]
در این روش، زیرمجموعه های N1 و N2 و … و NT بهصورت مستقل از مجموعهی N نمونهبرداری میشوند. برای هر زیرمجموعهی Ni ، ردهبند Hi با بهره گرفتن از Ni و P آموزش میبیند. سپس همهی ردهبندهای ایجاد شده، برای بهدست آوردن نتیجهی نهایی ترکیب میشوند. برای ترکیب ردهبندها از تکنیک Bagging استفاده میشود که در فصل دوم به آن پرداخته شد.
الگوریتمهای ردهبندی زیادی میتوانند برای ردهبندی هریک از زیرمجموعه ها مورد استفاده قرار بگیرندEasyEnsemble، در این مرحله از الگوریتم AdaBoost استفاده میکند که این الگوریتم نیز در فصل دوم معرفی شد.
۳-۲-۱-۳-۲٫ ModifiedBagging
ساختار این الگوریتم نیز مشابه الگوریتم EasyEnsemble میباشد. در این الگوریتم، زیرنمونه هایی از ردهی اکثریت تولید میشود. سپس هریک از این زیرنمونه ها با تمام نمونه های ردهی اقلیت ترکیب شده و مجموعهای برای آموزش ردهبند تولید میکنند. در نهایت نیز تمام ردهبندها با هم ترکیب شده و مدل نهایی را تولید میکنند. شبهکد موجود در شکل۳-۲، الگوریتم ModifiedBagging را معرفی میکند.
{Input:
A set of minority class examples Smin,
A set of majority class examples Smax, |Smin|<|Smax|