خوشه‌بندی در داده‌‌کاوی چه انواعی دارد و چگونه پیاده‌سازی می‌شود؟

خوشه‌بندی مرکزگرا یا مرکز-محور (Centroid-based Clustering)

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

• انتخاب تعداد خوشه‌ها: ابتدا باید تعداد خوشه‌هایی را که می‌خواهیم داده‌ها به آن‌ها تقسیم شوند مشخص کنیم. این موضوع می‌تواند به‌صورت دستی تعیین شود یا با استفاده از روش‌های تعیین تعداد بهینه خوشه‌ها مانند روش Elbow استفاده شود.
• مرحله شروع: در این مرحله، موقعیت اولیه مراکز خوشه‌ها به‌صورت تصادفی انتخاب می‌شود. 
• تخصیص به خوشه‌ها: در این مرحله، داده‌ها بر اساس فاصله بین داده‌ها و مراکز خوشه‌ها تخصیص داده می‌شوند. داده‌ها به خوشه‌ای تخصیص می‌یابند که فاصله کمتری با مرکز دارند.
• به‌روزرسانی مراکز خوشه: پس از تخصیص داده‌ها به خوشه‌ها، مراکز خوشه‌ها بر اساس اعضای خوشه‌هایی که به آن‌ها تخصیص پیدا کرده‌اند، به‌روزرسانی می‌شوند. به‌طور معمول، مرکز خوشه بر مبنای میانگین داده‌های خوشه تعیین می‌شود.
• تکرار مراحل 3 و 4: مراحل تخصیص داده‌ها به خوشه‌ها و به‌روزرسانی مراکز خوشه تا زمانی که الگوریتم به معیار تشخیص خاتمه حلقه نرسد ادامه پیدا می‌کند. 
• به‌طور معمول، این معیار می‌تواند شامل تغییر کم و نامحسوس مراکز خوشه‌ها یا تکراری شدن تخصیص داده‌ها باشد.
• خروجی: پس از پایان الگوریتم، خوشه‌بندی نهایی به‌دست می‌آید و می‌توان از آن برای تحلیل داده‌ها یا در مسائل دیگر استفاده کرد. 

خوشه‌بندی مبتنی بر مدل (Model-based Clustering)

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

یکی از مدل‌های احتمالاتی معروف که در خوشه‌بندی مبتنی بر مدل استفاده می‌شود، مدل آمیخته گاوسی (Gaussian Mixture Model) است. در این مدل، فرض می‌شود که داده‌ها از ترکیب توزیع‌های گاوسی مستقل تولید شده‌اند. هر خوشه با یک توزیع گاوسی مشخص معرفی می‌شود که شامل میانگین و ماتریس کواریانس است. مدل مخلوط گاوسی بر اساس الگوریتم EM سرنام Expectation-Maximization برای تخمین پارامترهای مدل و خوشه‌بندی داده‌ها استفاده می‌کند. به‌طور کلی، عملکرد خوشه‌بندی مبتنی بر مدل به‌شرح زیر است:

• انتخاب تعداد خوشه‌ها: برای شروع، تعداد خوشه‌های مورد نظر برای تقسیم‌بندی داده‌ها باید مشخص شود.
• انتخاب مدل: مدل احتمالاتی مناسب برای توزیع داده‌ها باید انتخاب شود. نمونه‌های متداول شامل مدل مخلوط گاوسی، مدل‌های مبتنی بر نمونه اولیه (Prototype-based Models) و مدل‌های دودویی (Binary Models) هستند.
• تخمین پارامترها: با استفاده از الگوریتم‌های مختلف، پارامترهای مدل تخمین زده می‌شوند. برای مدل مخلوط گاوسی، الگوریتم EM بهترین عملکرد را دارد. 
• خوشه‌بندی: پس از تخمین پارامترها، با استفاده از مدل احتمالاتی، احتمال تعلق هر نقطه به خوشه‌ها محاسبه می‌شود. به‌طور معمول، نقاط به خوشه‌ای تخصیص پیدا می‌کنند که احتمال تعلق بیشتری دارند.
• خروجی: پس از اتمام الگوریتم، خوشه‌بندی نهایی به‌دست می‌آید که می‌توان از آن برای تحلیل داده‌ها استفاده کرد.

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

خوشه‌بندی سلسله‌مراتبی (Hierarchical Clustering)

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

خوشه‌بندی تجمیعی (Agglomerative Clustering)

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

خوشه‌بندی تقسیمی (Divisive Clustering)

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

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

خوشه‌بندی فضایی مبتنی بر چگالی در کاربردهای دارای نویز  

خوشه‌بندی فضایی مبتنی بر چگالی در کاربردهای دارای نویز (DBSCAN سرنام Density-Based Spatial Clustering of Applications with Noise ( برای شناسایی خوشه‌هایی با شکل‌ها و اندازه‌های متفاوت در داده‌ها استفاده می‌شود. این تکنیک به کارشناسان کمک می‌کند تا ناهنجاری‌ها در داده‌ها را تشخیص دهند. به بیان دقیق‌تر، DBSCAN نقاطی را که به خوشه‌ای خاص تعلق ندارند به‌عنوان نویز شناسایی می‌کند. خوشه‌بندی DBSCAN بر مبنای دو مفهوم کلیدی زیر عمل می‌کند:

• چگالی (Density): چگالی یک نقطه به تعداد نقاط مشخص که در فاصله‌ای مشخص از آن نقطه قرار دارند، تعریف می‌شود. نقاطی که در فاصله مشخص قرار ندارند، به‌عنوان نقاط مرزی محسوب می‌شوند.
• نقطه مرکزی (Core Point): نقاطی که تعداد نقاط مورد نظر را در فاصله‌ای مشخص (که به‌عنوان شعاع چگالی معروف است) دارند، به‌عنوان نقاط مرکزی شناخته می‌شوند. در DBSCAN، هر نقطه مرکزی برای تشکیل یک خوشه استفاده می‌شود. عملکرد الگوریتم DBSCAN به‌شرح زیر است: 

1.  انتخاب یک نقطه تصادفی از داده‌ها که هنوز به هیچ خوشه‌ای تعلق ندارد.
2.  یافتن همسایگان نقطه انتخاب‌شده در فاصله مشخص (شعاع چگالی) و تعیین این موضوع که آیا آن نقاط به‌عنوان نقاط مرکزی قابل قبول هستند یا خیر.
3.  اگر تعداد نقاط مرکزی قابل قبول به حد نصاب برسد، یک خوشه جدید تشکیل می‌شود و نقاط مرکزی و تمام همسایگان به آن خوشه اضافه می‌شوند. سپس، به‌صورت بازگشتی برای همسایگان هر نقطه مرکزی این مرحله تکرار می‌شود.
4.  اگر نقاط مرکزی قابل قبول کمتر از حد نصاب باشند، نقطه مورد نظر به‌عنوان نویز تشخیص داده می‌شود.
5.  این روند برای نقاط باقی‌مانده ادامه می‌یابد تا تمام نقاط مورد بررسی قرار گیرند. 

چگونه خوشه‌بندی داده‌کاوی را در پایتون پیاده‌سازی کنیم؟

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

1. نصب کتاب‌خانه scikit-learn 

pip install -U scikit-learn

2. وارد کردن ماژول‌های مورد نیاز

from sklearn.cluster import KMeans

3. تعریف داده‌های ورودی

data = [[x1, y1], [x2, y2], ...]

4. ساخت یک شیء خوشه‌بندی

kmeans = KMeans(n_clusters=3)  

5. اجرای الگوریتم خوشه‌بندی بر روی داده‌ها

kmeans.fit(data)

6. دسته‌بندی داده‌ها

labels = kmeans.labels_

اکنون labels شامل برچسب‌های خوشه‌ها برای هر نقطه است. همچنین، می‌توانید مراکز خوشه‌ها را با استفاده از kmeans.cluster_centers دریافت کنید.

قطعه کد بالا مثال ساده‌ای از پیاده‌سازی خوشه‌بندی در پایتون با استفاده از کتاب‌خانه scikit-learn است. بسته به نیاز و الگوریتم خوشه‌بندی مورد نظر، می‌توانیم از روش‌های دیگری مانند خوشه‌بندی سلسله‌مراتبی یا DBSCAN استفاده کنیم. دقت کنید برای هر الگوریتم، مراحل و نحوه انجام کار متفاوت است.

یک مثال جدی‌تر از نحوه اجرای خوشه‌بندی 

فرض کنید می‌خواهید یک خوشه‌بندی روی داده‌های مربوط به گل‌های آیریس (Iris) انجام دهید. برای این منظور، از مجموعه داده‌های Iris که در scikit-learn موجود است استفاده می‌کنیم. ابتدا باید کتاب‌خانه‌های مورد نیاز را وارد کنیم و مجموعه داده را بارگیری کنیم:

from sklearn.datasets import load_iris

from sklearn.cluster import KMeans

import matplotlib.pyplot as plt

iris = load_iris()

data = iris.data

kmeans = KMeans(n_clusters=3)

kmeans.fit(data)

labels = kmeans.labels_

plt.scatter(data[:, 2], data[:, 3], c=labels)

plt.xlabel(‘Petal Length’)

plt.ylabel(‘Petal Width’)

plt.title(‘Clustering of Iris Dataset’)

plt.show()

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

به بیان دقیق‌تر، می‌توانیم به محاسبه مراکز خوشه‌ها و ارزیابی خوشه‌بندی بپردازیم. این اطلاعات کمک می‌کنند تا بهتر درک کنیم الگوریتم خوشه‌بندی چگونه کار می‌کند. در ادامه، همان مثال خوشه‌بندی داده‌های Iris را با اضافه کردن بخش‌های محاسباتی کامل‌تر می‌کنیم. 

iris = load_iris()

data = iris.data

kmeans = KMeans(n_clusters=3)

kmeans.fit(data)

labels = kmeans.labels_

centroids = kmeans.cluster_centers_

plt.scatter(data[:, 2], data[:, 3], c=labels)

plt.scatter(centroids[:, 2], centroids[:, 3], marker=’x’, s=200, linewidths=3, color=’r’)

plt.xlabel(‘Petal Length’)

plt.ylabel(‘Petal Width’)

plt.title(‘Clustering of Iris Dataset’)

plt.show()

correct_labels = iris.target

def calculate_accuracy(labels, correct_labels):

    mapping = {0: 2, 1: 0, 2: 1}  

    mapped_labels = [mapping[label] for label in labels]

    correct_count = sum(mapped_labels == correct_labels)

    accuracy = correct_count / len(correct_labels)

    return accuracy

accuracy = calculate_accuracy(labels, correct_labels)

print(f”Accuracy: {accuracy}”)

در این مثال، پس از اجرای الگوریتم خوشه‌بندی با استفاده از K-Means، مراکز خوشه‌ها را با استفاده از kmeans.cluster_centers دریافت می‌کنیم و آن‌ها را در نمودار با نماد x نشان می‌دهیم. سپس، با استفاده از تابع calculate_accuracy، صحت خوشه‌بندی را با برچسب‌های حقیقی محاسبه و چاپ می‌کنیم. با اجرای کد، شما یک نمودار خوشه‌بندی از داده‌های Iris را به‌همراه صحت خوشه‌بندی دریافت خواهید کرد. 

کلام آخر

خوشه‌بندی در داده‌کاوی به‌عنوان یک فرایند بدون نظارت (Unsupervised Learning) شناخته می‌شود، یعنی در آن برچسب یا کلاس قبلی برای داده‌ها در نظر گرفته نمی‌شود و تنها بر اساس ویژگی‌های داده‌ها خوشه‌بندی انجام می‌شود. استفاده از خوشه‌بندی در داده‌کاوی می‌تواند در شناسایی الگوها، دسته‌بندی داده‌ها و فهم بهتر ساختار داده‌ها کمک کند.