ارتقا خوشه‌بندی توزیع شده کلان‌داده

نوع: Type: پایان نامه

مقطع: Segment: کارشناسی ارشد

عنوان: Title: ارتقا خوشه‌بندی توزیع شده کلان‌داده

ارائه دهنده: Provider: سحر احسنی

اساتید راهنما: Supervisors: دکتر مرتضی یوسف صنعتی

اساتید مشاور: Advisory Professors: دکتر محرم منصوری زاده

اساتید ممتحن یا داور: Examining professors or referees: دکتر مهدی سخایی نیا - دکتر حسن ختن لو

زمان و تاریخ ارائه: Time and date of presentation: 1400/07/20 - ساعت 16

مکان ارائه: Place of presentation: دانشکده مهندسی

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

فایل: ّFile: تنزيل فایل