Empecemos a hablar de DBSCAN.
El clustering espacial basado en la densidad de las aplicaciones con ruido (DBSCAN) es un conocido algoritmo de clustering de datos que se utiliza habitualmente en minería de datos y aprendizaje automático.
A partir de un conjunto de puntos (pensemos en un espacio bidimensional como se ejemplifica en la figura), DBSCAN agrupa los puntos que están próximos entre sí en función de una medida de distancia (normalmente la distancia euclidiana) y un número mínimo de puntos. También marca como outliers los puntos que se encuentran en regiones de baja densidad.
Parámetros:
El algoritmo DBSCAN requiere básicamente 2 parámetros:
eps: especifica lo cerca que deben estar los puntos entre sí para ser considerados parte de un cluster. Significa que si la distancia entre dos puntos es menor o igual a este valor (eps), estos puntos se consideran vecinos.
minPoints: el número mínimo de puntos para formar una región densa. Por ejemplo, si establecemos el parámetro minPoints como 5, entonces necesitamos al menos 5 puntos para formar una región densa.
Estimación de parámetros:
La estimación de parámetros es un problema para toda tarea de minería de datos. Para elegir buenos parámetros debemos entender cómo se utilizan y tener al menos un conocimiento previo básico sobre el conjunto de datos que se va a utilizar.
eps: si el valor de eps elegido es demasiado pequeño, una gran parte de los datos no se agrupará. Se considerarán valores atípicos porque no satisfacen el número de puntos para crear una región densa. Por otro lado, si el valor elegido es demasiado alto, los clusters se fusionarán y la mayoría de los objetos estarán en el mismo cluster. El eps debe elegirse en función de la distancia del conjunto de datos (podemos utilizar un gráfico de k-distancia para encontrarlo), pero en general son preferibles los valores de eps pequeños.
minPuntos: Como regla general, un mínimo de minPuntos puede derivarse de un número de dimensiones (D) en el conjunto de datos, como minPuntos ≥ D + 1. Los valores más grandes suelen ser mejores para los conjuntos de datos con ruido y formarán clusters más significativos. El valor mínimo de minPoints debe ser 3, pero cuanto más grande sea el conjunto de datos, mayor será el valor de minPoints que debe elegirse.
Puede encontrar más información sobre la estimación de parámetros aquí.
¿Por qué debemos utilizar DBSCAN?
El algoritmo DBSCAN se debe utilizar para encontrar asociaciones y estructuras en los datos que son difíciles de encontrar manualmente pero que pueden ser relevantes y útiles para encontrar patrones y predecir tendencias.
Los métodos de clustering se suelen utilizar en biología, medicina, ciencias sociales, arqueología, marketing, reconocimiento de personajes, sistemas de gestión, etc.
Pensemos en un uso práctico de DBSCAN. Supongamos que tenemos un comercio electrónico y queremos mejorar nuestras ventas recomendando productos relevantes a nuestros clientes. No sabemos exactamente lo que buscan nuestros clientes, pero basándonos en un conjunto de datos podemos predecir y recomendar un producto relevante a un cliente concreto. Podemos aplicar el DBSCAN a nuestro conjunto de datos (basado en la base de datos de comercio electrónico) y encontrar clusters basados en los productos que los usuarios han comprado. Usando estos clusters podemos encontrar similitudes entre los clientes, por ejemplo, el cliente A ha comprado 1 bolígrafo, 1 libro y 1 tijera y el cliente B ha comprado 1 libro y 1 tijera, entonces podemos recomendar 1 bolígrafo al cliente B. Este es sólo un pequeño ejemplo de uso de DBSCAN, pero se puede utilizar en un montón de aplicaciones en varias áreas.
¿Cómo podemos implementarlo fácilmente?
Como ya escribí (consejo: no creas en todo lo que escribo) el DBSCAN es un algoritmo bien conocido, por lo tanto, no necesitas preocuparte por implementarlo tú mismo. Puedes utilizar alguna de las librerías/paquetes que se pueden encontrar en internet. Aquí hay una lista de enlaces en los que puedes encontrar la implementación de DBSCAN: Matlab, R, R, Python, Python.
También he desarrollado una aplicación (en portugués) para explicar cómo funciona el DBSCAN de forma didáctica. La aplicación fue escrita en C++ y se puede encontrar en Github.