{"id":9662,"date":"2021-02-16T10:45:46","date_gmt":"2021-02-16T09:45:46","guid":{"rendered":"https:\/\/www.makingscience.com\/blog\/clustering-mas-alla-de-k-means\/"},"modified":"2021-02-16T10:45:46","modified_gmt":"2021-02-16T09:45:46","slug":"clustering-mas-alla-de-k-means","status":"publish","type":"post","link":"https:\/\/www.makingscience.com\/es\/blog\/clustering-mas-alla-de-k-means\/","title":{"rendered":"Clustering: m\u00e1s all\u00e1 de k-means"},"content":{"rendered":"
Clustering: m\u00e1s all\u00e1 de k-means<\/div>\n
Clustering hace referencia a un conjunto de t\u00e9cnicas y algoritmos no supervisados que tienen como objetivo segmentar datos seg\u00fan grupos homog\u00e9neos, tambi\u00e9n llamados clusters. Dado un conjunto de puntos en un dataset, podemos aplicar estos algoritmos para clasificar cada punto en un grupo espec\u00edfico. Idealmente los puntos de un mismo cluster tienen caracter\u00edsticas similares entre s\u00ed y, al mismo tiempo, los puntos pertenecientes a clusters distintos tendr\u00e1n caracter\u00edsticas distintas. Esto, desde un punto de vista de negocio, permite sacar ventaja en una multitud de situaciones. Por ejemplo, clusterizar a tus clientes seg\u00fan sus compras y variables demogr\u00e1ficas para poder personalizar comunicaciones en base a las caracter\u00edsticas de cada cluster, o bien, ver qu\u00e9 grupos existen seg\u00fan el comportamiento que tienen los usuarios en tu web o app.<\/span> Es muy probable que lo primero que se nos venga a la cabeza cuando queremos crear clusters con nuestros datos sea la t\u00e9cnica <\/span>k<\/span><\/i>-means. Sin embargo, esta no es siempre la mejor opci\u00f3n. Un buen an\u00e1lisis previo junto con un buen entendimiento de los datos son clave para tomar la decisi\u00f3n acertada.<\/span> El algoritmo de clustering m\u00e1s conocido es <\/span>k<\/span><\/i>-means. Este algoritmo goza de una gran y bien merecida popularidad gracias a su sencillez y amplio soporte. Pero, como es razonable, es imposible que una sola t\u00e9cnica sea capaz de proporcionar una buena soluci\u00f3n para todo tipo de problemas. En este art\u00edculo vamos a introducir este y otros algoritmos.<\/span>   <\/p>\n

Cuando k<\/i>-means es la soluci\u00f3n<\/strong><\/h2>\n

Supongamos que tenemos el siguiente dataset con 2 dimensiones. Por ejemplo, imaginemos que estas variables son el peso y la altura normalizadas (de 0 a 1) de un conjunto de personas:<\/span> \"\" A simple vista se pueden diferenciar 4 grupos claramente. Esta informaci\u00f3n servir\u00e1 de entrada para <\/span>k<\/span><\/i>-means: <\/span>k<\/span><\/i>=4. Una vez el algoritmo recibe el n\u00famero de grupos deseado los pasos que sigue son sencillos:<\/span> <\/p>\n

    \n
  1. Se inicializan <\/span>k<\/span><\/i> centroides aleatoriamente, en este caso <\/span>k<\/span><\/i>=4 centroides.<\/span><\/li>\n
  2. Se clasifica cada punto del dataset calculando la distancia de cada punto a cada centroide. Cada punto pertenece al grupo cuyo centroide se encuentra m\u00e1s cercano.<\/span><\/li>\n
  3. Con los grupos creados en el paso 2, se recalculan los centroides como la media de todos los puntos del grupo. De ah\u00ed el nombre <\/span>k<\/span><\/i>-means.<\/span><\/li>\n
  4. Se repiten los pasos 2 y 3 hasta que los centroides ya no cambian demasiado por cada iteraci\u00f3n.<\/span><\/li>\n<\/ol>\n

    Para m\u00e1s detalle as\u00ed como una implementaci\u00f3n simple en python, puedes consultar <\/span>este art\u00edculo<\/span><\/a>.\u00a0\u00a0<\/span> Como vemos en la siguiente figura, <\/span>k<\/span><\/i>-means consigue segmentar el dataset tal y como lo esper\u00e1bamos:<\/span> \"\"   <\/p>\n

    \u00bfEs siempre k<\/i>-means la opci\u00f3n m\u00e1s recomendable?<\/strong><\/h2>\n

    La respuesta es no. Hay tipos de datos en los que <\/span>k<\/span><\/i>-means, por su propia naturaleza, no funciona de la forma deseada. Como hemos visto, para que <\/span>k<\/span><\/i>-means tenga un funcionamiento adecuado los centroides, <\/span>i.e.<\/span><\/i> las medias de cada cluster, tienen que estar suficientemente alejados. Adem\u00e1s, en el punto 3 del algoritmo <\/span>k<\/span><\/i>-means se recalculan los centroides calculando la media de cada grupo. Esto \u201cfuerza\u201d que los clusters tiendan a ser circulares por el hecho de que el centroide est\u00e1 justo en el centro del cluster. Pero, \u00bfqu\u00e9 pasar\u00eda si nuestros datos no son circulares, o si los centroides no est\u00e1n suficientemente alejados?<\/span>   <\/p>\n

    Gaussian Mixture Model (GMM)<\/strong><\/h3>\n

    Si los grupos que vemos a simple vista no son \u201ccirculares\u201d, puede que <\/span>k<\/span><\/i>-means no sea la opci\u00f3n a utilizar. En el siguiente dataset vemos 3 grupos claramente diferenciables a simple vista. Estos tienen forma el\u00edptica, no circular:<\/span> \"\" Para este tipo de datos, una buena opci\u00f3n podr\u00eda ser Gaussian Mixture Models (GMM). Con este algoritmo asumimos que los puntos siguen una distribuci\u00f3n Gaussiana. Esta asunci\u00f3n es menos restrictiva que suponer que son circulares como en el caso de <\/span>k<\/span><\/i>-means. De hecho, <\/span>k<\/span><\/i>-means es un caso especial de GMM donde la covarianza de cada cluster en todas las dimensiones tiende a 0. Con GMM, los clusters tienen 2 par\u00e1metros a optimizar: la media y la desviaci\u00f3n t\u00edpica. Con estos par\u00e1metros, en este ejemplo con 2 dimensiones, los clusters pueden adoptar cualquier forma el\u00edptica. En <\/span>este enlace<\/span><\/a> tienes m\u00e1s detalle, as\u00ed como una implementaci\u00f3n simple en python.<\/span> \"\" Como podemos ver en la figura de arriba, <\/span>k<\/span><\/i>-means (izquierda) en este caso no ha sido capaz de diferenciar bien los 3 grupos. En cambio, GMM (derecha) s\u00ed ha sido capaz de encontrarlos, gracias al par\u00e1metro de la desviaci\u00f3n t\u00edpica.<\/span>   <\/p>\n

    Density-Based Spatial Clustering of Applications with Noise (DBSCAN)<\/strong><\/h2>\n

    En un ejercicio de imaginaci\u00f3n, supongamos ahora que nuestros datos con las variables altura y peso tienen esta pinta:<\/span> \"\" A simple vista es f\u00e1cil distinguir 3 grupos, que se corresponden con los 3 anillos conc\u00e9ntricos que se observan. En este caso, ni <\/span>k<\/span><\/i>-means ni GMM van ser capaces de separar los 3 grupos dado que la media ideal de cada grupo se encontrar\u00eda en el mismo punto: en el centro.<\/span> En la siguiente figura, vemos precisamente c\u00f3mo los clusters que devuelven <\/span>k<\/span><\/i>-means (izquierda) y GMM (derecha) no son v\u00e1lidos para estos datos:<\/span> \"\" En este caso, utilizar el algoritmo Density-Based Spatial Clustering of Applications with Noise (DBSCAN) puede ser la opci\u00f3n correcta. Una caracter\u00edstica de este algoritmo es que no necesita recibir el n\u00famero de clusters como par\u00e1metro, sino que el propio algoritmo encuentra el n\u00famero \u00f3ptimo de clusters. El funcionamiento es sencillo:<\/span> <\/p>\n

      \n
    1. Se recibe como par\u00e1metro , que es la distancia con la que vamos a trabajar y <\/span>min_points.<\/span><\/i><\/li>\n
    2. Se empieza con un punto cualquiera del dataset y se miran los puntos que est\u00e1n a distancia de este punto. Si el n\u00famero de puntos encontrados es mayor que <\/span>min_points, <\/span><\/i>entonces el algoritmo empieza y consideramos al punto actual como el primer punto del nuevo cluster, si no, este punto se considera <\/span>ruido<\/span><\/i>.<\/span><\/li>\n
    3. Todos los puntos que est\u00e1n a distancia del punto actual se unir\u00e1n al cluster. Este proceso se repite para todos los puntos nuevos que se han a\u00f1adido al cluster.<\/span><\/li>\n
    4. Los pasos 2 y 3 se repiten hasta que todos los puntos del cluster han sido etiquetados.<\/span><\/li>\n
    5. Cuando terminamos con el primer cluster, se elige aleatoriamente otro punto no visitado anteriormente y se repite el proceso hasta que todo el dataset ha sido etiquetado, ya sea como perteneciente a un cluster o como ruido.<\/span><\/li>\n<\/ol>\n

      Para m\u00e1s detalle con este algoritmo puedes consultar el <\/span>siguiente art\u00edculo<\/span><\/a> donde tambi\u00e9n se incluye una implementaci\u00f3n sencilla en python.<\/span> En la figura de abajo vemos c\u00f3mo DBSCAN ha sido capaz de segmentar correctamente todos los puntos del dataset.<\/span> \"\"     <\/p>\n

      Cuando los datos son sparse<\/i><\/strong><\/h2>\n

      Finalmente, vamos a ver un tipo de datos diferente a los anteriores. Supongamos que tenemos un e-commerce donde vendemos productos de 30 categor\u00edas diferentes: moda, electr\u00f3nica, libros, hogar, etc. Tenemos datos de nuestros usuarios (20k usuarios) que nos indican el n\u00famero de compras ponderados\u00a0 que han realizado de cada categor\u00eda. Aqu\u00ed podemos ver un extracto de estos datos:<\/span> \"\" Como vemos, los datos son <\/span>sparse<\/span><\/i>, es decir, hay muchos ceros. Esto es debido a que, por lo general, los usuarios realizan compras de unas pocas categor\u00edas, pero no de todas. El objetivo de aplicar clustering en estos datos es conseguir obtener grupos de usuarios en base a sus compras. Idealmente, obtendremos grupos de usuarios que compran varias categor\u00edas de productos y por lo tanto tienen un comportamiento similar en nuestra web.<\/span> Si utilizamos <\/span>k<\/span><\/i>-means para clusterizar a los usuarios ocurre lo siguiente:<\/span> \"\" \"\" En la figura de arriba vemos por un lado el tama\u00f1o de cada cluster, y debajo, vemos c\u00f3mo son los centroides. Cuanto m\u00e1s intenso es el color, m\u00e1s importancia tiene esa categor\u00eda en ese cluster. Lo que ha identificado <\/span>k<\/span><\/i>-means es que hay un grupo muy numeroso (cluster 0) que casi no compra en comparaci\u00f3n con los otros. Los dem\u00e1s, aunque est\u00e9n formados por muy pocos usuarios s\u00ed tienen bastantes compras y se han agrupado en base a las diferentes categor\u00edas. Esto de cara al negocio puede que no sea muy \u00fatil ya que el objetivo es encontrar patrones de comportamiento en cuanto a las categor\u00edas para que los grupos se puedan activar de alguna manera y con <\/span>k<\/span><\/i>-means estamos descartando a 14k usuarios al meterlos en el grupo de usuarios que compran poco en vez de agruparlos tambi\u00e9n seg\u00fan las categor\u00edas que compran.<\/span>   <\/p>\n

      Non-negative Matrix Factorization (NMF)<\/strong><\/h2>\n

      Non-negative Matrix Factorization (NMF) es una t\u00e9cnica que tiene una propiedad inherente para clusterizar y es utilizada ampliamente para ello, especialmente cuando los datos de entrada son <\/span>sparse<\/span><\/i>. La idea de esta t\u00e9cnica es tratar de aproximar una matriz <\/span>V<\/span> mediante la multiplicaci\u00f3n de dos matrices no negativas, <\/span>W<\/span> y <\/span>H<\/span>:<\/span> <\/p>\n

      V=<\/b>WH<\/span><\/p>\n

      Donde <\/span>V<\/span> es nuestro dataset transpuesto, que tiene dimensiones <\/span>f x <\/span>n<\/span><\/em>, donde <\/span>f<\/span> es el n\u00famero de categor\u00edas y <\/span>n<\/span> es el n\u00famero de usuarios. Por lo tanto, la matriz resultante <\/span>W<\/span> tiene dimensiones <\/span>f x <\/span>t<\/span><\/em>, y la matriz resultante <\/span>H<\/span>, <\/span>t x <\/span>n<\/span><\/em>, siendo <\/span>t<\/span><\/em> el n\u00famero de clusters recibido como entrada del algoritmo. Las columnas de la matriz resultante <\/span>WH <\/span><\/em>son una combinaci\u00f3n lineal de los <\/span>t<\/span> clusters representados como las <\/span>t<\/span> columnas de <\/span>W<\/span>. Esto es importante ya que es la base del NMF: se asume que cada columna en <\/span>V <\/span>est\u00e1 construida a partir de un n\u00famero peque\u00f1o (<\/em><\/span>t<\/span><\/em>)<\/em> de <\/span>features<\/span><\/i> desconocidas y lo que se consigue con NMF es obtener esas <\/span>features<\/span><\/i>.<\/span> Se puede pensar en las <\/span>t<\/span><\/em> columnas de la matriz <\/span>W <\/span>como cada uno de los <\/span>t<\/span><\/em> clusters de usuarios que contienen valores para cada una de las <\/span>f<\/span><\/em> categor\u00edas. Cuanto m\u00e1s alto sea el valor de wij<\/em><\/span>\u00a0<\/span><\/em>la categor\u00eda <\/span>i<\/span><\/em> tendr\u00e1 m\u00e1s importancia en el cluster <\/span>j<\/span><\/em>. De forma equivalente, cada columna de la matriz <\/span>H<\/span><\/em> representa el peso que tiene cada cluster para cada usuario.<\/span> Siguiendo la explicaci\u00f3n anterior, en la matriz <\/span>H<\/span><\/em> tenemos la informaci\u00f3n de a qu\u00e9 cluster pertenecen los usuarios. Solo tenemos que quedarnos con el cluster que tenga m\u00e1s peso para cada usuario:<\/span> \"\" Es decir, el usuario <\/span>j<\/span><\/em> pertenece al cluster <\/span>k<\/span><\/em> que maximice la expresi\u00f3n anterior. Los centroides de cada cluster se corresponden con las columnas de <\/span>W<\/span><\/em>.<\/span> Para m\u00e1s informaci\u00f3n sobre este algoritmo, puedes consultar el <\/span>siguiente art\u00edculo<\/span><\/a>.<\/span> Tras aplicar el algoritmo a nuestro dataset, obtenemos los siguientes resultados:<\/span> \"\" \"\" Como vemos, los tama\u00f1os de los clusters son m\u00e1s uniformes y todos los clusters tienen un comportamiento asociado en cuanto a las categor\u00edas que compran, aunque hayan comprado poco. Con este resultado podr\u00edamos describir a nuestros clusters como:<\/span> <\/p>\n