Aplicación de Voronoi en algoritmos no supervisados de Machine Learning con análisis geoespacial

1. Introducción

Si bien los algoritmos de geometría computacional son conocidos en las distintas carreras relacionadas a la informática, la información referente a su integración con técnicas de Machine Learning es más bien escasa, o levemente referenciada, más no explorada en profundidad.

El algoritmo más útil para aplicarlo en Machine Learning no supervisado es el algoritmo de Voronoi, por ello, esta investigación pretende profundizar en su utilidad como herramienta complementaria a los algoritmos no supervisados, enfocando dicha aplicación sobre diferentes tipos de datos dentro de un diagrama geoespacial.

2. Fundamentación Teórica

2.1. Algoritmos

Aunque a menudo se hace uso de KMeans y KNN justificadamente, al ser los algoritmos de Machine Learning no supervisados más habituales, no se debe ignorar que otros tipos de algoritmos pueden tener ventajas computacionales o analíticas frente a los algoritmos anteriormente mencionados.

Por ejemplo, si se tiene un proyecto en el que se busca identificar el ruido dentro del conjunto de datos que están entre o alrededor de los clústers la elección de KMeans y KNN sería errónea ya que estos no son algoritmos para identificar el ruido como si lo puede hacer DBSCAN y OPTICS siendo estos similares entre sí, pero cuya diferencia principal radica en que DBSCAN usa un algoritmo de densidad mientras que OPTICS usa uno de proximidad, además DBSCAN es computacionalmente más rápido que OPTICS, por lo que, puede funcionar mejor para proyectos con un gran volumen de datos.

Por este motivo, la clasificación de los algoritmos es importante, ya que la eficiencia del modelo de datos que tengamos en mano a estudiar será más o menos eficiente según el tipo de algoritmo que escojamos y de cómo optimizamos sus parámetros en caso de que estos sean paramétricos, esto debido a que si dichos parámetros no se adecuan al conjunto de datos nuestro modelo presentará problemas como los que se mencionaron anteriormente para el caso de KMeans siendo los más habituales la asignación de peso distinto entre los datos, la mala selección de cantidad de clusters y la distribución anisotrópica de los datos.

2.2. Voronoi

Los diagramas de Voronoi forman parte de los algoritmos fundamentales en el campo de la geometría computacional, en este caso más específicamente es un algoritmo de interpolación que resulta en un diagrama en base a una nube de puntos, y con ella, se estudia la proximidad de dichos puntos.

A partir de la distancia entre un par de puntos p y q se obtiene la media de la distancia || p - q || y con ello es posible trazar una recta en el diagrama que divida ambos puntos, este cálculo de medias repetido recursivamente en cada uno de los puntos comparándolos entre sí da como resultado la generación del diagrama de Voronoi formado por los vértices como intersección entre dichas líneas formadas a partir de   || p - q || y la región de Voronoi como resultado de la unión de dichos vértices. Esta región es la que posteriormente se usará como una visualización de la división geométrica de un clúster.

Figura 1. Voronoi diagram in a plane 

Fuente: Galishnikova, V. & Jan Pahl, P. (2018)

Con este tipo de diagrama se puede estudiar la proximidad entre un punto y los puntos de Voronoi, los cuales a partir de estos se obtiene todo el diagrama. Esto mismo podemos aplicarlo en los algoritmos de aprendizaje no supervisado de Machine Learning, convirtiendo los centroides como los puntos de Voronoi que se necesitan para poder hacer el diagrama entero sobre la visualización obtenida por un algoritmo no supervisado.

Esto es aplicable porque sigue una lógica clara: si se obtiene una nube de puntos con la cual formar un clúster en Machine Learning, de estos puntos se puede obtener su centroide y con ello aplicar esta técnica de geometría computacional.

2.3. Normas generales

Teniendo en cuenta un conjunto de datos P, cuyos datos forman parte del conjunto a modo de P1, P2, P3...Px, entonces:

1. Los puntos del conjunto P representan datos discretos.
2. Los datos de P pueden usarse en un algoritmo no supervisado de Machine Learning.
3. La representación gráfica de este conjunto aplicado a un algoritmo sirve como base para el modelado de un diagrama de Voronoi, esto con el fin de obtener una serie de clústers que definan dicho modelo.
4. A partir de las regiones de Voronoi formadas por los clústers, se puede profundizar en la información contenida en dicho clúster como una forma de separar el espacio geográfico.
5. Con la información que se pueda extraer de las regiones de Voronoi y clústers, se pueden realizar cálculos con los cuales mejorar el entendimiento de los datos y su contexto, con el fin de realizar conclusiones sobre dichos datos.

2.4. Explicación y funcionamiento 

El diagrama de Voronoi tiene múltiples aportes a los algoritmos de aprendizaje no supervisado en Machine Learning, siendo estos aportes principalmente:

1. Trazar y comparar regiones de Voronoi con lo cual hacer seguimiento del comportamiento de los grupos y su pertenencia comparativa con los clúster más cercanos.
2. Permite al analista de datos tener en mente una clara posibilidad de pertenencia de un punto a un determinado clúster u otro, a pesar de que esta información aún no esté dada.
3. Estudiar la proximidad y los límites entre los diferentes centroides que conforman un clúster.
4. Uso de los vértices como elemento geométrico para visualizar la zona común que existe entre un grupo de clústers próximos entre sí y separados cada uno por una región de Voronoi.
5. A partir de los espacios vacíos generados en un diagrama de Voronoi, verificar si se cumple el tercer teorema, y estudiar la posible existencia de potenciales nuevos grupos por segmentar en la visualización de la clusterización.

3. Ejemplificación

Figura 2. Mapa de bares en Chamberí usando OSMNX y KMeans optimizado a cuatro clústers

Figura 3. Mapa de FIG 2 con cuatro clústers basado en las coordenadas UTM30 de los bares en Chamberí separados con regiones demarcadas por Voronoi

3.1. Implicación del código e hipótesis iniciales

Con la visualización del código finalmente nos quedan delimitado el distrito de Chamberí en cuatro grupos (clústers) distintos, los cuales llamaremos clúster A (azul), clúster B (morado), clúster C (verde) y clúster D (amarillo). También podemos dividir el distrito en forma de Norte - Sur:

Figura 4. Mapa completo de Chamberí separando los datos en grupos, clúster, delimitación del mapa a modo de Norte-Sur y leyenda completa sobre la gráfica 

Ahora, buscando responder a cada una de las hipótesis previamente planteadas con la información disponible se tiene lo siguiente:

1. Los clústers A y C tienen mayor densidad de datos en comparación con los clústers B y D debido a que si se revisa el mapa de Chamberí buscando en Google Maps usando las claves “clínicas en Chamberí”, “colegios en Chamberí” y “discotecas en Chamberí” Google Maps nos mostrará los datos geográficos de ese tipo de empresas.  Al ser un análisis más deductivo que cuantitativo no necesitamos las coordenadas de cada uno de esos datos, sino más bien delimitamos con una circunferencia tal como se hizo con los grupos dentro de los clústers, así podemos modificar el mapa para agrupar las zonas del distrito de Chamberí que contienen más clínicas y/o hospitales, colegios y discotecas. Esta información se usará para buscar una correlación entre la densidad de bares con sus cercanías.

Figura 5. Discotecas en Chamberí

Fuente: Google Maps

Figura 6. Colegios en Chamberí

Fuente: Google Maps

Figura 7. Clínicas y hospitales en Chamberí

Fuente: Google Maps

Figura 8. Mapa de Chamberí con clústers de los puntos (bares) y circunferencias como zonas de empresas relevantes para el estudio: colegios, hospitales y/o clínicas y discotecas

2. Gracias a la información que nos proporciona la respuesta anterior podemos inferir sobre las siguientes respuestas ya que logramos obtener la información implícita relevante:

• Hay más bares en la zona “Sur” de Chamberí respecto a la norte ya que hay mayor concentración de colegios y discotecas.
• Dada la información disponible, la densidad de bares cerca de colegios y discotecas mayormente en los clusters A, C y D implica que estos puedan tener más éxito que los bares del cluster B. Si bien se necesita más información para llegar a dicha conclusión, parece que los clústers A y C tienen una competencia más directa que puede dejar por fuera nuevos bares.
• El mercado en los clústers A y C está saturado por la competencia, debido a su densidad de grupos cercanos de entre 4 a 6 bares, siendo más difícil establecer un bar que pueda ofrecer un servicio diferencial frente a la competencia existente.

3. Sabiendo toda la información disponible con el análisis deductivo implícita dentro del mapa del distrito de Chamberí. ¿Cuáles son las posibles mejores zonas para abrir posibles nuevos bares?

Teniendo en cuenta los datos disponibles podemos concluir que el bar deberá encontrarse en la zona ‘Norte’ para evitar la competencia directa de la zona ‘Sur’, además estar alejado de clínicas y/o hospitales y cercano de alguna discoteca y/o colegios, esto depende de las cercanías. Por ejemplo: Un bar deportivo puede encajar dentro de las cercanías de un colegio.

Figura 9. Mapa de Chamberí con las zonas según relevancia para establecer el nuevo bar

Se han usado estas circunferencias basado a las cercanías para visualizar la relevancia a las zonas cercanas a discotecas, colegios y con menos competencia como zonas de máxima prioridad, las zonas relevantes aquellas con poca cercanía de colegios y discotecas, pero poca competencia con bares cercanos, mientras que las últimas opciones son las zonas con más competencia y/o más cercano de centros médicos como clínicas y hospitales.

Por evitar la competencia directa se descarta por defecto el clúster C y la zona densa del clúster A. El clúster D si cuenta porque cumple con las condiciones para ser una zona de máxima prioridad.

4. Análisis cuantitativo basado en el análisis deductivo de un diagrama Voronoi V(pi) del conjunto de clusters