Algoritmo de aprendizaje incremental para agrupar y clasificar running trails

Abstract

Es habitual entre los aficionados al running, buscar rutas en alguna zona de interés. Hay herramientas que permiten hacer este tipo de búsquedas, filtrando por distancia, locación, etc. No obstante, una vez aplicados todos los filtros aparecen rutas duplicados o muy similares, creando así mucha entropía y dificultando el proceso de búsqueda. En este trabajo se propone hacer un agrupamiento de rutas para identificar aquellas que son únicas en una zona determinada. Se propone usar un algoritmo basado en k-means incremental que agrupe las rutas disponibles, y posteriormente en un momento indeterminado en el tiempo, dada una nueva ruta ingresada al sistema, decide si esta debe ser asignada a un cluster ya creado debido a su similitud con las rutas que lo conformen, o se debe crear un nuevo cluster ya la ruta es lo suficientemente distante a las demás. En este trabajo se estudiará la mejor manera de representar las variables de una ruta, considerando feature engineering y técnicas de reducción de dimensionalidad que facilite y mejore los resultados del algoritmo de agrupamiento. Así mismo, se estudiarán los efectos sobre el rendimiento y las medidas de error intra e Inter grupos al considerar diferentes valores de threshold. Al final se espera entregar un aplicativo que permita visualizar las rutas únicas, filtrarlas, introducir nuevas rutas y ver información relacionada como: duración, elevación, distancia, velocidad promedio, entre otras.

It is common among running fans look for trails in some location of interest. There are tools that allow runners to do this kind of searches, filtering by distance, location, etc. However, once all the filters are applied, the result is duplicated trails or very similar ones, creating a lot of entropy and hindering the process. In this work it is proposed to make a grouping of trails to identify those that are unique in a given area. It is proposed to use an algorithm based on incremental k-means that clusters the available running trails, and later at some moment in time, given a new trail entered into the system, decides whether it should be assigned to a cluster already created due to its similarity with the trails that make it up, or a new cluster must be created since the trail is distant enough from the others. In this work it is studied the best way to represent the variables of a running trail, considering feature engineering and dimensionality reduction techniques that facilitate and improve the results of the clustering algorithm. Likewise, the effects on performance and intra and intergroup error measures will be studied when considering different threshold values. In the end, it is expected to deploy an application that allows viewing the unique routes, filtering them, introducing new routes and seeing related information such as: duration, elevation, distance, average speed, among others.

És habitual entre els aficionats al running, buscar rutes en alguna zona d'interès. Hi ha eines que permeten fer aquest tipus de cerques, filtrant per distància, localització, etc. No obstant això, una vegada aplicats tots els filtres apareixen rutes duplicades o molt similars, creant així molta entropia i dificultant el procés de cerca. En aquest treball es proposa fer un agrupament de rutes per a identificar aquelles que són úniques en una zona determinada. Es proposa usar un algorisme basat en k-means incremental que agrupi les rutes disponibles, i posteriorment en un moment indeterminat en el temps, donada una nova ruta ingressada al sistema, decideix si aquesta ha de ser assignada a un clúster ja creat a causa de la seva similitud amb les rutes que el conformin, o s'ha de crear un nou clúster ja la ruta és prou distant a les altres. En aquest treball s'estudiarà la millor manera de representar les variables d'una ruta, considerant feature engineering i tècniques de reducció de dimensionalitat que faciliti i millori els resultats de l'algorisme d'agrupament. Així mateix, s'estudiaran els efectes sobre el rendiment i les mesures d'error en considerar diferents valors de threshold. Al final s'espera lliurar un aplicatiu que permeti visualitzar les rutes úniques, filtrar-les, introduir noves rutes i veure informació relacionada com: durada, elevació, distància, velocitat mitjana, entre d'altres.