1. Introducción al Clustering Espectral

El clustering espectral es una técnica de agrupamiento basada en la teoría de grafos y el análisis de valores propios (eigenvectors) de la matriz de similitud del dataset. A diferencia de métodos como k‑means, que asumen formas convexas y tamaños similares, el clustering espectral puede capturar estructuras no lineales y clusters de forma arbitraria.

Se compone de tres fases principales:

1. Construcción del grafo de afinidad: se define una matriz de similitud W que conecta puntos similares.
2. Normalización y cálculo del espectro: se forma el Laplaciano del grafo L y se extraen los k eigenvectors más pequeños.
3. Clustering en el espacio espectral: los eigenvectors forman una representación de baja dimensión donde se aplica k‑means u otro algoritmo de partición.

2. Matemáticas Básicas

Sea X = {x_1,…,x_n} el conjunto de datos. La matriz de afinidad W se puede definir mediante:

• Kernel RBF: W_{ij}=exp(-||x_i-x_j||^2 / (2σ^2))
• K‑vecinos más cercanos (k‑NN): W_{ij}=1 si x_j está entre los k vecinos más cercanos de x_i, 0 en otro caso.

El Laplaciano no normalizado se define como L = D - W donde D es la matriz diagonal de grados (D_{ii}=∑_j W_{ij}). La versión normalizada más usada es:

L_{sym}=I - D^{-1/2} W D^{-1/2}

Los k eigenvectors asociados a los menores valores propios de L_{sym} forman la matriz U ∈ ℝ^{n×k}. Cada fila de U se normaliza y luego se agrupa con k‑means.

3. Implementación en Python

Scikit‑learn incluye una implementación robusta y optimizada del clustering espectral. A continuación se muestra un ejemplo completo.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons, make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import SpectralClustering
# 1️⃣ Generar un dataset no lineal (moons)
X, y_true = make_moons(n_samples=500, noise=0.05, random_state=42)
X = StandardScaler().fit_transform(X)
# 2️⃣ Aplicar Spectral Clustering
spectral = SpectralClustering(
    n_clusters=2,
    affinity='rbf',      # kernel RBF
    gamma=1.0,           # parámetro σ de RBF (1/(2σ²))
    assign_labels='kmeans',
    random_state=42
)
y_pred = spectral.fit_predict(X)
# 3️⃣ Visualizar resultados
plt.figure(figsize=(8,4))
plt.subplot(1,2,1)
plt.scatter(X[:,0], X[:,1], c=y_true, cmap='viridis', s=30)
plt.title('Ground truth')
plt.subplot(1,2,2)
plt.scatter(X[:,0], X[:,1], c=y_pred, cmap='viridis', s=30)
plt.title('Spectral Clustering')
plt.tight_layout()
plt.show()

En este caso, el algoritmo reconoce correctamente los dos semicírculos, algo que k‑means no logra.

4. Comparativa con Otros Algoritmos de Clustering

5. Casos de Uso Reales

• Segmentación de imágenes: en visión por computadora, los píxeles se modelan como un grafo y el Laplaciano permite separar objetos con contornos complejos.
• Análisis de redes sociales: detectar comunidades en grafos de amistad o interacción.
• Bioinformática: agrupar genes o proteínas basándose en similitud de expresión o estructura.

En todos estos dominios, el clustering espectral supera a k‑means cuando las fronteras entre grupos son no lineales.

6. Buenas Prácticas y Optimización

6.1 Selección de la Afinidad

Para datasets de alta dimensión, la distancia Euclídea pierde discriminación. Se recomienda:

• Usar affinity='nearest_neighbors' con n_neighbors=10‑15.
• Aplicar reducción de dimensionalidad previa (PCA, TruncatedSVD) para < 100 dimensiones.

6.2 Aproximaciones Escalables

Para n > 10⁵:

1. Utiliza el método Nyström para aproximar el kernel.
2. Emplea sklearn.utils.extmath.randomized_svd para obtener eigenvectors de forma rápida.
3. Considera bibliotecas GPU como cuML (NVIDIA RAPIDS) que implementan Spectral Clustering con cuBLAS.

6.3 Diagnóstico de Problemas Comunes

• Eigenvectors idénticos (valor propio 0 multiplicado): suele indicar que la matriz de afinidad está desconectada. Verifica la conectividad del grafo.
• Clusters vacíos después de k‑means: normaliza cada fila de U antes de aplicar k‑means (scikit‑learn lo hace internamente, pero con datos personalizados hay que hacerlo manualmente).
• Alto consumo de memoria: usa tipos de datos float32 y matrices dispersas (scipy.sparse) para W.

7. Código Avanzado: Spectral Clustering con Matriz Dispersa y Nyström

import numpy as np
import scipy.sparse as sp
from sklearn.metrics.pairwise import rbf_kernel
from sklearn.utils.extmath import randomized_svd
from sklearn.cluster import KMeans
def spectral_nystrom(X, n_clusters=3, n_samples=500, sigma=1.0):
    # 1️⃣ Seleccionamos una muestra aleatoria
    idx = np.random.choice(len(X), n_samples, replace=False)
    X_sample = X[idx]
    # 2️⃣ Calculamos kernel entre muestra y todo el conjunto
    K_mm = rbf_kernel(X_sample, X_sample, gamma=1/(2*sigma**2))
    K_nm = rbf_kernel(X, X_sample, gamma=1/(2*sigma**2))
    # 3️⃣ Aproximamos eigenvectors usando Nyström
    U, S, _ = randomized_svd(K_mm, n_components=n_clusters, n_iter=5)
    # Normalizamos
    U = U / np.sqrt(S)
    # 4️⃣ Proyección de los puntos restantes
    Z = K_nm @ U @ np.linalg.inv(np.diag(S))
    # 5️⃣ k‑means en el espacio proyectado
    labels = KMeans(n_clusters=n_clusters, random_state=42).fit_predict(Z)
    return labels
# Uso con datos de alta dimensión
from sklearn.datasets import make_classification
X, _ = make_classification(n_samples=20000, n_features=200, n_informative=50, random_state=0)
labels = spectral_nystrom(X, n_clusters=4, n_samples=2000, sigma=2.0)
print('Número de clusters encontrados:', len(np.unique(labels)))

Esta función muestra cómo escalar el algoritmo a decenas de miles de muestras sin construir la matriz completa W.