Guía del algoritmo de agrupación DBSCAN

En la ciencia de datos y el aprendizaje automático, la capacidad de descubrir patrones ocultos y agrupar puntos de datos similares es una habilidad importante. Los algoritmos de agrupación desempeñan un papel clave en este proceso. 

La agrupación es una técnica fundamental del aprendizaje automático y la ciencia de datos que consiste en agrupar puntos de datos similares. Es un método de aprendizaje no supervisado, lo que significa que no requiere datos etiquetados para encontrar patrones. 

El objetivo principal de la agrupación es:

• Simplificar grandes conjuntos de datos en subgrupos significativos
• Identificar agrupaciones naturales en los datos
• Revela pautas y estructuras ocultas

Aunque existen numerosos algoritmos de agrupación (puede que hayas oído hablar de K-means o de la agrupación jerárquica), DBSCAN ofrece ventajas únicas. Como método basado en la densidad, DBSCAN tiene varios puntos fuertes:

1. Flexibilidad en la forma del racimo
2. Sin número predefinido de agrupaciones
3. Manejo del ruido
4. Visión basada en la densidad

En este artículo, veremos qué es el algoritmo DBSCAN, cómo funciona, cómo implementarlo en Python y cuándo utilizarlo en tus proyectos de ciencia de datos.

¿Qué es DBSCAN?

DBSCAN, que significa Agrupación Espacial Basada en la Densidad de Aplicaciones con Ruido, es un potente algoritmo de agrupación que agrupa puntos que están muy juntos en el espacio de datos. A diferencia de otros algoritmos de agrupación, DBSCAN no requiere que especifiques de antemano el número de conglomerados, lo que lo hace especialmente útil para el análisis exploratorio de datos.

El algoritmo funciona definiendo los conglomerados como regiones densas separadas por regiones de menor densidad. Este enfoque permite al DBSCAN descubrir conglomerados de forma arbitraria e identificar los valores atípicos como ruido.

El DBSCAN gira en torno a tres conceptos clave:

1. Puntos básicos: Son puntos que tienen al menos un número mínimo de otros puntos (MinPts) a una distancia determinada (ε o épsilon).
2. Puntos fronterizos: Son puntos que están dentro de la distancia ε de un punto central, pero que no tienen vecinos MinPts.
3. Puntos de ruido: Son puntos que no son ni puntos centrales ni puntos fronterizos. No están lo suficientemente cerca de ningún cúmulo como para ser incluidos.

Imagen del autor

El diagrama anterior ilustra estos conceptos. Los puntos centrales (azules) forman el corazón de los conglomerados, los puntos fronterizos (naranjas) están en el borde de los conglomerados, y los puntos de ruido (rojos) están aislados.

DBSCAN utiliza dos parámetros principales:

• ε (épsilon): La distancia máxima entre dos puntos para que se consideren vecinos.
• MinPts: El número mínimo de puntos necesarios para formar una región densa.

Ajustando estos parámetros, puedes controlar el modo en que el algoritmo define los conglomerados, lo que le permite adaptarse a distintos tipos de conjuntos de datos y requisitos de conglomeración.

En la siguiente sección, veremos cómo funciona el algoritmo DBSCAN, explorando su proceso paso a paso para identificar clusters en los datos.

¿Cómo funciona el DBSCAN?

DBSCAN funciona examinando la vecindad de cada punto del conjunto de datos. El algoritmo sigue un proceso paso a paso para identificar los conglomerados basándose en la densidad de los puntos de datos. Veamos cómo funciona DBSCAN:

1. Selección de parámetros
• Elige ε (épsilon): La distancia máxima entre dos puntos para que se consideren vecinos.
• Elige MinPts: El número mínimo de puntos necesarios para formar una región densa.
2. Selecciona un punto de partida
• El algoritmo comienza con un punto arbitrario no visitado del conjunto de datos.
3. Examina el barrio
• Recupera todos los puntos dentro de la distancia ε del punto inicial.
• Si el número de puntos vecinos es inferior a MinPts, el punto se etiqueta como ruido (por ahora).
• Si hay al menos puntos MinPts dentro de una distancia ε, el punto se marca como punto núcleo, y se forma un nuevo conglomerado.
4. Expandir el Clúster
• Todos los vecinos del punto central se añaden al clúster.
• Para cada uno de estos vecinos:
• Si es un punto central, sus vecinos se añaden al conglomerado recursivamente.
• Si no es un punto central, se marca como punto fronterizo y la expansión se detiene.
5. Repite el proceso
• El algoritmo se desplaza al siguiente punto no visitado del conjunto de datos.
• Los pasos 3-4 se repiten hasta que se hayan visitado todos los puntos.
6. Finalizar las Agrupaciones
• Una vez procesados todos los puntos, el algoritmo identifica todos los conglomerados.
• Los puntos etiquetados inicialmente como ruido pueden ser ahora puntos fronterizos si están a ε de distancia de un punto central.
7. Manipulación del ruido
• Los puntos que no pertenecen a ningún conglomerado permanecen clasificados como ruido.

Este proceso permite al DBSCAN formar conglomerados de formas arbitrarias e identificar los valores atípicos con eficacia. La capacidad del algoritmo para encontrar conglomerados sin especificar de antemano el número de conglomerados es uno de sus puntos fuertes.

Es importante señalar que la elección de ε y MinPts puede afectar significativamente a los resultados de la agrupación. En la siguiente sección, hablaremos de cómo elegir eficazmente estos parámetros e introduciremos métodos como el gráfico de distancia k para la selección de parámetros.

Conceptos y parámetros clave de DBSCAN

Para comprender plenamente cómo DBSCAN forma agrupaciones, es importante entender dos conceptos clave: la alcanzabilidad de la densidad y la conectividad de la densidad.

Alcanzabilidad de la densidad

Un punto q es densamente alcanzable desde un punto p si:

1. p es un punto central (tiene al menos MinPts a una distancia ε)

2. Existe una cadena de puntos p = p₁, ..., p_n = q donde cada p_i+1 es directamente alcanzable en densidad desde p_i.

En términos más sencillos, puedes llegar a q desde p pasando por puntos centrales, donde cada paso no es mayor que ε.

Conectividad de la densidad

Dos puntos p y q están conectados por densidad si existe un punto o tal que tanto p como q son alcanzables por densidad desde o.

La conectividad de densidad es la base para formar clusters en DBSCAN. Todos los puntos de un conglomerado están conectados mutuamente por densidad, y si un punto está conectado por densidad a cualquier punto del conglomerado, también pertenece a ese conglomerado.

Elegir los parámetros DBSCAN

La eficacia de DBSCAN depende en gran medida de la elección de sus dos parámetros principales: ε (épsilon) y MinPts. He aquí cómo enfocar la selección de estos parámetros:

Seleccionar ε (épsilon)

El parámetro ε determina la distancia máxima entre dos puntos para que se consideren vecinos. Para elegir una ε adecuada:

1. Utiliza el conocimiento del dominio: Si tienes una idea de qué distancia es significativa para tu problema concreto, utilízala como punto de partida.

2. Gráfico de distancia K: Se trata de un enfoque más sistemático:

• Calcula la distancia al k-ésimo vecino más próximo de cada punto (donde k = MinPts).
• Traza estas distancias k en orden ascendente.
• Busca un "codo" en el gráfico, un punto en el que la curva empiece a nivelarse.
• El valor ε en este codo suele ser una buena elección.

Seleccionar MinPts

MinPts determina el número mínimo de puntos necesarios para formar una región densa. Aquí tienes algunas pautas:

1. Regla general: Un buen punto de partida es establecer MínPts = 2 * núm_características, donde núm_características es el número de dimensiones de tu conjunto de datos.

2. Consideración del ruido: Si tus datos tienen ruido o quieres detectar conglomerados más pequeños, tal vez quieras disminuir MinPts.

3. Tamaño del conjunto de datos: Para conjuntos de datos más grandes, puede que necesites aumentar MinPts para evitar crear demasiados clusters pequeños.

Recuerda que la elección de los parámetros puede afectar significativamente a los resultados. A menudo es beneficioso experimentar con distintos valores y evaluar los conglomerados resultantes para encontrar el que mejor se ajuste a tu conjunto de datos y problema específicos.

Implementación de DBSCAN en Python

En esta sección, veremos la implementación de DBSCAN utilizando Python y la biblioteca scikit-learn. Utilizaremos el conjunto de datos Hacer Lunas para demostrar el proceso.

Configurar el entorno

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors

Estas importaciones proporcionan las herramientas necesarias para la manipulación de datos, la visualización, la creación de conjuntos de datos y la aplicación del algoritmo DBSCAN.

Generar datos de muestra

X, _ = make_moons(n_samples=200, noise=0.05, random_state=42)

Este código crea un conjunto de datos sintéticos utilizando la funciónmake_moons de scikit-learn. He aquí una breve descripción del conjunto de datos:

La función hacer_lunas genera una clasificación binario que se asemeja a dos medias lunas intercaladas. En nuestro caso:

• Creamos 200 muestras (n_samples=200)
• Añadimos una pequeña cantidad de ruido gaussiano (noise=0.05) para que el conjunto de datos sea más realista
• Fijamos random_state=42 para la reproducibilidad

Este conjunto de datos es especialmente útil para demostrar el DBSCAN porque:

1. Tiene una forma no convexa que muchos agrupación algoritmos (como K-means) tendrían problemas
2. Los dos grupos están claramente separados pero tienen una forma compleja
3. El ruido añadido proporciona un escenario más realista en el que algunos puntos podrían clasificarse como valores atípicos

Vamos a visualizar este conjunto de datos para comprender mejor su estructura:

# Visualize the dataset
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1])
plt.title('Moon-shaped Dataset')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Esto te mostrará las dos formas de media luna intercaladas en nuestro conjunto de datos, como se muestra a continuación

Determinación del parámetro épsilon

Utilizamos el método del gráfico de distancia k para ayudar a elegir un valor épsilon adecuado:

1. Definimos una función plot_k_distance_graph que calcula la distancia al k-ésimo vecino más próximo de cada punto.
2. Las distancias se ordenan y se representan gráficamente.
3. Buscamos un "codo" en el gráfico resultante para elegir épsilon.

# Function to plot k-distance graph
def plot_k_distance_graph(X, k):
    neigh = NearestNeighbors(n_neighbors=k)
    neigh.fit(X)
    distances, _ = neigh.kneighbors(X)
    distances = np.sort(distances[:, k-1])
    plt.figure(figsize=(10, 6))
    plt.plot(distances)
    plt.xlabel('Points')
    plt.ylabel(f'{k}-th nearest neighbor distance')
    plt.title('K-distance Graph')
    plt.show()
# Plot k-distance graph
plot_k_distance_graph(X, k=5)

Salida

En nuestro ejemplo, basándonos en el gráfico de distancia k, elegimos un épsilon de 0,15.

Realizar la agrupación DBSCAN

Utilizamos la implementación DBSCAN de scikit-learn:

1. Fijamos epsilon=0.15 basándonos en nuestro gráfico de distancia k.
2. Establecemos min_samples=5 (2 * num_características, ya que nuestros datos son 2D).
3. Ajustamos el modelo a nuestros datos y predecimos las agrupaciones.

# Perform DBSCAN clustering
epsilon = 0.15  # Chosen based on k-distance graph
min_samples = 5  # 2 * num_features (2D data)
dbscan = DBSCAN(eps=epsilon, min_samples=min_samples)
clusters = dbscan.fit_predict(X)

Visualizar los resultados

Creamos un gráfico de dispersión de nuestros puntos de datos, coloreándolos según los conglomerados asignados. Los puntos clasificados como ruido suelen tener un color diferente (a menudo negro).

# Visualize the results
plt.figure(figsize=(10, 6))
scatter = plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.colorbar(scatter)
plt.title('DBSCAN Clustering Results')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Salida

Interpretar los resultados

Por último, imprimimos el número de conglomerados encontrados y el número de puntos clasificados como ruido. Esto nos da un resumen rápido de los resultados de la agrupación.

# Print number of clusters and noise points
n_clusters = len(set(clusters)) - (1 if -1 in clusters else 0)
n_noise = list(clusters).count(-1)
print(f'Number of clusters: {n_clusters}')
print(f'Number of noise points: {n_noise}')

Salida

Número de grupos: 2

Número de puntos de ruido: 5

Esta aplicación proporciona un flujo de trabajo completo, desde la generación de datos hasta la interpretación de los resultados. Es importante tener en cuenta que, en situaciones reales, sustituirías la generación de datos de muestra por la carga y preprocesamiento de tu conjunto de datos real.

Recuerda que la clave del éxito de la agrupación DBSCAN suele estar en la selección adecuada de los parámetros. No dudes en experimentar con distintos valores de épsilon y min/muestras para encontrar el que mejor se ajuste a tu conjunto de datos específico.

DBSCAN frente a K-Means

Aunque tanto DBSCAN como K-Means son algoritmos de agrupación populares, tienen características distintas que los hacen adecuados para distintos tipos de datos y casos de uso. Comparemos estos dos algoritmos para comprender cuándo utilizar cada uno.

Comparación visual

Para ilustrar estas diferencias, apliquemos ambos algoritmos a nuestro conjunto de datos con forma de luna

from sklearn.cluster import KMeans

# DBSCAN clustering
dbscan = DBSCAN(eps=0.15, min_samples=5)
dbscan_labels = dbscan.fit_predict(X)

# K-Means clustering
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans_labels = kmeans.fit_predict(X)

# Visualize the results
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(15, 6))

ax1.scatter(X[:, 0], X[:, 1], c=dbscan_labels, cmap='viridis')
ax1.set_title('DBSCAN Clustering')

ax2.scatter(X[:, 0], X[:, 1], c=kmeans_labels, cmap='viridis')
ax2.set_title('K-Means Clustering')

plt.show()

Este código aplica tanto DBSCAN como K-Means a nuestro conjunto de datos y visualiza los resultados uno al lado del otro.

Salida

Verás que

1. DBSCAN identifica correctamente las dos formas de media luna como conglomerados separados.
2. K-Means tiene problemas con la forma no convexa, y a menudo divide una luna en dos grupos o combina partes de ambas lunas en un grupo.
3. DBSCAN puede identificar algunos puntos como ruido (normalmente coloreados de forma diferente), mientras que K-Means asigna cada punto a un conglomerado.

¿Cuándo utilizar DBSCAN?

Ahora que hemos visto cómo funciona DBSCAN y lo hemos comparado con K-Means, veamos cuándo DBSCAN es la opción adecuada para nuestras necesidades de agrupación. Las propiedades únicas del DBSCAN lo hacen especialmente adecuado para determinados tipos de datos y dominios de problemas.

Formas de racimo complejas 

Basándonos en nuestra comparación anterior, DBSCAN brilla realmente cuando se trata de formas de conglomerados no globulares. Si tus datos forman patrones arbitrarios como las medias lunas que hemos explorado antes, es probable que DBSCAN supere a los algoritmos tradicionales como K-Means. 

Por ejemplo, en el análisis geográfico, las formaciones naturales como los sistemas fluviales o la expansión urbana suelen tener formas irregulares que DBSCAN puede identificar eficazmente.

Número desconocido de grupos

Una de las principales ventajas de DBSCAN es su capacidad para determinar automáticamente el número de conglomerados. Esto es especialmente útil en el análisis exploratorio de datos, en el que puede que no tengas conocimientos previos sobre la estructura subyacente de tus datos. 

Considera un problema de segmentación del mercado: puede que no sepas de antemano cuántos grupos de clientes distintos existen. DBSCAN puede ayudar a descubrir estos segmentos sin que tengas que adivinar el número de conglomerados.

Conjuntos de datos con ruido 

El enfoque del DBSCAN para tratar los puntos de ruido lo hace robusto frente a los valores atípicos. Esto es crucial en muchos conjuntos de datos del mundo real, donde los errores de medición o las anomalías son frecuentes.

Por ejemplo, en los sistemas de detección de anomalías para la seguridad de la red, DBSCAN puede separar eficazmente los patrones normales de tráfico de red de las posibles amenazas a la seguridad.

Densidades de agrupación variables

A diferencia de las K-Means, que suponen conglomerados de densidad similar, DBSCAN puede identificar conglomerados de densidades variables. Esto es especialmente útil en situaciones en las que algunos grupos de tus datos están más apretados que otros.

Un ejemplo podría ser el análisis de las distribuciones de galaxias en astronomía, donde diferentes regiones del espacio tienen densidades variables de objetos celestes.

Aunque el DBSCAN es potente, es importante ser consciente de sus limitaciones:

1. Sensibilidad de los parámetros: Como hemos dicho antes, elegir valores adecuados para ε y MinPts es crucial. Una mala elección puede conducir a resultados de agrupación subóptimos.
2. Datos de alta dimensión: El rendimiento de DBSCAN puede degradarse con datos de alta dimensionalidad debido a la "maldición de la dimensionalidad".
3. Densidades variables: Aunque DBSCAN puede manejar conglomerados de diferentes densidades, las densidades extremadamente variables en el mismo conjunto de datos pueden seguir planteando problemas.
4. Escalabilidad: Para conjuntos de datos muy grandes, DBSCAN puede resultar caro computacionalmente en comparación con algoritmos como K-Means.

En la siguiente sección, veremos algunas aplicaciones prácticas de DBSCAN.

Ejemplos prácticos de DBSCAN

El DBSCAN encuentra aplicaciones en diversos ámbitos.

Análisis de datos espaciales

En los sistemas de información geográfica (SIG), DBSCAN puede identificar zonas de gran actividad o interés. Por ejemplo, un estudio titulado 'Descubrir la movilidad humana urbana a partir de datos GPS de taxis a gran escalademuestra cómo el DBSCAN puede detectar puntos calientes urbanos a partir de datos GPS de taxis.

Esta aplicación muestra la capacidad de DBSCAN para identificar regiones de actividad densa en datos espaciales, lo que es crucial para la planificación urbana y la gestión del transporte.

Tratamiento de imágenes 

DBSCAN puede agrupar píxeles en objetos distintos para tareas como el reconocimiento de objetos en imágenes. Un estudio titulado 'Segmentación de tumores cerebrales a partir de imágenes de resonancia magnética: análisis de agrupaciones K-means y DBSCANdemuestra la eficacia de DBSCAN en el análisis de imágenes médicas .

Los investigadores utilizaron DBSCAN para segmentar con precisión tumores cerebrales en resonancias magnéticas, mostrando su potencial en el diagnóstico asistido por ordenador y la imagen médica.

Detección de anomalías 

En la detección de fraudes o la supervisión del estado del sistema, DBSCAN puede aislar patrones inusuales. Un estudio titulado 'Detección incremental de valores atípicos basada en clústeres y densidad eficiente en flujos de datosdemuestra la aplicación de un algoritmo DBSCAN modificado para la detección de anomalías en tiempo real.

Los investigadores aplicaron una versión incremental de DBSCAN para detectar valores atípicos en datos de flujo, lo que tiene aplicaciones potenciales en la detección del fraude y la supervisión del estado del sistema. 

Este estudio muestra cómo puede adaptarse DBSCAN para identificar patrones inusuales en flujos de datos continuos, una capacidad crucial para los sistemas de detección de fraudes en tiempo real.

Sistemas de recomendación

DBSCAN puede agrupar a usuarios con preferencias similares, lo que ayuda a generar recomendaciones más precisas. Por ejemplo, un estudio titulado "Sistema de recomendación de servicios basado en múltiples nubes mediante el algoritmo DBSCAN"demuestra la aplicación de DBSCAN para mejorar el filtrado colaborativo de los sistemas de recomendación. Los investigadores utilizaron DBSCAN como parte de un enfoque de agrupación para agrupar a los usuarios en función de sus preferencias y valoraciones de películas, lo que mejoró la precisión de las recomendaciones de películas.

Este enfoque muestra cómo DBSCAN puede mejorar las recomendaciones personalizadas en dominios como los servicios de streaming de entretenimiento.

Conclusión

DBSCAN es una poderosa herramienta del conjunto de herramientas del científico de datos, especialmente valiosa cuando se trata de conjuntos de datos complejos y ruidosos en los que se desconoce el número de conglomerados. Sin embargo, como cualquier algoritmo, no es una solución única. 

La clave del éxito de la agrupación reside en comprender tus datos, los puntos fuertes y las limitaciones de los distintos algoritmos, y elegir la herramienta adecuada para el trabajo. En muchos casos, probar varios enfoques de agrupación, incluidos DBSCAN y K-Means, y comparar sus resultados puede proporcionar información valiosa sobre la estructura de tus datos.

Con la práctica y la experiencia, desarrollarás una intuición para saber cuándo es probable que DBSCAN desvele los patrones ocultos de tus datos.

Puedes obtener más información sobre las distintas tecnologías y métodos que hemos tratado en este post sobre DataCamp con los siguientes recursos: 

• Científico de Aprendizaje Automático en Python
• Hoja de trucos del aprendizaje automático no supervisado
• Curso de Aprendizaje no Supervisado en Python