یادگیری درختان تصمیم جریانهای داده بزرگ

یادگیری درختان تصمیم جریانهای داده بزرگ – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

یک رویکرد موازی برای یادگیری درختان تصمیم از جریانهای داده­ای بزرگ

چکیده

در این مقاله ما یک الگوریتم یادگیری درخت تصمیم موازی به نام pdsCART را معرفی میکنیم. سه مشخصه اصلی و مهم در ساخت این درخت جود دارد. اول، الگوریتم ارائه شده میتواند با جریانهای داده­ای کار کرده و درخت تصمیم را ایجاد کند. دوم، الگوریتم قادر به پردازش موازی مقدار بزرگتری از جریان داده ثبت شده میباشد و بنابراین برای مجموعه داده­های خیلی بزرگ کاربرد دارد. و سوم اینکه، الگوریتم میتواند در چهار چوب MapReduce پیاده­سازی شود. جزئیات مرتبط با این الگوریتم و برخی از نتایج اصلی عملکرد در این مقاله ارائه شده است.

کلمات کلیدی: داده بزرگ، داده­کاوی تجاری، جریان­ها، MapReduce، درختان تصمیم­گیری

یادگیری درختان تصمیم جریانهای داده بزرگ

۱ -­مقدمه

داده بزرگ[۱] اصطلاحی برای تحلیل مجموعه­های بزرگ داده شده است. این مجموعه­های بزرگ داده­ای در کاربردهای علمی از قبیل فیزیک، زیست و هواشناسی تولید شدند. اما یکی از این کاربردها در زمینه تجارت و سرمایه­داری بود، افزایش مقدار داده تولید شده، محققان را با مسائل و مشکلاتی در رویارویی با مجموعه داده بزرگ مواجه کرد. اما زمینه با اهمیت دیگر، جریانهای داده تولید شده توسط انواع حسگرها همانند وسایل متحرک، حسگرهای دوردست، شناسایی مخابره­های مکرر و غیره است.

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

چهار چوب MapReduce [1]، استانداردی برای پیاده­سازی پردازش­هایی به منظور تحلیل مجموعه داده­های خیلی بزرگ بصورت موازی، با استفاده از خوشه­های توزیع شده است. ساختار اصلی آن شامل دو گام اصلی است: ابتدا، گام-نگاشت، که داده را برای تحلیل فیلتر و مرتب می­کند و به دنبال آن در گام گاهش داده را برای تحلیل متراکم می­سازد. این چهارچوب ساده برای کاربردهای بزرگ مجازست، اما در مواجهه با الگوریتمهایی که میتواند با روش مستقیم پیاده سازی شود، کاملا محدود می­شود. با انگیزه کاربردهای تجاری، علاقه مند به الگوریتمهای درخت تصمیم شدیم. در این مقاله، روشی را برای پیاده سازی الگوریتمهای درخت تصمیم برای جریانهای داده بزرگ در چهارچوب MapReduce ارائه میدهیم.

ادامه مقاله بصورت زیر سازماندهی شده است: در بخش بعدی، در مورد الگوریم داده­کاوی درخت تصمیم بحث میکنیم. سپس در مورد چگونگی استفاده از درخت تصمیم برای تحلیل جریان­های داده بحث میکنیم و در ادامه جزئیات پیاده­سازی الگوریتم درخت تصمیم موازی به همراه تحلیل کارایی آن ارائه می­شود.

[۱] Big Data

یادگیری درختان تصمیم جریانهای داده بزرگ

۲-­ درختان تصمیم برای استخراج داده بزرگ

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

در هر حال، درختان تصمیم یکسری معایب هم دارند. الگوریتمهای تصمیم­گیری سابق[۲و۳]، با مشکل کمبود حافظه مواجه بودند، چون باید مجموعه­های داده آموزشی را برای ساخت تصمیم بطور بازگشتی میخواندند. علاوه بر این، مقادیر عددی به منظور یافتن نقاط انشعاب، نیاز به مرتب سازی دارند. برای غلبه بر مشکل زمان و حافظه چندین راه حل پیشنهاد شده­اند.

۲٫۱­ پژوهش­های گذشته

یکی از تکنیک­های مورد استفاده الگوریتم­های درخت تصمیم، پیش-مرتب سازی مقادیر خصیصه­ها، از قبیل SPRINT [4] یا ScalParC[5] است. رویه دیگر تخمین داده به جای مرتب سازی آن با استفاده از ساختارهای هیستوگرام است، همانند، pCLOUDS [6]،SPIES [7] و SPDT[8]. برای ساخت هیستوگرام­ها، برخی از محققان از تکرار داده استفاده می­کنند. اگرچه رویه­های پیش- مرتب سازی دقیقترند، آنها ممکن است برای جریانی از داده مناسب نباشند.

الگوریتم­های درخت تصمیم موازی: در مقاله آمادو و همکاران[۱۰] و سریواستاوا و همکاران [۹]، چهار نوع مختلف از الگوریمهای درخت تصمیم توصیف شده­اند: افقی، عمودی، وظیفه و ترکیبی. در افقی، مجموعه کامل داده به زیر مجموعه­هایی منشعب می­شود. در حالت عمودی، مجموعه خصیصه­ها بخش بندی می­شود. موازی سازی وظیفه، قادر به توزیع نودهای درختان تصمیم برای پیشروی مستقل است. توع چهارم، یعنی موازی سازی ترکیبی، ترکیبی از تمام سه رویه قبلی است. برای مثال، در فاز اول فرایند رشد درخت تصمیم، موازی سازی افقی و عمودی ترکیب شده و موازی سازی وظیفه در انتها انجام می­گیرد.

مثالی از حالت ترکیبی PLANET گوگل است[۱۱]، تکنیکی که موازی سازی افقی در سطوح ابتدایی درخت بکار برده و موازی وظیفه را برای برگها و به محض فیت شدن داده در حافظه بکار میبرد.

در پژوهش دیگری[۸]، نویسندگان از موازات افقی برای ساخت هیستوگرام­های داده استفاده میکنند، که در ادامه برای تصمیم گیری به منظور ساخت درخت با روش اول- عرض استفاده میشود. مثالهای دیگری از موازات افقی برای ساخت درختان، درختان تصمیم گرادیان تقویتی([۱۲]GBDT) یا درختان رگرسیون ([۱۳]GBRT) می­باشند.

…

۲٫۲­ رویکرد موازی برای جریانات داده

ما PdaCART را ارائه دادیم که روشموازی برای ساخت درختان نصمیم برای استنتاج و پیش­بینی از جریانات داده بزرگ است. ما الگوریتم درخت تصمیم dsCART [24] را برای دسته بندی جریان داده بعنوان پایه و اصل کار خود انتخاب کردیم. راه حل پیشنهادی ما روشی برای تعدیل الگوریتم dsCART در موازات افقی با پیاده­سازی مدل برنامه نویسی MapReduce است. در حالیکه چندین راه حل دیگر قبلا رائه شده­اند، از قبیل: SPDT, PLANET, SRF, GBDT, GBRT و غیره. هیچیک از این متدها برای درخت تصمیم مسیر- تنها برای الگوریتم جریانهای داده بکار نرفته­اند. جزئیاتت روش پیشنهادی در بخش پیاده سازی ارائه می­شود.

یادگیری درختان تصمیم جریانهای داده بزرگ

 ۳-­ پیاده سازی PdsCART

در این بخش، روش پیشنهادی را توصیف می­کنیم که هدف آن موازی سازی الگوریتم درخت تصمیم PdsCART می­باشد. بدین منظور، ابتدا هر دوی PdsCART و PdsCART را برای جریانات داده معرفی کرده و سپس جزئیات پیاده سازی MapReduce خود را بیان می­کنیم. نکته مهم این است که ما تنها میخواهیم نشان دهیم که مدل­های یادگیری مشابه ممکن است با ثبت موازی انجام شوند که باعث کاهش زمان می­شود.

قبل از توصیف شبه کد، ذکر نکته­های زیر ضروری است:

-­ برای هر خصیصه aⁱ ، مجموعه مقادیر خصیصه Aⁱ به دو زیر مجموعه مجزای  و  بخش بندی می­شوند بطوریکه Aⁱ = ؛

-­ انتخاب  بطور اتوماتیک زیر مجموعه مکمل  را تعیین می­کند.

-­ مجموعه تمام بخش­های ممکن مجموعه Aⁱ توسط Vⁱ مشخص می­شوند.

-­  بهبود Gini محاسبه شده برای خصیصه aⁱ در برگ L_q است.

–  تعداد عناصر از کلاسk ام در برگ L_q است، برای اینکه مقدار خصیصه aⁱ معادل با  است که ().

۳٫۱ ­ ملاحظات مقدماتی

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

همچنین، هر خصیصه انتخاب شده در یک نود مورد نظر با توجه به داده فعلی آن، مشابه یکی با احتمال بالا، بعنوان انتخاب شده پس از خوانش کامل داده است. بدین معنا که مهم نیست موقعی که این تخمین­ها انجام میشوند، آنها با احتمالی یکسان با خصیصه انتخاب شوند.

تمام این حقایق مارا تحریک به محاسبه و کنترل شرایط انشعاب پس از خواندن یک مقدار متغیری از نمونه­ها هنگام پردازش مستقل آنها می­کنند. با انتخاب احتمال بالای مناسب(پارامتر α)، الگوریتم ما قادر به تولید درختان تصمیم بسیار مشابه در مقایسه با dsCART ، با سطح یکسانی از دقت اما زمانهای پردازش سریعتر می­کند. رویه موازی الگوریتم PdsCART در زیر بخش بعدی آمده و نتایج استفاده از این الگوریتم در بخش آزمایشات می آید.

۳٫۲­  پیاده­سازی MapReduce 

در درختان تصمیم PdsCART توزیع شده، نمونه MapReduce را با استفاده از یک روش بخش بندی افقی بکار می­بریم. پردازش کنترلر رشد درخت را تعدیل می­کند، در حالیکه پردازش­های نگاشت دهنده و کاهش دهنده وظایف استاندارد خود را کامل انجام می­دهند. با این فرض که نگاشت دهنده P را داریم و میخواهیم رکوردهای R را بطور موازی مصرف کنیم، کنترلر به هر نگاشت دهنده R/ P  رکورد برای پردازش تخصیص داده می­شود.

یادگیری درختان تصمیم جریانهای داده بزرگ

۴- آزمایشات

این بخش چندین نتیجه را از آزمایشات ما بطور خلاصه مطرح می­کند. رویه موازی برای یادگیری درخت تصمیم از جریانات داده برای دست یافتن به نتایج یکسان با الگوریتم dsCART طراحی می­شود. در حقیقت، در تمام تست­های ما، هنگام اجرا با مقدار α مناسب تنظیمات یکسان (به جز تعداد رکوردهای پردازش شده)، ما دقیقاً درختان مشابه با سطح یکسانی از دقت را با پیاده­سازی dsCART بدست آورده­ایم. بدین دلیل، ما نیاز نداریم که تفاوتهای دقت میان مدل­های یادگیری را محک بزنیم. در عوض، میخواهیم کارایی تئوری و عملی بدست آمده از پیاده سازی راه حلمان را با پردازش موازی تقویت کنیم.

بدین منظور، ابتدا سناریوهای تجربی جزئیات مجموعه­های داده مورد نظر، توصیف کرده و سپس نتایج پیاده سازی روش پیشنهادی را ارائه می­دهیم.

۱٫۴ سناریوهای تجربی

 اداره تعداد بزرگتری از رکوردهای داده بطور موازی زمان پردازش را کاهش خواهد داد، چندید جنبه دیگر به منظور ارزیابی رویه موازی ما در نظر گرفته شده است. برخی از جنبه­های مورد نظر، علاوه بر زمان اجرا شامل: تعداد رکوردهای مورد نظر در تکرار، تعداد خصیصه­ها و تعداد انبارهاست. جنبه­های دیگر، همانند اندازه درخت تصمیم، پارامتر α و روابط وابستگی بین تمام جنبه­ها ممکن است برای آینده در نظر گرفته شود.

۲٫۴ ­ نتایج تجربی

مجموعه اولیه نتایج، موجود در جدول ۲، بهبود زمان اجرای PdsCART را در مقایسه با dsCART با تولید دقیق درختان مشابه و دقیق نشان می­دهد.

یادگیری درختان تصمیم جریانهای داده بزرگ

۵- نتیجه گیری و تحقیقات آینده

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

این نتایج پایه ای را برای نحقیقات بیشتر ایجاد میکند. لازم است تحلیل کنیم که چگونه الگوریتم با افزایش تعداد واحدهای پردازش سنجیده می­شود و در کدام روش تمامی پارامترهای دیگر تحت تأثیر رفتار الگوریتم هستند. خروجی به آسانی قابل حدس است. در هر حال باید کار بیشتری به منظور ارزیابی تأثیر این پارامترها روی کیفیت درختان تصمیم انجام شود. میدانیم که میتوانیم نرخهای خطای مشابهی با دیگر الگوریتمها بدست آوریم. برخی از دیگر پارامترها پیرامون درختها همانند اندازه، عمق، ترتیب خصیصه­ها، باید در آینده بررسی شوند.