پایان نامه کارشناسی ارشد: بهینه‌سازی الگوریتم DBSCAN با استفاده از روشMap-Reduce بر روی داده‌های ترافیک شبکه

  برای دانلود و مطالعه کامل فایل در قالب فایل ورد قابل ویرایش و پی دی اف کلیک کنید
 


 

چکیده

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

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

واژه‌هاي كليدي:خوشه بندی، داده های حجیم، نگاشت کاهش، ترافیک شبکه

فصل ۱: فصل اول:
مقدمه

۱-۱- مقدمه

داده‌های حجیم به مجموعه داده‌هایی گفته می‌شود که مدیریت، کنترل و پردازش آن‌ها فراتر از توانایی ابزارهای نرم‌افزاری در یک ‌زمان مورد انتظار باشد. این داده‌ها به‌قدری بزرگ و حجیم هستند که با ابزارهای سنتی، تکنیک‌ها و ابزارهای معمول داده‌کاوی قابل‌تحلیل، آنالیز و داده‌کاوی نیستند(Chen, Mao et al. 2014). تحلیل، آنالیز دقیق و نهایتاً داده‌کاوی کلان داده‌ها افق بسیار وسیعی را در جهت بهبود خدمات سلامت، رشد اقتصادی و ارائه خدمات بهتر اجتماعی فراهم می‌نماید. تحلیل و نمایش این نوع داده‌ها چالشی بزرگ محسوب می‌شود.

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

خوشه‌بندی مبتنی بر چگالی با نام الگوریتم^[۱]DBSCAN عجین شده است. این الگوریتم در سال ۱۹۹۶ توسط استر^[۲] و همکارانش در (Ester, Kriegel et al. 1996)ارائه شد. هدف این الگوریتم شناسایی خوشه‌هایی با شکل دلخواه در محیط نویزی است. در این فصل ابتدا به بیان مسئله پرداخته می‌شود سپس اهداف پژوهش و نوآوری‌های پژوهش بیان می‌شود و در پایان ساختار کلی پایان‌نامه مشخص می‌شود.

۱-۲- بیان مسئله

داده‌های بزرگ ممکن است به‌اندازه اینترنت برای کسب‌وکار و جامعه مهم باشد؛ زیرا داده‌های بیشتر به تحلیل‌های دقیق‌تر می‌انجامد. تحلیل‌های دقیق‌تر منجر به تصمیم‌گیری‌های مطمئن بیشتری شده و تصمیمات بهتر می‌تواند به معنای کارایی بیشتر عملیات، کاهش هزینه‌ها و کاهش ریسک‌ها باشد. نمونه‌هایی از داده‌های انبوه شامل گزارش‌های وب، شبکه‌های حسگر، شبکه‌های اجتماعی، متون و اسناد اینترنتی، نمایه‌های جستجوهای اینترنتی، نجوم، مدارک پزشکی و … می‌باشد. چالش‌های مطرح در رابطه با داده‌های حجیم شامل استخراج، ذخیره‌سازی، جستجو، بازیابی، اشتراک، انتقال، آنالیز و امنیت می‌باشد (Chen and Zhang 2014).

امروزه مشکل اصلی داده‌ها، چگونگی پردازش داده‌ها با حجم بسیار بالاست. برای مقابله با حجم بالا از داده‌ها، نیاز به استفاده از ابزارهای قدرتمند برای کشف دانش و تکنیک‌های داده‌کاوی است. ترافیک شبکه‌های کامپیوتری که در این پژوهش بررسی می‌شود نیز از این امر مستثنا نیست. با آسان‌تر شدن دسترسی به اینترنت از یک‌سو و متصل شدن دستگاه‌های مختلف اعم از تلفن‌های هوشمند، رایانه‌های شخصی و تبلتها از سوی دیگر، حجم ترافیک شبکه چندین برابر شده است. استخراج اطلاعات مفید از این ترافیک و کسب دانش از الگوهای پنهان در آن، می‌تواند کاربردهای مختلفی نظیر بهبود سرویس، متعادل کردن بار و تشخیص ناهنجاری در شبکه داشته باشد. در طول زمان کاربردهای مختلف تحلیل داده‌های ترافیک شبکه، از کمبود نمونه جهت تحصیل مقاصد نهایی رنج برده‌اند. نمونه‌ای از این کاربردها تشخیص ناهنجاری در شبکه‌ها می‌باشد. در تشخیص ناهنجاری چالش اصلی نرخ بالای هشدارهای اشتباه است. هنگام دسته‌بندی کردن ترافیک شبکه و تشخیص برنامه‌های مختلف تحت شبکه نیز اطمینان از اینکه در مجموعه داده مورداستفاده به‌اندازه کافی از همه برنامه‌های موجود نمونه وجود دارد، یک چالش محسوب می‌شود(Ramírez‐Gallego, García et al. 2016).

خوشه‌بندی یکی از محبوب‌ترین ابزارها برای اکتشاف و سازمان‌دهی داده‌های بزرگ و بهبود عملکرد برای پردازش می‌باشد. با توجه به رشد نمایی در تولید داده‌ها این مسئله که چگونه و بر چه اساسی این داده‌ها خوشه‌بندی شوند، مطرح می‌شود. اگرچه داده‌کاوی می‌تواند به‌عنوان منشأ اصلی خوشه‌بندی در نظر گرفته شود، اما از آن در زمینه‌های دیگر نیز مانند انفورماتیک زیستی، انرژی، یادگیری ماشین، شبکه، تشخیص الگو و … استفاده می‌شود.(He, Tan et al. 2014) محققان ابتدا از الگوریتم‌های خوشه‌بندی به‌منظور رسیدگی به هزینه محاسباتی پیچیده و به‌تبع آن افزایش مقیاس‌پذیری و سرعت استفاده می‌کردند(Shim 2013). کار با داده‌های بزرگ نیز در سال‌های اخیر با چالش‌های بیشتری روبرو شده که خواستار تحقیقات بیشتری برای بهبود الگوریتم‌های خوشه‌بندی است.

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

مشکلات DBSCAN، خوشه‌بندی داده‌های با چگالی متغیر و همچنین محاسبات مربوط به دو مقدار eps و minpts می‌باشد. همچنین DBSCAN می‌تواند خوشه‌های با اشکال دلخواه را پیدا کند؛ اما در خصوص مجموعه داده‌های دارای خوشه‌هایی با چگالی متفاوت ضعف دارد. این الگوریتم توانایی تشخیص هم‌زمان خوشه‌هایی با چگالی متفاوت را ندارند. این در حالی است که داده‌های مرتبط با ترافیک شبکه دارای چگالی‌های متفاوتی هستند. پراکندگی ویژگی‌های بسته‌های مرتبط با برنامه‌های مختلف شبکه یا پراکندگی نمونه‌های هنجار و ناهنجار در شبکه لزوماً مشابه یکدیگر نیستند. تاکنون روش‌های مختلفی برای حل این مشکلات مطرح‌شده که در بخش پیشینه پژوهش به آن می‌پردازیم؛ اما همان‌طور که بررسی خواهیم کرد این روش‌ها مشکلات دیگری از قبیل کاهش سرعت پردازش و انجام شدن به‌صورت غیر موازی را دارند. روش پیشنهادی جهت خوشه‌بندی مبتنی بر چگالی داده‌ها در مدل برنامه‌نویسی نگاشت کاهش[۳] است. نگاشت کاهش یک مدل برنامه‌نویسی پردازش و تولید مجموعه داده‌های بزرگ با استفاده از یک الگوریتم موازی و توزیع‌شده روی یک خوشه پردازشی است. نگاشت کاهش به دلیل ساده بودن می‌تواند به‌صورتی مؤثر خرابی‌ها را اداره کند و درنتیجه مقیاس‌پذیری آن به چند هزار گره می‌رسد.

یک برنامه نگاشت کاهش از یک روال نگاشت و یک روال کاهش تشکیل شده است. روال نگاشت فیلتر و مرتب کردن داده‌ها را بر عهده دارد و روال کاهش عملیات خلاصه‌سازی را انجام می‌دهد(Chen, Alspaugh et al. 2012). نکته اصلی در خصوص چارچوب نگاشت کاهش توابع نگاشت و کاهش نیستند بلکه مقیاس‌پذیری و تحمل خطاست که این چارچوب را به یک چارچوب مقبول تبدیل کرده است. کتابخانه‌های زیادی در زبان‌های مختلف برای انجام عملیات نگاشت کاهش توسعه داده‌شده‌اند. هدوپ یکی از پیاده‌سازی‌های متن‌باز نگاشت کاهش به شمار می‌رود. اسپارک، محصول دیگر است که نگاشت کاهش را با هدف افزایش سرعت و در حافظه اجرا می‌کند.

نگاشت کاهش را می‌توان محاسباتی توزیع‌شده و موازی با پنج گام در نظر گرفت:

۱-    آماده‌سازی ورودی نگاشت

۲-     اجرای کد نگاشت کاربر

۳-     بر زدن خروجی نگاشت به پردازنده کاهش

۴-    تولید خروجی نهایی

 استفاده از فن‌های نظیر توزیع کار با استفاده از روش نگاشت – کاهش یا موازی‌سازی خوشه‌ها خود جای تأمل دارد. برتری نگاشت کاهش، در این است که اجازه می‌دهد تا پردازش عملیات پردازش و کاهش توزیع شود؛ بنابراین قصد داریم به‌صورت ویژه بر روی این موضوع و استفاده از این تکنیک برای روش پیشنهادی نیز اقدام کرده و امید می‌رود که این روش بر روی الگوریتم‌ها مفید بوده و کارایی الگوریتم را بهبود می‌بخشد. روش پیشنهادی شامل مراحل تقسیم فضای داده، خوشه‌بندی محلی، ادغام نتایج و برچسب‌زنی نهایی است که تمامی مراحل در مدل برنامه‌نویسی نگاشت کاهش ارائه شده‌اند. برای تقسیم فضا سیاست‌های متفاوت ارائه‌شده هرکدام تا حدی از خصوصیات آماری داده استفاده می‌کنند. روش خوشه‌بندی محلی روشی انعطاف‌پذیر برای شناسایی خوشه‌هایی با چگالی متفاوت است و مرحله ادغام نتایج به‌صورت خاص و مطابق با این روش ارائه می‌شود.

برای دانلود کامل فایل پایان نامه کلیک کنید

فصل ۲: فصل دوم:
مفاهیم پیش‌زمینه و مروری بر ادبیات

۲-۱- مقدمه

در انجام هر پژوهش با هدف نوآوری در حوزه‌های علمی، ابتدا باید تلاش‌های صورت گرفته قبلی در آن حوزه بررسی‌شده و با توجه به نقاط قوت و ضعف روش‌های مورداشاره، طرح یا روش جدید جهت پیشرفت حوزه موردنظر ارائه شود. در این فصل، در بخش ۲-۲ به بررسی مفاهیم پایه‌ای مبحث خوشه‌بندی داده‌های عظیم پرداخته می‌شود. سپس در بخش ۲-۳ ادبیات این حوزه مرور می‌شوند. ابتدا با توجه به خصوصیات مسئله حوزه پژوهش محدودتر گشته و با توجه به این خصوصیات پژوهش‌های موجود در مبحث خوشه‌بندی مبتنی بر چگالی، خوشه‌بندی داده‌های عظیم و درنهایت پیوند این دو مبحث در بخش ۲-۳-۴ تحت عنوان خوشه‌بندی مبتنی بر چگالی داده‌های عظیم بررسی خواهد شد. نتایج بررسی ادبیات موضوع در بخش ۲-۴ خلاصه می‌شوند.

۲-۲- تعاریف، اصول و مبانی نظری

در این قسمت جهت روشن بودن ادامه مباحث در قسمت‌های بعدی، مفاهیم مطرح در مباحث خوشه‌بندی داده‌های عظیم مطرح می‌گردند.

۲-۲-۱- خوشه‌بندی

در منابع مختلف برای خوشه‌بندی تعاریف گوناگونی ارائه داده‌اند. برخی از تعاریف ارائه‌شده برای خوشه‌بندی از این قرارند:

·         خوشه‌بندی یا تحلیل خوشه‌های داده به عملیات تقسیم داده‌ها به تعدادی گروه (خوشه) جهت خلاصه‌سازی یا بهبود درک آن‌ها گفته می‌شود. طی عملیات خوشه‌بندی، سعی بر آن شده که داده‌های مشابه در یک خوشه قرار بگیرند.(Fahad, Alshatri et al. 2014)

·         مسئله خوشه‌بندی مسئله قرار دادن داده‌ها در مجموعه‌ای گروه (خوشه) است به‌صورتی که داده‌های یک خوشه به یکدیگر شبیه‌تر باشند تا داده‌های خوشه‌های دیگر.(Jain 2010)

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

با قرار دادن تعداد زیادی نمونه در تعداد بسیار کمتری خوشه، مسئله ساده می‌شود. خوشه‌بندی شکلی از مدل کردن داده است. بدین ترتیب ریشه خوشه‌بندی را می‌توان در ریاضیات و آمار جستجو کرد. از دید یادگیری ماشین، خوشه‌بندی به پیدا کردن الگوهای مخفی مرتبط می‌شود و به جستجو به دنبال خوشه‌ها یادگیری بی ناظر به‌حساب می‌آید. بدین ترتیب خوشه‌بندی یادگیری بی ناظر یک مفهوم مخفی در داده است. با اعمال خوشه‌بندی در کاربردهای داده‌کاوی سه پیچیدگی به مسئله افزوده می‌گردد: (الف) داده‌های زیاد (ب) نمونه‌هایی با خصیصه‌های زیاد (ج) خصیصه‌هایی با انواع مختلف. این پیچیدگی‌ها نیازمندی‌های محاسباتی بسیار زیادی دارند که برای روش‌های خوشه‌بندی کلاسیک چالش‌های بزرگی ایجاد می‌کند(Rana, Jasola et al. 2011). در این پژوهش تمرکز بر پیچیدگی اول، یعنی داده‌های زیاد در ترافیک شبکه بوده است.

۲-۲-۲- داده‌های عظیم

داده‌های عظیم واژه‌ای است که برای توصیف مجموعه داده‌هایی با اندازه زیاد، تنوع فراوان و ساختار پیچیده به کار می‌رود به‌طوری‌که ذخیره‌سازی، تحلیل و به تصویر کشیدن آن‌ها با سختی مواجه است. به فرآیند پژوهش در مقادیر عظیم داده جهت افشای الگوهای پنهان و هم‌بستگی‌های مخفی در آن‌ها نیز تحلیل داده‌های عظیم گفته می‌شود(Chen, Mao et al. 2014). درواقع، در هر برهه‌ای از زمان می‌توان وجود داده‌هایی را متصور شد که پردازش آن‌ها فراتر از توانایی‌های پردازشی رایانه‌های متداول است؛ اما آنچه باعث مطرح‌شدن هر چه بیشتر داده‌های عظیم در زمان حال کرده، تسهیل امکان پردازش این نوع داده‌ها در محیط‌های توزیع‌شده است.

۲-۲-۳- مدل برنامه‌نویسی نگاشت کاهش

نگاشت کاهش[۴] (Dean and Ghemawat 2008)یک مدل برنامه‌نویسی پردازش و تولید مجموعه داده‌های بزرگ با استفاده از یک الگوریتم موازی و توزیع‌شده روی یک خوشه پردازشی است. نگاشت کاهش به خاطر ساده بودن می‌تواند به‌صورتی مؤثر خرابی‌ها را اداره کند و در نتیجه مقیاس‌پذیری آن به چند هزار گره می‌رسد. استفاده از مدل نگاشت کاهش برای تحلیل داده‌ها رایج شده است.

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

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

پردازش نگاشت کاهش می‌تواند برای داده‌هایی که در یک فایل سیستم ذخیره شده‌اند داده‌های غیر ساخته (و هم برای داده‌های یک پایگاه داده ) داده‌های ساخت‌یافته ( اجرا شود. نگاشت کاهش می‌تواند از محلی بودن داده‌ها بهره برده و آن‌ها را نزدیک به محل ذخیره‌سازی‌شان پردازش کند تا فاصله مخابره شدن آن‌ها کاهش یابد. از یک جنبه، مطابق شکل ۲-۱، یک کار در مدل نگاشت کاهش سه مرحله دارد: نگاشت، برزدن و کاهش.

·         مرحله نگاشت: هر گره کارگر تابع نگاشت را روی داده‌های محلی اعمال می‌کند و خروجی را به‌صورت موقتی ذخیره می‌سازد. یک گره کنترلی نسخه‌های افزونگی را مدیریت می‌کند تا در هر خروجی تنها یک‌بار پردازش شود.

·         مرحله بر زدن: گره‌های کارگر داده را با توجه به کلیدهای خروجی آن‌ها دوباره توزیع می‌کنند. این کلیدها در مرحله نگاشت تولید شده‌اند. بر زدن به‌گونه‌ای رخ می‌دهد که تمامی داده‌هایی با کلید یکسان به یک گره کارگر برسند.

·         مرحله کاهش: گره‌های کارگر در این مرحله به‌صورت موازی هر گروه از داده‌های خروجی را بر اساس کلید آن‌ها پردازش می‌کنند.

·       برای دانلود کامل فایل پایان نامه کلیک کنید

شکل ۲-۱:  دسترس‌پذیری با چگالی (Ester, Kriegel et al. 1996)

به‌علاوه با فرض نمونه p، اگر این نمونه در اپسیلون همسایگی نمونه‌ای «مستقیماً دسترس‌پذیر با چگالی» یا «دسترس‌پذیری با چگالی» از نمونه q باشد، آنگاه نمونه p نیز در دسترس‌پذیر با چگالی از نمونه q خواهد بود علاوه بر این، دو نمونه p و q متصل با چگالی هستند، اگر نمونه‌ای مانند o وجود داشته باشد که هر دو نمونه p و q دسترس‌پذیر با چگالی از نمونه o باشند. (شکل ۲-۴)

این تعاریف از اتصال با چگالی و دسترس‌پذیری با چگالی تعریف الگوریتم DBSCAN از خوشه را می‌سازند. در این الگوریتم، خوشه به‌عنوان مجموعه‌ای از نمونه‌های یک مجموعه داده تعریف می‌شود که به یک نمونه مرکزی متصل با چگالی باشند. هر نمونه‌ای که در هیچ خوشه‌ای عضویت نداشته باشد به‌عنوان نویز شناخته خواهد شد.

شکل ۲-۲:  اتصال با چگالی(Ester, Kriegel et al. 1996)

فصل ۳: برای دانلود کامل فایل پایان نامه کلیک کنید

عملیات خوشه‌بندی الگوریتم H-Density در دو مرحله صورت می‌پذیرد.

در گام اول، خوشه‌های مرکزی بدین‌صورت تشکیل می‌شوند.

ابتدا همه نقاط به‌عنوان خوشه‌های مرکزی شناخته می‌شوند. سپس چگالی هر نمونه محاسبه می‌شود. در گام بعد هر نمونه به خوشه مرکزی همسایه‌ای (در شعاع R) که بیشترین چگالی را داشته باشد ملحق می‌شود در پایان خوشه‌های مرکزی که از حد آستانه نویز کوچک‌تر باشند برچسب نویز می‌گیرند.

در گام دوم خوشه‌های مرکزی باهم ادغام می‌شوند تا خوشه‌های اصلی را تشکیل دهند:

ابتدا هر خوشه مرکزی یک خوشه شناخته می‌شود. سپس این دو مرحله تا رسیدن به K خوشه مدنظر ادامه پیدا می‌کنند:

۱٫ فاصله هر دو خوشه با استفاده از معیار معرفی‌شده محاسبه می‌شود.

۲٫ دو خوشه‌ای که کم‌ترین فاصله را از یکدیگر دارند باهم ادغام می‌شوند

درنهایت خوشه‌های مرکزی نویز به نزدیک‌ترین خوشه نسبت داده می‌شوند.

از مهم‌ترین معایب خوشه‌بندی H-Density می‌توان به پارامتر K اشاره کرد که در مقایسه با الگوریتم DBSCAN یک ضعف عمده به شمار می‌رود. هم‌چنین با انتساب نقاط نویز به خوشه‌های نهایی، امکان تشخیص نویز از بین می‌رود.

هر سه روش مورداشاره به‌صورت سلسله مراتبی با چگالی‌های متفاوت خوشه‌ها برخورد کرده‌اند؛ اما استفاده از روش‌های سلسله مراتبی به پیچیدگی مسئله افزوده و تصمیم‌گیری در خصوص نحوه خوشه‌بندی را مشکل‌تر می‌کند. دلیل این امر آن است که تصمیم‌گیری در خصوص متوقف کردن ادغام خوشه‌ها با یکدیگر با شکستن آن‌ها به خوشه‌های کوچک‌تر، امری پیچیده محسوب می‌شود.

در (Esfandani, Sayyadi et al. 2012) روشی بانام GDCLU برای شناسایی خوشه‌هایی با چگالی مختلف معرفی‌شده است. در GDCLU ابتدا فضای داده‌ها به یک توری تقسیم‌بندی می‌شود. سپس تعداد نقاط هر قسمت به‌عنوان چگالی آن قسمت در نظر گرفته می‌شود. میانگین چگالی یک قسمت، به چگالی قسمت‌های همسایه آن وابسته است. GDCLU پس از تعیین میانگین چگالی یک قسمت، مفهوم متوسط میانگین چگالی یک قسمت را نیز با توجه به میانگین چگالی قسمت‌های آن تعیین می‌کند؛ یعنی میانگین‌های چگالی نیز محاسبه می‌شود. پس‌ازآن با تعریف واریانس متوسط میانگین چگالی گرید، الگوریتم GDCLU قسمت‌های همسایه در فضا که چگالی آن‌ها به یکدیگر مشابه هست را با یکدیگر ادغام می‌کند. اندازه‌گیری این مشابهت، به میانگین چگالی، متوسط میانگین چگالی و واریانس آن وابسته است.

اگرچه نتایج گزارش (Esfandani, Sayyadi et al. 2012) می‌تواند امیدوارکننده باشد اما باید توجه داشت که با تغییر نگاه به خوشه‌بندی مبتنی بر چگالی و تقسیم فضا به سبک GDCLU، مقداری از جزئیات توسط الگوریتم کنار می‌رود نمی‌توان انتظار داشت خوشه‌هایی با هر شکل در فضا شناسایی شوند. از سوی دیگر انتخاب اندازه هر قسمت از توری تأثیر بسیار زیادی بر نتیجه خوشه‌بندی خواهد داشت.

درنهایت، در جدول ۲-۱ ویژگی‌های مختلف روش‌های خوشه‌بندی مبتنی بر چگالی با یکدیگر مقایسه شده‌اند. در این مقایسه، شناسایی خوشه‌هایی با چگالی متفاوت به خاطر طبیعت مسئله خوشه‌بندی داده‌های شبکه موردتوجه قرارگرفته است و سه ویژگی تکراری بودن، سلسله مراتبی بودن و امکان موازی شدن، جهت بررسی امکان توسعه روش‌ها برای استفاده در محیط توزیع‌شده آورده شده‌اند. روش‌هایی که تکراری و سلسله مراتبی باشند، به‌سختی در محیط توزیع‌شده قابل‌استفاده خواهند بود. امکان اجرای الگوریتم به‌صورت موازی نیز از الزامـات اجرای آن در محیط توزیع‌شده است. بدیـن ترتیب می‌توان مشاهده کرد که الگوریتم‌های DBSCAN و GDCLU ویژگی‌های لازم را دارند؛ اما روش GDCLU نیز باعث از دست رفتن جزئیات در خوشه‌بندی‌شده و بدین ترتیب یک نقطه‌ضعف دیگر دارد.

جدول ۳-۱: مقایسه روش‌های خوشه‌بندی مبتنی بر چگالی

	شناسایی خوشه‌هایی با چگالی متفاوت	خوشه‌بندی تکراری	خوشه‌بندی سلسله مراتبی	امکان موازی شدن الگوریتم
DBSCAN	û	û	û	ü
OPTICS	ü	ü	ü	û
DBCLASD	ü	ü	û	û
VDBSCAN	ü	ü	û	û
H-Density	ü	ü	ü	û
GDCLU	ü	û	û	ü

۳-۱-۲- روش‌های خوشه‌بندی مبتنی بر چگالی داده‌های عظیم

با توجه به انتخاب روش‌های مبتنی بر چگالی جهت خوشه‌بندی ترافیک شبکه با حجم زیاد در این پژوهش، در ادامه روش‌های خوشه‌بندی مبتنی بر چگالی داده‌های عظیم بررسی خواهد شد.

در سال‌های اخیر تلاش‌هایی برای خوشه‌بندی داده‌های عظیم با استفاده از مدل نگاشت کاهش انجام‌شده است. روش‌های DBSCAN-MR و DBSCAN-MR (He, Tan et al. 2014) پژوهش‌هایی هستند که بر اجرای موازی الگوریتم DBSCAN با استفاده از مدل برنامه‌نویسی نگاشت کاهش تمرکز دارند. نقطه اشتراک این روش‌ها، آن است که داده‌های مجاور را تا حد امکان به یک گره پردازشی ارسال می‌کنند.

مراحل اصلی هر سه روش ارائه‌شده را می‌توان به این صورت خلاصه کرد:

·         تقسیم داده‌ها برای خوشه‌بندی

·       برای دانلود کامل فایل پایان نامه کلیک کنید

کیم و دیگران در (Kim, Shim et al. 2014) روش DBSCAN-MR را برای خوشه‌بندی مبتنی بر چگالی داده‌های عظیم ارائه کرده‌اند. در روش خوشه‌بندی محلی DBCURE، همسایگی نمونه‌ها به‌صورت بیضوی و با استفاده از یک تابع گوسی چند متغیره محاسبه‌شده و در اساس آن مفاهیم موجود در روش DBSCAN، مثل دسترس‌پذیری با چگالی و متصل با چگالی تعریف‌شده‌اند. در این تابع گوسی چند متغیره از ماتریس کوواریانس نمونه شده است. برای محاسبه ماتریس کوواریانس که نشان‌دهنده توزیع نمونه‌ها اطراف یک نمونه است. فضای اطراف هر نمونه به یک شبکه توری شکسته شده و با توجه به اینکه بین نمونه و همسایه آن چند سلول فاصله است، میانگین فاصله وزن‌دار نمونه‌ها محاسبه‌شده و ماتریس کوواریانس ساخته می‌شود.

الگوریتم DBCURE-MR توسعه‌ای از الگوریتم DBCURE جهت خوشه‌بندی داده‌های عظیم با استفاده از مدل نگاشت کاهش است. این روش چهار گام دارد که عبارت‌اند از: (۱) تخمین ماتریس کوواریانس، (۲) محاسبه‌ی همسایگی‌های بیضوی (۳) شناسایی نمونه‌های مرکزی و (۴) ادغام خوشه‌ها.

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

 روش DBCURE-MR برای شناسایی خوشه‌هایی با چگالی متفاوت، همسایگی را به سمت نمونه‌ها متمایل می‌کند. (شکل ۲-۱۱)؛ اما هم چنان برای ادغام نمونه‌ها به حداقل چگالی وابسته است و براین اساس عمل می‌کند.

شکل ۳-۲:  همسایگی بیضوی در DBCURE (Kim, Shim et al. 2014)

درواقع، DBCURE بیش از آن‌که خوشه‌هایی یا چگالی متفاوت پیدا کند، خوشه‌هایی را پیدا می‌کند که چگالی درون آن‌ها متفاوت است. مجموعه داده‌های ساختگی مورداستفاده برای ارزیابی روش DBCURE نیز نشان می‌دهند که چگالی خوشه‌های موجود در مجموعه داده تفاوت زیادی با یکدیگر ندارد بلکه این چگالی درون یک خوشه است که از ناحیه‌ای به ناحیه‌ی دیگر تفاوت دارد.(شکل ۲-۱۲)

شکل ۳-۳:  یکی از مجموعه داده‌های به‌کاررفته برای ارزیابی DBCURE (Kim, Shim et al. 2014)

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

جدول ۳-۲: مقایسه روش‌های توزیع شدة خوشه‌بندی مبتنی بر چگالی

	شناسایی خوشه‌هایی با چگالی متفاوت	شناسایی خوشه‌هایی با تفاوت چگالی درون خوشه‌ها
MR-DBSCAN	û	û
DBSCAN-MR	û	û
DBCURE	û	ü

۳-۲- نتیجه‌گیری

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

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

فصل ۴: فصل سوم:

ارائه روش پیشنهادی

۴-۱- مقدمه

در این پژوهش روشی انعطاف‌پذیر برای خوشه‌بندی مبتنی بر چگالی داده‌های عظیم ارائه می‌شود. شکل ۳-۱ مراحل مختلف خوشه‌بندی داده‌های عظیم در روش پیشنهادی را نشان می‌دهد.

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

روش نگاشت – کاهش مزایایی دارد که می‌تواند بسیاری از مشکلات روش‌های قبلی را بر طرف نماید. از این مزایا می‌توان به موارد زیر اشاره نمود:

۱-    روش اجرایی برای پردازش، تولید و حل مسائل محاسباتی توزیع شده و موازی در داده‌های بزرگ

۲-    سادگی و قابلیت پیاده‌سازی با زبان‌های مختلف برنامه نویسی

۳-    توزیع خودکار برنامه‌ها بین ماشین‌های مختلف

۴-    نمایه‌سازی در یک خوشه از مجموعه داده‌های بزرگ

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

چارچوب روش پیشنهادی برای خوشه‌بندی داده‌های عظیم به‌صورت انعطاف‌پذیر، مشابه چارچوب خوشه‌بندی روش‌های MR-DBSCAN و DBSCAN-MR است؛ یعنی ابتدا فضا به زیر فضای مجزا تقسیم می‌شود، سپس نمونه‌های داخل هر زیر فضا خوشه‌بندی خواهد شد و درنهایت نتایج قسمت‌های مختلف با یکدیگر ادغام می‌گردند.

شکل ۴-۱: چارچوب خوشه‌بندی داده‌های عظیم

در این فصل ابتدا در بخش ۳-۲ مسئله تقسیم فضای داده مطرح می‌گردد. پس‌ازآن، یک روش خوشه‌بندی مبتنی بر چگالی انعطاف‌پذیر در بخش ۳-۳ ارائه خواهد شد. ازجمله ویژگی‌های این الگوریتم، امکان شناسایی خوشه‌هایی با چگالی متفاوت از یک‌سو و سادگی تنظیم پارامترها از سوی دیگر است. درحالی‌که تنظیم پارامتر برای الگوریتم DBSCAN و توسعه‌های مختلف آن با افزایش ابعاد و تعداد نمونه‌ها سخت‌تر می‌شود. پارامتر انعطاف‌پذیری روش پیشنهادی یک بازة محدود داشته و تنظیم آن ساده‌تر است.

در بخش۳-۳ نوبت به بررسی نحوه ادغام نتایج خوشه‌بندی محلی می‌رسد. روش ادغام به روش خوشه‌بندی محلی وابسته است. با توجه به اینکه روش خوشه‌بندی محلی پیشنهادی شعاع گسترش خوشه‌ها را محدود نمی‌کند، امکان استفاده از روش ادغام الگوریتم‌های MR-DBSCAN و DBSCAN-MR در اینجا وجود ندارد. چارچوب خوشه‌بندی داده‌های عظیم از ابتدا تا انتها، در مدل برنامه‌نویسی نگاشت کاهش بیان خواهد شد.

۴-۲-  تقسیم فضای داده

همان‌طور که در فصل ۲ بدان اشاره شد، پارامترهای تحلیل هزینه خوشه‌بندی که در MR-DBSCAN به کار گرفته شده‌اند، بسته به نحوه به‌کارگیری مدل نگاشت کاهش نقش متفاوتی خواهند داشت. اینکه الگوریتم خوشه‌بندی در تابع نگاشت انجام می‌شود یا تابع کاهش، در تعداد دسترسی‌های به دیسک تأثیر دارد. ضمن آن‌که در روش پیشنهادی، به‌جای پرس‌وجوهایی با شعاع مشخص حول یک نمونه که اصطلاحاً به آن‌ها region query گفته می‌شود، تنها نزدیک‌ترین همسایه‌ها مورد پرس‌وجو قرار می‌گیرند. این امر پرس‌وجو را ساده‌تر می‌سازد و می‌تواند موجب سریع شدن مرحله خوشه‌بندی محلی شود.

در روش DBSCAN-MR، تقسیم فضا با توجه به تعداد نقاط موجود در مرحله ادغام نتایج انجام می‌شود. چون روش خوشه‌بندی پیشنهادی منعطف است و شعاع همسایگی نمونه‌ها در آن ثابت نیست، نمی‌توان مرحله ادغام را شبیه به آن چه که DBSCAN-MR یا MR-DBSCAN صورت می‌پذیرد انجام داد. بدین ترتیب راهی برای کمینه کردن تعداد نقاط لازم برای ادغام نیز قبل از انجام خوشه‌بندی وجود ندارد.

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

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

برای تعیین آن‌که یک بخش p از فضا چگونه به بخش‌های کوچک تر تقسیم شود، باید در خصوص دو مسئله تصمیم گیری کرد:

·         محور تقسیم بخش p

·         نقطه تقسیم بخش p

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

·         طول بخش p در راستای محورها

·         واریانس نمونه‌های موجود در بخش p در راستای محورها

با در نظر گرفتن طول هر محور و انتخاب محوری که بیشترین طول را دارد، زیر بخش‌هایی که از شکستن بخش p تولید خواهد شد گستردگی بیشتری خواهند داشت؛ یعنی با انتخاب محوری که بخش p در راستای آن بیشترین طول را دارد تا حد امکان از باریک شدن زیر بخش‌ها جلوگیری می‌شود (شکل ۳-۲). باریک نشدن زیر بخش‌ها از آن نظر مهم است که بخش‌های باریک‌تر نمونه‌های مرزی بیشتری تولید خواهند کرد.

شکل ۴-۲: باریک شدن زیر قسمت‌ها

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

شکل ۴-۳:  نمونه‌ای از پراکندگی متفاوت نمونه‌ها در طول خصیصه‌های مختلف

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

برای دانلود کامل فایل پایان نامه کلیک کنید

فصل ۵: فصل چهارم:

ارزیابی و مقایسه کارایی روش پیشنهادی از طریق شبیه سازی

۵-۱- مقدمه

این قسمت به ارزیابی روش پیشنهادی با استفاده از مجموعه داده‌های ساختگی، استاندارد و شبکه مربوط می‌شود. هرچند ارزیابی بصری روش‌های داده‌کاوی دقیق نیست، همواره برای اثبات مفهوم روش‌های پیشنهادی به کار گرفته می‌شود. برای ارزیابی روش پیشنهادی و بررسی میزان موفقیت این روش در شناسایی خوشه‌هایی با هر شکل و چگالی دلخواه، دو مجموعه داده «هلال‌ها» و «آتش‌بازی» از خوشه‌هایی با چگالی‌های متفاوت تشکیل شده‌اند. در ارزیابی روش خوشه‌بندی محلی، از پنج مجموعه داده استاندارد UCI استفاده شده است. درخصوص داده‌های شبکه، از بخشی از مجموعه داده KDDCup99 در کاربرد تشخیص ناهنجاری آماده استفاده شده است. اطلاعات مربوط به مجموعه داده‌ها در بخش ۴- ۲ آمده‌اند.

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

در تمامی نتایجی که برای روش‌های مختلف ارائه می‌گردند. بهترین نتایج به‌دست‌آمده به ازای پارامترهای مختلف هر روش گزارش شده است.

۵-۲-  معرفی مجموعه داده‌ها

در این بخش انواع مجموعه داده‌هایی که برای ارزیابی روش پیشنهادی به‌کاررفته‌اند معرفی خواهند شد. هر نوع داده برای بررسی هدفی خاص به‌کاررفته که در بخش مربوطه توضیحات آن ارائه شده است.

۵-۲-۱- داده‌های ساختگی

دو مجموعه داده هلال و آتش‌بازی در این پایان‌نامه برای تائید توانایی روش پیشنهادی در شناسایی خوشه‌هایی با شکل دلخواه و چگالی متفاوت به کار رفته‌اند. نتایج خوشه‌بندی این داده‌ها برخلاف داده‌های دیگر قابل مشاهده است. درواقع ارزیابی بصری نتیجه‌ی خوشه‌بندی چنین داده‌هایی می‌تواند علل ضعف و قوت یک روش را نشان دهد.

در مجموعه داده‌ی آتش‌بازی (a) در شکل ۴-۱ هفت خوشه با چگالی‌های بسیار متفاوت دیده می‌شود. فاصله خوشه‌ها از یکدیگر به‌گونه‌ای نیست که الگوریتم DBSCAN بتواند با پارامترهای مناسب آن‌ها را از یکدیگر متمایز سازد (این موضوع در بخش ۴-۴ نشان داده خواهد شد). قسمت (b) در شکل ۴-۱ مجموعه داده هلال را نشان می‌دهد. این مجموعه نیز دارای هفت خوشه با چگالی متفاوت به شکل هلال ماه است.

شکل ۵-۱: مجموعه داده‌های ساختگی: آتش‌بازی (a) و هلال‌ها (b)

شناسایی خوشه‌های چنین مجموعه داده‌ای نظیر هلال‌ها برای روش‌های مبتنی بر چگالی مقدور است. خلاصه اطلاعات این دو مجموعه داده در جدول ۴-۱ آمده است.

جدول ۵-۱: مجموعه داده‌های ساختگی

نام مجموعه داده	تعداد خصیصه	تعداد خوشه‌ها	تعداد نمونه‌ها	بیشترین اختلاف چگالی
هلال‌ها	۲	۷	۷۰۰	۸ برابر
آتش‌بازی	۲	۷	۱۴۰۰	۷۰ برابر

۵-۲-۲- داده‌های استاندارد با حجم کم

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

از مجموعه داده‌های UCI به‌عنوان داده‌های واقعی جهت ارزیابی خوشه‌بندی محلی استفاده‌شده‌اند. مجموعه داده‌های iris، wine، ecoli، diabetes و seeds از پایگاه مجموعه داده‌های UCI در این ارزیابی به‌کار رفته‌اند. خلاصه اطلاعات مربوط به این مجموعه داده‌ها در جدول ۴-۲ آمده است.

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

جدول ۵-۲: خلاصه اطلاعات مجموعه داده‌های UCI

نام مجموعه داده	تعداد خصیصه‌ها	تعداد خوشه‌ها / دسته‌ها	تعداد نمونه‌ها
Iris	4	3	150
Ecoli	8	8	336
Diabetes	10	214	442
Winc	13	3	178
Soods	7	3	210

مجموعه داده ecoli مربوط به ساختارهای پروتئینی است.۳۳۶ نمونه که هر یک دارای هشت خصیصه‌اند این مجموعه را تشکیل می‌دهند. در مجموعه هشت دسته‌ی مختلف در ecoli وجود دارند که تعداد نمونه‌های متعلق به هرکدام از ۲ تا ۱۴۳ نمونه متغیر است.

برای دانلود کامل فایل پایان نامه کلیک کنید

---