Introducción

El avance de la tecnología ha proporcionado muchas comodidades para la sociedad en distintos ámbitos y campos técnicos (Suasnabas et al., 2016). Actualmente se cuenta con tecnologías para facilitar la recolección de información, como los dispositivos del sistema de posicionamiento global (GPS), (Juca Maldonado & Burgo Bencomo, 2016) que se puede encontrar múltiples artefactos de manera cotidiana o en el ámbito profesional, comúnmente vistos en vehículos, Smartphone, relojes inteligentes y entre otros, donde permite seguir sus trayectorias (Tusa et al., 2016). Estos instrumentos suministran grandes cantidades volúmenes de registros a las bases de datos, donde se adquiere información geoespacial (Reyes Zambrano & Cedeño Pozo, 2018).

Algoritmos de agrupamiento

El agrupamiento de datos es una técnica muy utilizada a la hora de identificar características comunes entre instancias de un mismo problema (Madhulatha, 2012). Actualmente las técnicas de agrupamiento brindan soluciones identificando grupos de datos en áreas muy diversas, tales como salud, finanzas, telecomunicaciones, agricultura y transporte, entre otras (A. Jain, 2009).

A lo largo del tiempo investigadores en todo el mundo han propuesto mejoras a las limitantes identificadas en algunas técnicas como en (Bindiya M Varghese, 2013) en otros casos se han mejorado las técnicas para que funcionen en un contexto especifico como, por ejemplo, para la minería de datos espacial (Tork, 2012) o para el análisis de trayectorias GPS (Mazimpaka & Timpf, 2016).

Figura 1.
Taxonomía de los tipos de algoritmos clustering.
Fuente: Autores.

En la figura 1 se muestran una taxonomía de los tipos de algoritmos clustering, existen muchas clasificaciones en la literatura revisada, pudiendo utilizarse cualquier clasificación dependiendo del tipo de investigación a realizarse.

Trayectorias

Una trayectoria GPS está definida por un conjunto de ubicaciones geográficas, cada una de las cuales se encuentra representada por su latitud y longitud, en un instante de tiempo. Es un conjunto de puntos que representan el espacio-tiempo, quedando definido como se observa en la ecuación 1:

Cada punto posee tres valores, que son: latitud (x), longitud (y) y tiempo (t). Al tener un conjunto de puntos, el trazo sobre estos en orden de tiempo (t) es el correspondiente a la trayectoria del objeto dado. Cada punto puede tener un conjunto de valores adicionales según sea necesario, tales como velocidad, altura o estado que presenta el objeto en el tiempo (t) que se obtiene o analiza de la información de este, en la figura 2 Se representa una trayectoria en un espacio 2D.

Figura 2.
Representación de una trayectoria en un espacio 2D como puntos a intervalos de tiempo iguales.
Fuente: Autores.

Como podemos observar se representa una trayectoria en un espacio 2D como puntos a intervalos de tiempos iguales, notándose la existencia de un punto inicial (start) y de un punto final (end) los cuales limitan la trayectoria.

Algoritmos de agrupamiento de trayectorias GPS

Los algoritmos de agrupamiento son fundamentales en el momento de definir el enfoque de una investigación, en este trabajo el enfoque es sobre agrupamiento de trayectorias vehiculares. De acuerdo a lo interpretado por (Vera, 2018) “clustering es una técnica no supervisada que tiene como tarea generar agrupaciones de acuerdo a la conexión de las semejanzas o diferencia que existen entre los objetos que se analizan.

En la literatura se han identificado una serie de soluciones que realizan agrupamiento de trayectorias. Estas soluciones mejoran algoritmos tradicionales de agrupamiento adaptándolos a un contexto en particular o aplicabilidad y utilizando medidas de similitud entre trayectorias no convencionales (C. Riquelme, J., Ruiz, R., & Gilbert, K.,2006).

(Yuan & Raubal, 2014) Adicionalmente combina dos paradas consecutivas con la misma ubicación geográfica y un intervalo temporal corto, haciendo uso del método cuantitativo de Yuan (Laohakiat, S., & Sa-ing, V.,2021).

En el algoritmo Tra-DBScan (L. X. Liu, J. T. Song, B. Guan, Z. X. Wu, and K. J., 2012) se utiliza el algoritmo DBScan, haciendo uso de una fase de segmentación de trayectorias, realizando una partición de las trayectorias en tramos y utilizando la distancia de Hausdorff como medida de similitud. Esta métrica considera la distancia perpendicular, angular y paralela de los distintos puntos GPS que son parte de los segmentos de las trayectorias.

Por otra parte, en (Ferreira et al., 2013) se presenta una nueva técnica de agrupamiento de trayectorias que utiliza campos vectoriales para representar los centros de los grupos y proponer una definición de similitud entre trayectorias. El campo vectorial k-means, aunque recuerda al algoritmo k-means se trata de una formulación nueva para la agrupación de trayectorias, que puede encontrar patrones globales que no son aparentes a nivel local en trayectorias ruidosas o incluso trayectorias parciales, además de ser altamente paralelizadle lo que le permite fácilmente escalar a grandes conjuntos de datos.

En (Q. Yu, Y. Luo, C. Chen, and S. Chen, 2019) se propone un modelo de trayectoria mejorado y se presenta un nuevo algoritmo de agrupación de trayectorias, con una medida de similitud de trayectorias que calcula la distancia entre dos trayectorias basado en múltiples características de la trayectoria, logrando maximizar la similitud de las trayectorias en el mismo grupo.

Hoy en día continúan los esfuerzos de investigación como se evidencia en (Y. Yang, J. Cai, H. Yang, J. Zhang, and X. Zhao, 2020) que propone un nuevo algoritmo de agrupamiento de trayectoria (TAD), entre sus principales ventajas están las siguientes: Introduce un factor de tolerancia al ruido, que puede evaluar dinámicamente y reducir el impacto del ruido en el proceso de ejecución del algoritmo; Integra las características de tiempo y espacio en una misma función de medición para mejorar la precisión del agrupamiento; Construye una nueva función de densidad, que distingue con mayor precisión diferentes tipos de puntos en trayectorias y encuentra estancias de trayectorias basada en análisis de datos de densidad espacio-temporal. Dos nuevas métricas: NMAST (Capacidad de movimiento y tiempo de permanencia en el vecindario) y un factor NT (tolerancia de ruido) se definen en este algoritmo.

En (Reyes et al., 2020) se define un método de segmentación de trayectorias GPS que utiliza el algoritmo Kmeans para el agrupamiento. El método tiene un componente de segmentación de trayectorias y un componente de agrupamiento de sub-trayectorias. La primera divide las trayectorias GPS en sub-trayectorias caracterizadas por no presentar cambios de dirección significativos, lo que favorece su análisis.

Algoritmos de agrupamiento de trayectorias GPS que procesan flujos de datos

Una de las aplicabilidades importantes al momento de analizar flujo de tráfico en una ciudad, es identificar patrones dentro agrupaciones de trayectoria de manera incremental, ya que estos algoritmos obtienen grandes cantidades de información. El aprendizaje incremental se refiere a las estrategias de aprendizaje en línea que funcionan con recursos de memoria limitados. (Gepperth & Hammer, 2016) Estos volúmenes de datos se denominan "flujos de datos"(data streams), porque se generan de forma secuencial a gran velocidad. (Molina & Hasperué, 2018).

Algoritmo de Clustering de flujos de datos a evaluar

Esta investigación evalúa un algoritmo de clustering llamado Dyclee, este algoritmo tiene la capacidad de procesar flujos de datos en entornos dinámicos. Este algoritmo está conformado por dos etapas, una primera etapa donde se realiza un agrupamiento por distancia y una segunda etapa donde se realiza un agrupamiento por densidad. La lectura de datos se puede realizar de manera incremental (flujos de datos) permitiendo obtener agrupamientos dinámicos en cada evolución.

El algoritmo Dyclee fue implementado utilizando el lenguaje de programación R adaptando la lectura y procesamiento de trayectorias y el agrupamiento por la dimensión de la velocidad. Se realizaron mediciones en 8 instantes de tiempo secuenciales que para propósitos de nuestro trabajo denominamos evoluciones, logrando obtener rangos comunes de velocidades. De la misma manera se realizaron mediciones de dos métricas de calidad para agrupamientos: Silhouette y Davies Bouldin y los resultaron fueron satisfactorios.

Materiales y Métodos

En éste trabajo se utilizó el algoritmo Dyclee para procesar diferentes conjuntos de datos que corresponden a trayectorias GPS para lograr identificar patrones de velocidad. Para ello la metodología utilizada permitió definir dos pasos:

1. 1. La definición de celdas para el área de procesamiento.

   La adaptación para que el algoritmo Dyclee procese trayectorias y realice el agrupamiento por la dimensión de velocidad.

El algoritmo de DyClee procesa datos de manera dinámica, en el caso de este algoritmo se optó por realizar flujos de datos los cuales se los denominarán evoluciones que ingresarán al procesamiento a partir de determinados periodos de tiempo, se utiliza por defecto el valor de 3, este valor está en unidades de minutos e indica la duración que tendrá cada evolución y los datos que ingresarán corresponderán a datos que se encuentren en ese rango de minutos de acuerdo a cada evolución que se realizarán de manera secuencial.

Definición de celdas para el área de procesamiento

Para poder enfocar los análisis de trayectorias en determinadas ubicaciones en una ciudad se realizar el trazo de celdas dentro del área a procesar. Para ello, tras haber obtenido la cantidad de ejecuciones necesarias para abarcar todo el conjunto de datos, se puede empezar a definir las celdas y el área que ocupará cada celda, tanto para el largo como el ancho, usando la proporción de n/10000 en donde n será la longitud de los lados de cada celda como se observa en la ecuación 2.

Valor de la longitud a usar=n/(100 000)=200/100000=0.002 (2)

Por ejemplo, el siguiente cálculo define el valor a utilizar para un largo de 200 metros y un ancho de 200 metros: El resultado es 0.002 que representa un largo de 200 metros y un ancho de 200 metros por lo que el área definida quedaría de tamaño 200x200 m2, si se traslada esta área a un mapa y se visualiza, se puede visualizar el área que ocupará cada celda, como se observa en la figura 3.

Figura. 3.
Área de procesamiento
Fuente: Autores.

Una vez que se definió el tamaño de la celda dentro del área de procesamiento, se implementó el algoritmo a evaluar, llamado Dyclee, realizando su adaptación para el procesamiento y análisis de trayectorias GPS.

Algoritmo Dyclee adaptado

Para pode procesar las trayectorias GPS se realizó una adaptación del algoritmo DyClee. En la tabla 1 se identifican algunas definiciones de Dyclee y que fueron utilizadas en la adaptación.

Para este trabajo se tuvo que modificar el parámetro que se menciona a continuación:

RelativeSize: Especifica el tamaño relativo que alcanzarán los μC con respecto a la Hipercaja. Permite crear microclusters de diferentes densidades y a su vez permite que se reconozcan regiones de bajas densidades que se encuentran conectadas. Debe tomar valores entre 0 y 1; en donde los valores cercanos a 1 creará microclústers de tamaños cercanos a la hipercaja y si es cercano a 0, tomará tamaños más pequeños. El tamaño de los microclusters se establece como una fracción del rango de la Hipercaja. Este parámetro es obligatorio, es definido por el usuario para DyClee y se ajusta de forma experimental.

En este artículo, en la primera etapa del algoritmo, en vez de utilizar directamente las ubicaciones GPS y su densidad, se consideraron las velocidades de los tramos de trayectorias que se encuentran comprendidos en cada celda. De esta forma, para un periodo de tiempo dado, cada celda será representada por la velocidad promedio de los tramos de trayectorias que contiene. Esto implica recortar las trayectorias adecuadamente considerando que las variaciones de velocidad pueden llevar a que un vehículo circulando a muy alta velocidad no sea registrado (o posea muy pocas ubicaciones GPS) al pasar por una celda. Además, es importante considerar que las velocidades deben ser promediadas considerando los vehículos y no la cantidad de ubicaciones registradas. En lo referido al tamaño de los microclusters, el valor del parámetro” Relative Size” especifica el tamaño relativo del parámetro” HiperBox” con respecto al área a procesar. Es decir que a medida que su valor se reduce la cantidad de microclusters aumenta y viceversa.

En su segunda etapa, el algoritmo analiza las densidades de los microclústers conformados y los clasifica en dos categorías: densos y semidensos. A partir de los microclusters densos comienza a unir aquellos que se encuentren directamente conectados. Dos microclustres se considerarán directamente conectados si la distancia máxima a la que pueden encontrarse los centroides de dos microclusters, con densidades similares, no supera el valor del parámetro” HiperBox”. Es decir que, a medida que se incrementa el valor del parámetro” HiperBox”, la cantidad de clusters será menor y, por lo tanto, los rangos de velocidades en el área de interés tendrán mayor amplitud.

Conjunto de datos utilizados

Los conjuntos de datos a utilizar son muestras representativas de los conjuntos de datos de trayectorias GPS de Guayaquil-Ecuador y de Roma-Italia. Para el conjunto de datos de Guayaquil dado que se trata de una parte del conjunto de trayectorias, para efectos de análisis se seleccionaron los registros en un horario comprendido entre las 16:30 hasta las 18:30 horas Como resultado de este proceso de filtrado se obtuvieron 29503 registros que representan 206 trayectorias de todo el conjunto de datos. Para el conjunto de datos de Roma, se efectuó el análisis en el horario comprendido entre las 18:00 hasta las 20:00 horas. Como resultado de este proceso de filtrado se obtuvieron 33793 registros

que representan 137 trayectorias de todo el conjunto de datos.

En la Tabla 2, se puede visualizar los conjuntos de datos con su correspondiente cantidad de trayectoria y la cantidad de puntos o registros generados y utilizados, en los experimentos diseñados.

Los conjuntos de datos tienen similares características, las columnas utilizadas se observan en la tabla 3.

Definición de experimentos

Para validar este trabajo se definieron dos experimentos con cada uno de los conjuntos de datos a utilizar. En cada experimento se realizan las mismas parametrizaciones iniciales con respecto al relative size, hipercaja, período de tiempo, evoluciones. Para cada período de tiempo consecutivo, evoluciones, se calcula las velocidades mínimas, máximas y promedio para realizar una interpretación de los rangos de velocidades. También por cada evolución se obtiene la cantidad de grupos densos, semi-densos y poco densos, así como también los indicadores de silhoutte y Davies bouldin que indican la calidad de los grupos.

Resultados y Discusión

Experimento 1. Algoritmo DyClee - Roma

La configuración de DyClee se realiza mediante parámetros necesarios. El valor para el parámetro” Relative Size” fue de 0.2, a partir de este valor y en base al área de procesamiento se define el valor de las dimensiones de la” hipercaja”. Se dividieron los 30557 registros del conjunto de datos de Roma-Italia en 8 bloques de 15 minutos cada uno y se los analizó en forma consecutiva.

Como podemos observar en la tabla 4 la información representada para cada celda consiste principalmente en la velocidad promedio de los vehículos registrados en su interior durante el periodo de tiempo analizado. Para cada grupo se indican sus velocidades mínimas, máxima y promedio, así como el desvío de las velocidades pertenecientes a dicho grupo. Existen 8 evoluciones para el agrupamiento realizado con la adaptación del algoritmo DyClee de las cuales podemos resaltar que la velocidad promedio más alta se encuentra en la evolución 7 con un valor de 96,35 esta velocidad se da en un grupo atípico el cual está representado con valores negativo, por otra parte, la velocidad promedio más baja se encuentra en la evolución 6 con un valor de 1,71 (Ver Tabla 4).

En la Tabla 5 podremos observar los resultados de algunos indicadores de agrupamiento evaluados durante las 8 evoluciones, al final de la tabla se observa las respectivas sumatorias y promedios. A lo largo de las evoluciones el algoritmo obtiene 5 grupos densos-semidensos de forma simultánea. También se destaca que en la evolución 1, 4 y la 5 se obtienen 4 grupos pocos densos o atípicos mientras que en la evolución 2, 3, 6, 7 y 8 se obtienen 5 grupos pocos densos o atípicos, dando como sumatoria 37 grupos poco densos. La evolución con más puntos en grupos densos es la 7 con un valor de 4766 con respecto a otras que obtuvieron un puntaje relativamente menor. El valor de Silhouette más alto en la primera etapa se ubica en la evolución 4 con 0,76060, sin embargo, el valor más alto de la segunda etapa es de 0,64525 y se ubica en la primera evolución. El valor más alto de Davies Bouldin etapa 1 está ubicado en la evolución 2 con un valor de 0,46921 y de la etapa2 se ubica en la misma evolución 2 con un valor de 0,58556 (Ver Tabla 5).

Experimento 2. Algoritmo DyClee – Guayaquil

La configuración de DyClee utilizada para el experimento con el conjunto de datos de Guayaquil es similar a la utilizada para el conjunto de datos de Roma.

Como podemos observar en la tabla 6 la información representada para cada celda consiste principalmente en la velocidad promedio de los vehículos registrados en su interior durante el periodo de tiempo analizado. Para cada grupo se indican sus velocidades mínimas, máxima y promedio, así como el desvío de las velocidades pertenecientes a dicho grupo. Existen 8 evoluciones para el agrupamiento realizado con la adaptación del algoritmo DyClee de las cuales podemos resaltar que la velocidad promedio más alta se encuentra en la evolución 5 con un valor de 106,57 esta velocidad se da en un grupo atípico el cual está representado con valores negativo, por otra parte, la velocidad promedio más bajo se encuentra en la misma evolución 5 con un valor de 4,87 (Ver Tabla 6).

En la tabla 7 podremos observar los resultados de algunos indicadores de agrupamiento evaluados durante las 8 evoluciones. Las evoluciones 1, 2 y 7 tiene 4 grupos densos, las evoluciones 3 y 6 tienen 5 grupos densos, la evolución 4 tiene 6 grupos, la evolución 5 tiene 7 grupos y la evolución 8 tiene 3 grupos totalizando 38 grupos densos-semidensos. También se destaca que en la evolución 2, 3, 6 y 7 se obtienen 4 grupos pocos densos o atípicos, mientras que en la evolución 1 tiene 2 grupos, la evolución 4 tiene 5, la evolución 5 tiene 6 y la evolución 8 tiene 3 totalizando 32 grupos densos o atípicos. La evolución más alta de puntos en grupos densos es la 4 con un valor de 7983 con respecto a otras que obtuvieron un puntaje relativamente menor. El valor de Silhouette más alto en la primera etapa se ubica en la evolución 1 con un valor de 0,56771, de igual manera, el valor más alto de la segunda etapa se ubica en la misma evolución es de 0,71126. Por otro lado, el valor más alto de Davies Bouldin etapa 1 está ubicado en la evolución 4 con un valor de 0,46138 y de la etapa 2 se ubica en la evolución 6 con un valor de 0,60718 (Ver Tabla 7).

Conclusiones

Al finalizar el trabajo se ha logrado la implementación del Algoritmo Dyclee para que procese trayectorias vehiculares utilizando la dimensión de velocidad. A si mismo se ha logrado configurar un área de procesamiento para los 2 conjuntos de datos utilizados en donde se definieron celdas que proporcionan resúmenes de los datos de las trayectorias que se envían al algoritmo de clustering para la identificación de grupos.

Una vez realizado los experimentos y el análisis de los resultados con los dos conjuntos de datos esto es Roma y Guayaquil, se lograron identificar patrones con respecto a la velocidad promedio más alta existentes en las 8 evoluciones.

También con respecto a los indicadores de agrupamiento luego de realizados los experimentos se identificaron las evoluciones con las respectivas cantidades de grupos densos-semidensos, así como también las cantidades de grupos pocos densos-atípicos. Con respecto a las métricas de calidad Silhouette y Davies Bouldin, estas presentan resultados con respecto a la cantidad de los agrupamientos que son satisfactorios.

Como trabajo futuro se plantea poder incorporar a los experimentos y análisis otros conjuntos de datos y realizar el agrupamiento incorporando la dimensión de la ubicación de las trayectorias GPS para de esta forma enriquecer el análisis previo a una toma de decisiones.

Referencias Bibliográfica

Bindiya M Varghese, U. A. P. J. (2013). Spatial Clustering Algorithms - an Overview. Asian Journal of Computer Science and Information Technology, 3(1).

Ferreira, N., Klosowski, J. T., Scheidegger, C. E., & Silva, C. T. (2013). Vector Field k-Means. 32(3).

Gepperth, A., & Hammer, B. (2016). Incremental learning algorithms and applications. ESANN 2016 - 24th European Symposium on Artificial Neural Networks, 357–368.

Juca Maldonado, F., & Burgo Bencomo, O. B. (2016). lended Learning as a model for universities use Moodle. Investigación, Tecnología e Innovación, 8(EE SE-Article), 27–34. https://doi.org/10.53591/iti.v8iEE.140

Madhulatha. (2012). An overview of clustering methods. Intelligent Data Analysis, 11(6), 583–605. https://doi.org/10.3233/ida-2007-11602

Mazimpaka, J. D., & Timpf, S. (2016). Trajectory data mining: A review of methods and applications. Journal of Spatial Information Science, 13(2016), 61–99. https://doi.org/10.5311/josis.2016.13.263

Molina, R., & Hasperué, W. (2018). D3CAS : un Algoritmo de Clustering para el Procesamiento de Flujos de Datos en Spark. 452–461. http://sedici.unlp.edu.ar/bitstream/handle/10915/73223/Documento_completo.pdf-PDFA.pdf?sequence=1&isAllowed=y

Reyes, G., Lanzarini, L., Hasperué, W., & Bariviera, A. F. (2020). GPS trajectory clustering method for decision making on intelligent transportation systems. Journal of Intelligent and Fuzzy Systems, 38(5), 5529–5535. https://doi.org/10.3233/JIFS-179644

Reyes Zambrano, G., & Cedeño Pozo, A. (2018). Algorithm GR-B for the compression of vehicular trajectories. Jurnaly, 39(28).

Suasnabas, L. S., Rubira, A. K., Casilla, I. N., & Schreiber, M. J. (2016). Uso de la tecnología en la educación universitaria ecuatoriana (p. 12).

Tork, H. F. (2012). Spatio-Temporal Clustering Methods Classification. Doctoral Symposium on Informatics Engineering (DSIE’2012), December, 1–12. https://doi.org/10.13140/RG.2.1.3812.7204

Tusa, F., Maza, J., & Briceño, X. (2016). La construcción de una educación del Buen Vivir a partir del estudio de las tecnologías de la comunicación y la información. In Investigación, Tecnología e Innovación (Vol. 8, Issue 8, pp. 97–106). https://doi.org/10.53591/iti.v8i8.141

Vera, J. (2018). ANÁLISIS DE TRAYECTORIAS VEHICULARES GPS PARA EVALUAR SU CALIDAD DE AGRUPAMIENTO UTILIZANDO ALGORITMOS CLUSTERING DE MINERÍA DE DATOS. Universidad de Guayaquil, 83. http://repositorio.ug.edu.ec/bitstream/redug/41488/1/T-ZAMBRANO ZAMBRANO JOSSELYN JAMILE.pdf

Yuan, Y., & Raubal, M. (2014). Measuring similarity of mobile phone user trajectories- a Spatio-temporal Edit Distance method. International Journal of Geographical Information Science, 28(3), 496–520. https://doi.org/10.1080/13658816.2013.854369

Información adicional

Cómo citar:: Reyes Zambrano, G., Zambrano Meza, E. S., León-Granizo, O., & Crespo León, C. (2023). Evaluación de un algoritmo de agrupamiento de flujo de datos para el análisis de trayectorias GPS. Ecuadorian Science Journal, 6(2), 33-45. https://doi.org/10.46480/esj.6.2.99