Benzinpreise vorhersagen: Effizientes, maschinelles Lernen für Sparfüchse
Nicht erst seit der hohen Inflation weiß man, dass es sich lohnt, Spritpreise zu vergleichen. Zwischen einzelnen Tankstellen können die Preise merklich schwanken, weshalb uns Tank-Apps helfen, die günstigsten zu finden. Zudem empfehlen uns Automobilclubs regelmäßig besondere Tageszeiten zum Tanken. Doch gelten diese empfohlenen Zeiten immer für alle circa 14.500 Tankstellen in Deutschland? In diesem Artikel erkläre ich mein Hobbyprojekt, das mittels maschinellen Lernens vorhersagen kann, wie sich der Spritpreis an einer Tankstelle entwickeln wird.
Das klingt nicht schwierig, irgendwas mit Deep Learning wird's schon richten. Jedoch gibt es einige Herausforderungen, die gegen Deep Learning sprechen und andere Lernverfahren wesentlich interessanter machen. Deshalb wird in diesem Artikel der Fokus vor allem auf der Auswahl sowie praktischen Anwendung dieser Verfahren liegen, da einige Kniffe erforderlich sind, um das Maximum an Performance mit geringer Rechenleistung zu erreichen.
Timing beim Tanken ist alles
Ich gebe zu: Ich bin ein Sparfuchs. Genau deshalb möchte ich meinen Pkw immer möglichst günstig betanken und keinen Cent zu viel bezahlen. Neben der Wahl der Tankstelle spielt auch die Uhrzeit eine Rolle, da zu verschiedenen Tageszeiten Tankstellen deutliche Preisunterschiede aufweisen.
Leider senken nicht alle Tankstellen in Deutschland zum Beispiel um 16:36 Uhr immer den Preis (siehe Abbildung 1), sondern jede Tankstelle scheint einem eigenen Muster zu folgen. Für Tankstellen in meiner Nähe kenne ich diese Muster, aber bei anderen Tankstellen nicht, etwa im Urlaub. Deshalb hatte ich schon öfter das Problem, dass ich getankt habe und kurze Zeit später der Preis gesenkt wurde - hätte ich das nur vorher gewusst!
Als Informatiker habe ich mir ein Hobbyprojekt überlegt, in dem ich eine Software entwickle, die mir für eine Tankstelle vorhersagen können soll, ob sich der Spritpreis innerhalb der nächsten 30 Minuten ändern wird. Und das soll nicht nur für eine Tankstelle, sondern für alle circa 14.500 aktiven Tankstellen in Deutschland mit den drei wesentlichen Treibstoffsorten Diesel, E5 und E10 funktionieren.
Die Software soll dabei potenziell viele Nutzer mit den Infos versorgen können. Aber da es ein Hobbyprojekt zu minimalen Kosten werden soll, darf hier das klassische Kiwi-Prinzip(öffnet im neuen Fenster) (Kill it with Iron: Wenn Performance schlecht, dann pack noch mehr Hardware dazu) nicht genutzt werden. Das Gleiche gilt übrigens auch für Cloudlösungen, die je nach Skalierung schnell ins Geld gehen können. Insofern ist klar, dass eine hohe Geschwindigkeit nur durch Algorithmik und Softwareoptimierungen erreicht werden kann, was zugegeben viel mehr Spaß macht.
Teile und herrsche (Nr. 1)
Was sich erstmal einfach anhört, hat bei näherer Betrachtung unzählige Facetten. Wie soll die Gesamtarchitektur aussehen? Lieber klassische Serverapplikation oder Serverless? Wie sieht die Datenbank im Hintergrund aus? In welcher Programmiersprache soll es geschrieben werden, und welche Frameworks nutzt man? Wie kann ich als Nutzer über ein ansprechendes Frontend die ganze Funktionalität am besten nutzen?
Die einzelnen Funktionen werden von mir als (Micro-)Services entwickelt, wofür ich in Java auf Quarkus(öffnet im neuen Fenster) zurückgreife. Viele davon sind aber noch gar nicht fertig implementiert, da es ein umfangreiches Unterfangen ist. Deshalb liegt der Artikelfokus auf dem für mich spannendsten Teil, dem maschinellen Lernen und damit insbesondere dem Training und der Inferenz der Spritpreisprognose. Denn wann eine Tankstelle ihren Preis ändern wird, ist nicht direkt bekannt, sondern das Verhalten muss anhand von Daten gelernt werden, um es vorhersagen zu können.
Dabei entsteht schon die erste Frage: Woher kommen eigentlich die Spritpreisdaten? Seit Ende 2013 gibt es die Markttransparenzstelle für Kraftstoffe (MTS-K)(öffnet im neuen Fenster) , an die alle öffentlichen Tankstellen in Deutschland innerhalb eines kurzen Zeitfensters ihre Spritpreisänderungen melden müssen. Die MTS-K bietet dafür eine kostenfreie API an, die überraschenderweise gut dokumentiert(öffnet im neuen Fenster) und die Grundlage nahezu jeder heutigen Tank-App ist.
Ärgerlicherweise bekommt man den API-Zugriff aber erst nach einer recht umfassenden, tiefgehenden Beschreibung des geplanten Vorhabens, in der es auch um Wirtschaftlichkeitsaspekte geht. Für mein Hobbyprojekt ist das zu viel bürokratischer Aufwand. Jedoch gibt es mit Tankerkoenig.de(öffnet im neuen Fenster) auch einen Spritpreisvergleich, der die Daten als Open Data unter einer Creative-Commons-Lizenz zur Verfügung stellt - sowohl in Form täglicher Datenbankdumps als auch mit begrenztem Echtzeitzugriff über eine eigene API. Gegen Geld sind dort auch unbeschränkte API-Zugriffe möglich.
Datenbank aufsetzen
Ausgangspunkt meiner Software ist eine zentrale Datenhaltung in Form einer Datenbank. Klar, ich könnte jetzt die ungewöhnlichsten Datenbanksysteme der Welt ausprobieren, aber am Ende entscheide ich mich für PostgreSQL(öffnet im neuen Fenster) .
Zum einen ist das relationale Datenbankschema ziemlich simpel: Es gibt eine Relation Tankstelle , die die Daten jeder Tankstelle speichert, und eine Relation Preise , die alle Preisänderungen mit der Tankstellen-ID als Fremdschlüssel sowie einem Zeitstempel speichert. Zum anderen hat PostgreSQL eine für mich bessere Open-Source-Lizenz, wohingegen der frühere Marktführer MySQL bei einer möglichen kommerziellen Nutzung lizenztechnisch kniffliger ist.
Ein weiteres Schmankerl von PostgreSQL ist die Geospatial-Erweiterung PostGIS(öffnet im neuen Fenster) . Da Nutzer aufgrund einer Ortsangabe Tankstellen in der Nähe finden wollen, braucht die Software eine effiziente Möglichkeit, diese zu finden. Die Tankstellen sind mit Adressangaben sowie Geokoordinaten in der Datenbank gespeichert. Dank des in PostGIS integrierten R-Baums(öffnet im neuen Fenster) als Geospatial-Index können so schnell und effizient die Tankstellen rund um eine Geokoordinate gefunden werden, so dass ich mir jedes Mal einen aufwendigen Full Table Scan sparen kann.
Um die Datenbank zu befüllen, schreibe ich mir zwei Services. Der eine importiert regelmäßig die Datenbankdumps von Tankerkoenig.de(öffnet im neuen Fenster) , der andere nutzt die kostenfreie Echtzeit-API, um alle fünf Minuten für die Tankstellen um meinen Wohn- und Arbeitsort die Preise abzufragen.
Auch um den Entwicklungsaufwand beherrschbar zu halten, konzentriere ich mich damit erst mal auf 44 Tankstellen. Da ich zumindest einen Teil davon kenne, kann ich auch leichter gelernte Muster validieren.
Die Abbildung 2 zeigt die Entwicklung der Anzahl der bei der MTS-K registrierten Tankstellen. Diese scheint interessanterweise nicht abzunehmen, sprich auch nicht mehr existente Tankstellen verbleiben in der Datenbank. Aber man erkennt, dass selbst innerhalb eines Monats regelmäßig neue Tankstellen entstehen. Das wird noch von hoher Bedeutung sein.
Warum Deep Learning diesmal keine gute Idee ist
Nachdem die relevanten Daten in der Datenbank liegen, kann es zum spannenden Teil kommen: Training und Inferenz. In Abbildung 3 ist die angedachte Verwendung des Vorhersagemodells dargestellt.
Als Nutzer wähle ich die für mich interessante Tankstelle, die relevante Spritsorte und erhalte als Ergebnis die erwartete Preisänderung innerhalb der nächsten 30 Minuten. 30 Minuten habe ich deshalb gewählt, weil es einerseits ein noch verlässlicher Vorhersagezeitraum ist. Andererseits möchte ich mein Tankvorhaben nicht um Stunden verschieben, sondern nur zeitnahe Preisänderungen berücksichtigen.
Die Vorhersage erfolgt durch das trainierte Modell. Neben der gewählten Tankstelle und der Spritsorte soll dieses Modell grundsätzlich auch auf die aktuelle Uhrzeit sowie alle vergangenen Preisänderungen anderer Tankstellen zurückgreifen können. Die Uhrzeit ist deshalb relevant, weil Tankstellen auch in Abhängigkeit der Tageszeit den Preis verändern. Die Preisänderungen anderer Tankstellen sind dagegen wichtig, weil Tankstellen in der Nähe immer relativ zeitgleich ihre Preise anpassen und somit Änderungen der Konkurrenz kontern.
Bleibt nur die Frage, wie man zum trainierten Modell kommt
Natürlich könnte ich einfach die aktuellen und vergangenen Preisdaten aller 14.500 Tankstellen in Deutschland nehmen, dazu vielleicht noch die Geokoordinaten der Tankstellen sowie die Uhrzeit, und dies alles in ein tiefes, neuronales Netz als Regressionsfunktion kippen. Dabei müssen die Tankstellen, um deren individuelle Methodik zur Preisanpassung berücksichtigen zu können, per One-Hot Encoding(öffnet im neuen Fenster) durchnummeriert werden, da keine natürliche Ordnung über die Tankstellen existiert.
Dies hat sehr viele Eingangsneuronen zur Folge, macht das Netz groß und damit das Training sehr aufwendig. Zudem vermute ich, dass die gleichzeitige Inferenz vieler Preisvorhersagen auch nur mit entsprechender Hardware schnell ist, womit ich wieder ein Problem mit dem KIWI-Prinzip habe.
Ein noch viel größeres Problem ist aber die Dynamik der Tankstellenlandschaft und die damit einhergehenden Tücken von maschinellem Lernen auf Datenströmen. So ist zu vermuten, dass einzelne Tankstellen, etwa durch einen Betreiberwechsel, ihre Methodik zur Preisanpassung verändern und damit die gelernten Zusammenhänge nicht mehr stimmen ( Concept Drift bzw. Shift(öffnet im neuen Fenster) ).
Das mag für eine singuläre Tankstelle recht unwahrscheinlich sein, aber bei größeren Anzahlen von Entitäten können solche Ereignisse durchaus wahrscheinlich werden, wie Google auch schon mal bei einem Serverproblem bemerkte . Zudem öffnen, wie bereits gezeigt, auch ab und zu neue Tankstellen und andere schließen, so dass das Modell an die geänderten Tankstellen angepasst werden muss.
Im Grunde müsste das Modell eigentlich ständig neu trainiert werden, was bei einem sehr rechenintensiven Verfahren wie Deep Learning bei geringer Hardwareleistung zum Problem wird.
Teile und herrsche (Nr. 2)
Ich vermute, dass das tiefe neuronale Netz durch das One-Hot-Encoding in Wirklichkeit nicht ein generalistisches Modell darstellen wird, sondern quasi pro Tankstelle ein Submodell beinhaltet, das sich durch die Aktivierung geringer Teile der Neuronen ergibt. Der Vorteil eines so großen Modells, sehr komplexe Zusammenhänge abbilden zu können, würde damit gar nicht zum Tragen kommen.
Warum trainiere ich also nicht einfach pro Tankstelle ein eigenes Modell? Möglich wäre es, jedoch bieten nicht alle Tankstellen alle drei Spritsorten an. Die Methodiken zur Preisanpassung können sich deshalb auch je nach Spritsorte unterscheiden, so dass ich nicht nur pro Tankstelle ein Modell brauche, sondern auch pro Spritsorte. Bei knapp 14.500 aktiven Tankstellen und drei Spritsorten ergäbe das 43.500 Modelle, aber da eben nicht alle Tankstellen alles anbieten, runde ich auf 40.000 Modelle ab.
40.000 Modelle zu trainieren, klingt für mich erstmal nach einem Wahnsinn, der viel Rechenleistung erfordert. Bei näherer Betrachtung zeigt sich aber, dass das gar nicht so sein muss.
Da jedes Modell genau eine Tankstelle und eine Spritsorte abdeckt, sinkt der Trainingsaufwand beträchtlich. Denn für eine Tankstelle sind nur die anderen Tankstellen in unmittelbarer Nähe relevant und deren aktuelle Preise kann ich schnell bestimmen. Das hält den Eingabevektor fürs Modell kompakt.
Das Modell wird zudem relativ schnell trainierbar sein, da es insgesamt sehr klein sein kann. Der größte Vorteil ist aber die unschlagbare Flexibilität. Eine neue Tankstelle wurde eröffnet? Kein Problem, ich trainiere jeweils ein Modell für diese und alle Tankstellen in der Nähe. Eine Tankstelle wurde geschlossen oder bietet eine Spritsorte nicht mehr an? Auch kein Thema, ich lösche überflüssige Modelle und trainiere die Modelle der Tankstelle in der Nähe neu.
Dies lässt sich alles sehr einfach automatisieren und ist überhaupt kein Vergleich zum Neutrainieren eines tiefen, neuronalen Netzes, das alle Tankstellen berücksichtigen muss.
Maschinelles Lernen auf Datenströmen als Schlüssel
Jedoch muss ich noch Concept Drifts/Shifts erkennen bzw. kompensieren, die sich durch die Veränderung der Methodik zur Preisanpassung einer Tankstelle ergeben können. Interessanterweise gibt es auch eine wissenschaftliche Community, die sich mit dem temporalen, maschinellen Lernen auf Datenströmen beschäftigt und so angepasste Lernverfahren hervorbringt, die sich sehr schnell an geänderte Zusammenhänge anpassen können.
Das Grundprinzip dieser Verfahren zur Adaption an geänderte Zusammenhänge ist immer mehr oder weniger das gleiche: Sie implementieren eine Technik, um vergessen zu können. Dabei werden die Modelle häufig kontinuierlich neu trainiert, sobald ein neues Datum vorliegt.
So können diese Modelle dann etwa nur die n neuesten Daten berücksichtigen ("Windowing", wie in Abb. 4 dargestellt), oder sie arbeiten mit einer Gewichtung, die ältere Daten als unwichtiger als neuere Daten erscheinen lässt.
Je nachdem, wie klein man das Window oder die Gewichtungsverteilung definiert, variiert das "Gedächtnis" des Modells und versetzt es in die Lage, schneller neue Zusammenhänge zu erkennen. Allerdings kann ein Modell bei zu kurzem Gedächtnis auch empfindlicher gegenüber Rauschen werden und schneller vermeintlich neue Zusammenhänge erkennen, die es gar nicht gibt.
Spannend ist zudem, dass typische Ansätze des klassischen maschinellen Lernens für die temporale Variante nicht mehr gelten. Die Unterteilung eines Datensatzes in Trainings-, Validierungs- und Testdaten in der Entwicklungsphase ist nicht mehr erforderlich. Da das Modell auf einem Datenstrom arbeitet, sagt es immer nur den nächsten Wert voraus. Da der tatsächliche nächste Wert aber mit dem nächsten Datum des Datenstroms bekannt wird, wird dieses Datum automatisch Teil des Trainingsdatensatzes.
Das temporale Modell kann also kontinuierlich auf Basis der ehemaligen Vorhersagen lernen und so seine Güte verbessern. Dies führt übrigens dazu, dass klassische Metriken zur Performancemessung nicht mehr gut funktionieren, weshalb es etwa von (Cohen's) Kappa(öffnet im neuen Fenster) mittlerweile auch eine temporale Variante(öffnet im neuen Fenster) gibt.
Programmschleife mit kontinuierlich neu gelernten Modellen
Wenn ich alle Ideen zusammenfüge, ergibt sich die wesentliche Programmschleife aus der Abbildung. Diese wird alle zehn Minuten wiederholt und aktualisiert die Prognosen für die Preisentwicklung der nächsten dreißig Minuten. Dazu werden zu Beginn die aktuellen Preise für alle Tankstellen aus der Datenbank in den RAM geladen.
Innerhalb des Programms habe ich einen Cache-Service integriert, damit nicht ständig über JDBC die Datenbank angefragt werden muss, sondern stattdessen die Werte schnell aus einer internen Map bereitgestellt werden können. Anschließend wird nacheinander jedes Modell einer Tankstelle und Spritsorte vom Dateisystem geladen und anhand des aktuellen Preises an dieser Tankstelle das Modell weiter trainiert. Dieses Modell wird anschließend wieder persistent gespeichert und eine Preisvorhersage für die nächsten 30 Minuten bestimmt, die wiederum gecacht wird.
Zehn Minuten klingen als Schleifendauer erst einmal lang, sind aber tatsächlich ziemlich kurz. Denn innerhalb dieser 600 Sekunden müssen 40.000 Modelle aktualisiert und zur Preisprognose genutzt werden. Das sind gerade mal 15 Millisekunden pro Modell, wenn ich eine Parallelisierung außen vorlasse.
Natürlich könnte ich die Modelle nur on demand aktualisieren, also immer dann, wenn eine Preisvorhersage angefragt wird. Jedoch reichen aufgrund der Umkreissuche nach Tankstellen schon relativ wenige, über Deutschland verteilte parallele Anfragen, um einen Großteil der Tankstellen anzufragen.
Zudem ist die Stärke des maschinellen Lernens auf Datenströmen, dass ich ständig die Modelle aktualisieren kann. Wird ein Modell nur sehr selten benötigt, hätte das zur Folge, dass ich alle Preisänderungen seit der letzten Abfrage dieses Modell rekonstruieren und aus der Datenbank abfragen müsste, was wieder einiges an Zeit kostet.
Insofern ist es einfacher, wenngleich auch bei geringer Nutzerzahl rechenaufwendiger, einfach ständig alle Modelle zu aktualisieren. Klar ist aber auch, dass das Training und die Inferenz deshalb sehr schnell ablaufen müssen.
Die Wahl des Lernverfahrens
Ich implementiere die Programmschleife in Java auf Basis von Java 13. Die Wahl fällt auf Java vor allem aufgrund der Verfügbarkeit der exzellenten Open-Source-Bibliothek Machine Learning for Data Streams (MOA)(öffnet im neuen Fenster) , die von den Machern des ML-Frameworks Weka(öffnet im neuen Fenster) stammt. MOA beinhaltet unzählige temporale, maschinelle Lernverfahren sowie passende Hilfsfunktionen zur Datenbereitstellung und Performancemessung, so dass hier schnell passende Modelle für die Tankstellen trainiert werden können.
Innerhalb von MOA gibt es unzählige Regressions-, aber auch Klassifikationsverfahren. Klassifikatoren sind zumeist leichter und schneller trainierbar, da sie nur zwischen einer endlichen Zahl von Klassen entscheiden müssen. Sie können deshalb den Parameterraum gut separieren und müssen kein aufwendiges Fitting berechnen.
Deshalb betrachte ich die Preisvorhersage als Klassifikationsproblem. Anstatt einen konkreten Preis vorherzusagen, soll der Klassifikator die Änderungshöhe des Preises prognostizieren, wobei jeder Cent Änderung einer Klasse entspricht. Prädiziert er etwa die Klasse -3, so wird eine Preissenkung um 3 Cent pro Liter vorhergesagt. Da Preissprünge um mehr als 10 Cent selten sind, sind die größten Preisänderungen +/- 10 Cent, so dass sich inklusive einer Änderung um 0 Cent insgesamt 21 Klassen ergeben.
Um das richtige Lernverfahren zu wählen, trainiere ich zahlreiche MOA-Klassifikatoren und vergleiche sie anhand der Daten meiner 44 Tankstellen (siehe Tabelle). Der Großteil der Verfahren basiert auf Entscheidungsbäumen, was nicht überrascht, da sie häufig einen guten Kompromiss aus Vorhersagegüte und Trainingsdauer bieten.
Das von der Performance her beste Verfahren ist Ozaboostadwin mit aktivierter Sammeloption mit einer Prognosegüte von 86,05 Prozent. Jedoch ist es verhältnismäßig langsam zu trainieren und erzeugt sehr große Modelle. Stattdessen wähle ich den Limattclassifier, der genauso wie Ozaboostadwin zu den Ensemble-Klassifikatoren gehört, indem er mehrere Entscheidungsbäume parallel nutzt und über Mehrheitsentscheid die Klasse bestimmt.
Dazu nutzen beide Verfahren Adwin als Algorithmus zur Änderungserkennung, der beim Erkennen einer Änderung des Modellzusammenhangs den schlechtesten Baum entfernt und einen neuen trainiert. Der Limattclassifier ist mit 84,415 Prozent ähnlich gut, wenngleich die Kappa-Werte als Performancemaß leicht schlechter sind. Dafür ist er aber schneller trainierbar und ein Modell mit im Durchschnitt 2,5 MB deutlich speicherschonender.
Oft liegt der Klassifikator übrigens nur um eine oder zwei Klassen daneben, so dass die vorhergesagte Preistendenz (steigt, sinkt, bleibt gleich) in über 90 Prozent der Fälle korrekt ist.
Dauer der Programmschleife
40.000 Modelle innerhalb von zehn Minuten zu aktualisieren, ist selbst mit den extrem schnellen Bäumen eine Herausforderung. Allein alle Modelle parallel im Speicher zu halten, würde etwa 100 GByte RAM erfordern, die ich nicht habe. Damit bleibt nichts anderes übrig, als die gelernten Modelle in jedem Zyklus zu persistieren, wofür MOA auch Writer-Klassen anbietet.
Jedoch sind diese relativ langsam und auch das Wiederherstellen dauert. Besser wäre es, die Objekte, die die Modelle repräsentieren, zu serialisieren und wieder zu deserialisieren, jedoch ist die Java-Standardvariante dafür ziemlich langsam.
Deshalb nutze ich Protostuff(öffnet im neuen Fenster) , eine Java-Implementierung von Googles Protobuf-Protokoll, um die Modelle zu persistieren und wieder in den Speicher zu laden. Zu (de-)serialisieren ist damit sehr schnell, je nach Größe des Java-Objekts liegt der Geschwindigkeitsvorteil zur Java-Standardvariante bei Faktor 15-20.
Auf meinem Entwicklungsrechner, einem 2018er Laptop mit Intel Core i3-6006U mit 2 GHz Takt und 8 GByte RAM, dauern das Deserialisieren eines Modells, das Aktualisieren von diesem, die Vorhersage des nächsten Preises sowie das anschließende Serialisieren mit der Java 13 Runtime ca. 107 ms auf einem Kern. Mit GraalVM sind es 100 ms, also leicht schneller.
Ein CPU-Kern könnte in den zehn Minuten also ca. 6.000 Modelle verarbeiten und da sich diese Berechnung gut parallelisieren lässt, reichen sieben CPU-Kerne aus, um die Zehn-Minuten-Zyklen permanent zu halten.
Ich habe zudem mit einer Kompression der serialisierten Modelle im RAM experimentiert, jedoch brachte dies keine Geschwindigkeitsvorteile, da I/O selbst ohne memory-mapped files kein limitierender Faktor ist. Hätte ich einen Hardwarewunsch frei, würde ich sehr viel RAM bestellen. Denn der zeitaufwendigste Teil der Programmschleife ist trotz hoher Softwareeffizienz das (De-)Serialisieren, das ca. zwei Drittel der Gesamtzeit erfordert. Könnte ich alle Modelle gleichzeitig im RAM halten, wäre das nicht mehr erforderlich.
Andreas Meier beschäftigt sich seit über 20 Jahren mit Künstlicher Intelligenz (KI) und verantwortet heute KI-Anwendungen bei einem Automobilhersteller