Análisis de Cluster, un ejemplo sencillo.

El análisis de agrupamiento (cluster), es sencillo de explicar y de implementar en R project. Lo delicado es procesar la información y la definición de la métrica que consideramos apropiada para nuestros datos o experimento.

Hago un ejemplo sencillo antes de explicar qué se hace con esta técnica.

#Ejemplo de Cluster
data(iris)
#Generamos 5 grupos en nuestros datos
modelo5<-kmeans(iris[1:2],5)
plot(iris[1:2],col=modelo5$cluster,main="Ejemplo de 5 cluster",xlab="longitud de la Sápal",ylab="Ancho de la Sápal")
#Generamos 3 grupos en nuestros datos
modelo3<-kmeans(iris[1:4],3)
plot(iris[1:4],col=modelo3$cluster,main="Ejemplo de 3 cluster")

 Ejemplo_5_cluster

Ejemplo_3_cluster

Los dos gráficos muestran de colores distintos un conjunto de puntos, por lo que se ve en el código, usando una función kmeans para definir modelo5,modelo3. Luego indico al gráfico que tomara los colores partiendo de un valor $cluster. Esto podríamos deducirlo viendo solo el  código, la pregunta es cómo se define qué puntos pintar de cierto color. Si uno hace el “scatter plot” de los mismos datos se observa una “regla”.

#Scatter Plot 
data(iris)
plot(iris[1:4],col=c(2,3),main="Scatter Plot de parejas de vectores de datos")

Ejemplo_Scatter_Plot_Datos Iris

Si uno compara los 3 gráficos, la regla para determinar el color de los puntos tienen que ver con un modo de agruparlos, de tener un modo de verlos cuan cercanos o similares son. Eso se nota principalmente entre los dos últimos gráficos.

La idea de “similar”, puede ser pensada como un modo de comparar cosas, si se piensa en tres personas  donde dos estudiaron en la misma universidad, tienen casi la misma edad y alturas y tienen diferencia de peso de solo un par de kilos, son “casi iguales” con respecto al tercer individuo, que no estudió en la misma universidad, tiene más años, tiene sobrepeso y mide más que los otros dos. Entonces podemos pensar que los dos primeros son “similares” o al compararlos “son más cercanos o parecidos”.

La noción de “cercanía” está asociada con la noción de distancia, podemos definir que dos cafeterías tienen una distancia pequeña si las separa una calle, pensando que su unidad de medida son el número de calles entre ellas. Entonces la noción a través de todo esto es la de “métrica“, cómo medir similitudes.

En geometría, la métrica es la distancia entre puntos la cual tienen ciertas propiedades; medir del punto 1 al punto 2 es igual que iniciar midiendo desde el punto 2 hasta el punto 1 (simetría); la distancia entre los puntos es por lo menos cero (positiva) y  medir la distancia entre dos puntos es menor o igual que la suma de las distancia de los puntos a un punto intermedio (desigualdad del tringualo) y la última, si la distancia entre dos puntos es cero los puntos no pueden ser distintos (identidad de los indiscernibles).

Entonces la idea de la técnica es medir la distancia de cada pareja de puntos de los datos. Esto no necesariamente implica que la distancia sea para números o vectores, puede ser definida por las características de los datos o sobre cadenas de texto o mensajes, características de una persona,etc.

Aclarado el código anterior, lo que se hizo con el comando kmeans fue aplicar un algoritmo que permite separar entre los grupos de datos, tomando como parte inicial el  eligir la cantidad de grupos que se desean, después se calcula el centroide con respecto a todos los datos y se hace un proceso de separación e iteracciones para determinar los cúmulos, la técnica se llama k-Means Clustering. Para entender en detalles el algoritmo se puede revisar las notas de Andrew Ng o de Andrew Moore, las notas de éste último son acompañadas de varias  gráficas lo cual ayuda a visualizar el algoritmo de un modo sencillo.

Un ejemplo puede ser pensando en una matriz de datos, donde cada fila representa un individuo y cada columnas es una característica la cual puede tomar el valor de -1,0 o 1. Entonces lo que se hace es realizar el producto de la matriz y su transpuesta para obtener la correlación entre cada uno de los individuos y lo que se usa como métrica es la distancia euclidiana. Con ellos se puede tener una matriz con información sobre las distancia entre nuestros individuos.

#Ejemplos 
x.matriz<-matrix(sample(c(-1,0,1),24,replace=TRUE),nrow=4,ncol=6)
#Etiquetamos las columnas y las filas
row.names(ex.matriz)<-c('A','B','C','D')
colnames(ex.matriz)<-c('P1','P2','P3','P4','P5','P6')
#Multiplicamos por la transpuesta
ex.mult<-ex.matriz%*%t(ex.matriz)

#Calculamos la distancia
ex.dis<-dist(ex.mult)

Ahora usamos el comando cmdscale para calcular el escalamiento multidimensional, obtendremos como resultado los puntos que son cercanos o próximos, según la métrica.

#Cluster
ex.mds<-cmdscale(ex.dis)
plot(ex.mds,type='n')
text(ex.mds,c('A','B','C','D'))

Ejemplo_Escalado_Multidimensional

Se concluye del ejemplo anterior que la estrategia es; procesar nuestra información, definir o usar una métrica, construir la matriz de similaridad y aplicar el análisis de escalamiento multidimensional o un algoritmo de agrupamiento.

Polarización de un Senado

Muestro un ejemplo del texto Machine Learning for Hackers [1]. El ejemplo usa los datos del senado de EEUU, se encuentran en la plataforma http://www.voteview.com y en caso de tener una falla en la descargar se puede bajar del repositorio de GitHub en https://github.com/johnmyleswhite/ML_for_Hackers.

La idea es la siguiente, revisar el comportamiento de las votaciones del Senado y revisar el comportamiento del periodo 110 al 111 del congreso.

Lo que se hará es procesar la información, asignar ciertas variables categóricas que solo tendrán valores -1,0 y 1 para cada una de las características de los senadores analizados. Esto permite definir una métrica sencilla, como la del último ejemplo y basta considerar el productos de matrices para formar la matriz de similaridad.

#Análisis de votos 
library(foreign)
library(ggplot2)
#Tomamos la ruta de los archivos
data.dir 6, 0,no.pres[,i])
         no.pres[,i] 0 & no.pres[,i] < 4, 1, no.pres[,i])
         no.pres[,i] 1, -1, no.pres[,i])
 }
 
 return(as.matrix(no.pres[,10:ncol(no.pres)]))
}

#Aplicamos la función a cada entrada de rollcall.data
rollcall.simple

Con lo anterior pueden construir las gráficas que para apreciar la evolución del senado, donde la hipótesis inicial es que el congresos se polarizó en el 111 congreso.

Primero se revisa el comportamiento solo de las votaciones del 111 congreso y después se compara con respecto los congresos previos, partiendo desde el 101.

MDS_Votacion_Senado111_US

MDS_Votacion_Senado del 101 al 111_congreso_USEn resumen la última gráfica muestra que el Senado en distintos periodos se puede dividir en dos grupos, se puede decir que se polariza entre Republicanos y Demócratas. Los pocos senadores considerados como “independientes” parece, al revisar la última gráfica; que siempre votaran como los Demócratas.

La moraleja es que bajo una métrica sencilla se pueden extraer ciertas propiedades del comportamiento o dinámica del los datos. Sería interesante hacer un ejercicio similar para  el Senado de otros países.

Resumiendo, la técnica o análisis de agrupamientos (cluster) requiere como primer paso explorar nuestra información y procesarla si es necesario para poder definir una métrica que tenga coherencia con el tipo de información y datos.

Después se debe de calcular la matriz de distancias y por último aplicar escalamiento multidimensional o algún algoritmos para detectar aglomeraciones.

Como paso intermedio, tienen sentido plantearse una pregunta respecto a los posibles grupos que se busca encontrar en los datos y como siempre para cerrar el análisis, hacer usos de gráficos que permitan visualizar el resultado.

Ha esta entrada le falta mucho muchos ejemplos, que espero más adelante compartir otros. Respecto al tema falta mostrar varios detalles; tipos de métricas para tipos de datos, algoritmos de aglomeración para tipos de análisis y la creación de modelos basados en esta técnica.

Los aspectos teóricos se encontrarán en la categoría “Sobre Machine Learning”. Una disculpa para la gente de matemáticas por no haber puesto la definición formal de espacio métrico, métrica y mencionar algunas de sus propiedades, espero posteriormente hacer algunas entradas con un enfoque formal.

Actualización 19-05-2015

En la primera versión de esta entrada faltó mencionar muchos detalles sobre la técnica de K-medias, pero además no mencioné nada sobre otro algoritmo Hirarchical Clustering o Cluster jerárquico.

Comparto un ejemplo de esta técnica y en resumen lo que se hace en este algoritmo es construir un árbol que ayude aglomerar los datos en conjuntos los cuales al terminar el algoritmo muestra las aglomeraciones obtenidas.

El costo computacional es mucho mayor que los métodos k-medias, pero en general para muestras de datos relativamente grandes no resulta tan costoso implementarlo y además se han desarrollado algoritmos para reducir el costo en tiempo y procesamiento.

Los datos los tomo de la página del libro Elements of Stadistical Learning [2], en el código indico como descargarlo directamente.

Respecto al origen de los datos, cabe resaltar que corresponde al análisis de tumores cancerígenos, se analiza su valor genético a 64 tumores y por medio de las técnicas de Cluster se trata de detectar cuantos cánceres corresponde a qué tipo de tumor.

Algunas precisiones. Se descargaron los nombres de los tumores en un archivo txt, a que los nombres de las columnas no vienen por default en los datos. La matriz de datos está formada por 64 columnas y 6830 filas.

#Ejemplo de Cluster con datos de tumores 
#Ubicado en el directorio donde estan los nombres de los genes se procede a cargarlos en R
#Se carga como un vector
Nombres=read.table("nombres_tumores.txt")
#Visualizamos los datos
head(Nombres)
# V1
# CNS
# CNS
# CNS
# RENAL
# BREAST
# CNS

#Cargamos los datos de los genes

datos=scan("http://statweb.stanford.edu/~tibs/ElemStatLearn/datasets/nci.data")

#Visualizamos los datos
head(M)
#Tranformamos los datos en una matriz de 64 renglones por 6830 columnas
#Después invertimos la matrix
M=matrix(datos,nrow=64)
M2=t(M)

#Agremagamos los nombres a las columnas de M2

colnames(M2)=as.vector(t(Nombres))
 
head(M2)
#Así se visualiza la tabla de datos
# CNS CNS CNS RENAL BREAST CNS CNS BREAST NSCLC NSCLC RENAL RENAL RENAL RENAL RENAL RENAL RENAL BREAST NSCLC RENAL UNKNOWN
#[1,] 0.300 0.679961 0.940 2.800000e-01 0.485 0.310 -0.830 -0.190 0.460 0.760 0.270 -0.450 -0.030 0.710 -0.360 -0.210 -0.500 -1.060 0.150 -0.290 -0.200
#[2,] 1.180 1.289961 -0.040 -3.100000e-01 -0.465 -0.030 0.000 -0.870 0.000 1.490 0.630 -0.060 -1.120 0.000 -1.420 -1.950 -0.520 -2.190 -0.450 0.000 0.740
#[3,] 0.550 0.169961 -0.170 6.800000e-01 0.395 -0.100 0.130 -0.450 1.150 0.280 -0.360 0.150 -0.050 0.160 -0.030 -0.700 -0.660 -0.130 -0.320 0.050 0.080
#[4,] 1.140 0.379961 -0.040 -8.100000e-01 0.905 -0.460 -1.630 0.080 -1.400 0.100 -1.040 -0.610 0.000 -0.770 -2.280 -1.650 -2.610 0.000 -1.610 0.730 0.760
#[5,] -0.265 0.464961 -0.605 6.250000e-01 0.200 -0.205 0.075 0.005 -0.005 -0.525 0.015 -0.395 -0.285 0.045 0.135 -0.075 0.225 -0.485 -0.095 0.385 -0.105
#[6,] -0.070 0.579961 0.000 -1.387779e-17 -0.005 -0.540 -0.360 0.350 -0.700 0.360 -0.040 0.150 -0.250 -0.160 -0.320 0.060 -0.050 -0.430 -0.080 0.390 -0.080

#Aplicamos k-Means con 3 cluster a
KM3=kmeans(M2,3)

#Generamos una gráfica para visualizar los componentes

library(cluster)
clusplot(M2,KM3$clusteres,shape=TRUE,color=TRUE,labels=3)

#Aplicamos Hierarchical Clustering
H1<-hclust(dist(M),"average")
#Dendrograma
plot(H1,col=2,frame.plot=TRUE)

 Las gráficas que obtengo del código  son las  siguientes:

Dendrograma

Cluster_Genes

La primera gráfica es el modo visual en que se comportan los clusters en el método jerárquico y la segunda es una herramienta visual para observar el comportamiento del método k-medias.

Una observación entre los dos métodos es, k-medias pide como parámetro conocer cuantos clusters se buscamos en el algoritmo y el jerárquico no, de cierto modo la aglomeración por el jerárquico es cercana a lo que sería un método no supervisado.

Para el  algoritmo de k-medias resulta importante el análisis de la elección de la cantidad de clusters en los datos.

Existen varias técnicas para tratar de elegir el mejor valor de k, en R project, existen varias librerías entre las cuales están: “fpc” y “mclust”. Para los datos de este ejemplo probé con mclust, pero le resultaba muy costoso así que cancelé el proceso.

Pero otro modo muy sencillo y que no requiere ninguna librería es mediante el análisis de los cuadrados de las distancias de cada  dato aglomerado con respecto a la cantidad de clusters que se calculan.

#Elección de K para k-medias
wss <- (nrow(M2)-1)*sum(apply(M2,2,var))
 for (i in 2:10) wss[i] <- sum(kmeans(M2,centers=i)$withinss)
plot(1:10, wss, type="b", xlab="Númbero de Clusters",ylab="Suma de cuadrados dentro de cada cluster")

 La gráfica que se obtiene es la siguiente:

K-Medias

Esta última técnicas es sencilla, pero el problema es que no siempre indica de modo claro como elegir la cantidad de clusters de un modo óptimo. Por lo cual es bueno recurrir a otro tipo de algoritmo y compara nuestra selección y al final validar con alguna muestra de datos.

En un trabajo de investigación de Robert Tibshirani-G. Walther y Trevor Hastie[5] plantean un método para obtener un óptimo del número de clusters en el algoritmo k-meadias, sobre este reporte de investigación se basan varias librerías en R project para estimar el valor óptimo de k.

Espero que este complemente de una idea en general del tipo de análisis y de las técnicas básicas de como usar este tipo algoritmo. Cabe mencionar que las técnicas de Cluster están relacionadas con la Mezcla de Modelos y el algoritmo EM, lo cual se puede usar para la construcción de modelos. En otra entrada explico el uso y relación de esto.

Referencias:

1.-http://shop.oreilly.com/product/0636920018483.do

2.-http://statweb.stanford.edu/~tibs/ElemStatLearn/

3.-http://www.amazon.com/Cluster-Analysis-Brian-S-Everitt/dp/0470749911

4.-http://www.amazon.com/Machine-Learning-Probabilistic-Perspective-Computation/dp/0262018020

5.-http://web.stanford.edu/~hastie/Papers/gap.pdf

Anuncios

5 comentarios sobre “Análisis de Cluster, un ejemplo sencillo.

  1. Hola. Excelente explicación. Pero me gustaría que me ayudaras a completar la linea ex.mds<-cmdscale(ex.dislot(ex.mds,type=’next(ex.mds,c(‘A’,’B’,’C’,’D

    Me aparece así de incompleta.
    Gracias

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s