IOException.de

Dieser Gastbeitrag wurde verfasst von Marcus Bombe:

In meinem vorherigen Artikel sprach ich viel über eine scheinbar widersprüchliche Aufgabenstellung aus der Wahrscheinlichkeitsrechnung, die in Wahrheit nur nicht vollständig war. In diesem Artikel nun will ich die Problematik mit einem einigermaßen realistischen Beispiel unterfüttern.

Tom hatte einen tollen Urlaub in Absurdistan. Erst als er wieder in Frankfurt landet erhält er die schlimme Nachricht: In Absurdistan ist die absurdianische Grippe ausgebrochen! Es handelt sich hierbei um eine tödliche Infaktion, die eine lange Inkubationszeit hat und zu beginn keine sichtbaren oder spürbaren Symptome hat. Folglich muss nun jeder Tourist aus Absurdistan und den Nachbarländern getestet werden, also auch Tom. Ein Arzt nimmt ihm Blut ab und es wird ein Schnelltest durchgeführt. Dieser Schnelltest hat folgende Eigenschaften:

• Der Test hat als Ergebnis entweder “Infiziert” oder “Nicht infiziert”
• 99% aller Infizierten werden als solche erkannt (Fachbegriff: Sensitivität)
• 99% aller Gesunden werden als solche erkannt ( Fachbegriff: Spezifität)

Zudem nehmen wir an, dass es sich hierbei um ein unabhängiges Zufallsexperiment handelt. Wird Blut von derselben Person nochmal getestet, so sind die Chancen wieder 99% korrekt zu 1% inkorrekt. Es ist also _nicht_ so, dass einmal falsch klassifiziertes Blut mit einer höheren Wahrscheinlichkeit wieder falsch klassifiziert werden würde. Aber zurück zu Tom, der sitzt im Warteraum des Arztes und wartet auf sein Ergebnis. Sorgen macht er sich eigentlich keine, weil ihm gehts gut und er hatte auch keinen Kontakt zu krank wirkenden Personen. Nach einer Stunde wird Tom zum Arztgespräch gebeten und zu seinem großen Unglück eröffnet ihm der Arzt, dass der Text positiv sei, er also laut dem Text infiziert sei. Aber kein Grund zur Sorge, machmal irre sich der Test, meinte der Arzt und nahm Tom nochmals Blut für einen zweiten Schnelltest ab. Wieder wartet Tom eine Stunde, diesmal fühlt sich die Zeit schon wesentlich länger an. Nach etwas mehr als einer Stunde wird er wieder zum Gespräch gebeten. Der Arzt bittet Tom, platz zu nehmen, denn er habe eine schlechte Nachricht. Auch der zweite Test ist positiv ausgefallen!

Frage: Wir große Sorgen sollte Tom sich nun machen? Wie wahrscheinlich ist es, dass Tom tatsächlich infiziert ist? Diese Frage sollte der Leser nun für sich selbst beantworten, bevor wir fortfahren. Ist es um die 99%? Oder eher um die 98%? Vielleicht sogar nur 95%? Was sagt das Bauchgefühl?

Alles falsch. Auch hier fehlt wieder eine notwendige Angabe. Mit der sogenannten Prävalenz bezeichnen Mediziner das Verhältnis zwischen der Anzahl der tatsächlich Kranken und der Anzahl aller Untersuchter. Und genau diese Werte fehlen uns. Also dichten wir sie unserer Geschichte hinzu: Die absurdianische Grippe ist glücklicherweise wenig infektiös und Absurdistan ist nicht dicht besiedelt, daher hat es nur 1 von 100.000 Touristen erwischt. Insgesamt wurden eine Million Touristen aus Absurdistan und den angrenzenden Ländern untersucht. Betrachten wir nun also die Abläufe des Tests für alle diese Menschen:

• 1.000.000 Menschen teilen sich auf in 10 Erkrankte und 999.990 Gesunde.
• Von den 10 Erkrankten wurden im ersten Test alle (genau genommen: 9,9) als erkrankt erkannt. Auch ein zweiter Test ändert daran nichts. Folglich sind nach zwei Test 10 tatsächlich kranke als Krank erkannt worden.
• Von den 999.990 Gesunden werden im ersten Test 999.990 * 0,01 ~= 10.000 fälschlicherweise als krank erkannt. Der Rest darf gehen. Die 10.000 im ersten Test falsch erkannten werden nochmals getestet. Im zweiten Test werden 9.900 der 10.000 richtigerweise doch als Gesund erkannt, aber 10.000 * 0,01 = 100 Personen werden ein zweites mal fälschlicherweise als krank eingestuft.
• Fazit: 110 nach zwei Tests als Krank erkannte, jedoch nur 10 tatsächlich erkrankte.

Wenn wir dies nun in einer Wahrscheinlichkeit ausdrücken wollen, so ist Tom nur mit 10/110 ~= 9%-iger Wahrscheinlichkeit infiziert. Glück für Tom.

Tatsächlich gibt es diese Problematik in der Praxis, Wikipedia rechnet dies am Beispiel von DNA-Tests durch. Der Artikel http://de.wikipedia.org/wiki/Pr%C3%A4valenzfehler gibt hierbei einen guten Einblick, wie belastend ein DNA-Test alleine ist. Angelehnt ist der Artikel an http://de.wikipedia.org/wiki/Sensitivit%C3%A4t#HIV_in_der_BRD sowie an einen Abschnitt aus dem Buch “Der Hund der Eier legt” [http://www.amazon.de/Hund-Eier-legt-Hans-Peter-Beck-Bornholdt/dp/3499611546], was ich nur wärmstens empfehlen kann.

Dieser Gastbeitrag wurde verfasst von Marcus Bombe:

Am Wochenende bin ich via Twitter auf folgende Fragestellung aus der Stochastik getroffen:

If you choose an answer to
this question at random,
what is the chance you will
be correct?
A) 25%
B) 50%
C) 60%
D) 25%

Quelle: http://flowingdata.com/2011/10/28/best-statistics-question-ever/

Die Frage hat einige Wellen geworfen und wurde in verschiedenen Medien ausführlich diskutiert. Alleine fast 500 Kommentare auf der Website, die die Frage veröffentlicht hat. Frei nach xkcds “Duty Calls” [ http://xkcd.com/386/ ] konnte ich natürlich nicht widerstehen und präsentiere hier meine Antwort auf die Frage und noch ein wenig Hintergrundwissen dazu. An dieser Stelle sollte sich der Leser jedoch zunächst die eigene Antwort überlegen.

Was fällt nach eingehender Betrachtung auf? Es gibt vier Antwortmöglichkeiten. Man kann nun annehmen, dass jede dieser Möglichkeiten mit der Wahrscheinlichkeit 1/4 gewählt wird. Der erste Gedanke wäre dann, dass 25% die korrekte Antwort ist. Nun ist die Antwortmöglichkeit “25%” jedoch doppelt vergeben, würde also mit 50%-iger Wahrscheinlichkeit gewählt. 50% könnte also die Antwort sein. 50% ist aber nur einmal als Antwort vertreten, sollte somit nur in 25% der Fälle gewählt werden. Aber halt, dann wäre ja auf einmal 25% die korrekte Antwort, aber die kommt ja doppelt vor, also mit 50%-iger Wahrscheinlichkeit… Scheinbar reiht sich diese Aufgabe in die Liste vieler bekannter und schöner Widersprüche ein. Sofort denkt man an klassiker wie: “Der nachfolgende Satz ist wahr. Der vorhergehende Satz ist falsch.” oder die Geschichte des Barbier von Sevilla: “Der Barbier von Sevilla rassiert genau jene Männer in Sevilla, die sich nicht selbst rassieren. Frage: Rassiert sich der Barbier selbst?”. Gerade diese Selbstbezogenheit im Beispiel mit dem Barbier haben wir scheinbar auch in dieser Frage.

Dem ist allerdings nicht so, denn es handelt sich bei der hier vorgestellten Aufgabe nicht um einen echten Widerspruch. Einerseits wurde auf flowingdata.com in den Kommentaren schon viel darüber diskutiert, dass es sich bei dem Fragetext eigentlich gar nicht um eine Multiple-Choice Frage handelt. Man stelle sich nur vor, die Antwortmöglichkeiten wären statt dessen etwa “A) 1%, B) 2%, C) 3% und D) 4%”. Dies sollte genauso erlaubt sein, wie dass man die im Original genannten Werte als Antwortmöglichkeiten unter die Frage schreibt. Man erkennt hier jedoch schon, dass die Einschränkung auf die Möglichkeiten A bis D künstlich erfolgt und offenbar auch etwas anderes als A bis D in Frage kommen könnte. Aber gut, da mögen sich nun die Geister scheiden. Der wesentliche Punkt folgt jedoch nun:

Die Aufgabenstellung hat jedoch noch eine größere Schwäche, die zudem sehr lehrreich ist und mich deshalb zu diesem Artikel motiviert hat. Nehmen wir also an, es gibt auf die Frage, wie impliziert, genau vier Antwortmöglichkeiten (25%, 50%, 60% und 25%). Mit anderen Worten, es handelt sich um ein Zufallsexperiment, bei dem eine Zufallsvariable, nennen wir sie X, die Werte A, B, C und D annehmen kann. Jeder kennt das beispielsweise beim Münzwurf, hier kann die zugehörige Zufallsvariable bei einem Wurf den Wert “Kopf” oder “Zahl” annehmen. Und hier sinds eben die Werte A, B, C und D. Nun ist allerdings in keinster Weise angegeben, wie die sogenannte Verteilung dieser Zufallsvariablen auszusehen hat. Nur weil X zufällig ist, bedeutet das nicht, dass jede Option wie oben in der ersten Betrachtung angenommen mit je Wahrscheinlichkeit 1/4 (=25%) daher kommt. Erst die Verteilung einer Zufallsvariable gibt an, wie hoch die Wahrscheinlichkeit für einen konkreten Wert ist. Bei der sogenannten “Gleichverteilung” wären es je 25% bei Vier möglichen Werten. Aber es kann auch jede andere Verteilung sein.

Beispiel: So könnte ich in einem weiteren Schritt erst einmal eine Zufallszahl Z gleichverteilt aus {1, 2, …, 10} wählen und festlegen, dass wenn Z = 1 ist, dann ist X = A. Mit anderen Worten: Wenn meine zufällig Zahl zwischen 1 und 10 gerade die 1 ist, dann wähle ich Antwort A in der Aufgabenstellung aus. Ist hingegen Z = 2, so soll X = B sein. Bei Z = 3 und Z = 4 wählen wir X = D und in allen anderen Fällen (Z = 5, … Z = 10) legen wir fest, dass X = C sein soll. Ist Z wie gefordert tatsächlich zufällig, so ist es X auch und wir haben, wie in der Aufgabenstellung gefordert, eine Antwort auf die Frage zufällig bestimmt. Nun können wir aber nachrechnen, wie hoch die Wahrscheinlichkeiten für die einzelnen Antworten sind: X = A und X = B wird in je einem Fall erreicht, also ist deren Wahrscheinlichkeit gerade 10%. X = D wird in zwei Fällen gewählt, nämlich wenn Z = 3 oder Z = 4 ist. Folglich geben wir mit 20%-iger Wahrscheinlichkeit D als Antwort an. In den restlichen sechs Fällen (Z = 5, …, Z = 10) wird X = C unsere Antwort sein. Dies tritt mit 60%-iger Wahrscheinlichkeit auf. Spannenderweise ist Antwort C gerade “60%”. Bei dieser eben erfundenen Verteilung von X gelingt es uns also sogar, die Aufgabenstellung zumindest teilweise zu beantworten in dem wir Antwort C nennen. Das löst noch nicht alle Probleme mit der Aufgabenstellung (insbesondere: Woran macht sich fest, dass C überhaupt die “korrekte” Antwort ist? Was passiert, wenn X != C ist?), aber wir haben den Knoten etwas gelöst.

Der geneigte Leser mag nun den Vorwurf äußern, dass die konstruierte Verteilung ja willkürlich gewählt sei. Das ist auch korrekt, es lassen sich ebenso leicht Verteilungen konstruieren, bei denen der Widerspruch in der Aufgabenstellung verschwindet, wenn A, B oder D die Antwort ist. Aber noch weiter: Es lässt sich auch eine Verteilung angeben, in der 25%, 50% und 60% nicht einmal als Wahrscheinlichkeiten von X auftreten. Für jede beliebige Wahrscheinlichkeit für die Antworten X = A, …, X = D, lässt sich eine Verteilung konstruieren, sofern die vier Wahrscheinlichkeiten in Summe 100% ergeben. Folglich fehlt der Aufgabenstellung eine relevante Angabe und die Aufgabenstellung bleibt somit sinnlos. Ich könnte ebenso gut fragen, was der kürzeste Weg zur nächsten Tankstelle sei und sogar Antworten beisteuer wie A) links-rechts-links, B) rechts, einmal duch den Kreisel und wieder rechts, u.s.w. und auch diese Frage ist sinnlos, wenn ich nicht dazu angebe, wo ich mich befinde oder wie die Strecke zurückzulegen sei.

Nun könnte man ja behaupten, dass es klar sei, dass die vier Antwortmöglichkeiten jeweils mit Wahrscheinlichkeit 1/4 (=25%) zu wählen seien, es sich also um eine Gleichverteilung handelt. Aber worauf soll diese Annahme beruhen? Es ist noch einsichtig, dass man mit guten Willen Gleichverteilung bei einem Würfel oder einer Münze annimmt, aber bei einer künstlich erstellten Frage? Einfach die Verteilung anzunehmen macht im Allgemeinen auch keinen Sinn. Beispiele hierzu: Morgen kann es in Ulm regnen oder es in Ulm nicht regnen, also sind das zwei Möglichkeiten. Daraus folgt aber keine Regenwahrscheinlichkeit von 50%. Weder für hier, noch einen anderen Ort auf der Welt (Sahara, Regenwald, …). Genauso kann ein Lottospieler mit einem Spiel (bei dem die sechs Kreuze auch zufällig gewählt werden) entweder sechs Richtige haben oder eben nicht und das ist zufall. Aber sicherlich hat man nicht 50% Chance auf den Millionenjackpot.

Somit ist für mich die Betrachtung der obigen Aufgabenstellung erledigt. In einem weiteren Artikel werde ich auf eine ähnliche, aber durchaus realistischere Fragestellung aus der Stochastik eingehen. die auch paradox wirkt.

Geeignete Links zum Einlesen/Weiterlesen:

• http://de.wikipedia.org/wiki/Wahrscheinlichkeitstheorie
• http://de.wikibooks.org/wiki/Mathematik:_Wahrscheinlichkeitstheorie:_DW:_Inhaltsverzeichnis
• http://de.wikibooks.org/wiki/Mathematik:_Statistik

Darüber hinaus hat Wikipedia auch einige tatsächliche spannende Widersprüche und Paradoxien zu liefern, die nicht wie diese Aufgabenstellung hier an unvollständigen Informationen kranken. Siehe hierzu

• http://en.wikipedia.org/wiki/List_of_paradoxes
• und insbesondere: http://en.wikipedia.org/wiki/Category:Probability_theory_paradoxes
• Besonderen Spaß und unendliche Diskussionen bereitet insbesondere das Ziegenproblem: http://de.wikipedia.org/wiki/Ziegenproblem

Im ersten Teil haben wir zwei einfache Lösungsstrategien entwickelt, wie sich Umkreissuchen der Form “Suche die nächstgelegenen 15 Orte heraus!” durch einen Subquery vorfiltern lassen: Die grundsätzliche Idee ist, über eine Näherungsformel eine Selektion von 15*faktor Datensätzen zu finden, aus denen dann die echt-nächsten Orte bestimmt werden können.

Als Näherung bietet sich so die Pythagorasformel an, die in diesem Beitrag in der simplen Form (Breiten- und Längengerade gehen gleich gewichtet ein) und der verbesserten (mit Gewichtung von 1:1,57 in Deutschland) untersucht wird. Dabei gilt grundsätzlich die Frage zu klären, wie groß in beiden Fällen wohl der faktor gewählt werden muss, damit in den meisten Fällen in der Näherungsselektion auch alle 15 echt-nächsten Orte enthalten sind. Daneben interessiert natürlich, wie groß der Performancegewinn beider Strategien ausfällt.

Dazu habe ich ein kleines Testscript in node.js geschrieben, das eine ganze Reihe Testfälle generiert und durchspielt. Insgesamt wurden für 200 zufällige Orte in Deutschland oder grenznahen Regionen jeweils die 1, 5, 10, 20, 50, 100, 150 und 200 echt-nächsten Orte gesucht. Das Script ermittelt dabei für die beiden Näherungsformeln, wieviele Datensätze durch diese geliefert werden müssen, damit die gesuchten Orte auch wirklich enthalten sind. Ein mögliches Ergebnis wäre also etwa, dass wir über die einfache Pythagorasformel für den Alexanderplatz Berlin mindestens 25 Datensätze erhalten müssten, damit keiner der 15 echt-nächsten fehlte.
Als Datenbasis dient dabei die Vereinsdatenbank von meinem nodeKO-Projekt, die etwa 2600 echte Vereine enthält und somit auch recht praxisnah für diesen Versuch ist.

Die entstandenen 1600 Messdaten und Auswertungen können bei GoogleDocs eingesehen werden. Das Testscript arbeitet so, dass nie zwei Queries gleichzeitig abgesetzt werden, die Zeitmessungen sind also ohne Last.

Als erstes soll es uns aber gar nicht um die Performance gehen, sondern viel mehr um die Ermittlung eines geeigneten Faktors für die beiden Näherungen. Im Limits-Sheet sind dabei die Messwerte zusammengefasst: Will man z.B. die 20 nächsten Datensätze ermitteln, so sollte man im Mittel über die einfache Pythagorasformel mindestens 35 Datensätze selektieren, bei der verbesserten Formel reichen dagegen 21 (!). Interessant sind auch die Maxima: Nach spätestens 97 Datensätzen waren in allen Testfällen alle 20 gesuchten bei der einfachen Formel enthalten, die verbesserte kam da mit einem maximalen Limit von 30 aus. Im Mittel über alle Tests ergibt sich, dass, wer die Pythagorasformel anwendet, den faktor wenigstens bei 1.75 ansetzen sollte. Bei Hinzunahme des Verhältnisses lon/lat reicht dagegen ein Faktor von 1.05. Wichtig hierbei ist natürlich, dass stets aufgerundet wird.

Der Mittelwert ist aber nur bedingt aussagefähig. Es bleibt immer noch die Frage: Wie häufig ist mein Ergebnis wohl trotzdem falsch, wenn die obigen Werte eingesetzt werden?
Hierfür habe ich die Versuchsergebnisse anders betrachtet: Mit welcher Wahrscheinlichkeit sind alle gesuchten Datensätze wohl enthalten, wenn bei der einfachen Pythagorasformel der Faktor 2 (wir sind mal großzügig…) genutzt wird? Für mich vor allem interessant, weil ich diesen Faktor bei meinem Projekt eingesetzt hatte. Und tatsächlich: Es zeigt sich, dass der Faktor 2 in gerade mal vier von fünf Fällen die gesuchten Ergebnisse liefert. Wer die Pythagoras-Näherung einsetzt, sollte diesen Faktor also doch lieber ein wenig großzügiger bemessen.

Anders ist das bei der verbesserten Pythagorasformel: Mit Faktor 2 hätte sie in allen 200 Testfällen die gesuchten Orte auch mit selektiert. Selbst der Faktor 1.5 ist noch mehr als ausreichend und lieferte in mehr als 99 Prozent die gesuchten Datensätze. Doch wie weit kann man noch runter gehen? Bei einem Faktor von 1.3 sind immer noch sehr annehmbare 98 Prozent der Anfragen korrekt, bei 1.1 fast 97 Prozent.

Und wozu das ganze? – Natürlich um Rechenzeit zu sparen. Die ermittelten Laufzeiten sind leider nur bedingt aussagefähig. Sie geben jeweils an, wieviel Zeit erforderlich war für eben jenen Query, der zuerst alle gesuchten Datensätze enthielt. In Ausnahmefällen kann das also schon mal deutlich mehr sein, als man erhalten würde, wenn man einfach einen fixen Faktor einsetzte. Und dennoch sprechen bereits diese Zahlen für sich: Durch die verbesserte Pythagorasformel erhält man einen Performancegewinn von fast 50 Prozent, die Anwendung lohnt also.

In meinem Projekt äußerte sich der Gewinn sogar noch deutlicher. Dort hatte ich direkt auf meine Tabelle gejoint und gleichzeitig die 15 nächsten Orte gesucht. Resultat: Alle Datensätze wurden erst gejoint und anschließend reduziert. Natürlich ist ein erster möglicher Schritt die Tabelle per Subquery sofort mit der exakten Entfernungsformel zu reduzieren, das bringt auch schon einen deutlichen Gewinn. Noch schneller geht es aber mit den beiden gezeigten Näherungen.
Insbesondere ist es durch die obigen Erkenntnisse möglich, einen Teil der Last auf den Client umzulegen. So wäre ein geeignetes Vorgehen etwa, dem Client stets limit*faktor genäherte Datensätze auf seine Anfrage zurück zu geben, was für den Server sehr viel schneller als die exakte Rechnung ginge. Der Client müsste jetzt selbst den letzten Schritt gehen und für die erhaltenen Orte die exakte Entfernungsberechnung durchführen, um die echt-nächsten limit Orte zu bestimmen.

Wie auch einige Kollegen dieses Blogs nahm ich vor wenigen Wochen am node.js knockout teil, einem 48-Stunden-Hackathon. Ich versuchte mich mit meinem Projekt an einem Mashup, das als zentrales Element eine Umkreissuche beherbergen sollte.

Diesen Anwendungsfall gibt es sehr häufig: In einer SQL-Datenbank sind Geo-Koordinaten von Orten gespeichert und es soll nun ausgehend von einer beliebigen Position eine bestimmte Anzahl der nächstgelegenen gespeicherten Orte gefunden werden. Da ich mit meinem Projekt eine Datenbank für deutsche Vereine realisieren wollte, wäre etwa eine konkrete Fragestellung gewesen: “Hey, ich bin gerade beim Alexanderplatz Berlin. Such mir doch mal die 15 nächstgelegenen Vereine heraus!” Die Ergebnismenge ist hierbei nur in der Anzahl, nicht aber der Entfernung eingeschränkt. Genau umgekehrt wäre es zum Beispiel, wenn nach allen Vereinen im Umkreis von 50km gesucht würde, wo auch mehr oder weniger als 15 Resultate gefunden werden könnten. Dieser Beitrag wird nur die erste Frage behandeln. Der Begriff “Umkreissuche” sollte also in diesem Sinne verstanden werden.

Nehmen wir an, unsere Koordinaten sind in der Tabelle coords in den Spalten lat und lon gespeichert. Die 15 nächstgelegenen Orte zu einem gegebenen Punkt (c.lat, c.lon) zu finden ist gar nicht so schwer, die SQL-Abfrage findet man im Internet:

'SELECT *, (acos(sin('+c.lat+'*Pi()/180)*sin(lat*Pi()/180)+cos('+c.lat+'*Pi()/180)*cos(lat*Pi()/180)*cos(('+c.lon+'-lon)*Pi()/180))) as distance FROM coords ORDER BY distance ASC LIMIT 15'

Die Resultate, die diese Abfrage liefert, sind die 15 nächstgelegenen Orte zum Punkt c. Problem bei diesem Vorgehen ist, dass die Abfrage recht umfangreich und somit auch zeitintensiv ist, wodurch sie etwa im Falle großer Datenmengen oder zusätzlicher Joins zum Flaschenhals wird. So lief die Abfrage bei meinem Projekt mit nur 2600 gespeicherten Orten sehr schleppend und drohte das Scheitern der gesamten Applikation.

Abhilfe sollte folgende Überlegung schaffen: Ist es schneller, nicht direkt von der Tabelle coords abzufragen, sondern eine Auswahl überhaupt in Frage kommender Vereine vorher abzuschätzen? Ziel wäre es also, einen Query in folgender Form zu nutzen:

'SELECT *, (Formel von oben) AS distance FROM (SELECT * FROM coords ORDER BY abschaetzung LIMIT faktor*15) AS shortened ORDER BY distance LIMIT 15'

Es werden also über eine Näherungsformel die 15*faktor besten Datensätze vorausgewählt, aus denen dann die 15 echt nächsten gesucht werden. Die simpelste Idee einer solchen Näherungsformel wäre schlicht die Abschätzung mittels Pythagoras, bei der wir mal außer Acht lassen, dass unsere Erde ja eigentlich ein räumliches Gebilde ist. Die Abschätzungsselektion sieht dann so aus:

'SELECT * FROM coords ORDER BY SQRT(POW(('+c.lat+'-lat), 2)+POW(('+c.lon+'-lon), 2)) LIMIT '+15*faktor

Entscheidend ist natürlich: Wie groß muss wohl faktor gewählt werden, damit auch wirklich alle der 15 echt nächsten Punkte in der Vorauswahl enthalten sind? Während des 48-Stunden-Hackathons hatte ich keine Zeit, dies näher zu ergründen und probierte es mit dem Faktor 2, der nach meinem Empfinden kaum false-positives lieferte. Ob dem wirklich so ist, wird der zweite Teil dieses Beitrags zeigen.

Die Betrachtung, Längen- und Breitengrade gleich gewichtet in die Pythagoras-Formel einfließen zu lassen, ist der naivste Weg. Die false-positive-Rate ließe sich verbessern, wenn man das Verhältnis Breitengrad zu Längengrad genauer wüsste. Diese lassen sich aber nicht einfach in Kilometer umrechnen – einen konstanten Umrechnungsfaktor kann es aufgrund der Erdkrümmung nicht geben. Da wir aber ohnehin nur eine Näherungsformel zur Vorauswahl suchen, ist das auch gar nicht so schlimm, Näherungswerte reichen für eine Verbesserung der eben genutzten Pythagorasformel vollkommen.

Über den Google Maps Distance Calculator lassen sich Näherungen für Deutschland recht schnell ermitteln: Ein Breitengrad (lat) entspricht bei uns rund 70 Kilometer, Längengrade (lon) erhöhen sich alle 110 Kilometer um eins. Damit lässt sich die obige Pythagoras-Formel verbessern:

'SELECT * FROM coords ORDER BY SQRT(POW(('+c.lat+'-lat)/70, 2)+POW(('+c.lon+'-lon)/110, 2)) ASC LIMIT '+15*faktor2

Der Preis einer solchen Verbesserung der Näherungsformel ist freilich, dass die Abfrage wieder rechenintensiver wird. Interessant dürfte also sein, ob sich das ganze dann überhaupt noch lohnt. Eigentlich ist es auch gar nicht nötig, die Breiten- und Längengrade auf Kilometer runter zu rechnen, da ja eigentlich nur das Verhältnis als Gewichtung eingehen soll. Statt beide zu dividieren würde also auch ein (lonDiff)*1.57 genügen – wieder eine Operation gespart!

Noch immer wissen wir jedoch nicht, wie groß der jeweilige Faktor bei den beiden Abschätzungen sein sollte, sodass man eine möglichst geringe Fehlerquote erhält (trivialerweise sollte er natürlich wenigstens 1 sein). Wieviel weniger darf der Faktor wohl angesetzt werden, wenn man die Pythagorasformel wie oben beschrieben verbessert? Ein Stochastiker würde das wohl in dieser Form fragen: Wie groß muss der Faktor wenigstens sein, dass nur in maximal 5 Prozent aller Abfragen nicht alle 15 nächsten Vereine enthalten sind?

Im nächsten Teil wird versucht, diese Fragen durch eine Vielzahl an Tests an den Vereinsdaten zu beantworten, und geklärt werden, ob sich die Vorauswahl denn wirklich in einer Steigerung der Perfomance ausdrückt. Ohne zu viel vorweg nehmen zu wollen: Bei meinem node.js knockout Projekt betrug der Performancegewinn über 80 Prozent. Da wusste ich aber auch noch nicht, dass die einfache Pythagorasabschätzung mit Faktor 2 in jedem fünften Fall nicht alle der 15 nächstgelegenen Vereine lieferte…

Anscheinend war es wohl mal wieder Zeit für einen etwas theoretischeren Beitrag. Binärbäume sind in der Informatik eine wichtige Datenstruktur, mit der sich beispielsweise Rechenterme abspeichern lassen. Sie bestehen aus Knoten, die einen linken und/oder rechten Knoten besitzen können, welche selbst wieder Unterknoten besitzen können. Mehr dazu findet man unter anderem bei Wikipedia.

Binärbäume werden über rekursive Aufrufe traversiert, bei (Binär-)Bäumen gibt es hauptsächlich drei wichtige Traversierungen: Pre-Order, In-Order und Post-Order. Ein Traversierungschritt besteht jeweils aus drei Teilschritten: Auswertung des aktuellen Knotenwerts, und der rekursive Abstieg in den linken und rechten Unterknoten. Der Name gibt jeweils an, an welcher Stelle die Auswertung des aktuellen Knotens stattfindet. Bei einer Post-Order-Traversierung wird also erst, der linke und der rechte Knoten rekursiv aufgerufen, und dann erst der aktuelle Knoten selbst ausgewertet. Hier ein Beispiel:

Pre-Order: L A H L O
In-Order: H A L L O
Post-Order: H L A O L
Nun ist es eine beliebte (Prüfungs-)Aufgabe, anhand zweier gegebenen Traversierungen den Originalbaum rekonstruieren zu lassen. In manchen Lehrbüchern ist zu finden, dass dies mit zwei Traversierungen möglich ist. Allerdings misslang mir dies bei einigen Versuchen mit Pre- und Post-Order-Ausagabe und ich sah mir das Ganze genauer an. Die Aussagen ist nämlich nicht ganz korrekt, ohne eine In-Order-Ausgabe ist dies nur in bestimmten Situationen möglich (nämlich wenn der Baum vollständig ist). Doch wieso klappt es nur mit Pre & Post nicht? Hier ein Gegenbeispiel:

Bei beiden Bäumen ergibt sich als Pre-Order-Durchlauf „A B C“ und als Post-Order „C B A“, obwohl die Binärbäume nicht identisch sind.

Nun ein vollständiger Baum:

Hier ergeben sich folgende Traversierungen:
Pre-Order: A B D E C F G
Post-Order: D E B F G C A
Hiermit lässt sich der Baum rekursiv rekonstruieren, indem man die Traversierung rückwärts durchspielt und dabei jeweils Teilbäume wiederherstellt.
Wird nun jedoch der rote F-Knoten entfernt (was die Vollständigkeit aufhebt), so ist nur anhand des Pre- und Post-Order-Durchlaufs nicht mehr eindeutig, ob der Knoten G links oder rechts unterhalb des Knotens C sich befindet. Also lassen sich nur vollständige Bäume mit einer Kombination von Pre und Post rekonstruieren.

Bei allen anderen Bäumen ist dies mit einer Kombination eines In-Order-Druchlaufs zusammen mit einem Pre- oder Post-Order-Durchlaufs möglich.

Update: Nach längerer Suche bin ich im Internet noch auf diese Seite gestoßen, die das Problem ebenfalls anspricht und Rekonstruktionen noch genauer untersucht.