eitelkalk Blogs Empfehlungssysteme – Teil 1: Inhaltsbasiertes Filtern
Empfehlungssysteme – Teil 1: Inhaltsbasiertes Filtern 10.03.2016 - 14:41 0

Hier auf pewn.de sind nach mittlerweile über anderthalb Jahren schon 155 Spiele eingetragen – das sind fast 2 Spiele pro Woche. Da braucht man gerade als neuer Benutzer schon eine ganze Weile, bis man die alle gesichtet hat und ein paar für einen selbst interessante Spiele gefunden hat. Zum Glück gibt es vielfältige Möglichkeiten, wie man die Auswahl einschränken kann: Nach Bewertungen gehen, nach den Charts, bei den Entdeckungen stöbern… durch all diese Möglichkeiten habe ich schon selbst das ein oder andere Juwel hier entdeckt.

Doch nehmen wir einmal an, ich habe mich neu auf pewn registriert und suche nach Spielen, die mich interessieren. Ich gehe in die Spieledatenbank und lasse mir alle Spiele mit dem Hashtag „sciencefiction“ anzeigen – wow, gerade mal ein Ergebnis, eXperinox. Na gut, es sieht ziemlich gut aus, die Bewertungen sind dementsprechend, vielleicht spiele ich es sogar an und es gefällt mir. Aber: gibt es nicht noch mehr Spiele in diese Richtung, die mir auch gefallen könnten?

Jetzt könnte ich selbst anfangen, nach ähnlichen Spielen zu suchen. Vielleicht komme ich noch auf das Hashtag „scifi“, oder auf die Idee nach weiteren „weltraum“-Spielen zu gucken. Vielleicht aber auch nicht. Das ist der Punkt, an dem Empfehlungssysteme ansetzen. Nicht den User suchen lassen, sondern dem User schon passende Spiele vorschlagen, bevor er überhaupt auf die Idee kommt zu suchen. „Wenn Dir dieses Spiel gefällt, könnten Dir auch die folgenden gefallen…“ – inhaltsbasiertes Filtern nach möglichen, passenden Spielen.

Ich habe mal eine total stupide und naive Implementierung eines solchen Empfehlungssystems vorgenommen und testweise auf die Spiele bei pewn losgelassen. Der Aufwand war überraschend gering und die Ergebnisse überraschend gut. Den Java-Quellcode gibt es auf gitlab, ich werde hier kurz die Grundzüge erläutern und ein paar Ergebnisse präsentieren.

Das Prinzip

Ziel ist es also, zu einem gegebenen Spiel (oder allgemeiner „Item“) aus allen anderen Spielen diejenigen auszuwählen, die „am besten“ dazu passen. Doch wie ermitteln wir, wie gut zwei Spiele zueinander passen?

Das Schöne an pewn ist, dass jedes Spiel Hashtags hinzufügen kann. In je mehr Hashtags zwei Spiele übereinstimmen, desto ähnlicher sind sie sich wahrscheinlich. Schauen wir uns z. B. die drei Spiele eXperinox, Final Cumeda und Realms of Gondar mit ihren Hashtags an:

e: action, mmo, strategie,        sciencefiction, weltraum, browsergame, browserspiel
f: action, mmo, strategie, scifi,                 weltraum, browsergame,              simulation
r:                                                                                    simulation

Für jedes Hashtag, das im Spiel vorkommt, schreiben wir eine 1, für jedes, das fehlt, eine 0. Somit erhalten wir die Vektoren

e = (1, 1, 1, 0, 1, 1, 1, 1, 1, 0)
f = (1, 1, 1, 1, 0, 1, 1, 1, 0, 1)
r = (0, 0, 0, 0, 0, 0, 0, 0, 0, 1)

Wie intuitiv klar sein sollte, sind sich eXperinox und Final Cumeda ähnlicher als Realms of Gondar und Final Cumeda. Sie stimmen in vielen Hashtags überein, Realms of Gondar stimmt zwar in 100 % seiner Hashtags mit Final Cumeda überein, hat aber auch nur dieses.

Ein (gutes) Maß zur Bestimmung der Ähnlichkeit ist nun die Kosinus-Ähnlichkeit, bei der die Winkel zwischen den Vektoren berechnet werden. Das liefert:

sim(e, f) = 5/7       = 0,714…
sim(r, f) = 1/sqrt(7) = 0,377…

Die Werte werden sich bei uns zwischen 0 und 1 bewegen, wobei 0 keiner Übereinstimmung entspricht und 1 einer vollständigen.

Werfen wir nun einen Blick auf die Hashtags aller Spiele, so stellen wir fest, dass einige Hashtags von ziemlich vielen Spielen verwendet werden und einige von zum Teil nur einem einzigen. Das Hashtag „windows“ wird z. B. sehr oft verwendet und ist natürlich nicht so aussagekräftig für die Ähnlichkeit zweier Spiele wie das viel seltenere Tag „puzzle“. Das können wir allerdings ausnutzen, um unsere Ergebnisse zu verbessern. Wir schätzen die Wichtigkeit eines Hashtags z. B. durch das „Tf-idf-Maß“ ab. Die Idee: in je mehr Spielen ein Hashtag vorkommt, desto unwichtiger wird es. Wir setzen dann den Wert im Vektor nicht mehr wie oben auf 1, sondern auf das zuvor berechnete Gewicht des Hashtags. Und die Ergebnisse können sich zum Teil sehen lassen.

Ausgewählte Ergebnisse

Mit der vollständigen Implementierung kann jede(r) Interessierte gerne selbst ein bisschen herumspielen, eine Liste der Spiele mit den jeweils 5 besten Empfehlungen ist auch verfügbar (werde ich aber voraussichtlich nicht aktualisieren). Ich werde hier nur kurz auf einige (in meinen Augen) interessante Ergebnisse eingehen.

Kehren wir noch einmal zu unserem Ausgangsbeispiel zurück: Was wird uns nun empfohlen, wenn wir gerade eXperinox betrachten? Final Cumeda, Da Vincis Erbe, PLANExT, Tycoopoli$ und Antares Open World – allesamt Spiele, die in meinen Augen sehr gut passen und die z. T. doch ein bisschen überraschend sind. Tatsächlich hat auch der Hälfte der Spieler, denen eXperinox gefällt, auch mindestens eines der anderen 5 gefallen – wie vom Modell gut vorhergesagt wurde.

Gerade Hashtags wie „Strategie“ und „Simulation“ liefern eine eigene „kleine Wolke“ von 9 Spielen, die sich allesamt gegenseitig „empfehlen“. Da taucht nur ganz selten eine Empfehlung auf, die nicht wirklich reinpasst. Hier sieht man schon einmal, wie hilfreich ein gutes Hashtag ist – am besten einfach mal selbst ausprobieren.

Weitere gute Empfehlungen kann man sogar auch erhalten, wenn ein Hashtag gar nicht existiert, die Zusammenhänge aber dennoch (durch andere Tags) aufgedeckt werden. So vermisse ich zum Beispiel schon seit geraumer Zeit ein Hashtag „pointandclick“ oder so ähnlich. Genügend Spiele, die dafür in Frage kämen, gäbe es. Gatio kündigt sich selbst z. B. mit „GATIO - ein Point & Click Adventure“ an, benutzt ein passendes Tag aber nicht. (Das Hashtag „pac“ wird nur von Gatio verwendet und soll eigentlich „pac-dk“ heißen, wird aber zu „pac“ geparst). Dennoch werden erstaunlich passende Spiele vorgeschlagen: Space Geekz - Die KnusperflockenverschwörungNo Way OutSherlock Holmes und die ThorbrückeSkazka und The Forgotten Time. 3 davon ebenfalls Point & Click Adventure.

Ausblick

Ein inhaltsbasiertes Empfehlungssystem steht und fällt mit dem „Inhalt“, in diesem Fall den Hashtags. Die sind bei vielen Spielen bisher recht schwach, bei vielen sogar nicht einmal vorhanden. Ein gutes Beispiel hierfür ist u. a. das Hashtag „snake“. Limousnake und Battle Snakes verwenden es beide und haben dadurch beide eine sehr hohe Übereinstimmung. Andere Snake-Spiele wie Hexagon-Snake oder der Snake-Klon benutzen es nicht und tauchen deshalb momentan auch nicht als Empfehlungen bei den anderen beiden auf.

Wird das verbessert (z. B. dadurch, dass User Hashtags hinzufügen können oder Entwickler deutlich auf „gute“ und viele Hashtags hingewiesen werden), könnten schon mit wenig Aufwand richtig gute Empfehlungen erreicht werden – und Amazon, eBay, Last.fm, IMDb und viele, viele andere machen vor, wie hilfreich Vorschläge für die Nutzer sind.

Sehr zu empfehlen ist auch der (englische) Wikipedia-Artikel zum Thema: Recommender System.

Wenn Ihnen dieser Blog-Eintrag gefallen hat, gefällt Ihnen vielleicht auch dieser: „Empfehlungssysteme – Teil 2: Kollaboratives Filtern“.  (Verfügbar, sobald in der pewn-Api auf Bewertungen zugegriffen werden kann.)


Aktualisiert: 19.06.2017 - 18:08
Grund:
13.03.2016 - 14:50
Slayer
In den letzten 60 min online
Slayer
Rang 12

Projekte: 2
Designs: 2
Blogs: 7
Aktivität:
Inaktiv

Servus eiteltalk!

Ah - der Ungesehene Beiträge (1) - Crasher wink. Ist ein Insider - ich denke, dass die Blog-News den Bug ausgelöst hatten, der an anderer Stelle schon angemerkt wurde.

Zum Beitrag: ich finde diesen Beitrag zu Empfehlungssystemen sehr interessant. Vor allem auch deshalb, weil du ein praktisches Beispiel umgesetzt hast, welches sehr gut zu funktionieren scheint.

@Krazun: könnte man etwas in der Art nicht direkt bei Pewn einbauen? Das Fände ich super!

Have fun und danke eiteltalk!
Slayer

Slayer
In den letzten 60 min online
Slayer
Rang 12

Projekte: 2
Designs: 2
Blogs: 7
Aktivität:
Inaktiv
13.03.2016 - 14:58
damios
In den letzten 60 min online
damios
Rang 18
Administrator

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

Sehr interessanter Blogeintrag  Du hattest ja schon vor einiger Zeit angekündigt, dass du etwas mehr zu deinem Empfehlungssystem schreiben möchtest - schön dass du endlich Zeit dafür gefunden hast! Mit ein bisschen Glück sehen wir das ganze System vielleicht ja schon im nächsten Update von Pewn 

damios
In den letzten 60 min online
damios
Rang 18
Administrator

Projekte: 3
Designs: 2
Blogs: 11
Aktivität:
Aktiv
Administrator
14.03.2016 - 08:28
Ersteller
eitelkalk
In den letzten 60 min online
eitelkalk
Rang 12
Moderator

Projekte: 2
Designs: 0
Blogs: 5
Aktivität:
Inaktiv

Ich danke euch beiden.

Ah - der Ungesehene Beiträge (1) - Crasher wink. Ist ein Insider - ich denke, dass die Blog-News den Bug ausgelöst hatten, der an anderer Stelle schon angemerkt wurde.

So langsam macht es erst klick bei mir, musste eine ganze Weile überlegen, was du meinst . Sehe ich das richtig, dass dieser (als Entwurf gespeicherte) Blog-Eintrag als „ungesehener Beitrag“ gezählt, aber nicht angezeigt wurde? Hätte ich das gewusst, hätte ich mich mehr beeilt 

 […] schön dass du endlich Zeit dafür gefunden hast!

Hehe, ich hatte das immer im Hinterkopf und die größte Verzögerung gab es eigentlich, weil ich „nur noch schnell mal was ausprobieren“ wollte. Das war dann aber immer komplizierter und hat – etwas überraschend – zu schlechteren Ergebnissen geführt. (Z. B. nicht nur die Hashtags einbeziehen, sondern die gesamte Spielebeschreibung.)

Ersteller
eitelkalk
In den letzten 60 min online
eitelkalk
Rang 12
Moderator

Projekte: 2
Designs: 0
Blogs: 5
Aktivität:
Inaktiv
Moderator
15.03.2016 - 15:47
krazun
In den letzten 60 min online
krazun
Rang 17
Administrator

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

 Echt toller Blogpost, vielen Dank dafür! Hat echt spaß gemacht deinen Ausführungen zu folgen. Finde das System echt gut und denke auch mit ein bischen mehr Hashtag pflege oder Funktionen die den Nutzern erlaubern Spiele zu taggen (Wie man es von Steam kennt) kommen da echt passende Ergebnisse bei raus. So ein Empfehlungskasten steht ja schon länger auf der ToDo, bisher hatte ich mir nur über einen vernünftigen Algorithmus dafür noch keine Gedanken gemacht. Muss ich ja nu auch nicht mehr, danke ;)

Ah - der Ungesehene Beiträge (1) - Crasher wink. Ist ein Insider - ich denke, dass die Blog-News den Bug ausgelöst hatten, der an anderer Stelle schon angemerkt wurde.

So langsam macht es erst klick bei mir, musste eine ganze Weile überlegen, was du meinst . Sehe ich das richtig, dass dieser (als Entwurf gespeicherte) Blog-Eintrag als „ungesehener Beitrag“ gezählt, aber nicht angezeigt wurde? Hätte ich das gewusst, hätte ich mich mehr beeilt 

Habe auch gegrübelt, aber Entwürfe sollten natürlich dort nicht mit reinzählen. Werde dies überprüfen und korrigieren, sonst wird man ja kirre wenn man verzweifelt versucht den neuen Beitrag zu finden der noch nicht angezeigt wird ;)

@Krazun: könnte man etwas in der Art nicht direkt bei Pewn einbauen? Das Fände ich super!

Jap! Da eitelkalk ja schon den Gehirnschmalz investiert hat, brauch ich mich ja nur bedienen ;) Freu mich schon auf Teil 2, nachdem die API ergänzt wurde!

krazun
In den letzten 60 min online
krazun
Rang 17
Administrator

Projekte: 0
Designs: 2
Blogs: 3
Aktivität:
Aktiv
Administrator
21.03.2016 - 17:10
krazun
In den letzten 60 min online
krazun
Rang 17
Administrator

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

(Verfügbar, sobald in der pewn-Api auf Bewertungen zugegriffen werden kann.)

Eigentlich sollte das nächste Update erst kommen wenn das Team-System funktioniert, aber da ichs cool finde wie Kreativ die Pewn-API genutzt wird habe ich einen Mini-Update zwischengeschoben, da ich die Funktionen ohnehin schon fertig hatte.

Einmal gibt es eine API-Methode um auf die Bewertungen für ein Spiel zuzugreifen und dann noch eine Methode um an die Hashtags/Metatags und Kategorien für ein Spiel zu kommen.

krazun
In den letzten 60 min online
krazun
Rang 17
Administrator

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