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.
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.
Aplicaciones potenciales
Estas son algunas formas en que se podría 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. El 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
La herramienta Clustering basado en densidad ofrece tres Métodos de clustering diferentes con los que 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.
- 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.
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 (obligatorio con todos los métodos)
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. En contraste, 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. En los límites de los clústeres, los puntos tendrán distancias de núcleo elevadas (y, probablemente, no se incluirán en un clúster). 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 no se encuentra dentro de la Distancia de búsqueda a partir de un punto en particular, ese punto se marcará como ruido. En otras palabras, si la distancia de núcleo (la distancia que se debe recorrer para alcanzar el número mínimo de entidades) de una entidad es mayor que la Distancia de búsqueda, el punto se marca como ruido. La Distancia de búsqueda, cuando se utiliza Distancia definida (DBSCAN), se trata como valor de corte de la búsqueda.
En el caso de Escala múltiple (OPTICS), la 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áxima 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 de OID 0 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. A continuación, estas distancias 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).
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 de Sensibilidad 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:
- Ester, M., Kriegel, H. P., Sander, J. y Xu, X. (1996, agosto). A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd (Vol. 96, No. 34, pp. 226-231).
Para obtener más información sobre HDBSCAN:
- Campello, R. J., Moulavi, D. y Sander, J. (2013, abril). Density-based clustering based on hierarchical density estimates. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 160-172). Springer, Berlín, Heidelberg.
Para obtener más información sobre OPTICS:
- Ankerst, M., Breunig, M. M., Kriegel, H. P. y Sander, J. (1999, junio). OPTICS: ordering points to identify the clustering structure. In ACM Sigmod record (Vol. 28, No. 2, pp. 49-60). ACM.