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

Clustering espacial basado en la densidad de aplicaciones con ruido (DBSCAN)

Descripción

ejemplo

idx = dbscan(X,epsilon,minpts) divide las observaciones de la matriz-por-datos en clústeres mediante el algoritmo DBSCAN (consulte). agrupa las observaciones (o puntos) en función de un umbral para un radio de búsqueda de vecindad y un número mínimo de vecinos requeridos para identificar un punto central.npXAlgoritmosdbscanepsilonminpts La función devuelve un vector-by-1 () que contiene índices de clúster de cada observación.nidx

ejemplo

idx = dbscan(X,epsilon,minpts,Name,Value) especifica opciones adicionales mediante uno o varios argumentos de par nombre-valor. Por ejemplo, puede especificar que se utilice la métrica de distancia Minkowski con un exponente de tres en el algoritmo DBSCAN.'Distance','minkowski','P',3

ejemplo

idx = dbscan(D,epsilon,minpts,'Distance','precomputed') Devuelve un vector de índices de clúster para las distancias de pares precalculadas entre observaciones. puede ser la salida de o, o un vector o matriz de dessimilitud más general conforme al formato de salida de o, respectivamente.DDpdistpdist2pdistpdist2

ejemplo

[idx,corepts] = dbscan(___) también devuelve un vector lógico que contiene los puntos principales identificados por, utilizando cualquiera de las combinaciones de argumentos de entrada en las sintaxis anteriores.coreptsdbscan

Ejemplos

contraer todo

Agrule un conjunto de datos circulares 2-D mediante DBSCAN con la métrica de distancia euclidiana predeterminada. Además, compare los resultados de agrupar el conjunto de datos mediante DBSCAN y-Means clustering con la métrica de distancia euclidiana cuadrada.k

Genere datos sintéticos que contengan dos círculos ruidosos.

rng('default') % For reproducibility  % Parameters for data generation N = 300;  % Size of each cluster r1 = 0.5; % Radius of first circle r2 = 5;   % Radius of second circle theta = linspace(0,2*pi,N)';  X1 = r1*[cos(theta),sin(theta)]+ rand(N,1);  X2 = r2*[cos(theta),sin(theta)]+ rand(N,1); X = [X1;X2]; % Noisy 2-D circular data set

Visualice el conjunto de datos.

scatter(X(:,1),X(:,2))

La gráfica muestra que el conjunto de datos contiene dos clústeres distintos.

Realice la agrupación en clústeres de DBSCAN en los datos. Especifique un valor de 1 y un valor de 5.epsilonminpts

idx = dbscan(X,1,5); % The default distance metric is Euclidean distance

Visualice la agrupación en clústeres.

gscatter(X(:,1),X(:,2),idx); title('DBSCAN Using Euclidean Distance Metric')

Mediante la métrica de distancia euclidiana, DBSCAN identifica correctamente los dos clústeres del conjunto de datos.

Realice la agrupación en clústeres de DBSCAN utilizando la métrica de distancia euclidiana cuadrada. Especifique un valor de 1 y un valor de 5.epsilonminpts

idx2 = dbscan(X,1,5,'Distance','squaredeuclidean');

Visualice la agrupación en clústeres.

gscatter(X(:,1),X(:,2),idx2); title('DBSCAN Using Squared Euclidean Distance Metric')

Con la métrica de distancia euclidiana cuadrada, DBSCAN identifica correctamente los dos clústeres del conjunto de datos.

Realizar-significa clustering usando la métrica de distancia euclidiana cuadrada.k Especifique = 2 clústeres.k

kidx = kmeans(X,2); % The default distance metric is squared Euclidean distance

Visualice la agrupación en clústeres.

gscatter(X(:,1),X(:,2),kidx); title('K-Means Using Squared Euclidean Distance Metric')

Usando la métrica de distancia euclidiana cuadrada,-significa que el clustering no puede identificar correctamente los dos clústeres en el conjunto de datos.k

Realice la agrupación en clústeres DBSCAN utilizando una matriz de distancias en pares entre las observaciones como entrada de la función y encuentre el número de valores atípicos y puntos principales.dbscan El conjunto de datos es una secuencia de escaneos LiDAR, cada uno almacenado como una nube de puntos 3D.

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;  loc = 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 = loc(:,1) <= xBound & loc(:,1) >= -xBound ...     & loc(:,2) <= yBound & loc(:,2) >= -yBound ...     & loc(:,3) > zLowerBound; loc = loc(indices,:);

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

scatter(loc(:,1),loc(:,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.

Calcule previamente una matriz de distancias en pares entre las observaciones mediante la función.Dpdist2

D = pdist2(loc,loc);

Agrupa los datos mediante el uso de las distancias en pares.dbscan Especifique un valor de 2 y un valor de 50.epsilonminpts

[idx, corepts] = dbscan(D,2,50,'Distance','precomputed');

Visualice los resultados y anote la figura para resaltar un clúster específico.

gscatter(loc(:,1),loc(:,2),idx); annotation('ellipse',[0.54 0.41 .07 .07],'Color','red') grid

Como se muestra en el gráfico de dispersión, identifica 11 clústeres y coloca el vehículo en un clúster independiente.dbscan

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.dbscan3,–4 La expectativa es que estos grupos deben estar en clústeres separados. Puede intentar usar un valor menor para dividir los clústeres grandes y seguir la partición de la nube de puntos.epsilon

La función también identifica algunos valores atípicos (un valor de) en los datos.idx–1 Busque el número de puntos que se identifican como valores atípicos.dbscan

sum(idx == -1)
ans = 412 

identifica 412 valores atípicos de 19.070 observaciones.dbscan

Busque el número de puntos que se identifican como puntos principales.dbscan Un valor de indica un punto central.corepts1

sum(corepts == 1)
ans = 18446 

identifica 18.446 observaciones como puntos centrales.dbscan

Vea para un ejemplo más extenso.Determinar valores para parámetros DBSCAN

Argumentos de entrada

contraer todo

Datos de entrada, especificados como una matriz numérica.np Las filas de corresponden a las observaciones (o puntos), y las columnas corresponden a las variables.X

Tipos de datos: single | double

Distancias en pares entre las observaciones, especificadas como un vector de fila numérico que es la salida de, matriz cuadrada numérica que es la salida de, Vector de fila lógico o matriz cuadrada lógica. también puede ser un vector o matriz de dessimilitud más general que se ajuste al formato de salida de o, respectivamente.pdistpdist2Dpdistpdist2

Para las especificaciones mencionadas, la tabla siguiente describe los formatos que pueden tomar, dada una matriz de entrada que tiene observaciones (filas) y dimensiones (columnas).DXnp

EspecificaciónFormato
Vector de fila numérico (salida de)pdist(X)
  • Un vector de fila de longitud n(n – 1)/2, correspondientes a pares de observaciones enX

  • Las distancias dispuestas en el orden (2,1), (3,1), ..., (n,1), (3,2), ..., (n,2), ..., (n,n – 1))

Matriz cuadrada numérica (salida de)pdist2(X,X)
  • Una-por-matriz, donde está la distancia entre las observaciones y ennnD(i,j)ijX

  • Una matriz simétrica con elementos diagonales iguales a cero

Vector de fila lógica
  • Un vector de fila de longitud n(n – 1)/2, correspondientes a pares de observaciones enX

  • Un vector de fila lógico con elementos que indican distancias que son menores o iguales queepsilon

  • Elementos dispuestos en el ordenD (2,1), (3,1), ..., (n,1), (3,2), ..., (n,2), ..., (n,n – 1))

Matriz cuadrada lógica
  • Una-por-matriz, donde indica la distancia entre las observaciones y en que son menores o iguales annD(i,j)ijXepsilon

Nota

Si es un vector lógico o una matriz, el valor de debe estar vacío; por ejemplo,.Depsilondbscan(D,[],5,'Distance','precomputed')

Tipos de datos: single | double | logical

Epsilon vecindario de un punto, especificado como un escalar numérico que define un radio de búsqueda de vecindad alrededor del punto. Si la vecindad épsilon de un punto contiene al menos vecinos, a continuación, identifica el punto como un punto central.minptsdbscan

El valor de debe ser Empty () cuando es un vector lógico o una matriz.epsilon[]D

Ejemplo: dbscan(X,2.5,10)

Ejemplo: , para una matriz lógica o Vectordbscan(D,[],5,'Distance','precomputed')D

Tipos de datos: single | double

Número mínimo de vecinos requeridos para un punto de núcleo, especificado como un entero positivo. La vecindad épsilon de un punto central de un clúster debe contener al menos vecinos, mientras que la vecindad épsilon de un punto de borde puede contener menos vecinos que.minptsminpts

Ejemplo: dbscan(X,2.5,5)

Tipos de datos: single | double

Argumentos de par nombre-valor

Especifique pares de argumentos separados por comas opcionales. es el nombre del argumento y es el valor correspondiente. deben aparecer dentro de las cotizaciones.Name,ValueNameValueName Puede especificar varios argumentos de par de nombre y valor en cualquier orden como.Name1,Value1,...,NameN,ValueN

Ejemplo: Especifica la agrupación en clústeres DBSCAN mediante una matriz precalculada de distancias en pares entre observaciones, una vecindad épsilon de y un mínimo de vecinos.dbscan(D,2.5,5,'Distance','precomputed')D2.55

Métrica de distancia, especificada como el par separado por comas que consta de un vector de caracteres, un escalar de cadena o un identificador de función, como se describe en esta tabla.'Distance'

ValorDescripción
'precomputed'

Distancias precalculadas. Debe especificar esta opción si la primera entrada es un vector o una matriz de distancias en pares.dbscanD

'euclidean'

Distancia euclidiana (por defecto)

'squaredeuclidean'

Distancia euclidiana cuadrada. (Esta opción se proporciona sólo para la eficiencia. No satisface la desigualdad triangular.)

'seuclidean'

Distancia euclidiana estandarizada. Cada diferencia de coordenadas entre las observaciones se escala dividiendo por el elemento correspondiente de la desviación estándar, S = nanstd(X). Se usa para especificar otro valor para.ScaleS

'mahalanobis'

Mahalanobis distancia utilizando la covarianza de muestra de,X C = nancov(X). Se utiliza para especificar otro valor para, donde la matriz es simétrica y positiva definida.CovCC

'cityblock'

Distancia de bloque de ciudad

'minkowski'

Distancia Minkowski. El exponente predeterminado es 2. Se usa para especificar un exponente diferente, donde es un valor escalar positivo.PP

'chebychev'

Chebychev distancia (diferencia máxima de coordenadas)

'cosine'

Uno menos el coseno del ángulo incluido entre los puntos (tratado como vectores)

'correlation'

Uno menos la correlación de muestra entre puntos (tratado como secuencias de valores)

'hamming'

Distancia de Hamming, que es el porcentaje de coordenadas que difieren

'jaccard'

Uno menos el coeficiente Jaccard, que es el porcentaje de coordenadas distintas de cero que difieren

'spearman'

Uno menos la correlación de rango de Spearman de muestra entre las observaciones (tratadas como secuencias de valores)

@distfun

Mango de función de distancia personalizado. Una función de distancia tiene la forma donde

function D2 = distfun(ZI,ZJ) % calculation of distance ...

  • es un vector que contiene una sola observación.ZI1n

  • es una-por-matriz que contiene múltiples observaciones. debe aceptar una matriz con un número arbitrario de observaciones.ZJm2ndistfunZJ

  • es un vector de distancias, y es la distancia entre las observaciones y.D2m21D2(k)ZIZJ(k,:)

Si los datos no son escasos, generalmente puede calcular la distancia más rápidamente mediante una distancia incorporada en lugar de un identificador de función.

Para las definiciones, vea.Las métricas de distancia

Cuando se utiliza la métrica, o Distance, se puede especificar el argumento de par nombre-valor adicional, o, respectivamente, para controlar las métricas de distancia.'seuclidean''minkowski''mahalanobis''Scale''P''Cov'

Ejemplo: especifica un vecindario épsilon de, un mínimo de vecinos para hacer crecer un clúster y el uso de la métrica de distancia Minkowski con un exponente de al realizar el algoritmo de clustering.dbscan(X,2.5,5,'Distance','minkowski','P',3)2.553

Exponente de la métrica de distancia Minkowski, especificada como el par separado por comas que consta de un escalar positivo.'P'

Este argumento sólo es válido si es.'Distance''minkowski'

Ejemplo: 'P',3

Tipos de datos: single | double

Matriz de covarianza para la métrica de distancia de Mahalanobis, especificada como el par separado por comas que consta de una matriz numérica simétrica, positiva y definida.'Cov'

Este argumento sólo es válido si es.'Distance''mahalanobis'

Tipos de datos: single | double

Factores de escalado para la métrica de distancia euclidiana estandarizada, especificada como el par separado por comas que consta de un vector numérico de valores positivos.'Scale'

Cada dimensión (columna) de tiene un valor correspondiente en; por lo tanto, es de longitud (el número de columnas en).X'Scale''Scale'pX Para cada dimensión de, utiliza el valor correspondiente para estandarizar la diferencia entre y un punto de consulta.Xdbscan'Scale'X

Este argumento sólo es válido si es.'Distance''seuclidean'

Tipos de datos: single | double

Argumentos de salida

contraer todo

Índices de clúster, devueltos como un vector de columna numérico. tiene filas, y cada fila de indica la asignación de clúster de la observación correspondiente en.idxnidxX Un índice igual a indica un valor atípico (o punto de ruido).–1

Nota

La asignación de clúster mediante el algoritmo DBSCAN depende del orden de las observaciones. Por lo tanto, barajar las filas de puede conducir a diferentes asignaciones de clúster para las observaciones.X Para obtener más información, consulte.Algoritmos

Tipos de datos: double

Indicador de puntos centrales, devuelto como vector lógico que indica los índices de los puntos principales identificados por.n1dbscan Un valor de en cualquier fila de indica que la observación correspondiente en es un punto central.1coreptsX De lo contrario, tiene un valor de para las filas correspondientes a las observaciones que no son puntos centrales.corepts0

Tipos de datos: logical

Más acerca de

contraer todo

Puntos principales

Los puntos principales de un clúster son puntos que tienen al menos un número mínimo de vecinos () en su vecindad Epsilon ().minptsepsilon Cada clúster debe contener al menos un punto central.

Puntos fronterizos

Los puntos de borde de un clúster son puntos que tienen menos que el número mínimo requerido de vecinos para un punto de núcleo () en su vecindad Epsilon ().minptsepsilon Generalmente, la vecindad épsilon de un punto de borde contiene significativamente menos puntos que la vecindad épsilon de un punto central.

Puntos de ruido

Los puntos de ruido son valores atípicos que no pertenecen a ningún clúster.

Sugerencias

  • Para mejorar la velocidad al iterar sobre muchos valores de, considere pasar como la entrada a.epsilonDdbscan Este enfoque impide que la función tenga que calcular las distancias en cada punto de la iteración.

  • Si utiliza para calcular previamente, no especifique los argumentos de par nombre-valor de para seleccionar u ordenar columnas de.pdist2D'Smallest''Largest'pdist2D Al seleccionar menos de las distancias, se produce un error, porque espera ser una matriz cuadrada.ndbscanD Clasificar las distancias en cada columna de conduce a una pérdida en la interpretación de y puede dar resultados sin sentido cuando se utiliza en la función.DDdbscan

  • Para un uso eficiente de la memoria, considere la posibilidad de pasar como una matriz lógica en lugar de una matriz numérica a cuando es grande.DdbscanD De forma predeterminada, almacena cada valor en una matriz numérica con 8 bytes (64 bits) y cada valor en una matriz lógica con 1 byte (8 bits).MATLAB®

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

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

Algoritmos

  • DBSCAN es un algoritmo de clustering basado en la densidad que está diseñado para detectar clústeres y ruido en los datos. El algoritmo identifica tres tipos de puntos: puntos centrales, puntos fronterizos y puntos de ruido [1]. Para los valores especificados de y, la función implementa el algoritmo de la siguiente manera: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

  • Si dos clústeres tienen densidades variables y están cerca uno del otro, es decir, la distancia entre dos puntos de borde (uno de cada clúster) es menor que, a continuación, puede fusionar los dos clústeres en uno.epsilondbscan

  • Es posible que todos los clústeres válidos no contengan al menos observaciones.minpts Por ejemplo, puede identificar un punto de borde perteneciente a dos clústeres que están cerca uno del otro.dbscan En tal situación, el algoritmo asigna el punto de borde al primer clúster detectado. Como resultado, el segundo clúster sigue siendo un clúster válido, pero puede tener menos observaciones.minpts

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.

Introducido en R2019a