| عنوان فارسی مقاله: | بهبود دقت و کارایی الگوریتم خوشه بندی K میانگین |
| عنوان انگلیسی مقاله: | Improving the Accuracy and Efficiency of the k-means Clustering Algorithm |
| دانلود مقاله انگلیسی: | برای دانلود رایگان مقاله انگلیسی با فرمت pdf اینجا کلیک نمائید |
| سال انتشار | 2009 |
| تعداد صفحات مقاله انگلیسی | 5 صفحه |
| تعداد صفحات ترجمه مقاله | 12 صفحه |
| مجله | کنگره جهانی مهندسی |
| دانشگاه | هند |
| کلمات کلیدی | تحلیل داده ها، خوشه بندی، الگوریتم میانگین k، الگوریتم میانگین k بهبود یافته |
| نشریه | WCE |
فهرست مطالب:
چکیده
۱ مقدمه
۲ الگوریتم خوشه بندی میانگین K
۳ کار وابسته
۴ شیوه اصلاح شده
۵ پیچیدگی زمانی
۶ نتایج آزمایشی
۷ نتیجه گیری
بخشی از ترجمه:
۱ مقدمه
پیشرفتهای صورت گرفته در روشهای جمع آوری داده های علمی موجب جمع آوری داده های امیدوارکننده ای در رابطه با فیلدهای گوناگون علوم و فناوری در مقیاس وسیع گردیده است. به خاطر توسعه تکنیک های جدید برای تولید و جمع آوری داده ها، نرخ رشد پایگاههای داده علمی چشمگیر شده است. بنابراین، استخراج اطلاعات مفید از آنها با استفاده از تکنیک های تحلیل پایگاه داده متداول غیر ممکن می باشد. روشهای داده کاوی موثر عنصری ضروری برای استخراج اطلاعات ضمنی از پایگاههای داده عظیم به شمار می روند. تحلیل خوشه ای یکی از روشهای اصلی تحلیل داده ها می باشد که در بسیاری از برنامه های کاربردی عملی در نواحی در حال ظهور مثل بیوانفورماتیک کاربرد دارد. خوشه بندی به فرایند تقسیم بندی مجموعه اشیاء در خوشه های مجزا اشاره می کند. این کار به شیوه ای انجام می شود که اشیاء حاضر در یک خوشه شبیه به هم هستند، در حالیکه اشیاء متعلق به خوشه های مختلف نسبت به مشخصه هایشان تفاوت قابل ملاحظه ای باهم دارند. الگوریتم میانگین k ابزاری موثر در تولید خوشه ها برای بسیاری از برنامه های کاربردی عملی به شمار می رود. اما پیچیدگی محاسباتی الگوریتم میانگین k اصلی به ویژه برای مجموعه داده های بزرگ، بسیار بالا می باشد. به علاوه، این الگوریتم باعث شکل گیری تیپ خوشه های گوناگون بسته به انتخاب تصادفی مراکز اولیه می شود. تلاشهای زیادی از سوی محققین برای بهبود عملکرد الگوریتم خوشه بندی میانگین k صورت گرفته است. این مقاله با روشی برای بهبود دقت و کارایی الگوریتم میانگین k سرو کار دارد.
7. نتیجه گیری
از الگوریتم میانگین k عمدتاً برای خوشه بندی مجموعه داده های بزرگ استفاده شده است. اما الگوریتم استاندارد همیشه نتایج مطلوب را تضمین نمی کند زیرا دقت خوشه های نهایی به انتخاب مراکز اولیه بستگی دارد. به علاوه، پیچیدگی محاسباتی الگوریتم استاندارد به خاطر نیاز به تخصیص مجدد نقاط داده ای در طول هر تکرار از حلقه، بالا می باشد. این مقاله یک الگوریتم میانگین k بهبود یافته را معرفی می کند که ترکیبی از روش سیستماتیک برای یافتن مراکز اولیه و یک راه کارآمد برای تخصیص نقاط داده ای به خوشه ها می باشد. این روش از کل فرایند خوشه بندی در زمان بدون قربانی کردن دقت خوشه ها اطمینان حاصل می کند. بهبودهای قبلی الگوریتم میانگین k با دقت و کارایی سازش می کند. یکی از محدودیت های الگوریتم پیشنهاد شده آن است که مقدار k، تعداد خوشه های مطلوب، می بایست به عنوان یک ورودی ، بدون توجه به توزیع نقاط داده ای معلوم گردد. تکامل برخی از روشهای آماری برای محاسبه مقدار k، بسته به توزیع داده ها، برای تحقیق آتی پیشنهاد شده است. روشهای بکاررفته برای اصلاح محاسبه مراکز اولیه ارزش پژوهش را دارند.
بخشی از مقاله انگلیسی:
I. INTRODUCTION
Advances in scientific data collection methods have resultedin the large scale accumulation of promising data pertainingto diverse fields of science and technology. Owing tothe development of novel techniques for generating andcollecting data, the rate of growth of scientific databases hasbecome tremendous. Hence it is practically impossible toextract useful information from them by using conventionaldatabase analysis techniques. Effective mining methods areabsolutely essential to unearth implicit information fromhuge databases.Cluster analysis [6] is one of the major data analysismethods which is widely used for many practical applicationsin emerging areas like Bioinformatics [1, 3]. Clustering isthe process of partitioning a given set of objects into disjointclusters. This is done in such a way that objects in the samecluster are similar while objects belonging to differentclusters differ considerably, with respect to their attributes.The k-means algorithm [6, 7, 8, 10, 11] is effective inproducing clusters for many practical applications. But thecomputational complexity of the original k-means algorithmis very high, especially for large data sets. Moreover, thisalgorithm results in different types of clusters depending onthe random choice of initial centroids. Several attempts weremade by researchers for improving the performance of thek-means clustering algorithm. This paper deals with a method for improving the accuracy and efficiency of the k-meansalgorithm.II. THE K-MEANS CLUSTERING ALGORITHMThis section describes the original k-means clustering algorithm.The idea is to classify a given set of data into knumber of disjoint clusters, where the value of k is fixed inadvance. The algorithm consists of two separate phases: thefirst phase is to define k centroids, one for each cluster. Thenext phase is to take each point belonging to the given dataset and associate it to the nearest centroid. Euclidean distanceis generally considered to determine the distance betweendata points and the centroids. When all the points areincluded in some clusters, the first step is completed and anearly grouping is done. At this point we need to recalculatethe new centroids, as the inclusion of new points may lead toa change in the cluster centroids. Once we find k newcentroids, a new binding is to be created between the samedata points and the nearest new centroid, generating a loop.As a result of this loop, the k centroids may change theirposition in a step by step manner. Eventually, a situation willbe reached where the centroids do not move anymore. Thissignifies the convergence criterion for clustering.Pseudocode for the k-means clustering algorithm is listed asAlgorithm 1 [7].
| عنوان فارسی مقاله: | بهبود دقت و کارایی الگوریتم خوشه بندی K میانگین |
| عنوان انگلیسی مقاله: | Improving the Accuracy and Efficiency of the k-means Clustering Algorithm |