بخشی از مقاله
چکیده -در این مقاله، روش جدیدی برای طبقه بندی چند کلاسه داده ها بر اساس کاهش داده ها، با هدف کاربرد برای داده های حجیم ارائه شده است. روش پیشنهادی دارای 2 فاز اصلی است: تشخیص نمونه های مرزی با کمک الگوریتم انتشار رو به جلو نمونه های اولیه بوسیله یک مجموعه از بردارهای پشتیبان، و دادن برچسب مناسب به نمونه های ورودی، که بر اساس تکنیک "یک در مقابل همه" پیشنهاد شده است.
این روش تنها با یک پارامتر تنظیم و گرایش کمی به overfitting می تواند نرخ بالایی از دقت طبقه بندی را برای داده هایی با توپولوژی های پیچیده و کلاس های غیر مقعر و یا نامتعادل ارائه دهد. روش ارائه شده با محاسبه error_rate و condensing_rate در محیط متلب ارزیابی شده است. نتایج نشان میدهد که الگوریتم پیشنهادی توانسته با نرخ فشرده سازی بالایی ، نرخ خطای طبقه بندی مناسبی نسبت به روش های محبوب دیگر داشته باشد. از این سیستم پیشنهاد شده میتوان در ابزارهایی با حافظه پایین و انتقال حجم بالایی از داده استفاده کرد که این تراکم داده در داده های حجیم می تواند از اهمیت بالایی برخوردار باشد.
-1 مقدمه
Big data اصطلاحی است برای مجموعه داده های حجیم که بزرگ ، متنوع با ساختاری پیچیده و با دشوارهایی برای ذخیره سازی ، تحلیل و پردازش های بیشتر نتایج می باشد به طوری که پردازش آن ها توسط نرم افزارهای سنتی پردازش اطلاعات امکان پذیر نیست و یا به سختی انجام می شود. به عنوان مثال داده های دیجیتال، که در همه اشکال و اندازه به صورت شگفت آوری در حال رشد هستند. به گزارش آژانس امنیت ملی فقط اینترنت در حال پردازش 1/826 پتا بایت داده در هر روز می باشد. [1] سال 2011 اطلاعات دیجیتال فقط در 5 سال 9 برابر رشد داشته اند و تا سال 2020 مقدار آن 35 تریلیون گیگا بایت خواهد رسید.
2] این انفجار از داده های دیجیتال فرمت ها و پتانسیل دگرگونی بزرگی برای بخش های مختلفی مانند شرکت ها، تولید و محصولات بهداشت و درمان و خدمات آموزشی، بینایی ماشین، بازیابی اطلاعات و ... به ارمغان خواهد آورد.[4] ,[3] از این رو تحقیقات علمی به دست آمده به سمت اکتشافات داده محور در حرکت است. یکی از سودمندترین کارها برای داده های حجیم، مقیاس پذیر1 کردن الگوریتم های موردنظر در این گونه مسائل می باشد. مقیاس پذیری یک ویژگی مطلوب برای یک سیستم یا فرآیند است که توانایی آن برای پاسخگویی به افزایش میزان بار کاری را نشان می دهد.
از روش های موثر برای مقیاس پذیر کردن الگوریتم ها، توزیع داده ها بر روی چند سرور مجزا - حداقل 4 سرور که یک سیستم مرکزی و 3 نود - می باشد به طوری که همزمان همه آن ها در حال اجرای الگوریتم موردنظر برای بخشی از داده های مشخص شده می باشد.[5] برای طبقه بندی کردن کلاس ها داشتن نمونه های مرزی بسیار موثر است و هدف از متراکم کردن داده ها نیز به دست آوردن همین نمونه های مرزی می باشد.
اما روش های معروفی مانند KNN و SVM و ... که تا الان مطرح شده اند دارای نقاط ضعفی مانند نیاز به حافظه ذخیره سازی بالا یا ناتوانی در برخورد با کلاس های نامتعادل و... است که این نقاط ضعف در برخورد با داده های حجیم مشکل ساز بوده اند و یا روش های ترکیبی ارائه شده که آن ها نیز در برخورد با کلاس های نامتعادل با مشکل عدم توانایی طبقه بندی در بعضی موارد روبه رو بوده اند. بنابراین ارائه الگوریتمی که بتواند در بطن خود و به صورت پایه انعطاف لازم برای برخورد با داده های حجیم را داشته باشد بسیار دارای اهمیت است.
مسایل طبقه بندی چندکلاسه هنوز یک کانون پژوهش در یادگیری ماشین است، وپژوهش ها برای ایجاد الگوریتم های جدید با دقت و کارایی بیشتر اختصاص می یابد.[6] به منظور حل یک مسئله طبقه بندی چند کلاسه، 3 راهکار می توان در نظر گرفت.[7] روش اول: استفاده ازروش های طبقه بندی است که می تواند با مشکلات طبقه بندی به طور مستقیم برخورد کند. دوم: ساخت یک مجموعه از طبقه بندی دودویی است. و سوم: ساخت یک مجموعه از طبقه بندی های یک طبقه است که در دو حالت آخر می توان مسئله چند طبقه را به چند زیر مسئله کوچکتر تجزیه و اجرا کرد.[8]
در میان این روش ها، ساخت یک مجموعه از طبقه بندی های دودویی محبوب ترین است و به طور گسترده ای استفاده می شود. 2روش متداول برای طبقه بندی دودویی، روش "یک در مقابل یک"2 و روش "یک در مقابل همه"3 می باشد.[9] روش یک"یک در مقابل همه " یا OVA برای حل مسائل مختلف طبقه بندی چند کلاسه استفاده شده است.[10] در واقع این روش یک طبقه بندی برای هر کلاس به صورت کلاس هدف و باقی کلاس ها می سازد.
در ی ک دسته بندی کننده »یک در مقابل همه« از تعداد k-1 دسته بندی کننده 2 کلاسی استفاده می شود، که هر کدام یکی از کلاس ها را از سایرین جدا می کند، که یکی از مشکلات این روش این است که این امر باعث به وجود آمدن نواحی با دسته بندی مبهم می شود. و مشکل دیگر این روش در برخورد با کلاس های نامتعادل است. که در این تحقیق از همین روش استفاده شده و با به کارگیری الگوریتم مناسب مشکلات گفته شده برطرف گردیده است.
لذا در این مقاله با کمک الگوریتم فشرده سازی انتشار رو به جلو و به کار گیری روش یک در مقابل همه الگوریتمی برای طبقه بندی چندکلاسه مطرح گردید که بتواند با فشرده سازی بالا مشکل نیاز به حافظه ذخیره سازی بالا را حل کرده و توانایی اجرا در سیستم های موازی که لازمه کار با داده های حجیم است را دارا باشد و همچنین بتواند با سرعت بالا و دقت مناسب حتی طبقه بندی کلاس های نامتعادل و یا مقعر را با overfitting کم به خوبی انجام دهد. باقیمانده ی مقاله به این صورت سازماندهی شده است: در قسمت 2 فشرده سازی داده ها و روش "انتشار رو به جلو نمونه های اولیه" توضیح داده می شود. در قسمت 3 روش پیشنهادی بیان می شود. در قسمت 4 نتایج آزمایش بر روی مجموعه داده هایی از UCI ارائه شده است و در نهایت در قسمت 5 نتیجه گیری نهایی مطرح خواهد شد.
-2 طبقه بندی دو کلاسه مبتنی بر فشرده سازی داده ها
روش های کاهش نمونه نیز از پرکاربردترین روشها برای طبقه بندی و متراکم کردن داده ها در Large dataset ها است.[11] ,[1] که الگوریتم های K-NN هنوز به عنوان مفیدترین و موثرترین الگوریتم ها برای داده کاوی مطرح هستند.[11] با این حال با وجود پیاده سازی ساده اما این الگوریتم ها فضای ذخیره سازی بالایی را نیازمند هستند. به منظور غلبه بر این مشکل چندین الگوریتم متراکم کردن پیشنهاد شده است که این الگوریتم ها در چندین برنامه کاربردی که ظرفیت محدود حافظه دارند مفید هستند.
-1-2 الگوریتم انتشار رو به جلو نمونه های اولیه - - PFP4
یکی از روش هایی که اخیرا در زمینه متراکم کردن داده ها مطرح شده است، روش متراکم کردن داده ها با استفاده از الگوریتم انتشار رو به جلو - PFP - می باشد [11] که به منظور بدست آوردن مرزهای کلاس ها ، مجموعه ای از داده های پشتیبان را می دهد. روش این الگوریتم مفصلا در زیر برای طبقه بندی 2کلاسه شرح داده شده است، و هدف ما در این کار استفاده از این روش کارآمد جهت طبقه بندی چندکلاسه برروی large data ها می باشد.
الگوریتم PFP درواقع 2 گام اساسی دارد:
گام :1 ابتدا همه نمونه ها در هر کلاس فاصله شان با تمام نمونه های کلاس مقابل بدست آمده و به اندازه نصف فاصله شان از نزدیک ترین کلاس مقابل کره ای زده می شود و تمام نمونه های داخل آن شمارش می شود.
نمایی از بدست آمدن [11] GP
بعد از انجام این مراحل، نمونه ها بر اساس بیشترین تجمع نمونه مرتب شده و مثلاً اگر کره n ام دارای بیشترین تعداد نمونه کلاس 1 بود به عنوان مرکز 1Gp ثبت و شعاع آن نی ز نگهداری می شود و تمام نمونه هایی که داخل کره Gp باشند از داده های train حذف شده و مراحل بالا دوباره تکرار می شوند تا جایی که دیگر هیچ کره ای با تعداد نمونه ای بیشتر از nn وجود نداشته باشد. nn تنها پارامتر این الگوریتم است که نشان دهنده آن است که تنها کره هایی که تعداد نمونه های داخل آن بیشتر از nn باشد نگهداری می شود و بسته به شرایط مجموعه داده و پراکندگی نمونه ها می توان به آن مقدار داد.
