La herramienta Clustering basado en densidad se basa en la detección de en qué áreas existen concentraciones de puntos y dónde están separados por áreas vacías o con escasos puntos. Los puntos que no forman parte de un clúster se etiquetan como ruido. Opcionalmente, el tiempo de los puntos se puede usar para buscar grupos de puntos que se agrupan en clústeres de espacio y tiempo.
Esta herramienta utiliza algoritmos de clustering de aprendizaje de máquina no supervisados que detectan automáticamente patrones basándose puramente en la ubicación espacial y en la distancia a un número de vecinos especificado. Estos algoritmos se consideran no supervisados porque no requieren ninguna formación sobre en qué consiste un clúster.
Sugerencia:
El clustering, el agrupamiento y la clasificación son algunas de las técnicas más utilizadas en aprendizaje de máquina. El Clustering multivariante y la herramienta Clustering multivariante restringido espacialmente también utilizan métodos no supervisados de aprendizaje de máquina para determinar los clústeres naturales presentes en sus datos. Estos métodos de clasificación se consideran no supervisados porque no requieren un conjunto de entidades previamente clasificadas para guiar o entrenar, ni para encontrar clústeres en sus datos.
Potenciales aplicaciones
Estas son algunas formas en que se puede aplicar esta herramienta:
- Las redes de suministro urbano de aguas son un importante activo subterráneo oculto. El clustering de las roturas y reventones de tuberías puede indicar problemas en ciernes. Mediante la herramienta Clustering basado en densidad, los ingenieros pueden determinar dónde se encuentran esos clústeres y tomar medidas preventivas en las zonas de alto riesgo de sus redes de suministro de aguas.
- Suponga que dispone de datos de posición de todos los tiros con enceste y sin enceste de los jugadores de la NBA. La herramienta Clustering basado en densidad puede mostrarle los diferentes patrones de posiciones de tiro con enceste y sin enceste de cada jugador. A continuación, esta información se puede usar como base para desarrollar estrategias de juego.
- Suponga que está estudiando una enfermedad concreta propagada por plagas y tiene un dataset de puntos que representa a los hogares de su área de estudio, algunas de ellas infestadas y otras no. Mediante la herramienta Clustering basado en densidad, puede determinar los mayores clústeres de hogares infestados para ayudarle a delimitar un área en la que iniciar el tratamiento y la erradicación de las plagas.
- La geolocalización de tuits después de una catástrofe natural o un ataque terrorista puede organizarse en clústeres para informar sobre las necesidades de rescate y evacuación en función del tamaño y la ubicación de los clústeres identificados.
Métodos de clustering
El parámetro Métodos de clustering de la herramienta Clustering basado en densidad ofrece tres opciones con las que se pueden encontrar clústeres en sus datos de puntos:
- Distancia definida (DBSCAN): utiliza una distancia especificada para separar los clústeres densos del ruido más disperso. El algoritmo DBSCAN es el método de clustering más rápido, pero solo es apropiado si se puede utilizar una Distancia de búsqueda muy clara, y funciona bien con todos los clústeres potenciales. Para ello, se requiere que todos los clústeres significativos presenten densidades similares. Este método también permite utilizar los parámetros Campo de tiempo e Intervalo de tiempo de búsqueda para buscar clústeres de puntos en espacio y tiempo.
- Autoajuste (HDBSCAN): utiliza toda una variedad de distancias para separar clústeres de densidades variables del ruido más disperso. El algoritmo HDBSCAN es el método de clustering que más se basa en los datos y, por tanto, requiere la menor participación del usuario.
- Escala múltiple (OPTICS): utiliza la distancia entre entidades vecinas para crear un diagrama de alcanzabilidad que, a continuación, se utiliza para separar los clústeres de densidades diferentes respecto del ruido. El algoritmo OPTICS ofrece la mayor flexibilidad en el afinamiento de los clústeres detectados, a pesar de que requiere una gran potencia de cómputo, en especial si la Distancia de búsqueda es grande. Este método también permite utilizar los parámetros Campo de tiempo e Intervalo de tiempo de búsqueda para buscar clústeres de puntos en espacio y tiempo.
Esta herramienta toma Entidades de puntos de entrada, una ruta para las Entidades de salida y un valor que representa el número mínimo de entidades requerido para considerar que existe un clúster. En función del Método de clustering seleccionado, puede ser necesario especificar parámetros adicionales, como se describe a continuación.
Entidades mínimas por clúster
Este parámetro determina el número mínimo de entidades requerido para considerar que un agrupamiento de puntos es un clúster. Por ejemplo, si tiene varios clústeres diferentes con un tamaño de entre 10 y 100 puntos y selecciona un valor de 20 en Entidades mínimas por clúster, todos los clústeres que tengan menos de 20 puntos se considerarán como ruido (porque no forman un agrupamiento lo suficientemente grande como para ser considerado un clúster), o bien se fusionan con los clústeres cercanos para satisfacer el número mínimo de entidades requerido. Por contra, al seleccionar un valor de Entidades mínimas por clúster menor del que consideraría su clúster significativo más pequeño, podría ocurrir que los clústeres significativos quedaran divididos en clústeres más pequeños. En otras palabras, cuanto más pequeño es el valor de Entidades mínimas por clúster, más clústeres se detectan. Cuanto mayor es el valor de Entidades mínimas por clúster, menos clústeres se detectan.
Sugerencia:
El valor ideal de Entidades mínimas por clúster depende de qué está intentando capturar y la pregunta que se hace en su análisis. Debe ser el agrupamiento de menor tamaño que desee considerar como un clúster significativo. Un aumento del valor de Entidades mínimas por clúster podría dar lugar a la fusión de algunos de los clústeres más pequeños.
El parámetro Entidades mínimas por clúster también es importante para el cálculo de la distancia de núcleo, que es una medida utilizada por los tres métodos a la hora de encontrar clústeres. Conceptualmente, la distancia de núcleo de cada punto es una medida de la distancia que es necesario recorrer desde cada punto hasta el número mínimo de entidades. Por tanto, si se elige un valor elevado en Entidades mínimas por clúster, la distancia de núcleo correspondiente será mayor. Por tanto, si se elige un valor pequeño en Entidades mínimas por clúster, la distancia de núcleo correspondiente será menor. La distancia de núcleo está relacionada con el parámetro Distancia de búsqueda, que se utiliza tanto en el método Distancia definida (DBSCAN) como en el método Escala múltiple (OPTICS).
Distancia de búsqueda (DBSCAN y OPTICS)
En Distancia definida (DBSCAN), si el número de Entidades mínimas por clúster se encuentra dentro de la Distancia de búsqueda a partir de un punto en particular, ese punto se marcará como punto de núcleo y se incluirá en un clúster, junto con todos los puntos dentro de la distancia de núcleo. Un punto de borde es un punto que se encuentra dentro de la distancia de búsqueda de un punto de núcleo, pero no tiene el número mínimo de entidades dentro de la distancia de búsqueda. Cada clúster resultante se compone de puntos de núcleo y puntos de borde, donde los puntos de núcleo tienden a estar en el centro del clúster y los puntos de borde se encuentran en el exterior. Si un punto no tiene el número mínimo de entidades dentro de la distancia de búsqueda y no está dentro de la distancia de búsqueda de otro punto de núcleo (es decir, no es ni un punto de núcleo ni un punto de borde), se marca como punto de ruido y no se incluye en ningún clúster.
En el caso de Escala múltiple (OPTICS), el valor de Distancia de búsqueda se trata como la distancia máxima que se comparará con la distancia de núcleo. Escala múltiple (OPTICS) utiliza un concepto de distancia mínima alcanzable que es la distancia desde un punto hasta su vecino más cercano que aún no se haya visitado en la búsqueda. (Nota: OPTICS es un algoritmo ordenado que comienza con la entidad que presenta el Id. más bajo y va desde este punto al siguiente para crear un diagrama. El orden de los puntos es fundamental para el resultado). Escala múltiple (OPTICS) busca todas las distancias vecinas dentro de la Distancia de búsqueda especificada, comparando cada una de estas distancias con la distancia de núcleo. Si cualquier distancia es menor que la distancia de núcleo, se asigna a la entidad esa distancia de núcleo como su distancia de alcanzabilidad. Si todas las distancias son mayores que la distancia de núcleo, la más pequeña de estas distancias se asigna como distancia de alcanzabilidad. Si no hay más puntos dentro de la distancia de búsqueda, el proceso se reinicia en un nuevo punto que no se ha visitado anteriormente. En cada iteración, las distancias de alcanzabilidad se recalculan y se ordenan. La menor de las distancias se utiliza para la distancia de alcanzabilidad final de cada punto. A continuación, estas distancias de alcanzabilidad se utilizan para crear el diagrama de alcanzabilidad, que es un diagrama ordenado de las distancias de alcanzabilidad utilizadas para detectar los clústeres.
Tanto para Distancia definida (DBSCAN) como para Escala múltiple (OPTICS), si no se especifica ninguna distancia, la Distancia de búsqueda predeterminada es la distancia de núcleo más alta encontrada en el dataset, excluidas aquellas distancias de núcleo que se encuentren dentro del 1 % superior (en otras palabras, se excluyen las distancias de núcleo más extremas).
Clustering en espacio y tiempo (DBSCAN y OPTICS)
En dos de los métodos de clustering, se puede proporcionar el tiempo de cada punto en el parámetro Campo de tiempo. Si se proporciona, la herramienta buscará clústeres de puntos cercanos entre sí en espacio y tiempo. El parámetro Intervalo de tiempo de búsqueda es análogo a la distancia de búsqueda y se utiliza para determinar los puntos de núcleo, los puntos de borde y los puntos de ruido de los clústeres de espacio-tiempo.
Para Distancia definida (DBSCAN), al buscar miembros de clústeres, las Entidades mínimas por clúster se deben encontrar dentro de los valores de Distancia de búsqueda e Intervalo de tiempo de búsqueda para que sean un punto de núcleo de un clúster de espacio-tiempo.
En la siguiente imagen, la distancia de búsqueda es de 1 milla, el intervalo de tiempo de búsqueda es de 3 días y el número mínimo de entidades es 4. El punto P es un punto de núcleo porque hay cuatro puntos dentro de la distancia y el intervalo de tiempo de búsqueda (incluido él mismo). El punto Q es un punto de borde porque solo hay tres puntos dentro de la distancia y el intervalo de tiempo de búsqueda, pero el punto se encuentra dentro de la distancia y el intervalo de tiempo de búsqueda de un punto central del clúster (el punto con marca de tiempo 1/5/2021). Los puntos C y D son puntos de ruido porque no son puntos de núcleo ni puntos de borde del clúster, y todos los demás puntos (incluidos P y Q) forman un clúster único.
Para Escala múltiple (OPTICS), todos los puntos que queden fuera del rango de Intervalo de tiempo de búsqueda de un punto se excluirán cuando el punto calcule su distancia de núcleo, busque todas las distancias vecinas dentro del valor de Distancia de búsqueda especificado y calcule la distancia de alcanzabilidad.
En la siguiente imagen, la distancia de búsqueda es de 2 millas, el intervalo de tiempo de búsqueda es de 3 días y el número mínimo de entidades es 4. La distancia de núcleo del punto P se calcula omitiendo el punto q3 porque está fuera del intervalo de tiempo de búsqueda. En este caso, la distancia de núcleo de P es igual a la distancia de alcanzabilidad de P.
La siguiente imagen muestra el cálculo de la distancia de alcanzabilidad cuando ya se han visitado algunos puntos vecinos. Los puntos q1, q2 y q4 se omitieron porque se visitaron anteriormente y puntos q3 y q5 se omitieron porque están fuera de la ventana de tiempo de búsqueda.
Diagrama de alcanzabilidad (OPTICS)
Una vez calculadas todas las distancias de alcanzabilidad de todo el dataset, se construye un diagrama de alcanzabilidad que ordena las distancias y revela la estructura de clustering de los puntos.
La presencia de valles en el diagrama de alcanzabilidad implica que es necesario recorrer una distancia corta de un punto al siguiente. Por tanto, los valles representan clústeres diferenciados dentro del patrón de puntos. Cuanto más denso es un clúster, menores serán las distancias de alcanzabilidad, y más bajo es el valle en el diagrama (el clúster de color rosa, por ejemplo, es el más denso del ejemplo anterior). Los clústeres menos densos presentan distancias de alcanzabilidad mayores y mayores valles en el diagrama (el clúster en verde oscuro, por ejemplo, es el menos denso del ejemplo anterior). Los picos representan las distancias que es necesario recorrer para viajar de un clúster a otro, o de un clúster a ruido y de nuevo a un clúster, en función de la configuración del conjunto de puntos.
El diagrama de alcanzabilidad puede presentar mesetas si la Distancia de búsqueda es menor que la distancia de núcleo más grande. Un aspecto clave de utilizar el método de clustering OPTICS es determinar cómo detectar los clústeres en el diagrama de alcanzabilidad, lo cual se realiza mediante el parámetro Sensibilidad de clúster.
Sensibilidad de clúster (OPTICS)
El parámetro Sensibilidad de clúster determina cómo la forma (tanto la pendiente como la altura) de los picos dentro del diagrama de alcanzabilidad se utilizará para separar los clústeres. Un valor de Sensibilidad de clúster muy elevado (cercano a 100) tratará incluso el pico más pequeño como una separación entre clústeres, lo que resulta en un mayor número de clústeres. Un valor deSensibilidad de clúster muy bajo (cercano a 0) tratará únicamente los picos más inclinados y elevados como una separación entre clústeres, lo que resulta en un menor número de clústeres.
El valor predeterminado de Sensibilidad de clúster se calcula como el umbral en el cual agregar más clústeres no agrega información adicional; se basa en la Divergencia de Kullback-Leibler entre el diagrama de alcanzabilidad original y el diagrama de alcanzabilidad suavizado que se obtiene tras el clustering.
Comparación de los métodos
Aunque solo Escala múltiple (OPTICS) utiliza el diagrama de alcanzabilidad para detectar clústeres, el diagrama puede usarse para explicar conceptualmente las diferencias entre estos métodos. A modo de ilustración, el diagrama de alcanzabilidad que aparece a continuación se utiliza para explicar las diferencias entre los 3 métodos. El diagrama revela clústeres con distintas densidades y distancias de separación. Exploraremos el resultado de usar cada uno de los métodos de clustering con estos datos ilustrativos.
Con Distancia definida (DBSCAN), imagine que dibuja una línea a través del diagrama de alcanzabilidad en la Distancia de búsqueda especificada. Las áreas situadas por debajo de la Distancia de búsqueda representan clústeres, mientras que los picos situados por encima de la Distancia de búsqueda representan puntos de ruido.Distancia definida (DBSCAN) es el método de clustering más rápido, pero solo es apropiado si se puede utilizar una Distancia de búsqueda muy clara como valor de corte y esta Distancia de búsqueda funciona bien con todos los clústeres. Para ello, se requiere que todos los clústeres significativos presenten densidades similares.
Con Autoajuste (HDBSCAN), las distancias de alcanzabilidad son como niveles anidados de clústeres. Cada nivel de clustering resultaría en la detección de un conjunto de clústeres diferente. Autoajuste (HDBSCAN) elige qué nivel de clústeres de cada serie de clústeres anidados creará óptimamente los clústeres más estables, incorporando tantos miembros como sea posible sin incorporar ruido. Para más información sobre el algoritmo, consulte la excelente documentación de los creadores de HDBSCAN. Autoajuste (HDBSCAN) es el método de clustering que más se basa en los datos y, por tanto, requiere la menor participación del usuario.
En Escala múltiple (OPTICS), el trabajo de detección de clústeres no se basa en una distancia en particular, sino en los picos y valles dentro del diagrama. Digamos que cada pico tiene un nivel que puede ser Pequeño, Mediano o Grande.
En esencia, cuando se elige un valor de Sensibilidad de clúster muy elevado, todos los picos, ya sean pequeños o grandes, actuarán como separaciones entre clústeres (lo que resulta en un mayor número de clústeres).
Al seleccionar un valor moderado en Sensibilidad de clúster, se utilizarán los picos medianos y grandes, pero no los picos pequeños.
Si se selecciona un valor muy bajo en Sensibilidad de clúster, solo se utilizarán los picos grandes, lo que resulta en la detección del mínimo número posible de clústeres.
Escala múltiple (OPTICS) ofrece la mayor flexibilidad en el afinamiento de los clústeres detectados, aunque también es el más lento de los tres métodos de clustering.
Resultados
Esta herramienta produce una clase de entidad de salida con un nuevo campo de tipo entero CLUSTER_ID, que le muestra de qué clúster es miembro cada entidad. La representación en pantalla predeterminada se basa en el campo COLOR_ID. Si hay varios clústeres, se asigna un color a cada uno. Los colores se asignarán y repetirán de forma que cada clúster sea visualmente diferente de sus clústeres vecinos.
Si el Método de clustering elegido fue Autoajuste (HDBSCAN), la clase de entidad de salida también contendrá estos campos: PROB, que es la probabilidad a la que pertenece la entidad en su grupo asignado; OUTLIER, que designa a la entidad quizá un valor atípico dentro de su propio clúster (cuanto mayor sea el valor, la entidad tendrá mayor probabilidad de ser un valor atípico) y EXEMPLAR, que denota las entidades más prototípicas o más representativas de cada clúster.
Esta herramienta también crea mensajes y gráficos para ayudarle a comprender las características de los clústeres identificados. Puede acceder a los mensajes desplazándose sobre la barra de progreso, haciendo clic en el botón emergente y ampliando la sección Mensajes en el panel Geoprocesamiento. También puede acceder a los mensajes de la anterior ejecución de la herramienta Clustering basado en densidad a través del historial de geoprocesamiento. Los gráficos están disponibles desde el panel Contenido.
Además del diagrama de alcanzabilidad que se crea cuando se elige Escala múltiple (OPTICS), todos los métodos de clustering crean también un gráfico de barras que presenta todos los Id. de clúster únicos. Este diagrama se puede utilizar para seleccionar fácilmente todas las entidades pertenecientes a un clúster específico, así como para explorar el tamaño de cada uno de los clústeres.
Recursos adicionales
Para obtener más información sobre DBSCAN:
- Birant, D. & Kut, A. (2007, January). "ST-DBSCAN: An algorithm for clustering spatial–temporal data." En Data & Knowledge Engineering (Vol 60, No. 1, pp. 208-221). https://doi.org/10.1016/j.datak.2006.01.013
- Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (1996, agosto). "A density-based algorithm for discovering clusters in large spatial databases with noise." En Kdd (Vol. 96, No. 34, pp. 226-231).
Para obtener más información sobre HDBSCAN:
- Campello, R. J., Moulavi, D., & Sander, J. (2013, abril). "Density-based clustering based on hierarchical density estimates." En Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 160-172). Springer, Berlín, Heidelberg.
Para obtener más información sobre OPTICS:
- Agrawal, K. P., Garg, S., Sharma, S., & Patel, P. (2016, noviembre). "Development and validation of OPTICS based spatio-temporal clustering technique." En Information Sciences (Vol 369, pp. 388-401). https://doi.org/10.1016/j.ins.2016.06.048.
- Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (1999, junio). "OPTICS: ordering points to identify the clustering structure." En ACM Sigmod record (Vol. 28, No. 2, pp. 49-60). ACM.