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

دوشنبه ۱۲ خرداد ۱۳۹۹سامان

الگوریتم  K-Means علی‌رغم سادگی آن یک روش پایه برای بسیاری از روش‌ های خوشه‌ بندی دیگر محسوب می‌شود.  در بسیاری از مواقع جزوِ بهترین الگوریتم‌ های خوشه‌ بندی نیز هست. یک روش پایه برای بسیاری از روش‌های خوشه‌ بندی دیگر (مانند خوشه‌ بندی فازی) محسوب می‌شود. یکی از سادە ترین و مشهورترین الگوریتم های خوشە بندی داده کاوی است و یک الگوریتم خوشە بندی افرازی است.

روش خوشه بندی K-Means از الگوریتم های یادگیری بدون نظارت (Unsupervised Learning) است.  در این روش هر خوشه متناظر با یک مرکز است و هر داده به خوشەای با نزدیکترین مرکز نسبت داده میشود. تعداد خوشه ها (K) باید از قبل تعیین شده باشد. در الگوریتم خوشه بندی K-Means  ابتدا k عضو که k تعداد خوشه‌ها است) بصورت تصادفی از میان n عضو به عنوان مراکز خوشه‌ها انتخاب می‌شود. سپس n-k عضو باقیمانده به نزدیک‌ترین خوشه تخصیص می‌یابند. بعد از تخصیص همه اعضا مراکز خوشه مجدداً محاسبه می‌شوند و با توجه به مراکز جدید به خوشه‌ها تخصیص می‌یابند و این کار تا زمانی که مراکز خوشه‌ها ثابت بماند ادامه می‌یابد.

برخی از ویژگی های مهم خوشه بندی K-Means  : 

•    عملکرد الگوریتم وابسته به مراکز اولیه است

•    اغلب در بهینەهای محلی خاتمه پیدا میکند

•    خوشەها به شکلهای محدب هستند

•    الگوریتمی موثر برای دادەهایی با حجم زیاد است(دلیل این ویژگی این است که پیچیدگی زمانی این الگوریتم O(nmkt) است که( n تعداد نمونه ها، m تعداد ویژگی ها، k تعداد خوشه ها و t  تعداد تکرار است) و تابعی خطی از حجم نمونه میباشد.

شبه کد از الگوریتم K-means :

برای روشن شدن موضوع به مثال زیر توجه کنید فرض کنید سن 9 نفر به صورت مجموعهی زیر جمع آوری شده است: {2, 4, 10, 12, 3, 20, 30, 11, 25}

میخواهیم با استفاده از روش  k-میانگین، دادههای به دست آمده را به دو خوشه تقسیم کنیم

گام 1 در این گام ابتدا باید دو عدد تصادفی به عنوان مراکز خوشهها تولید کنیم. فرض کنید اعداد 3 و 4 مراکز اولیه خوشه ها باشند .حال هریک از دادهها را با توجه به فاصله ی هریک از آنها از این مراکز، به یکی از خوشه ها نسبت میدهیم.به عنوان مثال عدد 2 به مرکز 3 و عدد 10 به مرکز4 نزدیکتر است.

بنابراین با ادامەی روند بالا، دو خوشەی زیر به دست میآیند  𝐶1 = {2, 3}                                                 𝐶2 = {4, 10, 12, 20, 30, 11, 25}

گام ٢ (گام تکرار) در این گام مراکز جدید هر خوشه را محاسبه کرده و با توجه به مراکز جدید، دوباره عمل واگذاری دادهها را انجام میدهیم. که مراکز جدید 2.5 و 16خواهند بود.

مشاهده میشود عدد 4 که در مرحله قبل به خوشه دوم نسبت داده شد در این مرحله به مرکز خوشه اول نزدیکتر است. در نتیجه باید عدد 4 را در خوشه اول قرار دهیم. پس خوشه های جدید به شکل زیر خواهند بود: 𝐶1 = {2, 3, 4} 𝐶2 = {10, 12, 20, 30, 11, 25}

• روند بالا را تا زمانی ادامه میدهیم که شرط توقف برقرار شود

• مراحل بعدی به صورت زیر خواهند بود.

𝜇1 = 3 𝜇2 = 18 → 𝐶1 = {2, 3, 4, 10 } 𝐶2 = {12, 20, 30, 11, 25}

مرحله بعد به صورت زیر خواهد بود

و مرحله نهایی به صورت زیر است که در ان مراکز ثابت شده است و خوشه ها تغییر نمیکنند.