Detailansicht
Improving the Cold Start Problem in personalized routing with geographic feature extraction
Leon Preusker
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Geowissenschaften, Geographie und Astronomie
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Kartographie und Geoinformation
Betreuer*in
Mina Karimi
DOI
10.25365/thesis.81753
URN
urn:nbn:at:at-ubw:1-11332.55497.267854-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Beim personalisierten Routing geht es darum, einem Nutzer die Route zwischen zwei Punkten zu empfehlen, die dieser als die beste erachtet. Während sich traditionelle Routingalgorithmen vor allem auf die Ermittlung des kürzesten Weges konzentrierten, berücksichtigt personalisiertes Routing, dass der kürzeste Weg in der Realität nicht unbedingt der beste Weg sein muss und dass sich die Vorstellung davon, was als am besten gilt, von Nutzer zu Nutzer unterscheidet. Ziel dieser Arbeit ist es, auf Grundlage der vorhandenen Literatur, insbesondere des Behavior-based Route Recommendation (BR2) Frameworks, einen Algorithmus für personalisiertes Routing zu entwickeln und zu erweitern. Dieser Algorithmus berechnet nutzer- und zeitabhängige Gewichte für einen Straßengraphen auf der Grundlage eines Datensatzes von Nutzern und deren bisher zurückgelegten Routen. Dabei werden die Verhaltenshäufigkeiten der Nutzer berechnet, d. h. wie oft sie sich zu einer bestimmten Tageszeit auf einem bestimmten Straßenabschnitt aufgehalten haben. Wir erweitern diese Berechnungen, indem wir auch die geografischen Eigenschaften der Straßenabschnitte berücksichtigen, um die Verhaltenshäufigkeiten zu schätzen. Dies wird getan, weil das Cold-Start Problem im ursprünglichen Framework sehr signifikant ist, was bedeutet, dass viele Verhalten eine geschätzte Häufigkeit von 0 haben. Wir nutzen die geografischen Eigenschaften der zugehörigen Straßenabschnitte, um die sog. Geographic Peer Frequencies (GPFs) zu berechnen, d.h., wir verwenden die vorhandenen Verhaltenshäufigkeiten geografisch ähnlicher Straßenabschnitte, um die fehlenden Häufigkeiten zu ermitteln. Wir gehen davon aus, dass die Verwendung von GPFs das Cold-Start Problem mindert und folglich die Precision und Recall des Algorithmus verbessert. Es werden mehrere Techniken zur Berechnung der GPFs in Betracht gezogen und es wird untersucht, welche zu der größten Verbesserung bei Precision und Recall führt. Wir untersuchen zudem, welche Kombination geografischer Eigenschaften bei der Berechnung der GPFs berücksichtigt werden sollte. Unsere experimentelle Auswertung zeigte im Vergleich zum ursprünglichen Modell leichte Steigerungen bei Precision und Recall. Die Berücksichtigung des nächsten geografisch ähnlichen Straßenabschnitts führt zu den größten Verbesserungen. Wir haben die folgenden geografischen Eigenschaften berücksichtigt: Straßentyp, Radweginfrastruktur, Straßenbelag, Vorhandensein von Ampeln, Verkehrsberuhigung, Steigung, angrenzende Landschaftselemente und angrenzende Gewässer. Die geografischen Daten wurden hauptsächlich aus OpenStreetMap (OSM) extrahiert und durch Open Government Data ergänzt. Wir berücksichtigen außerdem zwei weitere Aspekte im Zusammenhang mit personalisiertem Routing: Staus und Umwege. Hinsichtlich Staus wird untersucht, wie gut sich der Verkehr über das gesamte Straßennetz verteilen würde, wenn jeder Nutzer den Routenempfehlungen des Frameworks folgen würde. Hinsichtlich der Umwege wird untersucht, um wie viel länger die empfohlene Route im Vergleich zur historischen Route ist und ob diese zusätzliche Länge akzeptabel ist. Wir vergleichen unser Framework sowohl mit dem ursprünglichen BR2 Framework als auch mit traditionellem kürzesten Weg-Routing hinsichtlich Staus und Umwege. Es wurde festgestellt, dass personalisiertes Routing die Stausituation tatsächlich verschlimmert und die Verwendung der GPFs diese zusätzlich in geringem Maße verschlimmert. Andererseits wurde auch festgestellt, dass personalisiertes Routing im Vergleich zur ursprünglichen Route nicht zu übermäßigen Umleitungen führten. Aspekte bezüglich der Implementierung und des Data Handling des Frameworks werden in dieser Arbeit ebenfalls berücksichtigt. Zum Trainieren des Frameworks wurden zwei Sätze von GPS-Daten verwendet: der CyclePhilly- Datensatz aus Philadelphia, USA, und der Geolife- Datensatz aus Peking, China. Der Geolife-Datensatz wurde auch in der ursprünglichen BR2-Veröffentlichung verwendet, was direkte Vergleiche hinsichtlich Precision und Recall ermöglichte. Das Data Handling wurde im Vergleich zur ursprünglichen Veröffentlichung erweitert und das Herausfiltern verschiedener Verkehrsmittel sowie unausgewogener Nutzer miteinbezogen. Es wurde ein einfaches Demonstrationsprogramm des Frameworks erstellt, das eine Visualisierung und Überprüfung der empfohlenen Routen ermöglicht und weitere Einblicke in das Routing-Verhalten lieferte. Wir hoffen, dass diese Arbeit zu einem besseren Verständnis darüber beiträgt, wie geografische Daten zur Verbesserung des personalisierten Routings im Allgemeinen und zur Verringerung des Cold-Start Problems in personalisiertem Routing im Besonderen genutzt werden können, und dass die Methoden, die zu Verbesserungen bei Precision und Recall führen, für weitere Forschungsarbeiten in Betracht gezogen werden können.
Abstract
(Englisch)
Personalized routing is the task of recommending a user the route between two points they will consider the best. Although traditional routing has been mostly concerned with finding the shortest path, personalized routing recognizes that the shortest path might not necessarily be the best path in a real world scenario, and that what is considered best changes from user to user. This thesis aims to develop and expand an algorithm for personalized routing based on the existing literature, specifically the Behavior-based Route Recommendation (BR2) framework. This algorithm calculates user and time specific weights for a road graph, based on a dataset of users and their past taken routes, by considering the user’s behavior frequencies, meaning how often they were at a certain road segment at a specific time of the day. We expand upon this by also considering the geographic properties of the road segments to estimate these behavior frequencies. This is done because the cold start problem is very significant in the original framework, which means many behaviors will have a frequency of 0. We use the geographic properties of the related road segments to compute Geographic Peer Frequencies (GPFs), meaning that we use the existing behavior frequencies of geographically similar road segments to calculate the missing frequencies. We hypothesize that using GPFs will alleviate the cold start problem and consequently will improve the precision and recall of the algorithm. We consider several techniques to calculate the GPFs and investigate which leads to the biggest improvement in precision and recall. We also consider what combination of geographic properties should be considered to calculate the GPFs. Our experimental evaluation showed slight increases in precision and recall compared to the original model. Considering the closest geographically similar road segment leads to the biggest improvements. We considered the following geographic properties: road type, cycleway infrastructure, road surface type, presence of traffic signals, traffic calmness, slope, adjacent landscape features and adjacent water features. The geographic properties were extracted mainly from OpenStreetMap (OSM) and enhanced with some Open Government Data. We also consider two other aspects related to personalized routing, congestion and diversion. Congestion considers how well traffic would spread over the entire road network if every user follows the route recommendations. Diversion looks at how much longer the recommended route is in relation to the original route, and if that amount of extra length is acceptable. We compare our framework to both the original framework and traditional shortest path routing in terms of congestion and diversion. We found that personalized routing actually worsens congestion, and using the GPFs worsens it additionally by a small degree. On the other hand, we also found that our personalized routing methods did not lead to excessive diversions compared to the original route. Surrounding aspects concerning the implementation and data handling are also considered in this thesis. Two sets of GPS trajectories were used to train this framework: the CyclePhilly dataset from Philadelphia, USA and the Geolife dataset from Beijing, China. The Geolife dataset was also used in the original BR2 paper, enabling direct comparisons in precision and recall. We expanded the data preprocessing step compared to the original paper and included filtering out different modes of transportation and unbalanced users. A simple demonstration program of the framework was created which allowed a visualization and inspection of recommended routes and gave further insights into the routing behavior. We hope this thesis will contribute to an understanding of how to use geographic data to improve personalized routing in general, to lessen the cold start problem in personalized routing in particular, and that the methods that lead to improvements in precision and recall can be considered for further research.
Schlagwörter
Schlagwörter
(Deutsch)
Routing Cold Start Problem Personalisiertes Routing Empfehlungssysteme Random Walk with Restart OpenStreetMap Straßengraphen
Schlagwörter
(Englisch)
Routing Cold Start Problem Personalized Routing Recommendation Systems Random Walk with Restart OpenStreetMap Road Networks
Autor*innen
Leon Preusker
Haupttitel (Englisch)
Improving the Cold Start Problem in personalized routing with geographic feature extraction
Paralleltitel (Deutsch)
Verbesserung des Cold Start Problems bei personalisiertem Routing durch die Extraktion geografischer Features
Publikationsjahr
2026
Umfangsangabe
64 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Mina Karimi
Klassifikation
74 Geographie > 74.48 Geoinformationssysteme
AC Nummer
AC17973929
Utheses ID
81075
Studienkennzahl
UA | 066 | 856 | |