Técnicas de predicción de destinos geográficos futuros en desplazamientos de personas
Abstract
El desarrollo de este trabajo de investigación se orientará hacia un sector cada vez más amplio de usuarios que dispongan y utilicen frecuentemente dispositivos móviles con capacidades de gestión de base de datos y localización por GPS. Cuanta más capacidad tenga el dispositivo más posibles aplicaciones con conocimiento del contexto futuro podrán implantarse. Aunque las propuestas de esta tesis se pueden aplicar a sistemas de localización diferentes, en la implementación nos centramos en la predicción de recorridos urbanos e inter-urbanos rastreados por receptores GPS. Éstos no permiten el seguimiento en espacios sin visión directa sobre los satélites, por lo que quedan fuera de este trabajo la predicción de destinos en interiores. Nuestra propuesta, al usar como soporte mapas personales creados por el propio usuario al desplazarse diariamente, no necesitará de ningún GIS por lo que será utilizable en lugares donde no exista cartografía detallada, como por ejemplo en mares y océanos. El público objetivo de las predicciones de destino serán personas con todo tipo de hábitos de desplazamientos y que utilicen cualquier medio de transporte en el que puedan utilizarse dispositivos electrónicos (quedan por tanto fuera de nuestra hipótesis los aviones). Capítulo 2: Metodología off-line. Se propondrá una metodología para la recuperación de la información, su preprocesado y los algoritmos de extracción de conocimiento a partir de trazas de movimiento aportadas por diferentes voluntarios. Los objetivos de este capítulo son por una parte estudiar los métodos existentes para extraer los destinos frecuentes y las rutas seguidas, aportar nuevos algoritmos que mejoren los resultados, proponer una metodología con fases bien diferenciadas y estudiar los aspectos prácticos para poder desarrollar una metodología on-line realista. Capítulo 3: Modelo de Markov Oculto sobre "Mapa Soporte" . Basándonos en las rutas que genera un usuario, creamos un mapa personal que nos permite utilizarlo aplicando un Modelo Oculto de Markov (HMM). El mapa personal disminuye en gran medida la cantidad de información utilizada por lo que lo estudiamos para aplicarlo en dispositivos móviles. Capítulo 4: Similitud de recorridos. Las medidas de similitud existentes entre recorridos no se adaptan a nuestras necesidades por lo que propondremos nuevas métricas que permiten comparar tanto recorridos finalizados entre sí como recorridos no finalizados con aquellos que sí lo han hecho, lo que nos permite predecir rutas y destinos. Capítulo 5: Resultados. Revisaremos los resultados obtenidos aplicando la metodología off-line y evaluaremos los modelos de predicción utilizando rutas mediante similitudes y "Mapas soporte" a través de HMM, comparando las dos alternativas. Capítulo 6: Predicción on-line. Una vez comprobados los resultados de los diferentes modelos de predicción, trataremos su implementación en un dispositivo móvil para permitir la predicción en tiempo real. Además se propondrán técnicas para reducir el consumo innecesario de baterías, mejorando la disponibilidad de los servicios de predicción. Capítulo 7: Aplicaciones. Mostraremos las aplicaciones definidas para nuestro sistema de predicción on-line, de modo que se destaque la utilidad del sistema de predicción on-line propuesto. Capítulo 8: Conclusiones y trabajo futuro. En este capítulo se presentan las conclusiones de esta tesis doctoral y las líneas de investigación abiertas sobre las que se trabajaremos en los próximos años. Apéndice A: Sistema GPS Describiremos de forma breve en este apéndice el funcionamiento del Global Positioning System y la estructura de las sentencias NMEA. Apéndice B: Currículum. En este apéndice incluimos las publicaciones y los proyectos en los que hemos participado durante la elaboración de este trabajo. Bibliografía: Tras los dos apéndices, incluimos la bibliografía utilizada en la elaboración del documento.
Full text
UNIVERSIDAD DE SEVILLA DEPARTAMENTO DE LENGUAJES Y SISTEMAS INFORMÁTICOS Técnicas de predicción de destinos geográficos futuros en desplazamientos de personas Memoria de Tesis Doctoral presentada por D. Juan Antonio Álvarez García para la obtencion del grado de Doctor en Informática, dirigida por los doctores: D. Juan Antonio Ortega Ramirez yD. Luis González Abril. Sevilla, diciembre de 2009.
A mi mujer que ha sabido animarme en cada momento y a mi hija que ha traído más alegría aún a nuestro hogar.
Agradecimientos Quisiera expresar mi más sincero agradecimiento a mis directores de Tesis, Dr. D. Juan Antonio Ortega Ramírez y Dr. D. Luis González Abril, por todo el esfuerzo y tiempo dedicado a la elaboración de este trabajo. Del mismo modo, a Francisco Velasco y Francisco Javier Cuberos por su charla instructiva y amena. Destacar también el apoyo de mis compañeros y amigos del Departamento de Lenguajes y Sistemas Informáticos, especialmente de Fernando Enríquez, Toñi Reina, María Teresa Gómez, Alejandro Fernández, José Antonio Troyano, Miguel Ángel Álvarez y Luis Miguel Soria. Asimismo, mi agradecimiento a los compañeros de la UPC Dr. Cecilio Angulo, Dr. Andreu Català, Dr. Diego Esteban Pardo y a Carlos Pérez que me acogieron como a un amigo en mis fructíferas estancias en Vilanova. Finalmente, un agradecimiento muy especial a mis padres y a mi hermano por su cariño, ánimos y ayuda. A todos, muchas gracias.
ÍNDICE GENERAL Índice Índice General .................................. i Índice de Tablas ................................. ix Índice de Figuras ................................. xi 1 Introducción 1.1. Propuesta ................................. 3 1.2. Escenario motivador . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Contexto.................................. 6 1.4. Justificación................................ 10 1.5. Objetivos ................................. 12 1.6. Hipótesis de partida . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . 13 Página i
ÍNDICE GENERAL 2 Metodología off-line 2.1. Estadodelarte .............................. 17 2.1.1. Recuperación de la información de localización . . . . . . . . . 19 2.1.2. Segmentado en recorridos . . . . . . . . . . . . . . . . . . . . 21 2.1.3. Filtrado de recorridos . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.4. Extracción de destinos . . . . . . . . . . . . . . . . . . . . . . 22 2.1.5. Generación de rutas . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. Nuestra propuesta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.1. Esquema.............................. 24 2.2.2. Recuperación de puntos GPS . . . . . . . . . . . . . . . . . . 26 2.2.3. Filtrado y normalizado de puntos . . . . . . . . . . . . . . . . 29 2.2.3.1. Problemas conocidos en la captura de datos . . . . . 29 2.2.3.2. Filtrado de puntos GPS . . . . . . . . . . . . . . . . 31 2.2.4. Segmentado en recorridos por tiempo . . . . . . . . . . . . . . 33 2.2.5. Extracción de destinos . . . . . . . . . . . . . . . . . . . . . . 34 2.2.5.1. Radio de destinos . . . . . . . . . . . . . . . . . . . . 35 2.2.5.2. Mínimo número de puntos por cluster . . . . . . . . 36 2.2.5.3. Cluster jerárquico modificado . . . . . . . . . . . . . 36 2.2.6. Segmentado por cercanía a destinos . . . . . . . . . . . . . . . 38 2.2.7. Filtrado de recorridos . . . . . . . . . . . . . . . . . . . . . . . 40 Página ii
ÍNDICE GENERAL 2.2.8. Validación............................. 41 2.2.9. Obtención de mapas personales . . . . . . . . . . . . . . . . . 41 2.2.10. Obtención de rutas . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2.11. Técnicas de predicción . . . . . . . . . . . . . . . . . . . . . . 44 2.2.12.Evaluación............................. 44 2.3. Resumen.................................. 45 3 Modelo de Markov Oculto sobre “Mapa Soporte” 3.1. Estadodelarte .............................. 47 3.2. ModelosdeMarkov............................ 56 3.2.1. Modelos de Markov visibles . . . . . . . . . . . . . . . . . . . 56 3.2.2. Modelos de Markov ocultos . . . . . . . . . . . . . . . . . . . 57 3.2.3. Problemas a resolver usando HMM . . . . . . . . . . . . . . . 59 3.3. Nuestra propuesta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.3.1. Generación del mapa soporte . . . . . . . . . . . . . . . . . . 61 3.3.1.1. Selección de puntos de cruce . . . . . . . . . . . . . . 61 3.3.1.2. Generación de puntos significativos . . . . . . . . . . 63 3.3.1.3. Puntos soporte . . . . . . . . . . . . . . . . . . . . . 64 3.3.2. Generación del modelo . . . . . . . . . . . . . . . . . . . . . . 68 3.3.3. Predicción de destinos . . . . . . . . . . . . . . . . . . . . . . 71 Página iii
ÍNDICE DE TABLAS 5.6. Resultados de generación de rutas por cluster jerárquico de recorridos con regiones bola de radio 40 metros y agrupando con similitud superioral70%. .............................115 5.7. Resultados de la obtención de puntos soporte. . . . . . . . . . . . . . 116 5.8. Resultados del experimento. Mindica el número de capas en la validación cruzada. Los valores denotan el porcentaje de predicciones correctas. .................................117 5.9. Resultados del experimento con similitudes. Mindica el número de capas en la validación cruzada. Los valores denotan el porcentaje de predicciones correctas. . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.10. Comparación de resultados entre HMM+Mapa soporte y Similitud entrerecorridos...............................122 5.11. Índice de bondad de las predicciones. . . . . . . . . . . . . . . . . . . 124 7.1. Diario automático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 A.1. Extracto de sentencias NMEA. . . . . . . . . . . . . . . . . . . . . . 170 Página x
ÍNDICE DE FIGURAS 2.1. Metodología propuesta . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2. PDA y receptores GPS utilizados en la fase de recuperación de recorridos. ................................... 28 2.3. Ejemplo de recorridos idénticos con trazas diferentes. . . . . . . . . . 31 2.4. Extracto de los puntos finales de los recorridos realizados por el usuario1. ................................... 38 2.5. Ejemplo de segmentado por cercanía a destinos . . . . . . . . . . . . 40 2.6. Superposición de tres recorridos desplazados manualmente contenidos enelmismocluster. ........................... 43 2.7. Representación del índice IP definido para cuantificar la bondad de nuestras predicciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1. Ejemplo de modelo de Markov de segundo orden. . . . . . . . . . . . 49 3.2. Red Bayesiana dinámica utilizada por Patterson (derecha) y gráfico de predicción de correcta localización (izquierda). . . . . . . . . . . . 51 3.3. Modelo de Markov Jerárquico utilizado por Liao (derecha). Comparación del modelo propuesto por Patterson y el propuesto por Liao (izquierda). ................................ 52 Página xi
ÍNDICE DE FIGURAS 3.4. Secuencia de ejemplo del modelo “Predestination”. . . . . . . . . . . . 54 3.5. Modelo de Markov de 4ºorden en el que los estados son los segmentos decarretera................................. 55 3.6. Ejemplo de mapa soporte objetivo. . . . . . . . . . . . . . . . . . . . 62 3.7. Camino con cuatro desviaciones. . . . . . . . . . . . . . . . . . . . . . 63 3.8. Tipos de cruces entre dos recorridos y sus puntos previos y posteriores. 64 3.9. Operación de agrupamiento de puntos previos y posteriores de un cruce cuando están muy próximos. . . . . . . . . . . . . . . . . . . . . 65 3.10. Puntos soporte generados en una situación real . . . . . . . . . . . . 67 3.11. Secuencia de generación de puntos soporte. . . . . . . . . . . . . . . 68 3.12. Ejemplo gráfico de la drástica reducción en el número de puntos. . . 69 4.1. Utilidad de tener una similitud entre recorridos. . . . . . . . . . . . . 76 4.2. Similitud entre rutas de Internet propuesta por Hu. . . . . . . . . . . 81 4.3. Ejemplo de la similitud punto-segmento. . . . . . . . . . . . . . . . . 82 4.4. Ejemplo de dos recorridos GPS. . . . . . . . . . . . . . . . . . . . . . 89 4.5. Ejemplo de dos caminos como un polígono. . . . . . . . . . . . . . . . 91 4.6. Distancia entre dos caminos como un área. . . . . . . . . . . . . . . . 92 4.7. Ejemplo de dos recorridos comparados con las diferentes disimilitudes estudiadas: a) Hausdorff-GPS, b) Froehlich, c) áreas y d) Jaccard-GPS. 94 4.8. Ejemplo de ruta más cercana deslizante. . . . . . . . . . . . . . . . . 96 4.9. Ejemplo de funcionamiento de las similitudes Jaccard-GPS y la deslizante.................................... 97 Página xii
ÍNDICE DE FIGURAS 5.1. Visualización de recorridos obtenidos en España y detalle de los recuperados en Sevilla. . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.2. Puntos candidatos para segmentar en recorridos en función del tiempo entrepuntos. ...............................106 5.3. Puntos de segmentado generados en un edificio techado. . . . . . . . 107 5.4. Número de destinos generados en función del umbral elegido. . . . . 107 5.5. Representación del cluster jerárquico modificado aplicado a los puntos finales del usuario 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.6. Ejemplo de falso recorrido generado al recuperar información desde unlugartechado..............................110 5.7. Cálculo de distancia umbral para la equivalencia de regiones bola. . . 113 5.8. Número de rutas generadas al realizar el cluster jerárquico de recorridos. ...................................114 5.9. Dendrograma de rutas para el usuario 1 (izquierda) con una reducción del 73.58% en y para el 2 (derecha) con una reducción del 29.17%. . 114 5.10. Resultados de predicciones correctas utilizando el mapa soporte y HMM. ...................................118 5.11. Resultados de predicciones correctas utilizando la similitud Jaccard- GPS.....................................120 5.12. Ejemplo de recorrido con poca similitud con los demás. . . . . . . . . 121 5.13. Comparación de los resultados de predicción obtenidos para cada usuario. ..................................123 6.1. Terminal HTC P3300 utilizado para el prototipo de predicción on-line.131 6.2. Esquema seguido en el prototipo desarrollado en el terminal móvil para realizar una predicción on-line. ..................134 Página xiii
ÍNDICE DE FIGURAS 6.3. Terminal Samsung Omnia utilizado para la mejora de tiempo de baterías. ...................................139 6.4. Comparación de la duración de baterías para un Samsung Omnia según el tipo de sensor activado. . . . . . . . . . . . . . . . . . . . . . 140 6.5. Comparación de la precisión de seguimiento utilizando GPS y puntos de acceso WiFi geo-localizados. . . . . . . . . . . . . . . . . . . . . . 141 6.6. Puntos de acceso WiFi geo-localizados en las bases de datos de Wigle.net con cobertura global (izquierda) y PlaceEngine con cobertura para Japón (derecha). . . . . . . . . . . . . . . . . . . . . . . . . . . 142 6.7. Estudio de transiciones de interiores a exteriores basada en la acelerometría...................................144 7.1. Aplicación Web para generar recorridos ficticios. . . . . . . . . . . . . 150 7.2. Resultado de preguntas sobre la búsqueda de indicaciones para llegar a un lugar desconocido. . . . . . . . . . . . . . . . . . . . . . . . . . 151 7.3. Aplicación de consulta interactiva de estaciones de Sevici. . . . . . . . 155 A.1. Distribución de los 24 satélites activos de NAVSTAR. . . . . . . . . . 168 A.2. Proceso de recuperación del intervalo de tiempo entre el envío de la señal desde un satélite GPS y la recepción en tierra. . . . . . . . . . . 169 Página xiv
CAPÍTULO 1 INTRODUCCIÓN Entre 1990 y 1991, el ejército de los Estados Unidos utilizó el Sistema de Posicionamiento Global (GPS) [Get93] en la Guerra del Golfo. Su desarrollo, inspirado en la localización del satélite Sputnik en el espacio mediante el efecto Doppler, comenzó formalmente en 1973 y no se completa hasta 1995. Este sistema abrió las puertas al desarrollo de aplicaciones de localización en exteriores. Su uso inicial por parte del Departamento de Defensa estadounidense y el error aleatorio que introducían para el uso civil (técnica llamada “Disponibilidad Selectiva” y presente desde 1990), limitó su utilidad en investigación no militar. La eliminación de la “Disponibilidad selectiva” el 2 de mayo del año 2000 (la precisión del sistema pasó de 100 a 20 metros), la bajada de precios en los receptores GPS, la miniaturización de éstos y la orden de la Comisión de Comunicaciones Federal estadounidense E911(1), relanzaron el interés por las aplicaciones basadas en la localización (“Location Based Applications”) en exteriores. (1)Orden aplicada desde 2001 que obliga a los proveedores inalámbricos a localizar dentro de decenas de metros a usuarios que realizan llamadas de emergencia. Más tarde Europa propuso la recomendación europea E112 (aplicada desde 2003) con el mismo propósito. Página 1
Capítulo 1: Introducción Durante el siglo XXI, la progresión del mercado de los receptores GPS ha sido tremenda. Según recientes estudios(2) la población mundial de suscriptores de servicios de localización crecerá desde los 12 millones de 2006 a los 315 millones en 2011. Los factores para que el mercado de chips GPS se haya disparado se fundamenta en gran medida en los sistemas de guiado o navegación para vehículos(3) que ha provocado una estrecha alianza entre productores de navegadores GPS y empresas de cartografía, tanto es así que muchas de las segundas han sido adquiridas por las primeras(4). Uno de los sistemas que más acogida ha tenido relacionado con los sistemas de localización ha sido el de gestión de flotas de empresas de transporte. Explotando la combinación de receptores GPS y antenas GSM es posible conocer en todo momento los movimientos de toda una flota de cualquier tipo de vehículo. Esta idea se ha extendido al seguimiento de niños(5), de ancianos(6), presos en régimen abierto como maltratadores(7) o incluso de coches robados mediante proyectiles(8) GPS que evitan peligrosas persecuciones. Sin embargo la integración de los chips GPS en los terminales móviles (9 de cada 10 móviles contendrán chips GPS en el 2014 comparado con los 1 de cada 3 del 2008(9)) ha hecho que las aplicaciones con conocimiento de la localización se multipliquen. De ese modo encontramos aplicaciones de publicidad por localización(10) o localización de lugares de interés mediante realidad aumentada(11). (2)http://www.abiresearch.com/abiprdisplay.jsp?pressid=766. (3)http://reviews.cnet.com/best-gps/ (4)http://online.wsj.com/article/SB119677803171513059.html?mod=googlenews_wsj (5)http://www.laipac.com (6)http://www.keruve.com (7)http://www.elmundo.es/elmundo/2009/07/08/espana/1247048060.html (8)http://www.starchase.org/ (9)http://cp.gpsworld.com/gpscp/Latest+News/ABI-GPS-Enabled-Handsets-Will-Byass- Economic-Downt/ArticleStandard/Article/detail/580207?contextCategoryId=1385 (10)http://www.gpsworld.com/gps/the-business-location-driven-coupons-iphone-8657 (11)http://www.youtube.com/watch?v=b64_16K2e08 Página 2
1.1 Propuesta Por último, los proyectos de Rusia (Glonass), Europa (Galileo), China (Beidou), India (IRNSS) o Japón (QZSS) que desarrollan sus propias redes de satélites así como los sistemas de mejora de la señal basados en satélites como EGNOS, WAAS para Estados Unidos, MSAS para Japón y GAGAN para la India hacen prever un uso mucho más intensivo de la localización en exteriores en los próximos años. De hecho ya se ofertan productos con precisión de centímetros(12) para guiado automático de vehículos agrícolas. 1.1. Propuesta A pesar de todos estos avances en la industria e investigación, estamos convencidos, y en este sentido va dirigido este trabajo, que se pueden crear aplicaciones con conocimiento de la localización futura, mucho más ricas en información para el usuario si conseguimos predecir sus rutas y destinos durante sus desplazamientos en exteriores de manera rápida y precisa. Para ello nuestra investigación se ha basado en el conjunto de los recorridos realizados por cada usuario en el pasado. Dado que el comportamiento de la mayoría de las personas en sus desplazamientos es repetitivo y regular, es decir, nos dirigimos normalmente a los mismos destinos utilizando las mismas rutas, las necesidades para realizar predicciones en cuanto a mapas y cartografía no son las mismas que en un sistema de navegación y guiado de vehículos. Por ello en este trabajo se proponen modelos predictivos utilizando técnicas de aprendizaje supervisado basadas en mapas personales generados por los propios usuarios. Como comprobaremos, estos mapas personales permiten una drástica reducción en el coste de almacenamiento con respecto a los Sistemas de Información Geográfica (GIS) y, lo más importante, su especialización. Para validar los modelos predictivos desarrollados se ha planteado una metodología off-line que permite verificar los resultados de cada uno de ellos. Una vez verificados los modelos se describe una posible implementación en teléfonos móviles (12)http://www.outbackguidance.com/Default.aspx?tabid=431 Página 3
Capítulo 1: Introducción con capacidades GPS que permite la predicción on-line, es decir, obtener la predicción mientras el usuario se desplaza. Además se consigue la recuperación de los recorridos para que el modelo se retro-alimente con cada nuevo desplazamiento. Por último, dado el elevado consumo de baterías de los chips GPS, se propondrán técnicas para incrementar la vida útil del dispositivo móvil entre cada recarga. 1.2. Escenario motivador La predicción de rutas y destinos futuros supone una interesante fuente de aplicaciones que permiten adelantar conocimiento, tanto personal como social, de manera que podamos optimizar nuestras tareas diarias, evitando interrupciones y situaciones imprevistas. Veamos como ejemplo ilustrativo el siguiente escenario: Julia sale de su despacho algo más tarde de lo habitual, a las 19:50 y se dirige hacia su coche con la intención de ir a casa. En cuanto sale al exterior, su dispositivo comprueba la localización de su familia (accediendo a cada uno de sus móviles) al tiempo que se actualiza su localización automáticamente con la etiqueta “saliendo del despacho”. El dispositivo le indica por pantalla que su marido se encuentra en el trabajo (esa indicación es suficiente para ella por lo que no necesita un mapa que lo localice). La noche anterior, su vivienda inteligente generó una lista de la compra y la transmitió a su terminal móvil. Como el terminal es capaz de intuir hacia donde se dirige Julia en cuanto lleva 2 minutos conduciendo, éste consulta de manera autónoma la información del tráfico de las rutas típicas que suele seguir. El tráfico es denso en todas ellas aunque la previsión consultada indica que media hora después la circulación será mucho más fluida. Así que le propone 2 opciones: utilizar una ruta alternativa (que no realiza con asiduidad) o detenerse en el supermercado al que suele ir en el que realizar sus compras y que se encuentra aproximadamente a 5 Página 4
1.2 Escenario motivador minutos del punto actual y a 20 minutos de casa. Como le gusta realizar la compra personalmente y el tráfico será previsiblemente más fluido un poco más tarde, elige la segunda opción. Cambia entonces su ruta y aparca en el parking del supermercado. A las 20:10 Julia sigue en el supermercado y como acostumbra a llegar a casa sobre las 20:30, el dispositivo le avisa de que tal vez fuese interesante enviar un SMS a su marido que acaba de salir de una reunión. El aviso en este caso es escrito (la información es privada y no le gustaría que la gente le viese hablando con su móvil). El SMS ha sido ya redactado “Estoy en el ’supermercado de la avenida’ comprando, tardaré unos 20 minutos en llegar a casa”. Ella revisa el mensaje, cambia 20 por 30 (aún no ha terminado de comprar y hay cola en la caja), lo envía y poco después recibe confirmación de que ha sido leído. Jesús, su marido, tras recibir el aviso decide ir a correr un poco antes de ir a casa, se cambia en el gimnasio de la empresa y sale a la calle por una nueva ruta que no ha hecho antes. Su terminal inteligente comprueba que se desplaza rápidamente pero no lo suficiente como para ir en bici o coche, entiende que está corriendo y le solicita su atención para elegir entre dos opciones: “guiado hacia un determinado lugar” o “programa de entrenamiento”. Jesús pulsa sobre su pantalla el segundo y el dispositivo le informa de la velocidad, metros recorridos y le muestra una gráfica comparativa con sus últimas 2 carreras. Además al detectar que ha conectado los auriculares, escoge la carpeta de mp3’s etiquetada como “deporte” para que incremente el ritmo. Jesús termina la carrera pronto (40 minutos) se ducha y regresa a la vivienda, antes de comenzar a conducir consulta en su móvil la posición de su esposa, ve que su estado es ”dirigiéndose a casa, tiempo estimado de llegada 10 minutos” así que llegará a tiempo para ayudarle a descargar la compra. Como hemos comprobado, el único momento en el que en el escenario se ha podido necesitar un GIS ha sido cuando se le ofertó a uno de los usuarios un sistema de guiado, pero en esos casos, lo que haríamos sería iniciar una aplicación de navegación específica. Las predicciones, el etiquetado de los lugares y la comunicación sin información privada (se ha evitado utilizar coordenadas para la comunicación), se Página 5
Capítulo 1: Introducción no visitados anteriormente. La gran mayoría de estudios se basa en bases de datos iniciales con muchos datos. En el Capítulo 7 propondremos una interesante herramienta que nos posibilitará ir aumentando los destinos y rutas sin haberlos realizado previamente. Funcionalidad muy orientada. La mayoría de las predicciones tienen como obje- to la ayuda a conductores de vehículos en su conducción pero las posibilidades son mayores. 1.5. Objetivos Una vez justificada la temática de la tesis, explicaremos los objetivos fundamentales de la misma. Diseñar un modelo que permita obtener un mapa personal asociado a cada usuario que sustituya al GIS y que no dependa del lugar del mundo en el que se encuentre. Definir una metodología que nos permita recuperar datos geo-posicionados para hacer un tratamiento de los mismos y elegir las mejores técnicas y algoritmos para realizar una detección eficiente de destinos y rutas. Definir varios modelos que nos permitan realizar la predicción de destinos online. Definir similitudes entre recorridos finalizados para poder generar un cluster de estos y detectar rutas comunes. Aplicar la metodología y los resultados obtenidos en la fase off-line a un entorno on-line. Definir nuevas técnicas que permitan aumentar el tiempo de vida de las baterías del dispositivo pudiendo éste ejecutar de manera continua un servicio de predicción de destinos. Página 12
1.6 Hipótesis de partida Proponer nuevas aplicaciones que permitan demostrar la utilidad de las predicciones en tiempo real. 1.6. Hipótesis de partida El desarrollo de este trabajo de investigación se orientará hacia un sector cada vez más amplio de usuarios que dispongan y utilicen frecuentemente dispositivos móviles con capacidades de gestión de base de datos y localización por GPS. Cuanta más capacidad tenga el dispositivo más posibles aplicaciones con conocimiento del contexto futuro podrán implantarse. Aunque las propuestas de esta tesis se pueden aplicar a sistemas de localización diferentes, en la implementación nos centramos en la predicción de recorridos urbanos e inter-urbanos rastreados por receptores GPS. Éstos no permiten el seguimiento en espacios sin visión directa sobre los satélites, por lo que quedan fuera de este trabajo la predicción de destinos en interiores. Nuestra propuesta, al usar como soporte mapas personales creados por el propio usuario al desplazarse diariamente, no necesitará de ningún GIS por lo que será utilizable en lugares donde no exista cartografía detallada, como por ejemplo en mares y océanos. El público objetivo de las predicciones de destino serán personas con todo tipo de hábitos de desplazamientos y que utilicen cualquier medio de transporte en el que puedan utilizarse dispositivos electrónicos (quedan por tanto fuera de nuestra hipótesis los aviones). 1.7. Estructura del documento El resto de este trabajo está estructurado en los siguientes capítulos: Página 13
Capítulo 1: Introducción Capítulo 2: Metodología off-line. Se propondrá una metodología para la recuperación de la información, su preprocesado y los algoritmos de extracción de conocimiento a partir de trazas de movimiento aportadas por diferentes voluntarios. Los objetivos de este capítulo son por una parte estudiar los métodos existentes para extraer los destinos frecuentes y las rutas seguidas, aportar nuevos algoritmos que mejoren los resultados, proponer una metodología con fases bien diferenciadas y estudiar los aspectos prácticos para poder desarrollar una metodología on-line realista. Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte”. Basándonos en las rutas que genera un usuario, creamos un mapa personal que nos permite utilizarlo aplicando un Modelo Oculto de Markov (HMM). El mapa personal disminuye en gran medida la cantidad de información utilizada por lo que lo estudiamos para aplicarlo en dispositivos móviles. Capítulo 4: Similitud de recorridos. Las medidas de similitud existentes entre recorridos no se adaptan a nuestras necesidades por lo que propondremos nuevas métricas que permiten comparar tanto recorridos finalizados entre sí como recorridos no finalizados con aquellos que sí lo han hecho, lo que nos permite predecir rutas y destinos. Capítulo 5: Resultados. Revisaremos los resultados obtenidos aplicando la metodología off-line y evaluaremos los modelos de predicción utilizando rutas mediante similitudes y “Mapas soporte” a través de HMM, comparando las dos alternativas. Capítulo 6: Predicción on-line. Una vez comprobados los resultados de los diferentes modelos de predicción, trataremos su implementación en un dispositivo móvil para permitir la predicción en tiempo real. Además se propondrán técnicas para reducir el consumo innecesario de baterías, mejorando la disponibilidad de los servicios de predicción. Capítulo 7: Aplicaciones. Mostraremos las aplicaciones definidas para nuestro sistema de predicción on-line, de modo que se destaque la utilidad del sistema de predicción on-line propuesto. Página 14
1.7 Estructura del documento Capítulo 8: Conclusiones y trabajo futuro. En este capítulo se presentan las conclusiones de esta tesis doctoral y las líneas de investigación abiertas sobre las que se trabajaremos en los próximos años. Apéndice A: Sistema GPS Describiremos de forma breve en este apéndice el funcionamiento del Global Positioning System y la estructura de las sentencias NMEA. Apéndice B: Currículum. En este apéndice incluimos las publicaciones y los proyectos en los que hemos participado durante la elaboración de este trabajo. Bibliografía. Tras los dos apéndices, incluimos la bibliografía utilizada en la elaboración del documento. Página 15
CAPÍTULO 2 METODOLOGÍA OFF-LINE En este capítulo se describen los procesos necesarios para transformar los datos obtenidos mediante receptores GPS en recorridos y rutas. De ese modo es posible preparar una predicción de destinos basada en recorridos pasados. Para ello explicaremos en primer lugar el estado del arte para a continuación detallar nuestra metodología y todas sus fases. 2.1. Estado del arte Para obtener predicciones de destinos basadas en el historial de desplazamientos de un usuario es necesario en primer lugar, tratar los datos mediante una serie de procesos que permita generar un conjunto de destinos frecuentes, un conjunto de recorridos y si se quiere realizar una predicción de rutas, un conjunto de rutas. La terminología utilizada por los diferentes autores asume las siguientes definiciones: Destino frecuente. Lugar que puede o no ser techado donde un usuario realiza una Página 17
Capítulo 2: Metodología off-line estancia durante un determinado tiempo que le resulta significativa. Además las visitas a ese lugar las hace con cierta asiduidad. Recorrido. Secuencia de puntos temporalmente ordenados, generados durante el desplazamiento de un usuario. Éste comienza con la salida del individuo de un destino frecuente y finaliza con la llegada a otro. Los recorridos podrán realizarse a pie o en cualquier medio de transporte, excepto en avión por no poder utilizar dispositivos electrónicos. Los puntos de los que se compone el recorrido tienen información diversa como la longitud, latitud, altura, velocidad, orientación e instante temporal. Ruta. Secuencia de puntos temporalmente ordenados, que representa a uno o más recorridos. Los puntos de los que se compone la ruta tienen información de longitud, latitud, altura, velocidad y orientación. Aunque se podría almacenar información sobre el día de la semana o el periodo del día en el que se realizan esos recorridos, normalmente se obvia la información temporal. Para conseguir obtener estos conjuntos, la metodología seguida por la mayoría de los autores se puede describir como la cadena secuencial de los siguientes procesos: 1. Recuperación de la información de localización. El objetivo de este proceso es el de obtener un conjunto de puntos válidos de localización con una marca temporal durante un periodo de tiempo suficiente como para poder realizar predicciones (en torno a un mes). Destaca de esta fase el protocolo que debe seguir el usuario que interviene en la recuperación para gestionar los dispositivos que debe llevar en todo momento y el filtrado de outliers. 2. Segmentado en recorridos. Una vez recuperados todos los puntos geolocalizados y marcados temporalmente es necesario realizar un segmentado que indique cuando un punto pertenece a un recorrido o al siguiente. 3. Filtrado de recorridos. Del conjunto obtenido, se deben eliminar aquellos recorridos espurios. Éstos pueden venir del comportamiento incorrecto del Página 18
2.1 Estado del arte usuario al seguir el protocolo de gestión del dispositivo de seguimiento, de errores en el sistema de posicionamiento o de problemas del dispositivo. 4. Extracción de destinos. Para recuperar los destinos frecuentes, se analiza la información de los desplazamientos recuperando los lugares visitados asiduamente. 5. Generación de rutas. En los sistemas de predicción que utilizan información sobre los caminos seguidos, se agrupan los recorridos en las rutas que los representan. 6. Predicción. El proceso de predicción permite detectar el destino final al que un usuario se dirige. Este proceso se surte del los conjuntos obtenidos (destinos frecuentes, recorridos y rutas). A continuación mostraremos como se tratan la secuencia de procesos en otros estudios. 2.1.1. Recuperación de la información de localización En todos los trabajos en los que se propone un sistema de predicción basado en recorridos pasados es necesario aplicar técnicas para recuperar los datos provenientes del sistema de localización. Aunque estos métodos dependen del sistema utilizado (GPS, Puntos de acceso WiFi geo-localizados, antenas GSM, etc.) siempre es necesario que los usuarios estudiados porten un dispositivo capaz de almacenar con una determinada frecuencia los valores de posicionamiento. Lo deseable sería que esto fuera menos invasivo, por ejemplo una aplicación que se ejecute de manera transparente en el teléfono móvil, sin embargo hasta estos últimos años, los dispositivos que integran un sistema de localización global no han aparecido en el mercado con precios razonables. Para conseguir una información útil, es necesario definir un protocolo de uso sencillo del dispositivo y motivar a los usuarios para que lo sigan de manera continuada durante todo el periodo de recuperación de datos. Página 19
Capítulo 2: Metodología off-line En muchos casos la motivación era la investigación dado que eran los propios autores quienes portaban los receptores [AS03, Mar04, SBZS06] por lo que un protocolo de uso sencillo no era una prioridad. Sin embargo en otros casos [LFK04, PLG+04, KH05, RMI07] los usuarios eran voluntarios que no tenían relación con los autores por lo que sí que era una prioridad. Cabe destacar la experiencia de Microsoft [KH05] donde fomentaron el uso de receptores GPS con el sorteo de un reproductor de audio y vídeo, de ese modo consiguieron una alta participación de empleados de la compañía. Además conectaron la alimentación del receptor GPS a las baterías de los vehículos de los voluntarios de modo que con el arranque y paro de los vehículos éstos se activaban o paraban (aunque obviamente sólo conseguían desplazamientos en un único medio de transporte). Una vez definido el protocolo y motivados los usuarios, es vital filtrar aquellos valores de localización espurios o redundantes. En el caso concreto del sistema GPS, al existir un gran número de receptores en el mercado, éstos implementan diferentes políticas de almacenamiento de los puntos, por lo que no es necesario realizar el filtrado. Los filtrados más comunes son los siguientes: Por intervalo de tiempo. La captura de puntos se hace con una frecuencia temporal determinada, evitando así redundancia por puntos excesivamente cercanos en tiempo. Por intervalo de espacio. Se fija la frecuencia espacial, de modo que hasta que el usuario no recorra un determinado espacio no se almacenará el siguiente punto. Por cambio de dirección. No hay intervalos temporales ni espaciales, sólo se almacenan aquellos puntos que cambien la dirección en un número de grados con respecto a la original. Es muy útil para evitar almacenar muchos puntos en trayectos con largas rectas. Por cambio de velocidad. Tampoco hay intervalos temporales o espaciales, sólo se guardan los valores en los que varíe en varias unidades la velocidad del recep- Página 20
2.1 Estado del arte tor. Se considera interesante cuando queremos determinar cuando se comienza un desplazamiento y cuando se detiene. 2.1.2. Segmentado en recorridos Como los puntos GPS no ofrecen una indicación explícita de cuando comienza o finaliza un recorrido, es necesario segmentar la información para crearlos. Marmasse y Schmandt [MS00] usaron la pérdida de la señal GPS para indicar que el usuario había entrado en un edificio y por tanto se podía considerar un lugar de visita. Ashbrook y Starner [AS03] ampliaron esa técnica marcando como puntos de segmentado aquellos en los que un usuario permanecía más de 10 minutos, es decir, el punto de la secuencia que distaba temporalmente más de 10 minutos con el siguiente. Llamaremos a esta técnica a partir de ahora segmentado por salto temporal y podemos ver un ejemplo de ésta en la Tabla 2.1. Tabla 2.1: Segmentado por salto temporal entre los puntos 659 y 660. Id_Punto Tiempo Latitud Longitud Recorrido 658 13/12/2007 20:47:41 37.38184 -5.96976 1 659 13/12/2007 20:47:49 37.38176 -5.96977 1 660 13/12/2007 22:13:52 37.36250 -5.98221 2 661 13/12/2007 22:13:58 37.36250 -5.98220 2 El segmentado por salto temporal es la política seguida por diferentes autores [LFK04, HT04, KH06, Kru08, SBZS06, PLFK03] variando el tiempo de estancia entre tres y diez minutos. La elección de este valor de tiempo es una tarea compleja dado que es difícil diferenciar entre un semáforo que retenga el vehículo tres minutos y una parada del mismo tiempo para recoger a alguien en un lugar significativo. En los trabajos de Liao [LFK05, LFK07] se estudian los errores de esta técnica y se detecta que con valores entre cinco y diez minutos se obtienen el menor número de falsas detecciones. Concretamente el número de falsos positivos es inversamente Página 21
Capítulo 2: Metodología off-line Figura 2.2: PDA y receptores GPS utilizados en la fase de recuperación de recorridos. o Visual Earth(3). Esto permitió que los voluntarios recuperasen y analizasen sus desplazamientos pasados, midiendo distancias y tiempos, lo que alentó su uso incluso en periodos vacacionales. (3)http://maps.live.com Página 28
2.2 Nuestra propuesta 2.2.3. Filtrado y normalizado de puntos Una vez obtenidos los puntos GPS, es necesario realizar un tratamiento que permita eliminar los outliers y normalizar la secuencia de puntos. Aunque comprobamos que otros autores se apoyaban en las políticas de almacenamiento de los receptores GPS para evitar filtrar la información, nosotros al utilizar varios receptores decidimos independizarnos de esas implementaciones propietarias, capturar la información sin restricciones por parte del receptor y posteriormente crear un conjunto de filtros para generar el conjunto de puntos filtrados. Para comprender los filtros propuestos, comentamos a continuación los problemas derivados del sistema GPS, de los dispositivos receptores utilizados y del comportamiento de los usuarios. 2.2.3.1. Problemas conocidos en la captura de datos Tiempos de arranque del receptor. El tiempo que tarda un receptor GPS en obtener una primera posición válida varía según diferentes situaciones. Cuando el dispositivo se utiliza por primera vez o lleva mucho tiempo sin utilizarse, se produce el “arranque en frío”: la información que dispone sobre la visibilidad de los satélites es muy imprecisa por lo que tiene que buscarlos, el tiempo que puede durar ese proceso puede ser del orden de varios minutos. En nuestro caso los receptores se utilizaron frecuentemente por lo que se daba el “arranque normal” que en nuestros receptores era del orden de 40 segundos en condiciones ideales. Sin embargo, si la visibilidad sobre el cielo no era suficiente o el receptor estaba en movimiento, el tiempo de primer fijado de señal válida aumentaba enormemente, por lo que nos encontramos con situaciones en las que el primer punto del recorrido grabado estaba muy lejano del primero del recorrido real. Cañón urbano. Cuando estamos situados en calles circundadas por edificios altos se produce el llamado efecto “cañón urbano” que consiste en el “rebote” de las señales provenientes de los satélites en los edificios. Esto causa una reducción Página 29
Capítulo 2: Metodología off-line importante de la precisión e incluso una interrupciones de posiciones válidas de duración variable. En las ciudades en las que hemos recogido itinerarios, este efecto no suele darse por rascacielos pero sí que se da en calles estrechas típicas de Andalucía. Puntos obtenidos en interiores. Aunque hemos comentado que el receptor GPS debe estar en espacios abiertos con visión directa sobre el cielo para obtener señales de cuatro satélites, a veces también es posible obtener datos válidos en espacios techados si el receptor GPS está cerca de una ventana, provocando capturas de puntos validados por el sistema pero aislados temporalmente. Errores de dispositivo. Por algún tipo de error del dispositivo, determinados puntos, normalmente el primero de un nuevo recorrido distaba cientos de kilómetros con los siguientes. También aparecían puntos aislados en los polos, que debían filtrarse. Conducción. Además de los problemas derivados de las limitaciones de la tecnología GPS, también aparecían otros referentes a la experiencia real. Al proceder a analizar los datos, encontramos situaciones que no aportaban información relevante con respecto a la forma de los recorridos. Entre ellos los atascos en la que existían numerosos puntos muy cercanos unos de otros y la búsqueda de aparcamiento que además de la normal “desesperación” del conductor, incrementaba el número de puntos en los alrededores del lugar de destino, desvirtuando la forma de la secuencia de puntos. Medio de transporte y velocidad del trayecto. Si dos personas realizan un recorrido por la misma ruta, con sus receptores obteniendo puntos a idéntica frecuencia pero el primero lo hace a una velocidad media mucho mayor que la del segundo, al comparar las trazas que generan ambos, el resultado podría asemejarse al observado en la Figura 2.3. Todas estas situaciones, hacían que fuese necesario realizar en primer lugar un filtrado de puntos erróneos y de los derivados de situaciones anómalas y en segundo un Página 30
2.2 Nuestra propuesta Figura 2.3: Ejemplo de recorridos idénticos con trazas diferentes. normalizado para evitar que recorridos idénticos con velocidades diferentes tuviesen trazas GPS distintas. De ese modo tendremos puntos validados cuasi-equidistantes de manera que se pudiese comparar la componente espacial de manera independiente a la de velocidad, frecuencia de muestreo o medio de transporte utilizado. 2.2.3.2. Filtrado de puntos GPS Definición 2 (Filtrados)Definiremos el conjunto de puntos filtrados como el generado a partir de aplicar una serie de filtros al conjunto LogGPS (Definición 1) y lo notaremos como Filtrados ={b1, b2, . . . , bm},(m≤n)siendo bi=aktal que HDOPk≤HDOPmax (Precisi´on) velmin ≤velk≤velmax (V elocidad) dist(ak−1, ak)≥δ o dist(ak−1, ak+1)> δ (Distancia) , con HDOPmax, velmin, velmax yδparámetros que explicamos a continuación. Este conjunto, contiene una única secuencia de puntos GPS que indica todos los desplazamientos de un usuario sin indicar las paradas realizadas. Describimos a Página 31
Capítulo 2: Metodología off-line continuación los algoritmos utilizados. Filtrado por análisis de precisión. Como las componentes fundamentales en los recorridos son la latitud y la longitud, eliminamos aquellos puntos cuya HDOP sea muy elevada. Para calcular el valor de HDOP adecuado es necesario saber la precisión de los dispositivos receptores usados. Nuestros dispositivos poseían una precisión de 3 metros (CEP(4)) y 6 metros (2D RMS(5)). Es esta última medida la que utilizaremos. Para saber los metros de error máximo es necesario multiplicar la precisión 2D RMS del dispositivo por el valor de HDOP. Nosotros elegimos un valor de HDOPmax = 6 con objeto de tener valores dentro de los 36 metros de precisión (la mayoría de los puntos tienen una HDOP menor pero los peores casos los consideramos dentro de esa distancia). Es decir, si HDOPi> HDOPmax ⇒ak6∈ Filtrados. Con este filtrado se elimina la información imprecisa especificada por el propio sistema GPS. Filtrado por velocidad. Los puntos que indicaban una velocidad menor o igual al parámetro velmin fueron eliminados debido a la ausencia de desplazamiento significativo. Así mismo los que indicaban una velocidad por encima de un umbral velmax también se eliminaron. En nuestro caso se fijó velmin = 0 (ausencia total de movimiento) y velmax = 300 debido a que por encima de esa velocidad con vehículos terrestres es probable el error del dato. De ese modo, si velk≤velmin ovelk≥velmax ⇒ak6∈ Filtrados. Filtrado por distancia. Para eliminar puntos redundantes que provenían de situaciones en las que el usuario se desplazaba lentamente, por ejemplo, cuando un conductor está inmerso en un atasco, se consideró una distancia umbral que indicaría cuando eliminar puntos muy cercanos entre sí. Es decir, si distancia(ak−1, ak)< δ ydistancia(ak−1, ak+1)< δ ⇒ak6∈ Filtrados. Con este algoritmo conseguimos eliminar aquellos puntos demasiado cercanos (4)Radio del círculo que contiene el 50% de las medidas GPS. (5)Radio del círculo que contiene el 98% de las medidas GPS. Página 32
2.2 Nuestra propuesta evitando filtrar aquellos que hacen que se alejen excesivamente cada par de puntos. Para escoger la distancia umbral δse estudió la frecuencia de muestreo máxima de los receptores GPS (1 Hertzio) y los medios de transporte en los que podrían utilizar los usuarios los receptores (coche, autobús, moto, bicicleta, barco o a pie), descartando el avión por la prohibición del uso de aparatos electrónicos. Considerando una velocidad máxima de 144 kilómetros por hora (24 por encima de lo permitido en autopistas), la distancia máxima recorrida en un segundo sería de 40 metros. Esta distancia es la recorrida en 3.6 segundos a una velocidad media de 40 km/h (velocidad adecuada conduciendo un vehículo en ciudad) o en 36 segundos a una velocidad de 4 km/h (a pie) lo que nos permitiría filtrar una gran cantidad de puntos cuando los usuarios se desplazasen lentamente. De ese modo δ= 40. Algoritmo de eliminación de bucles. Inicialmente se contempló la posibilidad de filtrar los bucles en los recorridos. Se daban en giros indirectos durante recorridos en coche y en búsquedas de aparcamiento, pero la imposibilidad de determinar la influencia del bucle en el recorrido, terminó por descartarlo. 2.2.4. Segmentado en recorridos por tiempo Como hemos comentado en el estado del arte, es necesario tratar los datos geoposicionados como un conjunto de recorridos por lo que debemos segmentar el conjunto Filtrados. En nuestra aproximación el proceso de segmentado lo realizamos en varias fases. En primer lugar utilizamos la técnica salto temporal explicada en la sección 2.2.3. Posteriormente extraeremos los destinos (ver Sección 2.2.5) y finalmente aplicaremos un nuevo segmentado que llamaremos segmentado por distancia a destinos (ver Sección 2.2.6). En nuestro trabajo utilizamos como umbral para el salto temporal un valor de cinco minutos (saltotemporal = 5) por considerar un tiempo suficiente como para Página 33
Capítulo 2: Metodología off-line evitar paradas por semáforos y atascos y a la vez poder detectar breves paradas de esa duración. Definición 3 (SegTiempo)Definiremos el conjunto de puntos que indican el fin de un recorrido aplicando el segmentado temporal indicado anteriormente y notaremos como SegTiempo ={c1, . . . , c0 n}, siendo ci=bktal que (tiempok−tiempok+1)> saltotemporal. De la anterior definición determinamos el conjunto de recorridos: Definición 4 (RecorridosT)Definiremos el conjunto de recorridos segmentados temporalmente como la secuencia ordenada de todos los puntos filtrados que finalizan en uno de los puntos de SegTiempo y notaremos como RecorridosT=RT 1, . . . , RT n tal que RT i={bj, . . . , bk}siendo bjel punto origen y bk=ciel punto destino. 2.2.5. Extracción de destinos En nuestro trabajo utilizamos la aproximación de puntos finales (ver Sección 2.1.4), ya que trabajar sobre el conjunto SegTiempo en vez del Filtrados reduce en gran medida el tiempo de ejecución del algoritmo de cluster, facilitando de esa forma su implementación en dispositivos móviles. Para poder escoger una técnica determinada de clustering observamos las siguientes características de nuestro problema. Tamaño de los lugares. Cada lugar que se visita tiene un tamaño determinado. No es lo mismo visitar un campus universitario que una pequeña tienda. Distancia entre lugares. Para evitar superposiciones entre lugares cercanos, debemos tener en cuenta que no podemos agrupar en un mismo cluster puntos finales muy distantes. Página 34
2.2 Nuestra propuesta Falsos lugares. Largas paradas debidas a atascos o esperas en lugares que no significan nada para el usuario podrían dar lugar a detección de “falsos lugares”. Este aspecto es significativo porque algoritmos como K-means incluyen todos los puntos en el cluster final, haciendo los resultados bastante sensibles al ruido. En nuestra propuesta deberemos poder dejar al margen este tipo de fenómenos. De lo anterior podemos deducir que tendremos que establecer un umbral de tamaño máximo que permita detectar lugares que ocupen grandes extensiones (en la práctica lo que tenemos son diferentes puntos de acceso lejanos a un mismo lugar) pero que no agrupe dos lugares cercanos como uno solo. Por otra parte también debemos configurar nuestro algoritmo de cluster de modo que no incluya puntos que supongan ruido. 2.2.5.1. Radio de destinos Aunque ninguno de los autores propone justificadamente sus medidas de distancia, parece lógico que cuanto mayor sea ésta, menor será la granularidad, es decir no distinguiremos entre destinos cercanos entre sí. A su vez conseguiremos predicciones más precisas, debido a que se distinguen menos lugares y hay menos probabilidades de que la predicción sea errónea. Si considerásemos una distancia umbral de 25 kilómetros, podríamos realizar predicciones de destinos entre diferentes ciudades sin embargo no valdrían las predicciones urbanas, donde suelen realizarse la mayoría de los desplazamientos. Si por contra consideramos una distancia reducida, tendremos una alta granularidad, distinguiendo por ejemplo entre edificios cercanos pero reduciendo la precisión de la predicción. Por ejemplo, con una distancia umbral de 20 metros, podríamos distinguir entre el edificio donde trabajamos y el parking del mismo. Eso provocaría problemas a la hora de predecir el destino cuando nos dirigimos a trabajar ya que ambos lugares están muy relacionados y muchas veces se indicaría que vamos al parking en vez de al trabajo. Al depender el radio de los destinos de la distancia mínima entre lugares que Página 35
Capítulo 2: Metodología off-line visita cada usuario, decidimos basarnos en otro parámetro para establecer la granularidad del sistema: la utilidad de las predicciones. Las predicciones resultan más útiles cuánto más se adelanten al hecho que predicen. Consideramos útiles las predicciones que adelanten el destino al que se dirige un usuario en más de 3 minutos. Si tenemos en cuenta la menor velocidad de desplazamiento estudiada (a pie: unos 4 kilómetros por hora), la distancia que podremos recorrer en esos 3 minutos a esa velocidad es de unos 200 metros. Esa será el valor de nuestro parámetro. 2.2.5.2. Mínimo número de puntos por cluster Como comentamos, se dan situaciones en las que se podrían detectar “falsos lugares”. Un ejemplo que se repite frecuentemente son los atascos en carreteras de acceso a las grandes ciudades en horas punta. Si cada lugar en los que nos quedamos parados en esa carretera más de cinco minutos (tiempo utilizado para el segmentado temporal) lo consideramos como un lugar, obtendríamos múltiples destinos nada significativos. De ese modo, definimos un parámetro de mínimo número de puntos por cluster para que aquellos lugares que no fuesen visitados menos de un cierto número de veces no se considerasen destinos frecuentes. El número de repeticiones se escogió variándolo en el rango desde una a cinco y comprobando el número de lugares detectados. Un número muy elevado de repeticiones provocaba una pérdida de información significativa sabiendo que se admitieron datos de usuarios que sólo recogieron dos semanas de recorridos. Por otra parte, un número reducido, detectaba lugares muy poco frecuentes por lo que se escogió un valor de tres repeticiones, coincidiendo con el utilizado en el trabajo de Marmasse [MS00]. 2.2.5.3. Cluster jerárquico modificado El cluster utilizado para agrupar los puntos pertenecientes a SegTiempo en destinos es una modificación de un cluster jerárquico por distancia mínima. La modifi- Página 36
2.2 Nuestra propuesta cación consistió en que, tras aplicar este cluster, eliminamos aquellas agrupaciones con menos de tres elementos. Definición 5 (Destinos)Definimos el conjunto de destinos como el obtenido tras aplicar un cluster jerárquico por distancia mínima utilizando los parámetros de radio del destino (radio) y mínimo de puntos (minPtos) al conjunto SegTiempo y lo notaremos como Destinos =CJerarquico(SegTiempo, radio) = {d1, d2, . . . , dn}, siendo |di| ≥ minPtos. Una vez obtenido Destinos para cada recorrido RT i={bi, . . . , bj}etiquetamos su origen y destino con los destinos más cercanos a sus puntos extremos, es decir, RT itendrá como origen dky destino dlsiendo: m´ın(dist(bi, Destinos)) = dist(bi, dk), m´ın(dist(bj, Destinos)) = dist(bi, dl). En la Figura 2.4 podemos ver un extracto del mapa de destinos obtenidos para el usuario 1 estudiado en el Capítulo 5. En este mapa los puntos muy cercanos no pueden verse por lo que hemos agregado la lista de sus identificadores. Se puede observar cómo se han obtenido dos puntos finales (marcados con los números 7 y 26) que no han sido agrupados como ningún lugar al repetirse menos de tres veces. Debemos remarcar que sólo los puntos finales y no los puntos orígenes del conjun- to RecorridosTse usaron como candidatos para obtener los destinos frecuentemente visitados. Se hizo así para evitar el problema de tiempo de arranque del receptor explicado en la Sección 2.2.3.1. Recordamos que ese tiempo provocaba que un recorrido contuviese puntos no válidos en su inicio: RT i={ai, ai+1, . . . , aj, bk, bk+1, . . . , bn}. De ese modo, al filtrar los primeros puntos, el primer punto válido bkdistaba mucho del origen real, sin embargo el último punto válido bnsí era un candidato adecuado. Página 37
Capítulo 2: Metodología off-line 2.2.11. Técnicas de predicción Se evaluaron dos técnicas sobre el conjunto de datos obtenidos: Modelos de Markov Ocultos Utilizando el mapa de puntos soporte obtenido en la fase de generación de mapas personales, se aplicó un HMM en el que los estados son los destinos y las observaciones los puntos soporte. Esta técnica se explicará en el Capítulo 3. Similitudes dinámicas Utilizando el conjunto de rutas como mapa personal, se aplicó una medida de similitud dinámica que compara el recorrido de test con las rutas del mapa. Esta técnica se comentará en el Capítulo 4. 2.2.12. Evaluación Para evaluar los resultados de la predicción de cada técnica, en cada recorrido de test, se obtuvieron las resultados para el 10, 25, 50, 75 y 90 por ciento del trayecto recorrido sobre el total. De ese modo pudimos evaluar los sistemas de predicción prácticamente al comienzo del recorrido y en pasos intermedios hasta casi la finalización del mismo. Cabe destacar que aún la predicción realizada en el tramo final (en el 90% del recorrido) resulta útil en muchos casos donde la antelación de la predicción no es crítica. Esto lo veremos en las aplicaciones, concretamente en una herramienta útil para ciclistas. Con objeto de cuantificar la bondad de la predicción para cada método hemos considerado el siguiente índice: IP = 0,5 n−1 X i=0 (Pi+1 −Pi)(Qi+1 +Qi) donde Pirepresenta el porcentaje de recorrido parcial atravesado (en tanto por uno) y Qiel porcentaje de acierto en la predicción (en tantos por uno). Además consideramos que P0=Q0= 0 (sin desplazamiento el acierto es cero) y que Pn= Qn= 1 (cuando estamos en el lugar final asumimos que se acierta el 100% de las Página 44
2.3 Resumen veces) y ndenota el número de predicciones realizadas (en nuestro experimento es 6 que se corresponde con el 10%, 25%, 50%, 75%, 90% y 100%). El índice considerado se basa en las mismas consideraciones que el índice de Gini, el cual es utilizado en la literatura económica para el estudio de desigualdades en el reparto de un volumen de unidades monetarias. Así se tiene que 0< IP < 1y cuanto mayor sea IP mejor será el método de predicción ya que representa el área encerrada por el eje −−→ OX, la recta r:X= 1; y la curva que describe el índice. En la figura 2.7 podemos observar la representación de este índice para un usuario ficticio. Figura 2.7: Representación del índice IP definido para cuantificar la bondad de nuestras predicciones. 2.3. Resumen En este capítulo hemos estudiado en primer lugar las fases seguidas por otros autores para extraer información off-line a partir de una base de datos de puntos geo-posicionados obtenidos por personas durante sus desplazamientos habituales en exteriores. Tras ello hemos propuesto una metodología propia que permite recuperar información sobre destinos frecuentes, recorridos y mapas personales y a partir de Página 45
Capítulo 2: Metodología off-line ella evaluar dos técnicas de predicción: HMM y similitudes dinámicas. Por último aportamos un índice que permite evaluar la bondad de los métodos de predicción basándose en su comportamiento durante la ejecución parcial del recorrido de test. De este capítulo cabe destacar el enfoque novedoso de los mapas personales independientes del lugar donde se realicen las predicciones y por tanto de si existe cartografía de GIS. Así mismo, veremos como la fase de segmentado por cercanía a destinos mejora sustancialmente los resultados obtenidos con respecto a la técnica de segmentado temporal que es la adoptada por la mayoría de autores. Una vez explicada la metodología off-line, pasamos a describir las técnicas utilizadas para la predicción. En el Capítulo 3 estudiaremos la utilización de los modelos de Markov así como la generación de mapas de puntos soporte y en el Capítulo 4 utilizaremos medidas de similitud tanto para predecir el destino final como para realizar el cluster de rutas (ver Sección 2.2.9). Finalmente en el Capítulo 5, veremos el comportamiento de ambas técnicas. Página 46
CAPÍTULO 3 MODELO DE MARKOV OCULTO SOBRE “MAPA SOPORTE” Al no utilizar ningún GIS, propondremos un novedoso método para generar un mapa personal, que llamaremos “mapa soporte” y que permitirá aplicar modelos probabilísticos convencionales. En nuestro caso se seleccionó un modelo de Markov oculto. En primer lugar, nos centramos en describir los trabajos existentes en la literatura relacionados con nuestra aproximación. Seguidamente haremos una breve descripción de los modelos de Markov y los modelos de Markov ocultos, que serán fundamentales para nuestro sistema de predicción, para a continuación detallar la generación de mapas soporte. Finalmente explicaremos la integración de estos mapas con el modelo probabilístico. 3.1. Estado del arte En esta sección se muestran algunos trabajos que, al igual que en nuestra aproximación, utilizan modelos probabilísticos para obtener predicciones de rutas y des- Página 47
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” tinos de un usuario en un entorno geográfico. Los primeros en utilizarlos en este campo fueron Ashbrook y Starner entre 2002 y 2003 [AS02, AS03]. Ellos propusieron modelos de Markov de segundo orden para realizar la predicción de destinos en la zona de Atlanta (Estados Unidos). Su objetivo era prever el siguiente destino más probable al que se dirigiría un usuario. Su propuesta utilizaba el historial de los lugares visitados en el pasado, de modo que conociendo el último lugar visitado, es decir el lugar en el que se encontraba la persona estudiada y el penúltimo lugar visitado, predecir el próximo desplazamien- to. Su limitación fundamental es que además de no tener en cuenta las rutas que seguiría, no se consideraban ni el lugar actual del transeúnte o conductor ni si éste estaba en movimiento o no. Aún así, para el objetivo propuesto, la simplicidad del modelo usado les reportó buenos resultados. Un ejemplo del planteamiento de esta aproximación puede ser seguida de la Figura 3.1. En ella pueden verse las probabilidades de desplazamiento entre 3 lugares. Las flechas etiquetadas indican la fracción del número de desplazamientos que se hicieron desde el lugar origen hasta el lugar destino entre el número total de desplazamientos realizados desde ese lugar. En la Tabla 3.1 podemos ver las probabilidades de transición entre dos (identificadores A y B) de los tres lugares de la figura. Los demás identificadores corresponden con otras localizaciones. En 2003 desde la Universidad de Washington, Patterson propuso un modelo basado en una red Bayesiana dinámica [PLFK03], que representa un modelo de Markov de primer orden, en la que se infería el medio de transporte (coche, autobús o a pie) y el destino de un conductor de manera no supervisada. En la Figura 3.2 podemos ver su configuración y sus resultados. Al ser no supervisada, las predicciones no eran los lugares a los que se dirigía la persona, sino la distancia medida en número de manzanas hasta donde era posible conocer el destino. De ese modo se puede observar como en el 50% de los casos era posible conocer la futura localización del usuario hasta en 17 manzanas si iba en autobús. Un año más tarde, este grupo, mediante la iniciativa de Liao [LFK04] mejoró el Página 48
3.1 Estado del arte Figura 3.1: Ejemplo de modelo de Markov de segundo orden. modelo anterior utilizando un modelo de Markov jerárquico que puede representarse de manera compacta por una red Bayesiana dinámica. Realizan la inferencia mediante un filtro de partículas “Rao-Blackwellizado” que combina el filtro de partículas y los filtros de Kalman. El modelado del mundo al igual que en su anterior trabajo es un grafo dirigido donde las aristas corresponden con las calles de la ciudad de Washington y los vértices con las intersecciones. Los resultados comparados con los de Ashbrook pueden verse en la Tabla 3.2. En la Figura 3.3 podemos observar los instantes temporales kyk−1del modelo Página 49
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” Tabla 3.1: Probabilidades de transición de los modelos de Markov de primer y segundo orden. Transición Frecuencia Relativa Probabilidad A→B 14/20 0.7 A→B→A 3/14 0.2142 A→B→C 2/14 0.1428 A→B→D 3/14 0.2142 A→B→E 3/14 0.2142 A→B→F 3/14 0.2142 B→A 16/77 0.2077 B→A→B 13/16 0.8125 B→A→J 3/16 0.1875 Tabla 3.2: Tabla de precisión de modelos de Markov de segundo orden (Ashbrook) y jerárquico (Liao). Precisión media en cada instante Modelo Al inicio 25% 50 % 75% Modelo de Markov 2ºOrden 0.69 0.69 0.69 0.69 Modelo Jerárquico 0.66 0.75 0.82 0.98 que proponen. El modelo más completo y complejo, mejora en mucho al anterior de Patterson y al propuesto por Ashbrook. La capa superior permite la detección de novedades, la intermedia infiere destinos y segmentos de carretera. La capa inferior permite la detección del lugar, velocidad y medio de transporte usado. Es interesante observar que aunque el modelo jerárquico que proponen es mejor según avanza el recorrido, el modelo de Markov de segundo orden permite realizar una muy buena estimación de los destinos probables desde el inicio. El mayor problema del modelo de Liao, es que al ser necesario la estructura de un mapa de calles de la ciudad, el modelo es local y almacena e intervienen muchísimos Página 50
3.1 Estado del arte Figura 3.2: Red Bayesiana dinámica utilizada por Patterson (derecha) y gráfico de predicción de correcta localización (izquierda). datos que difícilmente se usarán, dado que un usuario “tipo” recorre una mínima fracción de la red de calles de una ciudad. En 2005, Gogate [GDB+05], incide en el uso de un modelo de red Bayesiano, concretamente en uno híbrido y dinámico para el problema de la predicción de rutas y destinos. Como ellos comentan tanto su modelo como varios más analizados no son más que representaciones de procesos de Markov que permiten tanto variables discretas como continuas, debido a que pretenden modelar aspectos de la vida real que contienen información probabilística y determinista. En 2006 el grupo de Microsoft liderado por Krum [KH06, Kru06] propone un método de predicción original, llamado “Predestination”. En él se analiza el área de Seattle generando una malla de 40 kilómetros cuadrados cuyas celdas miden 1 kilómetro cuadrado, siendo el número de celdas N= 40 ∗40 = 1600. Utilizan un conjunto de 7335 recorridos realizados por 169 conductores e infieren la distribución de probabilidad de que un usuario finalice un recorrido sobre cada una de las celdas. Aplicando el teorema de Bayes bajo distintas hipótesis “a-priori” obtienen dos modelos diferentes. El primero llamado “modelo cerrado”, donde consideran que un usuario sólo visita una serie de lugares que ya ha visitado previamente y el segundo, “modelo abierto” en el que se supone que el usuario podrá despla- Página 51
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” Figura 3.3: Modelo de Markov Jerárquico utilizado por Liao (derecha). Comparación del modelo propuesto por Patterson y el propuesto por Liao (izquierda). zarse hacia lugares desconocidos (muy útil cuando se analiza por primera vez un determinado conductor). En ambos modelos calculan la probabilidad de que cada celda sea el destino, es decir: P(ci|S)donde cirepresenta la celda destino i-ésima de las Nposibles y S= {s1, s2, ..., sN}es una variable aleatoria que representa el vector de características de las celdas atravesadas hasta el instante actual. Aplicando el Teorema de Bayes, P(ci|S) = P(STci) P(S)=P(S|ci)P(ci) PN j=1 P(S|cj)P(cj),(3.1) donde P(ci)es la probabilidad “a priori” de que el destino sea la celda iyP(S|ci) es la probabilidad de que se de la secuencia Sdado el destino ci(se denominan “verosimilitudes”). En el modelo abierto, la probabilidad “a priori” considerada en cada celda es P(ci) = 1 N, dando a todas las celdas la misma probabilidad. En el modelo cerrado, se utiliza un histograma de celdas que el usuario utiliza como destinos, donde para calcular la probabilidad a priori, se basan en dos tipos de información: Página 52
3.1 Estado del arte Tipo de suelo e infraestructura existente. Utilizando un mapa de Estados Unidos con la cobertura del suelo categorizado en 21 tipos, calculan la probabilidad de que los destinos sean un tipo de suelo u otro. Contemplando únicamente la primera información, asignan más probabilidad a zonas comerciales y de industria que contienen infraestructura como carreteras y raíles de tren, y a zonas residenciales que a zonas como barrancos o lagos. Lugares frecuentes. Basándose en los lugares en los que el usuario tiene como destino, dichos lugares poseen una probabilidad mayor de ser destino que otro en el que no haya estado aún. Para calcular la probabilidad futura, se basan en otros dos tipos de información: La probabilidad de una conducción eficiente. De manera intuitiva, si un conductor toma un camino muy ineficiente para llegar a un determinado lugar, seguramente es que no va a dicho lugar. Sabemos que cuando comenzamos un recorrido (estado s0), el tiempo que resta para llegar al destino (ts0) será mayor que el tiempo restante cuando llegamos a él (estado sN): tsN= 0. Si segmentamos el recorrido en trozos, basado en la división del mapa comentado, teóricamente se cumplirá que tsi> tsi+1 . Tras realizar los cálculos con los datos de sus recorridos y utilizando un planificador de rutas obtuvieron que la probabilidad de que un conductor redujese el tiempo de llegada al avanzar de celda era p= 0,625. El planificador daba estimaciones de tiempos mejores que al utilizar la distancia euclídea con una velocidad constante aunque no era del todo preciso por no considerar instantes temporales en los que era más rápido utilizar un camino más largo (por ejemplo circunvalaciones) que otro más directo. La distribución de la duración del viaje. Krumm y Horovitz también utilizan la duración del viaje para calcular la probabilidad de fin de trayecto. Se basaron en los datos de 66000 estadounidenses que mostraban que los viajes que más se repetían eran los relativamente cortos, de 5 a 19 minutos. Página 53
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” Debe ser integrable en dispositivos móviles con características de almacenamiento y baterías reducidas; y Debe ser utilizable por cualquier usuario en cualquier parte del mundo. Además como indicamos en la Sección 1.1 las necesidades para realizar predicciones en cuanto a mapas y cartografía no son las mismas que un sistema de navegación y guiado de vehículos por lo que podemos evitar conexiones a GIS costosas y almacenar cartografía de diferentes países sino sólo de nuestro mapa personal. Vistos los diferentes trabajos de predicción de destinos basados en modelos probabilísticos y concretamente en los modelos de Markov, decidimos proponer un sistema basado en un HMM. En él consideramos los estados como los lugares hacia los que tenemos la intención de desplazarnos en un instante determinado. Esta es la parte oculta del modelo y lo que pretendemos inferir. Para ello, contamos con las observaciones visibles que nos proporciona el receptor GPS de donde nos encontramos en cada momento. Dado que esas observaciones serían inabordables por la cantidad de puntos GPS diferentes que podemos obtener únicamente considerando la latitud y la longitud en cualquier punto del mundo, es necesario reducir éstas a los puntos que aportan información relevante para el usuario estudiado. Veremos cómo generar un mapa personal o mapa soporte a partir del historial de recorridos de cada usuario. Este mapa tendrá información significativa de todas las ciudades o incluso zonas sin cartografiar que frecuente el usuario. Consultando este mapa, nuestro sistema podrá inferir el destino más probable al que se dirige. A continuación pasamos a describir la generación del mapa soporte y la definición de los parámetros fundamentales de nuestro HMM. Página 60
3.3 Nuestra propuesta 3.3.1. Generación del mapa soporte La generación de este mapa, debe contener información de los recorridos pasados del usuario. El problema es que cada recorrido tiene cientos de puntos y cada usuario puede tener una cantidad importante de recorridos. Si queremos incluir todos los puntos en un modelo estadístico, tendríamos un modelo tan grande como inútil. Para reducir el conjunto inicial de datos, podemos utilizar las rutas descritas en la Sección 2.2.9 en vez del conjunto de todos los recorridos. Nuestro objetivo es identificar cada ruta por un número reducido de puntos para incorporarlos a nuestro HMM. Los puntos que incluyamos deben ser significativos de modo que nos ayuden a predecir hacia donde se dirige el usuario simplemente sabiendo que éste está cerca del punto y su dirección. En la Figura 3.6 podemos ver un ejemplo de qué tipo de mapa queremos crear. En él pueden observarse tres destinos que en nuestro modelo corresponden con estados no visibles. Los aros corresponden con los puntos significativos que pasamos a explicar a continuación. 3.3.1.1. Selección de puntos de cruce Consideremos la situación mostrada en la Figura 3.7: un usuario avanza por un camino y aparece ante él un cruce en el que puede escoger 4 posibles desviaciones. Descifrar su destino en ese instante será mucho más complejo que si esperamos unos segundos a que escoja una de las bifurcaciones. En este último caso, los destinos que se alcanzan por los tres caminos que ha dejado atrás resultan mucho menos probables que el que se alcanza siguiendo la ruta elegida. Esta es la justificación del porqué decidimos seleccionar los puntos tras un cruce de recorridos como los puntos significativos. Para evitar confusiones, a partir de ahora, el término “cruce” indicará un cruce real o un solapamiento de recorridos seguido de una separación de éstos como se puede ver en la Figura 3.8. Página 61
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” Figura 3.6: Ejemplo de mapa soporte objetivo. Como comentamos previamente, nuestro sistema no posee un mapa de carreteras o calles dado que no tenemos la cartografía mundial, por lo que no podemos escoger los cruces entre calles sino que utilizaremos los cruces de rutas. Además, como las rutas no tienen asociado un sentido, los puntos significativos aparecen antes y después de cada cruce. En el proceso de generación de puntos significativos, seleccionamos todos los puntos comunes que hay entre cada par de recorridos. Eso nos permite saber las zonas en las que se unen o bifurcan éstos. Definición 9 (Punto de cruce) Dado el conjunto Rutas ={R1, . . . , Rn}, para cada par de rutas Ri, Rjdefiniremos el conjunto de puntos de cruces que notaremos Página 62
3.3 Nuestra propuesta Figura 3.7: Camino con cuatro desviaciones. como Cruceij =cruceij 1, . . . , cruceij m, siendo cruceij k=latij k, lonij kun punto de cruce cuyas componentes básicas son latitud y longitud. El conjunto de todos los puntos de cruce entre cada par de rutas lo notaremos como sigue: Cruces = {cruce1, . . . , crucem} A partir de los extremos que nos indican las bifurcaciones y uniones, analizamos el tipo de cruce, pudiendo ser extremo-extremo, extremo-punto medio o punto mediopunto medio, indicando los extremos los puntos iniciales o finales y el ‘punto medio’ una zona intermedia del recorrido. Dependiendo del tipo de cruce, se genera por cada uno, desde dos hasta cuatro puntos significativos como podemos ver en la Figura 3.8. Podemos observar como se trata de una matriz simétrica en la que sólo varían cuál es la ruta 1 y cuál la 2, por lo que sólo tenemos cuatro tipos de cruces. Una vez que finaliza este proceso, llamaremos a los puntos significativos seleccionados “candidatos”. 3.3.1.2. Generación de puntos significativos Definición 10 (Punto significativo) Dado el conjunto Cruces, definiremos el conjunto de puntos significativos que notaremos como Significativos = Página 63
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” Figura 3.8: Tipos de cruces entre dos recorridos y sus puntos previos y posteriores. ClusterJerarquico(Cruces) = {sign1, . . . , signm}, siendo signi={lati, loni}el punto resultante de agrupar un conjunto de cruces mediante un cluster jerárquico por distancia umbral media. Dado que estamos analizando los cruces por cada par de recorridos, habrá muchos de ellos en los que el punto candidato se genere prácticamente en el mismo lugar que uno existente ya. Cuando eso ocurre, debemos agruparlos, realizando un cluster de puntos que elimine puntos redundantes y reduzca la complejidad del modelo. Este agrupamiento se representa en la Figura 3.9. Utilizamos para ello un cluster jerárquico con criterio de distancia umbral que indica cuánto de cerca deben estar dos candidatos para considerarse como uno solo. 3.3.1.3. Puntos soporte Definición 11 (Punto soporte) Dados los conjuntos Recorridos ={Rec1, . . . , Recn} ySignificativos ={sign1, . . . , signm}, para cada recorrido Recise observarán los puntos significativos que atraviesa y en qué sentido lo hace (Norte, Sur, Este u Oeste). Dado un punto significativo signi={lati, loni}definiremos un punto soporte y lo notaremos como sopi={lati, loni, orii}de modo que tenga las mismas latitudes Página 64
3.3 Nuestra propuesta Figura 3.9: Operación de agrupamiento de puntos previos y posteriores de un cruce cuando están muy próximos. y longitudes que el punto significativo y además incluya la componente del sentido en el que es atravesado (orii). Como cada punto significativo puede ser atravesado desde uno a cuatro sentidos, por cada punto significativo podrán existir de uno a cuatro puntos soporte. Los puntos significativos, están identificados por una latitud y una longitud. Sin embargo que el receptor GPS indique exactamente esa latitud y longitud resulta complejo por los consabidos problemas de precisión. Debido a ello, se considerarán como círculos centrados en esa posición y con un determinado radio para permitir que un usuario atraviese ese círculo aunque no pase exactamente por su centro. Además, cada círculo significativo, podrá ser atravesado en diferentes sentidos de marcha, por ejemplo un punto puede ser atravesado en sentido norte si utilizamos el camino de ida o sur si utilizamos el de vuelta. Para que la información sea suficientemente significativa, asociamos una de las cuatro direcciones cardinales según sea el sentido de la marcha. Para asociar cada una de las 4 direcciones aplicamos una regla simple: Si la diferencia de latitudes entre los puntos anterior al significativo y éste es mayor que la diferencia de longitudes, escogemos la orientación Norte o Sur dependiendo del resultado de la resta (mayor o menor a cero), en caso contrario asignaremos las Página 65
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” direcciones Este u Oeste considerando el resultado de la resta de longitudes. Orientacion =si (|∆lon|−|∆lat|) >0→ ∆lon > 0→Este ∆lon ≤0→Oeste ≤0→ ∆lat > 0→Norte ∆lat ≤0→Sur En la Figura 3.10 se puede ver un ejemplo de una situación real de puntos soporte. En ella se pueden ver tres segmentos de rutas (una de ellas solapada con otra) que generan un cruce de tipo punto medio - punto medio y que producen ocho puntos soporte, dos por cada punto significativo debido a que existen recorridos que atraviesan en ambas direcciones esas calles. Cada punto está lo suficientemente lejos del cruce para evitar que la imprecisión del sistema GPS indique puntos erróneos. Como cada punto significativo puede ser atravesado en diferentes direcciones, añadimos una etiqueta indicando la dirección de éste y generando así cada uno de los puntos soporte. Para resumir el proceso, ilustramos la generación de puntos soporte en la Figura 3.11. En ella se observan tres recorridos parcialmente solapados. En 1), se marcan como círculos negros las zonas comunes entre cada par de recorridos, en 2) tras analizar los tipos de cruces (todos punto medio - punto medio) se usan estrellas para destacar las zonas posteriores y anteriores a las zonas comunes para posteriormente en 3), realizar el cluster de candidatos cercanos. Finalmente en 4) se observa como para los tres puntos centrales, se generan seis puntos soporte añadiendo sus posibles direcciones. Se ha evitado mostrar otros seis puntos soporte (las 3 estrellas exteriores con dos direcciones cada una) para mejorar la visibilidad de la ilustración. Mostramos también la aplicación del proceso de obtención de puntos soporte sobre un conjunto de estudio real en la Figura 3.12. En ésta puede verse la situación inicial de los puntos GPS que formaban los recorridos de un usuario y los puntos que finalmente generan el mapa soporte. En a) puede observarse el conjunto de todos los puntos GPS etiquetados con la fecha de obtención. En b) se muestran los puntos Página 66
3.3 Nuestra propuesta Figura 3.10: Puntos soporte generados en una situación real soporte obtenidos tras el proceso de generación del mapa. Al reducirse drásticamente el número de puntos, el modelo probabilístico que va a resultar es mucho más ligero. Definición 12 (Mapa soporte) Al conjunto de todos los puntos soporte lo llamaremos “mapa soporte” y lo notaremos como Soporte ={sop1, . . . , sopn}. Las ventajas de este mapa soporte ligero son además de la independencia de cualquier GIS y la posibilidad de hacer predicciones en cualquier lugar que frecuente el usuario, es que dado que no se utilizan mapas cartografiados, se evita el problema de “map-matching”, es decir, el proceso de discernir a qué calle corresponde un determinado punto GPS y que se aborda en los demás trabajos estudiados [SBZS06, Kru08] mediante diversos algoritmos. Página 67
Capítulo 3: Modelo de Markov Oculto sobre “Mapa Soporte” Figura 3.11: Secuencia de generación de puntos soporte. 3.3.2. Generación del modelo Una vez creado el mapa soporte, debemos especificar el modelo de Markov ocul- to que usaremos. En primer lugar debemos decidir el diseño de la estructura, es decir, qué estados hay y cómo están conectados. En segundo lugar asignaremos las probabilidades de transición (A), emisión (B) y estado inicial (π). Como comentamos anteriormente el proceso invisible que queremos obtener es el destino que se pretende alcanzar. Para ello utilizamos las observaciones del proceso visible, es decir, los puntos soporte que nos indicará nuestro receptor GPS cuando pasemos cerca de ellos. A continuación, especificaremos los componentes del modelo de Markov oculto: (Q, V, π, A, B): Q: Nuestros estados corresponden con los lugares hacia los que nos dirigimos en un desplazamiento. Para tener una predicción basada en el histórico de desplazamientos, consideraremos sólo aquellos lugares que visitamos frecuentemente. N será el número de estados. V: Corresponderán con los puntos soporte obtenidos anteriormente compuestos por la localización (latitud, longitud) y la orientación (N, S, E, O). Mserá el número de observaciones. Página 68
3.3 Nuestra propuesta Figura 3.12: Ejemplo gráfico de la drástica reducción en el número de puntos. π={πi}: Contiene la probabilidad del lugar al que nos dirigiremos por primera vez. Normalmente el estado con mayor probabilidad de estado inicial es aquel al que suele dirigirse con más frecuencia, en muchos de los casos se trata del hogar de la persona estudiada. A={aij}: Esta matriz, indicará la probabilidad de que estando en un estado, cambiemos a otro. Es decir, que dirigiéndonos a un destino, cambiemos nuestra ruta para ir hacia otro lugar destino. B={bj(vk)}: Contiene las probabilidades de que dirigiéndonos a un lugar destino, pasemos por un punto de soporte. Una vez explicados los componentes del modelo, es necesario explicar cómo se genera cada uno de ellos. Existen dos posibilidades para ello: Sin datos previos. No disponer de secuencias pasadas de observaciones y los estados a los que corresponden. Sería necesario realizar una estimación inicial de Página 69
Capítulo 4: Similitud de recorridos Un ejemplo aclaratorio de estas cuestiones podemos verlo gráficamente representado en la Figura 4.1. Figura 4.1: Utilidad de tener una similitud entre recorridos. Para conseguir estos objetivos, comenzaremos analizando las variables de los recorridos que podemos usar, a continuación estudiaremos diferentes medidas de similitud propuestas por otros autores y finalmente propondremos nuevas medidas, las cuales son más apropiadas para nuestra aproximación. 4.1. Tipos de variables a comparar Para trabajar con una medida de similitud hemos de tener en cuenta que ésta depende del tipo de representación de los objetos a comparar así como de las características de éstos. Por ello en primer lugar analizaremos las componentes de cada recorrido y después justificaremos las elegidas para nuestros objetivos. Recordamos que cada recorrido del conjunto RecorridosFiltrados se componía de puntos GPS filtrados y éstos a su vez de diferentes atributos: bi=< lati, loni, alti, veli, rumboi, tiempoi, HDOPi, V DOPi, PDOPi>. Con objeto de disminuir el número de componentes del vector n-dimensional, y utilizar aquellas que nos sean útiles en los posteriores desarrollos es necesario hacer una selección de atributos que nos permita alcanzar nuestros objetivos de forma más eficiente. Para esta selección es primordial destacar que en primer lugar nos importa Página 76
4.2 Estado del arte el destino que vamos a alcanzar y en segundo el camino que seguiremos. Como podemos observar, realmente nos interesa la componente espacial del recorrido. Aún así cabría plantearse analizar la componente temporal, es decir el instante en que cada uno de los puntos ha sido obtenido. Sin embargo, esa componente temporal puede ser analizada como atributos del propio recorrido de manera resumida como tiempo de inicio o de fin, ahorrándonos mucha información a comparar. Dado que nuestro interés se centra en el espacio y no en el tiempo, vamos a seleccionar únicamente las componentes de latitud y longitud (la altura la obviamos dado que sería difícil hacer un mismo recorrido a diferentes alturas aunque usásemos un transporte aéreo). Como cada punto bidel recorrido ha sido obtenido en el instante tiempoiy la secuencia se ha obtenido en orden temporal, es decir, tiempoi< tiempoi+1, podemos considerar los recorridos como vectores ordenados en los que cada punto está indexado por su orden de obtención. De ese modo aunque en la metodología hemos definido los puntos de los recorridos con todas sus componentes, para obtener una medida de similitud entre ellos, trabajaremos sólo con las componentes de latitud y longitud. Para simplificar la notación utilizada en este capítulo, notaremos los recorridos como R={R1, . . . , Rn}de los que sólo consideramos sus componentes espaciales. 4.2. Estado del arte Tal y como expone Lin [Lin98] para poder dar una definición formal al concepto intuitivo de la similitud, en primer lugar debemos describir nuestras intuiciones sobre ésta. Así: 1. La similitud entre dos objetos AyBse relaciona con sus elementos en común. Cuantos más componentes compartan AyB, más similares. 2. También se relaciona con sus diferencias. Cuanto más difieran AyB, menos similares. Página 77
Capítulo 4: Similitud de recorridos 3. Se obtendrá la máxima similitud cuando AyBsean idénticos. La similitud es por tanto una cantidad que refleja la relación entre dos objetos, i.e. si λdenota el conjunto de objetos entonces una similitud Ses una aplicación S:λ×λ→R. A partir de estas intuiciones, es posible definir múltiples medidas de similitud dependiendo de la interpretación que se le dé a cada una de ellas. Así, por ejemplo en el trabajo de Cha [Cha07] podemos ver una clasificación de hasta 8 diferentes familias de distancias/similitud. Referente a nuestro trabajo, los objetos sobre los que se defina la similitud, deben ser recorridos. Aún habiendo descartado en el apartado anterior la componente temporal, cabe destacar el trabajo de Michail Vlachos [VKG02] que plantea una interesante medida de similitud basada en el uso del modelo de la subsecuencia común más larga (LCSS) para series temporales de varias dimensiones espaciales. Además se compara con otras propuestas como métricas euclídeas o el Alineamiento Dinámico Temporal (DTW). La medida propuesta, define umbrales de tiempo y espacio que permiten adaptar mejor las series y además incluye funciones de traslaciones para buscar patrones de comportamiento paralelos en espacio y tiempo. La propuesta de Vlachos es genérica por lo que permite comparar series como los trazos generados al escribir una palabra o la grabación de vídeo de los gestos de las manos para expresarse en el lenguaje de los signos. Sin embargo, dado que nuestros datos sólo son de recorridos, definiremos similitudes y distancias adaptadas a nuestro ámbito, sin incluir la variable temporal. Debemos tener en cuenta que para calcular las similitudes entre recorridos, es necesario medir distancias entre puntos de los mismos. Si consideramos los recorridos en un plano, la distancia entre dos puntos x= (x1, . . . , xn)ey= (y1, . . . , yn)puede ser cualquier variante de la distancia Minkowski o norma Lp: dP MK(x, y) = p v u u t n X i=1 |xi−yi|p(4.1) siendo nel número de dimensiones del punto (en nuestro caso n= 2 por tener únicamente las componentes de latitud y longitud) y pel valor de la norma. De Página 78
4.2 Estado del arte ese modo, p= 1 indica la distancia Manhattan, p= 2 la Euclídea, p= +∞la de Chebyshev (con d= 2 también llamada distancia del ajedrez), etc.. Sin embargo, en la práctica, tenemos que calcular distancias en una geometría esférica. Aunque existen diversas soluciones que calculan la distancia geodésica entre dos puntos de una elipsoide, la fórmula que normalmente se utiliza es la de Haverseno que permite conocer la distancia ortodrómica(1) a partir de las latitudes y longitudes de dos puntos x= (xlat, xlon)ey= (ylat, ylon): dHav(x, y) = 2Rarcsin ssin2ylat −xlat 2+ cos φicos φfsin2ylon −xlon 2!, (4.2) siendo Rel radio de curvatura de la tierra en la zona. También es posible utilizar la fórmula de Vincenty [Vin75] que permite obtener una precisión mayor aunque al tratarse de un algoritmo iterativo, resulta más costoso que la de Haverseno. Sin embargo, una exactitud en el rango de centímetros no tiene sentido cuando nuestro sistema GPS produce errores del rango de 5-10 metros. Pasamos a continuación a analizar diversas medidas de similitud propuestas en el estado del arte referidas a recorridos. Para ello las clasificaremos según la representación que se le dé a un punto de dicho recorrido. 4.2.1. Punto como símbolo de alfabeto finito. En los trabajos que destacamos, un punto de un recorrido es representado por un símbolo que forma parte de un conjunto de símbolos finito. Esos símbolos pueden ser una letra o una secuencia de caracteres, pero lo fundamental es que dos puntos son iguales si los símbolos que los representan lo son también. Laasonen [Laa05] realiza comparaciones de recorridos utilizando la red GSM. Los usuarios del estudio integraron en sus móviles un software que guardaba el identificador de la estación base, equivalente a un punto del recorrido, cuando realizaban (1)La distancia ortodrómica es el arco del círculo máximo que une dos puntos. Página 79
Capítulo 4: Similitud de recorridos una transición entre celdas GSM. De ese modo, un recorrido es una secuencia de identificadores de estaciones base. Para comparar recorridos, utilizan técnicas de de extracción textual, emparejando cadenas (los identificadores de las estaciones) y utilizando el algoritmo de la subsecuencia común más larga para definir la similitud: SimLaa(R, S) = |LCSS(R, S)| |S|(4.3) Así, como ejemplo, SimLaa(”abcdef”,”acbdg”) = 3 5. Desde una línea de investigación totalmente diferente, Ningning Hu [HS06] desarrolla una medida de similitud de rutas en Internet definidas. Las rutas en Internet se definen como una secuencia de nodos unidos por unos enlaces de subida o de bajada por lo que su representación en forma de grafo es directa. Cada nodo o punto del recorrido, es representada por el nombre de la máquina. La medida de similitud que utilizan es el ratio entre el número total de enlaces compartidos y el número total de enlaces de las dos rutas. Extrayendo la idea fundamental para que nos sirva como similitud de referencia: SimNin(R, S) = 2∗AristasComunes(R, S) TotalAristas(R, S)(4.4) siendo AristasComunes(R, S)el número de enlaces comunes que tienen las rutas yTotalAristas(R, S)es el número de enlaces totales de ambas rutas, es decir el número de aristas comunes entre el total de aristas. En la Figura 4.2 podemos ver un ejemplo para dos rutas utilizando la anterior aproximación. En este caso la SimNin(s1, s2) = 2∗4 17 =8 17 . Utilizando técnicas de extracción de información textual, Doherty [DGJS06], transforma los ficheros de coordenadas GPS en texto, consultando un servicio de 7 millones de entradas para asignar a cada par longitud-latitud el nombre de la localización más cercana (normalmente el nombre de una calle). Es decir, un recorrido está compuesto por puntos representados por los nombres de las calles más cercanas. Tras este proceso, aplica un modelo de extracción de texto (BM25). Aunque Página 80
4.2 Estado del arte Figura 4.2: Similitud entre rutas de Internet propuesta por Hu. es un enfoque bastante novedoso, los resultados no son aplicables en la mayoría de casos ya que encuentra segmentos de ruta comunes pero el resto es poco parecido en términos de distancias geográficas. 4.2.2. Punto como variable bidimensional (latitud y longitud). Las similitudes que normalmente se utilizan entre recorridos representan los puntos de cada uno como una variable con dos componentes continuas, la latitud y la longitud, normalmente influenciados por la tecnología GPS que provee de esos datos de manera precisa. Esta representación nada tiene que ver con la anterior en la que trabajábamos con símbolos en un alfabeto finito, dado que dos puntos sólo serán iguales si sus atributos (latitud y longitud) coinciden. Teniendo en cuenta que estas variables tienen entre 5 y 10 decimales y la precisión del sistema GPS, la igualdad entre dos puntos no suele darse nunca y lo que es más importante, al tratarse de variables cuantitativas son más adecuadas para un tratamiento más ricos en términos de extracción de conocimiento. Jan [JHP00] utiliza una medida de separación para aquellos recorridos que tienen los puntos iniciales y finales idénticos (considerando un área circular de coincidencia). Crean un índice de desviación de los caminos determinado por el área encerrado entre Página 81
Capítulo 4: Similitud de recorridos los 2 recorridos dividido entre la distancia del camino más corto T(que no tiene porqué ser ninguno de los 2 que se están comparando) al cuadrado: SepJan(R, S, T) = darea(R, S) longitud(T)2(4.5) El problema de esta medida es la necesidad de conocer el camino más corto Tque en su caso era el de menor tiempo recorrido para hallar la desviación entre los recorridos que compartían los inicios y los finales (RyS). Además, para hallar el área encerrada entre ambos recorridos, utilizaban polígonos dibujados a mano donde los lados de los polígonos eran las trazas de los recorridos. Froehlich y Krumm [FK08]computan la distancia mínima de cada uno de los puntos de un recorrido con los segmentos del otro. Eso les hace tener en cuenta las variaciones en la frecuencia de muestreo del GPS. Calculando esta similitud en ambos recorridos y haciendo la media obtienen la medida de distancia. La propuesta se ilustra en la Figura 4.3. Sean R={R1, . . . , Rn}yS={S1, . . . , Sm}dos recorridos Figura 4.3: Ejemplo de la similitud punto-segmento. formados por sus puntos GPS, se define la separación Froehlich entre ellos y se denota SepF ro(R, S)como sigue: SepF ro(R, S) = X i=1,...,n m´ın j=1,...,m−1dP to−segmento(Ri, Sj,j+1),(4.6) Página 82
4.3 Nuestra propuesta donde Sj,j+1 es el segmento determinado por los puntos SjySj+1.Para calcular la distancia dP to−segmento(Ri, Sj,j+1), se halla la distancia Haverseno entre Riy el punto resultante (Sk) de obtener una perpendicular a la recta generada por el segmento Sj,j+1 que pase por Ri. Si Skno pertenece a Sj,j+1, entonces el resultado que se considera es m´ın(dHav(Ri, Sj), dHav(Ri, Sj+1)). Aunque la distancia es más precisa que cuando se utiliza la de punto a punto, la complejidad es mayor. Además en su estudio no se demuestra que ciertamente es una distancia ya que ciertamente no lo es, al no ser simétrica Sep(R, S)6=Sep(S, R). A partir de la anterior separación se define la distancia Froehlich como sigue: DF ro(R, S) = SepF ro(R, S) + SepF ro(S, R) 2,(4.7) la cual ya si es simétrica, pero sigue sin demostrarse que es una distancia. Para decidir si dos recorridos son similares o no, Froehlich establece un umbral de unos 80 metros de diferencia, por encima de la cual, ambos recorridos no serán similares. Sin embargo, esta aproximación tiene una clara limitación ya que si consideramos dos recorridos totalmente paralelos entre sí manteniendo una distancia entre ellos de sólo un metro, la distancia de Froehlich será directamente proporcional al tamaño de los recorridos (concretamente a su número de puntos), por lo que si los recorridos tienen más de 80 puntos cada uno, se indicará que éstos no se parecen, mientras que si son más cortos indicará lo contrario. 4.3. Nuestra propuesta En esta sección plantearemos diferentes medidas de similitud específicas para nuestro problema teniendo en cuenta los trabajos previos estudiados. Comenzaremos definiendo similitudes y separaciones para recorridos finalizados y finalmente propondremos medidas de similitud para comparar recorridos no finalizados con los ya completos. Página 83
Capítulo 4: Similitud de recorridos 4.3.1. Aspectos de las medidas de similitud deseadas Las similitudes que propongamos deben considerar los siguientes aspectos de nuestros datos: 1. Precisión GPS: Aunque realizamos el filtrado de outliers en el preprocesado, nos encontraremos que una misma posición puede ser representada por múltiples puntos GPS diferentes dado que el dispositivo receptor tiene una precisión de varios metros. 2. Independencia del tamaño: Al comparar 2 recorridos su similitud será independiente del tamaño que tengan. Es decir, dos recorridos que se parezcan visualmente desde una perspectiva aérea deberán tener una similitud elevada tengan 100 metros de longitud o 100 kilómetros. 3. Caminos de ida y vuelta: En muchos casos, los recorridos de ida son prácticamente iguales a los recorridos de vuelta, cambiando el sentido de la marcha y existiendo un pequeño desplazamiento espacial dado que se realizan normalmente por diferentes carriles. Permitir una alta similitud entre caminos de ida y vuelta, permitirá reducir los datos almacenados. 4. Diferentes velocidades: Dos recorridos realizados por el mismo camino uno en bicicleta y otro en coche, deben tener una similitud elevada aunque sus velocidades sean completamente diferentes. 5. Pequeñas variaciones de camino: Dos recorridos deben parecerse si comparten gran parte del trayecto aunque durante una parte del mismo utilicen diferentes itinerarios. 4.3.2. Distancia Hausdorff-GPS Desde el ámbito de visión por computador [DR93, Ata83, Sho89, Sho91], la distancia Hausdorff es la más utilizada para medir las diferencias entre dos polígonos. Página 84
4.3 Nuestra propuesta Dado que los recorridos GPS pueden verse como líneas poligonales abiertas, se puede aplicar esta distancia. Un ejemplo de ello puede verse en el trabajo de Morris [MB08] en el que utiliza la distancia Hausdorff para determinar la similitud entre recorridos con inicio y fin definidos y ver si sus algoritmos de detección de caminos rurales a partir de imágenes aéreas y de satélite eran o no correctos. Definición 13 La separación de Hausdorff entre un conjunto de puntos R={R1, . . . , Rn}yS={S1, . . . , Sm}se define como la máxima de las distancias mínimas entre sus puntos y notamos como sigue: SepHff (R, S) = m´ax i=1,...,n m´ın j=1,...,m dP MK(Ri, Sj).(4.8) Dado que no se trata de una función simétrica, suele darse una definición de distancia: DHff = m´ax(SepHff (R, S), SepHff (S, R)).(4.9) Si los conjuntos en vez de puntos son líneas o polígonos, entonces dHff se aplica a todos los puntos de cada una de las líneas o polígonos, no solo los vértices, por lo que tenemos infinitos puntos en vez de un conjunto finito. Uno de los algoritmos que suele usarse para solventar ese problema se describe en el trabajo de Atallah [Ata83]. En nuestro trabajo [AGOV07] propusimos una variación de esta distancia: Definición 14 Dados dos recorridos RyS, se define la separación Hausdorff-GPS entre ellos y se denota por SepH−GP S(R, S), como sigue: SepH−GP S (R, S) = m´ax i=1,··· ,n m´ın j=1,··· ,m dHav(Ri, Sj).(4.10) Lo que significa aplicar la medida de diferencia de Hausdorff entre conjuntos (de ese modo se evita trabajar con infinitos puntos) en geoides utilizando la distancia Haverseno en vez de la de Minkowski. La medida de similitud busca en el conjunto Página 85
Capítulo 4: Similitud de recorridos Figura 4.6: Distancia entre dos caminos como un área. 3. darea(R, S)≥0,(0 ≤∆(R, S)≤1). 4. darea(R, S)≤darea(R, T) + darea(T, S)para cualquier R, S, T ∈R(AB). Esto es claro sin más que pensar que se ha identificado cada camino con una trayectoria (se puede pensar en el plano o en el espacio) o una función. Por tanto R=f1(x) yS=f2(x)y se ha definido darea(S, R) = RB Akf1(x)−f2(x)kdx. El principal inconveniente que presenta en la práctica esta aproximación se encuentra cuando se pretende aplicar este tipo de distancia a dos caminos que aún empezando y finalizando en los mismos lugares, los puntos iniciales y finales validados no coinciden, con lo cual no se obtendría un polígono (las poligonales no se cierran). Sin embargo, esta situación puede ser salvada si previamente se decide, por convenio, tomar los lugares más frecuentados en los caminos como marcas de posiciones y de esta forma se cierra el polígono con la línea que une el anterior punto con el primer punto validado del camino. 4.3.5. Análisis de las diferentes medidas de similitud Para poder analizar la adaptación de las diferentes similitudes/disimilitudes a nuestro problema, generamos la Tabla 4.1 en la que pueden verse las propuestas más destacadas con respecto a las características a analizar: precisión GPS, independencia del tamaño de los recorridos, recorridos de ida y vuelta, diferencia de velocidades y pequeñas desviaciones. Página 92
4.3 Nuestra propuesta Tabla 4.1: Comparación de medidas de similitud entre recorridos Característica Froehlich Hausdorff-GPS Área Jaccard-GPS Precisión No Sí No Sí Tamaño No Sí No Sí Ida y vuelta Sí Sí No Sí Velocidades Sí Sí Sí Sí Desviaciones No No No Sí Podemos observar que tanto en las medidas de Hausdorff-GPS, Froehlich y Área, no disponemos de una normalización, es decir, la medida depende de la magnitud de los recorridos comparados y no será sencillo escoger un umbral por encima del cuál decidir si ambos recorridos son parecidos o no. Imaginemos dos recorridos como los de la Figura 4.7. En ellos podemos intuir una similitud elevada, sin embargo, si los recorridos tienen muchos puntos o son muy largos, las similitudes de Froehlich y del área generarán valores que indicarán poca similitud o mucha distancia. En la medida propuesta por Torkkola o la nuestra de Hausdorff-GPS, dependerá de las distancias máximas entre puntos, por lo que si nos hemos desviado brevemente de nuestro recorrido, se alcanzarán esos máximos y se asumirá una disimilitud total. Sin embargo, con la propuesta de Jaccard-GPS, prácticamente todos los puntos están a una distancia suficiente como para considerarlos equivalentes y por tanto nuestra medida indicará una similitud muy elevada, es decir es robusta frente a pequeñas desviaciones mientras que las demás no lo son. 4.3.6. Similitud entre recorridos no finalizados Las similitudes propuestas hasta ahora consideran que todos los recorridos han finalizado y su objetivo era el de clasificar las diferentes rutas. Sin embargo, ahora nuestro objetivo varía y lo que pretendemos es realizar predicciones. Para ello necesitamos comparar recorridos que no han acabado con aquellos que sí lo han hecho. Al contrario que en el anterior apartado, no existe un estudio sobre este tipo de Página 93
Capítulo 4: Similitud de recorridos Figura 4.7: Ejemplo de dos recorridos comparados con las diferentes disimilitudes estudiadas: a) Hausdorff-GPS, b) Froehlich, c) áreas y d) Jaccard-GPS. similitudes en el estado del arte por lo que plantearemos una medida de similitud que recoja las siguientes características: Últimos datos más importantes. Es lógico considerar que la información más importante es la última recibida, dado que son los puntos GPS más próximos al destino. Recorridos no clasificados. En algunos casos se realizan trayectos que provienen de lugares no indexados pero cuyos destinos sí lo son. Este tipo de trayectos, se suelen adaptar a segmentos de rutas conocidas para llegar al destino. Desde el punto de vista de un conductor o de un transeúnte es lógico que se aproveche el conocimiento de sus rutas pasadas para realizar una composición de éstas y llegar a un destino conocido. Tiempo de fijado. Como ya hemos expuesto, el tiempo de fijado de los satélites por parte del receptor GPS puede ser de pocos segundos, si estamos en condiciones ideales, a varios minutos en caso contrario. En los datos reales detectamos que muchas veces el portador del receptor GPS no esperaba a tener fijados los satélites para comenzar su trayecto por lo que el primer punto vali- Página 94
4.3 Nuestra propuesta dado distaba cientos de metros del origen real. Este aspecto práctico tendremos que tenerlo en cuenta para evitar problemas en nuestras similitudes. Con el fin de alcanzar este objetivo, definiremos una medida con ponderaciones para considerar que la información más importante es la última recibida y una medida de similitud que la utilice. Para conseguir ponderar los últimos puntos por encima de los primeros, definimos la función Ordenα: Definición 24 Dado el recorrido sin finalizar R={R1, R2, . . . , Rm}y el recorrido finalizado S={S1, S2, . . . , Sn}, definimos la función Ordenα(Ri, S) = i si ∃Sjtal que Ri≡αSj 0e.o.c A partir de esa función, podemos obtener la siguiente medida de similitud: Definición 25 Definimos la α-similitud deslizante entre R y S y notamos como SimDα(R, S): SimDα(R, S) = m X i=1 λiOrdenα(Ri, S) donde λison las ponderaciones. En la Figura 4.8 podemos ver dos rutas XeYy cuatro regiones bola de un recorrido parcial Z. Obsérvese que Z3no es equivalente a ninguna región bola de Y yZ4no lo es con ninguna de X. Para esclarecer la representación hemos obviado las regiones bola de los recorridos finalizados. En este caso, el número de regiones bola de Zque intersectan con Xson las mismas que el que intersectan con Y, que son 3. Sin embargo, SimDα(Z, X) = 1 + 2 + 3 + 0 = 6 ySimDα(Z, Y ) = 1 + 2 + 0 + 4 = 7. En este ejemplo se ha considerado λi= 1,∀i Podemos observar que no existe simetría, aunque tampoco es algo importante ya que compararemos un recorrido parcial con todos los finalizados y no al revés. Página 95
Capítulo 4: Similitud de recorridos Figura 4.8: Ejemplo de ruta más cercana deslizante. Si queremos conseguir una medida de similitud como una media aritmética ponderada (combinación convexa) hemos de conseguir que λi≥0ym P i=1 λi= 1. Para ello podemos hacer λi=i m P i=1 i y como m P i=1 i=(m+1)m 2, tenemos: SimDα(R, S) = 1 m P i=1 i m X i=1 i Ordenα(Ri, S) Con esta medida, damos más importancia cuanto mayor sea i, sin embargo la medida no está acotada. Para subsanar ese inconveniente, buscamos otra aproximación para tener la similitud acotada lo cual facilitará su interpretación. Teniendo en cuenta que Ordenα(Ri, S)=0oi, se sigue que considerando los pesos constantes e igual a 2 m(m+1) , se tiene que 0≤ m P i=1 λiOrdenα(Ri, S) = 2 m(m+1) m P i=1 Ordenα(Ri, S)≤ 2 m(m+1) m P i=1 i= 1.De esta forma consideramos una nueva medida de similitud: SimD∗ α(R, S) = 2 m(m+ 1) m X i=1 Ordenα(Ri, S). Con esta medida de similitud, conseguimos destacar lo más importante de nuestro recorrido en curso es decir, la parte final que es la que se aproxima al destino, no a partir de los pesos, sino a través de la función Orden. Evidentemente los pesos Página 96
4.4 Resumen no suman 1 pero no se pierde la naturaleza de la similitud. Esto es lógico ya que se pueden considerar cambios de recorrido, con lo que rápidamente mejorarán aquellos que se parezcan más y empeorarán los que no se parezcan en los últimos puntos. En la Figura 4.9 podemos ver el comportamiento de las similitudes considerando sólo el número de regiones bola que intersectan con los demás caminos y la similitud deslizante. En el primer caso aunque el recorrido parece avanzar tal y como lo hace la ruta B, como hay un mayor tramo de recorrido que se asemeja a la ruta punteada, la mayor similitud sigue siendo con la ruta A. Utilizando el algoritmo de similitud deslizante, cuando el recorrido parcial está ya avanzado, la mayor similitud pasa a ser la ruta B dado que se ponderan más los últimos puntos. Figura 4.9: Ejemplo de funcionamiento de las similitudes Jaccard-GPS y la deslizante. 4.4. Resumen En este capítulo hemos estudiado las medidas de similitud existentes para comparar recorridos. Al no existir ninguna que cubriese totalmente nuestros requisitos, Página 97
Capítulo 4: Similitud de recorridos hemos definido tres similitudes (Hausdorff-GPS, Jaccard-GPS y áreas) adaptadas para los recorridos GPS. Tras comparar sus características comprobamos que la que denominamos Jaccard-GPS es la más apropiada para nuestro objetivo por lo que se seleccionó para aplicarla en el cluster de recorridos. Además, se ha definido una medida de similitud deslizante, útil y necesaria para permitir la comparación de recorridos no finalizados con rutas ya terminadas. Esta similitud es la adecuada para aplicar en predicción debido a que se ponderan los últimos puntos del recorrido parcial en mayor medida que los iniciales, permitiendo determinar la ruta que mejor se adapta y por tanto conocer cuál puede ser su destino más probable. Una vez analizadas las similitudes entre recorridos GPS, pasamos a analizar los resultados obtenidos tanto de extracción de conocimiento como de predicción en el Capítulo 5. Página 98
CAPÍTULO 5 RESULTADOS En este capítulo mostraremos los resultados obtenidos tras aplicar la metodología propuesta en el Capítulo 2. Comenzaremos describiendo el proceso de recogida de datos y los usuarios que participaron en él. A continuación analizaremos los procesos que la componen y estudiaremos las predicciones obtenidas tanto para la técnica de combinación de HMM junto con puntos soporte como para la de aplicación directa de las similitud deslizante. 5.1. Usuarios estudiados En primer lugar, estudiaremos a los participantes que nos proporcionaron los datos fuente. El número de usuarios que colaboraron en el estudio fueron ocho. De ellos, seis aportaron datos con más de una semana de recorridos consecutivos. Los otros dos realizaron muy pocos recorridos y en días sueltos. Observamos que aunque algunos usuarios estuvieron interesados en llevar el GPS para así poder utilizarlo con programas de navegación en vehículos, otros lo consideraban invasivo y poco cómodo y hubiesen preferido integrar el sistema de seguimiento Página 99
Capítulo 5: Resultados en sus terminales móviles. Por otra parte, hay que tener en cuenta que la información suministrada invadía la privacidad por lo que podría haber cierta reticencia a colaborar. Entre los datos privados a los que podemos acceder, se encuentran las zonas que más frecuenta, como la vivienda del usuario o posibles tramos de carretera en los que infringió las normas de tráfico rebasando la velocidad permitida mientras conducía. Deberíamos prestar atención a la legislación vigente(1) en la que se indica que quedan prohibidos los ficheros creados con la finalidad exclusiva de almacenar datos de carácter personal que revelen la ideología, afiliación sindical, religión, creencias, origen racial o étnico, o vida sexual. Prácticamente todos esos datos podrían extraerse de un fichero de las localizaciones si cotejamos los datos con bases de datos geo-localizadas o simplemente si conocemos donde se encuentra la sede de un partido político, lugar de culto, etc.. Dado que los usuarios eran conocidos por el autor no hubo problemas en compartir esa información, pero para evitar problemas, se eliminó cualquier rastro del nombre de los voluntarios para que no fuese posible relacionarlos con los ficheros. Además, existen estudios [Kru07] que demuestran la posibilidad de recuperar un alto porcentaje de los nombres y apellidos de los usuarios que participan en procesos de recogida de trazas GPS, simulando un ataque sobre una base de datos con recorridos. Por ello decidimos mantener la base de datos de manera personal y no publicarla para su uso por otros investigadores. De los seis usuarios con datos suficientes, uno es el autor de este documento y los demás son personas de su entorno cercano. Estas personas tenían diferentes hábitos de desplazamiento tanto por el número de trayectos diarios como por sus horarios, las zonas por las que se desplazaban y los medios de transporte utilizados. Para no revelar sus identidades los nombraremos a partir de ahora con los números del 1 al 6. A continuación los describimos someramente: Usuario 1: Se trata de una persona soltera y con empleo. Sus recorridos más (1)LEY ORGÁNICA 15/1999, de 13 de diciembre, de Protección de Datos de Carácter Personal. Página 100
5.1 Usuarios estudiados frecuentes son los trayectos de la vivienda de sus padres, con los que vivía, hacia su lugar de trabajo (y el camino inverso). Además suele incluir centros comerciales y la vivienda de su pareja, con la que compartió algunos recorridos en coche (ambos llevaban su receptor encendido por lo que sería posible encontrar los trayectos conjuntos). Usuario 2: Comercial casado con empleo. Su patrón de comportamiento es interesante para la predicción de destinos por la variedad de zonas que visita y el número de medios de transporte que utiliza. Usuario 3: Trabajador soltero con pareja. Sus destinos además de la casa de su pareja, son el lugar de trabajo y viviendas de familiares a los que visitaba los fines de semana o en vacaciones. Usuario 4: Trabajador casado. Sus desplazamientos incluían frecuentes situaciones de atasco entre su vivienda, el trabajo de su mujer a la que llevaba diariamente y su lugar de trabajo. Todos sus desplazamientos son en su vehículo e incluyó alguno a la vivienda de sus padres a más de 100 kilómetros de la suya. Usuario 5: Soltero con empleo. Entre sus recorridos se encuentra un periodo de vacaciones y múltiples viajes a diferentes ciudades por lo que resulta de especial interés para el proceso de extracción de destinos. Usuario 6: Estudiante universitario con pareja. Sus constantes desplazamientos a pie y con destinos cercanos entre sí supusieron un interesante desafío para el ajuste de parámetros. Entre sus recorridos aparecen los de sus vacaciones de verano. En la Tabla 5.1 podemos ver algunas características de cada usuario. En ella además de observar el número de días aportados por cada uno, se indican otros datos, como los medios de transporte utilizados y el número de zonas, entendidas como ciudades o pueblos por los que se desplazaron. Página 101
Capítulo 5: Resultados Figura 5.5: Representación del cluster jerárquico modificado aplicado a los puntos finales del usuario 1. extraídos. Para ver las mejoras introducidas por nuestra técnica con respecto a la comúnmente usada (segmentado temporal), mostramos los resultados comparativos de ambas en la Tabla 5.4. En ella para cada usuario se muestran el número de recorridos extraídos gracias al segmentado temporal (primera columna), los obtenidos tras aplicar el segmentado por cercanía a destinos (segunda), la diferencia entre éstos (tercera) y el porcentaje comparando ambos (última columna). Podemos observar cómo el porcentaje de nuevos recorridos gracias al segmentado doble es muy significativo sobre todo en el usuario 4. En su caso se debe al uso común por parte del usuario y su pareja del mismo vehículo, de modo que ambos parten hacia sus respectivos trabajos desde su hogar dejando el primero a su acompañante en su oficina y continuando posteriormente hacia la suya. Si no se realizase el doble segmentado, las predicciones indicarían siempre que el destino es lugar de trabajo del usuario, sin embargo el primer destino es suficientemente significativo como para considerar la parada dado que altera la ruta inicial. Esta situación se repite en los Página 108
5.2 Procesado Tabla 5.4: Diferencia de recorridos generados mediante segmentado temporal y segmentado por cercanía a destinos. Segmentado Nuevos recorridos Usuario temporal destinos Diferencia Porcentaje 1 77 79 2 102.60% 2 233 236 3 101.29% 3 116 120 4 103.45% 4 102 157 55 153.92% 5 498 589 91 118.27% 6 405 445 40 109.88% Total 1431 1626 195 113.63% usuarios 5 y 6 aunque con menor intensidad. Este resultado es significativo dado que se obtienen hasta un 13.63% más de recorridos mediante una técnica simple pero novedosa. Esto es importante para aplicaciones de predicción de tráfico: Si predijésemos directamente el destino final, la consulta sobre la ruta hacia ese destino indicaría un camino diferente al que se usa para pasar previamente por un lugar de encuentro antes de dirigirse al final. 5.2.5. Filtrado de recorridos En este proceso realizamos un filtrado de aquellos recorridos que no nos son útiles para la predicción. En primer lugar eliminamos los que generan un recorrido con inicio y fin en el mismo punto. Entre ellos se incluyen recorridos como paseos o carreras con el mismo origen y destino sin paradas intermedias (en nuestro caso no encontramos este tipo de recorridos) y falsos recorridos, es decir secuencias de puntos que parten y finalizan en el mismo lugar obtenidas al tener encendido el receptor en interiores. Un ejemplo puede verse en la Figura 5.6, donde aparece un falso recorrido por estar el receptor en un edificio techado pero cerca de una ventana. Página 109
Capítulo 5: Resultados Figura 5.6: Ejemplo de falso recorrido generado al recuperar información desde un lugar techado. Además, filtramos aquellos recorridos que no tienen sentido a la hora de las predicciones, es decir, aquellos que finalizan lejos de cualquier destino obtenido en el paso anterior. Este último filtrado puede darse en casos en los que la batería del dispositivo se agota o cuando se accede a lugares visitados menos de tres veces. Este último caso supone una pérdida de información con respecto al conjunto inicial de recorridos, pero debemos recordar que el objetivo es predecir un destino frecuente en un desplazamiento y éste se considerara a partir de tres visitas. Tras filtrar los recorridos obtuvimos los datos que mostramos en la Tabla 5.5. En ella se indica para cada uno de los usuarios el número de recorridos obtenidos tras el doble segmentado, el número de recorridos útiles (columna “Finales”), el porcentaje de recorridos útiles con respecto a los de doble segmentado y los recorridos eliminados por lejanía a destinos extraídos (columna “Distancia”) y los eliminados por comenzar y finalizar en el mismo lugar (columna “Inicio y Fin”). Página 110
5.2 Procesado Tabla 5.5: Resultados de filtrado de recorridos. Filtrado Usuario Recorridos Finales Porcentaje Distancia Inicio y Fin 1 79 53 67.09% 11 15 2 236 48 20.34% 70 118 3 120 84 70.00% 22 14 4 157 126 80.25% 20 11 5 589 308 52.29% 77 204 6 445 305 68.54% 49 91 Total 1626 924 56.83% 249 453 Observando la última fila podemos destacar que aunque el porcentaje de recorridos finales es el 56.83% del total, sólo 249 (un 15.31%) son por pérdida de información, es decir, recorridos válidos pero descartados por no finalizar cerca de un destino. El mayor número de recorridos filtrados 453, el 27.86% son falsos recorridos generados desde el interior de edificios. También podemos observar como para el usuario 2 se pierde un número elevado de recorridos (70, un 29.66%) por no finalizar cerca de los destinos. Tras analizar dichos trayectos filtrados se pudo observar que los había realizado durante periodos vacacionales (verano y navidades), por lo que había muchos recorridos que finalizaban en lugares que se visitaban menos de tres veces. Por otra parte observamos que para los usuarios 2, 5 y 6 también existe un filtrado muy alto por recorridos que comienzan y finalizan en el mismo lugar. Esto se explica por su gestión del receptor GPS: una vez llegaban a un destino techado lo mantenían encendido. Página 111
Capítulo 5: Resultados 5.2.6. Generación de rutas Tras comprobar que otras distancias no eran aplicables a nuestro problema [JHP00, HS06, DGJS06] o era necesario especificar un umbral dependiente del tamaño medio de los recorridos a comparar [FK08] o no eran suficientemente flexibles para nuestro propósito [TZL+07, ZLTG07], para generar las rutas, utilizamos la separación Jaccard-GPS propuesta en la Sección 4.3.3. Con nuestra alternativa permitimos dos niveles de tolerancia: el primero a nivel de puntos y el segundo a nivel de recorridos. A nivel de puntos establecimos el umbral, que indica cuando dos regiones bolas son equivalentes, en 40 metros. Escogimos esa distancia al considerar la situación más desfavorable: dos vehículos que viajen en sentidos opuestos a la máxima velocidad permitida, por los carriles más distantes de una autopista. Esa distancia permite que en los tramos en los que ambos sentidos sean paralelos, se generen regiones bolas equivalentes. En la Figura 5.7 podemos observar los cálculos para una distancia entre carriles de autopistas de 20 metros con una frecuencia de muestreo de 1 Hertzio a máxima velocidad y en el caso de instante de muestreo más desfavorable. Como vemos hasta los 40 metros previstos, existe margen suficiente. A nivel de recorridos, indicamos lo parecido que debían ser dos trayectos para ser considerados como una única ruta. Para permitir una reducción significativa de éstos en rutas escogimos un porcentaje de similitud del 70 % de modo que recorridos que utilizan pequeños desvíos pero comparten gran parte del recorrido siguen perteneciendo a la misma ruta. Además comprobamos que todos los recorridos de un mismo cluster tenían los mismos destinos como extremos. Para comprobar la corrección de la elección de los parámetros también probamos otros valores. En la Figura 5.8 podemos ver cómo evolucionan el número de rutas generadas según varía el parámetro de equivalencia de separación entre recorridos. Se puede observar que con una similitud del 85% (15% de separación) y 100 metros de distancia entre regiones bola equivalentes, obtenemos el mismo número de rutas que para el 70% de similitud (30% de separación) y 40 metros. Página 112
5.2 Procesado Figura 5.7: Cálculo de distancia umbral para la equivalencia de regiones bola. En la Tabla 5.6 mostramos el número de rutas obtenidas utilizando una distancia entre regiones bola de 40 metros y realizando agrupación a partir de una similitud superior al 70 %. Además incluimos una columna que indica el porcentaje de reducción. Podemos observar que la reducción de recorridos a sus rutas representantes es muy importante (60.71 % de media), permitiendo resumir la información almacenada y mejorando su integración en dispositivos móviles. Destacan los resultados extremos de los usuarios 2 y 4. En el primero observamos que no hay una gran reducción de recorridos en rutas mientras que en el segundo podemos agrupar sus recorridos en sólo 17 rutas siendo sólo el 13.49 % del total de recorridos. Para comprobar cómo son sus desplazamientos, comparamos los dendrogramas del usuario 2 y el usuario 1 que tiene un porcentaje de reducción también elevado y un número de recorridos menor que el 4 de modo que su representación gráfica es más clara) y el usuario 2. Podemos verlos en la Figura 5.9 y observamos cómo el primero recorre repetidas veces caminos muy parecidos mientras que el segundo varía bastante más su comportamiento. En el eje de ordenadas se observan los identificadores de cada uno de los recorridos de cada usuario y en el de abscisas Página 113
Capítulo 5: Resultados Figura 5.8: Número de rutas generadas al realizar el cluster jerárquico de recorridos. el índice de separación entre ellos. Figura 5.9: Dendrograma de rutas para el usuario 1 (izquierda) con una reducción del 73.58% en y para el 2 (derecha) con una reducción del 29.17%. 5.3. Predicción Tras el preprocesado de los datos, nos disponemos a analizar los resultados de predicción obtenidos mediante las dos técnicas descritas en los capítulos 3 y 4. Por una parte la predicción mediante el mapa soporte (Sección 3.3.1) y la aplicación del modelo de Markov Oculto (Sección 3.3 y por otra, la aplicación directa de las Página 114
5.3 Predicción Tabla 5.6: Resultados de generación de rutas por cluster jerárquico de recorridos con regiones bola de radio 40 metros y agrupando con similitud superior al 70 %. Usuario Recorridos Rutas Reducción 1 53 14 73.58% 2 48 34 29.17% 3 84 34 59.52% 4 126 17 86.51 % 5 308 161 47.73% 6 305 103 66.23% Total 924 363 60.71% similitudes deslizantes (Sección 4.3.6). 5.3.1. Predicción mediante mapa soporte y HMM En primer lugar, estudiamos el porcentaje de reducción de puntos obtenidos mediante la generación de puntos soporte con respecto al total de puntos tras el preprocesado. Para ello se ha elaborado la Tabla 5.7, en la cual podemos observar la alta reducción de puntos desde la información inicial hasta los puntos soporte, los cuales, recordamos, permiten la generación de un mapa personal. Este es uno de los avances más importantes de nuestras aportaciones dado que en el peor de los casos (Usuario 1) obtenemos una reducción del 96.14 % (3.86% del número de puntos filtrados), lo cual permite generar un mapa personal muy ligero y útil para el usuario en cuestión. En nuestro análisis de las predicciones el criterio usado para validar la predicción de un destino final dado un recorrido parcial, fue una validación cruzada de M-capas sobre el conjunto completo de datos, donde Mse escogió de acuerdo al tamaño de conjunto de datos. El procedimiento se repitió 50 veces para poder asegurar un Página 115
Capítulo 5: Resultados Tabla 5.7: Resultados de la obtención de puntos soporte. Puntos Puntos soporte Usuarios Total Filtrados Número % del total % de los filtrados 1 14884 7871 327 2.20% 3.86% 2 36161 10517 230 0.64% 2.19% 3 161426 57043 397 0.24% 0.96% 4 24099 24011 545 2.26% 2.27% 5 117820 36216 1054 0.89% 2.91% 6 143701 61179 1024 0.71% 1.67% buen comportamiento estadístico y de esta forma evitar comportamientos extraños al considerar valores promedios. En cada recorrido de test, se extrajeron los puntos soporte generados para el 10, 25, 50, 75 y 90 por ciento del trayecto recorrido sobre el total. Los datos de entrenamiento nos permitieron generar un modelo de Markov Oculto y poste riormente, utilizando el Algoritmo de Viterbi [Vit67], obtener el estado más probable (destino) para cada uno de los datos del conjunto de test. Los resultados se muestran en la Tabla 5.8 y en la Figura 5.10. Hemos de señalar que existen dos posibles situaciones de que no ocurran predicciones correctas: predicción incorrecta o imposibilidad de predicción. La primera se da cuando se predice un destino que finalmente no es el correcto. La segunda cuando el recorrido no atraviesa ninguno de los puntos soporte generados en el conjunto de entrenamiento. Así, si en la zona de la predicción existen múltiples cruces de rutas, entonces prácticamente todos los recorridos contendrán puntos soporte, sin embargo, si el transeúnte o conductor realiza un recorrido por una zona en la que sus rutas no se cruzan con otras, puede que su recorrido no pase cerca de ningún punto soporte generado. Esta situación suele solventarse cuando el número de recorridos es mayor ya que es común que se generen más rutas y éstas se traduzcan en puntos soporte. También suele corregirse al aumentar el porcentaje de recorrido parcial atravesado. Página 116
5.3 Predicción Tabla 5.8: Resultados del experimento. Mindica el número de capas en la validación cruzada. Los valores denotan el porcentaje de predicciones correctas. % Recorrido parcial atravesado UsuarioM10% 25% 50% 75% 90% 110 55.85% 66.60% 73.87% 82.55% 85.09% 210 26.98% 47.6% 53.75% 62.5% 66.25% 310 35.89% 50.71% 69.58% 80.89% 85.71% 410 64.8% 80.52 % 89.68 % 93.21 % 93.57 % 5521.98% 34.40% 47.26% 62.06% 72.66% 6521.70% 41.82% 54.31% 65.85% 74.75% Como cabe esperar, podemos ver que según el porcentaje de recorrido atravesado se incrementa, el porcentaje de predicciones correctas mejora considerablemente. Esto resulta lógico debido a que el número de observaciones y cruces es mayor y las probabilidades de predicciones imposibles decrecen. Es importante señalar que aunque los resultados no están todo lo cercano al 100% que nosotros desearíamos de corrección, los últimos puntos soporte obtenidos en el 90 % de los recorridos atravesados están lejos del 90% del recorrido completo, en algunos casos varios kilómetros. Esto es debido al método con el que se han seleccionado los puntos soporte. Esta característica de nuestra aproximación nos permite realizar la predicción con suficiente antelación a la llegada al destino final. Con respecto a los resultados, se puede observar que varían de un usuario a otro. Esto se explica debido a los diferentes patrones de movimientos, la zona en la que se desplazan y el número de lugares frecuentemente visitados por cada usuario. Por ejemplo, aunque existen bastantes más recorridos del usuario 5 y el 6, éstos visitan lugares cercanos entre sí, lo que implica que el número de predicciones correctas se reduzca. También puede observarse que el usuario 4 es el más predecible debido a que utiliza las mismas rutas y el número de destinos finales es pequeño. Página 117
Capítulo 5: Resultados Tabla 5.11: Índice de bondad de las predicciones. Usuario Similitud HMM 1 0.736 0.770 2 0.690 0.584 3 0.733 0.713 4 0.782 0.879 5 0.711 0.552 6 0.699 0.593 Media 0.725 0.682 de similitudes permitía incluir más información espacial (en el HMM sólo incluíamos puntos soporte mientras que en el otro incluíamos todos los puntos de las rutas) y no importaba tanto los datos frecuenciales. Utilizando el índice IP propuesto (ver Sección 2.2.12) obtenemos la Tabla 5.11, donde se puede constatar lo apuntado anteriormente referente a que el método HMM es superior para los usuarios 1 y 4. En la tabla también se ha añadido una fila donde se indica cual es el porcentaje de acierto medio para cada uno de los métodos y se observa que el método de similitud deslizante mejora al HMM. 5.4. Resumen En este capítulo hemos comprobado los resultados de aplicar la metodología off-line propuesta a un conjunto de datos de casi medio millón de puntos geoposicionados mediante el sistema de localización GPS. En cuanto al proceso de extracción de información, es importante resaltar la mejora en el segmentado de recorridos aplicando el método por cercanía a destinos con una mejora media del 13% con respecto a la técnica comúnmente aceptada del segmentado temporal. Página 124
5.4 Resumen Por otra parte, cabe destacar los resultados obtenidos mediante el uso de la combinación de los mapas personales (rutas y puntos soporte) con las dos técnicas de predicción (similitud deslizante y HMM). Concretamente la técnica de similitud utilizando rutas permite una corrección media superior al 50% habiendo recorrido sólo el 10% del recorrido. Aunque los resultados del HMM junto con puntos soporte son relativamente peores en el conjunto de los seis usuarios, observamos que en aquellos usuarios con los hábitos más repetitivos (usuarios 1 y 4) esta regla también se cumple. Una vez obtenidos estos resultados, estamos en disposición de adaptar esta metodología a entornos on-line, es decir entornos en los que tengamos que extraer la información de los mapas personales y realizar predicciones en tiempo real. En el Capítulo 6 veremos esta adaptación a terminales móviles cuyo mayor problema es el reducido tiempo de duración de sus baterías. Página 125
CAPÍTULO 6 PREDICCIÓN ON-LINE En los desarrollos anteriores hemos trabajado con resultados off-line, es decir, primero recuperábamos los datos mediante un receptor GPS y posteriormente los tratábamos en un ordenador. Sin embargo, la utilidad de las aplicaciones para las que están diseñadas nuestras aproximaciones radica en una predicción on-line. En este capítulo explicaremos el proceso seguido para llevar a la práctica esta predicción en un dispositivo móvil e incidiremos sobre las técnicas utilizadas para evitar la interacción con el usuario y reducir el consumo energético del terminal. De ese modo permitiremos utilizar la predicción de destinos de manera transparente y durante el máximo tiempo posible entre cada carga de baterías. 6.1. Estado del arte Para conseguir predicciones en tiempo real es necesario considerar la combinación de un receptor GPS para recoger la información, una CPU capaz de procesar la información y ejecutar el motor de predicciones y una base de datos que almacene la base de conocimiento compuesta por rutas y destinos. Frente a estas restricciones, existen dos soluciones según el lugar en el que se realice la predicción: Página 127
Capítulo 6: Predicción on-line 1. Predicción en el dispositivo. El dispositivo móvil integra tanto el receptor GPS como la CPU y la base de datos. Las características de esta solución son: SGBD poco maduros. La madurez de los sistemas gestores de bases de datos en terminales móviles dista mucho de la de los servidores. La sencillez con la que se implementaban las relaciones entre tablas, los reducidos tipos de datos aceptados y la baja precisión de éstos complica el almacenamiento y gestión de datos referentes al posicionamiento. Capacidad de cálculo limitada: Este aspecto es cada vez menos relevante por el rápido avance de la computación móvil. Sin embargo, el uso intensivo de la CPU del dispositivo incide negativamente en el siguiente punto. Baterías del dispositivo limitadas: Mientras las dos primeras características evolucionan rápidamente, esta tercera no lo hace tanto. Aunque ya han aparecido en el mercado los primeros móviles solares(1), el consumo de baterías del chip GPS incluido en los teléfonos es tal que hace que en pocas horas se agote en prácticamente todos los terminales. 2. Predicción en un servidor. El dispositivo personal integra el receptor GPS y un emisor/receptor inalámbrico para el envío y recepción de la información a un servidor. Éste, almacena la base de conocimiento y ejecuta su motor de predicciones con los datos recibidos. Posteriormente envía al dispositivo la predicción realizada. Los aspectos más relevantes de esta solución son los siguientes: Consumo de baterías. Además del coste obligatorio de obtener los puntos GPS, tal y como tenemos en la primera solución, las baterías del dispositivo se reducen rápidamente debido a las numerosas transmisiones de datos entre dispositivo y servidor, influyendo también su duración. Coste económico. Transmitir cada cierto número de segundos la posición espacial por parte del cliente y recibir la respuesta del servidor supone (1)http://www.reghardware.co.uk/2009/04/20/waterproof_solar_kddi/ Página 128
6.1 Estado del arte transmisiones durante todo el día, lo cual supone evidentemente un coste monetario. Aunque el coste de las transmisiones a través de la red telefónica se ha abaratado en los últimos años(2), puede que los usuarios no estén dispuestos a pagar por este tipo de servicios. Desconfianza sobre la privacidad. El envío de información de localización a un servidor supone dos posibles amenazas a la privacidad: la captura de datos a través del canal inalámbrico y el uso indebido de los datos almacenados en un servidor ajeno al usuario. Aunque estas amenazas pueden prevenirse con una gestión segura de la comunicación y el almacenamiento, el usuario puede desconfiar del tratamiento de su información de localización por parte de terceros. La segunda opción resulta útil en aplicaciones multiusuario como los sistemas de gestión de tráfico o en sistemas que necesitan de CPUs muy potentes. Por ejemplo podemos ver esta alternativa en el trabajo de Patterson [PLG+04] donde el servidor utiliza servicios de localización en tiempo real de los autobuses y de un GIS de la ciudad de Washington para ejecutar el motor de inferencia de predicciones. También podemos comprobarlo en el estudio de Brakatsoulas [BPT04] donde se describe un sistema de gestión de tráfico capaz de detectar situaciones problemáticas en la red de carreteras en Atenas. En el caso particular de la gestión de tráfico, la información del estado de la circulación de vehículos se obtiene de servicios de transportes públicos, coches de policía o vehículos que recorren la ciudad expresamente para medir la densidad del tráfico en tiempo real. Estos vehículos no son privados, por lo que no existen problemas de privacidad cuando se transmiten los datos al servidor dado que no son datos personales. Sin embargo, si consideramos que en vez de vehículos de trabajo, monitorizamos personas en cualquier instante y lugar, la invasión de la intimidad es un problema importante. (2)Yoigo y Orange (en verano de 2009) ofrecen una tarifa plana diaria de 1.2 euros más IVA. Página 129
Capítulo 6: Predicción on-line 6.2. Nuestra propuesta Para conseguir nuestro objetivo, predecir destinos de usuarios, es necesario realizar una monitorización continua de éstos, por lo que aunque el problema del consumo de baterías es un aspecto que debemos asumir, el coste económico y fundamentalmente la falta de privacidad no son aceptables. Dado que deseamos que los usuarios confíen en el servicio de predicción de destinos y que de esa manera lo adopten sin ninguna objeción, la opción elegida en nuestra investigación fue la de integrar todo en el dispositivo móvil preservando la intimidad y reduciendo el gasto económico y energético de las transmisiones inalámbricas. Para comprobar su viabilidad, construimos un prototipo, comprobamos su debilidad en cuanto a duración de baterías y gestionamos el consumo energético basado en el diseño del GPS y el comportamiento en exteriores de los usuarios. 6.2.1. Prototipo Para desarrollar un prototipo capaz de llevar a cabo la predicción de destinos on-line, se utilizó un terminal HTC P3300 que podemos ver en la Figura 6.1. Al intentar implementar las dos técnicas de predicción utilizados en la fase offline, HMM con mapas soporte y similitudes, analizamos dos indicadores para cada uno de ellas: la base de conocimiento inicial necesaria para poder realizar predicciones y el procesado necesario tras finalizar un recorrido. La base de conocimiento inicial nos indica el número de días necesarios para que el sistema comience a ser útil. En la técnica HMM, al estar basada en un mapa soporte, era necesario crearlo previamente. Eso supone tener un número de recorridos elevado para poder generar múltiples cruces entre rutas. El número medio de recorridos para conseguir las primeras predicciones correctas era de unos diez días. Sin embargo, utilizando la técnica de similitudes, una vez que definidos cuales son los destinos frecuentes, con pocos recorridos podríamos predecir los extremos de Página 130
6.2 Nuestra propuesta Figura 6.1: Terminal HTC P3300 utilizado para el prototipo de predicción on-line. éstos. Normalmente a partir del tercer día de desplazamientos ya se comenzaban a tener predicciones correctas. El segundo indicador, el procesado tras el fin de cada recorrido, nos informa de la cantidad de procesamiento necesario que debe realizar la CPU del dispositivo. Para la técnica de HMM y mapas soporte en primer lugar es necesario comprobar si el recorrido pertenece a una ruta antigua o no. A continuación debemos regenerar el mapa soporte revisando cada uno de los nuevos cruces con rutas anteriores y por último volver a crear las matrices de transición y emisión ya que suelen aparecer Página 131
Capítulo 6: Predicción on-line nuevas observaciones o estados. El proceso realizado en un portátil Intel Core 2 Duo P8400 a 2.26GHz y 3GB de memoria RAM utilizando un SGBD SQL Server 2005 tardaba entre 7 y 15 minutos por lo que aunque el procesador del dispositivo fuese potente ese cálculo podría tardar mucho más. Utilizando la técnica de similitud deslizante únicamente era necesario comprobar si el recorrido coincidía con una ruta antigua o era necesario crear otra para representarlo, por lo que el tiempo de procesado era mínimo. Al ser tan desfavorables las condiciones para el modelo de mapas soporte on-line, nos decidimos por el uso de la técnica de similitudes. Desarrollamos una aplicación prototipo que era activada y desactivada por el usuario cada vez que comenzaba un nuevo desplazamiento. La base de datos que utilizaba la aplicación se cargaba previamente utilizando un conjunto de recorridos extraídos de la fase off-line. De ese modo la aplicación simplemente utilizaba el motor de inferencia basado en la base de conocimiento existente para comprobar el tiempo de respuesta del procesador y la corrección de las predicciones. A partir de este trabajo observamos los siguientes hechos: Carga de recorridos. Depender de una recuperación off-line de recorridos para cargarlos en un dispositivo móvil no era una tarea sencilla ni intuitiva, por lo que en la aplicación final, el proceso de recogida y extracción de recorridos y destinos finales debía estar integrado de manera transparente. Interacción por parte del usuario. La activación y desactivación de la aplicación por parte del usuario no era aceptable. Al igual que en el proceso de recuperación de datos de la fase off-line, se producían olvidos. Además, la molestia para el usuario era importante. Respuesta del procesador. Aunque pensamos que podría haber retardo en la aplicación de la técnica de similitudes no fue así y aún recuperando datos GPS a la frecuencia máxima (1Hz) no hubo problemas, la predicción se realizaba cada segundo y se notificaba visualmente al usuario. En este prototipo no nos Página 132
6.2 Nuestra propuesta preocupamos de cuando realizar la notificación pero consideramos que para la aplicación final sería interesante buscar intervalos de predicciones estables (que indicasen el mismo destino) durante al menos un minuto. De lo anterior concluimos que nuestro sistema debía ser transparente al usuario y de ejecución continua, con lo que el problema de baterías se acrecentaría. Para ello en primer lugar definimos un diagrama de procesos para evitar que el usuario interactúase con el sistema y en segundo estudiamos las técnicas de reducción de baterías. 6.2.2. Diagrama de procesos En la metodología estudiada, trabajamos sobre una base de conocimiento estática de recorridos y destinos que no variaba con el tiempo. El reto al que nos enfrentamos ahora es que esa base de conocimiento se incrementa a medida que el usuario realiza sus desplazamientos. Así mismo, desde el primer instante en el que sea posible, se deben emitir predicciones de ruta y destino. A continuación pasamos a describir los aspectos más interesantes del diagrama de procesos que difiere en algunos puntos de la versión off-line. En la Figura 6.2 podemos ver el esquema seguido. Hemos numerado cada uno de los bloques para poder explicarlos fácilmente. Consideramos como punto de partida el estado de fin de recorrido (bloque 1), es decir, el instante en el que el usuario se encuentra en un destino o acaba de llegar a él. El objetivo es detectar un nuevo desplazamiento (bloque 2). El evento que lo dispara es la obtención durante un cierto tiempo (en la implementación se usaron 45 segundos) de un porcentaje suficiente (nosotros escogimos el 90%) de puntos válidos con HDOP menor que 6 que supusiesen una distancia recorrida de 50 metros. Una vez detectado, se van almacenando todos los puntos válidos tras aplicar los filtrados de distancia, velocidad y precisión. Al mismo tiempo, se aplican las técnicas de predicción para emitir conjeturas sobre la futura ruta seguida y el destino final Página 133