El análisis de agrupamiento es un problema importante en el análisis de datos. Y hoy en día DBSCAN es una de las técnicas de análisis de clústeres más populares. DBSCAN se refiere a la agrupación espacial de aplicaciones con ruido basada en la densidad, es el algoritmo de agrupación de datos propuesto a principios de los años 90 por un grupo de comunidad de base de datos y minería de datos.
DBSCAN es un algoritmo de clúster o agrupamiento basado en la densidad que puede ser utilizado para identificar clústeres de cualquier forma en un conjunto de datos que contiene ruido y valores atípicos.
La idea básica detrás del enfoque de agrupamiento basado en la densidad se deriva de un método intuitivo de agrupamiento humano. Por ejemplo, al mirar la figura, uno puede identificar fácilmente tres grupos junto con varios puntos de ruido, debido a las diferencias en la densidad de puntos.
Los clústeres son regiones densas en el espacio de datos, separadas por regiones de menor densidad de puntos. El algoritmo DBSCAN se basa en esta noción intuitiva de clústeres y ruido. La idea clave es que, para cada punto de un clúster, la vecindad de un radio dado tiene que contener al menos un número mínimo de puntos.
Antes de que podamos discutir la agrupación basada en la densidad, primero necesitamos cubrir algunos temas.
Parámetros
El algoritmo DBSCAN requiere básicamente 2 parámetros:
Épsilon (eps): especifica lo cerca que deben estar los puntos entre sí para ser considerados parte de un clúster. Esto significa que, si la distancia entre dos puntos es menor o igual a este valor de épsilon, estos puntos se consideran vecinos.
Puntos mínimos (minPts): el número mínimo de puntos para formar una región densa. Por ejemplo, si establecemos minPts como 5, entonces necesitamos al menos 5 puntos para formar una región densa.
En este algoritmo, tenemos tres tipos de puntos de datos. Podemos categorizar cada punto de datos en punto de núcleo, punto de borde y punto de ruido.
Definamos cada uno de ellos.
Punto de núcleo
- Un punto es un punto de núcleo si tiene más de un número especificado de puntos mínimos (minPts) dentro de un radio de épsilon a su alrededor.
- El punto de núcleo siempre pertenece a una región densa.
- Por ejemplo, consideremos que p se establece como un punto central si p es mayor o igual de los puntos mínimos (minPts) en un radio de épsilon (eps) alrededor de ella.
Punto de borde
- Un punto es un punto de borde si tiene menos de puntos mínimos (minPts) dentro de épsilon (eps), pero se encuentra en la vecindad de un punto de núcleo.
- Por ejemplo, p está configurado para ser un punto fronterizo si p no es un punto central. Ejemplo, p tiene menos puntos mínimos (minPts) en un radio de épsilon (eps). Pero p debe pertenecer al vecindario de q, donde q es un punto de núcleo.
- p pertenece al vecindario de q y la distancia de p y q es menor o igual a épsilon (eps).
Punto de ruido
- Un punto de ruido es cualquier punto que no sea un punto de núcleo o un punto de borde.
Hay dos ideas más importantes que debemos tener en cuenta antes de ir a aprender el algoritmo DBSCAB.
Borde de densidad
Si p y q son puntos centrales y la distancia entre p y q es menor o igual a épsilon (eps) entonces podemos conectar el vértice de p y q en un gráfico y llamarlo borde de densidad.
Densidad de puntos conectados
Se dice que dos puntos p y q son puntos de conexión de densidad si tanto p como q son puntos de núcleo y existen una trayectoria formada por los bordes de densidad que conectan el p con el punto q.
Pasos del algoritmo DBSCAN
Con las definiciones anteriores, podemos seguir los pasos del algoritmo DBSCAN como se indica a continuación.
- El algoritmo comienza con un punto arbitrario que no ha sido visitado y la información de su vecindario se recupera desde el parámetro de épsilon.
- Si es punto contiene puntos mínimos dentro del vecindario épsilon, se inicia la formación de clústeres. De lo contrario, el punto se etiqueta como ruido. Este punto se puede encontrar más tarde dentro de la vecindad de épsilon de un punto diferente y, por lo tanto, se pude hacer parte del clúster. El concepto de densidad alcanzable y los puntos de conexión de densidad son importantes aquí.
- Si se encuentra que un punto es un punto de núcleo, entonces los puntos dentro del vecindario de épsilon también son parte del grupo. Así que todos los puntos que se encuentran dentro del vecindario de épsilon se agregan, junto con su propio vecindario épsilon, si también son puntos de núcleo.
- El proceso anterior continúa hasta que se encuentra completamente el clúster conectado a la densidad.
- El proceso se reinicia con un nuevo punto que puede ser parte de un nuevo clúster o etiquetado como ruido.
Elección puntos mínimos
- Una de las cosas más importantes que hace los puntos mínimos es eliminar los puntos atípicos.
- Típicamente, la regla general para tomar puntos mínimos es, siempre debes tomar sus mínimos para ser mayor o igual a la dimensionalidad del conjunto de datos.
- Típicamente, las personas que trabajan más con DBSCAN toman el punto mínimo dos veces de la dimensionalidad de los datos.
- Si el conjunto de datos es más ruidoso, debemos elegir un valor mayor de puntos mínimos.
- Al elegir los puntos mínimos, realmente depende mucho del conocimiento del dominio.
Determinar épsilon
Una vez que se haya elegido el punto mínimo, se puede continuar con épsilon. Un método para obtener este valor consiste en calcular las distancias vecinas más cercanas en una matriz de puntos.
La idea es calcular, el promedio de las distancias de cada punto a sus vecinos más cercanos. El valor de k será especificado por el usuario y corresponde a los puntos mínimos. A continuación, estas k distancias se trazan en orden ascendente. El objetivo es determinar la rodilla, que corresponde al parámetro épsilon óptimo.
Una rodilla corresponde a un umbral en el que se produce un cambio brusco a lo largo de la curva de distancia k.
Ventajas del algoritmo
- A diferencia de K Means, DBSCAN no requiere que el usuario especifique el número de clústeres que se generarán.
- DBSCAN puede encontrar cualquier forma de clúster. El clúster no tiene que ser circular.
- Puede manejar muy bien el ruido y los valores atípicos.
- Es excelente para separar clústeres de alta densidad frente a clústeres de baja densidad dentro de un conjunto de datos determinado.
Desventajas del algoritmo
- Si la base de datos tiene puntos de datos que forman clústeres de densidad variable, entonces DBSCAN no puede agrupar bien los puntos de datos, ya que el agrupamiento depende del parámetro épsilon y puntos mínimos, no se pueden seleccionar por separado para todos los clústeres.
- Si los datos y características no son bien entendidos por un experto en dominios, entonces configurar épsilon y los puntos mínimos podría ser complicado y podría necesitar comparaciones para varias iteraciones con diferentes valores de épsilon y puntos mínimos.
- Es extremadamente sensible a los hiperparámetros. Un ligero cambio en los hiperparámetros puede llevar a un cambio drástico en el resultado.
Aplicaciones reales 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 específico. Podemos aplicar el algoritmo DBSCAN a nuestro conjunto de datos, basado en la base de datos de comercio electrónico, y encontrar los clústeres basados en los productos que los usuarios han comprado. Usando estos grupos podemos encontrar similitudes entre los clientes, por ejemplo, si el cliente A ha comprado un bolígrafo, un libro y un par de tijeras, mientras que el cliente B ha comprado un libro y un par de tijeras, entonces puedes recomendar un bolígrafo al cliente B.
- Antes del surgimiento de las metodologías basadas en el Aprendizaje Profundo los investigadores utilizaban DBSCAN para segregar genes de un conjunto de datos de genes que tenían la posibilidad de padecer cáncer.
- Los científicos han utilizado DBSCAN para detectar las paradas en los datos de trayectorias generados por los dispositivos de GPS móviles. Las paradas representan la parte más significativa y más importante de una trayectoria.
Con esto finalizamos la explicación de este contenido. Ya debes entener cómo funciona el algoritmo de agrupamiento espacial basado en densidad de aplicaciones de ruido o DBSCAN, por lo tanto te dejo la siguiente pregunta, ¿Cuáles de las siguientes afirmaciones crees tú que sea cierta?
Opción 1: El algoritmo DBSCAN forma parte del conjunto de algoritmos de aprendizaje supervisado.
Respuecta Incorrecta. Este es un algoritmo de aprendizaje no supervisado y más específicamente de agrupamiento.
Opción 2: Entre los parámetros que se debe definir en este algoritmo están epsilon y los parámetros mínimos.
Respuesta Correcta.
Opción 3: Este algoritmo puede reconocer clúster en el conjunto de datos con cualquier tipo de forma, no necesariamente tienen que ser circulares.
Respuesta Correcta.
