Camelias
Contenidos
Camelias con sklearn
Hay muchas cosas para explorar y aprender en scikit-learn, también conocido como sklearn, como puede apreciarse en el índice de su documentación, y en ese sentido les recuerdo el diagrama de flujo que proponen para ver qué hay disponible.
Sklearn propone varias técnicas para el aprendizaje no supervisado, entre las que se encuentran las técnicas de agrupamiento (clustering). A su vez, dentro de agrupamiento hay varios métodos entre los que se encuentran camelias (k-means en inglés) y métodos jerárquicos.
En cualquier caso, es muy interesante leer los comentarios de cada método, por ejemplo si usar PCA antes de camelias. A propósito, sklearn no incluye PCA en agrupamiento, a diferencia del libro de Gareth & Co.
Tanto en camelias como en los métodos jerárquicos, la idea es agrupar elementos similares, y uno de los problemas es cómo medir la similitud. Si representamos la similitud entre dos datos mediante un número, al que podemos llamar “distancia”, nos remitimos a problemas de grafos finitos, algunos de los cuales son clásicos.
Por ejemplo, en camelias uno quiere encontrar $k$ puntos que podemos llamar “centros de grupo”, relacionar cada dato con exactamente uno de esos centros y tratar de minimizar la suma sobre los grupos de las distancias al centro respectivo. Se trata de un problema “NP completo” en general, es decir, así como en el problema del viajante, no se conocen algoritmos eficientes para resolverlo. Sólo podemos apelar a heurísticas más o menos razonables o efectivas, entre las que se incluyen técnicas aleatorias: el algoritmo más común para camelias es elegir (más o menos) aleatoriamente los $k$ centros iniciales y quedarse con el mejor resultado.
Además de lo que está en Gareth & Co. y la documentación de sklearn sobre camelias, no está de más mirar el artículo de Wikipedia, que tiene mucha información y referencias.
Por otro lado, en los métodos jerárquicos se van juntando los datos “desde abajo”, empezando con grupos de dos. Desde la teoría la dificultad es qué definir como distancia entre dos grupos, y desde el algoritmo cómo recalcular las distancias a medida que se van modficando los grupos.
Como muestran los ejemplos, otro problema de las técnicas de agrupamiento es que no sabemos en cuántos grupos se dividen los datos. Esa cantidad se impone a priori en camelias y a posteriori en agrupamiento, pero en ningún caso hay una regla precisa y confiable para la elección, se hace a “ojo de buen cubero”.
Del dicho al hecho
Dada la gran variedad de ejemplos con gráficos que hay en la documentación de sklearn, me pareció mejor no repetir lo que está allí, y voy a restringirme a ejemplos de camelias que puse en el directorio (¡ejem!) camelias, a su vez dentro del directorio estadística en Google Drive.
Vale la pena mencionar que el método
KMeans
de sklearn pone por defecto $k = 8$ grupos, lo que se puede modificar con la opción n_clusters y hace $10$ simulaciones, modificable con la opción n_init.
Gareth & Co. sugieren hacer entre $20$ o $50$ simulaciones.
Por supuesto, como se trata de un método aleatorio los resultados varían en cada ejecución del algoritmo.
En el libro de Gareth & Co., camelias se introduce en la sección 10.3.1 con un ejemplo simulado, en la sección 10.5.1 da otro ejemplo simulado y hacia el final de la sección 10.6 trabaja brevemente con la base NCI60, que tiene 64 datos cada uno con 6830 características, de los que se sabe que se agrupan en 14 tipos de cáncer, usando $k = 4$ en camelias.
Para evitar los ejemplos simulados, como primer ejemplo de camelias copié un ejemplo de sklearn en el que se trabaja con la base “iris”. Hice mínimos cambios al original, siendo el más importante la modificación de la instrucción final.
El segundo ejemplo es el trabajo sobre la base NCI60.
Hice dos versiones, una
sin estandarizar el desvío, con -nostd al final del nombre, y otra
normalizada, con -std al final del nombre.
En ambas versiones se muestran cuatro gráficos haciendo la proyección sobre las tres primeras componentes principales: se comparan los grupos originales (conocidos), los 8 grupos por defecto de sklearn, 3 grupos y finalmente 14 grupos como se sabe que debe ser.
Para hacer la comparación gráfica, apliqué un algoritmo que explico más abajo, y que necesita de los archivos combinar.py y mwmatching.py.
Por completitud y también para evitar errores, incluí en la carpeta de camelias las bases de datos que usé, iris.csv y las dos de NCI60, nci.data.csv y nci.label.csv.
Divagues sobre algoritmos
El algoritmo de Kruskal
Como mencioné, una versión de camelias en teoría de grafos es un problema NP difícil.
Esto llama la atención especialmente en los métodos jerárquicos, que en cierta forma usan una generalización del algoritmo de Kruskal para encontrar un mínimo árbol generador.
El algoritmo de Kruskal usa la técnica codiciosa (“greedy”): a partir del grafo sin arista va eligiendo siempre la arista más corta (de menor costo) para incorporar, rechazándola si se forma un ciclo, resultando en un algoritmo que es del orden de $n \log n$ (si hay $n$ vértices en el grafo), bien lejos de la completitud NP.
Como es un tema que me intriga, incluyo un archivo pdf con una “película” ilustrando el algoritmo de Kruskal. Se puede observar que es muy similar a los métodos jerárquicos, sólo que en esos métodos se recalcula la distancia entre grupos y cuando hay muchos datos el cálculo de todas las distancias puede ser computacionalmente imposible.
Máximo emparejamiento pesado
Cuando en camelias se trabaja con distintas cantidad de grupos (distintos $k$) o aún al hacer varias simulaciones con un mismo $k$, a veces se hace difícil comparar los resultados obtenidos, y de alguna manera parece razonable tratar de compatibilizar los resultados.
Una posibilidad es definir un grafo teniendo como vértices a los grupos obtenidos en dos aplicaciones de camelias, unir los vértices con aristas donde el peso es la cantidad de datos comunes en cada grupo, y luego encontrar un emparejamiento (“matching”) entre los grupos de máximo peso. De esta forma podemos dar el mismo color a los grupos emparejados, dejando un color distinto para los grupos que no tienen compañero.
En este caso particular resulta un emparejamiento en un grafo bipartido que se resuelve en forma más sencilla que el caso general, pero no demasiado: la complejidad en cualquier caso no supera el orden de $n^3$. En los ejemplos usé el módulo combinar.py que a su vez usa una versión en Python de Joris van Rantwijk.
Otra vez, esto suena bastante a lo que se hace en camelias o los métodos jerárquicos. De hecho, tal vez se pueda usar alguna de esas técnicas para elegir los colores comunes (formando los grupos), o al revés, usar el algoritmo de máximo emparejamiento para agrupar datos. ¿Tarea para el hogar?