Innova-tsn en la KDD Cup 2021

Innova-tsn ha vuelto a participar en el encuentro anual de Knowledge Discover and Data Mining (KDD) en su edición de 2021. Esta conferencia interdisciplinar aúna a profesionales de la ciencia de los datos, Advanced Analytics y Big Data, entre otros. El KDD Congress, después de más de 30 años, sigue siendo el encuentro más grande y antiguo de este sector, manteniéndose a la vanguardia tecnológica. Este congreso virtual conecta a los científicos del dato y expertos a través de una competición en la que se proponen soluciones inteligentes a desafíos y casos reales. 

Para esta edición de 2021, Innova-tsn, ha competido en dos casos o challenges diferentes: City Brain Challenge, con un equipo de Innova-tsn al 100% y Multi-dataset Time Series Anomaly Detection, junto a otras tres personas de la Universidad Complutense de Madrid. 

City Brain Challenge situaba el problema en una red de carreteras de una ciudad, teniendo que optimizar la afluencia de vehículos minimizando el retraso. El objetivo era el desarrollo de un modelo automatizado de selección de fases, y su coordinación, de los semáforos en las intersecciones de la ya mencionada red de carreteras. Innova-tsn logró posicionarse en el Top 40 mundial en esta prueba. 

Por otro lado, Multi-dataset Time Series Anomaly Detection planteaba encontrar una solución para la detección de anomalías en series temporales univariantes. En este desafío, Innova-tsn obtuvo una posición dentro del Top 25 mundial. 

 

Challenge 1: CITY BRAIN CHALLENGE

El reto propuesto en este caso consistía en optimizar la gestión de una red de carreteras similar a la que tendría una gran ciudad. 

Para lograrlo, se partía con información sobre una red de carreteras a escala de la ciudad y de su demanda de tráfico. El objetivo es gestionar todos los semáforos de las distintas intersecciones de la red, tratando de organizar eficiente y eficazmente la cantidad del tráfico y su fluidez. 

Para entender mejor el problema, se muestra la siguiente figura, donde se puede ver la estructura de las intersecciones que habría que administrar, así como las posibles señales de paso: 

estructura de las intersecciones

Datos

Los datos de los que se partía para este desafío eran de dos tipos. Por un lado, los que cumplían la función de especificar el tamaño, la forma y las conexiones de la red de carreteras, con información sobre intersecciones y carreteras. Por otro lado, datos que servían para especificar los distintos flujos de tráfico en cada momento.

Además, se contaba con funciones APIs que, utilizando esos datos, facilitaban información más estadísticamente relevante, como por ejemplo, el número de coches por carril en cada intersección, o la velocidad media de dichos carriles.

La ciudad propuesta para el caso contaba con una red de carreteras de 2.048 intersecciones, en la que debían de circular un total de 126.572 vehículos.

En las siguientes imágenes se ve la red de carreteras con la que se ha trabajado:

Métrica de evaluación

El objetivo de este challenge es atender el mayor número de coches (entendiendo atender como permitir llegar a su destino), a la vez de minimizar el índice de retraso, el cual debía rondar un valor máximo estipulado de 1.60. Este índice de retraso se calcula como una media entre los índices de retraso de todos los vehículos atendidos.

Cada índice se calcula a partir de la siguiente información:

  • TTi : Tiempo que lleva de viaje el vehículo i.
  • TTir : Tiempo del resto del viaje (calculado sin parar en intersecciones).
  • TTif : Tiempo completo del viaje (calculado sin parar en intersecciones).

 

retaso de vehículo > índice de retraso

Así, una solución será mejor cuantos más vehículos sea capaz de atender, y entre diferentes soluciones que atiendan el mismo número de vehículos, será mejor aquella con un menor índice de retraso.

Algoritmos empleados

Para resolver el problema planteado, se han desarrollado varios algoritmos que se pueden clasificar en dos tipos: algoritmos deterministas y algoritmos de aprendizaje por refuerzo.

  • Algoritmo determinista 1 (Presión Básica): Evalúa para cada señal, la diferencia entre el número de coches en carriles de entrada, y la media del número de coches en los carriles de salida. Estas diferencias se ponderan dando ligeramente más valor a los carriles de entrada. Se cambia de señal cada cierto tiempo fijo.

 

  • Algoritmo determinista 2 (Presión como Cociente): Evalúa para cada carril, un ratio entre el número de coches en el carril de entrada, y la media del número de coches en los carriles de salida. Además, se incorpora la velocidad media de los carriles de entrada en el denominador. También se modifica el tiempo de cambio de señal, pasando a ser una función lineal dependiente del número total de coches en la intersección.

 

  • Algoritmo determinista 3 (Presión como Cociente):  Se parte del algoritmo anterior y se mejoran sus resultados con pequeñas modificaciones. Se cambia la función lineal del tiempo de cambio de señal por una combinación de raíz y logaritmo. Se añade información sobre la tasa de llegada de los carriles, así como información sobre cada vehículo de la intersección. También se prohíbe el uso de señales ineficientes.

 

  • Algoritmo DQN: Se utiliza la técnica del aprendizaje por refuerzo. Partiendo de algunas características que hasta ahora parecen importantes en los otros algoritmos, se definen algoritmos de aprendizaje por refuerzo probando distintas combinaciones en la definición de cada estado y cada recompensa.

 

Tras estudiar los algoritmos anteriores, así como alguna forma de combinarlos, se establece el algoritmo determinista 3 como el que brinda una mejor solución.

Tras desarrollar distintas soluciones y ajustes para este reto, el equipo de Innova-tsn ha conseguido llegar a satisfacer el número máximo de vehículos posible (126.572), con un retraso medio de 1.601472.

Este challenge ha contado con un total de 1.156 equipos participantes y el equipo de Innova-tsn se encuentra entre los 40 mejores.

Información adicional

Se puede obtener más información sobre la competición en los siguientes enlaces:

Yunqi Academy
Kdd Cup 2021: City Brain Challenge

 

Challenge 2: MULTI-DATASET TIME SERIES ANOMALY DETECTION

El objetivo de este caso era el desarrollo de un algoritmo o inteligencia artificial que permitiese detectar las anomalías en las diferentes series temporales univariantes propuestas.

Para la resolución de este caso, contaban con datos divididos en dos Fases:

  • Fase I. (del 15 marzo 2021 al 7 abril 2021). Un conjunto de 25 series temporales univariantes.
  • Fase II. (del 8 abril 2021 al 31 mayo 2021). Un conjunto de 250 series temporales univariantes (contiendo las 25 de la Fase I).

En cada una de las series temporales, las cuales son series de datos ordenados cronológicamente, se podía registrar como máximo una anomalía, siendo así el objetivo del estudio señalar la irregularidad más destacable. Hay diferentes tipos de anomalías, desde el ruido introducido en la serie, cambio de amplitud o patrones invertidos.

Ejemplos de anomalías

La anomalía en este caso sería que el segundo pico llegaría hasta la altura del primer pico. En azul se muestra los datos originales.

Otro ejemplo de anomalía señalado en rojo

 
Métricas de evaluación

Las métricas que se escogieron para llevar a cabo la clasificación de los algoritmos en el ranking fue el Porcentaje de Acierto sobre las 250 series totales. Para calcular esto, se consideraba acierto la localización de las anomalías dentro de un margen de error de +/- 100 de la situación exacta de la anomalía.

 

ejemplo de anomalía localizada

 

Algoritmos empleados

El algoritmo final que se empleó para obtener los resultados optimizados fue Matrix Profile. Este algoritmo funciona mediante una puntuación de pesos personalizada sobre las subsecuencias (trozos de la serie temporal) consideradas.

Del mismo modo, se trabajó con los siguientes algoritmos:

  • Arimas: modelo estadístico empleado para predecir patrones a través del análisis de estos a través de regresiones y variaciones.
  • AutoML: proceso de aprendizaje automatizado a través de inteligencia artificial.
  • Wavelets: algoritmo empleado para detectar las anomalías generadas a partir del ruido en las series.Isolation forest: algoritmo que descubre anomalías a través del aislamiento de los datos y patrones atípicos

 

Este challenge ha contado con un total de 555 equipos participantes y el equipo de UCM/Innova-tsn ha obtenido la posición 25 con un acierto del 70%. Esto es el Top 5%.

Información adicional

Se puede obtener más información sobre la competición en los siguientes enlaces:

The UCR Matrix Profile Page
Paper:
"Current Time Series Anomaly Detection Benchmarks are Flawed and are Creating the Illusion of Progress"

 
Innova-tsn en la KDD Cup: 6 años de participación

2020 y 2021 han sido dos años caracterizados por el confinamiento, la crisis sanitaria y la desaceleración económica. A pesar de esto, en Innova-tsn continuamos reforzando la perseverancia, el compromiso, la superación y el talento del equipo humano como valores clave fundamentales para nuestro éxito. Como prueba práctica de ello, Innova-tsn ha obtenido, por sexto año consecutivo, muy buenos resultados en la KDD Cup de 2021, posicionándose en el Top 25 mundial en el caso acerca de la detección de anomalías temporales (Multi-dataset Time Series Anomaly Detection) y el Top 40 en el caso sobre la optimización de la red de carreteras (City Brain Challenge).

Para Innova-tsn, la participación anual en la KDD Cup supone mucho más que la búsqueda de la solución al desafío planteado. Esta competición consigue conectar a los mejores científicos de datos del mundo y nos alienta a fomentar una motivación especial: la posibilidad de trabajar con profesionales que comparten la misma ilusión, talento, creatividad y que dedican su tiempo voluntariamente a un proyecto común.

En definitiva, nuestra finalidad es la satisfacción personal de cada uno de nuestros analíticos participantes, a quienes aprovechamos desde aquí para felicitar una vez más por su enorme esfuerzo y dedicación estos meses y, por supuesto, el refuerzo de sus ganas de continuar aprendiendo, creciendo y mejorando profesionalmente, tanto en la modelización como en el análisis de datos.