Agrupamiento de datos
Dra. Rocío C. Romero Zaliz
Agrupamiento de datos
• El agrupamiento de datos o data clustering
consiste en la clasificación de objetos similares
en diferentes grupos.
• Más precisamente, consiste en particionar un
conjunto de datos en subconjuntos o clusters
de tal manera que estos tengan “algo en
común”.
– Proximidad
– Similitud
• Aprendizaje no supervisado
Tipos de clustering
• Particionales
• Jerárquicos
– Aglomerativos
– Divisibles
Clustering particional
Clustering jerárquico
Aglomerativo
Divisible
Objetivo
• Minimizar la distancia intracluster
• Maximizar la distancia entre clusters
Propiedades de los clusters
• Numéricos vs. Categóricos
Propiedades de los clusters
• Disjuntos vs. No disjuntos
Propiedades de los clusters
• Completos vs. Incompletos
Formas de los clusters
K-means
•
•
•
•
•
Particional
Distancia euclídea
Necesita el valor de k (#clusters)
Búsqueda de prototipos
Sensible a outliers
K-means
• Ubicar k (2) puntos en el espacio representado por los
objetos a ser agrupados. Estos k puntos son los
centroides iniciales de cada grupo
K-means
• Asignar cada objeto al grupo que esté más cercano a su
centroide
K-means
• Recalcular la posición de los k centroides
K-means
• Repetir pasos 2 y 3 hasta que los prototipos ya no
varíen
De esta manera se minimiza la distancia intracluster
según la metrica dada
K-means
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/AppletKM.html
Single-linkeage
• Jerárquico
• Aglomerativo
• Si hay un error en algún paso no se puede
volver atrás …
Single-linkeage
• Dado un conjunto de N (5) elementos a ser
agrupado y una matriz de distancia (o similitud)
de N x N:
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
7
4
10
5
4
0
3
5
13
8
7
3
0
Single-linkeage
• Comenzar por asignar cada item a un cluster.
• Tenemos 5 clusters
• Sean las distancias entre los clusters las mismas que
entre los elementos de cada cluster
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
7
4
10
5
4
0
3
5
13
8
7
3
0
Single-linkeage
• Encontrar el par más cercano de clusters y
unirlo en un único cluster.
• Tenemos 4 clusters
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
7
4
10
5
4
0
3
5
13
8
7
3
0
Single-linkeage
• Calcular las distancias entre el nuevo cluster y
los viejos clusters old clusters
d
1
2-3
4
5
1
0
5,5
10
13
7
2-3
5,5
0
4,5
8,5
0
3
4
10
4,5
0
3
3
0
5
13
8,5
3
0
d
1
2
3
4
5
1
0
5
6
10
13
2
5
0
1
5
8
3
6
1
0
4
4
10
5
4
5
13
8
7
Single-linkeage
• Repetir los pasos 2y 3 hasta que todos los
elementos se encuentren en el mismo cluster
de tamaño N
Single-linkeage
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/AppletH.html
Aplicación: respuesta inflamatoria
• Respuesta inflamatoria de seres humanos al
aplicarles una endotoxina en forma
intravenosa, en comparacion con un grupo de
control al cual se le inyecta un placebo
• Sangre de los ocho pacientes tratados, cuatro
con la endotoxina (pacientes 1-4) y cuatro con
el placebo (pacientes 5-8)
• Datos extraídos en diferentes instantes de
tiempo, a 0, 2, 4, 6, 9 y 24 horas, y se han
procesado utilizando GeneChips ® y HGU133A v2.0 de Aymetrix Inc ®
Microarrays
Bases de datos
• Relacionales
– Atributo – valor
– Ej: Entrez
• Estructurales
– Ontologías
– Jerarquías
– Ej: GO, Taxonomías, PFAM, etc.
Gene Ontology (GO)
• El proyecto de Gene Ontology (GO) busca crear
descripciones consistentes de productos de genes
provenientes de diferentes bases de datos
• Se han desarrollado 3 ontologías (vocabularios
controlados y estructurados):
– Procesos biológicos
– Funciones moleculares
– Componentes celulares
• El uso de términos GO en diferentes bases de datos
uniformiza las búsquedas en ellas
• Diferentes niveles
Gene Ontology (GO)
• 3 ontologías
• 2 clases de relaciones
Gene Ontology (GO)
• Biological Process
– GO:0006446
• Molecular Function
– GO:0003723
– GO:0003742
• Cellular Component
– GO:0016281
Gene Ontology (GO)
• Diferentes relaciones
• Un nodo puede tener
más de un padre
• Diferentes niveles de
especificidad
• Un nodo puede
encontrares en
diferentes niveles al
mismo tiempo
Clustering Conceptual
EMO-CC
• Clustering Conceptual
• Algoritmos Evolutivos
MultiObjetivo
• Aplicaciones:
– Análisis de microarrays
– Redes regulatorias
– Moléculas
EMO-CC: Base de datos
EMO-CC: Base de datos
EMO-CC: Aprendizaje
EMO-CC: Aprendizaje
EMO-CC: Objetivos
• Sensitividad
• Especificidad
EMO-CC: Objetivos
• Sensitividad
• Especificidad
EMO-CC: Aprendizaje
EMO-CC: Compactación
EMO-CC: Compactación
EMO-CC: Compactación
EMO-CC: Compactación
EMO-CC: Modelos
EMO-CC: Predicción
Descargar

Document