Phase 02 - Lesson 07

Aprendizagem não supervisionada

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

Sem rótulos, sem professor. O algoritmo encontra a estrutura por conta própria.

Tipo: Construir Idiomas: Python Pré-requisitos: Fase 1 (Normas e Distâncias, Probabilidade e Distribuições), Fase 2 Lições 1-6 Tempo: ~90 minutos

Objetivos de aprendizagem

• Implementar modelos de mistura K-Means, DBSCAN e Gaussiana do zero e comparar seu comportamento de agrupamento
• Avalie a qualidade do cluster usando a pontuação da silhueta e o método do cotovelo para selecionar o K ideal
• Explique quando DBSCAN supera K-Means e identifique qual algoritmo lida com clusters não esféricos e outliers
• Construir um pipeline de detecção de anomalias usando métodos de cluster para sinalizar pontos que se desviam dos padrões normais

O problema

Todas as lições de ML até agora assumiram dados rotulados: "aqui está uma entrada, aqui está a saída correta". No mundo real, os rótulos são caros. Um hospital tem milhões de registros de pacientes, mas ninguém marcou manualmente cada um deles com uma categoria de doença. Um site de comércio eletrônico tem milhões de sessões de usuários, mas ninguém identifica segmentos de clientes manualmente. Uma equipe de segurança possui registros de rede, mas ninguém sinalizou todas as anomalias.

A aprendizagem não supervisionada encontra padrões sem que lhe seja dito o que procurar. Ele agrupa pontos de dados semelhantes, descobre estruturas ocultas e revela anomalias. Se a aprendizagem supervisionada é aprender com um livro didático com um gabarito, a aprendizagem não supervisionada é olhar para dados brutos até que os padrões se revelem.

O problema: sem rótulos, você não pode medir diretamente o “certo” ou o “errado”. Você precisa de ferramentas diferentes para avaliar se a estrutura encontrada pelo seu algoritmo é significativa.

O Conceito

Clustering: agrupando coisas semelhantes

O clustering atribui cada ponto de dados a um grupo (cluster) para que os pontos dentro do mesmo grupo sejam mais semelhantes entre si do que com pontos em outros grupos. A questão é sempre: o que significa “semelhante”?

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: O burro de carga

K-Means particiona dados em exatamente K clusters. Cada cluster possui um centróide (seu centro de massa) e cada ponto pertence ao centróide mais próximo.

Algoritmo de Lloyd:

1. Escolha K pontos aleatórios como centróides iniciais
2. Atribua cada ponto de dados ao centróide mais próximo
3. Recalcular cada centróide como a média dos pontos atribuídos
4. Repita as etapas 2 a 3 até que as atribuições parem de mudar

A função objetivo (inércia) mede a distância quadrada total de cada ponto ao centróide atribuído. K-Means minimiza isso, mas encontra apenas um mínimo local. Inicializações diferentes podem fornecer resultados diferentes.

Escolhendo K

Dois métodos padrão:

Método do cotovelo: Execute K-Means para K = 1, 2, 3, ..., n. Plote a inércia versus K. Procure o "cotovelo" onde adicionar mais clusters para de reduzir significativamente a inércia.

Pontuação da silhueta: Para cada ponto, meça o quão semelhante ele é ao seu próprio cluster (a) em relação ao outro cluster mais próximo (b). O coeficiente de silhueta é (b - a) / max(a, b), variando de -1 (cluster errado) a +1 (cluster bem agrupado). Média de todos os pontos para uma pontuação global.

DBSCAN: Clustering baseado em densidade

K-Means assume que os clusters são esféricos e exige que você escolha K antecipadamente. DBSCAN não faz nenhuma suposição. Ele encontra clusters como regiões densas separadas por regiões esparsas.

Dois parâmetros:

• eps: o raio de uma vizinhança
• min_samples: o número mínimo de pontos necessários para formar uma região densa

Três tipos de pontos:

• Ponto central: tem pelo menos pontos min_samples dentro da distância eps
• Ponto de fronteira: dentro do eps de um ponto central, mas não em si um ponto central
• Ponto de ruído: nem núcleo nem borda. Estes são valores discrepantes.

DBSCAN conecta pontos centrais que estão dentro de eps um do outro no mesmo cluster. Os pontos fronteiriços unem-se ao cluster de um ponto central próximo. Os pontos de ruído não pertencem a nenhum cluster.

Pontos fortes: encontra clusters de qualquer formato, determina automaticamente o número de clusters, identifica valores discrepantes. Fraqueza: luta com clusters de densidades variadas.

Clustering Hierárquico

Constrói uma árvore (dendrograma) de clusters aninhados.

Aglomerativo (de baixo para cima):

1. Comece com cada ponto como seu próprio cluster
2. Mesclar os dois clusters mais próximos
3. Repita até restar apenas um cluster
4. Corte o dendograma no nível desejado para obter K clusters

A "proximidade" entre clusters pode ser medida como:

• Ligação única: distância mínima entre quaisquer dois pontos nos dois clusters
• Ligação completa: distância máxima entre quaisquer dois pontos
• Linkage médio: distância média entre todos os pares
• Método de Ward: a mesclagem que causa o menor aumento na variação total dentro do cluster

Modelos de Mistura Gaussiana (GMM)

K-Means fornece atribuições difíceis: cada ponto pertence a exatamente um cluster. O GMM fornece atribuições suaves: cada ponto tem uma probabilidade de pertencer a cada cluster.

O GMM assume que os dados são gerados a partir de uma mistura de distribuições K Gaussianas, cada uma com sua própria média e covariância. O algoritmo Expectation-Maximization (EM) alterna entre:

• E-step: calcula a probabilidade de cada ponto pertencer a cada Gaussiana
• M-step: atualize a média, a covariância e o peso de mistura de cada gaussiana para maximizar a probabilidade dos dados

O GMM pode modelar clusters elípticos (não apenas esféricos como K-Means) e lida naturalmente com clusters sobrepostos.

Quando usar qual

Detecção de anomalias com cluster

O clustering suporta naturalmente a detecção de anomalias:

• K-Means: pontos distantes de qualquer centróide são anomalias
• DBSCAN: pontos de ruído são anomalias por definição
• GMM: pontos com baixa probabilidade sob todas as Gaussianas são anomalias

Construa

Etapa 1: K-Means do 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

Etapa 2: método do cotovelo e pontuação da silhueta

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

Etapa 3: DBSCAN do 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

Etapa 4: Modelo de mistura 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

Etapa 5: Gere dados de teste e execute tudo

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

Use-o

Com scikit-learn, os mesmos algoritmos são de uma linha:

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)

As versões originais mostram exatamente o que essas bibliotecas calculam. K-Means itera entre atribuir e recalcular. DBSCAN cresce cachos a partir de sementes densas. O GMM alterna entre expectativa e maximização. As versões da biblioteca adicionam estabilidade numérica, inicialização mais inteligente (K-Means++) e aceleração de GPU, mas a lógica central é a mesma.

Envie

Esta lição produz implementações funcionais de K-Means, DBSCAN e GMM do zero. O código de clustering pode ser reutilizado como base para métodos não supervisionados mais avançados.

Exercícios

1. Implemente a inicialização K-Means++: em vez de escolher centróides aleatórios, escolha o primeiro aleatoriamente e cada centróide subsequente com probabilidade proporcional à sua distância quadrada do centróide existente mais próximo. Compare a velocidade de convergência com a inicialização aleatória.
2. Adicione clustering aglomerativo hierárquico ao código. Implemente a ligação de Ward e produza um dendograma (como uma lista aninhada de mesclagens). Corte em diferentes níveis e compare com os resultados de K-Means.
3. Construa um pipeline simples de detecção de anomalias: execute DBSCAN e GMM nos mesmos dados, sinalize pontos que ambos os métodos concordam ser discrepantes (ruído em DBSCAN, baixa probabilidade em GMM). Meça a sobreposição e discuta quando os métodos discordam.

Termos-chave

Leitura Adicional

• Stanford CS229 - Aprendizagem não supervisionada - Notas de aula de Andrew Ng sobre clustering e EM
• scikit-learn Guia de Clustering - comparação prática de todos os algoritmos de clustering com exemplos visuais
• DBSCAN artigo original (Ester et al., 1996) - o artigo que introduziu o agrupamento baseado em densidade