Geospatial Analysis: KMeans in Python with Voronoi algorihtm and OpenStreetMap

Although computational geometry algorithms are known in the different careers related to computer science, the information regarding their integration with Machine Learning techniques is rather scarce, or slightly referenced, but not explored in depth. That is why in this article I will delve into this integration between algorithms and how beneficial it is to delimit the “dominance” of a cluster, for this I will use the Voronoi algorithm as it is the most useful algorithm since the centroids of each can be used. cluster to generate a Voronoi region and with that be able to delimit the region of each cluster. I will also add the code along with an application example in geospatial analysis.

Theoretical foundation of the analysis.

Optics, Kmeans, KNN or DBSCAN that is the question.

Although KMeans and KNN are often used justifiably, as they are the most common unsupervised Machine Learning algorithms, it should not be ignored that other types of algorithms may have computational or analytical advantages over the aforementioned algorithms.

For example, if you have a project that seeks to identify noise within the data set that is between or around the clusters, the choice of KMeans and KNN would be erroneous since these are not algorithms to identify noise as if they were. You can do DBSCAN and OPTICS, these being similar to each other, but whose main difference is that DBSCAN uses a density algorithm while OPTICS uses a proximity one, in addition DBSCAN is computationally faster than OPTICS, so it can work better for projects with a large volume of data.

That is why the efficiency of the data model that we have in hand to study will be more or less efficient depending on the type of algorithm we choose and how we optimize its parameters if they are parametric, this is because if these parameters do not fit To the data set, our model will present problems such as those mentioned above in the case of KMeans, the most common being the assignment of different weights between the data, the poor selection of the number of clusters and the anisotropic distribution of the data.

2. The cluster delimitation with Voronoi.

Voronoi diagrams are part of the fundamental algorithms in the field of computational geometry, in this case more specifically it is an interpolation algorithm that results in a diagram based on a cloud of points, and with it, the proximity of points is studied. said points.

From the distance between a pair of points p and q, the average of the distance || p – q || and with this it is possible to draw a line in the diagram that divides both points, this calculation of means repeated in each of the points comparing them with each other results in the generation of the Voronoi diagram formed by the vertices as an intersection between said lines formed at starting from   || p – q || and the Voronoi region as a result of the union of said vertices. This region is the one that will later be used as a visualization of the geometric division of a cluster.

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

With this type of diagram you can study the proximity between a point and the Voronoi points, from which the entire diagram is obtained. We can apply the same thing in Machine Learning unsupervised learning algorithms, converting the centroids as the Voronoi points that are needed to be able to make the entire diagram on the visualization obtained by an unsupervised algorithm.

This is applicable because it follows a clear logic: If a cloud of points is obtained with which to form a cluster in Machine Learning, its centroid can be obtained from these points and thus apply this computational geometry technique.

3. General rules.

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 clusters que definan dicho modelo.
4. A partir de las regiones de Voronoi formadas por los clusters, 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 clusters, 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.
   

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 clusters 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.
   

Código para hacer el análisis geoespacial.

Con el fin de aplicar esta serie de “reglas” a un caso práctico para hacer más ilustrativa la explicación, se usarán datos reales sobre bares en el municipio de Chamberí, y a partir de dicha información se usarán los algoritmos para profundizar más en dicha información se buscará llegar a una conclusión: Teniendo en cuenta los datos para luego hacer un análisis geoespacial ¿En que zona de Chamberí sería mejor establecer un nuevo bar?

En cuanto a los datos para usar en el código, también dejo el grupo de puntos geoespaciales con latitud y longitud en formato de coordenadas de grados decimales convertidas a coordenadas estándar UTM-30 basado en el mapa UTM de España que para este caso serán bares, esta información luego puede usarse para comparar la dominancia de los clusters en el diagrama y comparar los datos entre sí.
Las coordenadas de bares en UTM-30 de Chamberí se encuentran disponibles para descargar como archivo csv en este link 🙂

'''
#====================== DATOS Y ALGORITMOS ======================
'''

#Importación de librerias 
import matplotlib.pyplot as plt 
import osmnx as ox
from scipy.spatial import Voronoi, voronoi_plot_2d 
from sklearn.cluster import KMeans
import pandas as pd


#Mapa del distrito
distrito = ox.graph_from_place('Chamberí, Madrid, Spain', network_type='drive') 
streets_graph = ox.projection.project_graph(distrito)

streets = ox.graph_to_gdfs(ox.get_undirected(streets_graph), nodes=False, edges=True, fill_edge_geometry=True)
puntos = pd.read_csv('/home/usuario/documentos/mapeado.csv', header=None) #Datos
km = KMeans(n_clusters= 4, random_state=0).fit(puntos) #Modelo KMeans

 
 
'''
#====================== CREAR MAPA CON KMEANS VORONOI ======================
'''

#Crear el gráfico
f, ax = plt.subplots(figsize=(9, 9))
xmin, xmax = streets.total_bounds[0], streets.total_bounds[2]
ymin, ymax = streets.total_bounds[1], streets.total_bounds[3] 
ax.set_xlim(xmin, xmax)
ax.set_ylim(ymin, ymax)
streets.plot(ax=ax, color='blue', alpha=0.5, zorder=1) # agregar el mapa de calles al gráfico 


#Visualización de puntos y centroides
centers = km.cluster_centers_
plt.scatter(puntos[0], puntos[1], c=km.labels_, s=100)
plt.scatter(centers[:, 0], centers[:, 1], c='black', s=200, marker='*')
plt.scatter(puntos[0], puntos[1], c=km.labels_, s=10, cmap='viridis')


#Voronoi
vor = Voronoi(centers)
voronoi_plot_2d(vor, ax=ax, show_vertices=True)


#Etiqueta y visualización final
plt.xlabel('Longitud')
plt.ylabel('Latitud')
plt.show()

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

Figura 3. Mapa de FIG 2 con cuatro clusters basado en las coordenadas UTM30 de los bares en Chamberí separados con regiones demarcadas por Voronoi, como resultado de un diagrama para análisis geoespacial sobre la “dominancia” de cada clúster en un mapa.

Análisis geoespacial y otras aplicaciones.

Una vez que se tenga todo el procesamiento se puede empezar a usar la imagen de los resultados para hacer una inferencia analítica tanto sobre los datos como de la imagen final del código, por ejemplo usando de comparación cada clúster según otro tipo de empresas cercanas y ver si existe algún patrón lógico entre los ingresos de esas empresas respecto al clúster que pertenecen, etc.

En esta fase no puedo agregar el resto del ejemplo debido a que depende de lo que se quiera analizar, y va más orientado a la ambigüedad del objetivo del análisis que de un patrón más o menos organizado y metódico como puede ser el código que he dejado más arriba, así que eso implica que esta fase depende de quien lo analiza y no del metodo en sí. Pero la idea principal es que una vez delimitado los clusters, se pueden comparar y estudiar de forma individualizada, ya que en un grupo de datos grandes se puede cometer fallos al delimitar a ojo si un cierto punto pertenece o no al cluster ya sea Kmeans, KNN o el que sea, cosa que acaba resolviendo bastante bien el algoritmo de Voronoi.

Aplicación en marketing.

Esta unión entre Kmeans y Voronoi al tener unos clusters delimitados por una región de Voronoi o como me gusta llamarlo a mi, la dominancia del cluster, lo podemos aplicar también para el marketing, por ejemplo, en lugar de tener “latitud” o “longitud” de datos geoespaciales podríamos tener una relación entre ingresos de un grupo de usuarios y lo que suelen gastar, de forma que se podría optimizar una publicidad de forma más eficiente usando la región de Voronoi como una ayuda extra para delimitar una publicidad de marketing a un grupo dado, pero eso lo dejaré como un tema pendiente para otros artículos ya que a mi parecer este ejemplo con código es bastante completo.

Aplicación en medicina.

Citando al artículo de la Wikipedia que habla sobre el algoritmo de Voronoi: “Un uso particularmente notable fue en el análisis de la epidemia de cólera de1854 en Londres llevado a cabo por el médico John Snow, el cual determinó una fuerte correlación de muertes con la proximidad a una determinada bomba de agua —a la postre contaminada— en Broad Street (en el distrito de Soho)”.
Incluso en el ámbito médico tiene su aplicación, aunque en aquella época los datos se agrupaban de forma manual sin usar algoritmos no supervisados, pero aún así eso lo que puede confirmar es que siempre y cuando tengas datos que puedas agrupar o “clusterizar” entonces si aplicas Voronoi podrás inferir de mejor manera en los datos comparándolos entre distintos clusters.