Hadi Sadoghi Yazdi

Professor of Electrical and
Computer Engineering

📘 پروژه DPC-MK

عنوان پروژه: پیاده‌سازی و آزمایش الگوریتم DPC-MK
نام دانشجو: فرخنده خوشنود
ایمیل: F.khoshnoud24@gmail.com
مقطع: دانشجوی مجازی هوش مصنوعی، دانشگاه فردوسی مشهد

🧩 مقدمه

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

الگوریتم DPC-MK (Density Peak Clustering with Modified Kernels) با استفاده از چگالی نقاط و فاصله تا نقاط با چگالی بالاتر، خوشه‌ها را به شکلی دقیق شناسایی می‌کند. در این پروژه پیاده‌سازی این الگوریتم انجام شده و عملکرد آن بر روی داده‌های نمونه بررسی و به صورت تصویری نمایش داده شده است.

📘 پیش‌زمینه: الگوریتم DPC

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

  • ρ: چگالی محلی
  • δ: فاصله تا نزدیک‌ترین نقطه با چگالی بیشتر

مراکز خوشه در نواحی با ρ و δ بالا قرار دارند.

✅ مزایا

  • بدون نیاز به تعیین تعداد خوشه‌ها
  • تشخیص شکل‌های پیچیده
  • اجرای سریع و بدون تکرار زیاد

⚠️ معایب

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

منابع: Frontiers, AIMS Press

📈 خلاصه DPC-MK

DPC-MK نسخه‌ی توسعه‌یافته‌ی DPC است و برای داده‌های با چگالی متغیر طراحی شده است.

ویژگی‌های کلیدی

  • استفاده از KNN یا KNN متقابل برای چگالی دقیق‌تر
  • انتخاب مراکز با ترکیب چگالی و همسایگی
  • تخصیص چندمرحله‌ای و وزن‌دار نقاط مرزی

نتایج

  • تشخیص بهتر خوشه‌های غیرخطی
  • کاهش خطا در داده‌های مرزی

⚙️ کتابخانه‌ها و نصب

کتابخانه توضیح دستور نصب
numpy عملیات عددی و آرایه‌ها pip install numpy
matplotlib رسم نمودارها pip install matplotlib
scipy محاسبات علمی و فاصله‌ها pip install scipy

دستور نصب سریع همه با هم:

pip install numpy matplotlib scipy

🧠 کد اصلی پروژه (demo.py)

این کد از الگوریتم DPC-MK برای خوشه‌بندی داده‌ها استفاده کرده و نتایج را با matplotlib نمایش می‌دهد.

🧩 بخش ۱: وارد کردن کتابخانه‌ها (Imports)

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

import matplotlib.pyplot as plt
from sklearn.datasets import make_moons, make_blobs
from dpc_mk import dpc_mk
خط کد توضیح
import matplotlib.pyplot as plt کتابخانه matplotlib را برای رسم نمودارها وارد می‌کند و نام مستعار plt به آن می‌دهد.
from sklearn.datasets import make_moons, make_blobs توابعی از scikit-learn برای تولید داده‌های مصنوعی (داده‌های هلالی و توده‌ای) جهت آزمایش استفاده می‌شوند.
from dpc_mk import dpc_mk تابع اصلی خوشه‌بندی DPC-MK را از ماژول محلی dpc_mk وارد می‌کند.

🎨 بخش ۲: تعریف تابع plot_clusters

این تابع مسئول نمایش نتایج خوشه‌بندی است.

def plot_clusters(X, labels, centers_idx=None, title="DPC-MK"):
    plt.figure(figsize=(6,5))
    plt.scatter(X[:,0], X[:,1], c=labels, s=25, cmap='tab10')
    if centers_idx is not None and len(centers_idx) > 0:
        plt.scatter(X[centers_idx,0], X[centers_idx,1],
                    s=150, facecolors='none', edgecolors='k', linewidths=2)
    plt.title(title)
    plt.tight_layout()
    plt.show()
خط کد توضیح
def plot_clusters(...) تعریف تابع با چهار پارامتر ورودی: داده‌ها، برچسب‌ها، مراکز خوشه و عنوان نمودار.
plt.figure(figsize=(6,5)) یک پنجره‌ی نمودار جدید با اندازه‌ی ۶×۵ اینچ ایجاد می‌کند.
plt.scatter(X[:,0], X[:,1], c=labels, ...) نقاط داده را رسم می‌کند؛ هر خوشه با رنگ متفاوت نمایش داده می‌شود.
if centers_idx is not None and len(centers_idx) > 0: بررسی می‌کند که آیا مراکز خوشه مشخص شده‌اند.
plt.scatter(X[centers_idx,0], X[centers_idx,1], ...) مراکز خوشه را با دایره‌های بزرگ‌تر، توخالی و حاشیه مشکی نمایش می‌دهد.
plt.title(title) عنوان نمودار را تنظیم می‌کند.
plt.tight_layout() فاصله بین اجزای نمودار را به‌صورت خودکار تنظیم می‌کند.
plt.show() نمودار نهایی را نمایش می‌دهد.

⚙️ بخش ۳: بدنه‌ی اصلی اجرای کد (Main Execution Block)

این بخش داده‌های آزمایشی را تولید کرده، الگوریتم DPC-MK را اجرا و نتایج را نمایش می‌دهد.

if __name__ == "__main__":
    X1, _ = make_moons(n_samples=300, noise=0.08, random_state=0)
    res1 = dpc_mk(X1, percent_dc=2.0, k_list=(5,10,15), mutual=True)
    plot_clusters(X1, res1["labels"], res1["centers_idx"], title="moons - DPC-MK")

    X2, _ = make_blobs(n_samples=400, centers=4, cluster_std=0.6, random_state=1)
    res2 = dpc_mk(X2, percent_dc=2.0, k_list=(5,10,20), mutual=True)
    plot_clusters(X2, res2["labels"], res2["centers_idx"], title="blobs - DPC-MK")
خط کد توضیح
if __name__ == "__main__": اطمینان حاصل می‌کند که این کد تنها در صورت اجرای مستقیم فایل اجرا شود.
X1, _ = make_moons(...) داده‌های هلالی شکل (Moons) را برای آزمایش تولید می‌کند.
res1 = dpc_mk(X1, ...) اجرای الگوریتم DPC-MK بر روی داده‌های هلالی.
plot_clusters(X1, ...) نمایش نتایج خوشه‌بندی داده‌های هلالی.
X2, _ = make_blobs(...) تولید داده‌های توده‌ای (Blobs) با ۴ خوشه‌ی مجزا.
res2 = dpc_mk(X2, ...) اجرای الگوریتم DPC-MK بر روی داده‌های توده‌ای.
plot_clusters(X2, ...) نمایش نتایج خوشه‌بندی داده‌های توده‌ای.

🧩 ماژول اصلی (dpc_mk.py)

این فایل شامل توابع زیر است:

  • compute_rho → محاسبه چگالی محلی
  • compute_delta → محاسبه فاصله δ
  • build_mk_score → ساخت ماتریس وزن Multi-K
  • assign_labels_with_mk → تخصیص برچسب‌ها
  • dpc_mk → اجرای کامل الگوریتم

📷 خروجی‌های نمونه

تصویر توضیح
Figure-1  
Figure-2  

🧮 کاربردها

  • زیست‌داده‌ها (Bioinformatics)
  • بینایی ماشین (Computer Vision)
  • تحلیل بازار و داده‌های پیچیده (Marketing Data Analysis)

🏁 نتیجه‌گیری

الگوریتم DPC-MK قادر است خوشه‌های غیرمرکزی را با دقت بالا شناسایی کند.
افزودن مؤلفه‌ی Multi-K باعث کاهش خطا و بهبود دقت در داده‌های پیچیده می‌شود.

پیشنهاد: استفاده از DPC-MK در داده‌های بزرگ‌تر و مقایسه با سایر روش‌های خوشه‌بندی.