El analisis de conglomerados (clusters) tiene como objetivo agrupar elementos en grupos homogeneos en funcion de las similaridades entre ellos. Estos metodos tambien llamados como metodos de clasificacion automatica o no supervisada, o de reconocimiento de pratrones sin supervision. Este analisis de conglomerados estudia tres tipos de problemas:

Particion de los datos. Disponemos de datos que sospechamos son heterogeneos y se desea dividirlos en un numero de grupos prefijado, de manera que:

• cada elemento pertenezca a uno y solo uno de los grupos;
• todo elemento queda clasificado;
• cada grupo sea internamente homogeneo.

Construccion de jerarquias. Deseamos estructurar los elementos de un conjunto de forma jerarquica por su similitud. Una clasificacion jerarquica implica que los datos se ordenan en niveles, de manera que los niveles superiores contienen a los inferiores.

Clasificacion de variables. Cuando existen muchas variables es necesario hacer un estudio exploratorio inicial para dividir las variables en grupos. Las variables pueden clasificarse en grupos o estructurarse en una jerarquia. Los metodos de particion utilizan la matriz de datos, pero los algoritmos jerarquicos utilizan la matriz de distancias o similitudes entre elementos.

Todos los metodos de clustering tienen una cosa en comun, para poder llevar a cabo las agrupaciones necesitan definir y cuantificar la similitud entre las observaciones.

El termino distancia se emplea dentro del contexto del clustering como cuantificacion de la similitud o diferencia entre observaciones. Si se representan las observaciones en un espacio p dimensional, siendo p el numero de variables asociadas a cada observacion, cuando mas se asemejen dos observaciones mas proximas estaran, de ahi que se emplee el termino distancia.

La caracteristica que hace del clustering un metodo adaptable a escenarios muy diversos es que puede emplear cualquier tipo de distancia, lo que permite al investigador escoger la mas adecuada para el estudio en cuestion.

Distancia Euclidea

La distancia euclidea entre dos puntos p y q se define como la longitud del segmento que une ambos puntos. En coordenadas cartesianas, se calcula empleando el teorema de Pitagoras. Por ejemplo, en un espacio de dos dimensiones en el que cada punto esta definido por las coordenadas \((x,y)\), la distancia euclidea entre p y q viene dada por la ecuacion:

Distancia de Manhattan

Tambien se la conoce como taxicab metric, rectilinear distance o L1 distance, define la distancia entre dos puntos p y q como el sumatorio de las diferencias absolutas entre cada dimension.

Este metodo agrupa las observaciones en k clusters distintos, donde k lo determina el analista antes de ejecutar el algoritmo. K-means encuentra los k mejores clusters, es el mejor k el que minimiza la distancia intra cluster y maximiza la distancia inter cluster. El algoritmo empleado para ello es:

(1). Especificar el numero k de clusters que se quieren crear.

(2). Seleccionar de forma aleatoria k observaciones del set de datos como centroides iniciales.

(3). Asignar cada una de las observaciones al centroide mas cercano.

(4). Para cada uno de los K clusters recalcular su centroide.

(5). Repetir los pasos 3 y 4 hasta que las asignaciones no cambien o se alcance el numero maximo de iteraciones establecido.

K-means es uno de los metodos de clustering mas utilizados. Destaca por la sencillez y velocidad de su algoritmo, sin embargo, presenta una serie de limitaciones que se deben tener en cuenta.

• Requiere que se indique de antemano el numero de clusters que se van a crear.

• Las agrupaciones resultantes pueden variar dependiendo de la asignacion aleatoria inicial de los centroides.

• Presenta problemas de robustez frente a outliers.

K-medoids es un metodo de clustering muy similar a K-means en cuanto a que ambos agrupan las observaciones en K clusters, donde K es un valor preestablecido por el analista. La diferencia es que, en K-medoids, cada cluster esta representado por una observacion presente en el cluster (medoid), mientras que en K-means cada cluster esta representado por su centroide, que se corresponde con el promedio de todas las observaciones del cluster pero con ninguna en particular.

El algoritmo mas empleado para aplicar K-medoids se conoce como PAM (Partitioning Around Medoids) y sigue los siguientes pasos:

(1). Seleccionar K observaciones aleatorias como medoids iniciales.

(2). Calcular la matriz de distancia entre todas las observaciones si esta no se ha calculado anteriormente.

(3). Asignar cada observacion a su medoid mas cercano.

(4). Para cada uno de los clusters creados, comprobar si seleccionando otra observacion como medoid se consigue reducir la distancia promedio del cluster, si esto ocurre, seleccionar la observacion que consigue una mayor reduccion como nuevo medoid.

(5). Si al menos un medoid ha cambiado en el paso 4, volver al paso 3, de lo contrario, se termina el proceso.

• K-medoids es un metodo de clustering mas robusto que K-means, por lo es mas adecuado cuando el set de datos contiene outliers o ruido

• Al igual que K-means, necesita que se especifique de antemano el numero de clusters que se van a crear. Esto puede ser complicado de determinar si no se dispone de informacion adicional sobre los datos.

• Para sets de datos grandes necesita muchos recursos computacionales.

El coeficiente de Silueta es una metrica para evaluar la calidad del agrupamiento obtenido con algoritmos de clustering. El objetivo de Silueta es identificar cual es el numero optimo de agrupamientos.

El coeficiente de Silueta para una observacion \(i\) se denota como \(s(i)\) y se define como:

Donde:

• \(a\) es es el promedio de las disimilitudes (o distancias) de la observacion \(i\) con las demas observaciones del cluster al que pertenece \(i\)

• \(b\) es la distancia minima a otro cluster que no es el mismo en el que esta la observacion \(i\).

El valor de \(s(i)\) puede ser obtenido combinando los valores de \(a\) y \(b\) como se muestra a continuacion:

El coeficiente de Silueta es un valor comprendido entre -1 y 1. Mientras mas cercano sea este valor a 1 mejor sera el numero optimo de agrupamientos

En el entorno de programacion R existen multiples paquetes que implementan algoritmos de clustering y funciones para visualizar sus resultados. En este caso se usaran los siguientes:

Contienen multiples algoritmos de clustering y metricas para evaluarlos.

Extension basada en ggplot2 para crear visualizaciones de los resultados de clustering y su evaluacion.

“USArrests” contiene informacion sobre el numero de delitos (asaltos, asesinatos y secuestros) junto con el porcentaje de poblacion urbana para cada uno de los 50 estados de USA.

        Murder Assault UrbanPop Rape
Alabama   13.2     236       58 21.2
Alaska    10.0     263       48 44.5
Arizona    8.1     294       80 31.0

Como la magnitud de los valores difiere notablemente entre variables, se procede a escalarlas antes de aplicar el clustering.

datos <- scale(USArrests)
head(datos, 3)

            Murder   Assault   UrbanPop         Rape
Alabama 1.24256408 0.7828393 -0.5209066 -0.003416473
Alaska  0.50786248 1.1068225 -1.2117642  2.484202941
Arizona 0.07163341 1.4788032  0.9989801  1.042878388

set.seed(0911)
d <- dist(datos)
avgS <- c()
for(k in 2:5) {
  cl <- kmeans(datos, centers = k, iter.max = 200)
  s <- silhouette(cl$cluster, d)
  avgS <- c(avgS, mean(s[,3]))
}
data.frame(nClus = 2:5, Silh = avgS)

  nClus      Silh
1     2 0.4084890
2     3 0.3094312
3     4 0.3396889
4     5 0.3068221

Tomando en cuenta el coeficiente silueta lo mas optimo sera realizar 2 clusters

clusters <- kmeans(x = datos, centers = 2, nstart = 50)
clusters$centers

     Murder    Assault   UrbanPop       Rape
1 -0.669956 -0.6758849 -0.1317235 -0.5646433
2  1.004934  1.0138274  0.1975853  0.8469650

En el grupo uno se encuentran los estados con menor cantidad de asesinatos, asaltos, secuestros y porcentaje de poblacion, mientras que, en el grupo dos se encuentran los estados con mayor numero de asesinatos, asaltos, secuestros y porcentaje de poblacion.

Utilizando la base de datos del anterior ejemplo tenemos:

pc <- pam(datos, k = 2)
pc$medoids

               Murder    Assault   UrbanPop       Rape
New Mexico  0.8292944  1.3708088  0.3081225  1.1603196
Nebraska   -0.8008247 -0.8250772 -0.2445636 -0.5052109

Los medoids correspondientes a cada grupo son los estados de New Mexico y Nebraska respectivamente. En New Mexico existe mayor cantidad de asesinatos, asaltos, secuestros y porcentaje de poblacion, caso contrario sucede en Nebraska.

La aplicacion se encuentra en el siguiente enlace:

https://giorgiacongacha.shinyapps.io/kmeans/