فصل۳: دادههای نامتوازن
۳-۱٫ مقدمه
اغلب الگوریتمهای ردهبندی، فرض میکنند که توزیع ردهها یکسان است و در صورتیکه توزیع ردهها نامتوازن باشد، این الگوریتمها در تشخیص خود دچار مشکل میشوند و ردهی اقلیت که تعداد دادههای آن بسیار کم است، اغلب نادیده انگاشته میشود. نمونهای از این مسائل نامتوازن، بیماری مزمن انسدادی ریه است؛ که یکی از انواع بیماری تنفسی میباشد.
در این فصل روشهای یادگیری در دادههای نامتوازن و معیارهای ارزیابی مناسب برای مسائل نامتوازن را بررسی میکنیم.
۳-۲٫ روشهای یادگیری در دادههای نامتوازن
در دنیای واقعی، معمولا دادهها نامتوازن هستند. بهطوریکه برخی از ردهها، تعداد نمونههای بیشتری نسبت به سایر ردهها دارند. البته درجهی عدم توازن (نسبت تعداد نمونههای ردهی اکثریت به تعداد نمونههای ردهی اقلیت) ممکن است کم یا زیاد باشد. اغلب الگوریتمهای ردهبندی، فرض میکنند که توزیع ردهها یکسان است و در صورتیکه توزیع ردهها نامتوازن باشد، این الگوریتمها در تشخیص خود دچار مشکل شده و عملا بهسمت ردهی اکثریت متمایل میشوند و ردهی اقلیت که تعداد دادههای آن بسیار کم است، اغلب نادیده انگاشته میشود [۴۹].
۳-۲-۱٫ نمونهبرداری
نمونهبرداری، یکی از روشهای غلبه بر مشکلات یادگیری در دادههای نامتوازن است. در این روش، با هدف متوازنسازی مجموعهی داده، از یکسری مکانیسمهایی برای تغییر مجموعه دادهی نامتوازن استفاده میشود. مطالعات نشان میدهد که اغلب ردهبندهای پایه، روی دادهی متوازن بهتر عمل میکنند [۵۰, ۵۱] و این یک دلیل قانعکننده برای استفاده از تکنیک نمونهبرداری است. دو رویکرد مختلف در نمونهبرداری وجود دارد: بیشنمونهبرداری و زیرنمونهبرداری [۴۹].
۳-۲-۱-۱٫ بیشنمونهبرداری تصادفی[۵۸]
در بیشنمونهبرداری تصادفی، یک مجموعهی تصادفی از ردهی اقلیت، به مجموعهی آموزش اضافه میشود و به این ترتیب توازن در مجموعهی آموزش برقرار میشود. با تعیین تعداد نمونههایی از ردهی اقلیت که بهصورت تصادفی انتخاب شده و به مجموعهی آموزش اضافه میشوند، میتوان درجهی عدم توازن موردنظر را در مجموعهی آموزش نهایی بهدست آورد.
۳-۲-۱-۲٫ زیرنمونهبرداری تصادفی[۵۹]
در زیرنمونهبرداری تصادفی، برخلاف بیشنمونهبرداری، یک مجموعه از نمونههای ردهی اکثریت بهصورت تصادفی انتخاب شده و از مجموعهی آموزش حذف میشوند و به این ترتیب توازن در مجموعهی آموزش برقرار میشود.
۳-۲-۱-۳٫ نمونهبرداری آگاهانه[۶۰]
در نگاه اول بهنظر میرسد که عملکرد هر دو روش زیرنمونهبرداری و بیشنمونهبرداری، یکسان است اما هریک از این دو روش، مشکلاتی را ایجاد میکند. در زیرنمونهبرداری، با حذف تعدادی از نمونههای ردهی اکثریت، ممکن است ردهبند برخی از مفاهیم مهم مربوط به ردهی اکثریت را از دست بدهد. در بیشنمونهبرداری، بهدلیل تکرار برخی از نمونههای ردهی اکثریت، مشکل بیشبرازش اتفاق میافتد [۵۲] یعنی علیرغم صحت بالای ردهبند در مجموعهی آموزش، کارایی ردهبند روی دادههای آزمون، مناسب نخواهد بود.
روش نمونهبرداری آگاهانه، برای غلبه بر این مشکلات ارائه شده است. الگوریتمهای 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 

دانلود متن کامل این پایان نامه در سایت abisho.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|