Vergleich von Parkraumdaten

Der Abgleich und die Verschneidung unterschiedlicher Datenquellen ist das tägliche Brot des Datenwisschenschaftlers. Wir haben uns die Aufgabe gestellt, Inhalte der interaktiven Karte mit Inhalten von OpenStreetMap abzugleichen.Wir tun das hier am Beispiel der Parkraum-Inhalte der interaktiven Karte mit den Inhalten von OpenStreetMap. Ziel ist es Datenlücken zu identifizieren und einen Prozess zu etablieren, der uns dabei hilft, die Aktualisierungsaufwände von Parkraumdaten zu minimieren.

Die Zuordnung der Parkplätze aus den Vergleichsdatensätzen zu Parkplätzen der Interaktiven Karte erfolgt anhand zweier Kriterien

• Entfernung

• Namensgleichheit bzw. Namensähnlichkeit

Die Vergleichsdatensätze enthalten nicht immer Namen. Vor allem bei den OSM-Daten sind Parkplätze mit Namen eher die Ausnahme. Für diese Parkplätze erfolgt die Zuordnung ausschließlich über die Entfernung.

Alle Quelldaten liegen in EPSG:4326 vor. Zur Bestimmung der Entfernung werden die Daten zuerst nach EPSG:25832 konvertiert.

Im folgenden wird das Vorgehen grob beschrieben. Die detaillierte Beschreibung kann auf Anfrage zur Verfügung gestellt werden.

Der Python-Source-Code kann auf Gitlab heruntergeladen werden: https://gitlab.com/verkehrsverbund-rhein-neckar/Parkraumdaten/-/tree/master/osm-abgleich

Namensvergleich

Der Namensvergleich wird für alle Parkplätze des Vergleichsdatensatzes durchgeführt, die einen Namen haben und sich innerhalb eines Umkreises von 150 m Entfernung um einen Parkplatz der interaktiven Karte befinden, der ebenfalls einen Namen hat.

Wenn eine Seite keinen Namen hat wird der Ähnlichkeitswert auf -1 gesetzt.
Für den Namensvergleich arbeiten wir ausschließlich mit in Kleinbuchstaben (lower case) übersetzten Werten.
Der Namensvergleich basiert auf einer Ähnlichkeitsanalyse mithilfe der python-Bibliothek difflib, die als Ergebnis einen Wert zwischen 0 und 1 zurückgibt:

• 0 bedeutet keine Ähnlichkeit

• 1 bedeutet Gleichheit

Die difflib arbeitet dabei wie folgt:

SequenceMatcher is a flexible class for comparing pairs of sequences of any type, so long as the sequence elements are hashable. The basic algorithm predates, and is a little fancier than, an algorithm published in the late 1980’s by Ratcliff and Obershelp under the hyperbolic name “gestalt pattern matching”. The basic idea is to find the longest contiguous matching subsequence that contains no “junk” elements (R-O doesn’t address junk). The same idea is then applied recursively to the pieces of the sequences to the left and to the right of the matching subsequence. This does not yield minimal edit sequences, but does tend to yield matches that “look right” to people.

SequenceMatcher tries to compute a "human-friendly diff" between two sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the longest contiguous & junk-free matching subsequence. That's what catches peoples' eyes. The Windows(tm) windiff has another interesting notion, pairing up elements that appear uniquely in each sequence. That, and the method here, appear to yield more intuitive difference reports than does diff. This method appears to be the least vulnerable to syncing up on blocks of "junk lines", though (like blank lines in ordinary text files, or maybe "<P>" lines in HTML files). That may be because this is the only method of the 3 that has a concept of "junk" <wink>.

Dieser Ähnlichkeitberechnung haben wir folgende Schritte vorangestellt:

Zunächst werden von beiden Namen allgemeine Wörter entfernt (im Moment: "Tiefgarage", "Parkplatz", "Parkhaus", "Parkgarage", "Hauptbahnhof", "Bahnhof", "Schwimmbad")

Die verbleibenden Namensbestandteile werden verglichen.

• Ist einer der beiden Namen länger als fünf Zeichen und im anderen Namen enthalten, wird die Längendifferenz
  geprüft:

  • Sind beide Namen gleich lang erfolgt keine weitere Untersuchung und das Ergebnis ist 1.

  • Sonst berechnen wir das Verhältnis zwischen Längendifferenz und Länge des kürzeren Namens.

    • Ist dieses kleiner als 1, vergleichen wir die zuvor aus dem Namen entfernten Begriffe und legen für die möglichen Kombinationen folgende Ergebniswerte fest:

      • gleiche Begriffe: 1.0

      • Tiefgarage und Parkgarage: 0.8

      • Parkhaus und Parkgarage: 0.8

      • Tiefgarage und Parkhaus: 0.3

      • alle übrigen Kombinationen: 0.0

    • Ist das Verhältnis gleich 1, wird als Ergebnis 0.9 festgesetzt.

    • Ist das Verhältnis zwischen 1 (exklusive) und 2 (inklusive) wird als Ergebnis 0.7 festgesetzt.

• Wenn keine der vorgenannten Bedingungen zutrifft, wird der Ähnlichkeitswert per difflib berechnet.

Selektion

Kandidaten sind zunächst alle Objekte aus dem Vergleichsdatensatz, die sich in einem Umkreis von 150 m um das Objekt aus dem Referenzdatensatz befinden.
Für die Zuordnung zu einem Parkplatz der Interaktiven Karte wird höchstens einer der Kandidaten ausgewählt.

Vorauswahl

Die nachfolgenden Filterbedingungen werden auf die Kandidaten angewendet, um eine Vorauswahl zu treffen. Solange die Vorauswahl leer ist, wird die jeweils nächste
(schwächere) Bedingung angewendet. Sobald die Vorauswahl mindestens ein Element enthält, ist dieser Schritt abgeschlossen. Die Vorauswahl enthält also entweder kein
Objekt, ein Objekt oder mehrere Objekte, die dieselbe Bedingung erfüllen.

• Entfernung ist 0 m und Ähnlichkeitswert ist 1 oder kleiner als 0

• Ähnlichkeitswert ist 1 und Entfernung <= 150 m

• Entfernung ist 0 m

• Entfernung ist < 5 m und Ähnlichkeitswert ist größer als 0.7 oder kleiner als 0

• Kandidat mit der kürzesten Entfernung, wenn diese kleiner ist als die zweitkürzeste Entfernung und

  • Entfernung ist <= 50 m und

  • Ähnlichkeitswert ist größer als 0.7 oder kleiner als 0

Endauswahl

Enthält die Vorauswahl mehrere Kandidaten, wird der Kandidat mit der kürzesten Entfernung gerwählt, wenn die kürzeste Entfernung kleiner ist als die zweitkürzeste
Entfernung, sonst keiner.
Ist die Auswahl leer, gibt es zu dem Parkplatz der Interaktiven Karte keine Entsprechung im Vergleichsdatensatz.

Mehrfachzuordnungen

Da wir den Vergleich für jeden der Punkte aus der Interaktiven Karte separat durchführen, kommt es in einigen Fällen zu Mehrfachtreffern zwischen verschiedenen
Punkten der Interaktiven Karte und demselben Objekt im Vergleichsdatensatz.

Priorität für nicht zugeordnete Objekte aus dem Vergleichsdatensatz

Nicht zugeordnete Parkplätze der Vergleichsdatensätze sind mit dem zusätzlichen Attribut “priority” versehen. Dieses hat entweder den Wert 2 oder den Wert 3. Priorität 2 erhalten alle nicht zugeordneten Parkplätze, die sich - entweder in einem Umkreis von 400 m um eine zentrale Haltestelle befinden - oder in einem Umkreis von 200 m um eine sonstige Haltestelle liegen.