Verbesserte geographische Joins in RapidMiner

(English version)

Update 2020-02: GIS-Funktionalität ist jetzt als Erweiterung verfügbar.

Ich habe früher beschrieben, wie geographische Joins und Filter in RapidMiner mit Hilfe des Cartesian-Product-Operators umgesetzt werden. Dieser Ansatz ist relativ einfach nachvollziehbar und funktioniert mit kleinen Datenmengen ganz gut.

Leider wird bei einem Cartesian Join jede Zeile der beiden hineingehenden Datensätze miteinander kombiniert. Das Ergebnis des kartesischen Produkts hat dann so viele Zeilen wie das Produkt der beiden Datensatzlängen. Natürlich wird da viel Speicher verwendet, und die Schleife mit den gewünschten Berechnungen läuft länger.

Für größere Datenmengen mit jeweils Hunderten oder Tausenden von Zeilen gibt es einen besseren Ansatz. Der Script-Operator kann auch zwei ExampleSets verarbeiten. Mit einem etwas komplexeren Skript kann der Prozess in einer verschachtelten Schleife beliebige Join-Kriterien anwenden, ohne den Speicher mit einem temporären kartesischen Produkt zu belasten.

In diesem Beispielprozess hole ich von Open Data Wien eine Liste von über 28.000 Straßenabschnitten in Wien (als Linien) sowie die 23 Wiener Bezirke (als Flächen). Die Aufgabe ist, für jeden Bezirk die Straßen zu bestimmen, die in ihm liegen. Dafür wird die GeoScript-Funktion contains() verwendet.

Bei der Cartesian-Join-Methode werden für jede Zeile zwei als String gespeicherte Geo-Objekte konvertiert. Dies ist aufwändig, aber kaum zu vermeiden. Mit der verbesserten Methode ist es einfach, ein Array von konvertierten Geo-Objekten zu erstellen und indexbasiert abzufragen.

Das Ergebnis ist ein Prozess, der mit relativ geringen Speicher-Anforderungen und einer akzeptablen Geschwindigkeit auch größere Datenmengen verknüpfen kann.

Der Nachteil ist ein etwas komplexeres Skript, das jedoch nach der ersten Entwicklung leicht an neue Anforderungen angepaßt werden kann.

Der größere Aufwand lohnt sich aber auf jeden Fall. Der Beispielprozess ordnet auf meinem Rechner die 28.309 Straßen den 23 Bezirken in ca. 14 Sekunden zu. Ein versuchsweise erstellter alternativer Prozess, der mit Cartesian Join arbeitet, läuft über 20 Minuten, also fast 90 mal langsamer, und braucht dabei natürlich deutlich mehr Speicher.

Das Skript erstellt ein komplett neues ExampleSet, das alle Attribute aus den beiden hereinkommenden ExampleSets übernimmt (doppelte Attributnamen sollten vorher korrigiert werden). Das Ergebnis enthält nur die Datensätze, auf die die Bedingung zutrifft, es ist kein nachgeschalteter Filter notwendig.

Um das Skript möglichst wiederverwendbar/flexibel zu machen, werden alle prozess-spezifischen Teile am Anfang als Variablen konfiguriert. Das sind einerseits die Namen der beteiligten Attribute, andererseits aber auch die Join-Funktion. Da Groovy sogenannte Closures (Funktionsvariablen) anbietet, können wir am Anfang des Skripts die verwendete Funktion eingeben – die hier konfigurierte Funktion wird später im Join verwendet.

Konkret sieht die Definition so aus:


def joinFunc = { a1, a2 -> a1.contains(a2) }

Das bedeutet: eine Funktionsvariable namens joinFunc mit den Parametern a1 und a2 erstellen. Hinter dem -> erscheint der Inhalt der Funktion, in diesem Fall der Aufruf a1.contains(a2). Der Rückgabewert sollte ein Boolean sein; beim Rückgabewert True werden die beteiligten Zeilen ins Ergebnis ausgegeben. Der fixe Teil des Skripts ruft dann irgendwo in der Schleife die Funktion mit joinFunc(a1, a2) auf.

Diese Konstruktion hilft uns, das Skript einfacher wiederzuverwenden: Sollten wir einmal statt contains() etwa intersects() benötigen, braucht nur der Konfigurationsblock geändert zu werden. Wir müssen nicht mehr nach dem Funktionsaufruf irgendwo in den Tiefen des Skripts zu suchen.

Geographic joins in RapidMiner, improved

Update 2020-02: GIS functionality is now available in an extension.

Earlier I described geographic joins and filters in RapidMiner. The processes used the Cartesian Product operator. This approach is quite simple and easy to understand, and it works well with smaller data sets.

Cartesian Join combines each row of the incoming tables. The result has as many rows as the number of rows of both data sets multiplied together. This uses a lot of memory and the loop that calculates the results takes longer.

There‘s a better approach for larger data sets with hundreds or thousands of rows. The Execute Script operator can work with two incoming ExampleSets. A slightly more complex script can use nested loops to apply almost arbitrary join criteria on the data, without filling the memory with the cartesian product.

This example process fetches over 28,000 street segments as lines and 23 districts of Vienna as polygons from the Vienna Open Data server. The task is finding the streets inside each district. So this is a join based on the GeoScript function contains().

The Cartesian Join needs to convert two strings to Geometry objects in each line of the combined data set. This is slow and hard to avoid. The improved method makes it easy to create an array of converted Geometry objects and use them for further lookups.

The resulting process uses less memory and has an acceptable runtime even with large inputs. This comes at the cost of a more complex script; however, it should be easy to change the script for future requirements.

The effort is really worth it. On my computer the example process joins 28,309 streets with 23 districts in about 14 seconds. A variant of the process that uses Cartesian Join runs for over 20 minutes (about 90 times slower) and uses a lot more memory.

The script creates a new ExampleSet that combines all attributes of both incoming ExampleSets. (If you have duplicate attribute names, rename them before sending the data to the script.) The result contains only records that match the condition, no additional filtering is necessary.

In order to make the script as reusable as possible, all process specific parts are configured at the top in variables. There are variables for the join attributes‘ names and also for the join function. Groovy offers so-called Closures (function variables), so we can specify the function to use in the configuration block. The configured function will be used for joining later in the loop.

This is how the definition looks like:


def joinFunc = { a1, a2 -> a1.contains(a2) }

Translated: create a function variable called joinFunc created with parameters a1 and a2. The body of the function is specified after ->, in this case a1.contains(a2). The return value of the function should be a Boolean – if the value is True, the current rows will be put into the result example set.

The fixed part of the script calls this function using joinFunc(a1, a2) later in the loop.

With this construction we can reuse the script easily: If we need intersects() instead of contains() at some point in the future, we just change it in the script configuration, without having to analyze and change the code below.