برنامه نویسی و طراحی سایت

پیاده سازی الگوریتم K-means++‎‏ در پایتون — راهنمای گام به گام

پیاده سازی الگوریتم K-means++‎‏ در پایتون — راهنمای گام به گام

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

فهرست مطالب این نوشته
الگوریتم K-means++‎

بررسی وابستگی الگوریتم Lloyd به شرایط اولیه

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

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

faradars mobile

الگوریتم 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++‎ است.

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

آموزش خوشه بندی K میانگین K-Means با اس پی اس اس SPSS
فیلم آموزش خوشه بندی K میانگین K-Means با اس پی اس اس SPSS در تم آف

کلیک کنید

این الگوریتم را می‌توان در مراحل زیر توصیف کرد:

۱. مرکز خوشه اول ($$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()

که شکل زیر خواهیم داشت.

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

حال تابع هزینه را در قالب یک تابع تعریف می‌کنیم. در ورودی این تابع داده‌ها و مراکز خوشه‌ها را دریافت و در خروجی 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 توزیع را با جزئیات مناسب نشان نمی‌دهد و زیاد بودن آن باعث ایجاد ناپیوستگی‌هایی در نمودار می‌شود و باز هم مطلوب نیست. به همین دلیل، باید تعداد آن با توجه به اندازه داده و در بازه‌ مطلوب قرار گرفته باشد.

آموزش خوشه بندی تفکیکی با نرم افزار آر R
فیلم آموزش خوشه بندی تفکیکی با نرم افزار آر R در تم آف

کلیک کنید

پس از اجرای کد فوق نمودار زیر حاصل خواهد شد.

پیاده سازی کا مینز پلاس پلاس

به این ترتیب، مشاهده می‌کنیم که حدود ۷۰ بار اجرا، به هزینه‌ای کمتر از ۰٫۰۲ ختم شده است. در مقابل، برای برخی اجراها، تابع هزینه به بیشتر ۰٫۱۴ رسیده است که ۳۵ برابر کمترین مقدار است. به این ترتیب، به‌سادگی وابستگی الگوریتم Lloyd به شرایط اولیه مشاهده می‌شود.

آموزش خوشه بندی سلسله مراتبی با SPSS ای پی اس اس
فیلم آموزش خوشه بندی سلسله مراتبی با SPSS ای پی اس اس در تم آف

کلیک کنید

پیاده سازی الگوریتم 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 در خروجی یک آرایه برمی‌گرداند که با توجه به اینکه تنها یک عدد در آن وجود دارد، تنها عضو اول آن را انتخاب می‌کنیم.

آموزش خوشه بندی K میانگین K-Means با اس پی اس اس SPSS
فیلم آموزش خوشه بندی K میانگین K-Means با اس پی اس اس SPSS در تم آف

کلیک کنید

در نهایت، نیز مراکز خوشه‌ها را در خروجی برمی‌گردانیم و تابع نهایی شکل زیر را به خود می‌گیرد:

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++‎ بوده است. به همین دلیل، می‌توان با افزایش تعداد دفعات اجرای الگوریتم، با اطمینان بهتری عمل مقایسه را انجام داد.

آموزش کتابخانه scikit-learn در پایتون – الگوریتم های یادگیری ماشین
فیلم آموزش کتابخانه scikit-learn در پایتون – الگوریتم های یادگیری ماشین در تم آف

کلیک کنید

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

در این مطلب، تابع هزینه و وابستگی الگوریتم Lloyd به شرایط اولیه را بررسی کردیم. همچنین، به پیاده‌سازی الگوریتم K-means++‎ در پایتون پرداختیم.

مجموعه آموزش داده کاوی و یادگیری ماشین
فیلم مجموعه آموزش داده کاوی و یادگیری ماشین در تم آف

کلیک کنید

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

  1. چرا از توان دوم فاصله به‌عنوان معیار مرتبط با احتمال انتخاب داده استفاده کردیم؟
  2. آیا ممکن است در صورت استفاده از الگوریتم K-means++‎ نیز مراکز خوشه اولیه نزدیک به هم باشند؟ چه راهکاری برای حل این مشکل می‌توان ارائه داد؟
  3. اگر نمودار هیستوگرام دو الگوریتم را روی هم رسم و آن‌ها را مقایسه کنیم، چه معیارهای آماری می‌توانند عملکرد بهتر الگوریتم K-means++‎ را نشان دهند؟
  4. آیا الگوریم K-means++‎ می‌تواند به‌لحاظ هزینه محاسباتی، مزیتی داشته باشد؟

دیدگاهتان را بنویسید

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

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.