بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
داده کاوی توزیع شده بر روی کلان داده ها با استفاده از چارچوب هدوپ، (مطالعه موردی : مرکز آمار ایران)
چکیده
امروزه هوش تجاری و کاوش اطلاعات مفید نقش مهمی در مدیریت و تحلیل کلان داده ها دارد.در حوزه الگوریتم های داده کاوی،یافتن اقلام متناوب و استخراج قوانین انجمنی، نقش مهمی را ایفا می کند.از طرفی متناسب با افزایش حجم داده ها و با توجه به محدودیت منابع محاسباتی ،اعمال الگوریتم های ترتیبی داده کاوی بر روی یک ماشین ،کارایی مطلوب را ندارد و درحجم بالای داده، غیرممکن است. دراین زمینه تلاش های زیادی برای توسعه الگوریتم های موثر درحوزه داده کاوی موازی و توزیع شده انجام شده که تمرکز بیشتر آنها بر مباحثی نظیر ارتباطات در شبکه گرهها ، تعادل بار و سایر وظایف مبحث توزیع داده بوده است.در سالهای اخیر زمینه جدیدی از مطالعات در خصوص استفاده از چارچوب هدوپ مبتنی بر مدل برنامه نویسی نگاشت/کاهش صورت گرفته است.در این تحقیق ابتدا راهکارهای توزیع شده کلاسیک مربوط به الگوریتم Apriori ، بعنوان یکی از مهم ترین تکنیک ها برای تولید مجموعه اقلام متناوب ، مورد بررسی قرار گرفته و مزایا و معایب هر روش بیان می شود. سپس الگوریتم Apriori در چارچوب هدوپ و درحالت کاملا توزیع شده پیاده سازی میشود. مطالعه موردی برروی یک بانک اطلاعاتی کاربردی مرکز آمار ایران انجام شده و زمان اجرای الگوریتم در حالتهای مختلف پیکربندی هدوپ مورد ارزیابی قرار می گیرد.راهکار موردنظر با استفاده از ابزار کلودرا اکسپرس مورد آزمایش قرار گرفته است.نتایج نشان می دهد که سرعت اجرای الگوریتم درحالت بهره گیری از بستر هدوپ درحالت کاملا توزیع شده افزایش قابل توجهی دارد..
واژه های کلیدی : کلان داده 3 ، دادهکاوی توزیع شده4 ، مدل برنامه نویسی نگاشت/کاهش5 ، چارچوب هدوپ6 ، الگوریتم Apriori
مقدمه
پیشرفت فناوری اطلاعات و وجود سیستمهای یکپارچه اطلاعاتی منجر به ایجاد انبارهای عظیمی از دادهها شده است. استخراج دانش از این اطلاعات با استفاده از علم دادهکاوی معمولا نیاز به منابع زیادی از نظر فضای ذخیره سازی و همچنین زمان انجام محاسبات دارد. با پیشرفت تکنولوژیهای دسترسی به اطلاعات، ضرورت افزایش کارایی در تکنیکهای دادهکاوی بر روی داده های با حجم زیاد، نیز رو به افزایش است. در زمینهکاوش قوانین انجمنی مبتنی بر دادهکاوی توزیع شده، چندین الگوریتم Apriori با رویکرد توزیع شده پیادهسازی شده است. (اگراوال،شافر، (1996، (چونگ،هان ودیگران،(1996، (اگراوال،شافر،(2003، (اشرفی،تانیار و دیگران ،(2004، (تسوماکاس، ولاهاواس ،.( 2009 این الگوریتمها دارای کارایی مطلوب در مقایسه با الگوریتمهای رویکرد ترتیبی هستند و هر یک بر روی بخشی از پارامترهای موثر در حوزه دادهکاوی توزیع شده عمل می کنند.از طرفی در سیستمهای با رویکرد توزیع شده، با چالشهایی نظیر توزیع داده، کمینه کردن حجم تراکنش های ورودی/خروجی، برقراری تعادل بار بین ایستگاه های کاری، کمینه کردن ارتباطات، افزایش امکان محلیسازی مواجه هستیم. کارهای انجام شده قبلی ، در راستای دستیابی به یک حالت بهینه در برقراری فاکتورهای مطرح شده فوق با هم رقابت می کنند.
در بین تحقیقات جدید (جونووک، (2012، (یحیی ، هگازی و دیگران،(2012، ( زاوو، آر دو ،(2012،(اوراگانتی، کیو دینگ و دیگران،(2013، (فرزانیار،سرسونی و دیگران ، (2013 صورت گرفته ،چارچوب هدوپ بمنظور پردازش مجموعه دادههای بزرگ در یک راهکار توزیع شده ارائه شده است. این مدل مشکلاتی نظیر میزان تحمل خطا ، توزیع داده و تعادل بار را از دید کاربر پنهان میکند. این رفتار، موجب ایجاد تمرکز کاربر بر روی مساله اصلی و فارغ شدن از جزئیات و ملاحظات مربوط به رویکرد توزیع شده میشود. در این چارچوب که از مدل برنامه نویسی نگاشت /کاهش استفاده میکند، داده ورودی بر روی گرهها توزیع میشود. لذا با توجه به سیستم فایل توزیع شده هدوپ و مدل پردازشی آن، این چارچوب بعنوان یک راهکارموثر برای پردازش با رویکرد مقیاس پذیری بالا مورد توجه است.
در این مقاله ابتدا الگوریتم Apriori مبتنی بر راهکارهای توزیع شده کلاسیک مورد بررسی قرار می گیرد و مزایا و معایب هر روش تشریح میشود. سپس الگوریتم مذکور بر روی چارچوب هدوپ و مبتنی بر مدل برنامه نویسی نگاشت/کاهش پیاده سازی می شود.لازم به ذکر است که الگوریتم در بستر هدوپ و بصورت کاملا توزیع شده اجرا می شود و برای این منظوراز ابزارکلودرا اکسپرس))Cloudera Express استفاده می شود.بمنظور ارزیابی زمان اجرا ، الگوریتم در سه نوع پیکربندی هدوپ و مجموعه داده های متفاوت مورد بررسی قرار می گیرد.در ادامه و در بخش دوم مفاهیم و مبانی نظری پژوهش ، در بخش سوم پیشینه تحقیق ارائه شده است.در بخش چهارم روش تحقیق بیان می شود.در بخش پنجم تجزیه و تحلیل داده ها و در بخش ششم نتایج و ارزیابی عنوان می گردد.
مبانی نظری پژوهش
❖ داده کاوی و تکنیک قوانین انجمنی :
علم داده کاوی بعنوان یکی از تکنولوژی های برتر ، تحول بزرگی را در تحلیل و بررسی داده ها ایجاد کرده است.دادهکاوی فرآیندی ازشناخت الگوهای معتبر، جدید، بالقوه مفید و قابل فهم از داده هاست(فیاد،پیاتتسکی و دیگران ، .(1996بعبارتی داده کاوی ، مجموعه ای از روشها در فرآیند کشف دانش است که برای تشخیص الگوها و کشف ساختار های جالب توجه و با ارزش از داخل مجموعه وسیعی از داده ها مورد استفاده قرار می گیرد. (هاند،مانیلا و دیگران، (2001 ،( هان،کامبر ،.(2006 از میان تکنیک های داده کاوی، قوانین انجمنی1 یکی از روش های مورد توجه است. شاید این روش را بتوان به عنوان رایجترین شکل روشهای کشف الگو در سیستمهای یادگیری غیرنظارتی2 نام برد. این روش در سال 1993 توسط اگراوال مطرح شد (اگراوال،ایمیلینسکی و دیگران،.(1993 مثال متداول در رابطه با کشف قوانین انجمنی "تحلیل سبد خرید" است. در این فرآیند با توجه به اقلام مختلفی که مشتریان در سبد خریدشان قرار میدهند ، عادات و رفتار خرید مشتریان مورد تحلیل قرار میگیرد و الگوهای موجود در اقلام خریداری شده کشف می شود. (هان،کامبر .(2006 این تکنیک روابط و وابستگی های متقابل بین مجموعه بزرگی از اقلام داده ای را نشان می دهند .قالب کلی قوانین انجمنی به صورت x y می باشد که نشان دهنده نوعی پیش آمد همزمان بین اقلام xوy است x)وy دو مجموعه قلم دلخواه از انباره داده ها هستند) xوy به ترتیب مقدم3 و تالی4 قانون نامیده می شوند.
معیارهای مختلفی برای ارزیابی میزان صحت و ارزشمندی قوانین ارائه شده اند که بر اساس آنها می توان قوانین خوب را از میان مجموعه وسیعی از قوانین ممکن انتخاب کرد معروف ترین و پرکاربردترین این معیارها دو پارامترکمینه ضریب پشتیبانی5 وکمینه ضریب اطمینان6 است که بصورت روابط زیر تعریف می شود:
ضریب پشتیبان7
ضریب پشتیبانی قانون انجمنی x y در پایگاه داده تراکنشی یک نسبت است که در قالب فرمول 1 بصورت زیر است.
(1)
در واقع ضریب پشتیبان، درصد مجموعه تراکنش هایی است که شامل هر دو زیر مجموعه x,y باشد .ضریب پشتیبانی بیشتر، نشان دهنده پرتکرار بودن قانون می باشد.یعنی احتمال رخداد مجموعه اقلام بیشتر خواهد بود.کمینه پشتیبانی توسط مشتری و بر طبق نیاز او بعنوان کمینه پشتیبانتعیین میشود .
ضریب اطمینان1
نسبت میان تعداد دفعات تکرار همزمان x,y در تراکنش ها به تعداد تراکنش های شامل x است و در قالب فرمول 2 نمایش داده می شود .ضریب اطمینان، درصد تراکنش هایی است که x,y هر دو با هم ظاهر شده اند. در واقع یک احتمال شرطی است.
(2)
درنهایت، قوانینی مورد قبول واقع می شوند که مقادیر قابل قبولی برای هر دو معیار فوق داشته باشند (اگراوال،ایمیلینسکی و دیگران،)(1993هان،کامبر ،.(2006
الگوریتم Apriori
الگوریتم Apriori ، یکی از الگوریتم های پایه ای و پرکاربرد در حوزه استخراج قوانین انجمنی است.این الگوریتم دو گام دارد:
گام اول - تولید مجموعه اقلام متناوب : یک مجموعه اقلام متناوب نامیده می شود اگر ضریب پشتیبان مجموعه اقلام متناوب از کمینه ضریب پشتیبان مورد نظر ما بیشتر باشد. الگوریتم درمرحله اول، با اسکن کامل پایگاه داده اقلام متناوب تک عضوی شناسایی می شوند.سپس با استفاده از اقلام متناوب تک عضوی ، شروع به ساختن اقلام کاندید دو عضوی می کند و از بین آنها مجموعه اقلام متناوب دو عضوی شناسایی می شوند و این روال تا زمانی که مجموعه اقلام کاندید بیشتری نتوان تولید کرد پایان می یابد.
گام دوم- تولید قوانین انجمنی : برای تولید قوانین انجمنی از مجموعه اقلام متناوب استفاده می شود .در اکثر موارد تنها قوانینی جالب و مفید هستند که شامل اقلامی باشند که با دفعات تکرار زیاد باشند ، و درصد رخداد تراکنش های آن از کمینه درجه اطمینان2 تعیین شده بیشتر باشد . (اگراوال،ایمیلینسکی و دیگران،(1993، ( اگراوال، سیرکانت ،.(1994
❖ دادهکاوی توزیع شده3
با توجه به روند افزایش حجم اطلاعات و مبحث کلان داده ها ، راهکارهایی نظیر الگوریتم های موازی و توزیع شده بمنظور انجام عملیات داده کاوی بر روی داده های بزرگ مورد نیاز است .داده کاوی توزیع شده عبارت است ازکشف نیمهخودکار الگوهای پنهان موجود درداده ها، درحالتی که دادهها و یا مکانیزمهای استنتاج به صورت توزیع شده باشند(اف یو ،.(2001بعبارتی داده کاوی توزیع شده با همان کاربرد فرآیند دادهکاوی کلاسیک است که در محیط محاسبات توزیع شده، با تمرکز بر استفاده بهینه از منابع (شامل شبکه ارتباطی ، بخشهای محاسباتی و پایگاههای داده) درنظر گرفته می شود.به نوعی در این محیطها ، عملیات دادهکاوی در هر دو سطح ، یکی در سطح محلی شامل
عملیات مربوط به داده های توزیع شده هر نود و دیگری در سطح عمومی برای استخراج دانش عمومی از تجمیع دانش محلی منتج از نودهای مختلف انجام میشود. (اف یو ،(2001، (پارک، کارگوپتا،( 2003
❖ چارچوب هدوپ
یک پیاده سازی متن باز1مبتنی بر جاوا2 است که توسط شرکت نرم افزاری آپاچی((Apacheتولید شده و مورد پشتیبانی قرار دارد. این معماری برای توسعه برنامه های کاربردی مفید است که پردازش حجم زیادی از دادهها را بر روی مجموعه ای بزرگ از ماشین ها بطور موازی انجام میدهند. این راهکار قابلیت اطمینان بالا و تحمل پذیری مطلوب ارائه می دهد. ابزارهای این محصول در 3 حوزه اصلی ارایه شده اند :.)www.hadoop.apache.org)
مجموعه ابزار مشترک هدوپ: 3 مجموعه ابزارهای عمومی است که اجرای بخشهای مختلف این پروژه را پشتیبانی میکند. تمامی فرایندهای تعریف شده در این چارچوب وابسته به این حوزه است.
سیستم فایل توزیع شده هدوپ:4 ابزار مدیریت کننده فایلهای توزیع شده است که امکان دسترسی برنامه های کاربردی به داده های توزیع شده را فراهم میکند. این سیستم مدیریت کننده برای نگهداری دادههای حجیم روی مجموعه ماشینهای های متعدد طراحی شده است. پیاده سازی این سیستم بگونه ای است که در سیستم های موازی، دسترسی مناسبی به دادهها را فراهم میکند و همچنین با ذخیره سازی چندگانه اطلاعات بر روی ماشینهای مختلف، قابلیت اطمینان بالایی را برای جلوگیری از بروز خرابی داده، ارایه میدهد.
سیستم فایلی هدوپ ، حجم ذخیره سازی را روی کلاستر ساخته شده از کامپیوترهای ارزان قیمت، با شکستن فایل های ورودی به بلوک های کوچکتر مدیریت کرده و هر بلوک را بهصورت تکراری روی مخزنی از سرورها ذخیره میکند.در شکل 1 نمایی از عملکرد سیستم فایل توزیع شده هدوپ نمایش داده شده است.
شکل :(1) نحوه ذخیرهسازی داده در سیستم فایل توزیع شده هدوپ (انگفر،(2011
در صورتی که دو سرور در مجموعه سرورها دچار اختلال شوند، کل فایل مورد نظر باز هم قابل دستیابی است. در این حالت، سیستم فایل توزیع شده هدوپ از وجود چنین مشکلی آگاه شده و کپی های جدیدی از داده های قبلی ایجاد میکند. همچنین، به
این دلیل که کپیهای مختلفی از بلوکها روی یک کلاستر، توسط سیستم فایل توزیع شده هدوپ ایجاد میشود، کلاینتهای بیشتری میتوانند بدون ایجاد گلوگاه به داده های سیستم دسترسی داشته باشند.((www.ibm.com
❖ مدل برنامه نویسی نگاشت/کاهش هدوپ :1 یک مدل برنامه نویسی برای توسعه سیستمهایی است که هدف آنها پردازش موازی مجموعه دادههای حجیم در کلاستری از سیستمها میباشد )www.hadoop-mapreduce.org) ساختار نگاشت/کاهش بعنوان یک مدل برنامه نویسی توسط گوگل در سال 2004 برای پشتیبانی محاسبات توزیع شده معرفی شده است .در یک کلاستر نگاشت/کاهش ، یک گره بعنوان گره اصلی2 است که وظیفه زمان بندی3 فعالیت ها را برای اجرا بین گرهها انجام می دهد و مابقی گرهها ، گرههای انجام دهنده (کارگر)4 است (دین جی، جماوا ،.(2004 گره اصلی و گرههای انجام دهنده می تواند بر روی یک گره یکسان واقع شود. محاسبات در چارچوب نگاشت/کاهش توسط توابع نگاشت5 و کاهش6 انجام می شود. گره اصلی، فعالیت های نگاشت7 و فعالیت های کاهش8 کاهش8 را وقتی که یک وظیفه 9مقدار دهی اولیه می شود ، زمان بندی می کند.فعالیت های نگاشت بوسیله کارگرهای تنظیم شده بطور همزمان اجرا خواهند شد . برنامه نویس، کد تابع نگاشت را می نویسد که در آن یک بلوک10 از سیستم فایل خوانده می شود و مجموعه ای از جفت های کلید/مقدار میانی 1تولید می شود. کتابخانه2
1 Hadoop Map/Reduce model 2 Master node 3 schedule 4 worker 5 Map funcation 6 Reduce function 7 Map tasks 8 Reduce task 9 job 10 block
نگاشت/کاهش تمامی مقادیر میانی که مرتبط با یک کلید میانی یکسان هستند را با یکدیگر سازماندهی میکند و آنها را به تابع کاهش ارسال مینماید. تابع کاهش نیز توسط برنامه نویس نوشته می شود، که درآن یک کلید میانی و مجموعه از مقادیر آن کلید گرفته می شود . این تابع تمامی این مقادیر را با یکدیگرادغام میکند تا مجموعه کوچکتری از مقادیر را تشکیل دهد که این منجر به مدیریت لیستی از مقادیر بسیار بزرگ برای قرارگرفتن در فضای حافظه میشود. همانطور که مشاهده می شود ،مدل نگاشت/کاهش ،ایده موازی سازی را در سطح بالا انجام میدهد. تمامی عملیات نگاشت از یکدیگر مستقل هستند وبطور کامل موازی انجام میشوند (دین جی، جماوا ،.(2004 معماری مدل برنامه نویسی نگاشت/کاهش در شکل 2 آمده است.
شکل :(2) معماری پایه مدل برنامه نویسی نگاشت/کاهش
پیشینه پژوهش
با افزایش حجم داده امکان پردازش الگوریتم های داده کاوی بر روی یک سیستم ترتیبی واحد از منظر حافظه و زمان مورد نیاز ، امکان پذیر نیست. برای اینگونه موارد راهکار کاربردی استفاده ازرویکرد الگوریتم های توزیع شده بر مبنای اندازه بانک اطلاعاتی است. راهکارهای ارائه شده را میتوان در دو بخش الگوریتم های توزیع شده کلاسیک و الگوریتم های مبتنی بر مدل برنامه نویسی نگاشت/کاهش بیان کرد.
❖ راهکار Apriori توزیع شده کلاسیک
در مقالات (اگراوال،شافر، (1996، (تسوماکاس، ولاهاواس ،2009 )، به الگوریتم )CD( Count Distribution پرداخته شده است . ایده اصلی این الگوریتم مبتنی بر موازی ساده داده 3است . در این الگوریتم تقسیم داده بین ایستگاه های کاری انجام می شود . هر کدام از n ایستگاه کاری شامل n/1 حجم بانک اطلاعاتی است .و الگوریتم Apriori را بر
