الگوریتم Kmeans

الگوریتم های کلاسترینگ

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

کیفیت خوشه ها بر اساس تمایز بین گروه ها و همسان بودن درونی گروه ها تعیین می شود. در دامنه ای از تصاویر این توصیف کلی  به فاصله پیکسل ها در فضای رنگی تفسیر می شود پیکسل هایی که در کنار یکدیگر در یک کلاستر می باشند.

Kmeans

یک الگوریتم تکرار شونده است که تعداد کلاستر ها را قبل از اجرا تعیین می کند. در ابتدا مرکز حجم K به وسیله قوانینی تعیین می شود.(در ابتدا به صورت تصادفی با استفاده از نقاط داده ) و آنها وزن مرکز کلاستر را تعیین می کنند   

برای هر نقطه داده یک مرکز حجم محاسبه می شود. در نتیجه کلاستری هایی از نقاط تشکیل می شود و در مرحله بعد تمام نقاط به کلاستر ها می پیوندند این روند ادامه پیدا می کند تا شرط پایان برسد.

در این روش ، در ابتدا تعداد خوشه ها مشخص می شود (K) و برای هرخوشه ، یک نمونه داده از بین داده های موجود ، بعنوان هسته خوشه (مرکز خوشه) در نظر گرفته می شود.

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

Algorithm 1 Basic K-means algorithm 

1- انتخاب  K نقطه به عنوان مرکز حجم های اولیه به صورت تصادفی

   تکرار

2- اضافه کردن نقاط به نزدیک ترین مرکز حجم از کلاستر های K 

3- محاسبه مجدد حجم هر کلاستر

 پایان    زمانی که شرط پایان برسد و دیگر تغییری در مراکز حجم ها به وجود نیاید

 برای محاسبه فاصله مرکز حجم c  تا نقطه x از رابطه زیر استفاده می کنیم

ِ

 -شرایط پایان الگوریتم

دستیابی به حداکثر تعداد تکرار ها

مرکز حجم ها کمینه شود(Local or Global)- تغییر زیادی در محل حجم ها به وجود نیاید.

 

c' مرکز حجم به روز شده c   و d  مقدار جابه جایی که کمتر یا مساوی ازr  حداکثر جابه جایی است

در کلاستر بندی تصاویر شرط خاتمه دوم  استفاده می شود

پیچیدگی K means  از نوع  NP-Hard می باشد

 INTRODUCTION

Clustering is an important technique with applications in many fields such as computer vision and genome analysis. The goal of clustering is to group a number of input data points into several sets, so that data points within one set share similar characteristics. The k-means algorithm , also

known as Lloyd’s algorithm, is a well known clustering method and widely used in various applications. The k-means algorithm assigns each data point to a closest cluster. For a data point, its distance to a cluster is defined as its distance to the centroid of the cluster, where the centroid of a cluster is defined as the mean position of all the data points contained in the cluster. kmeans algorithm uses an iterative approach. Initially, the positions of k clusters’ centroids are randomly chosen. In a standard k-means iteration, each data point is labeled to the nearest cluster. After all the data points labeled, the centroid of each cluster is then be updated according to its data points. The labeling step and updating step are iterated until the labels do not change any more. Improving the performance of the k-means algorithm has attracted a lot of research attentions. Among the large number of proposed methods, an important approaches is to use triangle inequalities to eliminate unnecessary distance calculations when searching for the nearest centroid. Algorithms based on this idea have been studied by various researchers. Considerable speedups were reported over the standard k-means algorithm.