📘 پروژه DPC-MK
عنوان پروژه: پیادهسازی و آزمایش الگوریتم DPC-MK
نام دانشجو: فرخنده خوشنود
ایمیل: F.khoshnoud24@gmail.com
مقطع: دانشجوی مجازی هوش مصنوعی، دانشگاه فردوسی مشهد
مقدمه:
در دنیای امروزه و با پیشرفت علم و گسترش کسب و کارها، داده ها آنقدر پیچیده و گسترده شده اند که برای دسته بندی یا به عبارتی خوشه بندی بعضی ازین داده ها نیاز به الگوریتم برای خوشه بندی آنهاست؛ یکی از الگوریتم های متعددی که برای خوشه بندی داده ها معرفی شدهاست، الگوریتم DPC-MK است که درواقع این الگوریتم نمونهی توسعه یافته از الگوریتم DPC است.
پیشزمینه: الگوریتم DPC
برای اینکه بتوانیم الگوریتم DPC-MK را بهتر درک کنیم، ابتدا لازم است که به DPC بپردازین.
الگوریتم DPC (Density Peaks Clustering) یا بعبارتی خوشهبندی با قلههای چگالی، یک روش خوشهبندی مبتنی بر چگالی است که در آن دو معیار اصلی برای هر نقطه محساب میشود:
- چگالی محلی (ρ - rho): نشان میدهد چقدر نقاط در اطراف نقطهی موردنظر فشرده هستند.
- فاصله از نقاط با چگالی بالاتر (δ - delta): نشان میدهد نقطهی موردنظر چقدر از نقاطی که چگالی بیشتری از خودش دارند، دورهست.
بعد از محاسبهی ρ و δ، نمودار δ در برابر ρ رسم میشود (decision graph).
در این نمودار، نقاطی که هم چگالی بالا دارن (ρ زیاد) و هم از بقیهی نقاط چگالتر دورنند (δ زیاد)، به عنوان مرکز خوشهها در نظر گرفته میشوند.
به زبان خیلی ساده؛ فرض کنید یکسری نقطه روی صفحه داریم.
هر نقطه نشاندهندهی یه داده است (مثلاً موقعیت یه فرد در شهر، رنگ یک پیکسل و یا ویژگی یک نمونه).
حال قرار است این نقاط به چند «خوشه» تقسیم شوند.
ایده اصلی DPC به اینگونه است که هر خوشه یک “قلهی چگالی” دارد که بعنوان مرکز خوشه انتخاب میشود، الگوریتم میخواهد این قلهها (نقاط با چگالی بالا و دور از قلههای دیگر) را پیدا کند.
دو روش معروف برای اندازهگیری چگالی وجود دارد
۱. روش ساده (Cut-off distance):
برای هر نقطه میشمارد که چند نقطه در فاصلهی کمتر از یک عدد مشخص (مثلاً ۱.۰) از آن وجود دارد.
هر چه بیشتر، یعنی چگالتر.
درواقع ( d_c ) همان اندازهای است که نقاط با فاصلهی کمتر از این اندازه با نقطهی موردنظر، برای چگالی آن نقطه شمرده میشوند.
تابع (x) به این صورت عمل میکند:
سپس مجموع این ۰ و ۱ ها به عنوان چگالی برگردانده میشوند.
نکته اینکه فاصلهی هر نقطه با خودش هم در این تابع ۱ برگردانده میشود و برای جلوگیری از شمرده شدن خود نقطه در چگالی آن، در کد الگوریتم نهایتاً یک واحد از چگالی بدست آمده کم میشود.
۲. روش بهدست آوردن چگالی با تابع گوسی:
\[\rho_i = \sum_j e^{-(d_{ij}/d_c)^2}\]بعد از بدست آوردن چگالی نقاط، الگوریتم فاصلهی نقطه تا نقاط چگالتر از خودش را محاسبه میکند:
\[\delta_i = \min_{j: \rho_j > \rho_i} (d_{ij})\]در نهایت، الگوریتم نقاطی که هم چگالی زیادی دارند (قله هستند)، و هم از نقاط چگالتر دیگر دور هستند (یعنی یک قلهی مستقلاند)، را به عنوان مرکز خوشه انتخاب میکند.
در نمودار تصمیم (Decision Graph)، این نقاط معمولاً در بالا سمت راست دیده میشوند.
در ادامه تصویری از نقاط فرضی به عنوان دادهها و چگونگی پراکنده شدن این نقاط در گراف تصمیم حاصل از الگوریتم DPC مشاهده میکنیم:
خوشههای حاصل از این تصویر با دو رنگ قرمز و آبی نمایش داده شدهاند؛ و رنگ سیاه به معنی نویز است.
مزایا:
- عدم نیاز به تعیین تعداد خوشهها از قبل
برخلاف الگوریتمهایی مثل K-Means، نیاز به دانستن مقدار k (تعداد خوشهها) از قبل نیست. - قابلیت شناسایی خوشههای با شکل نامنظم
چون الگوریتم بر پایهی چگالی است، میتواند خوشههایی با شکلهای غیرکروی یا پیچیده را نیز تشخیص دهد. - مفاهیم چگالی (ρ) و فاصله (δ) سادهاند و خروجی گرافیکی (نمودار δ–ρ) قابل تفسیر است
میتوان با نگاه کردن به نمودار براحتی تعداد خوشهها را تشخیص داد. - توانایی شناسایی نویز و دادههای پرت
نقاطی با چگالی پایین و فاصله زیاد از بقیه معمولاً به عنوان نویز شناسایی میشوند. - استقلال از مقیاس دادهها
اگر دادهها نرمالسازی شوند، DPC معمولاً به مقیاسبندی خاصی حساس نیست.
معایب:
- انتخاب دستی مراکز خوشهها
مراکز خوشه از روی نمودار δ–ρ توسط کاربر انتخاب میشوند، نه بهصورت خودکار. این باعث میشود الگوریتم نیمهخودکار، وابسته به قضاوت انسان و غیرتکرارپذیر باشد. - پیچیدگی زمانی بالا
محاسبهی فاصله بین تمام جفتنقاطها زمانبر است. - حساسیت به نویز زیاد
هرچند میتواند نویز را تشخیص دهد، اما اگر نویز خیلی زیاد باشد، ممکن است قلههای کاذب ایجاد شوند و خوشهها اشتباه تشخیص داده شوند.
الگوریتم DPC-MK
در نسخهی DPC-KM (که ترکیبی از DPC و K-Means هست)، ضعفهای DPC مثل انتخاب دستی مراکز یا دقت پایین در مرزبندی خوشهها برطرف میشود.
در این الگوریتم علاوه بر چگالی محلی، نزدیکترین همسایه هم محاسبه میشود.
یعنی در DPC-KM، بعد از محاسبهی چگالی هر نقطه (ρ)، الگوریتم فقط به مقدار چگالی بسنده نمیکند؛ بلکه بررسی میکند که هر نقطه نزدیکترین همسایهی با چگالی بالاتراز خودش را شناخته و به آن متصل شود.
بطور خلاصه:
در DPC-KM، “نزدیکترین همسایه با چگالی بالاتر” برای هر نقطه مشخص میشود؛ یعنی برای هر نقطه مشخص میشود که باید به کدام مرکز (قلهی چگالی) متصل شود؛
که دراین صورت خوشهبندی بهصورت خودکارتر و دقیقتر انجام میشود و بخش K-Means مرزهای خوشهها را اصلاح میکند.
نتایج
تشخیص بهتر خوشههای غیرخطی
کاهش خطا در دادههای مرزی
۱. هدر فایل / توضیحات
"""
dpc_mk.py
A compact implementation of Density Peaks Clustering with a simple "MK" (multi-K / mutual-KNN)
extension to strengthen neighborhood relations. This is intended as an easy-to-run
research/demo implementation (not highly optimized for very large datasets).
"""
۲. وارد کردن کتابخانهها (imports)
| خط کد | توضیح |
|---|---|
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 وارد میکند. |
import numpy as np
from sklearn.metrics import pairwise_distances
from sklearn.neighbors import NearestNeighbors
۳. تابع compute_rho
توضیح: محاسبه چگالی ساده — تعداد نقاطی که فاصلهشان کمتر از dc است (به ازای هر نقطه).
def compute_rho(dist_matrix, dc):
# rho: تعداد نقاط با فاصله کمتر از dc (نسخه ساده)
n = dist_matrix.shape[0]
rho = np.sum(dist_matrix < dc, axis=1) - 1 # کم کردن خودِ نقطه
return rho
۴. تابع compute_delta
توضیح: برای هر نقطه فاصله تا نزدیکترین نقطه با چگالی بالاتر و اندیسِ آن را محاسبه میکند.
def compute_delta(dist_matrix, rho):
n = dist_matrix.shape[0]
delta = np.full(n, np.inf)
nneigh = np.full(n, -1, dtype=int)
order = np.argsort(-rho) # نزولی
for i_idx, i in enumerate(order):
if i_idx == 0:
delta[i] = np.max(dist_matrix[i])
nneigh[i] = -1
else:
higher = order[:i_idx]
dists = dist_matrix[i, higher]
j = higher[np.argmin(dists)]
delta[i] = dist_matrix[i, j]
nneigh[i] = j
return delta, nneigh
۵. تابع build_mk_score
توضیح: ساخت ماتریس وزن W براساس چند گراف k-NN. اگر mutual=True فقط لبههای متقابل نگه داشته میشوند.
def build_mk_score(X, k_list=(5,10,15), mutual=True):
"""
Build a weighted adjacency score matrix W based on multiple k-NN graphs.
W[i,j] = number of times j appears in i's kNN across k_list.
If mutual=True, keep only mutual edges via min(W, W^T).
Returns: W (n x n float)
"""
X = np.asarray(X)
n = X.shape[0]
W = np.zeros((n, n), dtype=float)
for k in k_list:
k_use = min(k, n-1)
nbrs = NearestNeighbors(n_neighbors=k_use+1).fit(X)
_, idx = nbrs.kneighbors(X)
for i in range(n):
neighs = idx[i, 1:] # skip itself
for j in neighs:
W[i, j] += 1.0
if mutual:
W = np.minimum(W, W.T)
return W
۶. تابع assign_labels_with_mk
توضیح: واگذاری برچسبها با دنبال کردن nneigh (روش استاندارد DPC). اگر W داده شده باشد، از آن برای ترجیح دادن والد با وزن قویتر استفاده میشود.
def assign_labels_with_mk(dist_matrix, rho, nneigh, centers_idx, W=None):
"""
Assign labels by following nneigh (standard DPC assignment),
but if W is provided, use W to break ties in ambiguous cases:
prefer assigning to neighbor with stronger W weight.
"""
n = dist_matrix.shape[0]
labels = -np.ones(n, dtype=int)
for idx, c in enumerate(centers_idx):
labels[c] = idx
order = np.argsort(-rho)
for i in order:
if labels[i] != -1:
continue
j = nneigh[i]
if j == -1:
# fallback: assign to nearest center
d2cent = dist_matrix[i, centers_idx]
labels[i] = np.argmin(d2cent)
else:
# normally inherit label of nneigh
# but if W exists and multiple possible parents, pick by W
labels[i] = labels[j]
if W is not None:
# check among higher-rho neighbors for strongest W
higher_idx = np.where(rho > rho[i])[0]
if higher_idx.size > 0:
cand = higher_idx
weights = W[cand, i]
best = cand[np.argmax(weights)]
if labels[best] != -1:
labels[i] = labels[best]
return labels
۷. تابع اصلی dpc_mk
توضیح: اجرای کامل الگوریتم با محاسبه dc، rho، delta، gamma، انتخاب مراکز و ساخت W و در نهایت واگذاری برچسبها.
def dpc_mk(X, percent_dc=2.0, k_list=(5,10,15), top_centers=None, mutual=True):
"""
Main function:
- X: (n_samples, n_features)
- percent_dc: percentile for dc (default 2.0)
- k_list: list/tuple of k values for MK scoring
- top_centers: if int, choose this many centers (otherwise sqrt heuristic)
- mutual: whether MK uses mutual edges
Returns dict with labels, centers_idx, rho, delta, gamma, dc
"""
X = np.asarray(X)
n = X.shape[0]
dist = pairwise_distances(X)
# compute dc using percentile of pairwise distances
if n <= 1:
raise ValueError("Need at least 2 samples")
dists = dist[np.triu_indices(n, 1)]
dc = np.percentile(dists, percent_dc)
rho = compute_rho(dist, dc)
delta, nneigh = compute_delta(dist, rho)
gamma = rho * delta
if top_centers is None:
top_centers = max(1, int(np.sqrt(n)))
centers_idx = np.argsort(-gamma)[:top_centers]
# build MK score
W = build_mk_score(X, k_list=k_list, mutual=mutual)
labels = assign_labels_with_mk(dist, rho, nneigh, centers_idx, W=W)
return {
"labels": labels,
"centers_idx": centers_idx,
"rho": rho,
"delta": delta,
"gamma": gamma,
"dc": dc,
"W": W
}
۸. بخش اجرای سریع (smoke test)
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-Kassign_labels_with_mk→ تخصیص برچسبهاdpc_mk→ اجرای کامل الگوریتم
📷 خروجیهای نمونه
| تصویر | توضیح |
|---|---|
 |
|
 |
🧮 کاربردها
زیستدادهها (Bioinformatics)
بینایی ماشین (Computer Vision)
تحلیل بازار و دادههای پیچیده (Marketing Data Analysis)
🏁 نتیجهگیری
الگوریتم DPC-MK قادر است خوشههای غیرمرکزی را با دقت بالا شناسایی کند.
افزودن مؤلفهی Multi-K باعث کاهش خطا و بهبود دقت در دادههای پیچیده میشود.
پیشنهاد: استفاده از DPC-MK در دادههای بزرگتر و مقایسه با سایر روشهای خوشهبندی.