Archive of the category   * Algorithms *
Der Immobot geht um

Schon vor Längerem habe ich ja bereits angekündigt, dass Freelenz an einem ebenso spannenden wie innovativen Projekt werkelt. Worum es sich dabei in etwa handelt, werden wiederkehrende Besucher wohl bereits obigem Plakat entnommen haben, das seit einiger Zeit an der Tapete hängt. Worum es sich konkret handelt, will ich hier und jetzt verraten. Schließlich sind es nur noch knapp zwei Wochen bis zum offiziellen Start.

Immoment ist eine regionale, semantische Suchmaschine für Immobilieninserate. Regional, weil auf Österreich beschränkt. Semantisch, weil Immoment bestimmte Eckdaten einer Immobilienanzeige im Internet erkennen und verwerten kann, wie zum Beispiel die Wohnfläche, den Preis, ob es sich um ein Miet- oder Kaufobjekt handelt, PLZ/Ort, etc. Nach diesen Kriterien kann eben auch auf Immoment gesucht/gefunden/sortiert werden.

Außerdem lässt das Web 2.0 herzlich grüßen. Durch den verstärkten Einsatz von Ajax wird das ebenso praktische wie innovative Konzept der Livesuche verwirklicht. Will heißen: Hier ein paar Stichworte eintippen, dort den Preisschieber bewegen, dann vielleicht noch ein paar Kästchen ankreuzen – die Suchergebnisse folgen prompt und auf dem Fuße. Und das Beste daran: Die Parameter können laufend verändert werden. Kein mühsames Durcharbeiten mehrerer Webformulare, kein mehrfaches Zurückklicken bei erfolgloser Suche.

Bei Immoment fühlt sich das Suchen eher an wie ein Eichen und Justieren, ein Frage-und-Antwort-Spiel, ein Dialog mit der Datenbank, ein lebendiger Prozess, … okay, genug damit. ;-)

Konkret sieht das ungefähr folgendermaßen aus:

immomentscreen.gif

Links spielt die Musik, da werden die Suchkriterien eingestellt, also zum Beispiel wird eine Preisober- und -untergrenze festgelegt. Daneben erscheinen ruckzuck die Resultate. Feine Sache oder was?

Also, am 1. Februar ist es soweit! Inzwischen geht der Immobot fleißig um und indiziert Inserate. So um die 40.000 werden es zu Beginn sein, aber das ist noch stark ausbaufähig.

 
Million Dollar Baby

Aus Spaß an der Freud’ quasi beteiligt sich Freelenz ab sofort am Wettrennen um den Netflix Prize. Wie wo was? Also, von vorne: Netflix ist ein US-amerikanischer DVD-übers-Internet-Verleiher. Die Eckdaten: 80.000 Filmtitel, 42 Millionen DVDs, 1300 Mitarbeiter, 1,6 Millionen DVD-Sendungen pro Tag an knapp 7 Millionen Kunden, von denen etwa 60 Prozent ihre Filme aus automatisch generierten Empfehlungen auswählen. Leicht nachzuvollziehen, dass diese Empfehlungsmaschinerie einen Gutteil des Erfolgs von Netflix ausmacht. Nur, wie kommen diese Empfehlungen zustande?

Jeder Kunde kann (und tut das auch fleißig) die Filme, die er geliehen und gesehen hat, auf der Website von Netflix mit 1-5 Sternen bewerten. Fünf will heißen “Oscar, wenn’s nach mir ginge”, eins hingegen “schwache Vorstellung”, dann gibt’s noch drei Zwischentöne für die Indifferenten. über die Jahre hat Netflix über eine Milliarde solcher Ratings eingesammelt und akribisch in einer riesigen Datenbank verstaut. Auf deren Basis ist ein Algorithmus in der Lage, zukünftige Bewertungen mit einer durchschnittlichen Abweichung von 0,9525 Sternen vorherzusagen. Mit anderen Worten: Die Maschine weiß ziemlich genau, was den Leuten gefallen wird und was nicht.

netflix.gif

Doch scheinbar ist das noch nicht ausreichend. Also will Netflix demjenigen $ 1.000.000 (in Worten: Eine Million Dollar) zustecken, der diesen Wert um 10 Prozent zu verbessern weiß, sprich mit einem besseren Algorithmus eine Standardabweichung unter 0,8572 erreicht. Netflix stellt die Daten zur Verfügung. Und da beginnt es auch, schwierig zu werden. Natürlich sind alle privaten Kundendaten zuvor entfernt worden. Der durch soviel Geld entsprechend motivierte Algorithmentüftler bekommt auf Anfrage komprimierte 700 Megabyte an Daten, die im wesentlichen aus 17.000 Filmtiteln, 480.000 nackter Kundennummern und schlappen 100.000.000 abgegebenen Bewertungen bestehen. Dann mal los!

Natürlich bildet sich Freelenz nicht ein, die Nuss knacken zu können. Wieso nicht? Vielleicht deshalb, weil sich bereits ganze Forscherteams an Informatik-Fakultäten seit Monaten die Zähne daran ausbeißen – und das Geld immer noch da liegt wo es ist. Nein, für Freelenz ist das Ganze eine Art Gelegenheit zum Abreagieren an Hard- und Software. Ein Ausreizen der technischen Möglichkeiten, um ein besseres Gefühl für die Leistungsfähigkeit von Algorithmen, Programmiersprachen und Datenbanksystemen zu bekommen. Weiter nichts. Naja, fast nichts. Die Hoffnung stirbt zuletzt. Vorher erwischt es vermutlich meinen 2.4-GHz-Prozessor.

 
Google’s Pagerank und die Mathematik

Das Smashing Magazine hat neuerdings einen Haufen Informationen zu Google’s PageRank Algorithmus zusammengetragen. Wie die Suchmaschine im Detail herumwerkt, ist und bleibt natürlich Betriebsgeheimnis, allerdings geben die gesammelten Artikel einen recht profunden und interessanten Einblick in deren Arbeitsweise.

google_math.jpg

Vorausgesetzt, man lässt sich nicht von staubtrock’ner Mathematik abschrecken. ;-)

 
Collaborative Filtering

Im Auftrag von Lovely Systems lese ich mich grad in die Materie Collaborative Filtering ein. Noch nie etwas davon gehört? Vielleicht läuten beim Begriff Recommendation Systems ein paar Glocken. Auch nicht? Na dann tönt bestimmt zumindest dieser Satz einigermaßen vertraut: “Kunden, die diesen Artikel angesehen haben, haben auch schon von folgenden Produkten geträumt.” Oder so ähnlich.

amazon_cf.gif

Es geht also darum, Vorhersagen über Uservorlieben zu treffen, aufgrund der Vorlieben von anderen, ähnlichen Usern. Doch wann sind sich User ähnlich? Und vor allem: Wie ähnlich sind sie sich? Kann man diese Ähnlichkeit in einer Zahl ausdrücken? Vielleicht auf einer Skala von 1 bis 100? Zwei Dinge braucht man dazu. Einen Haufen Daten und eine Hand voll Mathematik. Es gibt übrigens auch ein, zwei Bücher zu dem Thema.

Bei Amazon gestaltet sich die Sache noch einigermaßen einfach. Gekauft oder nicht gekauft. Das ist hier die (einzig relevante) Frage. Was aber, wenn man solche eindeutigen Anhaltspunkte nicht hat? Wenn Objekte nicht gekauft, sondern nur bewertet, verschlagwortet (also mit Tags versehen) oder frei kommentiert werden? Wie zum Beispiel bei Lovely Books. Dann wird’s etwas kniffliger.

Dass es nicht ganz ohne ist, solche Algorithmen effizient und vor allem exakt hinzubekommen, beweist dieser Wettbewerb: $1.000.000 Preisgeld für denjenigen, dem es gelingt, die Treffsicherheit des CF-Systems von Netflix (amerikanischer DVD-Verleiher) um 10 % zu steigern. Nachdem sich aber bereits einige Teams die Zähne daran ausgebissen haben, könnte man vielleicht ebensogut versuchen, die Goldbachsche Vermutung zu beweisen.