Schlagwort-Archive: Formel

„Heiße Themen“: Sortierung bei Hacker News, reddit & delicio.us

Die Sortierung von Nachrichten nach Neuigkeit oder Popularität ist trivial und ohne größeren Einsatz von Gehirnschmalz zu bewerkstelligen: etwa mit dem SQL-Statement ORDER BY date DESC bzw. ORDER BY likes DESC. Möchte man jedoch die Themen ausgeben, die momentan populär sind, kommt man mit einfachen Statements nicht mehr weiter. Im Folgenden werden drei Algorithmen von Hacker News, Reddit und delicio.us vorgestellt, die auch hier auf Englisch zusammengefasst sind.

Intuitiver Hacker News-Ansatz

Der intuitive Ansatz für die Problemstellung ist, solche Themen anzuzeigen, deren Bewertung hoch ist und deren Veröffentlichungstermin noch nicht lange her ist. Sei p die Anzahl der positiven Bewertungen (jeder Benutzer kann bei Hacker News nur eine positive Bewertung pro Thema abgeben) und t die Anzahl der Stunden, seitdem das Thema veröffentlicht wurde:

Algorithmus von Hacker News

Je länger also der Veröffentlichungszeitpunkt her ist, desto größer wird der Nenner. Da der Nenner mit der Potenz von 1,5 pro Stunde wächst, müssen die Votes ebenfalls potenziell mit der Zeit zunehmen, um f_h(p, t) auf gleichem Niveau zu halten.

Auch wenn keine Votes für das Thema eingehen, muss die Bewertungsfunktion f_h(p, t) jede Stunde neu berechnet werden. Dieses Problem hat der Reddit-Algorithmus nicht.

Reddit-Algorithmus

Anstatt die Bewertungen mit der Zeit exponentiell zu senken, bleibt bei Reddit die Bewertung über die Zeit gleich. Neue Themen erhalten stattdessen einen höheren Summanden, sodass ihre Bewertung höher ist. Der Reddit-Algorithmus ist etwas umfangreicher und passt nicht in eine einfache Formel. Zunächst definieren wir t_s als Differenz der Sekunden zwischen dem 08.12.2005 07:46:43 und dem Veröffentlichungsdatum des Themas:

t_s

Warum Reddit gerade den 08.12.2005 gewählt hat, ist nicht bekannt..

Da man bei Reddit sowohl positiv als auch negativ bewerten kann, wird x als Differenz der positiven (U) und negativen (D) Bewertungen definiert:

x

Wir definieren y als Signum- oder Vorzeichenfunktion von x. Wenn x > 0, ist y = +1. Wenn x = 0, ist y =0. Wenn x < 0, ist y = -1:

y

Und schließlich definieren wir z wie folgt

z

Ist der Betrag von x = 0, wird 1 genommen, sonst der Betrag von x.

Kommen wir zur eigentlichen Bewertungsfunktion. Mit dieser Funktion werden die Themen bewertet, sodass jene Themen mit der höchsten Bewertung die „heißen Themen“ darstellen:

Algorithmus von reddit

Funktionsgraph des Zehnerlogarithmus
Funktionsgraph des Zehnerlogarithmus (Quelle:Wikipedia)

Der erste Summand ist der „Bewertungssummand“. Wir sehen anhand des Funktionsgraph des Zehnerlogarithmus rechts, warum z so gewählt ist, dass er mindestens 1 ist. Der Summand ist somit immer 0 oder positiv sein.

Der Eintrag mit der höchsten Bewertung bei Reddit hat ein x von 21875. Der erste Summand ist bei diesem Eintrag also
Erster Summand: reddit

Der zweite Summand ist der „Zeitsummand“. y gibt aufgrund positiver/negativer/neutraler Bewertungen an, ob der Zeitsummand addiert, subtrahiert oder gar nicht berücksichtigt werden soll.

t_s ist die Zeitdifferenz in Sekunden. Schauen wir uns ein paar Beispiele an und stellen (Oh, Wunder!) fest, dass t_s mit der Zeit immer größer wird:

t_s Jetzt

t_s 2009

t_s wird noch durch 45.000 geteilt. 45.000 Sekunden sind 12,5 Stunden. Der Zeitsummand erhöht sich also alle 12,5 Stunden um 1. Das bedeutet, dass innerhalb von 12,5 Stunden der Bewertungssummand um 1 zulegen müsste, um das höhere Alter des Beitrags zu kompensieren. Der Bewertungssummand steigt um 1, wenn die Differenz zwischen positiven und negativen Bewertungen, um die Zehnerpotenz zunimmt. Von 1 auf 10 ist ja noch easy, aber es wird immer härter: von 10 auf 100, von 100 auf 1000, von 1000 auf 10.000 etc.

Ein Problem an dem Reddit-Algorithmus ist, dass die Bewertungen aufgrund des „Zeitsummands“ immer weiter steigt und man irgendwann an Grenzen von Speichergrößen stoßen wird. Wann dieser Zeitpunkt erreicht ist, habe ich nicht errechnet.. Vielleicht liefert ja ein Leser das Datum nach? ;)

HOT & delicio.us

Generell muss man sich die Frage stellen, ob die zwei genannten Algorithmen wirklich das liefern, was gerade populär ist. Auf meinem Blog beobachte ich nämlich zwei verschiedene Besucher- und Aktivitätsverläufe. Zum Einen den Blockbuster-Verlauf, sprich: gerade einen Artikel veröffentlicht und sofort Kommentare und Besucher. Und zum Anderen den Sleeper-Verlauf: der Artikel wird veröffentlicht und erst nach Monaten oder Jahren von den Besuchern entdeckt. Auch wenn der Sleeper-Verlauf seltener auftritt, bekommen „Hacker News“- und Reddit-Besucher nichts davon mit, weil das Thema, obwohl es gerade „hot“ ist, zu alt ist, um in den „heißen Themen“ zu landen.

Bei aktuellen Nachrichten ist der Sleeper-Verlauf vernachlässigbar, aber bei Bookmarks wie bei delicio.us, kann es sehr wohl relevant sein, dass ein „alter Bookmark“ gerade wieder „hot“ ist. delicio.us hat daher einen einfachen Ansatz, um heiße Bookmarks zu erkennen:

  • Welche Links wurden in der vergangenen Stunde am häufigsten gebookmarkt?

Fazit

Es gibt verschiedene Ansätze „heiße Themen“ zu erhalten.

  • Der intuitive Ansatz von Hacker News ist mit höherem Aufwand verbunden, da sich jede Stunde die Bewertung ändert und neu berechnet werden muss. Der Sleeper-Verlauf wird zudem nicht erkannt.
  • Der Reddit-Algorithmus bedeutet weniger Aufwand, allerdings erkennt er den Sleeper-Verlauf nicht.
  • Der delicio.us Ansatz erkennt zwar Blockbuster und Sleeper-Verlauf, allerdings kann nicht garantiert werden, dass auf kleinen Plattformen mit wenig User-Aktionen ausreichend Bewertungen vorhanden sind. Wenn keine oder wenig Bewertungen in dem Zeitraum abgegeben wurden, können keine „heiße Themen“ angezeigt werden.

Asus Service – Die Null bleibt stehen

Ihr kennt doch bestimmt diese tollen Firmenmail-Footer, wo nochmal die Anschrift, Mailadresse und Telefonnummer drin steht, oder? Schön verziert mit dem Firmenlogo und irgendeinem tollen Slogan. Bei Asus-Mitarbeitern steht dort der Slogan

About ASUS:
The Asus Winning Formula:
Winning = Marketing(Quality*Speed*Innovation*Service)/Cost

Ins Deutsche übersetzt (schließlich gilt „Wir sind hier in Deutschland„):

Über Asus:
Die ASUS Gewinnformel:
Gewinn = Marketing(Qualität*Geschwindigkeit*Innovation*Service)/Kosten

Mir ist jetzt nicht so ganz klar, worauf sich Speed/Geschwindigkeit bezieht, aber wenn der Service eine 0 ist, dann sollte auch die Asus Gewinnformel Null werden.

Ich würde nie wieder einen Computer von Asus kaufen und das liegt alleine an folgenden Umständen:

  1. mein Notebook ist seit dem 21.07. bei Asus in Reperatur
  2. mir wurde zwar nach einem Monat eine Gutschrift angeboten, diese kann ich laut Asus aber nicht in Anspruch nehmen, weil der Händler in Insolvenz gegangen ist (das Notebook habe ich bei einem Händler namens e-bug bei Amazon gekauft, damals hieß der Händler „BUG Computer Components AG„. Die Domain e-bug.de wurde dann von der „Computer Components GmbH“ übernommen. Ein Schelm, wer Böses dabei denkt…)
  3. Asus reagierte auf meine Mail nicht, in der ich um Auskunft bat, bis wann sie die Reparatur abgeschlossen haben
  4. Ich setzte eine zweiwöchige Frist, in der sie mir Auskunft geben sollten. Diese Frist verstrich.
  5. Erst nach einem Anruf bekam ich eine Mail, dass die Reparatur weitere 3-4 Wochen in Anspruch nehmen würde.
  6. Diese 4 Wochen verstrichen erneut ohne Reaktion. Ich telefonierte mit Asus.
  7. Ich bekam eine Mail mit der Aussage, dass auf ein Ersatzteil gewartet wird, welches frühestens am 25.10. bei Asus eintreffen wird. Frühestens.. *haha*
  8. Ich schrieb Asus erneut eine Mail, dass es ja wohl absolut inakzeptabel sei, dass man über 3 Monate auf die Reparatur warten muss. Ich setzte eine allerletzte Frist bis zum 09.11., in der ich mit einem Anwalt drohte.

[youtube CLfzfC3JXAw]

Und jetzt ist die letzte Frist fast abgelaufen und ich muss mir Gedanken machen, ob ich einen Anwalt für *** EUR beauftrage gegen ASUS vorzugehen. Ich würde ja gerne ein solches Serviceverhalten durch einen Anwalt abstrafen lassen, aber ich glaube, ich spare lieber das Geld, lasse hier meine Wut raus und gestalte die ASUS Gewinnformel durch mein schädliches Word of Mouth-Marketing noch etwas negativer! Suckers!

Differentiation

In der heutigen Prüfung war ich mir bei den Formeln sehr unsicher, was daran lag, dass vorher gesagt wurde, man müsse die Formeln nicht explizit hinschreiben können, sondern die Zusammenhänge verstehen. Es kann mir mittlerweile aber egal sein, denn die Prüfung bestand ich mit einer 2.

Witzig war aber folgende Situation:
Ich: „[…] und dann gibt es als weiteres Theorem der Fourier-Transformation noch das Differ… das Diff… das Ableitungstheorem.“
Prüfer: „Sie hätten ruhig „Differentiationstheorem“ sagen können…
Ich: „Das ist mir zu kompliziert auszusprechen..“
*lach*

In so einer Situation kann man zweierlei Dinge tun:

  1. Auf Konfrontationskurs gehen à la „Es ist mir schon klar, dass man auch Differentiationstheorem sagen kann! *grummel*“
  2. Die Situation in Humor auflösen

Wobei Humor ja durchaus ein Quäntchen Wahrheit beinhalten darf: In dem Moment kam ich immer wieder auf den eigentlich üblichen Begriff „Differenzierung“. Ich wusste aber, dass im Skript ein anderer Begriff genannt wurde, über den ich immer wieder gestolpert bin: Differention? Differentation? Differentiation? Alles komisch, irgendwie!?!

Wie auch immer: Das war meine letzte formale/theoretische Prüfung, die ich in meinem Studium bestehen musste. Jetzt kommt nur noch easy come, easy go:

  • Datenbank-Prüfung im Oktober
  • eine Vertiefungsprüfung (wahrscheinlich im Bereich Agenten)
  • eine BWL-Prüfung fürs Nebenfach

Es ist also ein Ende absehbar, wobei noch ein Seminar und Projekt abgeschlossen werden müssen.. Aber das macht ja auch deutlich mehr Spaß als das Differentiationstheorem auswändig zu können…