La tarea fundamental de los algoritmos de clustering se basa en explotar las similaridades entre entidades para realizar agrupaciones entre ellas. Para situarnos, estas técnicas nos permiten encontrar patrones ocultos en nuestros datos, esto es, en nuestros sistemas.
El clustering, por tanto, busca encontrar los conjuntos de entidades más similares entre ellos (elementos) y lo más más disjuntos entre sí. Pero, ¿para qué nos puede servir este conjunto de técnicas?
En el sector de retail estos algoritmos nos permiten realizar tareas, no supervisadas, de customer discovery y recomendación, esto es, nos permiten descubrir relaciones entre conjuntos de elementos, no descubiertas o utilizadas hasta este momento, y que nos dan una clara ventaja competitiva sobre el resto del sector. Pero, ¿cómo puede apoyar esto a la operativa industrial?
Si bien la regresión es la técnica predictiva principal de cara a la simulación, el clustering nos va a apoyar en tareas de planificación de mantenimientos predictivos y validación de sensores remotos.
Las técnicas de clustering se basan en algoritmos no supervisados, esto es, partimos de una base de vectores (datos) para generar K conjuntos de datos similares entre sí. Esta información se puede utilizar para planificar acciones de forma agregada.
Se diferencia de los algoritmos de clasificación en que, en estos, indicamos la categorías en las que queremos que se realice la predicción (etiquetando las categorías) mientras que en los que tratamos actualmente estas categorías no están predefinidas.
Por ejemplo, para una planificación de mantenimiento predictivo, podemos encontrar agrupaciones de sensores por Mean Time Between Failures, distancia existente entre el centro de operación y el sensor, condiciones de accesibilidad, … y utilizar un algoritmo de clustering para encontrar un conjunto de agrupaciones que cumplan condiciones similares y que, por tanto, podamos planificar bajo periodos de frecuencia similares, independientemente de la marca y modelo del sensor (método tradicional).
Bajo este mismo enfoque, podemos realizar validaciones de coherencia de datos y seguridad. Supongamos que realizamos una agregación por clustering de un conjunto de datos internos (sensores propios con los que realizamos las mediciones) y externos (que nos valen de contraste). Realizamos la agrupación a través de un algoritmo de clustering y utilizamos este modelo para ir validando la agrupación en Tiempo Real. Si un elemento por alguna razón cambia de grupo en las sucesivas iteraciones pueden ocurrir dos cosas:
- El sensor esta estropeado o ha sido manipulado.
- El sensor presenta un cambio de comportamiento no planificado (no tiene por qué ser un error)
En cualquiera de los dos casos conocer esta situación es necesaria desde el punto de vista de que es necesaria una actuación.
Si bien este último ejemplo se puede resolver por otro tipo de técnicas, como clasificación, los algoritmos de clustering nos pueden aportar resultados mucho más potentes en base al descubrimiento de relaciones entre entidades no detectadas hasta este momento.
Principio de funcionamiento
Los algoritmos de clustering se basan en un concepto bastante sencillo, si bien, su implementación no lo es tanto.
Todos los algoritmos descansan sobre el concepto de similitud, es decir, como de parecidos son, y la técnica más adoptada es la del cálculo de las distancias de los vectores que definen una instancia de una entidad (vector de atributos) con respecto a otro vector que indica el centro de una agrupación.
De forma general, la cercanía se define en términos de una determinada función de distancia, que puede ser la distancia Euclídea, la matriz de correlación entre vectores, la distancia de Manhattan, el coeficiente de correlación de Pearson o cualquier función definida por el usuario y que trasforme un conjunto de vectores en valores que indiquen, para nosotros, la distancia entre ellos.
Profundizando en los algoritmos, existen dos vertientes para su implementación.
Por un lado, están los algoritmos de la familia de k-centers en los que el número de agrupaciones se determinan de antemano y al que pertenecen los algoritmos de k-mean y k-metoids.
La base de los algoritmos de la familia de k-centers es sencilla:establecer k-vectores indicando los centros de cada una de las agrupaciones y determinar para cada uno de los vectores de datos (instancias de entidades) cual es la distancia a cada center y seleccionar aquella que sea la menor para asignarle dicha agrupación.
Sin embargo, la dificultad se encuentra en detectar cuales son los vectores centrales asociados a cada agrupación para obtener el mejor resultado, esto es, el más óptimo.
Una vez visto lo anterior introduciremos un nuevo dato. Los algoritmos de clustering se pueden ver como una extensión de los algoritmos de clasificación, pero realizado en dos pasos:
1) Detección y formación de los clusters y sus centros.
2) Generación de un modelo de clasificación sobre las K agrupaciones generadas.
Los algoritmos de k-centers son algoritmos iterativos que ejecutan la siguiente secuencia de pasos en pseudo-código:
- Inicializar los centers de forma aleatoria
- Hacer
- Asignar las instancias a los distintos cluster
- Reorganizar los centers en base a la función de distancia sobre las agrupaciones establecidas para obtener un nuevo vector centro de la agrupación
- Mientras (condición de paradano satisfecha)
Las condiciones de parada más habituales son un número determinado de iteraciones, la no modificación (o modificación dentro de un umbral) de los k-centers tras realizar una iteración, o la no variación de la asignación de las instancias a las agrupaciones definidas en la iteración anterior.
Por otro lado, están los algoritmos jerárquicos (basados en árboles), aglomerativos (Botom-up) o divisivos (Top-down), donde el número de agrupaciones no está predeterminado de antemano. La forma de representar los arboles de agrupación se realiza mediante los denominados dendogramas que no dejan de ser más que una representación gráfica de un árbol de decisión.
Los algoritmos Top-Down se basan en un algoritmo de división heurístico denominado DIANA (DIvisive ANAlysis Clustering). Inicialmente, todas las instancias de datos están en el mismo cluster. Iterativamente el grupo más grande se divide en objetos individuales y, tras esto y por medio de DIANA, se elige el objeto con la máxima disimilitud promedio generando un nuevo cluster. Posteriormente reorganizamos los objetos para teniendo en cuenta el nuevo cluster y así sucesivamente hasta satisfacer una condición de parada.
Los algoritmos Bottom-up o aglomerativos parten del principio opuesto al anterior. Inicialmente, todas las instancias de datos independientes, esto es, cada una en su propio cluster. Tras esto, se elige el objeto o cluster con la máxima similitud a otro y se genera una nueva agrupación recalculando el nuevo center para esa agrupación. Se repite la operación hasta que se satisfaga la condición de parada que puede ser o que no exista ninguna agregación posible que mejore la situación actual o bien cuando hay un número suficientemente pequeño de agrupaciones.
En la próxima entrega del blog hablaremos de la última característica realmente importante que necesitamos conocer para abordar nuestro problema que es la reducción de la dimensión o la extracción de las características principales que nos permitirá reducir el volumen de nuestro problema.