دانلود مقاله خوشه بندی K میانگین داده های بزرگ بهینه شده با استفاده از MapReduce
چکیده
تحلیل خوشه بندی یکی از رایج ترین الگوریتم های پردازش داده استفاده شده می باشد. بیش از نیم قرن، K میانگین به دلیل سادگی رایج ترین الگوریتم خوشه بندی باقی مانده است. اخیرا، با افزایش حجم داده ها، برخی محققان به MapReduce برای دستیابی به عملکرد بالا گرایش پیدا کرده اند. اما، MapReduce برای الگوریتم های تکراری مربوط به زمان های تکراری بازشروع کارها، خوانش داده های بزرگ و برهم زدن آن ها مناسب نیست. در این مقاله، ما مشکلات پردازش داده های مقیاس بزرگ را با استفاده از الگوریتم خوشه بندی Kمیانگین حل می کنیم و یک مدل پردازش جدید را در MapReduce برای حذف وابستگی تکراری و به دست آوردن عملکرد بالا ارائه می کنیم. ما ایده های خودمان را تحلیل و پیاده سازی می کنیم. آزمایشات گسترده در خوشه ما نشان می دهند که روش های پیشنهادی ما موثر، پویا و مقیاس پذیر هستند.
1- مقدمه
خوشه بندی داده ها یک مساله بنیادی در بسیاری از زمینه های علوم کامپیوتر و زمینه های مربوطه مانند یادگیری ماشین، داده کاوی، تشخیص الگو، و غیره می باشد. ضمنا، بسیاری از الگوریتم های پیچیده نیز از خوشه بندی برای انجام پیش پردازش مانند تقسیم بندی داده، ایجاد شاخصو غیره استفاده می کنند.
در سال های اخیر، تحلیل خوشه در معرض توسعه شدیدی بوده است. چندین نوع از خوشه بندی {1،2}، خوشه-بندی سلسله مراتبی، خوشه بندی مبتنی بر چگالی، خوشه بندی مبتنی بر شبکه، خوشه بندی مبتنی بر مدل و خوشه بندی تقسیمی وجود دارند. هر نوع خوشه بندی روش های بهینه سازی و سبک مخصوص به خودش را دارد. در این مقاله، ما بطور خاص بهینه سازی مفید الگوریتم خوشه بندی تقسیمی، Kمیانگین، را برای دستیابی به عملکرد خوشه بندی بالا مطالعه می کنیم.
تا آنجا که می دانیم، حل دقیق مساله خوشه بندی حتی تنها با دو خوشه بندی NP سخت است {3}. با توجه به ازدیاد داده های بزرگ و محدودیت یک ماشین تک، یک حل طبیعی در نظر گرفتن توازی سازی در یک محیط محاسباتی پراکنده می باشد. MapReduce{4} یک چارچوب برنامه نویسی برای پردازش مجموعه داده های بزرگ با استفاده از توازی سازی در میان یک خوشه از گره های محاسباتی می باشد. MapReduce محبوبیت خودش را به دلیل سادگی، انعطاف پذیری، تحمل پذیری خطا، و مقیاس پذیری به دست آورده است. قابل پیش بینی است که برخی محققان از MapReduce برای خوشه بندی داده های بزرگ استفاده می کنند.
در {7}، ویژانگ ژائو و همکارانش خوشه بندی Kمیانگین موازی را با استفاده از MapReduce ارائه کردند و یک توصیف دقیق برای این الگوریتم را منتشر کردند، و آلینا این و همکاران {8} اولین تحلیل را ارائه می دهند که چندین الگوریتم خوشه بندی تقسیمی را در MapReduce نشان می دهد. اما، تمام مسائل پردازش داده بزرگ نمی توانند با توازی سازی موثر باشند؛ یک تحقیق نشان می دهد که الگوریتم خوشه بندی تقسیمی به طور تکرارهای زیادی بطور نمایی احتیاج دارد {9}. ضمنا، باور کردن زمان ایجاد نمایی کار و زمان برهم زدن داده های بزرگ مخصوصا هنگامی که اندازه داده عظیم است مشکل می باشد، بنابراین تنها توازی سازی کافی نیست، و تنها با حذف وابستگی الگوریتم های خوشه بندی تقسیمی به تکرار می توانیم عملکرد بالا را به دست آوریم.
5- نتیجه گیری
در این مقاله، ما نشان دادیم که تکرار الگوریتم K میانگین فاکتور مهمی است که بر عملکرد خوشه بندی تاثیر گذاشت و یک مدل خوشه بندی موازی موثر جدید را ارائه کردیم. نتایج تجربی در مجموعه داده های دنیای واقعی بزرگ و مجموعه داده ترکیبی (مصنوعی) نشان می دهند که الگوریتم بهینه شده ما موثر است و بهتر از الگوریتم-های K میانگین، Kمیانگین موازی و Kmeans++ مستقل عمل می کند. اعتبارسنجی خوشه بندی نشان می دهد که کیفیت روش های خوشه بندی ما نیز به همان کیفیت Kمیانگین می باشد.
Abstract
Clustering analysis is one of the most commonly used data processing algorithms. Over half a century, K-means remains the most popular clustering algorithm because of its simplicity. Recently, as data volume continues to rise, some researchers turn to MapReduce to get high performance. However, MapReduce is unsuitable for iterated algorithms owing to repeated times of restarting jobs, big data reading and shuffling. In this paper, we address the problems of processing large-scale data using K-means clustering algorithm and propose a novel processing model in MapReduce to eliminate the iteration dependence and obtain high performance. We analyze and implement our idea. Extensive experiments on our cluster demonstrate that our proposed methods are efficient, robust and scalable.
1 Introduction
Clustering data is a fundamental problem in a variety of areas of computer science and related fields, such as machine learning, data mining, pattern recognition, etc. Meanwhile, many complex algorithms also use clustering to do preprocess such as data partitioning, index creating, etc.
In recent years, cluster analysis has undergone vigorous development. There are several types of clustering [1,2], hierarchical clustering, density-based clustering, gridbased clustering, model-based clustering and partitional clustering. Each clustering type has its own style and optimization methods. In this paper, we major in the efficiency optimization of partitional clustering algorithm, K-means, to get high clustering performance.
As we know, solving clustering problem exactly is NP-hard, even with just two clusters [3]. Regarding the expansion of the data size and the limitation of a single machine, a natural solution is to consider parallelism in a distributed computational environment. MapReduce [4] is a programming framework for processing large-scale datasets by exploiting the parallelism among a cluster of computing nodes. MapReduce gains popularity for its simplicity, flexibility, fault tolerance and scalability soon after its birth. It is appreciable that some researchers use MapReduce for big data clustering [5,6].
In [7], Weizhong Zhao and his colleagues proposed parallel Kmeans clustering using MapReduce and gave a detailed description for the algorithm, and Alina Ene et al. [8] give the first analysis that shows several partitional clustering algorithms in MapReduce. However, not all big data processing problems can be efficient by parallelism; a research shows that partitional clustering algorithm requires exponentially many iterations [9]. Meanwhile, job exponential creation time and time of big data shuffling are hard to swallow especially when data size is huge, so just parallelism is not enough, only by eliminating the partitional clustering algorithms dependence on the iteration can we implement high performance.
5 Conclusion
In this paper, we presented that the iteration of K-means algorithm was the important factor which affected the performance of clustering, and proposed a novel efficient parallel clustering model. Experimental results on large real-world datasets and synthetic dataset demonstrate that our optimized algorithm is efficient and performs better compared with parallel K-means, Kmeans|| and stand-alone Kmeans++ algorithms. Clustering validation shows that the quality of our clustering methods are as well as K-means.
(جهت بزرگ نمایی روی عکس کلیک نمایید)
چکیده
1- مقدمه
2- کار مرتبط
3- بهره برداری از Kمیانگین با استفاده از MapReduce
1-3 نمونه برداری احتمالی
3-2 خوشه بندی و ادغام نمونه
3-2-1 خوشه بندی ادغامی مبتنی بر وزن (WMC)
3-2-2 خوشه بندی ادغامی مبتنی بر توزیع (DMC)
4- آزمایشات و نتایج
4-1 مجموعه داده ها
4-2 اصول پایه
4-3 ارزیابی عملکرد
4-4 اعتبارسنجی خوشه بندی
5- نتیجه گیری
منابع
Abstract
1 Introduction
2 Related work
3 Handing K-means using MapReduce
3.1 Probability sampling
3.2 Sample clustering and merging
3.2.1 Weight-based merge clustering (WMC)
3.2.2 Distribution-based merge clustering (DMC)
4 Experiments and results
4.1 Data sets
4.2 Baselines
4.3 Performance evaluation
4.4 Clustering validation
5 Conclusion
References
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه