DBSCAN (Agrupamiento espacial basado en densidad de aplicaciones con ruido)

¿Qué es DBSCAN? 

DBSCAN significa Agrupamiento espacial basado en densidad de aplicaciones con ruido propuesto por Ester, Kriegel, Sander y Xu en 1996. Es el método de aprendizaje no supervisado más utilizado entre los métodos de agrupamiento basados ​​en densidad. Hay varias ventajas de usar este tipo de método: la capacidad de crear un número desconocido de clases, crear clases con formas no convexas y la capacidad de manejar anomalías.

Para utilizar el método DBSCAN, se requieren 2 parámetros:

• ϵ > 0;
• El número mínimo de puntos, también llamado MinPts > 0

Varias definiciones nos permiten entender cómo se hacen las clases. Primero, debemos definir y contar vecinos para cada punto. Un vecino se define como cualquier punto p del conjunto de datos de entrenamiento con una distancia menor o igual a ϵ desde un punto q .

Tenga en cuenta que, por definición, el punto q es su propio vecino. Se pueden definir 3 tipos de puntos con el algoritmo DBSCAN:

• Punto central: un punto con tantos o más vecinos como el número mínimo de puntos.
• Punto de borde: un punto que tiene menos vecinos que el número mínimo de puntos, pero es vecino de un punto central.
• Punto de ruido: ni un punto central ni un punto fronterizo.

Un punto p es directamente alcanzable por densidad desde q , si q es un punto central y p un vecino de q . Un punto p es alcanzable por densidad desde q si hay una secuencia ordenada de puntos directamente alcanzables por densidad desde el punto anterior. Dos puntos p y q están densamente conectados si hay un punto o de tal manera que ambos p y q se alcanzan por densidad a partir de o .

Finalmente, Ester definió una clase como un subconjunto del conjunto de datos que cumple dos condiciones:

• Si p pertenece a la clase C y q es densamente alcanzable desde p entonces q pertenece a C .
• Todos los puntos de la clase C están densamente conectados.

El algoritmo DBSCAN

El algoritmo DBSCAN visita todos los puntos del conjunto de datos de entrenamiento y los marca como visitados a medida que avanza.

Si un punto es un punto central, se inicia la primera clase (denominada clase 1). El punto central y sus vecinos se asignan a la clase 1. Luego, el algoritmo visita a sus vecinos para encontrar otro punto central y lo asigna a la clase 1. Este paso permite que la clase se expanda. El algoritmo se detiene para expandir la clase 1 cuando se han visitado todos los puntos densamente alcanzable.

El algoritmo continúa visitando los puntos no visitados y comenzará una nueva clase si se encuentra otro punto central. Esta clase también se puede ampliar y así sucesivamente.

Finalmente, todos los puntos que no están asignados a una clase son puntos de ruido.

Opciones para el agrupamiento DBSCAN en XLSTAT

Predicción con DBSCAN 

DBSCAN permite predecir la clase de nuevas observaciones.

Primero, debe encontrar los vecinos de cada nueva observación en el conjunto de datos de entrenamiento. Si la nueva observación es vecina de un punto central (del conjunto de datos de entrenamiento), la nueva observación se asigna a la misma clase que el punto central.

Si la nueva observación no tiene un punto central en sus vecinos, entonces se considera un punto de ruido.

Tenga en cuenta que el orden de visita puede cambiar la clase asignada a los puntos fronterizos durante el aprendizaje y la predicción.

Árbol K-dimensional 

Utilice el árbol K-dimensional cuando el conjunto de datos contenga solo variables cuantitativas (Bentley, 1975) no es posible calcular todas las distancias para encontrar todos los vecinos en un radio de tamaño épsilon.

El árbol k-dimensional es un árbol binario construido para ordenar los puntos de una dimensión y dividir el espacio en 2 partiendo de la mediana. Los puntos con un valor menor o igual que la mediana en esta dimensión se almacenan en el nodo secundario izquierdo, mientras que los puntos con un valor mayor que la mediana se almacenan en el nodo secundario derecho. La construcción del árbol se detiene cuando solo queda un punto en un nodo.

Métricas de distancia 

Existen diferentes métricas de distancia para calcular distancias sin importar el tipo de variable.

Hay 5 métricas cuando solo se seleccionan variables cuantitativas:

• Distancia euclidiana
• Distancia de Minkowski
• Distancia de Manhattan
• Distancia de Chebychev
• Distancia de Canberra.

Cuando solo hay variables cualitativas que describen las observaciones, se utiliza la distancia de superposición.

Con datos mixtos, se utiliza HEOM (Métrica de superposición euclidiana heterogénea).

Resultados del agrupamiento de DBSCAN en XLSTAT

Estadísticos descriptivos: La tabla de estadísticos descriptivos muestra los estadísticos simples para todas las variables seleccionadas. El número de valores perdidos, el número de valores no perdidos, la media y la desviación estándar (insesgado) se muestran para las variables cuantitativas. Para las variables cualitativas, incluida la variable dependiente, se muestran las categorías con sus respectivas frecuencias y porcentajes.

Matriz de correlación: esta tabla muestra las correlaciones entre las diversas variables seleccionadas.

Número de objetos por clase: esta tabla muestra el tamaño de cada clase y el número de puntos de ruido.

Resultados de las matrices distancia: Se muestran una o dos matrices de distancia si la opción de predicción está activada. La primera matriz muestra las distancias entre cada punto de la muestra de entrenamiento. La segunda matriz muestra las distancias entre las nuevas observaciones y las observaciones de la muestra de entrenamiento.

Resultados de los objetos: las clases asignadas a cada observación mediante el algoritmo DBSCAN se muestran para el entrenamiento y la muestra de predicción. Si la clase es 0, significa que la observación se considera un punto de ruido. Además, la puntuación de silueta de cada observación se muestra en la segunda columna (si la opción está activada).

Se muestra un gráfico de las puntuaciones de la silueta si la opción está activada. Las observaciones se agrupan por clases en orden descendente con respecto al coeficiente de silueta.

Resultados asociados con objetos ordenados por clase: esta tabla se muestra para mostrar las observaciones ordenadas por clase