Aprendizaje automático no supervisado (II)
Flavio Pazos Obregón
Implementación de modelos basados en aprendizaje automático para el abordaje de problemas biológicos
Curso PEDECIBA Bioinformática - 2023
Plan para hoy:
Clustering
- k means
- Clustering jerárquico
- DBSCAN
Evaluación
Aprendizaje no supervisado
alterix.com
- Engloba técnicas de aprendizaje automático en las que no hay un salida conocida de antemano, ni
etiquetas o categorías con las que entrenar al algoritmo de aprendizaje.
- Se le presentan los datos al algoritmo y se espera que el mismo “extraiga” conocimiento de ellos.
- Se puede dividir en dos tipos: transformaciones de los datos y clustering
Transformaciones
- Buscan crear nuevas representaciones de los datos que pueden ser más fáciles de entender que la
representación original (para humanos o para otros algoritmos)
- Una aplicación habitual es la reducción de dimensionalidad, que busca representar los datos en
espacios de menor dimensión manteniendo la mayor cantidad de información posible.
PCA
- Estandarización
- Cálculo de la matriz de covarianza (m x m)
- Cómputo de vectores y valores propios
- Elegir los p primeros vectores propios según sus valores propios (con p < m)
- Proyectar los datos originales en el nuevo espacio
tSNE
- Calcula la distribución conjunta Pij, que asigna una probabilidad a cada combinación de valores posibles
de todas las variables en el espacio original.
- Distribución Qij en el espacio de menor dimensionalidad (inicialización aleatoria u otra técnica)
- Cálculo de la divergencia Kullback-Leibler entre ambas distribuciones e Iteraciones para minimizarla
UMAP
- Grafo de vecinos en el espacio de alta dimensionalidad
- Para cada punto, se identifican sus k vecinos más cercanos en función de alguna métrica de similitud (los
dos parámetros a ajustar)
- se busca una representación de menor dimensionalidad que mantenga las relaciones de vecindad
- función de pérdida específica (SNE Loss) para optimizar las ubicaciones de los puntos
Clustering
- Es la tarea de dividir el dataset en grupos, llamados clusters,
- El objetivo es que los items de cada grupo sean similares entre sí y que los items de grupos
diferentes sean distintos
- Un algoritmo de clustering le asigna (o le predice) un grupo particular a cada item
Algunos algoritmos de clustering
k-means
k-Means
k-Means
- Busca los centroides de los
clusters que sean representativos
de ciertas regiones de los datos
- Itera entre dos pasos: asignar
cada punto al cluster con el
centroide más cercano y calcular
cada centroide como el promedio
de los puntos asignados al
mismo.
- El algoritmo termina cuando las
asignaciones a centroides dejan
de cambiar.
k-Means
Muller & Guido, 2017
- El algoritmo inicializa declarando, al azar, una cantidad de centroides que se debe indicar
- Luego se puede usar para asignar cada nuevo dato al centroide más cercano
k-Means
- Asume cosas que no siempre se cumplen; misma densidad, que todas las direcciones de variación son
igualmente importantes, que los clusters son convexos
k-Means
Muller & Guido, 2017
- Funciona bien cuando los datos forman clusters compactos y distintos y se elige un buen k
k-Means
https://stackoverflow.com/questions/15376075/
- Para elegir k se puede graficar la suma de todas las distancias (al cuadrado) entre los puntos de un
mismo cluster como función de k.
- Esta suma siempre es decreciente, pero también su pendiente. Se puede usar el codo o “elbow” como
criterio para fijar k
clustering jerárquico
https://medium.com/@viveksalunkhe80/hierarchical-clustering/
Clustering jerárquico
- Los métodos jerárquicos tienen por objetivo agrupar clusters para formar uno nuevo o bien
separar alguno ya existente para dar origen a otros dos, de tal forma que se minimice alguna
distancia o se maximice alguna medida de similitud.
- Se subdividen en métodos aglomerativos y disociativos, cada un una gran diversidad de variantes.
Clustering aglomerativo
Muller & Guido, 2017
- Al inicio cada punto es un cluster en sí mismo y luego se van combinando sucesivamente los dos clusters
más similares.
- Se va reduciendo el número de clusters hasta que se satisface cierta condición
- Existen varios criterios para definir cuales son los dos clusters “más cercanos” o “más similares”
Linkage
- Distintos criterios para combinar clusters:
- single linkage: la mínima distancia entre sus componentes
- complete linkage: la menor distancia máxima entre sus componentes.
- average: el menor promedio (ponderado o no) de la distancia entre todos sus componentes
- Ward: la fusión que resulte en el menor incremento en la suma de todas las distancias (al
cuadrado) de cada punto al centroide del nuevo cluster.
- Distintas distancias: Euclídea (L2), Manhattan (L1), coseno, matrices precomputadas.
Dendrogramas
Muller & Guido, 2017
- cada dato es un punto en al base y se forma un nodo al unir dos clusters
- el largo de cada rama representa la distancia entre los clusters que se unen y ramas más largas
indican que se unen clusters más distintos
Cuántos clusters?
- El dendrograma puede proporcionar una indicación del número de clusters.
- Método del codo, midiendo la varianza intra-cluster promedio para cada cantidad de clusters.
- Método silhouette: mide cuán similar es un objeto a su propio cluster en comparación con otros clusters.
DBSCAN
- Density-based Spatial Clustering of Applications with Noise
- No necesita predeterminar la cantidad de clusters
- Puede capturar formas complejas e identificar puntos que son ruído
DBSCAN
DBSCAN
- La idea es que los clusters forman zonas densas separadas por zonas menos densas
- Identifica puntos “core” en base a dos parámetros: : min_samples y eps.
- Un puno es un “core” si hay por lo menos min_samples a menos de la distancia eps del mismo
- Los cores que están entre sí a menos de eps se incluyen en el mismo cluster.
DBSCAN
- Se elige un punto al azar y se buscan todos los vecinos a menos de eps.
- si hay menos de min_samples, se lo clasifica como ruido (no pertenece a ningún cluster)
- si hay más que min_samples, se lo clasifica como core y se le asigna un nuevo cluster
- Para cada vecino a menos de eps
- si aún no pertenece a un cluster, se lo asigna al cluster que se acaba de crear
- si es core, se visita a sus respectivos vecinos y se repite
- si no es un core, se los clasifica como punto frontera
- El cluster crece hasta que no hay más cores a menos de eps del punto seleccionado al inicio
- Se visita otro punto que no haya sido visitado y se itera
DBSCAN
- Al finalizar hay tres tipos de
puntos: core, frontera (a menos
de eps de un core) y ruido.
- En sucesivas corridas el
algoritmo llegará siempre a los
mismo punto core y puntos
ruido.
- Los puntos frontera pueden
pertenecer a distintos clusters,
dependiendo del orden en que se
visiten los puntos.
- Es muy importante normalizar
Evaluación de clusterings
Evaluación
- Se pueden hacer distintos tipos de evaluaciones:
- Internas: utilizando scores para cuantificar la calidad de los clusters
- Externas: se compara con una clasificación pre-existente o “ground truth”
- Manuales: inspección por un humano
- Indirectas: evaluando su utilidad para cierta aplicación particular
Evaluación
- a: n° pares de puntos que están en el mismo cluster en ambas particiones.
- b: n° de pares de puntos que están en diferentes clusters en ambas particiones.
- n es el número total de puntos en el conjunto de datos.
- Cuando hay una “ground truth” adjusted rand index (ARI).
Evaluación
- a: distancia promedio entre un punto y todos los otros puntos de su mismo cluster
- b: distancia promedio entre un punto y todos los puntos del cluster más cercano
- Cuando no hay ground truth: silhouette coeficient
Evaluación
- Evaluar si el algoritmo aprendió algo útil suele ser un desafío
- En general se aplica a datos sin etiquetas y no se sabe cómo debería ser un clustering “correcto”.
- A menudo la única manera de evaluar los resultados es su inspección manual.
