r data-mining cluster-analysis dbscan

¿Eligiendo eps y minpts para DBSCAN(R)?



data-mining cluster-analysis (5)

He estado buscando una respuesta para esta pregunta durante bastante tiempo, así que espero que alguien pueda ayudarme. Estoy usando dbscan de la biblioteca fpc en R. Por ejemplo, estoy mirando el conjunto de datos de USArrests y estoy usando dbscan de la siguiente manera:

library(fpc) ds <- dbscan(USArrests,eps=20)

La elección de eps fue simplemente por prueba y error en este caso. Sin embargo, me pregunto si hay una función o código disponible para automatizar la elección de los mejores eps / minpts. Sé que algunos libros recomiendan producir una trama de la kth ordenada distancia a su vecino más cercano. Es decir, el eje x representa "Puntos ordenados según la distancia al kth vecino más cercano" y el eje y representa la "kth distancia del vecino más cercano".

Este tipo de gráfico es útil para ayudar a elegir un valor apropiado para eps y minpts. Espero haber proporcionado suficiente información para que alguien me ayude. Quería publicar una foto de lo que quise decir, sin embargo, todavía soy un novato, así que todavía no puedo publicar una imagen.

No hay una forma general de elegir minPts. Depende de lo que quieras encontrar. Un minPts bajo significa que construirá más grupos a partir del ruido, así que no lo elijas demasiado pequeño.

Para épsilon, hay varios aspectos. Nuevamente se reduce a elegir lo que funcione en este conjunto de datos y en estos minPts y esta función de distancia y esta normalización. Puede intentar hacer un histograma de distancia de knn y elegir un "codo" allí, pero puede que no haya uno visible o múltiple.

OPTICS es un sucesor de DBSCAN que no necesita el parámetro épsilon (excepto por razones de rendimiento con soporte de índice, vea Wikipedia). Es mucho más agradable, pero creo que es una molestia implementarlo en R, ya que necesita estructuras de datos avanzadas (idealmente, un árbol de índice de datos para la aceleración y un montón actualizable para la cola de prioridad), y R tiene que ver con las operaciones de matriz.

De manera ingenua, se puede imaginar que OPTICS hace todos los valores de Epsilon al mismo tiempo y coloca los resultados en una jerarquía de clústeres.

Sin embargo, lo primero que debe comprobar, independientemente del algoritmo de agrupación en clúster que vaya a utilizar, es asegurarse de tener una función de distancia útil y una normalización de datos adecuada. Si su distancia se degenera, no funcionará ningún algoritmo de agrupamiento.

Para obtener detalles sobre la elección de parámetros, consulte el documento a continuación en la pág. 11:

Schubert, E., Sander, J., Ester, M., Kriegel, HP, y Xu, X. (2017). DBSCAN revisado, revisado: por qué y cómo debe (aún) usar DBSCAN. ACM Transactions on Database Systems (TODS), 42 (3), 19.

  • Para datos bidimensionales: use el valor predeterminado de minPts = 4 (Ester et al., 1996)
  • Para más de 2 dimensiones: minPts = 2 * dim (Sander et al., 1998)

Una vez que sepa qué MinPts elegir, puede determinar Epsilon:

  • Grafique las distancias k con k = minPts (Ester et al., 1996)
  • Encuentre el ''codo'' en el gráfico -> El valor de la distancia k es su valor de Epsilon.

Una forma común y popular de administrar el parámetro épsilon de DBSCAN es calcular un gráfico de distancia K de su conjunto de datos. Básicamente, calcula los k vecinos más cercanos (k-NN) para cada punto de datos para comprender cuál es la distribución de densidad de tus datos, para k diferentes. El KNN es útil porque es un método no paramétrico. Una vez que elige un minPTS (que depende en gran medida de sus datos), arregle k a ese valor. Luego, utiliza como epsilon la distancia k correspondiente al área de la gráfica k-distance (para su k fija) con una pendiente baja.

MinPts

Como Anony-Mousse explicó Anony-Mousse , "Un valor de minPts bajo significa que construirá más grupos a partir del ruido, así que no lo elijas demasiado pequeño". .

minPts lo establece mejor un experto en dominios que entiende bien los datos. Desafortunadamente, muchos casos no conocemos el dominio, especialmente después de que los datos se normalizan. Un enfoque heurístico es usar ln (n) , donde n es el número total de puntos a agrupar.

épsilon

Hay varias formas de determinarlo:

1) gráfico de distancia k

En una agrupación con minPts = k, esperamos que las pintas centrales y los puntos de borde ''k-distancia estén dentro de un cierto rango, mientras que los puntos de ruido pueden tener una distancia k mucho mayor, por lo que podemos observar un punto de inflexión en la gráfica k-distance . Sin embargo, a veces puede no haber una rodilla obvia, o puede haber múltiples rodillas, lo que dificulta la decisión

2) Extensiones DBSCAN como OPTICS

OPTICS produce clusters jerárquicos, podemos extraer clusters planos significativos de los clusters jerárquicos mediante inspección visual, la implementación de OPTICS está disponible en el módulo pyclustering Python. Uno de los autores originales de DBSCAN y OPTICS también propuso una forma automática de extraer grupos planos, donde no se requiere intervención humana, para obtener más información, puede leer este documento .

3) análisis de sensibilidad

Básicamente, queremos elegir un radio que sea capaz de agrupar puntos más verdaderamente regulares (puntos que son similares a otros puntos), mientras que al mismo tiempo detectamos más ruido (puntos atípicos). Podemos dibujar un porcentaje de puntos regulares (los puntos pertenecen a un grupo) VS. análisis de épsilon , donde establecemos diferentes valores de épsilon como el eje x, y su porcentaje correspondiente de puntos regulares como el eje y, y con suerte podemos detectar un segmento donde el porcentaje del valor de los puntos regulares es más sensible al valor de épsilon, y Elegimos el valor de épsilon del límite superior como nuestro parámetro óptimo.