Capítulo 12 Analisis de clusters

Clustering se refiere a un conjunto amplio de técnicas para encontrar subgrupos o clusters, en una base de datos. Cuando agrupamos las observaciones, se busca dividirlos en grupos distintos para que las observaciones dentro cada grupo sean bastante similares entre sí, mientras que las observaciones en grupos diferentes sean muy distintas entre sí. Por ello, se debe definir qué significa que dos (o más) observaciones sean similares o diferentes.

Si $X$ es una matriz de $n$ filas (observaciones) y $p$ columnas, cada fila es un “punto” de $p$ dimensiones y cada columna se corresponde con una variable. Por ejemplo, una base con 30 alumnos y cuatro notas de distintas materias (cada alumno es un “punto”).

Clustering busca armar grupos de puntos con esos datos. Se trata de un problema no supervisado porque se trata de descubrir estructura, grupos distintos, en base a los datos. Esto es útil, por ejemplo, para segmentación de mercado.

Dissimilarity

Suponer dos puntos $x, z \in \Re^p$. ¿Cuán disímiles son $x$ y $z$, con $p$ coordenadas cada uno?

En el caso de variables cuantitativas la distancia euclídea³³ es:

\[\begin{equation} \tag{12.1} d(x,z) = [\sum_{j=1}^{p} (x_j - z_j)^{2}]^{\frac{1}{2}} \end{equation}\]

Definición: Dissimilarity Matrix

Si $D$ es una matriz $N \times N$ donde $D_{ij} = D(x_i, x_j)$ es el input del análisis de clusters. Idealmente las $D_{ij}$ son verdaderas distancias, de modo que $D$ es simétrica y con diagonal principal nula. El análisis es muy sensible a la elección de $D$.

Cluster analysis

Cada punto está indizado por $i \in {1,...,N}$ y supongamos que sabemos de antemano que hay $K$ clusters. A su vez, cada cluster está indizado por $k \in {1,...,K}$. Entonces, un mecanismo de clusters asigna cada punto a un solo cluster. Es decir:

$k = C(i)$, donde $C(i)$ es un “enconder”

$C(i)$: ${1,...,N} \to {1,...,K}$.

Por lo tanto, el análisis de cluster busca encontrar $C^{*}(i)$ óptimo, en base a la matriz de dissimilarities.

Si se considera la siguiente función de pérdida:

\[\begin{equation} \tag{12.2} W(C) = \frac{1}{2} \sum_{k=1}^{K} [\sum_{i,j/C(i) = C(j) = k} d(x_i,x_j)] \end{equation}\]

Intuitivamente $W(C)$ agrega las disimilitudes dentro de cada cluster.

Si se define $T$ como la disimilitud total, entre todas las observaciones (no depende de la clusterización):

\[\begin{align} T = & \frac{1}{2} \sum_{i,j} d_{i,j} \\ = & \frac{1}{2} \sum_{k=1}^{K} [\sum_{i,j/C(i) = C(j) = k} d(x_i,x_j) + \sum_{k=1}^{K} [\sum_{i,j/C(i) = C(j) \neq k} d(x_i,x_j)] \\ T = & W(C) + B(C) \end{align}\]

Donde $B(C)$ es la agregación de las distancias entre clusters. Entonces, si se propone como objetivo minimizar la disimilitud dentro de los clusters, como $T$ esta fijo, minimizar $W(C)$ es equivalente a maximizar $B(C)$.

12.1 K-Means Clustering

En K-Means Clustering se busca dividir las observaciones en un número preespecificado de grupos. Luego el algoritmo asignará cada observación a exactamente uno de los $K$ clusters.

La Figura 12.1 muestra los resultados obtenidos al realizar K-means clustering en un ejemplo simulado con 150 observaciones en dos dimensiones utilizando tres valores diferentes de $K$.

\[\begin{equation} \tag{12.3} W(C) = \sum_{k=1}^{K} N_k \sum_{C(i) = k} || x_i - \overline{x}_k ||^2 \end{equation}\]

donde $\overline{x}_k = (\overline{x}_{1k},...,\overline{x}_{pk})$ es el vector de medias asociado con el cluster $k$ y $N_k = \sum_{i=1}^{N} I(C(i)=k)$.

Figura 12.1: Clusters

Algoritmo de k-means:

Asignar aleatoriamente un número, del $1$ al $K$, a cada una de las observaciones. Estos sirven como asignaciones de grupos iniciales para las observaciones.
Iterar hasta que las asignaciones de clusters dejen de cambiar.

Para cada uno de los $K$ clusters, calcular el centroide del cluster. El k-ésimo centroide del cluster es el vector de $p$ medias de atributos para las observaciones en el k-ésimo cluster.
Asignar cada observación al cluster cuyo centroide esté más cerca (usando la distancia euclidiana).

Figura 12.2: Algoritmo

El mecanismo optimiza primero dentro del cluster (elige las medias) y luego optimiza reasignando las observaciones, dejando quietas las medias.

Dado que el algoritmo de K-means encuentra un óptimo local en lugar de un óptimo global, los resultados obtenidos dependerán de la asignación inicial (aleatoria) de clusters de cada observación en el paso $1$ del algoritmo. Por esta razón, es importante ejecutar el algoritmo varias veces desde diferentes puntos aleatorios iniciales. Luego se selecciona la mejor solución, es decir, aquella para la cual la ecuación (12.3) es el más pequeño.

La Figura 12.3 muestra los óptimos locales obtenidos ejecutando K-means clustering seis veces usando seis asignaciones iniciales diferentes.

Figura 12.3: Algoritmo

Cuestiones prácticas

Inicialización: puede ser en base a clusters o medias.
Número de clusters: No hay un mecanismo comúnmente aceptado. En algunos casos es exógeno.
La within dissimilarity $W(C)$ cae con el número de clusters.
$K$ óptimo se corresponde con un quiebre en el dibujo de $W(C)$ incrementando la cantidad de clusters (trade-off sesgo-varianza determinado por cantidad de clusters).

12.2 Aplicacion practica

La función kmeans() realiza K-means clustering en R. Comenzamos con un ejemplo simulado simple en el que realmente hay dos grupos en los datos: las primeras 25 observaciones tienen un cambio medio relativo a las siguientes 25 observaciones.

set.seed(2)
x <- matrix(rnorm(50 * 2), ncol = 2)
x[1:25, 1] <- x[1:25, 1] + 3
x[1:25, 2] <- x[1:25, 2] - 4

Ahora estimamos K-means clustering con $K = 2$

km.out <- kmeans(x, 2, nstart = 20)

Las asignaciones de clusters de las 50 observaciones están contenidas en km.out$cluster.

km.out$cluster

##  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2
## [39] 2 2 2 2 2 2 2 2 2 2 2 2

El K-means clustering separó perfectamente las observaciones en dos grupos a pesar de que no proporcionamos ninguna información de grupo a kmeans(). Podemos graficar los datos, con cada observación coloreada de acuerdo con su asignación de grupo.

plot(x, col = (km.out$cluster + 1),
    main = "K-Means Clustering Results with K = 2",
    xlab = "", ylab = "", pch = 20, cex = 2)

En este ejemplo, sabíamos que realmente había dos clusteres porque generamos los datos. Sin embargo, para datos reales, en general no se conoce el verdadero número de clusters. Podríamos haber realizado K-means clustering en este ejemplo con $K = 3$.

set.seed(4)
km.out <- kmeans(x, 3, nstart = 20)
km.out

## K-means clustering with 3 clusters of sizes 17, 23, 10
## 
## Cluster means:
##         [,1]        [,2]
## 1  3.7789567 -4.56200798
## 2 -0.3820397 -0.08740753
## 3  2.3001545 -2.69622023
## 
## Clustering vector:
##  [1] 1 3 1 3 1 1 1 3 1 3 1 3 1 3 1 3 1 1 1 1 1 3 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2
## [39] 2 2 2 2 2 3 2 3 2 2 2 2
## 
## Within cluster sum of squares by cluster:
## [1] 25.74089 52.67700 19.56137
##  (between_SS / total_SS =  79.3 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

plot(x, col = (km.out$cluster + 1),
    main = "K-Means Clustering Results with K = 3",
    xlab = "", ylab = "", pch = 20, cex = 2)

Cuando $K=3$, K-means clustering divide los dos grupos.

Para ejecutar la función kmeans() en R con múltiples asignaciones de clusteres iniciales, usamos el argumento nstart. Si se usa un valor de nstart mayor que uno, entonces K-means clustering se realizará usando múltiples asignaciones aleatorias en el Paso 1 del algoritmo, y la función kmeans() reportará solo los mejores resultados. Aquí comparamos el uso de nstart = 1 con nstart = 20.

set.seed(4)
km.out <- kmeans(x, 3, nstart = 1)
km.out$tot.withinss

## [1] 104.3319

km.out <- kmeans(x, 3, nstart = 20)
km.out$tot.withinss

## [1] 97.97927

Tener en cuenta que km.out$tot.withinss es la suma total de cuadrados dentro del grupo, que buscamos minimizar realizando K-means clustering. Las sumas de cuadrados individuales dentro del grupo están contenidas en el vector km.out$withinss.

Se recomienda ejecutar siempre K-means clustering con un valor grande de nstart, como 20 o 50, ya que de lo contrario puede obtenerse un óptimo local indeseable.

Al realizar un K-means clustering, además de utilizar varias asignaciones de agrupamiento iniciales, también es importante establecer una semilla aleatoria usando la función set.seed(). De esta manera, las asignaciones de grupos iniciales en el Paso 1 pueden ser replicadas y la salida de K-means será totalmente reproducible.

Agrega disimilitudes para cada atributo.↩︎