Búsqueda de patrones: técnicas de clustering

Clustering es una técnica de minería de datos (data mining) dentro de la disciplina de Inteligencia Artificial que identifica de forma automática agrupaciones o clústeres de elementos de acuerdo a una medida de similitud entre ellos. El objetivo fundamental de las técnicas de clustering consiste en identificar grupos o clústeres de elementos tal que:

  • La similitud media entre elementos del mismo clúster sea alta. Similitud intra-clúster alta.
  • La similitud media entre elementos de distintos clústeres sea baja. Similitud inter-clúster baja.

La identificación de clústeres o grupos de elementos se basa en una medida de similitud. Diferentes medidas de similitud dan lugar a diferentes clústeres.

_images/simpsons_general.png _images/simpsons_clustering_1.png _images/simpsons_clustering_2.png

En redes de co-expresión génica una de las posibles medidas de similitud que se utilizan con mayor frecuencia está basada en la correlación de Pearson. En este tutorial utilizaremos la siguiente medidad de similitud:

D(g1,g2)=1-cor(perfil(g1),perfil(g2))

Existen principalmente dos tipos diferentes de técnicas de clustering:

_images/clustering_techniques.png

Clústering jerárquico.

La técnica de clustering jerárquico construye un dendograma o árbol que representa las relaciones de similitud entre los distintos elementos. La exploración de todos los posibles árboles es computacionalmente intratable. Por lo tanto, suelen seguirse algoritmos aproximados guiados por determinadas heurísticas. Existen dos aproximaciones diferentes al clustering jerárquico:

  • Clustering jerárquico aglomerativo: se comienza con tantos clústeres como individuos y consiste en ir formando (aglomerando) grupos según su similitud.
  • Clustering jerárquico de división: se comienza con un único clúster y consiste en ir dividiendo clústeres según la disimilitud entre sus componentes.

En este tutorial nos centraremos en el clustering jerárquico aglomerativo. Esta técnica comienza con una matriz de similitud que contiene las distancias entre los distintos elementos a agrupar. En nuestro caso esta matriz se calcula a partir de la matriz de correlaciones.

_images/similarity_matrix_1.png

Consideramos todas las agrupaciones posibles y elegimos la mejor según la matriz de similitud.

_images/first_choice.png

Se recalcula la matriz de similitud teniendo en cuenta el nuevo clúster formado. La distancia al nuevo clúster se calcula como la media de las distancias a los elementos que lo forman.

_images/similarity_matrix_2.png

En el clustering jerárquico no es necesario especificar en número de clústeres a priori. Es posible seleccionarlo a posteriori según un umbral de corte. La estructura jerárquica es cercana a la intuición humana. La principal desventaja consiste en la acumulación de errores. Errores que se comenten en un paso de agrupamiento se propagan durante el resto de la construcción del dendograma sin ser posible su reajuste.

Clústering de partición.

La técnica de clustering de partición entorno a centroides (PAM) realiza una distribución de los elementos entre un número prefijado de clústeres o grupos. Esta técnica recibe como dato de entrada el número de clústers a formar además de los elementos a clasificar y la matriz de similitudes. Explorar todas las posibles particiones es computacionalmente intratable. Por lo tanto, suelen seguirse algoritmos aproximados guiados por determinadas heurísticas. En lugar de construir un árbol el objetivo en PAM consiste en agrupar los elementos entorno a elementos centrales llamados centroides a cada clúster. Definimos el centroide de un clúster como aquel elemento que minimiza la suma de las similitudes al resto de los elementos del clúster:

mC=argmin mC mjCdist(m,mj)

Paso 1: Seleccionar k centroides aleatoriamente.

_images/pam1.png

Paso 2: Crear k clústeres asignando cada elemento al centroide más cercano.

_images/pam2.png

Paso 3: Calcular nuevos centroides como aquellos elementos que minimizan la suma de las distancias al resto de elementos del clúster.

_images/pam3.png

Paso 4: Volver al paso 2 mientras haya cambio en los clústeres o se alcance un número máximo de iteraciones.

_images/pam4.png

En cada iteración de PAM se realiza un reajuste y mejora de los clústeres construídos de esta forma se evita la propagación de errores. Además de formar clústeres este algoritmo devuelve el elemento más central en cada clúster. La principal desventaja que presenta PAM consiste en la necesidad de fijar de antemano un número de clústeres a formar.

El paquete R WGCNA proporciona las funciones necesarias para realizar clustering jerárquico y de partición entorno a centroides. En particular, para realizar clustering jerárquico podemos utilizar la función hclust que recibe como entrada la matriz de similitudes a usar como distancia (as.dist) y el método para recalcular la matriz de distancias tras cada agrupamiento:

library("WGCNA")
allowWGCNAThreads()

similarity.matrix <- 1 - gene.correlation

hierarchical.clustering <- hclust(as.dist(similarity.matrix),method="average")

La función cutree recibe como dato de entrada el clustering jerarquico y el número de clústeres a generar:

hclust.2 <- cutree(hierarchical.clustering,k=2)
hclust.3 <- cutree(hierarchical.clustering,k=3)
hclust.4 <- cutree(hierarchical.clustering,k=4)
hclust.5 <- cutree(hierarchical.clustering,k=5)
hclust.6 <- cutree(hierarchical.clustering,k=6)
hclust.7 <- cutree(hierarchical.clustering,k=7)
hclust.8 <- cutree(hierarchical.clustering,k=8)
hclust.9 <- cutree(hierarchical.clustering,k=9)
hclust.10 <- cutree(hierarchical.clustering,k=10)

Mientras que la función pam con entrada la matriz de similitudes a usar como distancia (as.dist), el número de clústeres (k) y el uso de disimilitudes (diss=TRUE) se utiliza para realziar clustering de partición entorno a centroides:

pam.2 <- pam(as.dist(similarity.matrix),k=2,diss=TRUE)
pam.3 <- pam(as.dist(similarity.matrix),k=3,diss=TRUE)
pam.4 <- pam(as.dist(similarity.matrix),k=4,diss=TRUE)
pam.5 <- pam(as.dist(similarity.matrix),k=5,diss=TRUE)
pam.6 <- pam(as.dist(similarity.matrix),k=6,diss=TRUE)
pam.7 <- pam(as.dist(similarity.matrix),k=7,diss=TRUE)
pam.8 <- pam(as.dist(similarity.matrix),k=8,diss=TRUE)
pam.9 <- pam(as.dist(similarity.matrix),k=9,diss=TRUE)
pam.10 <- pam(as.dist(similarity.matrix),k=10,diss=TRUE)

Medida de calidad de un proceso de clustering, su silueta.

Durante el flujo de trabajo de clustering existen tres puntos claves donde se toman decisiones que determinan la identificación final de grupos o clústeres de genes:

  • Elección de la medida de similitud o distancia.
  • Elección del algoritmo de clustering.
  • Elección del número de clústers a identificar.

Para determinar la mejor elección posible es necesario fijar un criterio para mediar la calidad del resultado proporcionado por un flujo de trabajo de clustering. El objetivo general perseguido por las técnicas de clustering consiste en identificar grupos o clústeres compactos. Es decir, clusteres con una similitud intra-clúster alta y una similitud inter-clúster baja. Esta idea intuitiva se formaliza en el concepto de silueta de un cluster.

Como medida de la distancia intracluster de un elemento del clúster si se toma:

a(si)= sjCd(sj,si) |C|-1
_images/intra_cluster.png

Como medida de la distanica intercluster se toma:

b(si)=mink sjCkd(si,sj) |Ck|
_images/inter_cluster_1.png _images/inter_cluster_2.png

Por último definimos la silueta de un elemento si:

s(si)= b(si)-a(si) max{a(si),b(si)}

La función silhouette calcula la sileta media de todos los elementos en un análisis de clusteres. En nuestro estudio para determinar cuál es la mejor combinación entre técnica de clustering y número de clústeres calculamos la silueta de todos los clústering realizados con el método jerárquico y el método de partición entorno a centroides para 2,3, ... , 10 clústeres:

sil2 <- silhouette(hclust.2,dist=similarity.matrix)
sil3 <- silhouette(hclust.3,dist=similarity.matrix)
sil4 <- silhouette(hclust.4,dist=similarity.matrix)
sil5 <- silhouette(hclust.5,dist=similarity.matrix)
sil6 <- silhouette(hclust.6,dist=similarity.matrix)
sil7 <- silhouette(hclust.7,dist=similarity.matrix)
sil8 <- silhouette(hclust.8,dist=similarity.matrix)
sil9 <- silhouette(hclust.9,dist=similarity.matrix)
sil10 <- silhouette(hclust.10,dist=similarity.matrix)

hclust.sil.values <- c(summary(sil2)[["avg.width"]],summary(sil3)[["avg.width"]],summary(sil4)[["avg.width"]],summary(sil5)[["avg.width"]],summary(sil6)[["avg.width"]],summary(sil7)[["avg.width"]],summary(sil8)[["avg.width"]],summary(sil9)[["avg.width"]],summary(sil10)[["avg.width"]])

sil2 <- silhouette(pam.2)
sil3 <- silhouette(pam.3)
sil4 <- silhouette(pam.4)
sil5 <- silhouette(pam.5)
sil6 <- silhouette(pam.6)
sil7 <- silhouette(pam.7)
sil8 <- silhouette(pam.8)
sil9 <- silhouette(pam.9)
sil10 <- silhouette(pam.10)

pam.sil.values <- c(summary(sil2)[["avg.width"]],summary(sil3)[["avg.width"]],summary(sil4)[["avg.width"]],summary(sil5)[["avg.width"]],summary(sil6)[["avg.width"]],summary(sil7)[["avg.width"]],summary(sil8)[["avg.width"]],summary(sil9)[["avg.width"]],summary(sil10)[["avg.width"]])

Podemos representar la silueta de una combinación en particular entre técnica de clustering y número de clústeres con la función plot. Por ejemplo, para PAM con cuatro clústeres:

plot(sil4,main="Silueta PAM 4",border="blue")
_images/silueta_pam4.png

Para determinar la mejor combinación entre técnica de clustering y número de clústeres podemos generar un gráfico que para PAM y HCLUST represente la silueta media para cada posible número de clústeres:

plot(2:10,pam.sil.values[2:10],type="o",col="blue",pch=0,ylim=c(0.3,0.65),xlab="Number of clusters",ylab="Silhouette")
lines(2:10,hclust.sil.values[2:10],type="o",col="red",pch=1,xlab="",ylab="")
legend("topright",legend=c("PAM","HCLUST"),col=c("blue","red"),pch=c(0,1))
_images/siluetas.png

Como podemos observar en la figura anterior la mejor técnica de clustering es PAM para 2, 3 ó 4 clústeres. En lo que resta de este tutorial estudiaremos o bien dos o cuatro clústeres.

Visualización en la red de clústeres y generación de listas de genes.

Para visualizar la distribución de estos clústeres en nuestra red de co-expresión tenemos que generar dos ficheros de atributos de nodos:

clustering.pam.2 <- pam.2[["clustering"]]
names(clustering.pam.2) <- 0:2196
write.table(clustering.pam.2,file="pam_2.txt")

clustering.pam.4 <- pam.4[["clustering"]]
names(clustering.pam.4) <- 0:2196
write.table(clustering.pam.4,file="pam_4.txt")
_images/pam_2.png _images/pam_4.png

Utilizando las funciones apropiadas de annaffy de forma similar a lo realizado anteriormente podemos generar para cada clúster una página web y un fichero de texto con la anotación disponible de los genes que lo forman:

cluster1.pam4 <- names(which(pam.4[["clustering"]] == 1))
cluster2.pam4 <- names(which(pam.4[["clustering"]] == 2))
cluster3.pam4 <- names(which(pam.4[["clustering"]] == 3))
cluster4.pam4 <- names(which(pam.4[["clustering"]] == 4))

cluster1.pam4.table <- aafTableAnn(cluster1.pam4, "ath1121501.db", aaf.handler())
cluster2.pam4.table <- aafTableAnn(cluster2.pam4, "ath1121501.db", aaf.handler())
cluster3.pam4.table <- aafTableAnn(cluster3.pam4, "ath1121501.db", aaf.handler())
cluster4.pam4.table <- aafTableAnn(cluster4.pam4, "ath1121501.db", aaf.handler())

saveHTML(cluster1.pam4.table, file="cluster_1_annotation.html")
saveHTML(cluster2.pam4.table, file="cluster_2_annotation.html")
saveHTML(cluster3.pam4.table, file="cluster_3_annotation.html")
saveHTML(cluster4.pam4.table, file="cluster_4_annotation.html")

saveText(cluster1.pam4.table, file="cluster_1_annotation.txt")
saveText(cluster2.pam4.table, file="cluster_2_annotation.txt")
saveText(cluster3.pam4.table, file="cluster_3_annotation.txt")
saveText(cluster4.pam4.table, file="cluster_4_annotation.txt")