Gestión de Tráfico – Ejemplo de Análisis Estadístico vs Minería de Datos (Reglas de Asociación).

1.    Resumen:

El diseño de un Sistema de Control y Regulación del Tráfico está pensado para incrementar la eficiencia y capacidad del sistema de transporte y mejorar su seguridad. El sistema de control de tráfico consiste en esencia en unos dispositivos que permitan detectar las situaciones anómalas, un centro de control en el que se reciben las informaciones de los detectores y se adoptan las decisiones pertinentes, y un medio para comunicar estas decisiones a los usuarios finales. Los sistemas de captación son los encargados de la captación de datos de tráfico, especialmente velocidad, intensidad y densidad. Estos datos son mandados al centro de control donde son tratados mediante algoritmos y se establece un mapa continuo del estado del tráfico, se genera una base de datos y se simula para analizar situaciones concretas.

En definitiva, se desarrolla un sistema que, en función a diversas variables, detecte el nivel de flujo del tráfico (fluido, denso, condensado), y las anomalías (detección automática de incidentes) que se produzcan, pero que, además, sea capaz de predecir cómo se va a comportar el sistema en el futuro inmediato en función del estado actual, o en función de un día/hora determinados.

Así pues, los principales problemas residen en definir qué es tráfico denso, fluido, o condensado, en función de que parámetros de definen dichos valores, qué umbrales de dichos valores el sistema determina un estado u otro, y cuándo dichos valores muestran a una anormalidad que indique la posible presencia de un incidente.

En definitiva, es un problema de ponderar unos indicadores para clasificar los estados de los distintos tramos, y una vez definida esta clasificación, poder predecir el estado a futuro en base a las mismas reglas que en el estado actual.

 

2.    Comparativa de métodos

2.1. Análisis Estadístico.

El análisis estadístico está basado en al obtención de unos componentes principales que identifiquen el estado de las carreteras, normalmente basados en las medias de velocidad e intensidad, y la comparativa de estos valores con unos umbrales determinados por tramo. La definición de estos umbrales  puede ser «a priori», o basado en históricos, es decir, a priori, en base a la experiencia de los controladores, o basado en las medias históricas que se han obtenido del análisis del archivo histórico de una carretera.

2.1.1. Flujo del tráfico.

La valoración del tráfico en un punto se realiza a partir de tres magnitudes básicas:

INTENSIDAD, OCUPACIÓN y VELOCIDAD. La fórmula que liga a las tres variables es la siguiente: (siendo «Ve» la velocidad media espacial)

I=DVe

Esta relación liga por tanto las tres magnitudes fundamentales y permite calcular una de ellas (generalmente la densidad) en función de las otras dos.

 

Cuando la densidad sea nula, también lo será la intensidad; y cuando la densidad alcance su valor máximo, por anularse la velocidad media, se anulará también la intensidad. El hecho de que exista un valor máximo de la intensidad que puede circular por una carretera es de la mayor importancia. Este valor máximo se conoce como capacidad de la carretera, y la densidad para la que se obtiene se llama densidad crítica. Cuando la densidad es menor que la crítica, el tráfico se mantiene relativamente fluido y estable, en el sentido que si se produce alguna pequeña perturbación que aumente momentáneamente la densidad de tráfico, tiende a disiparse y volver a la situación anterior. Por el contrario, cuando la densidad es superior a la crítica, las perturbaciones tienden a producir un empeoramiento de la situación que puede llegar a la detención total del tráfico

El diagrama que representa la intensidad en función de la densidad se conoce como diagrama fundamental del tráfico, y en él puede obtenerse para cualquier punto la intensidad (ordenada), densidad (abscisa) y velocidad media (pendiente de la recta que une el origen con el punto en cuestión).

Se estima que la densidad crítica suele ser del orden del 30% al 40% de la densidad máxima. En definitiva, si queremos aumentar la capacidad de una vía actuando sobre la velocidad, debemos obligar a circular a una velocidad determinada, por debajo del límite establecido. Esta será aquella que nos sitúe en la parte de la gráfica próxima a la capacidad en condiciones de circulación estable. A menor velocidad, mayor densidad e intensidad. Lo que se consigue, es evitar que los vehículos se paren

Conociendo la capacidad de la vía, su geometría y la experiencia de un experto, se pueden definir ciertos umbrales de los valores intensidad, ocupación y velocidad para los cuales se determine si el tráfico es fluido (por ejemplo, velocidad media > 70), denso (velocidad media < 69), o condensado (velocidad media < 50).

Lo usual es que sobre la variable densidad se determinen los estados del flujo (curva Intensidad/Densidad):

 

• Detección de anomalías.

La detección automática de incidentes intenta identificar los incidentes analizando los datos proporcionados por los sensores. Diversos algoritmos de detección se han desarrollado. Todos constan de comparación de datos tales como volumen, ocupaciones o velocidades con valores umbral pensados para indicar la presencia de congestión resultado del incidente. Algunos algoritmos, además, comparan datos de estaciones adyacentes.

2.1.2. Estado del arte de los principales algoritmos estadísticos para la detección de incidencias en el tráfico.

• Algoritmo California

Desarrollado a finales de los años 60 en Los Ángeles, los algoritmos California comparan las condiciones del tráfico entre dos estaciones detectores adyacentes. El análisis del algoritmo se basa en el seguimiento de las siguientes variables de ocupación:

• Diferencia absoluta de ocupación entre los detectores aguas arriba y aguas abajo.

• Diferencia entre la ocupación medida en los detectores aguas arriba y aguas abajo relativa a la ocupación aguas arriba.

• Diferencia entre la ocupación medida en los detectores aguas arriba y aguas abajo relativa a la ocupación aguas abajo.

• Análisis de ondas

Recientemente desarrollado en la Universidad de Berkeley, este algoritmo analiza las diferencias entre las ocupaciones acumuladas aguas arriba y aguas abajo buscando perturbaciones significativas. Bajo unas condiciones normales de tráfico la diferencia acumulada siempre está alrededor de cero. Diferencias sustanciales sugieren la presencia de un incidente.

• Algoritmo APID (All Puryose Incident Detection)

El algoritmo APID fue desarrollado en el sistema avanzado de gestión del tráfico

COMPASS de Toronto. Incorpora y expande la mayoría de los elementos del algoritmo

California en una sola estructura. El sistema APID incluye un algoritmo general de detección para usar bajo condiciones de tráfico extremas, para condiciones de tráfico bajo, medio, un test para comparación de ondas y un test de persistencia. Algunos tests demuestran que este algoritmo trabaja mejor bajo condiciones de gran volumen de tráfico, mientras que para bajos volúmenes sus resultados son un poco pobres.

• Algoritmo Pattern Recognition(PATREG)

El algoritmo PATREG fue desarrollado en el Transport and Road Reserch Lab (TRRL) como parte de su sistema de detección automática de incidentes. Este algoritmo se usa junto al algoritmo HIOCC para la detección de incidentes en las vías rápidas del Reino

Unido. El algoritmo estima la velocidad de los vehículos mediante la medición de tiempos de recorrido entre detectores. El algoritmo compara estas velocidades con unos umbrales preestablecidos, dando lugar a una alarma cuando los valores caen respecto a estos umbrales. Algunas evaluaciones de este algoritmo muestran que tiene problemas cuando el tráfico excede de los 1500 vph.

• Algoritmo Mónica

Desarrollado en 1991 dentro del programa europeo DRIVE 1, Mónica fue testada durante los dos primeros años del proyecto HERMES. Basado en la medición de los valores y la variación de los avances entre vehículos (dT) y de la diferencia de velocidad entre sucesivos vehículos (dV), se producen señales de alarma cuando estos parámetros experimentan grandes perturbaciones y exceden unos umbrales preestablecidos. El algoritmo Mónica es independiente del numero de carriles y del comportamiento del tráfico en otras secciones, pero requiere distancias cortas entre detectores (500 — 600 m).

• Desviación estándar normal (SND Standar Normal Deviation)

El algoritmo SND fue desarrollado en el Texas Transportation Institute (III) a principio de los 70 para ser usado en el centro de control instalado en Houston Gulf Freeway (1-

45). Está basado en la premisa de que un cambio brusco en la medida de una variable del tráfico sugiere que un incidente ha ocurrido. El algoritmo compara continuamente las medias de ocupación, calculadas en un minuto, con valores históricos de la media y la desviación estándar normal. Dependiendo de la estrategia a seguir, la media y la desviación estándar se calculan sobre tres minutos de tiempo o cinco minutos y una o dos iteraciones sucesivas del SND han de ser críticas para dar la alarma.

• Algoritmo series de tiempo ARIMA

El modelo sostiene que las diferencias en variables medidas en el tiempo presente (t) y las mismas variables justo en un instante de tiempo anterior (t- 1) pueden ser predichas haciendo la media de los errores entre la predicción y la observación desde los tres períodos de tiempo anteriores. Este modelo se usa para desarrollar previsiones a corto plazo. Los datos que se desvíen de estas previsiones desencadenarán una alarma.

• Algoritmo de alta ocupación. HIOCC (High Occupancy Algorithm)

Desarrollado en Inglaterra, el algoritmo HIOCC inspecciona los datos referentes a la ocupación de un detector individual en busca de la presencia de vehículos estacionarios o circulando muy lentamente. Una computadora escanea los datos referentes a la ocupación de los detectores cada décima de segundo, y muchos valores consecutivos de la ocupación instantánea son examinados para ver si exceden los umbrales marcados por el algoritmo.

• Algoritmo exponencial de uniformidad

Estos algoritmos sopesan las observaciones de ocupación pasadas y presentes para pronosticar condiciones futuras de tráfico. La mayoría de este tipo de algoritmos deben ser expresados matemáticamente como una función exponencial simple o doble, con una constante de uniformidad que tiene en cuenta observaciones pasadas. En algunos modelos los incidentes son detectados usando una señal de rastreo, definida como la suma de todos los errores anteriores (diferencias entre el parámetro pronosticado y el actual). Bajo condiciones normales, la señal de rastreo debe oscilar alrededor de cero.

Cuando ocurre un incidente el parámetro previsto y el actual deben diferir de forma que la señal de rastreo se desviará de cero.

2.1.3.  Ventajas del Análisis Estadístico.

• No requiere implementar algoritmos complejos multivariable y de regresión o series temporales.

• Implantación de un sistema clásico de programación para determinar flujos de tráfico y posibles incidencias.

2.1.4.  Desventajas del Análisis Estadístico.

• La principal desventaja del Análisis Estadístico reside en la definición de los umbrales sobre los que se «dispararán» las alertas, bien de estados, bien de incidencias. Por un lado, los límites serán diferentes para cada uno de los tramos, dado que las características del tráfico varían en gran medida según la configuración de la vía (número de carriles, anchura de carriles, existencia de arcén, pendiente, ….).
• Estos umbrales no tienen en consideración otras variables que afectan al tráfico como lo son el estado meteorológico, los cambios de sentido en situaciones de obras u accidentes de ciertos carriles, y lo que es más importante, los hábitos de desplazamientos de los usuarios (fines de semanas, vacaciones, horas putas, puntos negros, etc…).
• La puesta en marcha de un sistema complejo de regulación basado en este sistema de umbrales es costosa, en base a un  ajuste de los umbrales por cada tramo en función de las respuestas del sistema.
• No son sistemas evolutivos, ya que nuevas configuraciones del entorno no afecta a los valores de umbrales, a no ser que se reajusten manualmente. En general, se considera que la demanda y número de usuarios se mantiene estable en el tiempo de las configuraciones de los umbrales, y lo que se espera es una mejor distribución de los volúmenes de las diferentes vías, lo cuál, no es siempre cierto.

2.2. Minería de Datos. Reglas de Asociación.

2.2.1.  Reglas de Asociación. Introducción.

Las reglas de asociación obtienen una serie de parejas «condicionante-conclusión» en función a los datos pasados de forma automática, y además, según el sistema evoluciona, se pueden incorporar más reglas a la definición de un tramo como «fluido», «denso» o «congestionado», o modificar las existentes en función a las nuevas acciones realizadas sobre el sistema.

Tanto la técnica de Clasificación como la de Predicción buscan la definición de los valores de un determinado atributo, conocido en un conjunto de datos de prueba, en base a los valores de otros atributos. En nuestro caso, el atributo a obtener es, o bien, el estado del tráfico en un tramo, o bien, la posibilidad de existencia de una incidencia en dicho tramo. Dicho atributo se denomina etiqueta o label. Sus valores, han de ser conocidos en la muestra que se utiliza para extraer el modelo. Un tipo habitual de estos modelos son los modelos basados en reglas, por ejemplo:

Si MODELO = SP02 Y GASTO_MENSUAL > 105

ENTONCES ABANDONO = si

Si EDAD < 18 Y GASTO_MENSAJES > 35

ENTONCES ABANDONO = si

Si OFERTA = TT12 Y RESIDENCIA = MADRID Y CASADO = si > 105

ENTONCES ABANDONO = no

En relación al conjunto de datos usado para extraer el modelo se suele dividir en dos subconjuntos, uno de ellos denominado conjunto de entrenamiento (training data set) es el usado para generar el modelo, mientras que el otro subconjunto, conjunto de prueba (testing data set) se usa para contrastar la predicción del modelo con datos no usados durante su entrenamiento. Es evidente, por tanto, la necesidad de históricos de los estados del tráfico en el pasado, (denso, fluido, condensado), y os valores de los atributos (densidad, intensidad, velocidad, fecha, condiciones meteorológicas, cortes, obras…) de cada tramo en relación a dicho estado.

Para cada una de las reglas obtenidas, se proporciona un valor de probabilidad de que dicha regla sea cierta sobre el conjunto de valores.

No existe diferencia entre la clasificación o la predicción, ya que las reglas que se ejecutan para ambos casos son las mismas.

Un ejemplo sencillo de la extracción de conocimiento con reglas de asociación se muestra en la siguiente figura:

En el caso de que llegase un nuevo titular desconocido, el sistema podría clasificar en función de las reglas al desconocido como fijo o no en función de sus datos. Posteriormente, si dicha clasificación fuese incorrecta, y se corrigiese, se lanzaría de nuevo el algoritmo de árboles de decisión, pudiéndose generar una nueva regla, o modificándose las anteriores. Así, otro ejemplo de un árbol de decisión generado de forma automática se muestra en la siguiente figura:

 

 

Una de las principales ventajas de los algoritmos de reglas de asociación (utilizamos en este caso el algoritmo C45), es que la propia «poda» de las ramas de los árboles definen qué atributos del total de atributos en el sistema (velocidad, temperatura, día festivo, estado de otras carreteras, etc…), son las que tienen correlación con los valores objetivos, de forma, que podemos extraernos de la obtención de los atributos que se correlacionan con una solución concreta.

2.2.2.  Reglas de Asociación aplicadas a la Gestión de Tráfico.

En función de los históricos que tenemos de las condiciones del tráfico en el pasado (fluido, denso, congestión), el registro de incidencias (accidentes, obras), y los valores de las distintas variables en el momento de producirse los cambios de estado o la generación de incidencias, podemos generar de forma automática un modelo que represente al sistema multivariable en distintos espacios temporales, que clasifique la información que devuelven los distintos sensores en el momento actual, y que prediga que ocurrirá en el futuro partiendo de cualquier momento temporal determinado.

Así, tenemos una serie de indicadores por tramo y fecha (tráfico generado durante varios meses):

 

Referencia 1	Pkfinal	IM	Intensidad	Fecha/hora
AP-8	30	20	2	10:05
N-IA	2	15	23	10:05
AP-8	38	10	10	10:05
N-IA	2	23	38	10:05

 

Y una relación de los estados en los que han estado dichos tramos en esas fechas/horas:

 

Tiempos Fecha/hora (con formato extendido)	276	250	248	249
10:25	TR001	TRAKING	TRAKING	TRAKING
11:05	TR001	TR001	TRAKING	TRAKING
11:07	TR001	TR001	TR001	TRAKING
11:20	TR002	TR001	TR001	TRAKING
15:00	TR002	TR001	TR001	TR001
15:07	TR002	TR002	TR002	TR001
16:00	TR002	TR002	TR002	TR002
17:00	TRAKING	TRAKING	TRAKING	TRAKING
10:15	TRAKING	TRAKING	TRAKING	TRAKING
10:25	TR001	TRAKING	TRAKING	TRAKING
11:05	TR001	TR001	TRAKING	TRAKING
11:07	TR001	TR001	TR001	TRAKING
11:20	TR002	TR001	TR001	TRAKING
15:00	TR002	TR001	TR001	TR001
15:07	TR002	TR002	TR002	TR001
16:00	TR002	TR002	TR002	TR002

Unimos la información de dichas tablas, y obtenemos, por un lado, reglas que nos definen los atributos que determinan el estado de los tramos, y por otro lado, reglas que nos determinan las relaciones de las tablas en un espacio temporal determinado (si una referencia tiene un accidente, otra lejana puede que comience a saturarse). De esta forma, obtenemos reglas del siguiente tipo:

– Reglas de estados (ejemplo para una referencia):

if IMD > 29.500 then Sin Incidencia  (14 / 0 / 6 / 0)

if IMD ≤ 20 then Tráfico Lento  (0 / 2 / 0 / 0)
if IMD ≤ 27 and fecha = 5/21/08 then Sin Incidencia  (1 / 0 / 0 / 0)
if fecha = 1/23/10 then Tráfico Denso  (0 / 0 / 1 / 0)
if fecha = 6/26/08 then Sin Incidencia  (1 / 0 / 0 / 0)
else Tráfico Denso  (0 / 0 / 0 / 0)

– Reglas de relaciones entre referencias («T» es la referencia temporal):

Si RF1 = TR001 y «T» = 1 entonces RF2 = AC000

Si RF1 = TR001 y «T» = 3 entonces RF2 = TR001

Si RF2 = TR002 y «T» = 1 entonces RF4 = TR001

Si RF2 = TR002 y «T» = 2 entonces RF4 = TR002

Estas reglas se ubican en un «contenedor» de reglas, y se lanza un motor de ejecución de las reglas  que optimiza la ejecución de las mismas, la transitividad, asociatividad y concurrencia, en base al algoritmo Rete (Charles Forgy).

Según se van modificando los comportamientos, acciones, comunicaciones y valores de cualquiera de los atributos del sistema, o de todos, las reglas se van generando, modificando, añadiendo o borrando en función a la generación de los árboles de decisión. Si por ejemplo, en un momento determinado, se incluye una nueva variable al sistema, como pudiera ser el estado del hielo en las carreteras, este valor, una vez que comience a iterar con el sistema, incorporará nuevas reglas que afectarán a la densidad del tráfico o a la posibilidad de accidentes en invierno.

2.2.3.  Ventajas de las reglas de Asociación.

• Sistema multivariable y basado en la repetición estadística de eventos en históricos, de generación automática.
• Varía con el entorno, con las modificaciones tanto de atributos como de valores de forma automática.
• Aprende con la evolución del sistema, sin necesidad de reprogramación .
• Modificación automática de los valores umbrales en función a las respuestas del sistema, y a su gestión automática.
• .Es capaz de explicar (mostrar las reglas que se han ejecutado) las razones de una acción. (Es fluido por que han ejecutado «n» reglas….).

2.2.4.  Desventajas de las reglas de Asociación.

• Necesidad de Históricos para un buen funcionamiento a futuro.

2.2.5.  Algoritmos Utilizados.

• Repeated Incremental Pruning to Produce Error Reduction (RIPPER, Cohen 1995).
• Tobias Scheffer: Finding Association Rules That Trade Support Optimally against Confidence. In: 5th European Conference on Principles of Data Mining and Knowledge Discovery, 424-435, 2001.