[MÚSICA] Bienvenidos al nuevo video de nuestro curso de Minería de Datos. En este video veremos un nuevo algoritmo de clustering, conocido como DBSCAN. Lo que principalmente nos motiva en este video es conocer un algoritmo que funciona de una forma completamente distinta al algoritmo K-Means y al algoritmo de clustering jerárquico. Esto hace que DBSCAN pueda ser más adecuado que las técnicas revisadas anteriormente en algunos casos en la práctica. DBSCAN es un algoritmo de clustering que está basado en la idea de conectar datos en el mismo cluster si estos están en una misma zona de densidad de datos. Este criterio genera clusters de formas arbitrarias, típicamente DBSCAN se usa para realizar clustering en mapas geográficos por ejemplo. Lo primero que debemos hacer es definir algunos conceptos. El primer concepto es el de core object, un dato corresponde a un core object si ocurre que tiene un número de vecinos que supera un umbral previamente definido dentro de un radio previamente definido. Vemos entonces que aquí you detectamos dos parámetros del algoritmo, el número mínimo de vecinos y el radio donde contaremos a estos potenciales vecinos. La intención detrás de esta definición es que un core object es un punto candidato a formar un cluster, you que está rodeado de vecinos a una distancia muy baja, en otras palabras, por una alta densidad de datos. Por ejemplo, supongamos que el mínimo número de vecinos es 3, en la figura vemos un punto marcado con una x, dado el radio r, ese punto tiene tres vecinos, por lo tanto, es un core object. Ahora vemos un caso donde el punto z tiene solo dos vecinos dentro del radio r, por lo tanto, z no es un core object. Podemos you intuir entonces que el algoritmo DBSCAN parte buscando dentro de la base de datos a todos los puntos que son core object, para así formar los clusters iniciales, en este caso, los mismos core objects y luego expandir estos clusters, como veremos luego. En la figura podemos chequear que los puntos m, p, o, j y r son efectivamente core objects, ahora el siguiente paso es expandir estos clusters. Otra definición que tenemos que ver es la siguiente. Diremos que un objeto h es directamente alcanzable por densidad desde otro objeto o, si es que h está dentro de la vecindad de o, definida por su radio r y además o es un core object. La figura muestra un esquema de la definición anterior. La intuición detrás de esta definición es que estamos viendo cuáles serán los objetos que un core object podrá juntar a su propio cluster. Los primeros objetos que cada core object podrá adjuntarse son los alcanzables directamente por densidad. Otro paso natural del algoritmo será continuar la expansión de los clusters, es evidente entonces que el siguiente paso es que cada core object adjunte a su cluster a los puntos que son alcanzables desde los puntos que recién se adjuntó. Aquí tenemos otra definición, un objeto s es alcanzable indirectamente por densidad desde otro objeto o, si existe una secuencia de objetos donde cada objeto es directamente alcanzable por densidad desde la anterior. En la figura vemos que el objeto s es alcanzable desde o en forma indirecta a través de h, puesto que h es directamente alcanzable desde o y s es directamente alcanzable desde h. Es importante notar que los objetos intermedios que continúan la cadena de alcances deben ser todos core objects. El proceso anterior da pie para una nueva definición. Vamos a decir que dos objetos, p y s, están conectados por densidad, si existe un objeto h, tal que p es alcanzable por densidad desde h y también s es alcanzable por densidad desde h. Veamos un ejemplo entonces. En los datos que aparecen en la figura, supongamos que tenemos los core objects m, p, o, j y r, el radio de vecindad está marcado con azul y el mínimo de vecinos es 3, generamos primero un cluster por cada core object, los marcamos en colores. El siguiente paso es expandir cada uno de los core objects adjuntando a cada uno de ellos los datos que son directamente alcanzables por densidad, marcamos en colores sólidos la asignación actual de los puntos a sus respectivos clusters. Dado que m y p están conectados por densidad, ambos se fusionan en un mismo cluster, los marcamos todos en verde, lo mismo hacemos con los clusters que corresponden a o, j y r. Vemos con círculos punteados que no hay más vecindades que cumplan con el número mínimo de vecinos, por lo tanto, no se pueden alcanzar más puntos. Dado que no quedan más puntos por alcanzar, you que no hay más core objects que puedan adjuntarse más datos, el algoritmo se detiene. Vemos en colores entonces los clusters finales, los puntos rojos no pertenecen a ningún cluster, puede ser considerado como ruido que existe en los datos. [SONIDO] En este video entonces aprendimos cómo funciona el algoritmo DBSCAN. Debemos recordar que es una técnica basada en la densidad de los datos, esto hace que las formas de los clusters que encuentra se da directamente por las formas en que se distribuyen los puntos que generan las zonas de alta densidad. Dado esto, si tenemos datos donde existen clusters que tienen distintos grados de densidades entre sí, lo más probable es que DBSCAN no sea el algoritmo más apropiado. [AUDIO_EN_BLANCO]
