Localización de varios almacenes mediante agrupación geoespacial

En un artículo anterior, desarrollamos un modelo capaz de determinar la localización de una instalación (almacén), de acuerdo a un conjunto de ubicaciones existentes (clientes); estas ubicaciones tenían una ponderación determinada (peso, por ejemplo demanda), y basamos nuestro desarrollo en el algoritmo de Centro de Gravedad.

El valor agregado del modelo consistía en la integración de una capa de mapa de calor (para graficar la densidad), un proceso de geocodificación y el uso de un entorno geográfico real. El alcance de este modelo se encuentra determinado por la localización de una sola instalación (depósito, almacén, etc.), y en los casos en los que se requiera determinar múltiples localizaciones, el modelo no aplica.

La pregunta siguiente que nos hacemos es ¿Cómo determinar la localización de múltiples instalaciones? En realidad, hay muchas respuestas para este interrogante, y gran parte de ellas conducen a la agrupación geoespacial (Clustering).

¿Qué es la agrupación geoespacial (Clustering)?

La agrupación geoespacial es un método que se utiliza para asociar un conjunto de objetos espaciales en grupos denominados «clusters«. Los objetos que conforman cada grupo presentan un grado de similitud asociado a un atributo o varios atributos en particular.

El objetivo de la agrupación geoespacial, consiste en determinar una relación entre atributos espaciales (coordenadas, ubicación) y no espaciales (demanda, por ejemplo).

En la literatura encontraremos varios tipos de agrupación geoespacial, cada uno con un enfoque particular, y un campo de aplicación específico; entre los cuales podemos encontrar:

En nuestro caso, que pretendemos determinar la localización de varias instalaciones, considerando la ponderación y ubicación de los puntos existentes, requerimos de un modelo capaz de relacionar atributos espaciales (coordenadas) y no espaciales (peso de cada nodo). Que nos permita, primero agrupar los puntos dados (ubicaciones), y eventualmente, aplicar un algoritmo de Centro de Gravedad, para determinar localizaciones potenciales.

Para tales efectos, vamos a utilizar la agrupación de particiones, que se caracteriza, entre otras, por:

Vale la pena destacar que en cuanto a la agrupación de participaciones, en esta categoría encontraremos varios métodos de partición, y nosotros utilizaremos el método K-Means, un algoritmo de aprendizaje automático (Machine Learning) no supervisado. Para ello utilizaremos Python.

Para sintetizar, el objetivo de este artículo será el de emplear un algoritmo de aprendizaje automático capaz de agrupar nuestros nodos en clusters, de acuerdo a atributos espaciales (coordenadas) y no espaciales (ponderación); para luego, utilizar un algoritmo de Centro de Gravedad en cada clúster para determinar la localización de múltiples instalaciones (almacenes, depósitos, etc.).

En el desarrollo de este ejercicio emplearemos:

Para desarrollar estas herramientas, vamos a plantear un caso típico de localización de múltiples instalaciones a partir de la consideración de otros nodos (nodos de demanda, por ejemplo).

Caso de aplicación

El Departamento de Desarrollo Sostenible de la ciudad de Cali se encuentra implementando una estrategia piloto de recolección de aceite de cocina usado. Ha articulado este proyecto con una Universidad, la cual desarrolló 4 contenedores inteligentes (BIN’s) para la disposición del bioresiduo.

En investigaciones asociadas, la Universidad ha determinado que el reciclaje del aceite es un problema de densidad; esto quiere decir que es vital la ubicación de los contenedores (cobertura), para así mismo optimizar el proceso de disposición y recolección. El proyecto piloto piensa articular a las instituciones de educación como puntos potenciales de recolección. Por medio de las instituciones piensan socializar el programa con la comunidad. El primer reto del proyecto consiste en determinar la ubicación de los contenedores inteligentes (4 unidades). La información relacionada con las instituciones de educación que hacen parte del programa (ubicación geográfica / población estudiantil), se detalla a continuación:

Para tales efectos, desarrollaremos un modelo que apoye el análisis preliminar y la localización de los múltiples contenedores. También, que tenga la capacidad de predecir el grupo (clúster) al que pertenecería un nodo nuevo.

Paso 1: Crear el entorno de trabajo en Colaboratory

Lo primero que vamos a hacer consiste en crear un entorno de trabajo en Google Colaboratory, así que vayamos allá: Abrir cuaderno nuevo.

Verán que tienen un lienzo para programar el modelo, así que en este cuaderno podemos ir generando las líneas de código que explicaremos en los pasos siguientes.

Paso 2: Importar las librerías necesarias

Respecto a las librerías, en la introducción del artículo hicimos una descripción de la funcionalidad de cada una, veamos como importarlas en nuestro entorno:

#Importar las librerías necesarias
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

De esta manera, tenemos todo lo necesario para empezar a desarrollar nuestro código.

Paso 3: Importar los datos desde Excel

De acuerdo a las necesidades del modelo, podemos desarrollar un código que permita la entrada manual de la información, la captura de los datos desde entornos digitales (Internet, por ejemplo), o podemos, desde luego, alimentar nuestro modelo con información contenida en documentos externos, como es el caso de un archivo de Microsoft Excel.

Esta puede considerarse como una de las ventajas de utilizar Python, su capacidad de integrarse con cualquier fuente de datos. En nuestro caso, toda la información se encuentra contenida en un documento de Excel, el cual presenta el siguiente formato:

Ya veremos cómo, parte de estos datos son prescindibles y otros indispensables.

En Colaboratory, el siguiente fragmento permitirá cargar un archivo al entorno de ejecución:

from google.colab import files

uploaded = files.upload()

for fn in uploaded.keys():
  print('User uploaded file "{name}" with length {length} bytes'.format(
      name=fn, length=len(uploaded[fn])))

Al ejecutar este fragmento de código, se abrirá una ventana emergente del explorador que permitirá cargar nuestra base de datos, en nuestro caso el archivo tienen el nombre de cluster.xlsx.

La siguiente línea de código permitirá almacenar los datos contenidos en el documento en un Dataframe de nuestro entorno, dentro de la variable data.

#Leer el documento de Excel y almacenar los datos en la variable data
data = pd.read_excel('cluster.xlsx')

Podemos en cualquier momento confirmar si la carga de los datos se ha realizado correctamente, para eso imprimiremos las primeras cinco filas del  DataFrame:

data.head()

Al ejecutar esta instrucción tenemos la siguiente salida:

Paso 4: Graficar los puntos dados iniciales (Nodos)

Nuestros puntos iniciales, o las ubicaciones de partida son las instituciones de educación que nos otorga el planteamiento del problema.

Para graficar estos puntos utilizamos el sistema de coordenadas disponible: Latitud y Longitud. Así entonces, debemos extraer estos datos de la hoja de cálculo (DataFrame) que hemos importado al modelo; convertir estas coordenadas en una matriz bidimensional (Latitud y Longitud) y graficar los puntos:

#Graficar los nodos dados (ubicaciones)
Lat= data['Latitud']
Lon = data['Longitud']
Peso = data['Peso']
X = []
for i in range(len(data['Latitud'])):
    X.append(Lat[i])
    X.append(Lon[i])

X = np.array(X)

X = X.reshape(-1, 2,)


plt.scatter(Lat, Lon)
plt.show()

Al ejecutar este fragmento de código, tendremos:

Podemos apreciar cómo se encuentran dispersos los nodos iniciales, formando parte un mismo conjunto que es la población. Las coordenadas son latitud y longitud. Los nodos son, una vez más recordamos, las instituciones educativas, de acuerdo al caso de estudio.

Paso 5: Agrupar los nodos geoespacialmente mediante Machine Learning

Cuando mencionamos Machine Learning, a menudo la primera consideración que tenemos es de complejidad. Pues bien, muchos de los algoritmos que hemos utilizado durante décadas son en realidad de aprendizaje automático, como por ejemplo la regresión lineal. El algoritmo de K-Means que emplearemos de forma automatizada mediante Python, utiliza centroides que minimizan la inercia, o el criterio de suma de cuadrados de cada clúster:

Me pareció conveniente explicar un poco la teoría, pero vayamos a la práctica. Toda vez que tenemos los nodos del modelo, lo siguiente que debemos indicar es la cantidad de agrupaciones que queremos (clúster). Ya que el problema plantea la disposición de 4 contenedores, vamos a dividir la población de nodos en 4 conjuntos.

Luego, correremos el algoritmo K-Means, veamos cómo:

#Ejecutar el algoritmo KMeans
clusters = 4
KMean = KMeans(n_clusters=clusters)
KMean_g = KMean.fit_predict(X)
KMean.fit(X)

Lo siguiente que haremos será establecer los centroides de cada clúster, es decir, la ubicación de nuestros contendores. En primer lugar, el modelo nos dará las coordenadas. Utilizaremos la siguiente línea de código:

#Determinar los centroides de cada clúster
KMean.cluster_centers_

Al ejecutarla tendremos:

Estas son las coordenadas que indican el centro de cada uno de nuestros grupos de nodos. Y teóricamente ahí deberíamos disponer nuestros contenedores.

Paso 6: Graficar los clusters y los centroides (Localizaciones múltiples)

El siguiente paso consiste en graficar todas las coordenadas que ya tenemos: tantos los nodos iniciales, como los los centroides, o las localizaciones solución. Veamos cómo:

#Graficar todas las coordenadas (Puntos y centroides)
plt.scatter(X[:,0], X[:,1], c=KMean_g) #Puntos iniciales

#Centroides
plt.scatter(KMean.cluster_centers_[0][0], KMean.cluster_centers_[0][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[1][0], KMean.cluster_centers_[1][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[2][0], KMean.cluster_centers_[2][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[3][0], KMean.cluster_centers_[3][1], s=50, c='r')

Al ejecutar el fragmento tendremos:

Vemos cómo se han efectuado las agrupaciones de los nodos (colores), y los marcadores rojos indican los centroides. Este debería ser el final de nuestro desarrollo, sin embargo, no sé si lo han notado, siempre hemos hablado de centroides, nunca de centros de gravedad o centros de masa. Bien, no sé si también han identificado que en ningún momento hemos considerado el peso de cada nodo, en este caso la población estudiantil de cada institución.

¿Esto qué implica? Implica que hemos desarrollado un modelo que tiene exclusivamente consideraciones espaciales. De hecho, visualmente puede observarse cómo, básicamente los centroides se ubican en lo que podría considerarse el medio de cada clúster, sin ninguna consideración adicional aparente, por lo menos a la vista.

Pues bien, vamos a solucionarlo, para ello debemos retocar algunos de los pasos anteriores:

Paso 5 (Recargado): Agrupar los nodos geoespacialmente mediante Machine Learning (Considerando atributos espaciales y no espaciales)

Dentro de nuestro marco de datos (DataFrame) tenemos la información relacionada al peso de cada nodo (Población estudiantil). Pues bien, vamos a considerarla al ejecutar el algoritmo K-Means.

#Ejecutar el algoritmo KMeans (Considerando el peso de los nodos)
clusters = 4
KMean = KMeans(n_clusters=clusters)
KMean_g = KMean.fit_predict(X)
KMean.fit(X, sample_weight=Peso)

Lo siguiente que haremos será establecer los centroides de cada clúster, que ahora sí serán Centros de Gravedad; es decir, la ubicación de nuestros contendores. En primer lugar, el modelo nos dará las coordenadas. Utilizaremos la siguiente línea de código:

#Determinar los centroides de cada clúster
KMean.cluster_centers_

Al ejecutarla tendremos:

Los centroides han cambiado, ahora son centros de gravedad afectados por el peso de cada nodo. Es posible que incluso haya cambiado la agrupación de los nodos (composición de los clusters).

Paso 6 (Recargado): Graficar los clusters y los Centros de Gravedad (Localizaciones múltiples)

El siguiente paso consiste en graficar todas las coordenadas que ya tenemos: tantos los nodos iniciales, como los los Centros de Gravedad, o las localizaciones solución. Veamos cómo:

#Graficar todas las coordenadas (Puntos y centroides)
plt.scatter(X[:,0], X[:,1], c=KMean_g) #Puntos iniciales

#Centroides
plt.scatter(KMean.cluster_centers_[0][0], KMean.cluster_centers_[0][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[1][0], KMean.cluster_centers_[1][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[2][0], KMean.cluster_centers_[2][1], s=50, c='r')
plt.scatter(KMean.cluster_centers_[3][0], KMean.cluster_centers_[3][1], s=50, c='r')

Al ejecutar el fragmento tendremos:

El resultado respecto a los centroides es diferente. La consideración de un atributo no espacial, en este caso el peso de cada nodo (población estudiantil de cada institución educativa), ha incidido en la ubicación propuesta de las localizaciones solución. Y este debería ser el final de nuestro modelo.

Hemos logrado agrupar nuestros puntos iniciales en clusters, y luego hemos determinado los Centros de Gravedad de cada uno de los clusters.

Por último, veamos una característica de la librería K-Means Análisis predictivo de nodos en clusters, es decir, de acuerdo a unas coordenadas dadas, podemos estimar el grupo al que pertenecerá un nuevo nodo.

Paso 7: Predicción de clusters

En primer lugar ejecutaremos una línea que nos permite identificar a cada nodo dentro de un grupo. Ya que tenemos 4 grupos, estos se identificarán de la siguiente manera: 0, 1, 2, 3.

KMean.labels_

Al ejecutar esta línea tendremos:

Vemos como cada una de las 60 instituciones educativas (nodos), tienen un identificador de grupo dentro del modelo.

Ahor, dadas las coordenadas de un nuevo nodo, podemos predecir el grupo al cual pertenecerá:

sample_test=np.array([-3.433,-76.22])
second_test=sample_test.reshape(1, -1)
KMean.predict(second_test)

Al ejecutar este fragmento tendremos:

Es decir, el algoritmo predice que de acuerdo a las coordenada dadas, el nuevo nodo formaría parte del clúster 0.

Pudimos observar cómo varía el resultado dependiendo de la consideración de atributos netamente geoespaciales, y de atributos no espaciales, como la ponderación de cada nodo.

Integración con mapas de calor y entornos geográficos reales

Uno de los puntos negativos del modelo que acabamos de desarrollar es quizá que no nos permite visualizar gráficamente la densidad de los puntos. Si observamos las gráficas, todos los puntos parecen tener el mismo tamaño, y si bien esta no es una consideración para el funcionamiento del algoritmo; en el análisis preliminar quisiéramos tener esta herramienta. Otra consideración adicional sería la posibilidad de graficar todos nuestros puntos, y los centros de gravedad de cada (clúster) en un entorno geográfico real.

Pues bien, una de las ventajas fundamentales de Python consiste en que podemos integrar distintos desarrollos en nuestros modelos, tal es el caso del desarrollo que efectúanos en un artículo anterior (Mapas de calor y Entornos geográficos reales); de tal manera que podamos complementar nuestro modelo.

No vamos a profundizar en la librerías, ni en la definición de las variables, para eso recomendamos leer el artículo. Veamos entonces, como complementamos este modelo:

import folium
import statistics
from folium.plugins import HeatMap
mediaLong = statistics.mean(Lon)
mediaLat = statistics.mean(Lat)

# Crear un objeto de mapa base Map()
mapa = folium.Map(location=[mediaLat, mediaLong], zoom_start = 13)

# Crear una capa de mapa de calor
mapa_calor = HeatMap( list(zip(Lat, Lon, data["Peso"])),
                   min_opacity=0.2,
                   max_val=data["Peso"].max(),
                   radius=50, 
                   blur=50, 
                   max_zoom=1)

#Creamos el marcador de Centro de Gravedad
tooltip = 'Centro de gravedad'
folium.Marker([KMean.cluster_centers_[0][0], KMean.cluster_centers_[0][1]], popup="Centro", tooltip = tooltip).add_to(mapa)
folium.Marker([KMean.cluster_centers_[1][0], KMean.cluster_centers_[1][1]], popup="Centro", tooltip = tooltip).add_to(mapa)
folium.Marker([KMean.cluster_centers_[2][0], KMean.cluster_centers_[2][1]], popup="Centro", tooltip = tooltip).add_to(mapa)
folium.Marker([KMean.cluster_centers_[3][0], KMean.cluster_centers_[3][1]], popup="Centro", tooltip = tooltip).add_to(mapa)

# Adherimos la capa de mapa de calor al mapa principal
mapa_calor.add_to(mapa)
mapa

Al ejecutar este fragmento tendremos el siguiente resultado:

Ahora tenemos un modelo capaz de agrupar nuestros nodos en clusters de acuerdo a atributos geoespaciales; capaz de determinar los centros de gravedad de cada cluster de acuerdo a atributos no espaciales (en nuestro caso la población de los nodos); capaz de complementarse con una capa de visualización de mapa de calor que nos permite apreciar la densidad y todo esto puede visualizarse en un entorno geográfico real.

Consideraciones finales

Ya lo expresamos anteriormente, la base del algoritmo K-Means es la consideración y minimización de la inercia, y en espacios de muy altas dimensiones, las distancias suelen inflarse, ya que esta no es una medida normalizada.

Sin embargo, para los efectos que hemos empleado, el algoritmo suele arrojar resultados satisfactorios.

El código completo de este desarrollo lo puedes encontrar en nuestro cuaderno: Localización de varias instalaciones mediante agrupación geoespacial y Centro de Gravedad (Python).