روش خوشه‌بندی (K-Means و C-Means یا C-Centeriod)

  این روش علی‌رغم سادگی آن یک روش پایه برای بسیاری از روش‌های خوشه‌بندی دیگر (مانند خوشه‌بندی فازی) محسوب می‌شود. این روش روشی انحصاری و مسطح محسوب می‌شود.[1] برای این الگوریتم شکلهای مختلفی بیان شده است. ولی همة آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه‌ها سعی در تخمین موارد زیر دارند:

·        بدست آوردن نقاطی به عنوان مراکز خوشه‌ها این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.

·        نسبت دادن هر نمونه داده به یک خوشه که آن داده کمترین فاصله تا مرکز آن خوشه را دارا باشد.

  

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

                                                             (6)

که ║║ معیار فاصلة بین نقاط و cj مرکز خوشة j ام است.

الگوریتم زیر الگوریتم پایه برای این روش محسوب می‌شود:

1. در ابتدا K نقطه به عنوان به نقاط مراکز خوشه‌ها انتخاب می‌شوند.

2. هر نمونه داده به خوشه‌ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست، نسبت داده‌ می‌شود.

3. پس تعلق تمام داده‌ها به یکی از خوشه‌ها برای هر خوشه یک نقطه جدید به عنوان مرکز محاسبه می‌شود. (میانگین نقاط متعلق به هر خوشه)

4. مراحل 2 و 3 تکرار می‌شوند تا زمانی که دیگر هیچ تغییری در مراکز خوشه‌ها حاصل نشود.

مثالی برای روش خوشه‌بندی K-Means:

در شکل زیر نحوة اعمال این الگوریتم خوشه‌بندی روی یک مجموعه داده‌ که شامل دو گروه داده است نشان داده شده است. یک گروه از داده‌ها با ستاره و گروه دیگر با دایره مشخص شده اند(a). در مرحله اول نقطه‌ای به عنوان مرکز خوشه‌ها انتخاب شده اند که با رنگ قرمز نشان‌داده شده اند(b). سپس در مرحله دوم هر یک از نمونه‌ داده‌ها به یکی از این دو خوشه نسبت داده شده است و برای هر دسته جدید مرکزی جدید محاسبه شده سات که در قسمت c نشان داده شده اند. این روال تا رسیدن به نقاطی که دیگر تغییر نمی‌کنند، ادامه پیدا کرده است.

(a)

(b)

(c)

(d)

(e)

(f)

شکل 11: مثالی برای روش خوشه‌بندی K-Means

   مشکلات روش خوشه‌بندی K-Means

علی‌رغم اینکه خاتمه‌پذیری الگوریتم بالا تضمین شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نمی‌باشد. به طور کلی روش ساده بالا دارای مشکلات زیر است.

•  جواب نهایی به انتخاب خوشه‌های اولیه وابستگی دارد.

•  روالی مشخص برای محاسبة اولیة مراکز خوشه‌ها وجود ندارد.

• اگر در تکراری از الگوریتم تعداد داده‌های متعلق به خوشه‌ای صفر شد راهی برای تغییر و بهبود ادامة روش وجود ندارد.

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

  الگوریتم خوشه‌بندی LBG

 همان‌گونه که ذکر شد الگوریتم خوشه‌بندی K-Means به انتخاب اولیة خوشه‌ها بستگی دارد و این باعث می‌شود که نتایج خوشه‌بندی در تکرارهای مختلف از الگوریتم متفاوت شود که این در بسیاری از کاربردها قابل نیست. برای رفع این مشکل الگوریتم خوشه‌بندی LBG پیشنهاد شد که قادر است به مقدار قابل قبولی بر این مشکل غلبه کند.[7]

در این روش ابتدا الگوریتم تمام داده‌ها را به صورت یک خوشه‌ در نظر می‌گیرد و سپس برای این خوشه یک بردار مرکز محاسبه می‌کند.(اجرای الگوریتم K-Means  با تعداد خوشة 1K=). سپس این بردار را به 2 بردار می‌شکند و داده‌ها را با توجه به این دو بردار خوشه‌بندی می‌کند (اجرای الگوریتم K-Means با تعداد خوشة K=2  که مراکز اولیه خوشه‌ها همان دو بردار هستند). در مرحلة بعد این دو نقطه به چهار نقطه شکسته می‌شوند و الگوریتم ادامه پیدا می‌کند تا تعداد خوشة مورد نظر تولید شوند.

الگوریتم زیر را می‌توان برای این روش خوشه‌بندی در نظر گرفت:

1. شروع: مقدار M(تعداد خوشه‌ها) با عدد 1 مقدار دهی اولیه می‌شود. سپس برای تمام داده‌ها بردار مرکز محاسبه می‌شود.

2. شکست: هر یک از M بردار مرکز به 2 بردار جدید شکسته می‌شوند تا 2Mبردار مرکز تولید شود. هر بردار جدید بایستی درون همان خوشه قرار داشته باشد و به اندازة کافی از هم دور باشند.

3. K-Means: با اجرای الگوریتم K-Means با تعداد خوشة 2M و مراکز اولیه خوشه‌های محاسبه شده در مرحلة ii خوشه‌های جدیدی با مراکز جدید تولید  می‌شود.

4. شرط خاتمه: در صورتی که M برابر تعداد خوشة مورد نظر الگوریتم LBG بود الگوریتم خاتمه می‌یابد و در غیر این صورت به مرحلة ii  رفته و الگوریتم تکرار می‌شود.