Schlagwort-Archive: Loop

Simulation mit RapidMiner

(English version)

Die Simulation von mathematisch beschreibbaren Prozessen ist für viele Anwendungen nützlich. Die „Monte-Carlo-Simulation“ ist eine elegante Methode, verschiedene Probleme zu lösen, etwa die Berechnung der Kreiszahl Pi.

RapidMiner wird zwar nicht unbedingt als Simulationswerkzeug beworben, aber auch diese Aufgabe läßt sich mit etwas Know-How leicht darin lösen. Und was liegt näher als die „Monte-Carlo-Simulation“ am Beispiel von (französischem) Roulette zu demonstrieren?

Roulette läßt sich einfach beschreiben: Die Spieler setzen auf verschiedene Bereiche eines Tisches. Diese Bereiche decken unterschiedlich große Teile des Zahlenraums zwischen 0 und 36 ab. Die Wahrscheinlichkeit, daß ein Zahlenfeld gewinnt, liegt bei 1/37; bei größeren Bereichen (z. B. vier Zahlen, sechs Zahlen, ein Drittel der Zahlen von 1-36, eine Farbe) bei Mehrfachen davon. Der Gewinn ist bei einzelnen Zahlen das 35-Fache des Einsatzes (zusätzlich zum Einsatz, den man behält), und nimmt bei größeren Bereichen proportional zum Risiko ab. Z. B. erhält man, wenn man etwa auf Rot gesetzt hat und die Kugel auf einem roten Feld landet, den Einsatz noch einmal zurück. Da auch das Feld 0 existiert, das von den meisten möglichen Einsätzen nicht abgedeckt ist, verdient die Bank auch manchmal Geld. Roulette ist wahrscheinlich das „fairste“ reine Glücksspiel, das man spielen kann. (Deswegen gibt es wohl auch „Amerikanisches Roulette“ mit einem zweiten Null-Feld – Die Kasinos in den USA haben sich mit 1/37 Gewinn nicht zufriedengegeben.)

Simulationsprozess

Der hier verfügbare Prozess simuliert wiederholte Besuche im Kasino mit einigen Einstellungen. Die Einstellungen lassen sich im Prozesskontext (View/Show Panel/Context) in Form von Makros setzen. Sie sind auch direkt im Prozess beschrieben.

Man legt die Anzahl der Besuche fest und die Anzahl der Spiele pro Besuch (solange man noch Geld übrig hat). Es läßt sich auch ein Betrag angeben, bei dessen Erreichen man freiwillig aufhört zu spielen. (Z. B. wenn man das anfängliche Guthaben verdoppelt hat.)

Die eigene Spielweise läßt sich im Makro „Risk“ einstellen. Hier legt man das gewünschte Risiko fest: von 2 (rot/schwarz, gerade/ungerade, 1-18/19-36) bis 36 (einzelne Zahl).

Der Prozess besteht aus zwei verschachtelten Schleifen (Loop Visits und Loop Bets) und danach etwas Datenaufbereitung für die Darstellung der Ergebnisse.

Die tatsächliche Berechnung einer Spielrunde findet in „Calculate bet results“ (Generate Attributes) statt. Aus dem Einsatz und dem Risiko wird der Gewinn (Einsatz + gewonnener Betrag) oder der Verlust (der Einsatz) berechnet; daraus dann das neue Spielguthaben.

Nach der Ausführung der äußeren Schleife werden Kennzahlen errechnet.

Aggregierte Ergebnisse der Simulation
Aggregierte Ergebnisse der Simulation

average(VisitWonPct): Anteil des Einsatzes, der durchschnittlich gewonnen oder verloren wurde. (Realistischerweise eher verloren, ausgedrückt durch eine negative Zahl.)

average(VisitReachedGoal): Anteil der Casino-Besuche, bei denen man das Ziel-Guthaben (z. B. 150 € bei einem Anfangsguthaben von 100 €) erreicht hat.

average(VisitLostEverything): Anteil der Casino-Besuche, bei denen man das gesamte Anfangsguthaben verloren hat.

average(VisitWonAmount): Durchschnittlich gewonnener oder verlorener Betrag.

Zusätzlich lassen sich die Verläufe der einzelnen Besuche grafisch darstellen:

Grafische Darstellung der einzelnen Spielverläufe
Grafische Darstellung der einzelnen Spielverläufe

Dafür habe ich das Ergebnis „Pivot for series plot“ geöffnet, die Charts aktiviert, den Chart-Typ Series ausgewählt, die BetNr als Index-Dimension festgelegt und alle CurrentAmount-Spalten für die Plot Series markiert.

Jede Linie zeigt den Verlauf eines Casinobesuchs (pro Besuch eine Farbe). Die X-Achse ist die Spielrunde, die Y-Achse das Guthaben, das man nach dieser Runde hat. Es ist gut sichtbar, daß es Besuche gab, in denen man über 30 Runden nur verloren hat! Oben ist das Feld durch die Besuche begrenzt, in denen man vor Ablauf der geplanten Spielrunden den Zielbetrag erreicht hat.

Mit diesem Simulationsprozess, der auch mit RapidMiner Studio Basic (gratis und ohne Registrierung nutzbar) funktioniert, läßt sich gut feststellen, wie die Chancen im Casino stehen, wenn man mit einer „Strategie“ spielt. Wenig überraschend ist das Ergebnis überwiegend negativ.

Der Prozess ließe sich leicht für andere Arten von Spielen und generell andere Zwecke adaptieren. Eine Monte-Carlo-Simulation zur Annäherung von Pi wäre z. B. mit der gleichen Struktur möglich.

Simulation in RapidMiner

There are many applications for simulation of processes that can be described mathematically. The Monte Carlo simulation is an elegant method for solving different problems like calculating Pi.

RapidMiner is not advertised as a simulation tool, but with a bit of knowledge you can easily solve this task in it. So how about demonstrating Monte Carlo simulation with the example of French roulette?

The game of roulette is easy to describe. Players bet on different areas of a table. The areas cover smaller or larger sets of the numbers between 0 and 36. The probability of winning with a single number is 1/37; when betting on a larger area (e. g. four numbers, six numbers, one third of the numbers between 1 and 36, one color) it is a multiple of that. The won amount when guessing a number correctly is the 35 times the bet amount (and the player keeps the bet), and it decreases proportionally with the risk. For example, if you bet on red and the ball lands on a red field, you win an equal amount to your bet.

There is also a field with 0 that is not covered by most of the bets, so the bank also wins sometimes. Roulette is probably one of the most „fair“ games of luck available. (That’s probably the reason for the existence of American roulette that has a second 0 field: The US casinos weren’t satisfied with winning just 1/37 of the players‘ money.)

Simulation process

The process available here simulates repeated casino visits with a few settings. You can manipulate the settings in the process context (View menu/Show Panel/Context) in the Macros area. The process contains a description of each setting.

You can specify the number of visits and the betting rounds per visit (as long as there’s money left in the current visit). It is also possible to specify an amount that is enough to leave the casino before the specified number of rounds. (E. g. when you doubled the original amount.)

You can set a „style of gambling“ with the macro „Risk“. Here you specify the risk you’d like to try: it starts at 2 (red/black, even/odd, 1-18/19-36) and ends at 36 (betting on one number).

The process contains two loops, the first one (Loop Visits) holding the second one (Loop Bets) inside. After those there is some processing for displaying results.

The calculation of one betting round happens in „Calculate bet results“ (Generate Attributes). The amount lost or won in the round is calculated from the bet amount and the risk. This results in a change of the current amount.

After finishing the outer loop, the process calculates a few summary results.

Aggregated simulation results
Aggregated simulation results

average(VisitWonPct): Portion of the original amount that was lost or won in the average case. (Realistically, lost: this is expressed with a negative percentage.)

average(VisitReachedGoal): Portion of visits when reaching the desired amount (e. g. 150 € after starting with 100 €).

average(VisitLostEverything): Portion of visits when you lost everything.

average(VisitWonAmount): Average amount won or lost.

In addition to the numbers you can display each visit graphically:

Chart of each visit's progression
Chart of each visit’s progression

Open the „Pivot for series plot“ result, go to Charts, select Series, select BetNr as the Index dimension and mark all CurrentAmount attributes as Plot Series.

Each line describes the course of a casino visit (one color per visit). The X axis is the betting round, the Y axis the available amount after the round. It is easy to see that in several visits up to 30 rounds have been lost! The upper limit is the specified „leaving amount“ that was reached before the number of specified rounds.

This simulation process even works in RapidMiner Studio Basic (available for free without registration). You can easily determine your chance of winning in the casino playing your „strategy“. It’s not a big surprise that the result is mostly negative.

It should be easy to change the process to simulate other games or events. For example, you could estimate Pi using the same process structure.

 

GIS in RapidMiner (4) – Geo-Filter und Joins

(English version)

In diesem vierten Teil geht es um die Filterung von Datensätzen und die Verbindung mehrerer Datensätze anhand geographischer Kriterien. (Um die Beispiele nachzuvollziehen, muß RapidMiner wie in der Einführung beschrieben um die GeoScript-Libraries ergänzt werden.)

Da kein eingebauter Join-Operator für geographische Kriterien existiert, bauen wir diese Operation nach, indem wir jedes Element der beiden Datensätze miteinander vergleichen und das Ergebnis dann filtern. Der Vergleich wird mit geographischen Operationen durchgeführt.

In den bisherigen Beispielen wurde mit Hilfe des Cartesian-Product-Operators jede Kombination der Datensätze gebildet. Die andere Möglichkeit ist, in einer Schleife alle Elemente eines Datensatzes mit denen des anderen zu vergleichen.

(Dies ist wieder ein Bereich, in dem PostGIS mit geographischen Indizes in der Datenbank eine wesentliche Beschleunigung bietet, die bei wirklich großen Datenmengen auch noch gut funktioniert.)

Einige Funktionen, die uns für die Verbindung von Datensätzen zur Verfügung stehen:

distance: Diese Funktion haben wir bereits kennengelernt. Wenn wir die Distanzen aller Kombinationen bestimmt haben, können wir das Ergebnis filtern, um z. B. jene herauszufiltern, deren Distanz einen bestimmten Wert nicht überschreitet.

intersects: Liefert true, wenn die Objekte sich an mindestens einem Punkt überschneiden.

intersection: Erzeugt die Überschneidung der Objekte als neues geometrisches Objekt. Der Typ des überschneidenden Bereichs orientiert sich an den verglichenen Objekten: Z. B. ist die Überschneidung einer Fläche mit einer Linie wieder eine Linie. Wir können mit dem Ergebnis natürlich weiterarbeiten und z. B. die Fläche oder andere Kennzahlen bestimmen und darauf filtern.

contains: A.contains(B) liefert true, wenn das Objekt A das Objekt B vollständig enthält, also kein Teil von B außerhalb von A liegt.

Bei intersects und intersection ist die Richtung des Aufrufs egal (A.intersects(B) ergibt das gleiche wie B.intersects(A)). Bei contains jedoch nicht: Eine Fläche A kann einen Punkt B enthalten, was im umgekehrten Fall nicht gilt.

Eine häufig verwendete geographische Operation ist das Buffering, das mit der buffer-Funktion realisiert wird. Hierbei wird um das ursprüngliche Objekt (Punkt, Linie, Fläche) eine Fläche erzeugt, deren Grenze die im Funktionsaufruf angegebene Distanz zum Objekt hat. Das Ergebnis ist somit immer eine Fläche. Damit können wir verschiedene Dinge wie Einzugsgebiete von Geschäften, die Reichweite von Funkantennen oder die tatsächliche Fläche einer als Linie mit Breitenangabe angegebenen Straße berechnen. Mit der Berechnung des Buffers werden auch häufig Distanz-Vergleiche mit Hilfe von contains oder intersects durchgeführt.

Die Vorgehensweise in RapidMiner ist diese: zuerst werden in einem Execute-Script-Operator mit Groovy/GeoScript die benötigten Ergebnisse ermittelt (z. B. contains: true/false) und danach die Ergebnismenge mit Filter Examples gefiltert, sodaß nur die Objekte übrigbleiben, auf die das gewünschte Kriterium zutrifft (z. B. contains = true oder distance < 10).

Der Beispielprozess existiert in zwei Varianten: einmal mit Cartesian Product und einmal mit Loop Examples. Die erste Variante ist deutlich schneller, braucht jedoch sehr viel Speicher, weil sie riesige Tabellen anlegen muß. Die zweite Variante braucht viel länger, aber der Speicherverbrauch ist geringer, da keine „multiplizierten“ Datensätze erzeugt werden.

Für manche Operationen wie intersects oder contains ist die Projektion unerheblich (solange beide Geometrien im gleichen Koordinatensystem angegeben sind). Für buffer müssen wir aber eine Ausdehnung angeben, somit ist es wieder zweckmäßig, mit einer Meter-basierten Projektion zu arbeiten. Deswegen transformieren die Beispielprozesse alle Datensätze in die für Österreich geeignete Projektion EPSG:3416.

Drei Datensätze werden vom Wiener Open-Data-Server geholt: Wasserflüsse (Linien), Brücken (Flächen) und Spielplätze (Punkte). Dann sucht der Prozess mit intersects und intersection die Bereiche, in denen die Brücke über Wasser führt. Mit buffer wird der Bereich um die Wasserflüsse markiert, in dem mit contains nach Spielplätzen gesucht wird. Das Ergebnis ist dann eine Liste von Spielplätzen, die nahe an einem Bach oder Fluß liegen.

Beispielprocess mit Cartesian Product

Beispielprozess mit Schleifen

Damit ist diese Serie über GIS in RapidMiner vorerst abgeschlossen. Die besprochenen Methoden decken schon eine große Anzahl von Aufgaben ab, und mit etwas Kreativität ist noch viel mehr möglich. Ich werde sicherlich noch Anwendungen und Lösungen finden und darüber auch hier berichten. Wenn etwas unklar sein sollte, beantworte ich gerne Fragen: hier in den Kommentaren, im RapidMiner-Forum, oder auch direkt. Ich wünsche viel Erfolg!

GIS in RapidMiner (4) – Geographic Filter and Joins

The fourth part of this series is about filtering and joining example sets on geographic criteria. (RapidMiner needs to be extended with the GeoScript libraries as described in the Introduction for the examples to work.)

There is no built-in Join operator with support for geographic functions. So we reproduce this functionality by comparing each element of both example sets and filter the result. Geographic functions are used for the comparison.

In the examples until now, we used the Cartesian Product operator for building an example set with each combination of examples. The other way is a Loop over each element of example set 1 that compares the one example of the loop with all elements of example set 2.

(This is also an area where PostGIS shines with geographic indexes in the database that improve processing times by a huge factor, even in the case of huge tables.)

Some geographic functions usable for joining or connecting example sets:

distance: We already saw this. After calculating the distance of all combinations, we can filter the result set to only contain those within a certain distance.

intersects: Returns true if the objects have at least one point in common.

intersection: Creates a new geometry with the common parts of both objects. The type of the result depends on the compared objects: e. g. the intersection of an area and a line is again a line. The resulting geometry can be processed further, for example by calculating its area or other measures and filtering on those.

contains: A.contains(B) returns true if object A fully contains B, in other words, no part of B is outside of A.

The order of the objects is not relevant when using intersects and intersection: A.intersects(B) has the same result as B.intersects(A). This is not true for contains: An area A can contain point B but this is not true for the opposite.

Buffering is a popular geographic operation, available in the buffer function. Buffering creates an area around the original object (point, line, area) with a border in a distance specified in the function call. The result is always an area. We can calculate different things with buffering: the service area of shops, the coverage of wireless antennas or the actual area of a street that is specified as a line but has a width attribute. After creating the buffer, less-or-equal distance calculations can be done with contains or intersects.

The following work flow is available in RapidMiner: first, in an Execute Script operator we process the data using geographic functions with Groovy and GeoScript (e. g. contains: true/false); then we filter the result set with Filter Examples to only keep examples with the selected criteria (e. g. contains = true or distance < 10).

There are two variants of the example process: one with Cartesian Product and one with Loop Examples. The first version is much faster but needs a huge amount of memory as it has to create very large tables. The second version takes much longer but uses less memory, as it doesn’t need to process „multiplied“ data sets.

For some operations like intersects oder contains, the projection is not relevant (as long as both geometries use the same coordinate system). But we need to specify the border size in buffer, so it is again better to work with a meter based projection. Therefore, the example processes transform the original geometries to EPSG:3416, a projection suitable for Austria.

The process fetches three data sets from the Vienna Open Data Server: Water flows (lines), Bridges (areas) und playgrounds (points). It then uses intersects and intersection to find areas where the bridge is over water. Using buffer, it marks an area around water flows and uses contains to find playgrounds in that area. The result is a list of playgrounds in the vicinity of streams or rivers.

Example process with Cartesian Product

Example process with loops

This concludes the series about GIS in RapidMiner for now. The described methods solve a range of problems, and many more can be solved with some creativity. I will surely find use cases and solutions, and describe them here. If something is not clear, please ask: here in the comments, in the RapidMiner Forum or even directly. I wish you a lot of success!