68  K-Means y K-Medoids

K-Means es el algoritmo de clustering más ampliamente usado en la práctica. Su popularidad se debe a su simplicidad conceptual, su eficiencia computacional y la facilidad de interpretar sus resultados: cada grupo queda representado por un centroide, que es el punto promedio de las observaciones asignadas (MacQueen 1967; Lloyd 1982).

El algoritmo alterna entre dos pasos: asignar cada punto al centroide más cercano, y actualizar los centroides como el promedio de los puntos asignados. Estos dos pasos se repiten hasta que las asignaciones no cambian. A pesar de su elegancia, K-Means tiene limitaciones importantes: converge a óptimos locales, asume que los grupos son convexos y similares en tamaño, y es sensible a valores atípicos y a la escala de las variables.

Este capítulo desarrolla el algoritmo K-Means, su análisis teórico, la inicialización inteligente K-Means++, el método del codo para elegir \(k\), y el algoritmo K-Medoids, que es más robusto a outliers.

1 El objetivo de K-Means

K-Means busca una partición de \(n\) observaciones en \(k\) grupos \(C_1,\dots,C_k\) que minimice la suma de cuadrados intra-grupo, también llamada WCSS (within-cluster sum of squares).

Definición. El objetivo de K-Means es minimizar \[ J(C_1,\dots,C_k) = \sum_{j=1}^{k}\sum_{\mathbf{x}\in C_j}\|\mathbf{x}-\boldsymbol{\mu}_j\|^2, \tag{1}\] donde \(\boldsymbol{\mu}_j = \frac{1}{|C_j|}\sum_{\mathbf{x}\in C_j}\mathbf{x}\) es el centroide del grupo \(j\).

Minimizar \(J\) sobre todas las particiones posibles es un problema NP-complejo cuando \(k\) y \(p\) son arbitrarios. El algoritmo de Lloyd encuentra un mínimo local mediante dos pasos de coordinación alternada.

2 Algoritmo de Lloyd

Algoritmo K-Means (Lloyd).

Entrada: observaciones \(\mathbf{x}_1,\dots,\mathbf{x}_n\), número de grupos \(k\).

1. Inicializar \(k\) centroides \(\boldsymbol{\mu}_1,\dots,\boldsymbol{\mu}_k\) (por ejemplo, eligiendo \(k\) observaciones al azar).
2. Asignación. Para cada \(i\), asignar \(\ell(i) = \arg\min_j \|\mathbf{x}_i-\boldsymbol{\mu}_j\|^2\).
3. Actualización. Para cada \(j\), actualizar \(\boldsymbol{\mu}_j = \frac{1}{|C_j|}\sum_{\ell(i)=j}\mathbf{x}_i\).
4. Repetir los pasos 2 y 3 hasta que las asignaciones no cambien.

Salida: asignación \(\ell\) y centroides finales \(\boldsymbol{\mu}_1,\dots,\boldsymbol{\mu}_k\).

Cada iteración del algoritmo reduce o mantiene \(J\), y como el número de particiones posibles es finito, el algoritmo converge en un número finito de iteraciones. Sin embargo, no se garantiza convergencia al mínimo global.

2.1 Complejidad computacional

El paso de asignación requiere \(O(nk)\) cálculos de distancia por iteración. El paso de actualización requiere \(O(n)\). En la práctica, K-Means converge en pocas iteraciones relativas a \(n\). Para datos en alta dimensión o \(k\) grande, existen variantes más eficientes basadas en estructuras de árbol o aproximaciones.

3 Inicialización K-Means++

La solución encontrada por K-Means depende fuertemente de la inicialización. Una inicialización aleatoria puede dar lugar a centroides iniciales mal distribuidos, lo que lleva a soluciones de baja calidad. K-Means++ (Arthur y Vassilvitskii 2007) proporciona una inicialización probabilística que garantiza una solución esperada dentro de un factor logarítmico del óptimo global.

Algoritmo K-Means++.

1. Elegir el primer centroide \(\boldsymbol{\mu}_1\) uniformemente al azar entre \(\mathbf{x}_1,\dots,\mathbf{x}_n\).
2. Para \(j=2,\dots,k\):
   • Para cada punto \(\mathbf{x}_i\), calcular \(D(\mathbf{x}_i)=\min_{l<j}\|\mathbf{x}_i-\boldsymbol{\mu}_l\|^2\).
   • Elegir \(\boldsymbol{\mu}_j=\mathbf{x}_i\) con probabilidad proporcional a \(D(\mathbf{x}_i)\).
3. Continuar con el algoritmo de Lloyd estándar.

La idea es que los centroides iniciales estén bien distribuidos: cada centroide nuevo se elige con mayor probabilidad en zonas alejadas de los centroides ya elegidos. scikit-learn usa K-Means++ por defecto.

K-Means — animación paso a paso
Observa cómo los centroides se mueven y los grupos cambian en cada iteración

k = 3

4 Limitaciones de K-Means

K-Means tiene varios supuestos implícitos que, cuando no se cumplen, producen clustering de baja calidad:

Grupos convexos y esféricos. K-Means minimiza distancias Euclídeas, lo que favorece grupos circulares en 2D o elipsoidales alineados con los ejes en alta dimensión. Grupos con formas no convexas —anillos, medias lunas, espirales— no pueden segmentarse correctamente.

Grupos de tamaño similar. El centroide de un grupo pequeño puede ser “absorbido” por un grupo grande. Esto puede mitigarse con K-Medoids o con restricciones de tamaño.

Sensibilidad a outliers. El centroide es la media, que puede desplazarse considerablemente ante un solo punto extremo. K-Medoids es más robusto porque usa medianas en vez de medias.

Número de grupos fijo. K-Means requiere especificar \(k\) de antemano. La elección adecuada de \(k\) es un problema abierto que se aborda con heurísticas como el método del codo.

5 Método del codo

Una heurística clásica para elegir \(k\) es graficar el WCSS en función de \(k\) y buscar un codo: el punto donde la reducción marginal de WCSS disminuye al agregar otro grupo.

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
import numpy as np

X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.7, random_state=7)

wcss = []
for k in range(1, 11):
    km = KMeans(n_clusters=k, random_state=0, n_init=10)
    km.fit(X)
    wcss.append(km.inertia_)

for k, w in enumerate(wcss, 1):
    print(f"k={k:2d}  WCSS={w:10.2f}")

k= 1  WCSS=  21990.36
k= 2  WCSS=   8805.13
k= 3  WCSS=   2236.26
k= 4  WCSS=    279.94
k= 5  WCSS=    250.42
k= 6  WCSS=    223.32
k= 7  WCSS=    197.53
k= 8  WCSS=    171.05
k= 9  WCSS=    154.82
k=10  WCSS=    140.95

Método del codo y silueta — selección de k
Haz clic en un k para ver el clustering y sus métricas

6 K-Medoids (PAM)

K-Medoids es una variante de K-Means que, en vez de representar cada grupo por su media, lo representa por una observación real llamada medoide (Kaufman y Rousseeuw 1990). Esto lo hace más robusto a outliers, porque los medoides son puntos del conjunto de datos y no pueden ser arrastrados por valores extremos.

Definición. Un medoide del grupo \(C_j\) es la observación \(\mathbf{m}_j\in C_j\) que minimiza la suma de distancias a los demás puntos del grupo: \[ \mathbf{m}_j = \arg\min_{\mathbf{x}\in C_j}\sum_{\mathbf{x}'\in C_j}d(\mathbf{x},\mathbf{x}'). \tag{2}\]

El algoritmo PAM (Partitioning Around Medoids) itera intercambiando medoides con no-medoides y aceptando los cambios que reducen el costo total. PAM es más costoso que K-Means (\(O(k(n-k)^2)\) por iteración), pero produce resultados más robustos ante outliers.

from sklearn.datasets import make_blobs
import numpy as np

rng = np.random.default_rng(42)
X, _ = make_blobs(n_samples=200, centers=3, cluster_std=0.8, random_state=42)

# Agregar outliers
X = np.vstack([X, [[10, 10], [10, -10], [-10, 10]]])

from sklearn.cluster import KMeans

km = KMeans(n_clusters=3, random_state=0, n_init=10)
labels_km = km.fit_predict(X)
print("K-Means centroides:\n", km.cluster_centers_.round(3))

# Implementación simple de K-Medoids
def kmedoids_simple(X, k, seed=0):
    rng = np.random.default_rng(seed)
    idx = rng.choice(len(X), k, replace=False)
    medoids = list(idx)

    for _ in range(100):
        D = np.array([[np.linalg.norm(X[i] - X[m]) for m in medoids] for i in range(len(X))])
        labels = D.argmin(axis=1)
        new_medoids = []
        for j in range(k):
            cluster = np.where(labels == j)[0]
            if len(cluster) == 0:
                new_medoids.append(medoids[j])
                continue
            sub_D = np.array([[np.linalg.norm(X[a] - X[b]) for b in cluster] for a in cluster])
            new_medoids.append(int(cluster[sub_D.sum(axis=1).argmin()]))
        if new_medoids == medoids:
            break
        medoids = new_medoids
    return np.array(medoids), labels

medoids_idx, labels_kmed = kmedoids_simple(X, 3)
print("\nK-Medoids medoides (índices):", medoids_idx)
print("K-Medoids medoides (valores):\n", X[medoids_idx].round(3))

K-Means centroides:
 [[ 4.789  2.015]
 [-6.772 -6.857]
 [-2.737  8.984]]

K-Medoids medoides (índices): [74  7 24]
K-Medoids medoides (valores):
 [[-1.387  7.893]
 [-7.256 -6.694]
 [-6.334 -7.128]]

7 Implementación con scikit-learn

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

X, y_true = make_blobs(
    n_samples=400, centers=[[-3, -3], [0, 0], [3, 3], [0, 5]],
    cluster_std=[0.8, 1.0, 0.7, 0.9], random_state=42
)

X_std = StandardScaler().fit_transform(X)

km = KMeans(
    n_clusters=4,
    init="k-means++",
    n_init=20,
    max_iter=300,
    random_state=42
)
labels = km.fit_predict(X_std)

print("Inercia (WCSS):", round(km.inertia_, 4))
print("Iteraciones hasta convergencia:", km.n_iter_)
print("Silueta:", round(silhouette_score(X_std, labels), 4))
print("Distribución:", np.bincount(labels))

Inercia (WCSS): 76.5005
Iteraciones hasta convergencia: 4
Silueta: 0.6207
Distribución: [ 95 106 102  97]

8 Consideraciones prácticas

• Ejecutar K-Means múltiples veces (n_init) y quedarse con la solución de menor WCSS reduce el riesgo de caer en mínimos locales pobres.
• Estandarizar siempre los datos antes de aplicar K-Means, a menos que las distintas escalas tengan significado conceptual.
• En espacios de muy alta dimensión, considerar primero reducción de dimensión (PCA, UMAP) antes de aplicar K-Means.
• K-Means no es adecuado para datos con clusters de forma irregular; en ese caso preferir DBSCAN o clustering espectral.

Arthur, David, y Sergei Vassilvitskii. 2007. «k-means++: the advantages of careful seeding». Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1027-35.

Kaufman, Leonard, y Peter J. Rousseeuw. 1990. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.

Lloyd, Stuart P. 1982. «Least squares quantization in PCM». IEEE Transactions on Information Theory 28 (2): 129-37.

MacQueen, James. 1967. «Some methods for classification and analysis of multivariate observations». Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1: 281-97.