خوشه بندی با الگوریتم k-means

الگوریتم k-means یکی از الگوریتمهای خوشه بندی به صورت غیر نظارت شده و بدون استفاده از برچسب، است که برای تولید کدبوک مورد استفاده قرار می گیرد که در نوع خود دارای معایب و محاسنی است.

k-means یک الگوریتم تکرار شونده است: از یک نقطه ای شروع میشود-یک بدنه تکرارشونده دارد – و با مشخص نمودن شرط توقف به پایان می رسد.

ساختار الگوریتم k-means :

1. Input: این مرحله شامل دوقسم است :

- مشخص نمودن داده هایی که قرار است روی آن خوشه بندی انجام شود مانند تصویر

- مشخص نمودن تعداد خوشه ها

2. Body : بدنه تکرار

3. Output : بعد ازمشخص کردن تعداد خوشه در ابتدای کار،به همان تعداد ،کلاستر یا خوشه داریم بعبارتی هر پیکسل یا object به یکی از کلاسترها تعلق پیدا می کند.

مرحله اول:

همانطور که گفته شد برای مقدار دهی اولیه، مفهومی با عنوان مرکز خوشه داریم-جهت تشکیل خوشه،یک مرکز یا نماینده برای هریک از خوشه ها باید در نظر گرفته شود که تعیین مرکز خوشه این الگوریتم بصورت تصادفی انتخاب می شود.

میتوان گفت که مرحله دوم یعنی بدنه تکرار در دو گام انجام می شود:

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

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

گام اول: محاسبه فاصله هرobject (مثلا پیکسل) با مراکز اولیه . هر پیکسل به خوشه ای تعلق میگیرد که کمترین فاصله را با مرکز تعیین شده داشته باشد.

گام دوم: آپدیت کردن خوشه ها.

از آنجایی که ممکن است پیکسل ها جابه جا شوند یا تعداد پیکسل های موجود در خوشه های فعلی تغییر کند،باید مراکز خوشه ها آپدیت شوند که با تغییر مراکز، اعضای خوشه ها نیز تغییر می کند.

در الگوریتم k-means برای آپدیت کردن مرکزخوشه،باید میانگین نمونه های هر خوشه را محاسبه کرد،مقدار بدست آمده بعنوان مرکزجدید خوشه مشخص می شود و لذا باید فاصله اقلیدسی مابین هر نمونه-پیکسل با مرکز جدید محاسبه شود.در این حین ،ممکن است با تغییر مراکز،اعضای هر خوشه نیز تغییر کند

مرحله سوم : شرط توقف

مرحله تکرار تا زمانی انجام می شود که مراکز خوشه ها تغییر نکنند یا اعضا،جا به جا نشوند.

K-means Clustering Method:

If k is given, the K-means algorithm can be executed in the following steps:

Partition of objects into k non-empty subsets
Identifying the cluster centroids (mean point) of the current partition.
Assigning each point to a specific cluster
Compute the distances from each point and allot points to the cluster where the distance from the centroid is minimum.
After re-allotting the points, find the centroid of the new cluster formed.

The step by step process: