ارائه الگوریتم خوشه¬بندی مبتنی بر چگالی افزایشی برای داده¬های انبوه در انباره¬ داده ابری با رویکرد نگاشت-کاهش

چکیده

با توسعه سریع عصر اطلاعاتی و محیط­های اطلاعاتی پویا و در حال تغییر از قبیل اینترنت، هر روز داده­های بیشماری بدست می­آید و کشف و استخراج اطلاعات و دانش مفید از این حجم انبوه داده­ها مشکل است چراکه دیگر انباره­داده­های سنتی پاسخگوی این حجم انبوه از داده­ها نیستند و برای حل این چالش انباره­داده­های ابری مطرح می­شود.از سوی دیگر با رشد فزاینده اطلاعات، نیاز برای سازماندهی این اطلاعات به  یک روش موثر نسبت به قبل اهمیت شایانی پیدا کرده است.یکی از منابع مهم کسب دانش در همه فعالیتهای بشری، انبوه داده­هایی است که به تدریج در بخش­های مختلف جمع­آوری می­شود و در هر زمانی بروزرسانی می­شوند. داده­کاوی در اصل حلقه واسط بین مسائل و مشکلات از سوئئ و روش­های تصمیم­گیری از سوی دیگر است، یعنی داده­کاوی دانش موردنیاز برای تصمیمات درست را فراهم می­کند. خوشه­بندی به عنوان یک روش یادگیری بدون نظارت، یکی از تکنیک­های اصلی داده­کاوی محسوب می­شود. الگوریتم­های مبتنی بر چگالی یکی از روش­های اصلی در داده­کاوی محسوب می­شوند. این الگوریتم­ها نیازی به تعیین تعداد خوشه­ها از قبل ندارند و یکی از ویژگی­های مهم این الگوریتم­ها این است که به شکل خوشه­ها محدود نمی­باشند. روش­های خوشه­بندی مبتنی بر چگالی در زمینه­های پردازش شهری، پردازش تصویر و تحقیقات نجومی بسیار مورد استفاده قرار می­گیرند و محققان از  الگوریتم DBSCAN که الگوریتم پایه در این زمینه است، برای خوشه­بندی استفاده کرده­اند. در خوشه‌بندی مبتنی بر چگالی، خوشه‌ها به عنوان نواحی چگال از مجموعه‌داده، تعریف می‌شوند. اشیای موجود در نواحی کم‌تراکم، جداکننده‌ی خوشه‌ها از هم هستد (این اشیا می‌توانند نقاط پارازیت یا نقاط مرزی باشند.). این روش نقاطی که در محدوده‌ی معینی (در یک شعاع همسایگی) از هم قرار دارند را به هم وصل می‌کند. این الگوریتم، تنها نقاطی را متصل می‌کند که چگالی کمینه‌ای داشته باشند. که این امر به عنوان حداقل تعداد اشیای موجود (MinPoints) در شعاع همسایگی (Epsilon) تعریف شده است و بر خلاف بسیاری از روش‌های دیگر، می‌تواند خوشه‌های دارای اشکال دلخواه را شناسایی کند. ولی این روش در تشخیص خوشه‌ها با چگالی‌های مختلف ناتوان است. از سویی دیگر رشد فزاینده حجم داده­های امروزی  که مفهوم بیگ دیتا را مطرح کرده است ، نیاز به راهکاری در زمینه بیگ دیتا برای استخراج الگوهای پنهان را مطرح می­کند. پردازش ابری رویکردی مناسب جهت اجرای پردازش­هایبا حجم بالا است که به صورت توزیع­شده عمل پردازش صورت می­گیرد.  هدوپ راهکاری مناسب برای پیاده­سازی  الگوریتم­ها به صورت موازی می­باشد. چارچوب Hadoop یک پلتفرم محبوب برای پردازش مجموعه های بزرگتر است.

Hadoop با استفاده از یک الگوی محاسباتی به نام MapReduce, برنامه‌ها را در دو فاز نگاشت (Map) و کاهش (Reduce) اجرا ‌می‌کند. MapReduce یک مدل برنامه نویسی ساده برای پردازش داده‌هاست. برجسته ترین مزیت آن مقیاس پذیری آسان پردازش داده‌ها روی چندین گره محاسباتی است اما هنوز هم برای بیان تمامی برنامه‌ها آسان و ساده نمی‌باشد.MapReduce  یک مدل پردازش داده با مقیاس پذیری آسان و پردازش داده روی چندین گره محاسباتی است، این مدل پردازش داده در بسیاری از زبان‌ها قابل دسترسی می‌باشد (White, 2009).

لذا چالش اصلی تحقیقات اخیر،اجرای پردازش بر روی داده­هایی با چگالی متفاوت و بروز­رسانی خوشه­های موجود در داده­های افزایشی است. الگوریتم DBSCAN   علی­رغم وجود مزایایی که دارد، دارای کمبودهایی نظیر عدم پشتیبانی از داده­های با چگالی متفاوت است. اگرچه الگوریتم­های متنوعی در این زمینه ارائه شده اما هریک از یک جنبه  به مساله نگاه کرده­اند با درنظر گرفتن عدم کارائی و اثربخش بودن الگوریتم­های موجود به دلیل اجراشدن در یک ماشین و چالشهای دیگری که در ارتباط با داده­های انبوه و در حال افزایش مطرح می­شود، در این رساله  سعی شده تا از چندین بعد به مساله نگریسته و راه­حلی ارائه شود ۱-  ابتدا به دلیل توزیع داده­ها در پایگاه داده­های متنوع نیاز به طراحی انباره داده می باشد که انباره داده­های سنتی پاسخگوی این حجم از داده­ها نمی­باشند و از پایگاه داده مبتنی بر هدوپ  که  Hive می­باشد، استفاده شده است.همچنین فرایند ELT  به جای  ETL  بکارگرفته شده است. ۲- بحث پارتیشن­بندی صحیح داده­ها می­باشد که  از الگوریتم PRBP^[۱]  (Dai & Lin, 2012) استفاده شده است. ۳- الگوریتم خوشه­بندی مبتنی بر چگالی  DBSCAN در  بسیاری از موارد ناکارآمد است از آنجائیکه هدف ما ارائه الگوریتمی برای چگالی متنوع است. برای این منظور از چگالی محلی هر نقطه برا جداسازی خوشه­های با چگالی متنوع استفاده شده است ۴- برای حل مشکل عدم پاسخگویی یک ماشین به حجم انبوه داده از نگاشت- کاهش برای پردازش داده­ها در چندین ماشین استفاده شده است. ۵- برای کاهش زمان جستجوی محلی برای داده­های افزایشی، داده­های جدید به طور جداگانه خوشه­بندی ونتایج خوشه­بندی جدید با خوشه­های قدیمی ادغام می­شوند. در این رساله نتایج پیاده­سازی الگوریتم پیشنهادی و مقایسه آن با الگوریتم­های موجود حاکی از سرعت بالای اجرای آن است. در بخش دوم رساله، با داده­های جریانی سروکار داریم که اسپارک بهتر از هدوپ برای پیاده­سازی پاسخ می­دهد و زمان اجرا در حد قابل توجهی کاهش می­یابد.

[۱] : Partition with Reduced boundary points

 

فهرست مطالب

فصل اول: کلیات تحقیق… ۲

۱-۱        مقدمه. ۳

۲-۱        بیان مسئله پژوهش…. ۳

۳-۱        اهمیت و ضرورت انجام پژوهش…. ۸

۴-۱          جنبه جدید بودن و نوآور بودن پژوهش…. ۹

۵-۱          اهداف پژوهش…. ۹

۱-۵-۱   هدف  آرمانی.. ۹

۲-۵-۱   اهداف اصلی.. ۹

۳-۵-۱      اهداف ویژه. ۱۰

۴-۵-۱   اهداف کاربردی… ۱۰

۱-۶        سؤالات پژوهش…. ۱۰

۱-۷        فرضیه پژوهش…. ۱۰

۱-۸        واژه‌ها و اصطلاحات فنی و تخصصی پژوهش…. ۱۱

۱-۹        روش پژوهش…. ۱۲

۱-۹-۱      شرح کامل روش تحقیق بر حسب هدف، نوع دادهها و نحوه اجرا ۱۲

۱-۹-۲   روش و ابزار گردآوری داده‌ها ۱۴

۱-۱۰      روش‌ها و ابزار تجزیه‌وتحلیل داده‌ها ۱۴

۱-۱۱      مدل مفهومی پژوهش(متغیرهای مورد بررسی در قالب یک مدل مفهومی و شرح چگونگی بررسی و اندازهگیری متغیرها). ۱۴

فصل دوم: مروری بر ادبیات تحقیق و پیشینه تحقیق… ۱۶

۲-۱ مقدمه………………… ۱۷

۲-۲   دادههای انبوه. ۱۸

۲ -۲-۱ مشخصات دادههای کلان از دید IBM… 20

۲-۲-۲ طبقهبندی دادههای کلان.. ۲۳

۲-۲-۴ اهمیت و کاربرد کلان داده. ۲۹

۲-۳-۱ اجزای اصلی و کارکردی هدوپ… ۳۳

۲-۳-۲ مزایا و معایب هدوپ… ۳۷

۲-۳-۳-۱ زیرپروژه های ذخیرهسازی داده. ۴۰

۲-۳-۳-۴ زیر پروژههای مدیریت داده. ۴۸

۲-۴-۱ مدل‌های به‌کارگیری رایانش ابری… ۵۰

۲-۴-۲ مدل‌های ارائه خدمات در رایانش ابری… ۵۱

۲-۴-۳  فناوری در سرویسهای ابری… ۵۲

۲-۴-۳-۱ معرفی سرویس وب آمازون (AWS) 53

۲-۴-۳-۲ سرویس‌ها و اجزای وب سرویس آمازون (کریمی, موسوی, نمازی, & بوشهریان, ۱۳۹۳): ۵۵

۲-۴-۴  ماشینهای مجازی در رایانش ابری… ۵۷

۲-۵-۳ انباره داده (Turban, Sharda, Delen, & King, 2011) 64

۲-۵-۳-۱ ویژگی های داده های درون انبار داده (Turban, Sharda, Delen, & King, 2011) 66

۲-۵-۳-۲ OLAP  در مقابل OLTP  (Turban, Sharda, Delen, & King, 2011) 66

۲-۵-۳-۳ روشهای ایجاد انبارداده (Turban, Sharda, Delen, & King, 2011) 69

۲-۵-۳-۴ انواع طراحی انباره داده  (Turban, Sharda, Delen, & King, 2011) 69

۲-۵-۳-۵ فرایند  ELT  و  ETL.. 70

۲-۵-۳-۶ Hive             ۷۶

۲-۶        اسپارک… ۷۸

۲-۶-۱   مقایسه هدوپ و اسپارک… ۸۰

۲-۷        پیشینه پژوهش…. ۸۲

۲-۷-۱ DBSCAN.. 82

۲-۷-۲  VDBSCAN.. 82

۲-۷-۳ LDBSCAN.. 84

۲-۷-۴ ST-DBSCAN.. 84

۲-۷-۵ DVBSCAN.. 86

۲-۷-۷ PACA-DBSCAN.. 88

۲-۷-۸ DMDBSCAN.. 88

۲-۷-۱۰ MR-DBSCAN.. 90

۲-۷-۱۱ الگوریتم FDBSCAN.. 90

۲-۷-۱۴ DBCLASD.. 92

۲-۷-۱۵ optics. 94

۲-۷-۱۶ the DENCLUE algorithm… 94

۲-۷-۱۷ MR-DBSCAN.. 95

۲-۷- ۱۸ برای دادههای نامتوازن.. ۹۶

۲-۷ -۱۹  کاهش تاخیر زمانی.. ۹۶

۲-۷ -۲۰ الگوریتم DBSCAN افزایشی.. ۹۷

۲-۷-۲۱ خوشههای محلی.. ۹۷

۲-۷-۲۲ پارتیشنبندی توسط نقاط مرزی… ۹۸

۲-۷-۲۳ ادغام خوشه های محلی با خوشه کلی.. ۹۹

۲-۸ مدل پیشنهادی تحقیق.. ۱۰۰

فصل سوم: روش شناسی پژوهش….. ۱۰۴

۳-۱ مقدمه. ۱۰۴

۳-۲ روش پژوهش…. ۱۰۵

۳-۲-۱ تعریف علم طراحی.. ۱۰۷

۳-۲-۲  چرخه عمومی طراحی.. ۱۰۸

۳-۳ دستورالعمل پژوهش علم طراحی هونر (March, Hevner, Park, & Ram, 2004) 109

دستورالعمل ۱- طراحی به عنوان یک ساخته. ۱۰۹

دستورالعمل ۲- ارتباط با مساله. ۱۱۰

دستورالعمل ۳-  ارزیابی طراحی.. ۱۱۱

دستورالعمل ۴-  سهم پژوهش…. ۱۱۱

دستورالعمل ۵-  دقت پژوهش…. ۱۱۱

دستورالعمل ۶- طراحی به عنوان یک فرایند جستجو.. ۱۱۱

دستورالعمل ۷-  ارتباطات پژوهش…. ۱۱۲

۳-۴   اعتبارسنجی و درستی سنجی.. ۱۱۲

۳-۵ مشکلات اعتبار سنجی و درستیسنجی.. ۱۱۴

۳-۶ جهان واقعی…. ۱۱۵

۳-۷    انواع اعتبارسنجی.. ۱۱۵

۳-۷-۱  اعتبارسنجی مدل مفهومی.. ۱۱۵

۳-۷-۲  اعتبارسنجی داده. ۱۱۵

۳-۷-۳ درستی سنجی و اعتبارسنجی جعبه سفید.. ۱۱۶

۳-۷-۴   اعتبار سنجی جعبه سیاه. ۱۱۶

۳-۷-۵  اعتبارسنجی آزمایشی.. ۱۱۶

۳-۷-۶  اعتبار سنجی راه حل.. ۱۱۷

۳-۸ روش تحقیق.. ۱۱۷

۳-۹ دیتاستها و روش های نرم افزاری مورد استفاده. ۱۱۷

۳-۹-۱ دیتاستهای مورد استفاده در رساله. ۱۱۷

۳-۹-۲ نرم افزارها و روشهای نرمافزاری مورد استفاده. ۱۱۷

۳-۹-۳   طراحی الگوریتم خوشهبندی دادههای انبوه با چگالی متفاوت با رویکرد نگاشت کاهش- الگوریتم    MR-VDBSCAN.. 118

۳-۹-۴  بهینهسازی الگوریتم پیشنهادی جهت خوشهبندی  افزایشی دادههای انبوه با چگالی متفاوت با رویکرد نگاشت کاهش – الگوریتم  IMR-VDBSCAN   ۱۲۶

۳-۹-۵ بهینه­سازی الگوریتم پیشنهادی جهت خوشهبندی  افزایشی دادههای انبوه با چگالی متفاوت در انباره داده ابری با رویکرد نگاشت کاهش –   IMR-VDBSCAN.. 127

۳-۱۰ معماری مدل پیشنهادی… ۱۲۸

۳-۱۱   ویژگیهای الگوریتم پیشنهادی… ۱۳۱

فصل چهارم: یافته­های پژوهش….. ۱۳۲

۴-۱        مقدمه. ۱۳۳

۴-۲        دیتاستهای مورد استفاده. ۱۳۴

۴-۳        یافته­های حاصل از اجرای مرحله اول الگوریتم پیشنهادی جهت خوشه­بندی دادههای انبوه با چگالی متفاوت با رویکرد نگاشت کاهش     ۱۳۴

۴-۴        یافته­های حاصل از اجرای مرحله اول و دوم الگوریتم پیشنهادی جهت خوشه­بندی  افزایشی دادههای انبوه با چگالی متفاوت در انباره داده ابری  با رویکرد نگاشت کاهش IMR-VDBSCAN.. 140

فصل پنجم: نتیجهگیری و پیشنهادات… ۱۴۳

۵-۱        مقدمه. ۱۴۴

۵-۲        بررسی دستیابی به اهداف پژوهش و پاسخگویی به سوالات پژوهش…. ۱۴۴

۵-۳        تحلیل دستاوردهای پژوهش…. ۱۴۵

۵-۴        نوآوری در پژوهش…. ۱۴۶

۵-۵        پیشنهادهای پژوهشی.. ۱۴۶

۵-۶        چالشها و محدودیتهای پژوهش…. ۱۴۷

۵-۷          نتیجهگیری… ۱۴۷

References  ۱۴۹