روش خوشه‌بندي K-Means (C-Means يا C-Centeriod)
اين روش علي‌رغم سادگي آن يک روش پايه براي بسياري از روش‌هاي خوشه‌بندي ديگر (مانند خوشه‌بندي فازي) محسوب مي‌شود. اين روش روشي انحصاري و مسطح محسوب مي‌شود.[1] براي اين الگوريتم شکلهاي مختلفي بيان شده است. ولي همة آنها داراي روالي تکراري هستند که براي تعدادي ثابت از خوشه‌ها سعي در تخمين موارد زير دارند:
· بدست آوردن نقاطي به عنوان مراکز خوشه‌ها اين نقاط در واقع همان ميانگين نقاط متعلق به هر خوشه هستند.
· نسبت دادن هر نمونه داده به يک خوشه که آن داده کمترين فاصله تا مرکز آن خوشه را دارا باشد.
در نوع ساده‌اي از اين روش ابتدا به تعداد خوشههاي مورد نياز نقاطي به صورت تصادفي انتخاب مي‌شود. سپس در داده‌ها با توجه با ميزان نزديکي (شباهت) به يکي از اين خوشه‌ها نسبت داده مي‌شوند و بدين ترتيب خوشههاي جديدي حاصل مي‌شود. با تکرار همين روال مي‌توان در هر تکرار با ميانگين‌گيري از داده‌ها مراکز جديدي براي آنها محاسبه کرد و مجدادأ داده‌ها را به خوشههاي جديد نسبت داد. اين روند تا زماني ادامه پيدا مي‌کند که ديگر تغييري در داده‌ها حاصل نشود. تابع زير به عنوان تابع هدف مطرح است.
که ║║ معيار فاصلة بين نقاط و 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 رفته و الگوريتم تکرار مي‌شود.