DBSCAN1
Jurgen Soto
27/4/2020
DBSCAN
DBSCAN: Density-based spatial clustering of applications with noise
Es un método de clusterización adecuado para buscar patrones de agrupación en el espacio físico, este método es más adecuado para los datos en los que los métodos jerárquicos no funcionan del todo bien debido al ruido y los valores atípicos.
Este algorítmo agrupa los puntos que están más cercanos respecto a alguna métrica, comúnmente se utiliza la distancia euclidiana, además para este algorítmo se tiene que cada cluster contendrá un mínimo de puntos.
Diferencias con otros métodos de clusterización.
- ¿Cuándo utilizar DBSCAN?
Este método tiene sus ventajas y desventajas respecto otros métodos de clusterización (K-MEANS por ejemplo) y dependiendo del problema que se quiera analizar se debe elegir el método más adecuado, aún así hay varios aspectos que deben ser tomados en cuenta.
- DBSCAN no necesita que se especifique el número de clusters
- Es más fácil de implementar y de entender
- Con este método podemos garantizar que cada cluster tendrá un mínimo número de puntos
También tiene algunas desventajas
- DBSCAN es menos rápido que K-MEANS
- No funciona bien en clusters de diferentes densidades
- Los parámetros deben ser elegidos con mayor cuidado o precisión
Implementación en R
Parámetros
Este método necesita sólo dos parámetros
eps: Esta es la distancia que se tomará como radio de los clusters
Este parámetro se puede elegir “correctamente” basándose en la distancia del dataset (utilizando un K-distance Plot)
Es preferible utilizar valores pequeños
minPoints: Mínimo de números que deben estar en un grupo para que el algorítmo lo tome com un cluster
- Este número se puede elegir basándose en el número de dimensiones del dataset
\[minPoints \geq D + 1\]
- D es el número de dimensiones del dataset
- Este parámetro debe ser proporcional al tamaño del dataset pero nunca es menor que 3
Ejemplos
1
Con la base iris Tenemos 150 observaciones y 5 variables, una de ellas es “species” que es a la clasificación que trataríamos llegar aplicando el algorítmo así que la removeremos del dataset
Cabe mencionar que sólo hay 3 tipos de especies, así que lo ideal sería obtener esos 3 clusters.
## Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1 5.1 3.5 1.4 0.2 setosa
## 2 4.9 3.0 1.4 0.2 setosa
## 3 4.7 3.2 1.3 0.2 setosa
## 4 4.6 3.1 1.5 0.2 setosa
## 5 5.0 3.6 1.4 0.2 setosa
## 6 5.4 3.9 1.7 0.4 setosaPrimero, tenemos 4 variables restantes en la base así que tomaremos 5 como el mínimo número de puntos.
Ahora, para elegir el radio de los grupos utilizaremos un K-Distance Plot.
#df: dataset sin variable "species"
#k: el número mínimo de puntos que elegimos
kNNdistplot(df, k = 5 )
abline(h = 0.4, lty = 2)
Por lo que se observa en la gráfica tomaremos eps= 0.4
Por último, al aplicar la función y graficar el resultado se observaron 4 clusters y con el fin de que el resultado se acercara más a la clasificación con la que ya cuenta el dataset se modificó el radio a 4.2 y así se llegó a 3 clusters.
#Con eps=0.4
cl<-dbscan(df,eps=0.4,MinPts = 5)
head(cbind(df,cl$cluster))## Sepal.Length Sepal.Width Petal.Length Petal.Width cl$cluster
## 1 5.1 3.5 1.4 0.2 1
## 2 4.9 3.0 1.4 0.2 1
## 3 4.7 3.2 1.3 0.2 1
## 4 4.6 3.1 1.5 0.2 1
## 5 5.0 3.6 1.4 0.2 1
## 6 5.4 3.9 1.7 0.4 1hullplot(df,cl$cluster, main = "Convex cluster Hulls, eps= 0.4")
#Con eps=0.42
cl1<-dbscan(df,eps=0.42,MinPts = 5)
head(cbind(df,cl1$cluster))## Sepal.Length Sepal.Width Petal.Length Petal.Width cl1$cluster
## 1 5.1 3.5 1.4 0.2 1
## 2 4.9 3.0 1.4 0.2 1
## 3 4.7 3.2 1.3 0.2 1
## 4 4.6 3.1 1.5 0.2 1
## 5 5.0 3.6 1.4 0.2 1
## 6 5.4 3.9 1.7 0.4 1hullplot(df,cl1$cluster, main = "Convex cluster Hulls, eps= 0.42")
2
## -- Attaching packages ------------------------------------------------------- tidyverse 1.3.0 --## v ggplot2 3.3.0 v purrr 0.3.4
## v tibble 3.0.1 v dplyr 0.8.5
## v tidyr 1.0.2 v stringr 1.4.0
## v readr 1.3.1 v forcats 0.5.0## -- Conflicts ---------------------------------------------------------- tidyverse_conflicts() --
## x dplyr::filter() masks stats::filter()
## x dplyr::lag() masks stats::lag()## Linking to GEOS 3.6.1, GDAL 2.2.3, PROJ 4.9.3## Google's Terms of Service: https://cloud.google.com/maps-platform/terms/.## Please cite ggmap if you use it! See citation("ggmap") for details.## Parsed with column specification:
## cols(
## nombre = col_character(),
## tipo = col_character(),
## categoria = col_character(),
## lat = col_double(),
## lng = col_double()
## )En este ejemplo se utiliza para encontrar y clasificar geograficamente una ciudad en las zonas comerciales, de salud, entretenimiento, etc.
La base de datos se trata de lugares en el área urbana de una ciudad llamada Mendoza, son 93 lugares, agrupados en 12 categorías generales.
## # A tibble: 6 x 5
## nombre tipo categoria lat lng
## <chr> <chr> <chr> <dbl> <dbl>
## 1 Banco de la Nación Argentina atm banca -32.9 -68.8
## 2 Hospital Central BANCO DE LA NACION ARGENTINA Caj~ atm banca -32.9 -68.8
## 3 Banelco atm banca -32.9 -68.8
## 4 Banelco atm banca -32.9 -68.8
## 5 Cajero Automatico Banelco atm banca -32.9 -68.8
## 6 Citibank bank banca -32.9 -68.8Por ejemplo, en el siguiente mapa se muestra cada bar registrado. En este ejemplo por ser una zona geográfica se debe crear una matriz de distancias entre cada bar respecto a la curvatura de la tierra, para esto se utiliza la paquetería “geosphere”.
## # A tibble: 93 x 3
## categoria tipo n
## <chr> <chr> <int>
## 1 banca atm 93
## 2 banca bank 112
## 3 culto church 248
## 4 culto mosque 2
## 5 culto place_of_worship 4
## 6 culto synagogue 3
## 7 cultura art_gallery 14
## 8 cultura library 18
## 9 cultura museum 55
## 10 educacion school 890
## # ... with 83 more rows## Source : http://tile.stamen.com/toner-background/13/2528/4887.png## Source : http://tile.stamen.com/toner-background/13/2529/4887.png## Source : http://tile.stamen.com/toner-background/13/2530/4887.png## Source : http://tile.stamen.com/toner-background/13/2531/4887.png## Source : http://tile.stamen.com/toner-background/13/2528/4888.png## Source : http://tile.stamen.com/toner-background/13/2529/4888.png## Source : http://tile.stamen.com/toner-background/13/2530/4888.png## Source : http://tile.stamen.com/toner-background/13/2531/4888.png## Source : http://tile.stamen.com/toner-background/13/2528/4889.png## Source : http://tile.stamen.com/toner-background/13/2529/4889.png## Source : http://tile.stamen.com/toner-background/13/2530/4889.png## Source : http://tile.stamen.com/toner-background/13/2531/4889.png## Source : http://tile.stamen.com/toner-background/13/2528/4890.png## Source : http://tile.stamen.com/toner-background/13/2529/4890.png## Source : http://tile.stamen.com/toner-background/13/2530/4890.png## Source : http://tile.stamen.com/toner-background/13/2531/4890.png
Para este ejemplo los parámetros se eligieron de tal forma que en un radio de una cuadra (128 metros) a la redonda de un bar dado, se encuentren al menos otros 5 bares. Entonces epsilon = 128 y minPts = 5.
Esto es sólo con el cluster de bares, ahora se hará con todas las categorías.
En esta gráfica se observan todos los clusters para todas las categorías, no sólo para bares, también para salud, escuela, etc.
Por último simplemente se mostrarán los resultados encima del mapa de la ciudad.
## Coordinate system already present. Adding new coordinate system, which will replace the existing one.
## Coordinate system already present. Adding new coordinate system, which will replace the existing one.
FIN
PD TE QUIERO MUCHO
A caption