eitelkalk Blogs Empfehlungssysteme – Teil 2: Kollaboratives Filtern
Empfehlungssysteme – Teil 2: Kollaboratives Filtern 28.06.2017 - 17:28 2
Folgenden Nutzern gefällt das Design: damios, krazun

Demnächst folgt auf Pewn eine Anzeige von empfohlenen Spielen für jeden einzelnen Nutzer, wie man sie von mittlerweile so gut wie allen Seiten im Web kennt. Hauptsächlich benutzt wird dafür Recown, eine von mir entwickelte Bibliothek für Empfehlungen. Vor mehr als einem Jahr hatte ich schon einmal daran gearbeitet und ein inhaltsbasiertes Filtersystem vorgestellt, das heute bei den Spielen für die „Anzeige der ähnlichen Spiele“ zuständig ist.

Ich werde hier kurz erklären, wie die Erstellung von Spieleempfehlungen funktioniert. Recown ist open source, der Quellcode kann auf Gitlab eingesehen werden. Wer es nicht abwarten kann und schon einmal sehen möchte, welche Spiele ihm oder ihr vorgeschlagen werden könnten, kann einen Blick auf eine ziemlich lang geratene Beispielausgabe werfen, die mit den Daten von Pewn über die Pewn API arbeitet.

Das Prinzip

Ein Bild sagt mehr als tausend Worte und in diesem Fall gibt es auf der englischsprachigen Wikipediaseite zu kollaborativem Filtern eines, das die Grundzüge perfekt beschreibt:

Kollaboratives Filtern

Abbildung 1. Funktionsweise von kollaborativem Filtern.
(von Wikipedia-User Moshanin, veröffentlicht unter einer CC BY-SA 3.0 Lizenz)

Das Prinzip ist also sehr einfach: Für einen User wird zuerst anhand der Bewertungen nach ähnlichen Usern gesucht, und anschließend auf Grundlage ihrer Bewertungen die Bewertung für ein Item abgeschätzt. Diese zwei Schritte sind schon alles, was man für persönliche Empfehlungen benötigt.

Schritt 1 – ähnliche User bestimmen

Ähnlichkeit ist bei Empfehlungsdiensten ein sehr wichtiger und zentraler Punkt. Erinnern wir uns an Teil 1, das inhaltsbasierte Filtern, dann wurden dort ähnliche Spiele anhand der Kosinus-Ähnlichkeit ermittelt. Das könnten wir bei Usern nun ebenfalls machen und das wird auch von Recown unterstützt. Recown bietet aber noch einen alternativen Ansatz an, der unter Umständen bessere Ergebnisse liefern kann, die Pearson-Korrelation. Die Pearson-Korrelation misst, wie sehr zwei Nutzer in ihren Bewertungen übereinstimmen (also wie die Kosinus-Ähnlichkeit), betrachtet dabei aber nur die gemeinsam bewerteten Spiele und bezieht die durchschnittliche Bewertung der User mit ein. Am Beispiel:

atzimmer und krazun sind zum einen zwei recht aktive Nutzer, zum anderen haben sie auch recht viele Bewertungen abgegeben, weshalb ich sie mir hier einmal herauspicke. Gemeinsam bewertet haben sie nur drei Spiele: Respawn Attack (atzimmer 6 Sterne, krazun 7 Sterne), The Dead Beneath (atzimmer 7 Sterne, krazun 8 Sterne) und Bomberman (atzimmer 5 Sterne und krazun 7 Sterne).

Nach der Kosinus-Ähnlichkeit würden sie zu 18 % übereinstimmen, es gibt jeweils eine Menge anderer Spieler, die ihnen deutlich ähnlicher sind. Tatsächlich haben sie ja bei den drei gemeinsamen Spielen andere Bewertungen abgegeben. Nach der Pearson-Korrelation stimmen beide aber zu 79 % überein. Zwar haben beide unterschiedlich bewertet, krazun liegt aber jeweils immer ein bis zwei Sterne über der Bewertung von atzimmer. Das reicht aber noch nicht aus. Ein Blick auf die durchschnittliche Bewertung zeigt, dass krazun im Schnitt knappe 7 Sterne vergibt, atzimmer ist kritischer und vergibt durchschnittlich 4 Sterne. Das heißt, dass die 3 Spiele von beiden jeweils (über)durchschnittlich bewertet wurden und erklärt die starke Ähnlichkeit der beiden, die durch die Kosinus-Ähnlichkeit nicht zu erkennen war. Mit der Pearson-Korrelation ist krazun nun sogar der Spieler, der atzimmer am zweitähnlichsten ist.

Wichtig ist bei dem Begriff der Ähnlichkeit, dass man ihn nicht zu eng sieht. Je nach Anwendungsfall kann die eine Ähnlichkeitsbestimmung passender sein als die andere. Das hängt von verschiedenen Faktoren ab, zum Beispiel der Anzahl abgegeben Bewertungen. Recown unterstützt auf jeden Fall beide Varianten, sodass die passendere gewählt werden kann.

Schritt 2 – Bewertung vorhersagen

Haben wir eine Abschätzung dafür, welche Nutzer sich ähnlich sind, können wir anhand ihrer Bewertungen eine Vorhersage für Spiele treffen, die ein User noch gar nicht bewertet hat.

Bleiben wir beim Beispiel von atzimmer. Neben krazun sind noch damios und jonnydjango ähnliche Nutzer. Gehen wir die Spiele durch, die diese drei bewertet haben, aber atzimmer nicht, stoßen wir auf eine ganze Menge an Spielen. Recown zieht nun aber die schon erwähnte Ähnlichkeit der User zu atzimmer in Betracht und ihre Bewertungen, wieder bezogen auf die durchschnittlichen Bewertungen. Die Top 5 Empfehlungen für atzimmer sind demnach mit geschätzter Bewertung:

  1. Gatio - Die Zeit vergeht, nicht aber wir (7,6 Sterne)
  2. Just Get Through (6,8 Sterne)
  3. Bard's Gold (6,6 Sterne)
  4. Canyonbreed (6,6 Sterne)
  5. Twee World, 2D Online Mehrspieler Indie, Open World (6,1 Sterne)

Also allesamt Spiele, die atzimmer voraussichtlich überdurchschnittlich bewerten würde. Ob und wie gut die Empfehlungen sind, kann er ja vielleicht selber mal sagen wink

Ausblick

Wie schon beim inhaltsbasierten Filtern die Hashtags eine tragende Rolle gespielt haben, sind hier vor allem die Bewertungen entscheidend. Davon gibt es leider sehr wenige. Im obigen Beispiel basieren die Empfehlungen für atzimmer auf jeweils einer Bewertung der ähnlichen User – ein Grund, warum vielleicht die Kosinus-Ähnlichkeit (für atzimmer) doch passender sein könnte, da sie mehr ähnliche Nutzer anzeigt.

Das Problem weniger Bewertungen ist allerdings ein Problem, das nicht nur Pewn betrifft, sondern alle Empfehlungssysteme, die auf kollaborativem Filtern basieren. Deswegen hat es sogar einen Namen bekommen, nämlich „Data sparsity“. Möglichkeiten, wie Pewn das Problem umgehen könnte und zum Teil auch wird:

  • Likes in die Bewertung mit einbeziehen – Das wird kommen. Ein Like geht leichter von der Hand und es gibt viel mehr Likes als Bewertungen. Allerdings sind Likes damit auch nicht ganz so aussagekräftig.
  • Ist das Spiel in der Playlist eines Users? – Wird auch kommen. Bietet noch mehr Möglichkeiten der Bewertung, ist aber noch ungenauer. Playlist bedeutet ja meist, dass der User das Spiel noch gar nicht gespielt hat.
  • Implizite Bewertungen – So etwas wie Aufrufrate eines Spiels, Scrollweite, Likes für Blog- und Designbeiträge, Suchanfragen, Verweildauer auf einer Spieleseite, Downloads… Das gäbe die Möglichkeit, Bewertungen anhand vieler Faktoren zu erstellen, ohne dass der User explizit eine Bewertung abgibt. Wird aufgrund des Umfangs erst einmal nicht kommen.

Zusätzlich zu den beschriebenen Empfehlungen unterstützt Recown auch noch weitere Möglichkeiten, Empfehlungen zu geben:

  • Spieler, denen Spiel X gefallen hat, gefällt auch Spiel Y – Bekannt geworden durch Amazon. Bei einem Spiel wird geguckt, wer es gut bewertet hat und dann wird nachgesehen, welche Spiele der User noch gut bewertet hat – diese werden empfohlen.
  • Ähnliche Spiele zu den am besten bewerteten Spielen finden – Verbindet Bewertungen und inhaltsbasiertes Filtern: Zu den am besten bewerteten Spielen eines Nutzers wird nach ähnlichen Spielen gesucht. Recht einfach, aber auch effektiv.
  • Beste Spiele zu beliebten Hashtags anzeigen – Ein hybrider Ansatz, der kollaboratives und inhaltsbasiertes Filtern verbindet. Anhand der Bewertungen eines Users kann abgeschätzt werden, wie gut er oder sie bestimmte Hashtags findet. Bewertet ein Spieler zum Beispiel ausschließlich Spiele mit dem Hashtag „Linux“, kann man dementsprechend Spiele empfehlen – nach obigem Prinzip der vorhergesagten Bewertungen.
  • Alle Spiele zu beliebten Hashtags – Die gerade genannte Variante liefert oftmals kaum Spiele. Einfach alle Spiele zu einem Hashtag anzuzeigen würde mehr Ergebnisse liefern.

Ob, und wie diese Punkte umgesetzt werden, steht noch nicht fest. Die Möglichkeit ist aber da.

Vor allem, wenn Likes noch miteinbezogen werden, denke ich, sollten schon wirklich gute Empfehlungen auf Pewn möglich sein. Wie gut die Empfehlungen sind, könnt ihr dann ja mal kommunizieren wink (Und nochmal: Wer jetzt schon schmulen möchte: Klick)
Edit: Likes sind nun über die Pewn-API abrufbar, ich werde zeitnah ein Update nachreichen.

 

Ich hätte auch große Lust, noch an einem dritten Teil der Serie zu arbeiten. Bisher waren beide Varianten der Empfehlungssysteme sogenannte speicherbasierte. Sehr reizvoll für mich wären nun noch modellbasierte Empfehlungssysteme, bei denen man neuronale Netze mit den entsprechenden Bewertungen füttert und guckt, was dabei herauskommt.


Aktualisiert: 28.06.2017 - 17:54
Grund:
28.06.2017 - 19:47
krazun
In den letzten 60 min online
krazun
Rang 17
Administrator

Projekte: 0
Designs: 2
Blogs: 3
Aktivität:
Aktiv

Yeah, vielen Dank das du dir die Zeit genommen hast die Theorie dahinter so ausführlich zu erklären. Sehr spannend was da alles an Theorie hinter solchen Empfehlungs-Systemen steckt

Wenn du irgendwann noch einen weiteren Blogbeitrag zu dem Thema schreibst fände ich das toll und würden diesen ebenso interessiert verschlingen wie den hier!

krazun
In den letzten 60 min online
krazun
Rang 17
Administrator

Projekte: 0
Designs: 2
Blogs: 3
Aktivität:
Aktiv
Administrator