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

۳۳۴۰ بازدید
آخرین به‌روزرسانی: ۱۴ تیر ۱۴۰۲
زمان مطالعه: ۸ دقیقه
پیاده سازی الگوریتم خوشه بندی K-means در پایتون — راهنمای گام به گام

الگوریتم K-means یا همان خوشه بندی K میانگین (K-means Clustering)، یکی از ساده‌ترین و رایج‌ترین الگوریتم‌های نوع بدون نظارت‌ یا همان نظارت نشده و خوشه بندی در یادگیری ماشین به حساب می‌آید. الگوریتم خوشه بندی K-means برای پیدا کردن دسته‌هایی در داده‌ها مورد استفاده قرار می‌گیرد که برچسب مشخصی ندارند. K-means می‌تواند برای تایید فرضیات تجاری درباره اینکه چه نوع دسته‌ها و نظم‌هایی در داده‌ها وجود دارند یا برای شناسایی دسته‌های ناشناخته در مجموعه داده‌های پیچیده به کار گرفته شود. در این مقاله، ابتدا به این سوال پاسخ داده می‌شود که K-means چیست و سپس آموزش پیاده سازی K-means در پایتون به بیان ساده و به صورت گام به گام ارائه شده است.

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

K-Means یکی از پرکاربردترین الگوریتم‌های خوشه‌بندی داده‌ها به شمار می‌رود. در K-means با تکرار اعمالی ثابت و استفاده از توابعی مانند Norm ،Mean و Argmin، می‌توان به ازای هر خوشه، مراکزی را یافت که دقت بالا و لَختی (اینرسی) کمی دارند.

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

مراحل اجرای الگوریتم K-means چیست ؟

به طور کلی، گام‌های اجرای الگوریتم K-means به شرح زیر است:

  1. تعیین تعداد خوشه‌ها (K)
  2. انتخاب K عدد تصادفی از داده‌ها به عنوان مختصات مراکز خوشه‌ها
  3. تخصیص تمام نقاط (داده‌ها) به نزدیک‌ترین مرکز خوشه
  4. انتخاب میانگین وزن‌دار داده‌های هر خوشه به عنوان مرکز آن
  5. تکرار گام‌های ۳ و ۴ تا زمانی که معیار توقف برقرار شود.

معیارهای توقف برای الگوریتم K-means چیست ؟

اساساً می‌توان سه معیار توقف را برای متوقف کردن حلقه تکرار الگوریتم K-means به کار گرفت. این سه معیار در ادامه فهرست شده‌اند:

  1. مرکزهای خوشه‌های ایجاد شده جدید تغییر نکنند.
  2. نقطه‌ها (داده‌ها) در همان خوشه باقی بمانند و تغییر در عضویت خوشه برای داده‌ها ایجاد نشود.
  3. تعداد تکرارها به تعداد تکرار بیشینه (تعیین شده) برسد.

رابطه ریاضی الگوریتم K-means چیست ؟

این الگوریتم، به زبان ریاضی، به شکل زیر در خواهد آمد:

$$ C_j = mean( A_j(t-1)), t \geqslant 1 $$

$$ A_j(t) = \{ X_i \mid X_i \in X, j = \mathop{argmin}_{\textbf{j}} ( norm(X_i - C_j (t))) \} $$

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

پیاده سازی K-means در پایتون

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

فراخوانی کتابخانه‌ها برای پیاده سازی الگوریتم K-means در پایتون

پیاده سازی الگوریتم K-means در پایتون از کتابخانه‌های numpy‌ و Matplotlib استفاده می‌شود، بنابراین باید وارد محیط برنامه‌نویسی شده و این کتابخانه‌ها را فراخوانی کرد:

1import numpy as np
2import matplotlib.pyplot as plt

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

تولید داده‌های مصنوعی برای پیاده سازی الگوریتم K-means در پایتون

پس از فراخوانی کتابخانه‌های مورد نیاز برای پیاده سازی الگوریتم K-means در پایتون ، باید یک مجموعه داده با مرکزهای خوشه تعیین شده (مشخص) تولید شود تا در نهایت بتوان نتایج حاصل شده از اجرای الگوریتم K-means را با مقادیر واقعی مقایسه کرد.

کدهای تولید داده‌های مصنوعی با مرکزهای خوشه مشخص در پایتون به صورت زیر است:

1def CreateDataset(Cs, nD, S):
2    nC = len(Cs)
3    N = nD * nC
4    X = np.zeros((N, 2))
5    for i in range(0, nD):
6        for j in range(0, nC):
7            X[nC*i + j, 0] = Cs[j, 0] + np.random.randn() / S
8            X[nC*i + j, 1] = Cs[j, 1] + np.random.randn() / S
9    return X

در تابع CreateDataset که در کدهای فوق ایجاد شده است، حول هر مرکز ورودی، به تعداد nD داده به صورت تصادفی ایجاد و در خروجی بازگردانده می‌شود.

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

فراخوانی تابع CreateDataset به صورت زیر است:

1# Centers of Synthetic Data
2Cs = np.array([[-0.5, +1.0], [+1.6, -0.1],
3                [-0.9, -1.7], [-2.9, +2.3],
4                [+0.7, +2.2], [-2.2, +0.3]])
5nD = 200 # Count of Data in Each Cluster
6S = 2.5
7
8X = CreateDataset(Cs, nD, S)

در کدهای فوق، ابتدا پارامترهای ورودی تابع CreateDataset شامل nD ،Cs و S تعریف و مقداردهی شده‌اند. سپس، تابع CreateDataset فراخوانی و متغیرهای تعریف شده به عنوان ورودی به این تابع ارجاع داده می‌شوند. ‌پس از اجرای تابع، داده‌های مورد نیاز در آرایه‌ی X ذخیره خواهند شد.

بصری‌سازی داده‌های تولید شده

برای نمایش و بصری‌سازی داده‌های تولید شده می‌توان داده‌ها را به یک صورت نمودار توزیعی (Scatter Plot) رسم کرد:

1plt.style.use('ggplot')
2plt.scatter(X[:, 0], X[:, 1], c = 'k', s = 9, label = 'Data')
3plt.scatter(Cs[:,0], Cs[:, 1], c = 'r', s = 100, label = 'Center', marker = '*')
4plt.title('Scatter Plot of Data')
5plt.xlabel('X1')
6plt.ylabel('X2')
7plt.legend()
8plt.show()

باید توجه داشت که در کدهای فوق، دوبار از دستور plt.scatter استفاده شده است. در اولین فراخوانی plt.scatter، توزیع داده‌های ماتریس X و در فراخوانی دوم، مراکز خوشه‌ها رسم شده‌اند. در این مقاله برای پیاده سازی الگوریتم K-means در پایتون از داده‌های دو بُعدی استفاده شده است. این کار با هدف ساده‌سازی محاسبات و امکان نمایش داده‌ها در نمودار صورت گرفته است. می‌توان با تغییر دادن ابعاد X در تابع CeateDataset، داده‌هایی با ابعاد بالاتر ایجاد کرد. نمودار توزیعی کدهای فوق در خروجی به صورت زیر چاپ می‌شود:

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

تعیین تعداد خوشه‌ها مراکز آن‌‌ها

برای شروع پیاده سازی الگوریتم K-means در پایتون ، باید ابتدا تعداد خوشه‌های مورد نظر را تعیین و سپس مراکز خوشه‌‌ها را به صورت تصادفی مشخص کرد.
1nClusters = 6
2
3Centers = np.random.uniform(-2, +2, (nClusters, 2)) # Initializing Centers Posotions

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

ایجاد تابعی برای تخصیص هر داده به یک خوشه

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

1def GetClusters(Centers, nClusters, X):

ایجاد یک لیست برای ذخیره داده‌های هر خوشه

اکنون باید یک لیست ایجاد شود که در آن به تعداد nClusters لیست خالی وجود داشته باشد تا بعداً هر داده به لیست مربوط به آن خوشه اضافه شود:

1def GetClusters(Centers, nClusters, X):
2    Clusters = []
3    for i in range(0, nClusters):
4        Clusters.append([])

در خروجی کدهای فوق، لیست Clusters، به شکل زیر خواهد بود:

$$ Clusters = [ [\space\space\space], [\space\space\space], \dots, [\space\space\space] ] $$

محاسبه فاصله هر نقطه از مرکز

حال باید به ازای هر داده‌ $$ X_i $$، فاصله را از هر مرکزِ $$ C_j $$ محاسبه کرد. برای انجام این کار، ابتدا حلقه‌ای به ازای تمامی داده‌ها ایجاد و سپس یک آرایه خالی برای افزودن فاصله هر مرکز از $$ X_i $$ تعریف می‌شود.

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

1for xi in X:
2        d = np.zeros(nClusters)
3        for j in range(0, nClusters):
4            cj = Centers[j]
5            dij = xi - cj
6            d[j] = np.linalg.norm(dij)

در کدهای فوق، با کم کردن دو بردار $$ X_i $$ و $$ C_j $$ از یکدیگر، بردار $$ D_(i,j) $$ حاصل می‌شود که مقدار L2-Norm آن، بیان‌گر فاصله اقلیدسی خواهد بود. تابع norm به طور پیش‌فرض، از روش L2 استفاده می‌کند. البته در صورت نیاز، می‌توان از روش‌های دیگر نیز استفاده کرد. حال باید داده $$ X_i $$ را به لیست مربوط به نزدیک‌ترین مرکز خوشه اضافه کرد:

1        a = np.argmin(d) # Arg of Nearest Center
2        Clusters[a].append(xi) # Appending Xi to Nearest Centers List

به این ترتیب، تابع مورد نظر تا به اینجا کامل شده و عملکرد مورد نیاز را انجام می‌دهد.

تبدیل لیست‌های خوشه‌ها به آرایه

بهتر است در انتها، لیست‌های موجود در Clusters به آرایه تبدیل شوند تا استفاده از آن‌ها، راحت‌تر باشد:

1def GetClusters(Centers, nClusters, X):
2    Clusters = []
3    for i in range(0, nClusters):
4        Clusters.append([])
5    for xi in X:
6        d = np.zeros(nClusters)
7        for j in range(0, nClusters):
8            cj = Centers[j]
9            dij = xi - cj
10            d[j] = np.linalg.norm(dij)
11        a = np.argmin(d) # Arg of Nearest Center
12        Clusters[a].append(xi) # Appending Xi to Nearest Centers List
13    for i in range(0, nClusters):
14        Clusters[i] = np.array(Clusters[i])
15    return Clusters

اکنون می‌توان در متن اصلی برنامه، از تابع ایجاد شده استفاده کرد:

1nClusters = 6
2
3Centers = np.random.uniform(-2, +2, (nClusters, 2)) # Initializing Centers Posotions
4Clusters = GetClusters(Centers, nClusters, X)

پیاده سازی گام‌های تکرار شونده ۳ و ۴ الگوریتم K-means در پایتون

تا این مرحله در مقاله «K-means چیست»، گام‌های 1 و 2 الگوریتم K-means کامل و در پایتون پیاده سازی شده‌اند، حال برای پیاده سازی تکرار مراحل 3 و 4، نیاز به ایجاد یک حلقه وجود دارد:

1nIter = 20
2
3for i in range (0, nIter):

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

1def UpdateCenters(Centers, Clusters, nClusters):

اکنون باید به ازای هر خوشه، مرکز مربوطه، در میانگین نقاط مربوط به آن خوشه قرار گیرد:

1def UpdateCenters(Centers, Clusters, nClusters):
2    for i in range(0, nClusters):
3        Centers[i] = np.mean(Clusters[i], axis = 0)

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

در چنین شرایطی، مقدار میانگین به عدد $$ \frac{0}{0} $$ خواهد رسید که باعث اختلال در اجرای برنامه می‌شود. به همین دلیل، باید شرطی تعیین کرد تا عمل به روزرسانی در صورتی انجام شود که آرایه مربوطه خالی نیست:

1def UpdateCenters(Centers, Clusters, nClusters):
2    for i in range(0, nClusters):
3        if np.size(Clusters[i]) != 0: # if Array is not Empty
4            Centers[i] = np.mean(Clusters[i], axis = 0)
5    return Centers

به این ترتیب، تابع مورد نیاز برای به‌روزرسانی مراکز ایجاد شده است. حالا باید حلقه‌ی ایجاد شده را تکمیل کرد:

1nIter = 20
2
3for _ in range (0, nIter):
4    Centers = UpdateCenters(Centers, Clusters, nClusters)
5    Clusters = GetClusters(Centers, nClusters, X)

بنابراین، پیاده سازی الگوریتم K-means در پایتون انجام شده است و الگوریتم K-means به درستی عمل خواهد کرد.

مقایسه نتایج پیاده سازی شده الگوریتم K-means با مراکز خوشه واقعی

پس از اتمام مراحل، می‌توان نمودار مختصات مراکز حاصل از الگوریتم K-Means را با مراکزی که تعیین شده بودند، مقایسه کرد.

1plt.scatter(Cs[:,0], Cs[:,1], label='Target Centers', marker = '*', s = 80, c = 'r')
2plt.scatter(Centers[:,0], Centers[:,1],
3            label='Centers Found by K-Means', marker = 'x', s = 60, c = 'k')
4plt.xlabel('X1')
5plt.ylabel('X2')
6plt.legend()
7plt.show()

پس از اجرای کدهای فوق، تصویر خروجی به صورت زیر خواهد بود:

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

نمایش بصری مراحل الگوریتم K-means

در تصویر متحرک زیر، می‌توان مراحل طی شده تا همگرایی را مشاهده کرد:
مراحل الگوریتم K-means
به این ترتیب،‌ پیاده سازی الگوریتم K-means در پایتون در این مقاله ارائه شد. حال در بخش پایانی مقاله «K-means چیست» به معرفی دوره‌های آموزش K-means و یادگیری ماشین فرادرس پرداخته شده است.

جمع‌بندی

در این مقاله، ابتدا به این سوال پاسخ داده شد که الگوریتم k-means چیست و سپس پیاده سازی الگوریتم K-means در پایتون به صورت گام به گام و تا حد امکان به بیان ساده ارائه شد. در این پیاده سازی ابتدا داده‌های مصنوعی تولید و مراکز خوشه برای آن‌ها تعیین شد. سپس، کدها و توابع لازم برای پیاده سازی K-means ایجاد شدند و این الگوریتم روی داده‌های تولید شده اجرا و نتایج آن با مراکز تعیین شده برای خوشه‌ها مقایسه شد.

بر اساس رای ۱۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
مجله فرادرس
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *