Algoritmo de agrupamiento DBSCAN
Este algoritmo utiliza el concepto de agrupamiento basado en densidad y requiere que el número de objetos (puntos u otros objetos espaciales) contenidos en una determinada área del espacio de agrupamiento no sea inferior a un umbral determinado. Filtre áreas de baja densidad para descubrir puntos de muestra de alta densidad. Las muestras de una misma categoría están estrechamente relacionadas entre sí, es decir, debe haber una muestra de la misma categoría no muy lejos de cualquier muestra de la categoría.
Definición de densidad de DBSCAN: DBSCAN describe la proximidad de un conjunto de muestras en función de un conjunto de vecindades, y el parámetro ?(?, MinPts)? . Entre ellos, ? describe el umbral de distancia de vecindad de una muestra específica, MinPts? describe el número de muestras en la vecindad de una muestra específica y ? describe el umbral de la cantidad de muestras en la vecindad de una muestra específica.
La definición anterior se puede entender fácilmente a partir de la figura anterior, donde MinPts=5 y los puntos rojos son objetos centrales porque su vecindario ? tiene al menos 5 muestras. Las muestras negras son objetos secundarios. Todas las muestras directas de densidad del objeto central están dentro de la hiperesfera centrada en el objeto central rojo. Si no están dentro de la hiperesfera, no son muestras directas de densidad. Los objetos centrales conectados por flechas verdes en la figura constituyen una secuencia de muestra alcanzable en densidad. En estas secuencias de muestras con densidad alcanzable, todas las muestras están conectadas por densidad.
El conjunto de muestras conectadas con máxima densidad derivadas de la relación de accesibilidad de densidad es una clase o grupo para nuestra agrupación final. Puede haber uno o más objetos principales dentro de este clúster DBSCAN. Si solo hay un objeto principal, entonces todas las demás muestras de objetos no principales en el grupo están dentro de la vecindad ? de este objeto principal; si hay varios objetos principales, entonces la vecindad ? de cualquier objeto principal en el grupo. Si hay varios objetos principales, entonces el grupo de agrupación DBSCAN de cualquier objeto principal del grupo consta de la vecindad de todas las muestras del conjunto.
1. ¿El proceso de descubrimiento de clústeres por parte de DBSCAN
? Inicialmente, todos los objetos en un conjunto de datos dado D se marcan como "no visitados" y DBSCAN selecciona aleatoriamente un objeto p no visitado, marca p como "visitado" y comprueba si el dominio del clúster de p contiene al menos objetos MinPts. - Si el dominio contiene al menos objetos MinPts. En caso contrario, marque p como punto de ruido. De lo contrario, cree un nuevo clúster C para p y agregue ?- DBSCAN para p a C agregando iterativamente objetos de N que no pertenecen a otros clústeres. Durante este proceso, DBSCAN agregará repetidamente a C objetos en N que no pertenecen a otros grupos. , DBSCAN lo marcará como "visitado" y verificará su dominio ?. Si el dominio P'? contiene al menos objetos MinPts, entonces P'?- DBSCAN continuará agregando objetos a C hasta que C no pueda extenderse, es decir. , N está vacío. En este punto, el grupo C completa la generación y la producción.
?Para encontrar el siguiente grupo, DBSCAN selecciona aleatoriamente un objeto no visitado entre los objetos restantes. El proceso de agrupación continúa hasta que se hayan visitado todos los objetos.
Hay tres cuestiones a considerar:
Primero, hay algunos puntos de muestreo anormales, o una pequeña cantidad de puntos de muestreo fuera del grupo. No están cerca de ningún objeto central. DBSCAN Generalmente los etiquetamos como puntos de ruido.
El segundo es el problema de la medición de la distancia, es decir, cómo calcular la distancia entre una determinada muestra y la muestra del objeto central. En DBSCAN, generalmente se adopta la idea del vecino más cercano y se utiliza una determinada métrica de distancia para medir la distancia de la muestra, como la distancia euclidiana. Esto es exactamente lo mismo que la idea del vecino más cercano del algoritmo de clasificación KNN. Para una pequeña cantidad de muestras, puede calcular directamente las distancias de todas las muestras al buscar vecinos más cercanos. Si la cantidad de muestras es grande, generalmente se utilizan árboles KD o árboles de bolas para buscar rápidamente los vecinos más cercanos.
La tercera pregunta es que la distancia entre algunas muestras y los dos objetos centrales puede ser menor que..., pero los dos objetos centrales no pertenecen al mismo grupo debido a la densidad indirecta. Entonces, si. ¿Qué define la categoría de esta muestra? En términos generales, DBSCAN adopta un enfoque por orden de llegada en este momento, y el grupo de categorías que se agrupa primero etiquetará la muestra como su categoría. Esto muestra que el algoritmo BDSCAN no es un algoritmo completamente estable.
2. Proceso del algoritmo DBSCAN
Ventajas:
En comparación con el algoritmo K-Means tradicional, la mayor diferencia de DBSCAN es que no necesita ingresar el número de categorías k, por supuesto, su mayor ventaja es que puede encontrar grupos de formas arbitrarias, en lugar de K-Means, que generalmente solo se usa para agrupar conjuntos de muestras convexos. Al mismo tiempo, también puede encontrar valores atípicos durante la agrupación y no es sensible a los valores atípicos en el conjunto de datos. En términos generales, si el conjunto de datos es denso y no convexo, entonces usar DBSCAN para la agrupación funcionará mucho mejor que K-Means. Si el conjunto de datos no es denso, no se recomienda utilizar DBSCAN para la agrupación.
Desventajas:
1. Si la densidad del conjunto de muestras es desigual, la diferencia en el espaciado de los grupos es muy diferente y la calidad de la agrupación es muy pobre, generalmente no es adecuado Utilice la agrupación DBSCAN.
2. En comparación con los algoritmos de agrupación tradicionales como K-Means, el ajuste es un poco más complicado. ¿Requiere principalmente un umbral de distancia? En general, la determinación de estos dos parámetros se basa principalmente en valores empíricos. Si cree que los resultados de la agrupación de valores empíricos no son ideales, puede ajustar los valores? y MinPts de manera adecuada y seleccionar los valores de parámetros más apropiados después de múltiples cálculos y comparaciones iterativos. Cuando MinPts permanece sin cambios, si el valor de MinPts es demasiado grande, la mayoría de los puntos se agruparán en el mismo grupo; si el valor de MinPts es demasiado pequeño, provocará la división del grupo cuando MinPts permanezca sin cambios, el valor de MinPts si; es demasiado grande, los puntos en el mismo grupo se marcarán como valores atípicos. Si el valor de MinPts es demasiado pequeño, se descubrirá una gran cantidad de puntos centrales.
3. No es adecuado para datos de alta dimensión, puede realizar operaciones de reducción de dimensionalidad primero
4. Sklearn es muy lento, primero puede implementar una estrategia de reducción de datos
URL de la demostración visual
Artículo de referencia
Liu Jianping