Abstract
A linear scaling parallel clustering algorithm implementation and its application to very large datasets for cluster analysis is reported. WaveCluster is a novel clustering approach based on wavelet transforms. Despite this approach has an ability to detect clusters of arbitrary shapes in an efficient way, it requires considerable amount of time to collect results for large sizes of multi-dimensional datasets. We propose the parallel implementation of the WaveCluster algorithm based on the message passing model for a distributed-memory multiprocessor system. In the proposed method, communication among processors and memory requirements are kept at minimum to achieve high efficiency. We have conducted the experiments on a dense dataset and a sparse dataset to measure the algorithm behavior appropriately. Our results obtained from performed experiments demonstrate that developed parallel WaveCluster algorithm exposes high speedup and scales linearly with the increasing number of processors
چکیده
پیاده سازی الگوریتم کلاسترینگ موازی مقیاس گذاری خطی و کاربرد آن در دیتاستهای خیلی بزرگ برای تجزیه و تحلیل کلاستر گزارش شده است. موج کلاستر روش کلاسترینگ جدیدی است که بر اساس تبدیلات موج کوچک کار میکند. علی رغم آنکه این روش قابلیت تشخیص کلاسترهای شکل های اختیاری را با روشی بهینه دار ، به حجم قابل توجهی از زمان نیاز دارد تا بتواند نتایج را برای دیتاستهای چند بعدی بزرگ جمع آوری نماید.ما در اینجا پیاده سازی موازی الگوریتم کلاستر موجی را بر اساس مدل عبور پیام ، برای یک سیستم چند پردازنده ایی حافظه – توزیع شده پیشنهاد کرده ایم.در متد پیشنهادی نیازمندیهای ارتباطی بین پردازنده ها در حافظه ، به منظور دستیابی به بهره برداری بالا ، در حداقل نگه داشته شده اند. در این پژوهش ما آزمایشاتی را بر روی یک دیتاست متراکم و یک دیتا ست پراکنده انجام داده ایم تا بتوانیم رفتار الگوریتم را به خوبی اندازه گیری کنیم.نتایج بدست آمده از این آزمایشات نشان دادند که این الگوریتم با افزایش تعداد پردازنده ها ، مقیاس و سرعت بالایی را به صورت خطی از خود نشان می دهد.
واژگان کلیدی : آنالیز کلاستر الگوریتم کلاستر موجی ، کلاستر موج موازی
1-مقدمه
کلاسترینگ ، یک تکنیک داده کاوی عمومی است برای بازیابی اطلاعات از طریق گروه بندی و دسته بندی اشیاء مشابه در درون کلاسترها یا کلاسهای گسسته استفاده می شود. با پیشرفت های اخیر در تکنولوژی ذخیره سازی داده ، در دامنه های تجاری و علمی ،رشد منفجر شونده ایی در دیتاست های عظیم یا خیلی بزرگ دیده می شود.از آنجایی که آنالیز کلاستر برای استخراج داده ها ، به یک وظیفه بحرانی و مهم تبدیل شده است ، حجم قابل توجهی از پژوهش ها ، تمرکز خود را بر توسعه و ایجاد متدهای آنالیز کلاسترینگ ترتیبی اختصاص داده اند، که از این پژوهشها می توان به kمفولی ها [11] و Birch [22] ، [4] db scan ، [21] STING و کلاستر موج [17] اشاره کرد.الگوریتم های کلاسترینگ ، در حوزه های مختلفی نظیر قطعه سازی تصاویر ماهواره ایی، کلاسترینگ اسناد غیر نظارتی [20] و کلاسترینگ بیو انفورماتیک، به صورت گسترده ایی بهینه سازی شده اند. علی رغم بهبود های اساسی و مهم بر روی تکنولوژی پردازنده در مواردی نظیر سرعت ، الگوریتم های کلاسترینگ ترتیبی هنوز نمی تواند وظیفه مورد نیاز با حجم قابل قبول زمانی را در دیتاست های خیلی بزرگ تحقق بخشد. در کنار این موضوعحجم منابع حافظه اصلی در دسترسنیز برای نگه داری کلیه داده ها بر روی یک کامپیوتر ساده ، کافی به نظر می رسد.یکی از راه حل های ممکن برای غلبه بر چنین مواردی و بهره برداری دیتاست های عظیم، ایجاد و ساخت الگوریتم های موازی و بهینه سازی آنها است. در سالهای اخیر ، حجم قابل توجهی از پژوهش ها تمرکز خود را بر روی پیاده سازی موازی الگوریتم های کلاسترینگ موازی اختصاص داده اند...