نمونه گیری به روش smote

نمونه گیری به روش smote

چکیده:

روشی برای ساخت طبقه بندها از مجموعه داده‌های نامتعادل توضیح داده شده‌است.

در صورت عدم تعادل دسته‌ها یک مجموعه داده نامتعادل است.

اغلب مجموعه‌های داده واقعی غالباً از نمونه‌های " عادی " با درصد کمی از نمونه‌های " غیرعادی " یا " جالب " تشکیل شده‌اند. همچنین این حالت وجود دارد که هزینه یک مثال عادی (جالب) به عنوان مثال عادی اغلب بسیار بیشتر از هزینه خطای معکوس است. طبقه اکثریت (معمولی) به عنوان ابزاری خوب برای افزایش حساسیت نسبت به طبقه اقلیت پیشنهاد شده‌است. این مقاله نشان می‌دهد که ترکیبی از روش بیشن نمونه گیری در طبقه اقلیت (غیر عادی) و تحت نمونه‌گیری اکثریت (معمولی) می‌تواند به طبقه‌بندی بهتری از طبقه اکثریت (در فضای roc) منجر شود.

این مقاله همچنین نشان می‌دهد که ترکیبی از روش بیش نمونه گیری طبقه اقلیت و طبقه زیر - طبقه اکثریت می‌تواند به طبقه‌بندی بهتری (در فضای roc) نسبت به تغییر نسبت زیان موجود در (roc یا گروه) در بیز ساده دست یابد. روش ما نسبت به طبقه اقلیت شامل ایجاد نمونه‌های کلاس اقلیت ترکیبی است.

آزمایش‌ها با استفاده از c4. الگوریتم Ripper and a Naive Bayesripper به‌کار می‌رود. این روش با استفاده از سطح زیر منحنی مشخصه عملکرد گیرنده (auc) و استراتژی پوسته محدب ارزیابی می‌شود.

مقدمه

یک مجموعه داده نامتعادل است اگر کلاس تقریباً به همان اندازه نمایش داده نشده باشد. نامتعادل به ترتیب ۱۰۰ تا ۱ متداول است در تشخیص تقلب و عدم تعادل بین ۱۰۰۰۰۰ تا ۱ در کاربردهای دیگر گزارش شده‌است (Provost Fawcett، ۲۰۰۱). تلاش‌هایی برای رسیدگی به داده‌های نامتعادل در حوزه‌هایی مانند تماس‌های تلفنی جعلی (Fawcett & Provost، ۱۹۹۶)، مدیریت ارتباطات راه دور (Ezawa، Singh، & Norton، ۱۹۹۴؛ Dumais، Grobelnik، ۱۹۹۴؛ Lewis، ۱۹۹۵) و کشف نشت نفت در تصاویر ماهواره‌ای انجام شده‌است (قباد، Holte، & Matwin، ۱۹۹۸).

کارایی الگوریتم‌های یادگیری ماشین معمولاً با استفاده از دقت پیش‌بینی ارزیابی می‌شود. با این حال، این کار زمانی مناسب نیست که داده‌ها نامتعادل باشند و یا هزینه‌های خطاهای مختلف به طور قابل‌توجهی متفاوت باشند. به عنوان مثال، طبقه‌بندی پیکسل را در تصاویر ماموگرافی که احتمالاً سرطانی هستند در نظر بگیرید (وودز، Doss، بائر، Solka، &، ۱۹۹۳). یک مجموعه داده ماموگرافی، ممکن است شامل ۹۸ درصد پیکسل معمولی و ۲ درصد نقطه غیر عادی باشد. یک استراتژی پیش‌فرض ساده برای حدس زدن طبقه اکثریت، دقت پیش‌بینی ۹۸ % را می‌دهد. با این حال، ماهیت برنامه نیاز به نرخ نسبتاً بالایی از تشخیص درست در طبقه اقلیت دارد و اجازه می‌دهد تا نرخ خطای کمی در کلاس اکثریت برای رسیدن به این هدف وجود داشته باشد. دقت پیش‌بینی ساده در چنین شرایطی مناسب نیست.

منحنی مشخصه گیرنده (ROC) یک تکنیک استاندارد برای خلاصه کردن عملکرد طبقه‌بندی کننده در محدوده‌ای از تعادل بین نرخ‌های خطای مثبت و مثبت کاذب (Swets، ۱۹۸۸) است. مساحت تحت این منحنی یک متریک عملکرد سنتی برای یک منحنی ROC است (Duda، هارت، & Stork، ۲۰۰۱؛ بردلی، ۱۹۹۷؛ لی، ۲۰۰۰). بدنه محدب ROC نیز می‌تواند به عنوان روشی قوی برای شناسایی کننده‌های بهینه بالقوه بالقوه مورد استفاده قرار گیرد (Provost Fawcett، ۲۰۰۱). اگر یک خط از یک نقطه بر روی بدنه محدب عبور کند، پس هیچ خط دیگری با شیب یک‌سان در یک نقطه دیگر با یک نقطه تقاطع مثبت حقیقی مثبت (TP) وجود ندارد. بنابراین، طبقه‌بندی کننده در این نقطه، تحت هر فرض توزیعی در کنار آن شیب بهینه است.

جامعه یادگیری ماشین مساله عدم تعادل کلاس را به دو روش مورد خطاب قرار داده‌است.

یکی برای تعیین هزینه‌های متمایز برای آموزش مثال‌ها است (Pazzani، Merz، مورفی، علی، هیوم، & Brunk، ۱۹۹۴؛ Domingos، ۱۹۹۹). دیگری برای نمونه مجدد مجموعه داده اصلی، یا با نمونه‌گیری از طبقه اقلیت و / یا تحت نمونه‌گیری از طبقه اکثر (قباد & Matwin، ۱۹۹۷؛ Japkowicz، ۲۰۰۰؛ Lewis & catlett، ۱۹۹۴؛ لینگ & لی، ۱۹۹۸). رویکرد ما (Chawla، بائر، هال، & Kegelmeyer، ۲۰۰۰) با نمونه‌ای خاص از نمونه‌گیری بیش از حد از طبقه اقلیت، تحت نمونه‌گیری طبقه‌ای اکثریت قرار گرفته‌است. آزمایش‌ها با مجموعه داده‌های مختلف و C۴. طبقه‌بندی کننده درخت تصمیم‌گیری (Quinlan، ۱۹۹۲)، ری پر (کوهن، ۱۹۹۵)، و یک مدل Naive بیز، نشان می‌دهد که رویکرد ما نسبت به دیگر رویکردهای نمونه‌گیری مجدد، تغییر نسبت تلفات، و استفاده از بدنه محدب و AUC (AUC) بهبود می‌یابد.

معیارهای عملکرد

عملکرد الگوریتم‌های یادگیری ماشین معمولاً توسط یک ماتریس درهم‌ریختگی که در شکل ۱ نشان‌داده شده‌است، ارزیابی می‌شود (برای یک مساله کلاس ۲). ستون‌ها طبقه پیش بینی شده هستند و سطرها کلاس واقعی هستند. در ماتریس درهم‌ریختگی، TN تعداد نمونه‌های منفی است.

مثبت پیش بینی شده

منفی پیش بینی شده

FP

TN

منفی واقعی

TP

FN

مثبت واقعی

در طبقه‌بندی صحیح (منفی‌های درست), fp تعداد نمونه‌های منفی است که به‌اشتباه دسته‌بندی شده‌اند (مثبت‌های کاذب), fn تعداد نمونه‌های مثبت طبقه‌بندی شده منفی (منفی کاذب) و tp (مثبت‌های درست) است.

دقت پیش‌بینی معیار عملکرد عموماً مرتبط با الگوریتم‌های یادگیری ماشین است و به صورت دقت = tp + tn) / (tp + fp + tn + fn) تعریف می‌شود. در زمینه داده‌های متعادل و هزینه‌های یک‌سان خطا, استفاده از نرخ خطا به عنوان یک معیار عملکرد منطقی است. میزان خطا از دقت بالایی برخوردار است. در حضور مجموعه داده‌های نامتوازن با هزینه خطای نابرابر, استفاده از منحنی roc یا روش‌های مشابه دیگر مناسب‌تر است.

منحنی ROC می‌تواند به عنوان نماینده خانواده بهترین محدوده‌های تصمیم‌گیری برای هزینه‌های نسبی TP و FP انتخاب شود. در منحنی ROC، X نشان‌دهنده % FP = FP / (TN + FP) و محور Y نشان‌دهنده % TP / (TP + فرست) است. نقطه ایده‌آل در منحنی ROC می‌تواند (۰،۱۰۰) باشد، که همه نمونه‌های مثبت به درستی طبقه‌بندی می‌شوند و هیچ مثال‌های منفی به عنوان مثبت نیستند. یکی از روش‌های منحنی ROC می‌تواند با دستکاری تعادل نمونه‌های آموزشی برای هر کلاس در مجموعه آموزشی باشد. شکل ۲ یک تصویر را نشان می‌دهد.

خط y = x سناریوی تصادفی کلاس را نشان می‌دهد. مساحت زیر ROC (AUC) یک معیار مفید برای عملکرد طبقه‌بندی کننده است زیرا مستقل از معیار تصمیم‌گیری انتخاب‌شده و احتمالات قبلی است. مقایسه AUC را می‌توان یک رابطه غالب بین طبقه‌بندی کننده‌ها ایجاد کرد. اگر منحنی ROC مقطعی باشد، میانگین AUC یک مقایسه میانگین بین مدل‌های (لی، ۲۰۰۰) است. با این حال، برای برخی توزیع‌های هزینه و هزینه خاص، طبقه‌بندی کننده‌ها که بیش‌ترین AUC را دارند ممکن است در واقع نیمه بهینه باشند. از این رو، ما همچنین بدنه محدب ROC را نیز محاسبه می‌کنیم، چون نقاط نشان‌داده‌شده روی بدنه محدب جمهوری چین به طور بالقوه بهینه هستند (Provost، Fawcett، & Kohavi، ۱۹۹۸؛ Provost Fawcett، ۲۰۰۱).

کار قبلی: مجموعه داده نامتعادل

Kubat و Matwin (۱۹۹۷) به طور انتخابی از طبقه اکثریتی استفاده کرده‌اند در حالی که جمعیت اصلی طبقه اقلیت را حفظ می‌کنند. آن‌ها از میانگین هندسی به عنوان یک معیار عملکرد برای طبقه‌بندی کننده استفاده کرده‌اند که می‌تواند به یک نقطه واحد در منحنی ROC مرتبط باشد.

نمونه‌های اقلیت به چهار دسته تقسیم شدند: برخی از نویز در منطقه تصمیم‌گیری طبقه مثبت، نمونه‌های مرزی، نمونه‌های تکراری و نمونه‌های ایمن تقسیم شدند. مثال‌های مرزی با استفاده از مفهوم لینک‌های Tomek شناسایی شدند (Tomek، ۱۹۷۶).

?

یکی دیگر از کارهای مرتبط، سیستم SHRINK را پیشنهاد داد که یک منطقه همپوشانی کننده اقلیت (مثبت) و اکثریت (منفی) را به عنوان مثبت طبقه‌بندی می‌کند؛ آن به دنبال "بهترین منطقه مثبت" است (قباد و همکاران، ۱۹۹۸).

Japkowicz (۲۰۰۰) در مورد تاثیر عدم تعادل در مجموعه داده‌ها بحث و تبادل نظر کرد. او سه استراتژی را ارزیابی کرد: نمونه‌برداری، نمونه‌گیری مجدد و یک طرح القای تشخیص مبتنی بر بازشناسی. ما بر رویکردهای نمونه‌گیری او تمرکز می‌کنیم. او داده‌های ۱ بعدی مصنوعی را برای اندازه‌گیری آسان و ساخت پیچیدگی مفهوم آزمایش کرد. دو روش نمونه‌گیری مجدد در نظر گرفته شد.

نمونه‌گیری مجدد تصادفی شامل نمونه‌گیری مجدد از کلاس کوچک‌تر تصادفی تا زمانی که تعداد زیادی از نمونه‌ها به عنوان نمونه بیشتر و "نمونه‌گیری مجدد متمرکز" شامل نمونه‌گیری مجدد فقط آن نمونه‌های اقلیت که در مرز بین اقلیت و اقلیت رخ داد، بود. نمونه‌گیری تصادفی به صورت تصادفی در نظر گرفته شد، که نمونه‌های رده اکثریت را به طور تصادفی نمونه‌گیری کرد تا تعداد آن‌ها با تعداد نمونه‌های طبقه اقلیت مطابقت داشته باشد. او اشاره کرد که هر دو روش نمونه‌گیری موثر بودند، و همچنین مشاهده کرد که با استفاده از تکنیک‌های نمونه‌گیری پیچیده، هیچ مزیت روشنی در این حوزه وجود ندارد (Japkowicz، ۲۰۰۰).

یک رویکرد که به ویژه مربوط به کار ما است این است که لینگ و لی (۱۹۹۸).

آن‌ها با نمونه‌گیری بیش از حد از طبقه اقلیت با نمونه‌گیری از طبقه اقلیت، ترکیب شدند. آن‌ها از آنالیز بالابر به جای دقت برای اندازه‌گیری عملکرد طبقه بندی استفاده کردند. آن‌ها پیشنهاد کردند که نمونه‌های تست با یک اندازه‌گیری مطمئن رتبه‌بندی شوند و سپس به عنوان معیارهای ارزیابی مورد استفاده قرار گیرند.

منحنی بالابر شبیه منحنی ROC است، اما برای مساله تحلیل بازاریابی مناسب‌تر است (لینگ & Li، ۱۹۹۸). در یک آزمایش، آن‌ها گروه اکثریت را نمونه‌گیری کردند و اشاره کردند که بهترین شاخص بالابر در زمانی بدست می‌آید که کلاس‌ها به همان اندازه نمایش داده شوند (لینگ & Li، ۱۹۹۸). در یک آزمایش دیگر، آن‌ها نمونه‌های مثبت (اقلیت) را با جایگزینی برای مطابقت با تعداد نمونه‌های مثبت (اکثریت) نمونه‌های مثبت آزمایش کردند. روش نمونه‌گیری بیش از نمونه‌گیری و نمونه‌برداری تحت نمونه‌گیری بهبود قابل‌توجهی در شاخص بالابر ارایه نداد. با این حال، رویکرد ما نسبت به نمونه‌گیری از نمونه‌گیری متفاوت است.

Solberg و Solberg (1996) به بررسی مساله مجموعه داده‌های نامتعادل در طبقه‌بندی روغن نرم از تصاویر SAR پرداخت. آن‌ها از تکنیک‌های نمونه‌گیری بیش از نمونه‌گیری و زیر نمونه‌گیری استفاده کردند تا طبقه‌بندی محصولات نفتی را بهبود بخشند. داده‌های آموزشی آن‌ها دارای توزیع ۴۲ شرکت نفت slicks و ۲,۴۷۱ شبیه بود که احتمال بیشتری از آلفای کرونباخ برای نگاه کردن به مشابهت ها داشت. این عدم تعادل باعث می‌شود که یاد گیرنده (بدون هیچ کدام از توابع خسارت مناسب و یا یک روش برای اصلاح و دسته‌بندی) به طور درست به هزینه نادرست بسیاری از نمونه‌های لغزنده نفت (Solberg & Solberg, 1996) هدایت شود. برای غلبه بر این مشکل عدم تعادل, آن‌ها نمونه‌گیری بیش از ۱۰۰ نمونه از لیز نفتی را به طور تصادفی نمونه‌برداری کردند و آن‌ها به طور تصادفی ۱۰۰ نمونه از کلاس غیر لغزنده را نمونه‌برداری کردند تا یک مجموعه داده جدید با احتمالات مساوی ایجاد کنند.

آن‌ها یک درخت طبقه‌بندی کننده را بر روی این مجموعه داده متوازن آموختند و به نرخ خطای ۱۴ % روی لیز نفتی در یک روش (یکی را خارج قرار دادن) برای تخمین خطا دست یافتند؛ در حالت شبیه به نرخ خطای ۴ % دست یافتند (Solberg & Solberg، ۱۹۹۶).

یک رویکرد دیگر که مشابه کار ما است مربوط به Domingos (1999) است. او رویکرد " metacost " را با هر کدام از اکثریت تحت نمونه‌گیری و اقلیت مقایسه می‌کند.

وی دریافته است که metacost در هر دو مورد بهبود یافته‌است، و این روش نمونه‌گیری ترجیح داده می‌شود که از نمونه‌گیری بیش از اندازه اقلیت برخوردار باشد. طبقه‌بندی کننده‌های مبتنی بر خطا نسبت به هزینه حساس هستند. احتمال هر کلاس برای هر نمونه تخمین زده می‌شود و مثال‌های آن به طور بهینه با توجه به هزینه‌های طبقه‌بندی طبقه‌بندی می‌شوند. برچسب‌دار مثال‌های فضای تصمیم را گسترش می‌دهد چون نمونه‌های جدیدی را ایجاد می‌کند که طبقه‌بندی کننده ممکن است یاد بگیرند (Domingos، ۱۹۹۹).

یک شبکه عصبی که در مجموعه داده نامتعادل آموزش‌دیده است ممکن است یادگیری بین کلاس‌ها را یاد بگیرد (DeRouin، Brown، fausett، & اشنایدر، ۱۹۹۱). نویسندگان پیشنهاد کردند که سرعت یادگیری شبکه عصبی با آمار نمایش کلاس در داده‌ها تطبیق داده شود. آن‌ها یک عامل توجه را از نسبت نمونه ارائه‌شده به شبکه عصبی برای آموزش محاسبه کردند. سرعت یادگیری عناصر شبکه براساس فاکتور توجه تنظیم شد. آن‌ها یک مجموعه آموزشی تولید شده مصنوعی و در یک مجموعه آموزشی واقعی، هم با چند کلاس (بیش از دو کلاس) را امتحان کردند. آن‌ها این مساله را با رویکرد تکرار نمونه‌های کلاس اقلیت برای متعادل کردن مجموعه داده مورد استفاده برای آموزش مقایسه کردند. دقت طبقه‌بندی در طبقه اقلیت بهبود یافت.

Lewis و catlett (۱۹۹۴) نمونه‌گیری عدم قطعیت ناهمگن برای یادگیری نظارت شده را بررسی کردند. این روش برای آموزش نمونه‌های آموزشی با کلاس‌های نامشخص مفید است. نمونه‌های آموزشی به صورت افزایشی در دو فاز برچسب گذاری می‌شوند و نمونه‌های نامشخص به فاز بعدی منتقل می‌شوند. آن‌ها C۴ را تغییر دادند. ۵ برای اضافه کردن نسبت تلفات برای تعیین مقادیر کلاس در برگ‌ها. ارزش‌های کلاس با مقایسه با آستانه احتمال LR / (LR + ۱) تعیین شدند، که در آن LR نسبت تلفات است (لوئیس & catlett، ۱۹۹۴).

بازیابی اطلاعات (IR) (Dumais و همکاران, 1998; Mladenic & Grobelnik, 1999; لوییس & Ringuette, 1994) نیز با مشکل عدم تعادل طبقاتی در مجموعه داده‌ها مواجه است. یک سند یا صفحه وب به یک نمایش از کلمات تبدیل می‌شود; یعنی, یک بردار ویژگی که منعکس‌کننده وقایع کلمات در صفحه است ساخته شده‌است. معمولا, نمونه‌های بسیار کمی از این گروه جالب در طبقه‌بندی متن وجود دارد. این حضور بیش از حد طبقه منفی در مشکلات بازیابی اطلاعات می‌تواند باعث بروز مشکلاتی در ارزیابی عملکرد طبقه‌بندی کننده‌ها شود. از آنجا که نرخ خطا, معیار خوبی برای مجموعه داده‌های انحرافی نیست, عملکرد طبقه‌بندی الگوریتم در بازیابی اطلاعات معمولاً با دقت اندازه‌گیری می‌شود و اینطور بیان می کند:

?

Mladenic و Grobelnik (۱۹۹۹) یک رویکرد انتخاب زیرمجموعه ویژگی را برای رسیدگی به توزیع نامتعادل در کلاس IR پیشنهاد کردند. آن‌ها روش‌های مختلف انتخاب ویژگی را امتحان کردند و دریافتند که نسبت احتمالات (ون Rijsbergen، هار پر، & پرتر، ۱۹۸۱) در ترکیب با یک طبقه‌بندی کننده بیز، بهترین عملکرد را در حوزه خود انجام می‌دهد. نسبت احتمال، معیار احتمالاتی است که برای رتبه‌بندی اسناد مطابق با ارتباط آن‌ها با طبقه مثبت (کلاس اقلیت) مورد استفاده قرار می‌گیرد. از طرف دیگر، کسب اطلاعات برای یک کلمه، به طبقه هدف خاص توجه نمی‌کند؛ در هر کلمه برای هر کلاس محاسبه می‌شود. در مجموعه داده‌ها نامتعادل (با فرض ۹۸ تا ۹۹ %، کلاس منفی است)، اغلب ویژگی‌ها مرتبط با طبقه منفی هستند. نسبت شرط، اطلاعات کلاس هدف را در معیار خود، در مقایسه با کسب اطلاعات برای طبقه‌بندی متن، نتایج بهتری می‌دهد.

Provost و Fawcett (1997) روش بدنه محدب ROC را برای تخمین عملکرد طبقه‌بندی کننده در مجموعه داده‌های نامتعادل معرفی کردند. آن‌ها توجه دارند که مشکلات توزیع طبقه نابرابر و هزینه‌های خطای نابرابر به هم مربوط هستند و این کار کوچک برای رسیدگی به این مشکل انجام شده‌است (Provost &, 2001). در روش ROC محدب, فضای ROC برای جدا کردن عملکرد طبقه‌بندی از کلاس و اطلاعات توزیع هزینه استفاده می‌شود.

برای خلاصه کردن متون درسی، طبقه متوسط ممکن است طبقه کننده‌های بهتری ساخته شوند تا نمونه‌گیری بیش از حد از طبقه اقلیت. ترکیبی از دو روش انجام‌شده در کار قبلی منجر به طبقه‌بندی کننده‌ها نمی‌شود که بهتر از آن‌هایی که تنها با استفاده از زیر نمونه گیری ساخته شده‌اند، عملکرد بهتری داشته باشند.

با این حال، نمونه‌گیری بیش از حد از طبقه اقلیت با نمونه‌گیری از داده‌های اصلی انجام شده‌است. رویکرد ما از روش متفاوتی از نمونه‌گیری بیش از نمونه‌گیری استفاده می‌کند.

SMOTE: تکنیک اقلیت مصنوعی بیش نمونه گیری

(لینگ & لی، ۱۹۹۸؛ Japkowicz، ۲۰۰۰) در مورد نمونه‌برداری با جایگزینی بحث و بررسی کرده و اشاره کرد که این موضوع به طور قابل‌توجهی به رسمیت شناختن طبقه اقلیت نیست.

ما تاثیر زیربنایی بر حسب مناطق تصمیم‌گیری در فضای ویژگی را تفسیر می‌کنیم. اساساً، همانطور که طبقه اقلیت با افزایش مقادیر نمونه‌گیری شد، تاثیر آن مشخص کردن مناطق خاص اما بیشتر در فضای ویژگی به عنوان منطقه تصمیم‌گیری برای طبقه اقلیت است این اثر برای درختان تصمیم‌گیری را می‌توان از قطعات در شکل زیر فهمید.

.?

شکل 3

داده‌های طرح در شکل 3 از a Mammography استخراج شد (وودز و همکاران، ۱۹۹۳). نمونه‌های طبقه اقلیت نشان داده می‌شود و نمونه‌های درجه اکثریت در نمودار نشان داده می‌شود. در شکل 3 (a)، منطقه‌ای که توسط مستطیل خط توپر نشان داده شده‌است، منطقه تصمیم‌گیری طبقه اکثریت است. با این وجود، این شامل سه نمونه طبقه اقلیت است که در "+" به عنوان نقاط منفی کاذب نشان‌داده شده‌است. اگر ما طبقه اقلیت را تکرار کنیم، منطقه تصمیم‌گیری برای طبقه اقلیت بسیار خاص می‌شود و باعث ایجاد شکاف جدید در درخت تصمیم‌گیری خواهد شد. این امر منجر به nodes بیشتر گره‌ها (برگ‌ها) به عنوان الگوریتم یادگیری برای یادگیری بیشتر و بیشتر در طبقه اقلیت، در اصل، بیش از حد پوشش داده می‌شود. تکرار کلاس اقلیت باعث نشد که مرز تصمیم‌گیری در منطقه اکثریت فراگیر شود. بنابراین، در شکل ۳ (b)، سه نمونه قبلی در منطقه تصمیم‌گیری طبقه اکثریت در حال حاضر مناطق تصمیم‌گیری بسیار ویژه‌ای دارند.

SMOTE

ما روش نمونه‌گیری بیش از اندازه را پیشنهاد می‌کنیم که در آن طبقه اقلیت با ایجاد نمونه‌های " مصنوعی " به جای نمونه‌گیری بیش از نمونه‌گیری مجدد نمونه‌گیری می‌شود. این رویکرد از تکنیکی الهام‌گرفته شده که در بازشناسی شخصیت دست‌نویس موفق شد (Ha & Bunke, 1997). آن‌ها داده‌های آموزشی اضافی را با انجام عملیات خاص بر روی داده‌های واقعی ایجاد کردند. در مورد آن‌ها, عملیاتی مانند چرخش و انحراف روش‌های طبیعی برای آشفته کردن داده‌های آموزشی بودند. ما مثال‌های ترکیبی را در یک روش کم‌تر با کاربرد کم‌تر, با عمل در " فضای ویژگی " به جای " فضای داده ", تولید می‌کنیم. طبقه اقلیت با در نظر گرفتن نمونه کلاس اقلیت و معرفی مثال‌های ترکیبی در امتداد بخش‌های خطی که به هر یک از نزدیک‌ترین همسایگان طبقه اقلیت ملحق می‌شوند, بیش از حد مورد نمونه‌گیری قرار می‌گیرد. بسته به مقدار مورد نیاز, همسایگان از نزدیک‌ترین همسایه به طور تصادفی انتخاب می‌شوند. در حال حاضر اجرای ما از پنج همسایه نزدیک استفاده می‌کند. به عنوان مثال, اگر مقدار نمونه‌گیری مورد نیاز ۲۰۰ % باشد, تنها دو همسایه از نزدیک‌ترین همسایه انتخاب می‌شوند و یک نمونه در جهت هر کدام ایجاد می‌شود. نمونه‌های مصنوعی به روش زیر تولید می‌شوند: تفاوت بین بردار ویژگی (نمونه) تحت بررسی و نزدیک‌ترین همسایه آن را در نظر بگیرید. این تفاوت را با اعداد تصادفی بین ۰ و ۱ ضرب کنید و آن را به بردار ویژگی اضافه کنید. این امر منجر به انتخاب یک نقطه تصادفی در امتداد بخش خطی بین دو ویژگی خاص می‌شود. این رویکرد به طور موثر منطقه تصمیم‌گیری طبقه اقلیت را تقویت می‌کند تا کلی‌تر شوند.

الگوریتم smote, در صفحه بعد, شبه کد است. جدول ۴.۲ نمونه‌ای از محاسبه نمونه‌های مصنوعی تصادفی را نشان می‌دهد. مقدار نمونه‌گیری بیش از نمونه‌گیری, پارامتری از سیستم است و یک سری از منحنی‌های ROC می‌تواند برای جمعیت‌های مختلف و تحلیل ROC ایجاد شود.

مثال‌های ترکیبی باعث می‌شود که طبقه‌بندی کننده برای ایجاد مناطق تصمیم‌گیری خاص و کم‌تر در شکل ۳ (c), به جای مناطق کوچک‌تر و بیشتر, مناطق تصمیم‌گیری خاص کم‌تر و کم‌تر را ایجاد کنند. در حال حاضر مناطق عمومی بیشتری برای نمونه کلاس اقلیت یاد گرفته می‌شوند و نه آن‌هایی که توسط نمونه‌های رده اکثریت در اطراف آن‌ها طبقه‌بندی شده‌اند. نتیجه این است که درخت‌های تصمیم‌گیری بهتر تعمیم می‌یابند. شکل‌های ۴ و ۵ گروه اقلیت را با جایگزینی و smote مقایسه می‌کنند. آزمایش‌ها بر روی مجموعه داده‌های ماموگرافی انجام شد.

نمونه‌های ۱۰۹۲۳ در کلاس اکثریت و ۲۶۰ نمونه در طبقه اقلیت وجود داشت. ما تقریباً ۹۸۳۱ نمونه در کلاس اکثریت و ۲۳۳ نمونه در کلاس اقلیت برای مجموعه آموزشی مورد استفاده در اعتبار سنجی متقابل ۱۰ برابر داریم. کلاس اقلیت به طور بیش از ۱۰۰ %, ۲۰۰ %, ۳۰۰ % و ۵۰۰ % از اندازه اصلی آن نمونه‌گیری شد. نمودارها نشان می‌دهند که اندازه درخت برای نمونه‌گیری بیش از اندازه با جایگزینی در درجات بالاتر کپی بسیار بزرگ‌تر از نمونه‌های smote است, و به رسمیت شناختن اقلیت بیش از حد با تکنیک جایگزینی در درجات بالاتر تکرار به اندازه smote خوب نیست.

Algorithm SMOTE(T, N, k)

Input: Number of minority class samples T; Amount of SMOTE N%; Number of nearest

neighbors k

Output: (N/100) * T synthetic minority class samples

1. (∗ If N is less than 100%, randomize the minority class samples as only a random

percent of them will be SMOTEd. ∗)

2. if N < 100

3. then Randomize the T minority class samples

4. T = (N/100) ∗ T

5. N = 100

6. endif

7. N = (int)(N/100) (∗ The amount of SMOTE is assumed to be in integral multiples of

100. ∗)

8. k = Number of nearest neighbors

9. numattrs = Number of attributes

10. Sample[ ][ ]: array for original minority class samples

11. newindex: keeps a count of number of synthetic samples generated, initialized to 0

12. Synthetic[ ][ ]: array for synthetic samples

(∗ Compute k nearest neighbors for each minority class sample only. ∗)

13. for i ← 1 to T

14. Compute k nearest neighbors for i, and save the indices in the nnarray

15. Populate(N, i, nnarray)

16. endfor

Populate(N, i, nnarray) (∗ Function to generate the synthetic samples. ∗)

17. while N 6= 0

18. Choose a random number between 1 and k, call it nn. This step chooses one of

the k nearest neighbors of i.

19. for attr ← 1 to numattrs

20. Compute: dif = Sample[nnarray[nn]][attr] − Sample[i][attr]

21. Compute: gap = random number between 0 and 1

22. Synthetic[newindex][attr] = Sample[i][attr] + gap ∗ dif

23. endfor

24. newindex++

25. N = N − 1

26. endwhile

27. return (∗ End of Populate. ∗)

End of Pseudo-Code.

منابع:

References

Blake, C., & Merz, C. (1998). UCI Repository of Machine Learning Databases

http://www.ics.uci.edu/∼mlearn/∼MLRepository.html. Department of Information

and Computer Sciences, University of California, Irvine.

Bradley, A. P. (1997). The Use of the Area Under the ROC Curve in the Evaluation of

Machine Learning Algorithms. Pattern Recognition, 30(6), 1145–1159.

Chawla, N., Bowyer, K., Hall, L., & Kegelmeyer, P. (2000). SMOTE: Synthetic Minority

Over-sampling TEchnique. In International Conference of Knowledge Based Com-

puter Systems, pp. 46–57. National Center for Software Technology, Mumbai, India,

Allied Press.

Chawla, N., & Hall, L. (1999). Modifying MUSTAFA to capture salient data. Tech. rep.

ISL-99-01, University of South Florida, Computer Science and Eng. Dept.

Cohen, W. (1995a). Learning to Classify English Text with ILP Methods. In Proceed-

ings of the 5th International Workshop on Inductive Logic Programming, pp. 3–24.

Department of Computer Science, Katholieke Universiteit Leuven.

Cohen, W. W. (1995b). Fast Effective Rule Induction. In Proc. 12th International Confer-

ence on Machine Learning, pp. 115–123Lake Tahoe, CA. Morgan Kaufmann.

Cohen, W. W., & Singer, Y. (1996). Context-sensitive Learning Methods for Text Categorization.

In Frei, H.-P., Harman, D., Sch¨auble, P., &Wilkinson, R. (Eds.), Proceedings

of SIGIR-96, 19th ACM International Conference on Research and Development in

Information Retrieval, pp. 307–315Z¨urich, CH. ACM Press, New York, US.

Cost, S., & Salzberg, S. (1993). A Weighted Nearest Neighbor Algorithm for Learning with

Symbolic Features. Machine Learning, 10(1), 57–78.

DeRouin, E., Brown, J., Fausett, L., & Schneider, M. (1991). Neural Network Training on

Unequally Represented Classes. In Intellligent Engineering Systems Through Artificial

Neural Networks, pp. 135–141New York. ASME Press.

Domingos, P. (1999). Metacost: A General Method for Making Classifiers Cost-sensitive.

In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge

Discovery and Data Mining, pp. 155–164San Diego, CA. ACM Press.

Drummond, C., & Holte, R. (2000). Explicitly Representing Expected Cost: An Alternative

to ROC Representation. In Proceedings of the Sixth ACM SIGKDD International

Conference on Knowledge Discovery and Data Mining, pp. 198–207 Boston. ACM.

Duda, R., Hart, P., & Stork, D. (2001). Pattern Classification. Wiley-Interscience.

Dumais, S., Platt, J., Heckerman, D., & Sahami, M. (1998). Inductive Learning Algorithms

and Representations for Text Categorization. In Proceedings of the Seventh

International Conference on Information and Knowledge Management., pp. 148–155.

Chawla, Bowyer, Hall & Kegelmeyer

Ezawa, K., J., Singh, M., & Norton, S., W. (1996). Learning Goal Oriented Bayesian

Networks for Telecommunications Risk Management. In Proceedings of the Interna-

tional Conference on Machine Learning, ICML-96, pp. 139–147Bari, Italy. Morgan

Kauffman.

Fawcett, T., & Provost, F. (1996). Combining Data Mining and Machine Learning for Effective

User Profile. In Proceedings of the 2nd International Conference on Knowledge

Discovery and Data Mining, pp. 8–13Portland, OR. AAAI.

Ha, T. M., & Bunke, H. (1997). Off-line, Handwritten Numeral Recognition by Perturbation

Method. Pattern Analysis and Machine Intelligence, 19/5, 535–539.

Hall, L., Mohney, B., & Kier, L. (1991). The Electrotopological State: Structure Information

at the Atomic Level for Molecular Graphs. Journal of Chemical Information and

Computer Science, 31(76).

Japkowicz, N. (2000). The Class Imbalance Problem: Significance and Strategies. In Pro-

ceedings of the 2000 International Conference on Artificial Intelligence (IC-AI’2000):

Special Track on Inductive Learning Las Vegas, Nevada.

Kubat, M., Holte, R., & Matwin, S. (1998). Machine Learning for the Detection of Oil

Spills in Satellite Radar Images. Machine Learning, 30, 195–215.

Kubat, M., & Matwin, S. (1997). Addressing the Curse of Imbalanced Training Sets: One

Sided Selection. In Proceedings of the Fourteenth International Conference on Machine

Learning, pp. 179–186Nashville, Tennesse. Morgan Kaufmann.

Lee, S. (2000). Noisy Replication in Skewed Binary Classification. Computational Statistics

and Data Analysis, 34.

Lewis, D., & Catlett, J. (1994). Heterogeneous Uncertainity Sampling for Supervised Learning.

In Proceedings of the Eleventh International Conference of Machine Learning, pp.

148–156 San Francisco, CA. Morgan Kaufmann.

Lewis, D., & Ringuette, M. (1994). A Comparison of Two Learning Algorithms for Text

Categorization. In Proceedings of SDAIR-94, 3rd Annual Symposium on Document

Analysis and Information Retrieval, pp. 81–93.

Ling, C., & Li, C. (1998). Data Mining for Direct Marketing Problems and Solutions. In

Proceedings of the Fourth International Conference on Knowledge Discovery and Data

Mining (KDD-98) New York, NY. AAAI Press.

Mladeni´c, D., & Grobelnik, M. (1999). Feature Selection for Unbalanced Class Distribution

and Naive Bayes. In Proceedings of the 16th International Conference on Machine

Learning., pp. 258–267. Morgan Kaufmann.

O’Rourke, J. (1998). Computational Geometry in C. Cambridge University Press, UK.

Pazzani, M., Merz, C., Murphy, P., Ali, K., Hume, T., & Brunk, C. (1994). Reducing

Misclassification Costs. In Proceedings of the Eleventh International Conference on

Machine Learning San Francisco, CA. Morgan Kauffmann.

Provost, F., & Fawcett, T. (2001). Robust Classification for Imprecise Environments. Ma-

chine Learning, 42/3, 203–231.

Provost, F., Fawcett, T., & Kohavi, R. (1998). The Case Against Accuracy Estimation

for Comparing Induction Algorithms. In Proceedings of the Fifteenth International

Conference on Machine Learning, pp. 445–453Madison, WI. Morgan Kauffmann.

Quinlan, J. (1992). C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo,

CA.

Solberg, A., & Solberg, R. (1996). A Large-Scale Evaluation of Features for Automatic

Detection of Oil Spills in ERS SAR Images. In International Geoscience and Remote

Sensing Symposium, pp. 1484–1486Lincoln, NE.

Stanfill, C., & Waltz, D. (1986). Toward Memory-based Reasoning. Communications of

the ACM, 29(12), 1213–1228.

Swets, J. (1988). Measuring the Accuracy of Diagnostic Systems. Science, 240, 1285–1293.

Tomek, I. (1976). Two Modifications of CNN. IEEE Transactions on Systems, Man and

Cybernetics, 6, 769–772.

Turney, P. (1996). Cost Sensitive Bibliography. http://ai.iit.nrc.ca/bibiliographies/costsensitive.

html.

van Rijsbergen, C., Harper, D., & Porter, M. (1981). The Selection of Good Search Terms.

Information Processing and Management, 17, 77–91.

Woods, K., Doss, C., Bowyer, K., Solka, J., Priebe, C., & Kegelmeyer, P. (1993). Comparative

Evaluation of Pattern Recognition Techniques for Detection of Microcalcifications

in Mammography. International Journal of Pattern Recognition and Artificial Intel-

ligence, 7(6), 1417–1436.