در آموزش‌های پیشین مجله فرادس، با پیاده سازی الگوریتم خوشه بندی K-means در پایتون آشنا شدیم. در این آموزش، روش گام به گام پیاده‌سازی نوع خاصی از این الگوریتم خوشه‌بندی، یعنی پیاده سازی الگوریتم K-means++ در پایتون را بیان می‌کنیم.
الگوریتم K-means++
همان‌طور که می‌دانیم، در مسئله K-means تابع هزینه به شکل زیر تعریف می‌شود:
$$ large J=sum_{i=1}^{k} sum_{x in S_{i}}left|c_{i}-xright|^{2} $$
به عبارتی این تابع حاصل جمع فاصله اقلیدسی هر داده از مرکز خوشه مربوطه را نشان می‌دهد که به آن Within Cluster Sum of Squares گفته می‌شود.
بهینه‌سازی موقعیت خوشه‌ها برای دست یافتن به کمترین مقدار تابع هزینه، یک مسئله NP-Hard است و به‌لحاظ محاسباتی هزینه‌بر است. به این دلیل از الگوریتم‌هایی برای یافتن بهینه‌های محلی (Local Optimum) استفاده می‌شود. الگورتم لوید (Lloyd Algorithm) که در آموزش‌های قبلی پیاده‌سازی شد نیز مثالی از این روش‌ها است.
همان‌طور که گفته شد، این الگوریتم‌ها اغلب به‌جای یافتن بهینه سراسری (Global Minimum)، بهینه محلی را می‌یابند. به همین دلیل، نتایج حاصل نیز به شرایط شروع (Initialization) بسیار وابسته هستند.
برای حل این مشکل، راه‌حل‌هایی ارائه شده‌اند که یکی از آن‌ها، استفاده از روش K-means++ است.
در این روش، اولین مرکز خوشه به صورت تصادفی از بین داده‌ها انتخاب می‌شود. سایر مراکز نیز به‌صورت تصادفی از بین داده‌ها انتخاب می‌شوند، با این تفاوت که برای داده‌هایی با فاصله بیشتر از مراکز قبلی، احتمال انتخاب بیشتری داده می‌شود. به این ترتیب، احتمال انتخاب مراکز خوشه نزدیک به هم کاهش می‌یابد.
این الگوریتم را می‌توان در مراحل زیر توصیف کرد:
۱. مرکز خوشه اول ($$C_1$$) به‌صورت تصادفی از بین داده‌ها انتخاب می‌شود.
۲. مراحل زیر به تعداد $$k-1$$ بار تکرار می‌شود:
a. فاصله همه داده‌ها از تمامی مراکز خوشه محاسبه و کمترین آن به‌صورت زیر ذخیره می‌شود:
$$ large D_{j}=min _{i in{1,2 ldots k}}left|c_{i}-x_{j}right|^{2} $$
b. احتمال انتخاب متناظر برای هر داده به شکل زیر تعریف می‌شود:
$$ large P_{j}=frac{D_{j}^{2}}{sum_{k=1}^{n} D_{k}^{2}} $$
c. یک داده با توجه به احتمال‌های محاسبه شده، انتخاب می‌شود.
۴. مراکز خوشه به نقاط شروع انتخاب می‌شوند.
۵. لگوریتم Lloyd اجرا می‌شود.
به این ترتیب، مراحل کار الگوریتم کامل بیان می‌شود.
برای یادگیری برنامه‌نویسی با زبان پایتون، پیشنهاد می‌کنیم به مجموعه آموزش‌های مقدماتی تا پیشرفته پایتون تم آف مراجعه کنید که لینک آن در ادامه آورده شده است.
بررسی وابستگی الگوریتم Lloyd به شرایط اولیه
حال وارد محیط برنامه‌نویسی می‌شویم و الگوریتم نوشته‌شده در مطلب قبلی با عنوان «پیاده سازی الگوریتم خوشه بندی K-means در پایتون — راهنمای گام به گام» را که لینک آن را در ابتدای متن آوردیم، به شکل زیر بازنویسی می‌کنیم:
import numpy as np
import matplotlib.pyplot as plt
def CreateDataset(Cs:np.ndarray, nD:int, S:float):
nC = Cs.shape[0]
N = nD * nC
X = np.zeros((N, 2))
for i in range(nC):
for j in range(nD):
X[nC*j + i, 0] = Cs[i, 0] + np.random.randn() / S
X[nC*j + i, 1] = Cs[i, 1] + np.random.randn() / S
return X
def GetClusters(Centers:np.ndarray, X:np.ndarray):
nClusters = Centers.shape[0]
Clusters = []
for i in range(nClusters):
Clusters.append([])
for xj in X:
d = np.zeros(nClusters)
for i in range(nClusters):
d[i] = np.linalg.norm(xj - Centers[i])
a = np.argmin(d)
Clusters[a].append(xj)
for i in range(nClusters):
Clusters[i] = np.array(Clusters[i])
return Clusters
def UpdateCenters(Centers:np.ndarray, Clusters:list):
nClusters = Centers.shape[0]
for i in range(nClusters):
if np.size(Clusters[i]) != 0:
Centers[i] = np.mean(Clusters[i], axis = 0)
return Centersابتدا داده‌ها را ایجاد و نمایش می‌دهیم:
np.random.seed(0)
plt.style.use('ggplot')
Cs = np.array([[-0.5, +1.0], [+1.6, -0.1],
[-0.9, -1.7], [-2.9, +2.3],
[+0.7, +2.2], [-2.2, +0.3]])
nD = 200
S = 2.5
X = CreateDataset(Cs, nD, S)
plt.scatter(X[:, 0], X[:, 1], c='k', s=9, label='Data')
plt.scatter(Cs[:,0], Cs[:, 1], c='r', s=100, marker = '*', label='Center')
plt.title('Scatter Plot of Data')
plt.xlabel('X1')
plt.ylabel('X2')
plt.legend()
plt.show()که شکل زیر خواهیم داشت.
حال تابع هزینه را در قالب یک تابع تعریف می‌کنیم. در ورودی این تابع داده‌ها و مراکز خوشه‌ها را دریافت و در خروجی Within Cluster Sum of Squares را برمی‌گردانیم:
def Cost(Centers:np.ndarray, X:np.ndarray):
WCSS = 0
for i in Centers:
d = []
for j in X:
d.append(np.linalg.norm(i - j, ord=2)**2)
WCSS += min(d)
return WCSSحال برنامه را ۱۰۰ بار با شرایط شروع متفاوت اجرا می‌کنیم و مقدار تابع هزینه را ذخیره می‌کنیم:
nRun = 100
nClusters = 5
nIter = 10
Costs = np.zeros(nRun)
for i in range(nRun):
Centers = np.random.uniform(-2, +2, (nClusters, 2))
Clusters = GetClusters(Centers, X)
for _ in range (nIter):
Centers = UpdateCenters(Centers, Clusters)
Clusters = GetClusters(Centers, X)
Costs[i] = Cost(Centers, X)اکنون یک نمودار هیستوگرام (Histogram) برای مقدار تابع هزینه رسم می‌کنیم:
plt.hist(Costs, bins=11, color='crimson', alpha=0.5)
plt.title('K-Means Algorithm Final Cost Function Value With Different Initilizations')
plt.xlabel('Cost')
plt.ylabel('Frequency')
plt.show()توجه داشته باشید که کم بودن تعداد bins توزیع را با جزئیات مناسب نشان نمی‌دهد و زیاد بودن آن باعث ایجاد ناپیوستگی‌هایی در نمودار می‌شود و باز هم مطلوب نیست. به همین دلیل، باید تعداد آن با توجه به اندازه داده و در بازه مطلوب قرار گرفته باشد.
پس از اجرای کد فوق نمودار زیر حاصل خواهد شد.
به این ترتیب، مشاهده می‌کنیم که حدود ۷۰ بار اجرا، به هزینه‌ای کمتر از ۰٫۰۲ ختم شده است. در مقابل، برای برخی اجراها، تابع هزینه به بیشتر ۰٫۱۴ رسیده است که ۳۵ برابر کمترین مقدار است. به این ترتیب، به‌سادگی وابستگی الگوریتم Lloyd به شرایط اولیه مشاهده می‌شود.
پیاده سازی الگوریتم K-means++ در پایتون
برای پیاده‌سازی الگوریتم K-means++ در پایتون یک تابع ایجاد می‌کنیم که در ورودی تعداد مرکز و مجموعه داده را دریافت می‌کند:
def KMeansPP(nClusters:int, X:np.ndarray):حال تعداد داده را استخراج و سپس ماتریسی خالی برای ذخیره مراکز دسته انتخاب شده ایجاد می‌کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))حال اولین مرکز دسته را به‌صورت تصادفی از مجموعه داده انتخاب می‌کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]حال یک حلقه برای $$k-1$$ بار تکرار کد می‌نویسیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):حال باید ماتریس فاصله هر داده از نزدیک‌ترین مرکز را محاسبه و ذخیره کنیم، برای این کار، ابتدا ماتریسی خالی برای آن ایجاد می‌کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)حال یه حلقه ایجاد می‌کنیم تا برای هر داده فاصله را محاسبه کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):در این مرحله، یک لیست خالی ایجاد می‌کنیم تا فاصله داده از هر مرکز خوشه را به آن اضافه کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):
d = []حال می‌توانیم یک حلقه برای تمامی مراکز خوشه ایجاد و فاصله را به لیست ایجادشده اضافه کنیم. توجه داشته باشید که با هر بار اجرای حلقه بیرونی، تعداد مراکز خوشه افزایش می‌یابد؛ به این دلیل، باید تعداد مراکز از متغیر $$i+1$$ تبعیت کند:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):
d = []
for k in range(i+1):
d.append(np.linalg.norm(X[j] - Centers[k], ord=2))حال باید کمترین فاصله مشاهده شده را به آرایه D اضافه کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):
d = []
for k in range(i+1):
d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
D[j] = min(d)به این ترتیب، کمترین فاصله هر داده از مراکز محاسبه می‌شود. با توجه به فرمول، باید از توان دوم فاصله‌ها استفاده کنیم؛ بنابراین، به‌شکل زیر توان دوم ماتریس D را محاسبه می‌کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):
d = []
for k in range(i+1):
d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
D[j] = min(d)
D2 = np.power(D, 2)حال مجموع مقادیر آرایه D2 را محاسبه کرده و در نهایت احتمال متناظر با هر داده را می‌یابیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):
d = []
for k in range(i+1):
d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
D[j] = min(d)
D2 = np.power(D, 2)
SD2 = np.sum(D2)
P = D2 / SD2به این ترتیب، احتمال انتخاب هر داده به‌عنوان مرکز بعدی محاسبه شد. حال باید با استفاده از Random Choice یک داده را انتخاب کنیم:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):
d = []
for k in range(i+1):
d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
D[j] = min(d)
D2 = np.power(D, 2)
SD2 = np.sum(D2)
P = D2 / SD2
Index = np.random.choice(nD, size=1, p=P)[0]
Centers[i+1] = X[Index]به این ترتیب، داده مورد نظر با توجه به احتمال‌های محاسبه‌شده، انتخاب می‌شود. توجه داشته باشید که تابع np.random.choice در خروجی یک آرایه برمی‌گرداند که با توجه به اینکه تنها یک عدد در آن وجود دارد، تنها عضو اول آن را انتخاب می‌کنیم.
در نهایت، نیز مراکز خوشه‌ها را در خروجی برمی‌گردانیم و تابع نهایی شکل زیر را به خود می‌گیرد:
def KMeansPP(nClusters:int, X:np.ndarray):
nD = X.shape[0]
Centers = np.zeros((nClusters, 2))
Centers[0] = X[np.random.randint(nD)]
for i in range(nClusters - 1):
D = np.zeros(nD)
for j in range(nD):
d = []
for k in range(i+1):
d.append(np.linalg.norm(X[j] - Centers[k], ord=2))
D[j] = min(d)
D2 = np.power(D, 2)
SD2 = np.sum(D2)
P = D2 / SD2
Index = np.random.choice(nD, size=1, p=P)[0]
Centers[i+1] = X[Index]
return Centersحال برای استفاده از این تابع، کد قبلی را به شکل زیر تغییر می‌دهیم:
nRun = 100
nClusters = 5
nIter = 10
Costs = np.zeros(nRun)
for i in range(nRun):
Centers = KMeansPP(nClusters, X)
Clusters = GetClusters(Centers, X)
for _ in range (nIter):
Centers = UpdateCenters(Centers, Clusters)
Clusters = GetClusters(Centers, X)
Costs[i] = Cost(Centers, X)پس از اجرای این کد و رسم نمودار هیستوگرام، نمودار زیر حاصل می‌شود.
در اولین نگاه، کاملاً مشهود از که ۹۰٪ اجراها به هزینه‌ای کمتر از ۰٫۰۲ رسیده‌اند که در مقایسه با حالت معمولی (۷۰٪) بسیار بهتر است.
توجه داشته باشید که برای اثبات اثربخشی هر الگوریتم، باید تعداد دفعات اجرا بسیار بیشتر از ۱۰۰ بار باشد. از طرفی، بررسی عملکرد روی چندین مجموعه داده نیز از الزامات این کار است. برای مثال، در نمودار اخیر، برای یک اجرا مقدار تابع هزینه به ۰٫۲ رسیده که نسبت به الگوریتم معمولی افزایش یافته است. این حالت برخلاف تصور ما و غالب مشاهدات ما مبنی بر عملکرد بهتر الگوریتم K-means++ بوده است. به همین دلیل، می‌توان با افزایش تعداد دفعات اجرای الگوریتم، با اطمینان بهتری عمل مقایسه را انجام داد.
جمع‌بندی پیاده سازی الگوریتم K-means++ در پایتون
در این مطلب، تابع هزینه و وابستگی الگوریتم Lloyd به شرایط اولیه را بررسی کردیم. همچنین، به پیاده‌سازی الگوریتم K-means++ در پایتون پرداختیم.
برای مطالعه بیشتر، می‌توان پاسخ پرسش‌های زیر را تحقیق کرد:
- چرا از توان دوم فاصله به‌عنوان معیار مرتبط با احتمال انتخاب داده استفاده کردیم؟
- آیا ممکن است در صورت استفاده از الگوریتم K-means++ نیز مراکز خوشه اولیه نزدیک به هم باشند؟ چه راهکاری برای حل این مشکل می‌توان ارائه داد؟
- اگر نمودار هیستوگرام دو الگوریتم را روی هم رسم و آن‌ها را مقایسه کنیم، چه معیارهای آماری می‌توانند عملکرد بهتر الگوریتم K-means++ را نشان دهند؟
- آیا الگوریم K-means++ می‌تواند به‌لحاظ هزینه محاسباتی، مزیتی داشته باشد؟
.png "چرا باید الکترون (ElectronJS) را یاد بگیریم")
.png "کتابخانه بند کفش (ShoeLace) و مزایای آن")
