Phase 02 - Lesson 07

Aprendizaje no supervisado

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Sin etiquetas, sin profesor. El algoritmo encuentra la estructura por sí solo.

Tipo: Construcción Idiomas: Python Requisitos previos: Fase 1 (Normas y distancias, probabilidad y distribuciones), Fase 2, Lecciones 1-6 Tiempo: ~90 minutos

Objetivos de aprendizaje

• Implementar los modelos K-Means, DBSCAN y de mezcla gaussiana desde cero y comparar su comportamiento de agrupación
• Evaluar la calidad del racimo utilizando la puntuación de la silueta y el método del codo para seleccionar el K óptimo
• Explicar cuándo DBSCAN supera a K-Means e identificar qué algoritmo maneja grupos no esféricos y valores atípicos
• Construir un canal de detección de anomalías utilizando métodos de agrupación para marcar puntos que se desvían de los patrones normales.

El problema

Hasta ahora, todas las lecciones de ML han asumido datos etiquetados: "aquí hay una entrada, aquí está la salida correcta". En el mundo real, las etiquetas son caras. Un hospital tiene millones de registros de pacientes, pero nadie ha etiquetado manualmente cada uno con una categoría de enfermedad. Un sitio de comercio electrónico tiene millones de sesiones de usuarios, pero nadie tiene segmentos de clientes etiquetados manualmente. Un equipo de seguridad tiene registros de red, pero nadie ha detectado todas las anomalías.

El aprendizaje no supervisado encuentra patrones sin que le digan qué buscar. Agrupa puntos de datos similares, descubre estructuras ocultas y muestra anomalías. Si el aprendizaje supervisado consiste en aprender de un libro de texto con una clave de respuestas, el aprendizaje no supervisado consiste en observar datos sin procesar hasta que los patrones se revelan por sí solos.

El problema: sin etiquetas, no se puede medir directamente lo "correcto" o lo "incorrecto". Necesita diferentes herramientas para evaluar si la estructura que encontró su algoritmo es significativa.

El concepto

Agrupación: agrupar cosas similares

La agrupación asigna cada punto de datos a un grupo (clúster) de modo que los puntos dentro del mismo grupo sean más similares entre sí que los puntos de otros grupos. La pregunta siempre es: ¿qué significa "similar"?

flowchart LR
    A[Raw Data] --> B{Choose Method}
    B --> C[K-Means]
    B --> D[DBSCAN]
    B --> E[Hierarchical]
    B --> F[GMM]
    C --> G[Flat, spherical clusters]
    D --> H[Arbitrary shapes, noise detection]
    E --> I[Tree of nested clusters]
    F --> J[Soft assignments, elliptical clusters]

K-Means: El caballo de batalla

K-Means divide los datos en exactamente K grupos. Cada grupo tiene un centroide (su centro de masa) y cada punto pertenece al centroide más cercano.

Algoritmo de Lloyd:

1. Elija K puntos aleatorios como centroides iniciales
2. Asigne cada punto de datos al centroide más cercano.
3. Vuelva a calcular cada centroide como la media de sus puntos asignados.
4. Repita los pasos 2 y 3 hasta que las asignaciones dejen de cambiar.

La función objetivo (inercia) mide la distancia total al cuadrado desde cada punto hasta su centroide asignado. K-Means minimiza esto, pero solo encuentra un mínimo local. Diferentes inicializaciones pueden dar resultados diferentes.

Eligiendo K

Dos métodos estándar:

Método del codo: Ejecute K-Means para K = 1, 2, 3, ..., n. Trazar la inercia frente a K. Busque el "codo" donde agregar más grupos deja de reducir significativamente la inercia.

Puntuación de silueta: Para cada punto, mida qué tan similar es a su propio grupo (a) versus el otro grupo más cercano (b). El coeficiente de silueta es (b - a) / max(a, b), y oscila entre -1 (grupo incorrecto) y +1 (bien agrupado). Promedio de todos los puntos para obtener una puntuación global.

DBSCAN: Agrupación basada en densidad

K-Means asume que los grupos son esféricos y requiere que elijas K por adelantado. DBSCAN no hace ninguna suposición. Encuentra grupos como regiones densas separadas por regiones dispersas.

Dos parámetros:

• eps: el radio de un barrio
• min_samples: el número mínimo de puntos necesarios para formar una región densa

Tres tipos de puntos:

• Punto central: tiene al menos puntos min_samples dentro de una distancia de eps
• Punto fronterizo: dentro de los eps de un punto central, pero no es un punto central en sí mismo.
• Punto de ruido: ni núcleo ni frontera. Estos son valores atípicos.

DBSCAN conecta puntos centrales que están dentro de eps entre sí en el mismo grupo. Los puntos fronterizos se unen al grupo de un punto central cercano. Los puntos de ruido no pertenecen a ningún grupo.

Puntos fuertes: encuentra grupos de cualquier forma, determina automáticamente el número de grupos, identifica valores atípicos. Debilidad: lucha con grupos de diferentes densidades.

Agrupación jerárquica

Construye un árbol (dendrograma) de clústeres anidados.

Aglomerativo (de abajo hacia arriba):

1. Comience con cada punto como su propio grupo.
2. Fusionar los dos grupos más cercanos
3. Repita hasta que solo quede un grupo.
4. Corte el dendrograma al nivel deseado para obtener K grupos.

La "cercanía" entre grupos se puede medir como:

• Enlace único: distancia mínima entre dos puntos cualesquiera en los dos grupos
• Enlace completo: distancia máxima entre dos puntos cualesquiera
• Vínculo promedio: distancia promedio entre todos los pares
• Método de Ward: la fusión que provoca el menor aumento en la variación total dentro del clúster

Modelos de mezcla gaussiana (GMM)

K-Means ofrece tareas difíciles: cada punto pertenece exactamente a un grupo. GMM ofrece asignaciones suaves: cada punto tiene una probabilidad de pertenecer a cada grupo.

GMM supone que los datos se generan a partir de una mezcla de distribuciones K Gaussianas, cada una con su propia media y covarianza. El algoritmo de Maximización de Expectativas (EM) alterna entre:

• E-step: calcula la probabilidad de que cada punto pertenezca a cada gaussiano
• Paso M: actualiza la media, la covarianza y el peso de mezcla de cada gaussiano para maximizar la probabilidad de los datos.

GMM puede modelar grupos elípticos (no solo esféricos como K-Means) y, naturalmente, maneja grupos superpuestos.

Cuándo usar cuál

Detección de anomalías con agrupación

La agrupación en clústeres admite naturalmente la detección de anomalías:

• K-Means: los puntos alejados de cualquier centroide son anomalías
• DBSCAN: los puntos de ruido son anomalías por definición
• GMM: los puntos con baja probabilidad bajo todos los gaussianos son anomalías

Constrúyelo

Paso 1: K-Means desde cero

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

Paso 2: método del codo y puntuación de la silueta

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

Paso 3: DBSCAN desde cero

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

Paso 4: Modelo de mezcla gaussiana (algoritmo 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

Paso 5: generar datos de prueba y ejecutar todo

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

Úsalo

Con scikit-learn, los mismos algoritmos son de una sola línea:

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)

Las versiones desde cero le muestran exactamente lo que calculan estas bibliotecas. K-Means itera entre asignar y recalcular. DBSCAN produce racimos a partir de semillas densas. GMM alterna entre expectativa y maximización. Las versiones de la biblioteca agregan estabilidad numérica, inicialización más inteligente (K-Means++) y aceleración de GPU, pero la lógica central es la misma.

Envíalo

Esta lección produce implementaciones funcionales de K-Means, DBSCAN y GMM desde cero. El código de agrupación se puede reutilizar como base para métodos no supervisados ​​más avanzados.

Ejercicios

1. Implementar la inicialización K-Means++: en lugar de seleccionar centroides aleatorios, elija el primero al azar y cada centroide subsiguiente con una probabilidad proporcional a su distancia al cuadrado desde el centroide existente más cercano. Compare la velocidad de convergencia con la inicialización aleatoria.
2. Agregue agrupación aglomerativa jerárquica al código. Implemente el enlace de Ward y produzca un dendrograma (como una lista anidada de fusiones). Córtelo en diferentes niveles y compárelo con los resultados de K-Means.
3. Cree un canal de detección de anomalías simple: ejecute DBSCAN y GMM con los mismos datos, marque los puntos que ambos métodos coinciden en que son valores atípicos (ruido en DBSCAN, baja probabilidad en GMM). Mida la superposición y discuta cuando los métodos no estén de acuerdo.

Términos clave

Lectura adicional

• Stanford CS229 - Aprendizaje no supervisado - Notas de la conferencia de Andrew Ng sobre agrupación y EM
• scikit-learn Guía de agrupación: comparación práctica de todos los algoritmos de agrupación con ejemplos visuales
• DBSCAN artículo original (Ester et al., 1996) - el artículo que introdujo la agrupación basada en densidad