Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

DBSCAN

Introducción a DBSCAN

El clustering espacial basado en la densidad de aplicaciones con ruido (DBSCAN) identifica clústeres de forma arbitraria y ruido (valores atípicos) en los datos. La función realiza clustering en una matriz de datos de entrada o en distancias en parejas entre observaciones. Devuelve los índices del clúster y un vector que indica las observaciones que son puntos principales (puntos dentro de los clústeres).Statistics and Machine Learning Toolbox™dbscandbscan A diferencia de la agrupación en clústeres, el algoritmo DBSCAN no requiere conocimientos previos del número de clústeres y los clústeres no son necesariamente esferoidal.k DBSCAN también es útil para la detección de valores atípicos basados en la densidad, ya que identifica puntos que no pertenecen a ningún clúster.

Para que un punto se asigne a un clúster, debe satisfacer la condición de que su vecindad Epsilon () contenga al menos un número mínimo de vecinos ().epsilonminpts O, el punto puede estar dentro del barrio épsilon de otro punto que satisface las condiciones.epsilonminpts El algoritmo DBSCAN identifica tres tipos de puntos:

  • Punto de núcleo: un punto de un clúster que tiene al menos vecinos en su vecindad épsilonminpts

  • Punto de borde: un punto de un clúster que tiene menos de vecinos en su vecindad épsilonminpts

  • Punto de ruido: un valor atípico que no pertenece a ningún clúster

DBSCAN funciona con una amplia gama de, y puede definir una métrica de distancia personalizada para su aplicación en particular.métricas de distancia La elección de una métrica de distancia determina la forma de la vecindad.

Descripción del algoritmo

Para los valores especificados de la vecindad épsilon y el número mínimo de vecinos requeridos para un punto central, la función implementa DBSCAN como sigue:epsilonminptsdbscan

  1. En el conjunto de datos de entrada, seleccione la primera observación sin etiquetarX X1 como el punto actual e inicialice la primera etiqueta de clúster en 1.C

  2. Encuentre el conjunto de puntos dentro de la vecindad épsilon del punto actual.epsilon Estos puntos son los vecinos.

    1. Si el número de vecinos es menor que, a continuación, etiquetar el punto actual como un punto de ruido (o un valor atípico).minpts Vaya al paso 4.

      Nota

      puede reasignar puntos de ruido a clústeres si los puntos de ruido más adelante satisfacen las restricciones establecidas por y desde algún otro punto.dbscanepsilonminptsX Este proceso de reasignación de puntos se produce para los puntos de borde de un clúster.

    2. De lo contrario, etiquete el punto actual como un punto central perteneciente al clúster.C

  3. Recorra en iteración cada vecino (nuevo punto actual) y repita el paso 2 hasta que no se encuentren nuevos vecinos que puedan etiquetarse como pertenecientes al clúster actual.C

  4. Seleccione el siguiente punto sin etiquetar como el punto actual y aumente el número de clústeres en 1.X

  5. Repita los pasos 2 – 4 hasta que se etiqueten todos los puntos.X

Determinar valores para parámetros DBSCAN

Este ejemplo muestra cómo seleccionar valores para los parámetros y.epsilonminptsdbscan El conjunto de datos es una secuencia de escaneos LiDAR, cada uno almacenado como una nube de puntos 3D.

Cargue, preprocese y visualice el conjunto de datos.

Cargue una secuencia de nubes de puntos. Seleccione la última marca de tiempo en la secuencia y extraiga las coordenadas de los objetos que rodean a un vehículo.x, y, z

d = load('01_city_c2s_fcw_10s_Lidar.mat');  pcloud = d.LidarPointCloud;  X = pcloud(end).ptCloud.Location;

Para resaltar el entorno alrededor del vehículo, establecer la región de interés para abarcar 20 metros a la izquierda y la derecha del vehículo, 20 metros en la parte delantera y trasera del vehículo, y el área por encima de la superficie de la carretera.

xBound  = 20; % in meters yBound  = 20; % in meters zLowerBound = 0; % in meters

Recorte la nube de puntos para que contenga solo los extremos dentro de la región especificada.

indices = X(:,1) <= xBound & X(:,1) >= -xBound ...     & X(:,2) <= yBound & X(:,2) >= -yBound ...     & X(:,3) > zLowerBound; X = X(indices,:); 

Visualice los datos como un gráfico de dispersión en 2-D. Anote el trazado para resaltar el vehículo.

scatter(X(:,1),X(:,2),'.'); annotation('ellipse',[0.48 0.48 .1 .1],'Color','red')

El centro de la nube de puntos (rodeado de rojo) contiene el techo y la capucha del vehículo. Todos los demás puntos son obstáculos.

Seleccione un valor para.minpts

Para seleccionar un valor, considere un valor mayor o igual que uno más el número de dimensiones de los datos de entrada [1].minpts Por ejemplo, para una-por-matriz, establezca el valor de mayor o igual que p.npX'minpts'+1

Para el conjunto de datos especificado, especifique un valor mayor o igual que 4, concretamente el valor 50.minpts

minpts = 50; % Minimum number of neighbors for a core point

Seleccione un valor para.epsilon

Una estrategia para estimar un valor es generar un gráfico de una distancia para los datos de entrada.epsilonkX Para cada punto en, encuentre la distancia al punto más cercano y trace los puntos ordenados contra esta distancia.Xk El gráfico contiene una rodilla. La distancia que corresponde a la rodilla es generalmente una buena opción para, porque es la región donde los puntos empiezan a salir en territorio atípico (ruido) [1].epsilon

Antes de trazar el gráfico de distancia, primero se encuentran las distancias en pares más pequeñas para las observaciones, en orden ascendente.kminptsX

kD = pdist2(X,X,'euc','Smallest',minpts); % The minpts smallest pairwise distances

Trace el gráfico de distancia.k

plot(sort(kD(end,:))); title('k-distance graph') xlabel('Points sorted with 50th nearest distances') ylabel('50th nearest distances') grid

La rodilla parece estar alrededor de 2; por lo tanto, establezca el valor en 2.epsilon

epsilon = 2;

Cluster usando.dbscan

Se utiliza con los valores de y que se determinaron en los pasos anteriores.dbscanminptsepsilon

labels = dbscan(X,epsilon,minpts);

Visualice la agrupación en clústeres y anote la figura para resaltar clústeres específicos.

gscatter(X(:,1),X(:,2),labels); title('epsilon = 2 and minpts = 50') grid annotation('ellipse',[0.54 0.41 .07 .07],'Color','red') annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue') annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')

identifica 11 clústeres y un conjunto de puntos de ruido.dbscan El algoritmo también identifica el vehículo en el centro de la nube de puntos como un cluster diferenciado.

identifica algunos clústeres distintos, como el clúster con un círculo en negro (y centrado alrededor de (– 6, 18)) y el clúster en un círculo azul (y centrado alrededor de (2,5, 18)).dbscan La función también asigna el grupo de puntos marcados en rojo (y centrado alrededor de ()) al mismo cluster (Grupo 7) como el grupo de puntos en el cuadrante sureste de la trama.3,–4 La expectativa es que estos grupos deben estar en clústeres separados.

Utilice un valor más pequeño para dividir los clústeres grandes y seguir la partición de la nube de puntos.epsilon

epsilon2 = 1; labels2 = dbscan(X,epsilon2,minpts);

Visualice la agrupación en clústeres y anote la figura para resaltar clústeres específicos.

gscatter(X(:,1),X(:,2),labels2); title('epsilon = 1 and minpts = 50') grid annotation('ellipse',[0.54 0.41 .07 .07],'Color','red') annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue') annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')

Mediante el uso de un valor de épsilon más pequeño, es capaz de asignar el grupo de puntos marcados en rojo en un clúster distinto (grupo 13).dbscan Sin embargo, algunos clústeres que se identificaron correctamente antes se dividen ahora entre puntos de clúster y valores atípicos.dbscan Por ejemplo, vea el grupo de clústeres 2 (con un círculo en negro) y el grupo de clústeres 3 (con un círculo en azul). El valor correcto está en algún lugar entre 1 y 2.epsilon

Utilice un valor para agrupar los datos.epsilon1.55

epsilon3 = 1.55; labels3 = dbscan(X,epsilon3,minpts);

Visualice la agrupación en clústeres y anote la figura para resaltar clústeres específicos.

gscatter(X(:,1),X(:,2),labels3); title('epsilon = 1.55 and minpts = 50') grid annotation('ellipse',[0.54 0.41 .07 .07],'Color','red') annotation('ellipse',[0.53 0.85 .07 .07],'Color','blue') annotation('ellipse',[0.39 0.85 .07 .07],'Color','black')

realiza un mejor trabajo de identificación de los clústeres cuando se establece en.dbscanepsilon1.55 Por ejemplo, la función identifica los distintos clústeres marcados en rojo, negro y azul (con centros alrededor (), (– 6, 18) y (2,5, 18), respectivamente).3,–4

Referencias

[1] Ester, M., H.-P. Kriegel, J. Sander, and X. Xiaowei. “A density-based algorithm for discovering clusters in large spatial databases with noise.” In Proceedings of the Second International Conference on Knowledge Discovery in Databases and Data Mining, 226-231. Portland, OR: AAAI Press, 1996.

Temas relacionados