الگوریتم خوشه‌بندی K-Means — همراه با مثال و پیاده سازی در پایتون

خوشه‌بندی K-Means یک الگوریتم یادگیری بدون نظارت «Unsupervised Learning» است که برای حل مسائل خوشه‌بندی «Clustering» در یادگیری ماشین «Machine Learning» یا علوم داده «Data Science» به کار می‌رود. در این مبحث، یاد خواهیم گرفت که الگوریتم خوشه‌بندی K-Means چیست، این الگوریتم چگونه کار می‌کند و همچنین پیاده‌سازی K-Means با استفاده از پایتون را بررسی خواهیم کرد.

الگوریتم K-Means چیست؟

خوشه‌بندی K-Means یک الگوریتم یادگیری بدون نظارت است که مجموعه داده‌های بدون برچسب را به خوشه‌های مختلف تقسیم می‌کند. حرف K نشان‌دهنده تعداد خوشه‌های از پیش تعیین‌شده‌ای است که باید در طول فرآیند ایجاد شوند. به عنوان مثال، اگر K=2 باشد، الگوریتم دو خوشه ایجاد می‌کند؛ اگر K=3 باشد، سه خوشه ایجاد می‌شود.

این الگوریتم به صورت تکراری عمل کرده و مجموعه داده‌های بدون برچسب را به K خوشه‌ی مجزا تقسیم می‌کند، به گونه‌ای که هر داده تنها به یک گروه با ویژگی‌های مشابه تعلق داشته باشد. این الگوریتم به ما اجازه می‌دهد تا داده‌ها را به گروه‌های مختلف خوشه‌بندی کرده و به صورت خودکار دسته‌بندی‌های موجود در مجموعه داده‌های بدون برچسب را بدون نیاز به آموزش کشف کنیم.

K-Means یک الگوریتم مبتنی بر مرکز ثقل است که در آن هر خوشه با یک مرکز ثقل (centroid) مرتبط است. هدف اصلی این الگوریتم کاهش مجموع فواصل بین نقاط داده و مراکز خوشه‌های مربوطه‌شان است.

الگوریتم مجموعه داده‌های بدون برچسب را به عنوان ورودی دریافت کرده، آن را به K خوشه تقسیم می‌کند و این فرآیند را تکرار می‌کند تا زمانی که بهترین خوشه‌ها را پیدا کند. در این الگوریتم، مقدار K باید از قبل تعیین شود.

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

• تعیین بهترین مقدار برای نقاط مرکز (centroids) K از طریق فرآیند تکراری.
• اختصاص هر نقطه داده به نزدیک‌ترین مرکز K. نقاط داده‌ای که به یک مرکز خاص K نزدیک هستند، یک خوشه ایجاد می‌کنند.

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

الگوریتم K-Means چگونه کار می‌کند؟

مراحل کار الگوریتم K-Means به شرح زیر توضیح داده شده است:

• مرحله ۱: تعداد K را برای تعیین تعداد خوشه‌ها انتخاب کنید.
• مرحله ۲: K نقطه یا مرکز ثقل تصادفی انتخاب کنید. (این نقاط می‌توانند از مجموعه داده ورودی باشند).
• مرحله ۳: هر نقطه داده را به نزدیک‌ترین مرکز ثقل اختصاص دهید، که باعث تشکیل خوشه‌های K از پیش تعیین‌شده می‌شود.
• مرحله ۴: واریانس را محاسبه کرده و یک مرکز ثقل جدید برای هر خوشه تعیین کنید.
• مرحله ۵: مرحله ۳ را تکرار کنید، به این معنی که هر نقطه داده را مجدداً به نزدیک‌ترین مرکز ثقل جدید خوشه اختصاص دهید.
• مرحله ۶: اگر تغییری در تخصیص نقاط داده رخ داد، به مرحله ۴ بازگردید؛ در غیر این صورت به مرحله پایانی بروید.
• مرحله ۷: مدل آماده است.

فلوچارت الگوریتم K-Means

به صورت کلی می‌توان فلوچارت الگوریتم K-Means به صورت شکل زیر نشان داد.

مراحل الگوریتم K-Means

مراحل گفته شده را با در نظر گرفتن نمودارهای تصویری توضیح می‌دهیم. فرض کنید دو متغیر M1 و M2 داریم. نمودار پراکندگی محور x-y این دو متغیر به صورت زیر است:

انتخاب تعداد k خوشه

برای شناسایی مجموعه داده و تقسیم آن به خوشه‌های مختلف، تعداد k خوشه را به صورت K=2 انتخاب می‌کنیم. این به این معنی است که در اینجا سعی می‌کنیم این مجموعه داده را به دو خوشه مختلف گروه‌بندی کنیم.

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

اختصاص نقاط داده به نزدیک‌ترین مرکز ثقل

اکنون هر نقطه داده از نمودار پراکندگی را به نزدیک‌ترین نقطه K یا مرکز ثقل اختصاص می‌دهیم. این کار را با استفاده از محاسبات ریاضی انجام می‌دهیم که برای محاسبه فاصله بین دو نقطه آموخته‌ایم. بنابراین، میانه‌ای بین هر دو مرکز ثقل رسم می‌کنیم. تصویر زیر را در نظر بگیرید:

از تصویر بالا مشخص است که نقاط سمت چپ خط به K1 یا مرکز ثقل آبی نزدیک هستند و نقاط سمت راست خط به مرکز ثقل زرد نزدیک می‌باشند. برای درک بهتر نقاط مورد نظر را به رنگ‌های آبی و زرد رنگ‌آمیزی کنیم.

از آنجا که باید نزدیک‌ترین خوشه را پیدا کنیم، فرآیند را با انتخاب یک مرکز جدید تکرار خواهیم کرد. برای انتخاب مراکز جدید، مرکز جرم این مراکز را محاسبه خواهیم کرد و سپس مراکز جدید را به صورت زیر پیدا خواهیم کرد:

سپس، هر نقطه داده را به مرکز جدید اختصاص خواهیم داد. برای این کار، همان فرآیند پیدا کردن خط میانه را دوباره تکرار خواهیم کرد. میانه به صورت تصویر زیر خواهد بود:

از تصویر بالا می‌توان مشاهده کرد که یک نقطه زرد در سمت چپ خط و دو نقطه آبی در سمت راست خط قرار دارند. بنابراین، این سه نقطه به مراکز جدید اختصاص خواهند یافت.

با توجه به اینکه اختصاص مجدد انجام شده است، دوباره به مرحله چهارم خواهیم رفت که یافتن مراکز جدید یا نقاط K است. فرآیند را با محاسبه مرکز جرم مراکز ادامه خواهیم داد، بنابراین مراکز جدید به شکل تصویر زیر خواهند بود:

با توجه به اینکه مراکز جدید را به دست آورده‌ایم، دوباره خط میانه را رسم کرده و نقاط داده را مجدداً اختصاص خواهیم داد. بنابراین، تصویر به صورت زیر خواهد بود:

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

از آنجا که مدل ما آماده است، اکنون می‌توانیم مراکز فرضی را حذف کرده و دو خوشه نهایی به صورت تصویر زیر خواهند بود:

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

عملکرد الگوریتم K-means به شدت به خوشه‌های مؤثری که ایجاد می‌کند بستگی دارد. اما انتخاب تعداد بهینه خوشه‌ها یک کار چالش‌برانگیز است. روش‌های مختلفی برای پیدا کردن تعداد بهینه خوشه‌ها وجود دارد، اما در این مقاله به یکی از مناسب‌ترین روش‌ها برای پیدا کردن تعداد خوشه‌ها یا مقدار K پرداخته می‌شود. روش مورد نظر به روش Elbow (آرنج) است:

روش Elbow یکی از محبوب‌ترین روش‌ها برای پیدا کردن تعداد بهینه خوشه‌ها است. این روش از مفهوم مقدار WCSS استفاده می‌کند. WCSS مخفف «Within Cluster Sum of Squares» است که تغییرات کل درون یک خوشه را تعریف می‌کند. فرمول محاسبه مقدار WCSS (برای ۳ خوشه) به شرح زیر است:

$$WCSS = \sum\limits_{i = 1}^k {\sum\limits_{j = 1}^n {\left( {||x_j^{(i)} – {c_i}|{|^2}} \right)} } $$

که در آن:

• \(k\) تعداد خوشه‌ها است.
• \({x_j^{(i)}}\) نمایانگر نقطه داده \(j\) از خوشه \(i\) است.
• \({{c_i}}\) مرکز خوشه \(i\) است.

در این روش، ابتدا الگوریتم K-means برای مقادیر مختلف K (تعداد خوشه‌ها) اجرا می‌شود و مقدار WCSS برای هر K محاسبه می‌شود. سپس این مقادیر رسم شده و نقطه‌ای که در آن کاهش سرعت تغییرات WCSS مشاهده می‌شود (که به شکل یک “آرنج” روی نمودار ظاهر می‌شود) نشان‌دهنده تعداد بهینه خوشه‌ها است.

از آنجا که نمودار نشان‌دهنده انحنای تیز است که شبیه به آرنج به نظر می‌رسد، به همین دلیل این روش به نام روش آرنج شناخته می‌شود. نمودار مربوط به روش آرنج به صورت زیر خواهد بود:

پیاده سازی الگوریتم K-Means در پایتون

برای پیاده‌سازی الگوریتم K-Means و نمایش نتایج، نیاز به وارد کردن کتابخانه‌های زیر داریم:

وارد کردن کتابخانه‌های مورد نیاز

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

ایجاد دیتاست

مجموعه داده یا یک دیتاست فرضی را با make_blobs ایجاد می‌کنیم و نمودار آن را رسم می‌کنیم.

X,y = make_blobs(n_samples = 500,n_features = 2,centers = 3,random_state = 23)

fig = plt.figure(0)
plt.grid(True)
plt.scatter(X[:,0],X[:,1])
plt.show()

نمودار حاصل از اجرای کد بالا به صورت زیر خواهد بود:

مقداردهی اولیه مراکز centroids تصادفی

کد زیر سه خوشه را برای خوشه بندی K-means مقداردهی اولیه می کند. یک seed تصادفی تنظیم می‌کند و مراکز خوشه را در یک محدوده مشخص ایجاد می کند و یک لیست خالی از نقاط برای هر خوشه ایجاد می‌کند.

k = 3

clusters = {}
np.random.seed(23)

for idx in range(k):
    center = 2*(2*np.random.random((X.shape[1],))-1)
    points = []
    cluster = {
        'center' : center,
        'points' : []
    }
    
    clusters[idx] = cluster
    
clusters

خروجی:

{۰: {'center': array([0.06919154, 1.78785042]), 'points': []},
 ۱: {'center': array([ 1.06183904, -0.87041662]), 'points': []},
 ۲: {'center': array([-1.11581855,  0.74488834]), 'points': []}}

نمودار، یک نمودار پراکنده از نقاط داده (X[:،۰]، X[:،۱]) با خطوط شبکه را نمایش می‌دهد و مراکز اولیه خوشه (ستاره های قرمز) ایجاد شده برای خوشه بندی K-means را مشخص می‌کند.

تعریف فاصله اقلیدسی

def distance(p1,p2):
    return np.sqrt(np.sum((p1-p2)**2))

ایجاد تابع اختصاص و به روز رسانی مرکز خوشه

E-step نقاط داده را به نزدیکترین مرکز خوشه اختصاص می‌دهد و M-step مراکز خوشه را بر اساس میانگین نقاط تخصیص یافته در خوشه بندی K-means به روز می‌کند.

#Implementing E step 
def assign_clusters(X, clusters):
    for idx in range(X.shape[0]):
        dist = []
        
        curr_x = X[idx]
        
        for i in range(k):
            dis = distance(curr_x,clusters[i]['center'])
            dist.append(dis)
        curr_cluster = np.argmin(dist)
        clusters[curr_cluster]['points'].append(curr_x)
    return clusters
        
#Implementing the M-Step
def update_clusters(X, clusters):
    for i in range(k):
        points = np.array(clusters[i]['points'])
        if points.shape[0] > 0:
            new_center = points.mean(axis =0)
            clusters[i]['center'] = new_center
            
            clusters[i]['points'] = []
    return clusters

ایجاد تابع پیش بینی خوشه برای نقاط داده

def pred_cluster(X, clusters):
    pred = []
    for i in range(X.shape[0]):
        dist = []
        for j in range(k):
            dist.append(distance(X[i],clusters[j]['center']))
        pred.append(np.argmin(dist))
    return pred

اختصاص مرکز خوشه، به‌روزرسانی و پیش‌بینی

clusters = assign_clusters(X,clusters)
clusters = update_clusters(X,clusters)
pred = pred_cluster(X,clusters)

رسم نقاط داده با مرکز خوشه پیش بینی شده

plt.scatter(X[:,0],X[:,1],c = pred)
for i in clusters:
    center = clusters[i]['center']
    plt.scatter(center[0],center[1],marker = '^',c = 'red')
plt.show()

خروجی:

نمودار فوق نقاط داده رنگ آمیزی شده توسط خوشه های پیش بینی شده آنها را نشان می‌دهد. نشانگرهای قرمز نشان دهنده مراکز خوشه به روز شده پس از مراحل E-M در الگوریتم خوشه بندی K-means است.

نتیجه گیری

خوشه‌بندی K-means یک الگوریتم یادگیری ماشینی بدون نظارت قدرتمند برای گروه‌بندی مجموعه‌های داده بدون برچسب است. هدف این است که داده ها را به خوشه‌های مختلف تقسیم کند و نقاط داده مشابه را بخشی از همان گروه کند. این الگوریتم مرکزهای خوشه را مقدار دهی اولیه می کند و به طور مکرر نقاط داده را به نزدیکترین مرکز انتساب می‌دهد و مرکزها را بر اساس میانگین نقاط هر خوشه به روز می‌کند