قبل از ارائه توضیحات در‌‌خصوص الگوریتم K-Means توضیحاتی در خصوص خوشه‌‌بندی و مفهوم خوشه بیان می‌‌کنیم. خوشه‌‌بندی به ما در درک صحیح داده‌‌ها کمک می‌‌کند. فرض کنید یک بانک در نظر دارد که به مشتریان خود کارت اعتباری ارائه دهد. با بررسی جزییات حساب و گردش مالی هر فرد بانک امکان محاسبه اعتبار فرد را دارد، که با توجه به آن، کارت اعتباری را اختصاص دهد. با وجود میلیون‌‌ها نفر مشتری بانک، آیا امکان بررسی تک تک حساب افراد در بانک وجود دارد؟ البته که نه! زیرا این فرآیند دستی است و بسیار زمان‌‌بر خواهد بود. روشی آسان‌‌تر، دسته بندی مشتریان به سه گروه است. گروه اول: درآمد بالا، گروه دوم: درآمد متوسط، گروه سوم: درآمد پایین. با این رویکرد بانک نیازی به بررسی تک تک حساب‌‌ها نخواهد بود. بلکه با دسته بندی میلیون‌‌ها مشتری به سه گروه شرح داده شده، به راحتی استراتژیک‌‌های مختلفی را می‌‌تواند لحاظ کند.

 به فرآیند تقسیم بندی داده‌‌ها اصطلاحا خوشه‌‌بندی و به هر یک از گروه‌‌های فوق الذکر یک خوشه گفته می‌‌شود. خوشه‌‌بندی در حوزه‌‌های مختلفی مورد استفاده قرار می‌‌گیرد. به عنوان مثال: خوشه‌‌بندی مشتریان براساس سابقه خرید، براساس علایق آن‌‌ها، براساس فعالیت مشتریان در وب‌‌سایت‌‌ها و تقسیم‌‌بندی تصاویر، جداسازی صداها و…

خوشه‌‌بندی کا-مینز نوعی از یادگیری بدون نظارت است و زمانی استفاده می‌‌شود که داده‌‌هایی بدون برچسب در اختیار داشته باشیم. هدف این خوشه‌‌بندی، پیداکردن بهترین گروه در داده است و k در آن تعداد خوشه‌‌ها را تعیین می‌‌کند. داده‌‌ها بر اساس میزان شباهت در خوشه‌‌ها قرار می‌‌گیرد. به صورتی که در نهایت داده‌‌ها با بیشترین شباهت در یک گروه قرار می‌‌گیرند و کمترین شباهت را با سایر گروه‌‌ها دارند.

همان‌‌طور که از اسم آن مشخص است k تعداد خوشه‌‌ها و means میانگین‌‌گیری را مشخص می‌‌کند. خوشه‌‌ها دارای یکسری ویژگی هستند. ویژگی اول: تمامی داده‌‌های درون یک خوشه باید بیشترین شباهت را با هم داشته باشند. ویژگی دوم: داده‌‌ها در خوشه‌‌های مختلف باید بیشترین تفاوت را باهم داشته باشند.

مراحل الگوریتم کا-مینز:

  1. انتخاب مقداری برای K  (تعداد خوشه)
  2. انتخاب K رندم داده در بین داده‌‌ها و تعیین آن‌‌ها به عنوان نقاط centroid (نقاط مرکزی)
  3. نسبت دادن داده‌‌ها به نزدیکترین مراکز مشخص شده در مرحله‌‌ی قبل
  4. محاسبه نقاط جدید مرکزی (centroid)
  5. تکرار مرحله‌‌ی 3 و4

شرط توقف الگوریتم:

  1. مراکز در محاسبه جدید تغییر نکند.
  2. داده‌‌ها در همان خوشه قبلی باقی بمانند و تغییر خوشه ندهند.
  3. به حداکثر تعداد تکرار الگوریتم رسیده باشد.

نقاط ضعف الگوریتم کا-مینز:

  1. بهینه سراسری را پیدا نمی‌‌کند.
  2. برای داده‌‌های عددی مناسب است.
  3. نسبت به داده‌‌های نویزی و اصطلاحا outlier ها حساس است.
  4. تعداد خوشه‌‌ها در ابتدای شروع الگوریتم باید مشخص شود.
  5. نسبت به انتخاب خوشه‌‌ی اول حساس است.
  6. خوشه‌‌هایی که شکل توزیع آن‌‌ها غیرمحدب است را نمی‌‌تواند به خوبی تشخیص دهد.

نحوه‌‌ی تعیین تعداد خوشه‌‌ها:

روش استاندارد و مشخصی برای تعیین تعداد خوشه‌‌ها وجود ندارد و بسته به صورت سوال می‌‌تواند متفاوت باشد.

دو روش تجربی برای تعیین تعداد k در ادامه ارائه می‌‌شود:

  • تعداد کلاسترها را از فرمول زیر محاسبه نمایید. ( n تعداد نمونه‌‌ها در دیتاست می‌‌باشد)
  • استفاده از متد Elbow

ارزیابی کیفیت خوشه‌‌ها:

یکی از معیارهای ارزیابی کیفیت خوشه‌‌ها، معیار نیم‌‌رخ (Silhouette coefficient) است. که به منظور تعیین میزان جدایی بین خوشه‌‌ها استفاده می‌‌شود.

مثال:

در مثال زیر از کتابخانه Scikit-Learn استفاده شده است.

مرحله 1: (لود کتابخانه‌‌های ضروری به محیط کاری)

#Import necessary libraries
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
%matplotlib inline

مرحله 2: (تولید داده‌‌های رندم)

# Genrate random data
X = -2 * np.random.rand(200,2)
X1 = 1 + 2 * np.random.rand(100,2)

X[100:200, :] = X1
plt.scatter(X[:,0],X[:,1], s=50,c='b')
plt.show()

مرحله 3: (استفاده از کتابخانه Scikit-Learn برای خوشه‌‌بندی داده‌‌ها)

# Use Scikit-Learn
Kmean = KMeans(n_clusters=2)
Kmean.fit(X)

KMeans(n_clusters=2)

مرحله 4: (مشخص کردن نقاط مرکزی هر خوشه در نمودار)

# Find the Centroid
Kmean.cluster_centers_
plt.scatter(X[:,0],X[:,1],s=50,c='b')
plt.scatter(2.06779818,1.95034122, s=200,c='g',marker='D')
plt.scatter(-0.99932096,-1.0726907, s=200, c='r', marker='D')

مرحله 5: (بررسی دسته‌‌بندی‌‌های صورت گرفته توسط کتابخانه Scikit-Learn)

# Testing the algorithm
Kmean.labels_

array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
       0, 0])

مرحله 6: (تست خوشه‌‌بندی با استفاده از داده‌‌ی تستی)

sample_test = np.array([-1.0,1.0])
second_test = sample_test.reshape(1,-1)
Kmean.predict(second_test)

array([1])