یادگیری نظارت‌نشده و الگوریتم‌های خوشه‌بندی

در اکثر پروژه‌های واقعی با حجم عظیمی از داده‌های بدون برچسب روبه‌رو هستیم؛ از لاگ‌های شبکه و نشست‌های کاربری وب‌سایت‌ها گرفته تا سوابق پزشکی بیماران. برچسب‌گذاری دستی این داده‌ها نیازمند زمان و هزینه‌ی بسیار بالاست و گاهی عملاً ممکن نیست. یادگیری نظارت‌نشده راهکاری دقیق برای درک داده‌های خام، دسته‌بندی آن‌ها و کشف الگوهای مخفی بدون نیاز به ناظر بیرونی در اختیارتان می‌گذارد.

در این درس به‌جای تکیه بر فراخوانی توابع آماده، الگوریتم‌های پایه‌ای خوشه‌بندی مانند K-Means، DBSCAN و مدل‌های آمیخته‌ی گوسی (GMM) را از صفر پیاده‌سازی می‌کنید و شیوه‌ی ارزیابی خوشه‌ها با امتیاز سیلوئت و روش آرنجی را یاد می‌گیرید. در نهایت نیز یاد می‌گیرید چگونه از همین مفاهیم برای طراحی سیستم‌های تشخیص ناهنجاری استفاده کنید.

بدون برچسب، بدون معلم. الگوریتم خودش ساختار را پیدا می‌کند.

اهداف یادگیری

• پیاده‌سازی K-Means، DBSCAN و مدل‌های آمیخته‌ی گوسی (Gaussian Mixture Models یا GMM) از صفر و مقایسه‌ی رفتار خوشه‌بندی آن‌ها
• ارزیابی کیفیت خوشه‌ها با امتیاز سیلوئت (silhouette score) و روش آرنجی (elbow method) برای انتخاب K بهینه
• توضیح شرایط برتری DBSCAN نسبت به K-Means و تشخیص الگوریتم مناسب برای خوشه‌های غیرکروی و داده‌های پرت (outliers)
• ساخت پایپ‌لاین تشخیص ناهنجاری (anomaly detection) با روش‌های خوشه‌بندی برای شناسایی داده‌هایی که از الگوهای عادی انحراف دارند

صورت مسئله

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

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

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

مفاهیم پایه

خوشه‌بندی: گروه‌بندی داده‌های مشابه

خوشه‌بندی (Clustering) هر نقطه‌ی داده را به یک گروه (خوشه) اختصاص می‌دهد، به‌طوری که نقاط درون یک گروه شباهت بیشتری به یکدیگر داشته باشند تا به نقاط گروه‌های دیگر. پرسش همیشگی این است: منظور از «مشابه» دقیقاً چیست؟

K-Means: اسب کاری خوشه‌بندی

الگوریتم K-Means داده‌ها را دقیقاً به K خوشه افراز می‌کند. هر خوشه یک مرکز (centroid یا مرکز جرم) دارد و هر نقطه به نزدیک‌ترین مرکز تعلق می‌گیرد.

الگوریتم لوید (Lloyd's algorithm):

1. انتخاب K نقطه‌ی تصادفی به‌عنوان مراکز اولیه‌ی خوشه‌ها
2. تخصیص هر نقطه‌ی داده به نزدیک‌ترین مرکز
3. محاسبه‌ی دوباره‌ی هر مرکز به‌عنوان میانگین نقاط اختصاص‌یافته به آن
4. تکرار گام‌های 2 و 3 تا زمانی که تخصیص‌ها دیگر تغییر نکنند

تابع هدف (اینرسی یا inertia) مجموع مجذور فاصله‌ی هر نقطه تا مرکز خوشه‌ی اختصاص‌یافته‌اش را اندازه می‌گیرد. الگوریتم K-Means این مقدار را کمینه می‌کند، اما فقط به یک کمینه‌ی محلی (local minimum) می‌رسد. مقداردهی‌های اولیه‌ی مختلف می‌توانند نتایج متفاوتی به بار آورند.

انتخاب K

دو روش استاندارد:

روش آرنجی (Elbow method): اجرای K-Means به ازای $K = 1, 2, 3, \ldots, n$. رسم نمودار اینرسی بر حسب K. پیدا کردن نقطه‌ی «آرنج»؛ جایی که افزودن خوشه‌های بیشتر دیگر اینرسی را به میزان چشمگیری کاهش نمی‌دهد.

امتیاز سیلوئت (Silhouette score): برای هر نقطه، میزان شباهت آن به خوشه‌ی خودش ($a$) در مقایسه با نزدیک‌ترین خوشه‌ی دیگر ($b$) سنجیده می‌شود. ضریب سیلوئت برابر است با $(b - a) / \max(a, b)$ و بازه‌ی آن از 1- (خوشه‌بندی نادرست) تا 1+ (خوشه‌بندی عالی) تغییر می‌کند. با میانگین‌گیری روی تمام نقاط، یک امتیاز سراسری به دست می‌آید.

DBSCAN: خوشه‌بندی مبتنی بر چگالی

الگوریتم K-Means فرض می‌کند خوشه‌ها کروی هستند و شما را مجبور می‌کند از همان ابتدا K را مشخص کنید. DBSCAN هیچ‌کدام از این دو فرض را ندارد. این الگوریتم خوشه‌ها را به‌صورت ناحیه‌های چگالی پیدا می‌کند که با نواحی کم‌تراکم از هم جدا شده‌اند.

دو پارامتر:

• eps: شعاع یک همسایگی
• min_samples: حداقل تعداد نقاط لازم برای تشکیل یک ناحیه‌ی چگال

سه نوع نقطه:

• نقطه‌ی مرکزی (Core point): حداقل به تعداد min_samples نقطه در فاصله‌ی eps خود دارد
• نقطه‌ی مرزی (Border point): در فاصله‌ی eps یک نقطه‌ی مرکزی است، اما خودش نقطه‌ی مرکزی نیست
• نقطه‌ی نویز (Noise point): نه مرکزی است و نه مرزی. این‌ها همان داده‌های پرت هستند.

الگوریتم DBSCAN نقاط مرکزی را که در فاصله‌ی eps یکدیگر باشند به یک خوشه وصل می‌کند. نقاط مرزی به خوشه‌ی یک نقطه‌ی مرکزی مجاور ملحق می‌شوند. نقاط نویز به هیچ خوشه‌ای تعلق نمی‌گیرند.

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

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

این روش درختی از خوشه‌های تودرتو (دندروگرام یا dendrogram) می‌سازد.

تجمعی (Agglomerative یا پایین‌به‌بالا):

1. شروع کار با فرض اینکه هر نقطه خود یک خوشه است
2. merge کردن دو خوشه‌ی نزدیک‌تر به یکدیگر
3. تکرار تا زمانی که فقط یک خوشه باقی بماند
4. برش دندروگرام در سطح دلخواه برای رسیدن به K خوشه

معیار «نزدیکی» میان خوشه‌ها را می‌توان به روش‌های زیر اندازه گرفت:

• پیوند تکی (Single linkage): کمترین فاصله بین هر دو نقطه در دو خوشه
• پیوند کامل (Complete linkage): بیشترین فاصله بین هر دو نقطه
• پیوند میانگین (Average linkage): میانگین فاصله‌ی تمام جفت‌ها
• روش وارد (Ward's method): حالتی از merge که کمترین افزایش را در واریانس کل درون‌خوشه‌ای ایجاد کند

مدل‌های آمیخته‌ی گوسی (GMM)

الگوریتم K-Means تخصیص سخت (hard assignment) انجام می‌دهد؛ یعنی هر نقطه دقیقاً به یک خوشه تعلق دارد. در مقابل، GMM تخصیص نرم (soft assignment) دارد؛ یعنی هر نقطه یک احتمال برای تعلق به هر خوشه دریافت می‌کند.

مدل GMM فرض می‌کند داده‌ها از ترکیبی از K توزیع گوسی تولید شده‌اند که هر کدام میانگین و کوواریانس ویژه‌ی خود را دارند. الگوریتم امید ریاضی-بیشینه‌سازی (Expectation-Maximization یا EM) بین دو مرحله تناوب می‌کند:

• گام E (امید ریاضی): محاسبه‌ی احتمال تعلق هر نقطه به هر توزیع گوسی
• گام M (بیشینه‌سازی): به‌روزرسانی میانگین، کوواریانس و وزن ترکیب هر توزیع گوسی برای بیشینه‌سازی درست‌نمایی داده‌ها

مدل GMM می‌تواند خوشه‌های بیضوی را مدل‌سازی کند (نه فقط کروی مانند K-Means) و خوشه‌های هم‌پوشان را هم به‌طور طبیعی مدیریت می‌کند.

چه زمانی از کدام استفاده کنیم؟

تشخیص ناهنجاری با خوشه‌بندی

خوشه‌بندی ذاتاً از تشخیص ناهنجاری پشتیبانی می‌کند:

• K-Means: نقاطی که از تمام مراکز فاصله دارند، ناهنجاری هستند
• DBSCAN: نقاط نویز بر اساس تعریف ناهنجاری به شمار می‌آیند
• GMM: نقاطی که تحت تمام توزیع‌های گوسی احتمال پایینی دارند، ناهنجاری تلقی می‌شوند

ساخت گام‌به‌گام

گام 1: پیاده‌سازی K-Means از صفر

import math
import random


def euclidean_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))


def kmeans(data, k, max_iterations=100, seed=42):
    random.seed(seed)
    n_features = len(data[0])

    centroids = random.sample(data, k)

    for iteration in range(max_iterations):
        clusters = [[] for _ in range(k)]
        assignments = []

        for point in data:
            distances = [euclidean_distance(point, c) for c in centroids]
            nearest = distances.index(min(distances))
            clusters[nearest].append(point)
            assignments.append(nearest)

        new_centroids = []
        for cluster in clusters:
            if len(cluster) == 0:
                new_centroids.append(random.choice(data))
                continue
            centroid = [
                sum(point[j] for point in cluster) / len(cluster)
                for j in range(n_features)
            ]
            new_centroids.append(centroid)

        if all(
            euclidean_distance(old, new) < 1e-6
            for old, new in zip(centroids, new_centroids)
        ):
            print(f"  Converged at iteration {iteration + 1}")
            break

        centroids = new_centroids

    return assignments, centroids

گام 2: روش آرنجی و امتیاز سیلوئت

def compute_inertia(data, assignments, centroids):
    total = 0.0
    for point, cluster_id in zip(data, assignments):
        total += euclidean_distance(point, centroids[cluster_id]) ** 2
    return total


def silhouette_score(data, assignments):
    n = len(data)
    if n < 2:
        return 0.0

    clusters = {}
    for i, c in enumerate(assignments):
        clusters.setdefault(c, []).append(i)

    if len(clusters) < 2:
        return 0.0

    scores = []
    for i in range(n):
        own_cluster = assignments[i]
        own_members = [j for j in clusters[own_cluster] if j != i]

        if len(own_members) == 0:
            scores.append(0.0)
            continue

        a = sum(euclidean_distance(data[i], data[j]) for j in own_members) / len(own_members)

        b = float("inf")
        for cluster_id, members in clusters.items():
            if cluster_id == own_cluster:
                continue
            avg_dist = sum(euclidean_distance(data[i], data[j]) for j in members) / len(members)
            b = min(b, avg_dist)

        if max(a, b) == 0:
            scores.append(0.0)
        else:
            scores.append((b - a) / max(a, b))

    return sum(scores) / len(scores)


def find_best_k(data, max_k=10):
    print("Elbow method:")
    inertias = []
    for k in range(1, max_k + 1):
        assignments, centroids = kmeans(data, k)
        inertia = compute_inertia(data, assignments, centroids)
        inertias.append(inertia)
        print(f"  K={k}: inertia={inertia:.2f}")

    print("\nSilhouette scores:")
    for k in range(2, max_k + 1):
        assignments, centroids = kmeans(data, k)
        score = silhouette_score(data, assignments)
        print(f"  K={k}: silhouette={score:.4f}")

    return inertias

گام 3: پیاده‌سازی DBSCAN از صفر

def dbscan(data, eps, min_samples):
    n = len(data)
    labels = [-1] * n
    cluster_id = 0

    def region_query(point_idx):
        neighbors = []
        for i in range(n):
            if euclidean_distance(data[point_idx], data[i]) <= eps:
                neighbors.append(i)
        return neighbors

    visited = [False] * n

    for i in range(n):
        if visited[i]:
            continue
        visited[i] = True

        neighbors = region_query(i)

        if len(neighbors) < min_samples:
            labels[i] = -1
            continue

        labels[i] = cluster_id
        seed_set = list(neighbors)
        seed_set.remove(i)

        j = 0
        while j < len(seed_set):
            q = seed_set[j]

            if not visited[q]:
                visited[q] = True
                q_neighbors = region_query(q)
                if len(q_neighbors) >= min_samples:
                    for nb in q_neighbors:
                        if nb not in seed_set:
                            seed_set.append(nb)

            if labels[q] == -1:
                labels[q] = cluster_id

            j += 1

        cluster_id += 1

    return labels

گام 4: مدل آمیخته‌ی گوسی (الگوریتم EM)

def gmm(data, k, max_iterations=100, seed=42):
    random.seed(seed)
    n = len(data)
    d = len(data[0])

    indices = random.sample(range(n), k)
    means = [list(data[i]) for i in indices]
    variances = [1.0] * k
    weights = [1.0 / k] * k

    def gaussian_pdf(x, mean, variance):
        d = len(x)
        coeff = 1.0 / ((2 * math.pi * variance) ** (d / 2))
        exponent = -sum((xi - mi) ** 2 for xi, mi in zip(x, mean)) / (2 * variance)
        return coeff * math.exp(max(exponent, -500))

    for iteration in range(max_iterations):
        responsibilities = []
        for i in range(n):
            probs = []
            for j in range(k):
                probs.append(weights[j] * gaussian_pdf(data[i], means[j], variances[j]))
            total = sum(probs)
            if total == 0:
                total = 1e-300
            responsibilities.append([p / total for p in probs])

        old_means = [list(m) for m in means]

        for j in range(k):
            r_sum = sum(responsibilities[i][j] for i in range(n))
            if r_sum < 1e-10:
                continue

            weights[j] = r_sum / n

            for dim in range(d):
                means[j][dim] = sum(
                    responsibilities[i][j] * data[i][dim] for i in range(n)
                ) / r_sum

            variances[j] = sum(
                responsibilities[i][j]
                * sum((data[i][dim] - means[j][dim]) ** 2 for dim in range(d))
                for i in range(n)
            ) / (r_sum * d)
            variances[j] = max(variances[j], 1e-6)

        shift = sum(
            euclidean_distance(old_means[j], means[j]) for j in range(k)
        )
        if shift < 1e-6:
            print(f"  GMM converged at iteration {iteration + 1}")
            break

    assignments = []
    for i in range(n):
        assignments.append(responsibilities[i].index(max(responsibilities[i])))

    return assignments, means, weights, responsibilities

گام 5: تولید داده‌های آزمایشی و اجرای همه‌چیز

def make_blobs(centers, n_per_cluster=50, spread=0.5, seed=42):
    random.seed(seed)
    data = []
    true_labels = []
    for label, (cx, cy) in enumerate(centers):
        for _ in range(n_per_cluster):
            x = cx + random.gauss(0, spread)
            y = cy + random.gauss(0, spread)
            data.append([x, y])
            true_labels.append(label)
    return data, true_labels


def make_moons(n_samples=200, noise=0.1, seed=42):
    random.seed(seed)
    data = []
    labels = []
    n_half = n_samples // 2
    for i in range(n_half):
        angle = math.pi * i / n_half
        x = math.cos(angle) + random.gauss(0, noise)
        y = math.sin(angle) + random.gauss(0, noise)
        data.append([x, y])
        labels.append(0)
    for i in range(n_half):
        angle = math.pi * i / n_half
        x = 1 - math.cos(angle) + random.gauss(0, noise)
        y = 1 - math.sin(angle) - 0.5 + random.gauss(0, noise)
        data.append([x, y])
        labels.append(1)
    return data, labels


if __name__ == "__main__":
    centers = [[2, 2], [8, 3], [5, 8]]
    data, true_labels = make_blobs(centers, n_per_cluster=50, spread=0.8)

    print("=== K-Means on 3 blobs ===")
    assignments, centroids = kmeans(data, k=3)
    print(f"  Centroids: {[[round(c, 2) for c in cent] for cent in centroids]}")
    sil = silhouette_score(data, assignments)
    print(f"  Silhouette score: {sil:.4f}")

    print("\n=== Elbow Method ===")
    find_best_k(data, max_k=6)

    print("\n=== DBSCAN on 3 blobs ===")
    db_labels = dbscan(data, eps=1.5, min_samples=5)
    n_clusters = len(set(db_labels) - {-1})
    n_noise = db_labels.count(-1)
    print(f"  Found {n_clusters} clusters, {n_noise} noise points")

    print("\n=== GMM on 3 blobs ===")
    gmm_assignments, gmm_means, gmm_weights, _ = gmm(data, k=3)
    print(f"  Means: {[[round(m, 2) for m in mean] for mean in gmm_means]}")
    print(f"  Weights: {[round(w, 3) for w in gmm_weights]}")
    gmm_sil = silhouette_score(data, gmm_assignments)
    print(f"  Silhouette score: {gmm_sil:.4f}")

    print("\n=== DBSCAN on moons (non-spherical clusters) ===")
    moon_data, moon_labels = make_moons(n_samples=200, noise=0.1)
    moon_db = dbscan(moon_data, eps=0.3, min_samples=5)
    n_moon_clusters = len(set(moon_db) - {-1})
    n_moon_noise = moon_db.count(-1)
    print(f"  Found {n_moon_clusters} clusters, {n_moon_noise} noise points")

    print("\n=== K-Means on moons (will fail to separate) ===")
    moon_km, moon_centroids = kmeans(moon_data, k=2)
    moon_sil = silhouette_score(moon_data, moon_km)
    print(f"  Silhouette score: {moon_sil:.4f}")
    print("  K-Means splits moons poorly because they are not spherical")

    print("\n=== Anomaly detection with DBSCAN ===")
    anomaly_data = list(data)
    anomaly_data.append([20.0, 20.0])
    anomaly_data.append([-5.0, -5.0])
    anomaly_data.append([15.0, 0.0])
    anomaly_labels = dbscan(anomaly_data, eps=1.5, min_samples=5)
    anomalies = [
        anomaly_data[i]
        for i in range(len(anomaly_labels))
        if anomaly_labels[i] == -1
    ]
    print(f"  Detected {len(anomalies)} anomalies")
    for a in anomalies[-3:]:
        print(f"    Point {[round(v, 2) for v in a]}")

کاربرد عملی

در scikit-learn، همین الگوریتم‌ها با یک خط کد پیاده می‌شوند:

from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.mixture import GaussianMixture
from sklearn.metrics import silhouette_score as sklearn_silhouette

km = KMeans(n_clusters=3, random_state=42).fit(data)
db = DBSCAN(eps=1.5, min_samples=5).fit(data)
agg = AgglomerativeClustering(n_clusters=3).fit(data)
gmm_model = GaussianMixture(n_components=3, random_state=42).fit(data)

نسخه‌هایی که از صفر پیاده کردید، دقیقاً نشان می‌دهند این کتابخانه‌ها در باطن چه چیزی را محاسبه می‌کنند. K-Means بین تخصیص و محاسبه‌ی مجدد تکرار می‌شود. DBSCAN خوشه‌ها را از بذرهای متراکم رشد می‌دهد. GMM مدام بین امید ریاضی و بیشینه‌سازی رفت‌وآمد می‌کند. نسخه‌های کتابخانه‌ای قابلیت‌هایی مانند پایداری عددی، مقداردهی اولیه‌ی هوشمندانه‌تر (++K-Means) و شتاب‌دهی با GPU را اضافه می‌کنند، اما منطق اصلی کاملاً یکسان است.

جمع‌بندی و تحویل

این درس پیاده‌سازی‌های کاملی از K-Means، DBSCAN و GMM را از پایه در اختیارتان گذاشت. کدهای این الگوریتم‌های خوشه‌بندی می‌توانند به‌عنوان پایه‌ای برای روش‌های پیشرفته‌تر یادگیری نظارت‌نشده بازاستفاده شوند.

تمرین‌ها

1. مقداردهی اولیه‌ی ++K-Means را پیاده‌سازی کنید: به‌جای انتخاب تصادفی همه‌ی مراکز، مرکز اول را تصادفی انتخاب کنید و هر مرکز بعدی را با احتمالی متناسب با مجذور فاصله‌اش از نزدیک‌ترین مرکز موجود برگزینید. سرعت همگرایی را با مقداردهی تصادفی مقایسه کنید.
2. خوشه‌بندی سلسله‌مراتبی تجمعی را به کد اضافه کنید. پیوند وارد (Ward's linkage) را پیاده‌سازی کرده و دندروگرام بسازید (در قالب لیستی تودرتو از mergeها). آن را در سطوح مختلف برش دهید و نتایج را با K-Means مقایسه کنید.
3. یک پایپ‌لاین ساده برای تشخیص ناهنجاری بسازید: DBSCAN و GMM را روی داده‌های یکسان اجرا کنید و نقاطی را که هر دو روش به‌عنوان داده‌ی پرت شناسایی کرده‌اند علامت بزنید (نویز در DBSCAN و احتمال پایین در GMM). هم‌پوشانی نتایج را بسنجید و موقعیت‌هایی را که دو روش در آن‌ها اختلاف نظر دارند بررسی کنید.

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• Stanford CS229 - Unsupervised Learning - یادداشت‌های کلاسی اندرو ان‌جی درباره‌ی خوشه‌بندی و الگوریتم EM
• scikit-learn Clustering Guide - مقایسه‌ی کاربردی تمام الگوریتم‌های خوشه‌بندی با مثال‌های تصویری
• DBSCAN original paper (Ester et al., 1996) - مقاله‌ای که خوشه‌بندی مبتنی بر چگالی را معرفی کرد