Învățare nesupravegheată

Fără etichete, fără profesor. Algoritmul găsește singur structura.

Tip: Construire Limbaje: Python Cerințe preliminare: Faza 1 (Norme și distanțe, Probabilități și distribuții), Faza 2, lecțiile 1–6 Durată: ~90 de minute

Obiective de învățare

• Implementarea de la zero a K-Means, DBSCAN și a modelelor gaussiene mixte și compararea comportamentului lor de clusterizare
• Evaluarea calității clusterelor folosind scorul silhouette și metoda cotului pentru alegerea unei valori potrivite a lui K
• Explicarea situațiilor în care DBSCAN depășește K-Means și identificarea algoritmilor care tratează clustere nesferice și valori aberante
• Construirea unui flux de detectare a anomaliilor bazat pe metode de clusterizare, care semnalează punctele ce se abat de la tiparele normale

Problema

Fiecare lecție de învățare automată de până acum a presupus existența datelor etichetate: „aceasta este intrarea, iar aceasta este ieșirea corectă”. În lumea reală, etichetele sunt costisitoare. Un spital are milioane de fișe ale pacienților, dar nimeni nu a asociat manual fiecăreia o categorie de boală. Un site de comerț electronic are milioane de sesiuni ale utilizatorilor, dar nimeni nu a etichetat manual segmentele de clienți. O echipă de securitate are jurnale de rețea, însă nimeni nu a semnalat fiecare anomalie.

Învățarea nesupravegheată caută tipare fără să i se spună în prealabil ce anume să găsească. Ea grupează puncte de date similare, descoperă structuri ascunse și scoate la iveală posibile anomalii. Dacă învățarea supravegheată seamănă cu studiul dintr-un manual care include răspunsurile, învățarea nesupravegheată seamănă cu examinarea datelor brute până când tiparele încep să se contureze.

Dificultatea este că, fără etichete, nu puteți măsura direct dacă rezultatul este „corect” sau „greșit”. Aveți nevoie de alte instrumente pentru a evalua dacă structura găsită de algoritm este semnificativă.

Notă tehnică a traducerii: algoritmii nesupravegheați găsesc structură în raport cu reprezentarea, metrica și ipotezele alese; ei nu garantează că acea structură corespunde unor categorii reale sau utile. Scorurile interne trebuie completate, când este posibil, cu stabilitatea rezultatelor, cunoașterea domeniului și validare externă.

Conceptul

Clusterizarea: gruparea elementelor similare

Clusterizarea atribuie fiecare punct de date unui grup, numit cluster, astfel încât punctele din același grup să fie mai asemănătoare între ele decât cu punctele din alte grupuri. Întrebarea este întotdeauna: ce înseamnă „asemănător”?

K-Means: algoritmul de bază

K-Means împarte datele în exact K clustere. Fiecare cluster are un centroid, adică media punctelor sale, iar fiecare punct este atribuit celui mai apropiat centroid.

Algoritmul lui Lloyd:

1. Alegeți K puncte aleatoare drept centroizi inițiali.
2. Atribuiți fiecare punct de date celui mai apropiat centroid.
3. Recalculați fiecare centroid ca medie a punctelor care i-au fost atribuite.
4. Repetați pașii 2–3 până când atribuirile nu se mai schimbă sau deplasarea centroizilor scade sub o toleranță.

Funcția-obiectiv, numită inerție, măsoară suma distanțelor pătratice dintre fiecare punct și centroidul căruia i-a fost atribuit. K-Means minimizează această cantitate, dar găsește în general numai un minim local. Inițializări diferite pot produce rezultate diferite.

Alegerea lui K

Două metode uzuale sunt:

Metoda cotului: rulați K-Means pentru K = 1, 2, 3, …, n. Reprezentați inerția în funcție de K. Căutați „cotul”, adică punctul după care adăugarea de clustere reduce mult mai puțin inerția.

Scorul silhouette: pentru fiecare punct, măsurați cât de apropiat este de propriul cluster (a), comparativ cu cel mai apropiat alt cluster (b). Coeficientul silhouette este (b - a) / max(a, b) și variază între -1, asociat de regulă unei atribuiri nepotrivite, și +1, asociat unei separări bune. Media pe toate punctele oferă un scor global.

Notă tehnică a traducerii: metoda cotului nu produce întotdeauna un cot clar, iar valoarea K care maximizează scorul silhouette nu este neapărat numărul „adevărat” sau cel mai util de clustere. Scorul favorizează separări compacte și bine distanțate și poate evalua slab structuri neregulate. Folosiți aceste metode ca diagnostice, nu ca oracole.

DBSCAN: clusterizare bazată pe densitate

K-Means favorizează clustere compacte, aproximativ sferice, și vă cere să alegeți K în avans. DBSCAN nu impune niciuna dintre aceste două condiții. El găsește clustere ca regiuni dense separate de regiuni rare.

Doi parametri:

• eps: raza unei vecinătăți;
• min_samples: numărul minim de puncte necesar pentru a forma o regiune densă.

Trei tipuri de puncte:

• Punct nucleu: are cel puțin min_samples puncte, inclusiv pe sine, la o distanță de cel mult eps.
• Punct de frontieră: se află la cel mult eps de un punct nucleu, dar nu este el însuși un punct nucleu.
• Punct de zgomot: nu este nici punct nucleu, nici punct de frontieră. DBSCAN nu îl atribuie niciunui cluster.

DBSCAN unește în același cluster punctele nucleu conectate prin vecinătăți de rază eps. Punctele de frontieră se alătură clusterului unui punct nucleu apropiat. Punctele de zgomot nu aparțin niciunui cluster.

Puncte forte: găsește clustere cu forme neregulate, determină numărul lor din structura de densitate și semnalează punctele de zgomot. Punct slab: tratează dificil clusterele cu densități foarte diferite.

Notă tehnică a traducerii: eticheta de zgomot nu transformă un punct în anomalie „prin definiție”; rezultatul depinde puternic de eps, min_samples, scară și metrică. Un punct de frontieră aflat în vecinătatea mai multor clustere poate fi atribuit în funcție de ordinea parcurgerii, fără să schimbe punctele nucleu. Consultați documentația oficială DBSCAN.

Clusterizarea ierarhică

Construiește un arbore, numit dendrogramă, de clustere imbricate.

Varianta aglomerativă, de jos în sus:

1. Începeți cu fiecare punct în propriul cluster.
2. Uniți cele mai apropiate două clustere.
3. Repetați până când rămâne un singur cluster.
4. Tăiați dendrograma la nivelul dorit pentru a obține K clustere.

„Apropierea” dintre clustere poate fi măsurată astfel:

• Legătură simplă: distanța minimă dintre oricare două puncte din cele două clustere.
• Legătură completă: distanța maximă dintre oricare două puncte.
• Legătură medie: distanța medie dintre toate perechile.
• Metoda Ward: unirea care produce cea mai mică creștere a varianței totale din interiorul clusterelor.

Notă tehnică a traducerii: criteriul Ward este legat de distanța euclidiană pătratică și de minimizarea creșterii sumei pătratelor din interiorul clusterelor; nu este compatibil în mod arbitrar cu orice metrică. Costul O(n^2) de memorie este caracteristic multor implementări aglomerative dense, dar poate varia cu structura și implementarea.

Modele gaussiene mixte (GMM)

K-Means produce atribuiri ferme: fiecare punct aparține exact unui cluster. GMM produce atribuiri probabilistice: fiecare punct are o probabilitate a posteriori de apartenență la fiecare componentă.

GMM presupune că datele sunt generate dintr-un amestec de K distribuții gaussiene, fiecare cu propria medie și covarianță. Algoritmul Expectation-Maximization (EM) alternează între:

• Pasul E: calculați probabilitatea a posteriori ca fiecare punct să provină din fiecare distribuție gaussiană.
• Pasul M: actualizați media, covarianța și ponderea de amestec ale fiecărei distribuții pentru a maximiza verosimilitatea datelor în raport cu responsabilitățile curente.

Cu matrici de covarianță complete, GMM poate modela clustere eliptice, nu doar clustere aproximativ sferice precum K-Means, și tratează în mod natural suprapunerea probabilistică dintre componente.

Notă tehnică a traducerii: EM crește sau menține verosimilitatea la fiecare iterație în condițiile standard, dar poate converge la un optim local ori la o soluție degenerată; inițializarea și regularizarea covarianței contează. Componentele unui amestec nu sunt automat echivalente cu „clustere reale”, iar etichetele lor pot fi permutate fără a schimba modelul.

Ce metodă să folosiți

Metodă	Potrivită pentru	Evitați-o când
K-Means	Seturi mari, clustere compacte cu varianțe similare, K cunoscut	Forme neregulate, valori aberante puternice
DBSCAN	K necunoscut, forme neregulate, semnalarea punctelor de zgomot	Densități foarte diferite, dimensiuni foarte multe fără o metrică adecvată
Ierarhică	Seturi mici sau medii, dendrogramă necesară, explorarea mai multor niveluri	Seturi foarte mari în implementări cu memorie O(n^2)
GMM	Clustere suprapuse, atribuiri probabilistice necesare	Seturi foarte mari sau multe dimensiuni fără regularizare și structură de covarianță potrivită

Notă tehnică a traducerii: toate aceste metode sunt sensibile la reprezentarea și scara caracteristicilor. În dimensiuni foarte multe, distanțele pot deveni mai puțin informative, iar o reducere de dimensionalitate sau o metrică adaptată domeniului poate fi necesară.

Detectarea anomaliilor prin clusterizare

Clusterizarea poate susține detectarea anomaliilor:

• K-Means: punctele aflate foarte departe de orice centroid pot fi candidate la anomalie.
• DBSCAN: punctele etichetate drept zgomot pot fi candidate la anomalie.
• GMM: punctele cu densitate foarte mică sub întregul amestec pot fi candidate la anomalie.

În toate cazurile este necesar un prag sau un criteriu operațional, calibrat pentru costul erorilor din aplicație.

kmeans-step

Construiți

Pasul 1: K-Means de la zero

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

Pasul 2: metoda cotului și scorul silhouette

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

Pasul 3: DBSCAN de la zero

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

Pasul 4: model gaussian mixt (algoritmul 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

Pasul 5: generați date de test și rulați totul

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]}")

Notă tehnică a traducerii: implementările sunt didactice și au câteva limitări. La convergență, funcția kmeans întrerupe bucla înainte de a atribui new_centroids variabilei centroids, astfel încât poate returna centroizii iterației precedente; dacă se atinge limita de iterații, atribuirile și centroizii pot proveni din pași succesivi diferiți. Implementarea DBSCAN caută liniar toți vecinii și are cost pătratic. Implementarea GMM folosește câte o singură varianță scalară izotropă pentru fiecare componentă, deci nu poate modela clustere eliptice orientate; responsabilitățile returnate nu sunt recalculate după ultima actualizare M, iar plafonarea exponentului poate distorsiona probabilitățile extrem de mici. Aceste diferențe nu trebuie confundate cu algoritmii compleți din biblioteci.

Folosiți

Cu scikit-learn, aceiași algoritmi se exprimă într-o singură instrucțiune fiecare:

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)

Versiunile construite de la zero vă arată exact logica de bază. K-Means alternează atribuirea punctelor și recalcularea centroizilor. DBSCAN extinde clusterele pornind din nuclee dense. GMM alternează pașii de estimare și maximizare. Versiunile din bibliotecă adaugă stabilitate numerică, inițializări mai bune, precum K-Means++, structuri de date și implementări CPU optimizate.

Notă tehnică a traducerii: scikit-learn nu oferă automat accelerare GPU pentru implementările K-Means, DBSCAN, AgglomerativeClustering și GaussianMixture prezentate aici. Proiectul are suport experimental Array API pentru o listă limitată și în creștere de estimatori, dar documentația precizează că algoritmi precum K-Means sunt implementați în Cython și nu beneficiază în prezent de această cale eficientă. Consultați FAQ-ul oficial despre GPU.

Livrați

Această lecție produce implementări funcționale, cu scop didactic, pentru K-Means, DBSCAN și GMM de la zero. Codul de clusterizare poate fi reutilizat drept bază pentru metode nesupravegheate mai avansate, după tratarea limitărilor tehnice menționate.

Exerciții

1. Implementați inițializarea K-Means++: în loc să alegeți centroizii aleatoriu, alegeți-l aleatoriu pe primul, apoi alegeți fiecare centroid următor cu o probabilitate proporțională cu pătratul distanței sale față de cel mai apropiat centroid existent. Comparați viteza de convergență cu inițializarea aleatoare.
2. Adăugați în cod clusterizarea ierarhică aglomerativă. Implementați criteriul Ward și produceți o dendrogramă, reprezentată ca o listă imbricată de uniri. Tăiați-o la niveluri diferite și comparați rezultatele cu K-Means.
3. Construiți un flux simplu de detectare a anomaliilor: rulați DBSCAN și GMM pe aceleași date, apoi semnalați punctele pe care ambele metode le consideră candidate la anomalie — zgomot în DBSCAN și densitate mică în GMM. Măsurați suprapunerea și discutați situațiile în care metodele nu sunt de acord.

Termeni-cheie

Termen	Cum i se spune	Ce înseamnă de fapt
Clusterizare	„Gruparea elementelor similare”	Împărțirea datelor în submulțimi în care similaritatea internă depășește similaritatea dintre grupuri, conform unei metrici precise
Centroid	„Centrul unui cluster”	Media tuturor punctelor atribuite unui cluster; este folosită de K-Means ca reprezentant al clusterului
Inerție	„Cât de compacte sunt clusterele”	Suma distanțelor pătratice dintre fiecare punct și centroidul atribuit; o valoare mai mică indică o ajustare mai compactă pentru același K
Scor silhouette	„Cât de bine sunt separate clusterele”	Pentru fiecare punct, (b - a) / max(a, b), unde a este distanța medie în interiorul clusterului, iar b este distanța medie față de cel mai apropiat alt cluster
Punct nucleu	„Un punct dintr-o regiune densă”	În DBSCAN, un punct cu cel puțin min_samples puncte, inclusiv el însuși, la o distanță de cel mult eps
Algoritmul EM	„K-Means probabilistic”	Expectation-Maximization: calculează iterativ responsabilitățile de apartenență în pasul E și actualizează parametrii distribuțiilor în pasul M
Dendrogramă	„Un arbore de clustere”	O diagramă arborescentă care arată ordinea și distanța la care au fost unite clusterele în clusterizarea ierarhică
Anomalie	„O valoare aberantă”	Un punct care nu corespunde tiparului operațional așteptat; poate fi semnalat drept zgomot de DBSCAN sau prin densitate mică într-un GMM

Lecturi suplimentare

• Stanford CS229 — Unsupervised Learning — notele de curs ale lui Andrew Ng despre clusterizare și EM
• Ghidul scikit-learn despre clusterizare — comparație practică a algoritmilor de clusterizare, cu exemple vizuale
• Lucrarea originală DBSCAN (Ester et al., 1996) — lucrarea care a introdus clusterizarea bazată pe densitate

---

Sursă: Unsupervised Learning — original

Navigare: înapoi: 02.06 — Cei mai apropiați k vecini și distanțe · Faza 2 — Bazele învățării automate · Catalog complet · în continuare: 02.08 — Ingineria și selecția caracteristicilor.